基于ASIFT的圖像快速匹配算法

李校林，劉 欣

(1.重慶郵電大學，重慶400065;2.重慶信科設計有限公司，重慶400065)

基于ASIFT的圖像快速匹配算法

李校林1，2，劉 欣1

(1.重慶郵電大學，重慶400065;2.重慶信科設計有限公司，重慶400065)

ASIFT特征在圖像旋轉、尺度變換和視角變化的條件下具有良好的不變性，較傳統(tǒng)的SIFT算法具有完全的仿射不變性，且在圖像配準中能夠獲得更多精確的匹配點。但是，ASIFT匹配效率比較低，耗時較長?；贏SIFT的圖像快速匹配算法是結合基于BBF查詢機制的KD－Tree索引的近似最近鄰搜索即先建立數(shù)據集索引，然后進行快速匹配的算法。實驗結果表明，改進的算法比傳統(tǒng)的ASIFT圖像匹配算法和SIFT匹配算法在匹配速度、匹配精度方面優(yōu)勢明顯。

ASIFT;匹配效率;SIFT;BBF;KD－Tree

圖像匹配技術［1］是圖像處理中一項重要的技術，同時也是計算機視覺研究中一項非常重要的工作。隨著科學技術的發(fā)展，圖像匹配技術在醫(yī)學圖像處理分析、圖像三維重建、天氣預測、圖像數(shù)據庫檢索、圖像拼接、目標識別等多個領域中都有廣泛的應用。所謂圖像匹配，就是將相同或者不同場景的二幅或者多幅圖片在空間上進行配準。目前的圖像匹配方法主要有基于區(qū)域灰度的匹配方法［2］、基于圖像解析的匹配方法［3］以及基于特征的匹配方法［4］。其中最常用的是基于特征的圖像匹配方法，該方法通過對圖像特征點分析，提高圖像的匹配速度，且提取的圖像特征點對旋轉、亮度變化、尺度縮放保持不變性，對視角變化、仿射變化、噪聲也具有良好的穩(wěn)定性。

SIFT(Scale Invariant Feature Transform)算法［5－6］是1999年Lowe提出的，于2004年加以完善。SIFT算法將斑點檢測和特征矢量生成、特征點搜索匹配等步驟完整地結合在一起，能夠很好地解決環(huán)境因素、成像器材本身的成像特性因素、目標遮擋等影響造成的圖像變形問題。但是SIFT在對一些目標傾斜的圖片不能檢測到更多精確的特征點進行配準，并且存在錯誤匹配，不能滿足實時配準的要求。

ASIFT(Affine Scale Invariant Feature Transform)［7］是一種完全仿射不變的局部圖像特征提取算法，由Jean－Michel Morel和Guoshen Yu在2009年提出。ASIFT算法除了對旋轉、縮放、平移具有完全不變性以外，還對SIFT不具備的相機軸方向和相機角度方向具有完全不變性，所以ASIFT在仿射較大造成變形的圖像上能夠得到更多精準的特征點，在配準方面具有良好的效果。但由于算法本身計算復雜，所以算法存在運算速度較慢、配準重復、誤匹配等問題。所以，在實時性上存在一定缺陷。

通過對SIFT和ASIFT算法進行深入研究，在ASIFT特征點匹配階段結合基于BBF(Best－Bin－First)查詢機制的KD－Tree索引的最近鄰搜索策略實現(xiàn)圖像快速匹配。KD－Tree的BBF查詢算法的引入能夠較大程度地減少計算量，大大提高ASIFT的匹配速度。

1 ASIFT匹配算法介紹

ASIFT算法是在SIFT算法的基礎上提出，該算法對攝像機的經度角和緯度角同樣具有完全不變性，這就解決了傳統(tǒng)SIFT算法在仿射較大引起的圖片之間匹配精確度不足的缺陷。

1.1 ASIFT算法原理

1.1.1 攝像機仿射模型

攝像機采集到的空間平面景物都可以用仿射模型描述為

式中:參數(shù)u表示最終得到數(shù)字圖像;u0表示景物平面圖像;S1表示采樣操作;G1表示高斯卷積;T和R分別表示由攝像機引起的圖像平移和旋轉變換;A表示空間平面景物的仿射變換。

以上模型中A可以簡化為一個仿射變換。任何一個線性仿射變換由于仿射矩陣不存在相似矩陣，所以只存在唯一的分解式子

式中:λ＞0，λt為A的行列式;φ∈［0，π);Tt表示傾斜變換的矩陣，且第一個特征值t＞1，第二個特征值t=1;Ri表示旋轉變換的矩陣。攝像機仿射模型由圖1給出，其中參數(shù)u表示平面景物圖像，右上角小平行四邊形代表觀看u的攝像機的角度位置，參數(shù)φ和θ=arccos(1/t)，分別為攝像機的經度角和緯度角，參數(shù)λ為縮放尺度變化。

