文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2015.11.035
中文引用格式： 張格森，陳東生，王懷野，等. 一種圖像局部特征快速匹配算法[J].電子技術應用，2015，41(11)：124-127.
英文引用格式： Zhang Gesen，Chen Dongsheng，Wang Huaiye，et al. A rapid matching algorithm via image local feature[J].Application of Electronic Technique，2015，41(11)：124-127.
0 引言
圖像匹配是指通過圖像分析方法在兩幅或者多幅圖像中尋找同名點的過程[1]。圖像匹配是機器視覺和圖像處理領域的核心問題之一，是目標識別技術的重要研究內容，廣泛應用于遙感影像處理、目標識別與跟蹤、醫學圖像處理和圖像制導技術等領域。目前，常用的圖像匹配算法主要有基于區域統計性特征的圖像匹配和基于局部特征的匹配兩大類[2]，而由于圖像場景的復雜性和局部特征具有更好的魯棒性，基于局部特征的圖像匹配算法日益成為該領域研究的主流方向[3]。
迄今為止，SIFT（Scale Invariant Feature Transform）算法[4]被公認為具有很好的魯棒性，是最適合在復雜場景中應用的一種局部特征匹配算法，已成為目前最主流的圖像匹配算法之一[5]。根據SIFT算法的原理，SIFT算法能夠很好地抵御圖像尺度變換、旋轉變換和仿射變換，當圖像存在一定程度的噪聲時，也能夠實現圖像匹配，因此該算法常常被用于一些復雜場景的圖像匹配問題。但是，SIFT需要生成很高維度的描述向量，匹配時利用歐式空間距離法分析描述向量的相似性，運算量大，很大程度上限制了該算法在實際硬件系統中的應用。目前，針對SIFT算法簡化運算的研究主要聚焦在如何簡化描述向量方面，如PCA-SIFT[6]，而對描述向量匹配過程中運算量大的問題研究較少。針對該問題，本文以角度相似性分析為基本思路，提出了一種易于實現的圖像局部特征快速匹配算法，提升算法性能。
1 SIFT匹配算法原理
SIFT匹配算法主要包括特征點搜索、描述向量生成和特征點匹配三個基本步驟。
1.1 特征點搜索
SIFT特征點搜索也稱特征點檢測，主要分為三個基本步驟：尺度空間生成、空間鄰域極大值搜索和特征點精確定位[4]。
(1)尺度空間生成
目前，已經有文獻用數學方法證明了高斯核是產生信號多尺度空間的惟一有效核[7]，由高斯核生成的尺度空間滿足尺度、平移以及旋轉不變性等。對于二維圖像I(x，y)，其尺度空間L(x，y)的定義為：
(2)空間鄰域極大值搜索
Lowe在文獻[4]中提出，在某個尺度上搜索圖像斑點，可以先在兩個相鄰的高斯尺度空間圖像之間做減運算，求得一個DoG（Difference of Gaussian）響應值圖像D(x，y)，D(x，y)的公式為：
其中，k為兩個相鄰尺度倍數的常數。
在實際操作中，DoG是通過建立圖像的尺度空間金字塔來實現的[8]。在尺度空間金字塔中，每一個像素點和其26個鄰域(包含同尺度相鄰點和上下相鄰尺度的相鄰點共26點)進行比較，實現空間范疇的局部極大值搜索，得到的所有極大值點構成的集合即為特征點的備選集合。建立備選集合時，可去除對比度較低的極值點，由此對集合進行初步提純。
(3)特征點精確定位
特征點精確定位時，通過三維二次函數來擬合特征點，由此可以獲得特征點的精確位置和尺度值，此外，為了確保所提取特征點的穩定性，基于Hessian矩陣計算主曲率，去除在邊緣上極值點。
1.2 描述向量生成
SIFT描述向量生成主要包括求取特征點主方向和特征點描述兩個基本步驟。
(1)求取特征點主方向
對于某個特征點，首先在其尺度圖像中設定一定范圍為鄰域區域，在鄰域中計算每個點的梯度M(x，y)和方向(x，y)，其表達式分別為：
統計鄰域區域內的梯度及方向數據，構建直方圖，直方圖中的主峰值則為特征點的主方向，若在直方圖中存在一個次峰值，其能量相當于主峰值80%以上，則將這個方向確定為特征點的輔方向[9]。至此，特征點有了四個參數信息分別為特征點坐標、尺度信息、方向信息。確定主方向和輔方向的作用是使特征點具有旋轉不變性。
(2)描述向量生成
在對每個特征點進行描述時，首先將尺度圖像坐標軸旋轉至主方向上，在特征點鄰域范圍劃定4×4共16個子區域，在每個子區域，將0～360°全方向劃分為8個子方向（每個子方向寬度為45°），統計各子方向梯度強度，構建8維子區域描述向量。對于16個子區域，則最終生成4×4×8=128維描述向量，描述向量也稱描述子或特征向量。
1.3 特征點匹配
特征點匹配的目的是在原圖像和待匹配圖像中尋找相似程度高的特征點對，通常特征點在圖像間都是一對一關系，因此點對匹配時僅考慮相似度最近鄰情況。
目前的匹配方法主要采用歐式距離分析法[4]，對于k維向量Xi和Xj，其歐式距離公式為：
為刪除一些易混淆點對，采用最優與次優比值的方法，對于歐式距離來說，即為最近鄰與次近鄰比值的方法。在運算中，若最近鄰與次近鄰比值小于預設的閾值，則認定為正確匹配對，認定關系式可表述為：
式(7)中，Min{Dis}為求得的最近鄰，secMin{Dis}為求得的次近鄰，TDis表示最近鄰與次近鄰的比值閾值。若式(7)成立，則認定最近鄰相對應的特征點對為正確匹配對。通常，TDis在0.6～0.75之間取值。
歐式距離分析法能夠有效實現特征點對的相似性篩選，物理意義明確，但該方法運算速度慢，制約了SIFT算法的應用范圍。
2 改進的匹配算法
為了提升匹配速度和進一步篩選匹配對，本文提出角度相似性分析和隨機抽樣一致性(Random Sample Consensus，RANSAC)篩選[10]相結合的方法，簡化匹配運算并刪除不符合空間一致性關系的錯誤匹配對。該算法以SIFT描述向量為處理對象，包括描述向量預匹配和匹配點對篩選兩個基本步驟。
2.1 描述向量預匹配
描述向量預匹配以角度相似性作為匹配準則，該方法也可稱為角度相似性匹配。角度相似性分析的原理：對于兩個單位向量，其夾角與弧長正相關，夾角很小時，弧長與弦長近似相等，弦長即為歐式距離。因此，夾角大小與歐式距離正相關，可以利用夾角的大小來判斷單位向量之間的相似程度。對于待匹配的k維單位向量，計算向量間的空間夾角，夾角越小，則這兩個描述向量越相似。
k維空間中的向量夾角?椎ij計算公式為：
對于SIFT描述向量，描述向量生成過程中已經進行過歸一化運算，因此，式（8）可簡化為：
因(i，j)較大時不符合相似性準則，因此，首先舍棄(i，j)數值較大的情況。然后，利用最優與次優的比值大小來認定是否為正確匹配對，其認定關系可表述為：
式(10)中，Min表示最小夾角(即最優夾角)，secMin表示次小夾角(即次優夾角)，T為最小夾角與次小夾角比值閾值，當式(10)成立時，最小夾角對應的匹配對即被認定為備選匹配對，經過遍歷運算后，建立備選匹配對集合。需要注意根據角度相似性分析原理，作為無量綱的比值閾值TDis和T?椎應具有相同的取值區間，即T同樣可在0.6～0.75之間取值。
為了進一步減化運算，在實際算法設計中，計算向量之間夾角余弦值后僅保留最大和次大值，然后僅對最大和次大值做反余弦計算求取最小和次小角度值。
2.2 匹配點對篩選
由于圖像場景的復雜性，不能避免在備選匹配對集合中有錯誤匹配對存在的情況。針對該問題，采用RANSAC算法[10]對特征點對進一步篩選，保證匹配點對空間關系的一致性。
RANSAC算法原理：認為正確的匹配對在圖像中滿足空間關系的一致性，因此，可以在備選集合中不斷地隨機性抽取匹配點對，利用抽取的匹配點對建立圖像間空間投影矩陣，然后通過空間關系的一致性度量驗證該空間投影關系的正確性，多次抽取和計算后，獲得的一致性最強的空間投影矩陣即為實際的空間投影矩陣，由此可以刪除備選集合中的錯誤匹配對。
RANSAC算法的基本步驟包括[10]：
(1)從備選集合中隨機抽取4對初始匹配點對（每個圖像平面上的4個點須滿足任意3點不共線），計算兩平面之間的線性投影矩陣的參數。
(2)對于未被抽取到的特征點，通過步驟(1)中計算得到的投影矩陣計算其在另一平面中的坐標值，進而獲得該坐標值與它預匹配的點之間的距離，若該距離很小，則該匹配點對認定為內點，否則認定為外點，記錄內、外點數量。
(3)多次重復步驟(1)、(2)操作，選擇內點數量最多時對應的投影矩陣參數作為正確的投影矩陣參數。
(4)對于被確認的投影矩陣，其相應的內點即被認定為正確的匹配點對。
經過上述篩選后，不滿足空間一致性關系的匹配點對將被成功刪除。
2.3 算法流程
本文算法的實現流程如圖1所示。
新算法結構清晰、運算簡便，易于向硬件系統移植。在實際應用中，可采用典型的DSP+FPGA雙核心結構實現硬件設計。
3 算法驗證與分析
將圖2中原始圖像SCENE（分辨率：384×512）和目標圖像BASMATI（分辨率：175×265）作為待匹配圖像，采用本文算法進行實驗。實驗環境：Intel Core i3-2 350 M 2.30 GHz CPU、4 GB（3.07 GB可用）內存、Win7操作系統PC機，Matlab7.6。從圖2可以看出，原始圖像對應區域和目標圖像之間存在尺度、旋轉和仿射變換。
實驗中，首先對SCENE圖像和BASMATI圖像進行SIFT特征點搜索，然后，分別用歐式距離分析和本文的角度相似性分析進行預匹配，當閾值TDis和T取0.65時，輸出結果如圖3和圖4所示。
在描述向量預匹配過程，歐式空間匹配法耗時6.31 s，而角度相似性匹配法耗時4.19 s，運算速度明顯提升。圖3中，預匹配對總數量和正確匹配對數量分別為39和37，圖4中，預匹配對總數量和正確匹配對數量分別為41和39。為了更好地說明算法的有效性，將比值閾值在0.6~0.75間取值，預匹配正確率統計結果如表1所示。
由于特征點匹配以遍歷搜索為基本流程，因此比值閾值的大小不影響匹配耗時。經過預匹配后，再利用RANSAC空間一致性篩選刪除錯誤匹配對，獲得的最終匹配結果（T=0.65）如圖5所示。
由圖5可知，錯誤匹配對被RANSAC篩選成功刪除。實驗表明，當T在（0.6，0.75）范圍內取值時，RANSAC同樣能有效刪除錯誤匹配對。
分析上述實驗可知，本文算法的預匹配速度較傳統方法明顯提升，預匹配點對總數量和正確率均優于傳統方法，引入RANSAC篩選后，錯誤的匹配對被成功刪除。上述實驗驗證了本文算法的有效性。
4 結論
針對SIFT匹配運算速度較慢和存在錯誤匹配對的問題，本文提出采用角度相似性分析代替傳統的歐式距離分析，引入RANSAC篩選刪除不滿足空間一致性關系的匹配對。實驗結果表明，新算法計算速度和預匹配正確率均優于傳統方法，且能夠有效刪除錯誤匹配對。后續的研究將重點著眼于如何進一步提升算法運算速度和算法的環境適應性等問題。
參考文獻
[1] ARICAN Z，FROSSARD P.Scale-invariant features and polar descriptors in omnidirectional imaging[J].IEEE Transaction on Image Processing，2012，21(5)：2412-2423.
[2] 堯思遠，王曉明，左帥.基于SURF的特征點快速匹配算法[J].激光與紅外，2014，44(3)：347-350.
[3] 余先川，呂中華，胡丹.遙感圖像配準技術綜述[J].光學精密工程，2013，21(11)：2960-2972.
[4] LOWE D G.Distinctive image feature from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60(2)：91-110.
[5] 楊天天，魯云萍，張為華.一種基于GPGPU的SIFT加速
算法[J].電子技術應用，2015，41(1)：149-152，160.
[6] KE Y，SUKTHANKAR R.PCA-SIFT：A more distinctive representation for local image descriptors[C].Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition，Washington DC，USA：CVPR，2004(2)：506-513.
[7] 白廷柱，侯喜報.基于SIFT算子的圖像匹配算法研究[J].北京理工大學學報，2013，33(6)：622-627.
[8] 楊娜娜，哈力旦·阿布都熱依木，伊力亞爾·達吾提.基于SIFT圖像配準的維吾爾語文字識別方法[J].傳感器與微系統，2014，33(3)：40-43.
[9] 王程冬，程筱勝，崔海華，等.SIFT算法在點云配準中的應用[J].傳感器與微系統，2012，31(2)：149-152.
[10] LI B，MING D，YAN W，et al.Image matching based on two-column histogram hashing and improved RANSAC[J].IEEE Geosciences and Remote Sensing Letters，2014，11(8)：1433-1437.