文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2015.11.035
中文引用格式： 張格森，陳東生，王懷野，等. 一種圖像局部特征快速匹配算法[J].電子技術(shù)應(yīng)用，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]。圖像匹配是機器視覺和圖像處理領(lǐng)域的核心問題之一，是目標識別技術(shù)的重要研究內(nèi)容，廣泛應(yīng)用于遙感影像處理、目標識別與跟蹤、醫(yī)學(xué)圖像處理和圖像制導(dǎo)技術(shù)等領(lǐng)域。目前，常用的圖像匹配算法主要有基于區(qū)域統(tǒng)計性特征的圖像匹配和基于局部特征的匹配兩大類[2]，而由于圖像場景的復(fù)雜性和局部特征具有更好的魯棒性，基于局部特征的圖像匹配算法日益成為該領(lǐng)域研究的主流方向[3]。
迄今為止，SIFT（Scale Invariant Feature Transform）算法[4]被公認為具有很好的魯棒性，是最適合在復(fù)雜場景中應(yīng)用的一種局部特征匹配算法，已成為目前最主流的圖像匹配算法之一[5]。根據(jù)SIFT算法的原理，SIFT算法能夠很好地抵御圖像尺度變換、旋轉(zhuǎn)變換和仿射變換，當(dāng)圖像存在一定程度的噪聲時，也能夠?qū)崿F(xiàn)圖像匹配，因此該算法常常被用于一些復(fù)雜場景的圖像匹配問題。但是，SIFT需要生成很高維度的描述向量，匹配時利用歐式空間距離法分析描述向量的相似性，運算量大，很大程度上限制了該算法在實際硬件系統(tǒng)中的應(yīng)用。目前，針對SIFT算法簡化運算的研究主要聚焦在如何簡化描述向量方面，如PCA-SIFT[6]，而對描述向量匹配過程中運算量大的問題研究較少。針對該問題，本文以角度相似性分析為基本思路，提出了一種易于實現(xiàn)的圖像局部特征快速匹配算法，提升算法性能。
1 SIFT匹配算法原理
SIFT匹配算法主要包括特征點搜索、描述向量生成和特征點匹配三個基本步驟。
1.1 特征點搜索
SIFT特征點搜索也稱特征點檢測，主要分為三個基本步驟：尺度空間生成、空間鄰域極大值搜索和特征點精確定位[4]。
(1)尺度空間生成
目前，已經(jīng)有文獻用數(shù)學(xué)方法證明了高斯核是產(chǎn)生信號多尺度空間的惟一有效核[7]，由高斯核生成的尺度空間滿足尺度、平移以及旋轉(zhuǎn)不變性等。對于二維圖像I(x，y)，其尺度空間L(x，y)的定義為：
(2)空間鄰域極大值搜索
Lowe在文獻[4]中提出，在某個尺度上搜索圖像斑點，可以先在兩個相鄰的高斯尺度空間圖像之間做減運算，求得一個DoG（Difference of Gaussian）響應(yīng)值圖像D(x，y)，D(x，y)的公式為：
其中，k為兩個相鄰尺度倍數(shù)的常數(shù)。
在實際操作中，DoG是通過建立圖像的尺度空間金字塔來實現(xiàn)的[8]。在尺度空間金字塔中，每一個像素點和其26個鄰域(包含同尺度相鄰點和上下相鄰尺度的相鄰點共26點)進行比較，實現(xiàn)空間范疇的局部極大值搜索，得到的所有極大值點構(gòu)成的集合即為特征點的備選集合。建立備選集合時，可去除對比度較低的極值點，由此對集合進行初步提純。
(3)特征點精確定位
特征點精確定位時，通過三維二次函數(shù)來擬合特征點，由此可以獲得特征點的精確位置和尺度值，此外，為了確保所提取特征點的穩(wěn)定性，基于Hessian矩陣計算主曲率，去除在邊緣上極值點。
1.2 描述向量生成
SIFT描述向量生成主要包括求取特征點主方向和特征點描述兩個基本步驟。
(1)求取特征點主方向
對于某個特征點，首先在其尺度圖像中設(shè)定一定范圍為鄰域區(qū)域，在鄰域中計算每個點的梯度M(x，y)和方向(x，y)，其表達式分別為：
統(tǒng)計鄰域區(qū)域內(nèi)的梯度及方向數(shù)據(jù)，構(gòu)建直方圖，直方圖中的主峰值則為特征點的主方向，若在直方圖中存在一個次峰值，其能量相當(dāng)于主峰值80%以上，則將這個方向確定為特征點的輔方向[9]。至此，特征點有了四個參數(shù)信息分別為特征點坐標、尺度信息、方向信息。確定主方向和輔方向的作用是使特征點具有旋轉(zhuǎn)不變性。
(2)描述向量生成
在對每個特征點進行描述時，首先將尺度圖像坐標軸旋轉(zhuǎn)至主方向上，在特征點鄰域范圍劃定4×4共16個子區(qū)域，在每個子區(qū)域，將0～360°全方向劃分為8個子方向（每個子方向?qū)挾葹?5°），統(tǒng)計各子方向梯度強度，構(gòu)建8維子區(qū)域描述向量。對于16個子區(qū)域，則最終生成4×4×8=128維描述向量，描述向量也稱描述子或特征向量。
1.3 特征點匹配
特征點匹配的目的是在原圖像和待匹配圖像中尋找相似程度高的特征點對，通常特征點在圖像間都是一對一關(guān)系，因此點對匹配時僅考慮相似度最近鄰情況。
目前的匹配方法主要采用歐式距離分析法[4]，對于k維向量Xi和Xj，其歐式距離公式為：
為刪除一些易混淆點對，采用最優(yōu)與次優(yōu)比值的方法，對于歐式距離來說，即為最近鄰與次近鄰比值的方法。在運算中，若最近鄰與次近鄰比值小于預(yù)設(shè)的閾值，則認定為正確匹配對，認定關(guān)系式可表述為：
式(7)中，Min{Dis}為求得的最近鄰，secMin{Dis}為求得的次近鄰，TDis表示最近鄰與次近鄰的比值閾值。若式(7)成立，則認定最近鄰相對應(yīng)的特征點對為正確匹配對。通常，TDis在0.6～0.75之間取值。
歐式距離分析法能夠有效實現(xiàn)特征點對的相似性篩選，物理意義明確，但該方法運算速度慢，制約了SIFT算法的應(yīng)用范圍。
2 改進的匹配算法
為了提升匹配速度和進一步篩選匹配對，本文提出角度相似性分析和隨機抽樣一致性(Random Sample Consensus，RANSAC)篩選[10]相結(jié)合的方法，簡化匹配運算并刪除不符合空間一致性關(guān)系的錯誤匹配對。該算法以SIFT描述向量為處理對象，包括描述向量預(yù)匹配和匹配點對篩選兩個基本步驟。
2.1 描述向量預(yù)匹配
描述向量預(yù)匹配以角度相似性作為匹配準則，該方法也可稱為角度相似性匹配。角度相似性分析的原理：對于兩個單位向量，其夾角與弧長正相關(guān)，夾角很小時，弧長與弦長近似相等，弦長即為歐式距離。因此，夾角大小與歐式距離正相關(guān)，可以利用夾角的大小來判斷單位向量之間的相似程度。對于待匹配的k維單位向量，計算向量間的空間夾角，夾角越小，則這兩個描述向量越相似。
k維空間中的向量夾角?椎ij計算公式為：
對于SIFT描述向量，描述向量生成過程中已經(jīng)進行過歸一化運算，因此，式（8）可簡化為：
因(i，j)較大時不符合相似性準則，因此，首先舍棄(i，j)數(shù)值較大的情況。然后，利用最優(yōu)與次優(yōu)的比值大小來認定是否為正確匹配對，其認定關(guān)系可表述為：
式(10)中，Min表示最小夾角(即最優(yōu)夾角)，secMin表示次小夾角(即次優(yōu)夾角)，T為最小夾角與次小夾角比值閾值，當(dāng)式(10)成立時，最小夾角對應(yīng)的匹配對即被認定為備選匹配對，經(jīng)過遍歷運算后，建立備選匹配對集合。需要注意根據(jù)角度相似性分析原理，作為無量綱的比值閾值TDis和T?椎應(yīng)具有相同的取值區(qū)間，即T同樣可在0.6～0.75之間取值。
為了進一步減化運算，在實際算法設(shè)計中，計算向量之間夾角余弦值后僅保留最大和次大值，然后僅對最大和次大值做反余弦計算求取最小和次小角度值。
2.2 匹配點對篩選
由于圖像場景的復(fù)雜性，不能避免在備選匹配對集合中有錯誤匹配對存在的情況。針對該問題，采用RANSAC算法[10]對特征點對進一步篩選，保證匹配點對空間關(guān)系的一致性。
RANSAC算法原理：認為正確的匹配對在圖像中滿足空間關(guān)系的一致性，因此，可以在備選集合中不斷地隨機性抽取匹配點對，利用抽取的匹配點對建立圖像間空間投影矩陣，然后通過空間關(guān)系的一致性度量驗證該空間投影關(guān)系的正確性，多次抽取和計算后，獲得的一致性最強的空間投影矩陣即為實際的空間投影矩陣，由此可以刪除備選集合中的錯誤匹配對。
RANSAC算法的基本步驟包括[10]：
(1)從備選集合中隨機抽取4對初始匹配點對（每個圖像平面上的4個點須滿足任意3點不共線），計算兩平面之間的線性投影矩陣的參數(shù)。
(2)對于未被抽取到的特征點，通過步驟(1)中計算得到的投影矩陣計算其在另一平面中的坐標值，進而獲得該坐標值與它預(yù)匹配的點之間的距離，若該距離很小，則該匹配點對認定為內(nèi)點，否則認定為外點，記錄內(nèi)、外點數(shù)量。
(3)多次重復(fù)步驟(1)、(2)操作，選擇內(nèi)點數(shù)量最多時對應(yīng)的投影矩陣參數(shù)作為正確的投影矩陣參數(shù)。
(4)對于被確認的投影矩陣，其相應(yīng)的內(nèi)點即被認定為正確的匹配點對。
經(jīng)過上述篩選后，不滿足空間一致性關(guān)系的匹配點對將被成功刪除。
2.3 算法流程
本文算法的實現(xiàn)流程如圖1所示。
新算法結(jié)構(gòu)清晰、運算簡便，易于向硬件系統(tǒng)移植。在實際應(yīng)用中，可采用典型的DSP+FPGA雙核心結(jié)構(gòu)實現(xiàn)硬件設(shè)計。
3 算法驗證與分析
將圖2中原始圖像SCENE（分辨率：384×512）和目標圖像BASMATI（分辨率：175×265）作為待匹配圖像，采用本文算法進行實驗。實驗環(huán)境：Intel Core i3-2 350 M 2.30 GHz CPU、4 GB（3.07 GB可用）內(nèi)存、Win7操作系統(tǒng)PC機，Matlab7.6。從圖2可以看出，原始圖像對應(yīng)區(qū)域和目標圖像之間存在尺度、旋轉(zhuǎn)和仿射變換。
實驗中，首先對SCENE圖像和BASMATI圖像進行SIFT特征點搜索，然后，分別用歐式距離分析和本文的角度相似性分析進行預(yù)匹配，當(dāng)閾值TDis和T取0.65時，輸出結(jié)果如圖3和圖4所示。
在描述向量預(yù)匹配過程，歐式空間匹配法耗時6.31 s，而角度相似性匹配法耗時4.19 s，運算速度明顯提升。圖3中，預(yù)匹配對總數(shù)量和正確匹配對數(shù)量分別為39和37，圖4中，預(yù)匹配對總數(shù)量和正確匹配對數(shù)量分別為41和39。為了更好地說明算法的有效性，將比值閾值在0.6~0.75間取值，預(yù)匹配正確率統(tǒng)計結(jié)果如表1所示。
由于特征點匹配以遍歷搜索為基本流程，因此比值閾值的大小不影響匹配耗時。經(jīng)過預(yù)匹配后，再利用RANSAC空間一致性篩選刪除錯誤匹配對，獲得的最終匹配結(jié)果（T=0.65）如圖5所示。
由圖5可知，錯誤匹配對被RANSAC篩選成功刪除。實驗表明，當(dāng)T在（0.6，0.75）范圍內(nèi)取值時，RANSAC同樣能有效刪除錯誤匹配對。
分析上述實驗可知，本文算法的預(yù)匹配速度較傳統(tǒng)方法明顯提升，預(yù)匹配點對總數(shù)量和正確率均優(yōu)于傳統(tǒng)方法，引入RANSAC篩選后，錯誤的匹配對被成功刪除。上述實驗驗證了本文算法的有效性。
4 結(jié)論
針對SIFT匹配運算速度較慢和存在錯誤匹配對的問題，本文提出采用角度相似性分析代替?zhèn)鹘y(tǒng)的歐式距離分析，引入RANSAC篩選刪除不滿足空間一致性關(guān)系的匹配對。實驗結(jié)果表明，新算法計算速度和預(yù)匹配正確率均優(yōu)于傳統(tǒng)方法，且能夠有效刪除錯誤匹配對。后續(xù)的研究將重點著眼于如何進一步提升算法運算速度和算法的環(huán)境適應(yīng)性等問題。
參考文獻
[1] ARICAN Z，F(xiàn)ROSSARD 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] 余先川，呂中華，胡丹.遙感圖像配準技術(shù)綜述[J].光學(xué)精密工程，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].電子技術(shù)應(yīng)用，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].北京理工大學(xué)學(xué)報，2013，33(6)：622-627.
[8] 楊娜娜，哈力旦·阿布都熱依木，伊力亞爾·達吾提.基于SIFT圖像配準的維吾爾語文字識別方法[J].傳感器與微系統(tǒng)，2014，33(3)：40-43.
[9] 王程冬，程筱勝，崔海華，等.SIFT算法在點云配準中的應(yīng)用[J].傳感器與微系統(tǒng)，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.