圖1 攝像機仿射模擬

1.1.2 不同傾斜角度拍攝仿射模型

將攝像機通過不同傾斜角度得到的2張圖片進行仿射模擬。用A和B分別表示得到的2張不同的圖片，并有u1(x，y)=u(A(x，y))，u2(x，y)=u(B(x，y))。那么二張圖片的變換矩陣BA－1可以描述為

1.2 ASIFT算法主要步驟

1)得到攝像機經度角和緯度角采樣序列

ASIFT算法首先利用式(3)對攝像機的經度角φ和緯度角θ進行采集，來模擬所有可能由攝像機光軸造成的仿射變形來實現(xiàn)圖像變換。其中緯度角的采樣對應傾斜t，且遵循等比數(shù)列采樣的原則，即按1，a，a2，…，an采樣，a＞1，a =時，算法精確度可以達到最佳，所以在本文中取該值，另外n≥5。經度角的采集隨傾斜t變化，且遵循等差數(shù)列采樣原則，即按0，b/t，…，kb/t采樣，取b= 72°［7］，k為滿足條件kb/t＜π的最后一個整數(shù)值。

2)將待匹配圖像進行傾斜旋轉變換

利用采用得到的參數(shù)序列，根據式(1)首先將圖像進行經度角度為φ的旋轉變換，將旋轉變換后的圖像進行模擬傾斜，最終得到仿射變換下的模擬圖片，其中傾斜t=|1/cosθ|。

3)圖像特征點檢測和匹配

將生成的模擬圖片根據SIFT算法進行特征點檢測和圖片匹配。

1.3 ASIFT算法優(yōu)缺點

綜上可知，ASIFT算法在仿射較大圖像之間的匹配性能優(yōu)越，也能夠獲取更多精確的匹配特征點。但是，ASIFT算法在匹配階段采用的傳統(tǒng)SIFT用的全局最近鄰搜索方式，該方式沒有利用數(shù)據集本身包含的任何結構信息，搜索效率比較低，所以造成ASIFT算法在匹配效率上比較低。

2 基于BBF查詢機制的KD－Tree近似最近鄰搜索算法

2.1 KD－Tree算法描述

KD－Tree［8］(K－Demension Tree)是數(shù)據點在K維空間中劃分的一種數(shù)據結構。通過建立有效的數(shù)據索引結構來大大加快檢索的速度。該算法由Jon Louis Bentley在1975年提出。它與二叉樹的不同點是，它的每個節(jié)點表示K維空間的一個點，且每一層都會根據該層的分辨器對應的對象做出分枝決策。

2.2 基于BBF的KD－Tree查詢算法

標準的KD－Tree算法主要分為KD－Tree的構建和數(shù)據最近鄰查詢。標準KD－Tree的最近鄰查詢算法，并沒有考慮查詢路徑數(shù)據本身的性質，所以該算法不適合高維度數(shù)據的應用?？梢灾?，ASIFT描述矢量長度為128，所以采用傳統(tǒng)的KD－Tree最近鄰算法，搜索效率會下降，并且會接近無窮搜索算法，造成圖像匹配效率較低。而通過基于BBF機制的KD－Tree查詢算法，能夠滿足高維數(shù)據下對檢索速度的要求，大大提高了圖片匹配的效率。

2.2.1 KD－Tree構建［9］過程

1)確定split域的值。通過計算數(shù)據點在x，y維度上的數(shù)據方差，取方差值最大的維度作為split域的值。

2)確定Node－data域。根據得到的split域的值，將數(shù)據在該維度上排序，根據數(shù)據的中值得到Node－data域數(shù)據點，這樣，就確定了該節(jié)點的分割超面。

3)確定左、右子空間。分割超面把整個空間分為兩部分，分割超面左邊的點為左子空間，分割超面右邊的點為右子空間。

4)然后根據左子空間和右子空間可以得到一級子節(jié)點，再分別將空間和數(shù)據集進一步細分，直到空間中只包含一個數(shù)據點。

2.2.2 基于BBF機制的KD－Tree查詢算法［9］流程

1)根據數(shù)據點集建立KD－Tree。

2)建立優(yōu)先級隊列，首先把KD－Tree的根節(jié)點壓入隊列。

3)檢測該樹節(jié)點表示的空間中是否有更好的最近鄰，提取出最優(yōu)先節(jié)點。

4)繼續(xù)檢索該最優(yōu)先節(jié)點，重復步驟2)，直到優(yōu)先隊列為空。

3 算法實現(xiàn)及結果分析

本文利用C++語言在VS2010平臺上驗證該算法的性能，算法驗證圖片取自攝像機的拍攝。在這里，利用傾斜角度較大的圖片進行了圖像匹配。匹配結果如圖2和圖3，算法性能參數(shù)見表1。

圖2 基于全局搜索的SIFT算法圖片匹配

從圖2中看出，圖片在匹配過程中，得到的匹配特征點比較少，匹配精確度較差，存在較多的誤匹配。與圖3對比，明顯看出，ASIF算法和SIFT算法相比，不僅能夠檢測到更多的匹配特征點，而且在特征點匹配精度上也具有突出的優(yōu)勢。除此之外，從表1的數(shù)據可以看出，基于KD－Tree BBF查詢的ASIFT算法匹配速度比基于全局搜索的ASIFT算法在圖片匹配階段時間將近縮短一半，該算法綜合了圖片在匹配精度和匹配效率兩方面，是一種比較出色的匹配算法。

圖3 結合KD－Tree BBF查詢的ASIFT算法圖片匹配

表1 算法性能比較

4 小結

本文研究了基于BBF查詢機制的KD－Tree搜索和AISF圖像匹配算法。在提取圖像特征點和生成描述圖像的特征向量前，采用了比SIFT算法更具精準的ASIFT算法。在圖像匹配特征點階段，采取結合BBF KD－Tree查詢算法，提升圖像在匹配階段的耗時。通過二者的結合，從而形成了一種快速的圖像匹配技術。實驗結果顯示，該算法同時兼顧了圖像匹配精確性和圖像匹配效率，且更具有完全的仿射不變性。圖像匹配技術目前是圖像處理應用領域一項重要的技術，在后續(xù)的研究工作中，該算法的匹配實時性和技術應用將是下一步的重點。

［1］張銳娟.圖像配準理論及算法研究［D］.西安:西安電子科技大學，2009.

［2］MORTANIM，SATIONH F.Image templatematching base on ratio ofmean and cent－ral pixel in local area［EB/OL］.［2013－06－02］.http://proceedings.spiedigitallibrary.org/proceeding.aspx?articleid=829671.

［3］BARBARA Z，JAN F.Image registration methods:a survery［J］.Image and Vison Computing，2003，21(11):97－100.

［4］王宏力，賈萬波.圖像匹配算法研究綜述［J］.計算機技術與應用，2008(6):17－19.

［5］LOWE D.Object recognition from local scale－invariant features［C］// Proc.International Journal of Computer Vision.［S.l.］:IEEE Press，2004:1150－1157.

［6］LOWE D.Distinctive image features from scale invariant keypoints［J］.International Journal of Computer Vision，2004(60):91－110.

［7］MOREL J，YU G.ASIFT:a new framework for fully affine invariant image comparison［J］.SIAM Journal on Imaging Sciences，2009(2): 438－469.

［8］BENTLEY J.Multidimensional binary search trees used for associative searching［J］.Commun.ACM，1975，18(2):509－517.

［9］王永明，王貴錦.圖像局部不變性特征與描述［M］.北京:國防工業(yè)出版社，2010.

Fast Image M atching Algorithm Based on ASIFT

LIXiaolin1，2，LIU Xin1
(1.Chongqing University of Posts and Telecommunications，Chongqing 400065，China; 2.Chongqing Information Technology Designing Co.Ltd.，Chongqing 400065，China)

ASIFT in image rotation，scaling and perspective changing conditions have good invariance，compared with the traditional SIFT algorithm，ASIFT have fully affine invariant，and in the image registration，ASIFT can getmore precisematching points.But，ASIFTmatching efficiency is relatively low and time－consuming.Based ASIFT imagematching algorithm is a combination of BBF fast KD－Tree indexes approximate nearest neighbor search for a data set index，then a quick match.Experimental results show that the improved algorithm than the traditional ASIFT imagematching algorithm and SIFT imagematching algorithm in thematching rate，matching accuracy obvious advantages.

ASIFT;matching efficiency;SIFT;BBF;KD－Tree

TP391.41

A

李校林(1968— )，碩士生導師，正高級工程師，主要研究方向為新一代移動通信技術、物聯(lián)網與視頻監(jiān)控技術、天線與電波傳播;

?? 雯

2013－08－28

【本文獻信息】李校林，劉欣.基于ASIFT的圖像快速匹配算法［J］.電視技術，2014，38(13).

科技型中小企業(yè)技術創(chuàng)新基金項目(11C26215113601)

劉 欣(1990— )，碩士生，主研智能視頻監(jiān)控、圖像處理。