0 引言

　　圖像匹配是指通過圖像分析方法在兩幅或者多幅圖像中尋找同名點(diǎn)的過程[1]。圖像匹配是機(jī)器視覺和圖像處理領(lǐng)域的核心問題之一，是目標(biāo)識別技術(shù)的重要研究內(nèi)容，廣泛應(yīng)用于遙感影像處理、目標(biāo)識別與跟蹤、醫(yī)學(xué)圖像處理和圖像制導(dǎo)技術(shù)等領(lǐng)域。目前，常用的圖像匹配算法主要有基于區(qū)域統(tǒng)計(jì)性特征的圖像匹配和基于局部特征的匹配兩大類[2]，而由于圖像場景的復(fù)雜性和局部特征具有更好的魯棒性，基于局部特征的圖像匹配算法日益成為該領(lǐng)域研究的主流方向[3]。

　　迄今為止，SIFT（Scale Invariant Feature Transform）算法[4]被公認(rèn)為具有很好的魯棒性，是最適合在復(fù)雜場景中應(yīng)用的一種局部特征匹配算法，已成為目前最主流的圖像匹配算法之一[5]。根據(jù)SIFT算法的原理，SIFT算法能夠很好地抵御圖像尺度變換、旋轉(zhuǎn)變換和仿射變換，當(dāng)圖像存在一定程度的噪聲時(shí)，也能夠?qū)崿F(xiàn)圖像匹配，因此該算法常常被用于一些復(fù)雜場景的圖像匹配問題。但是，SIFT需要生成很高維度的描述向量，匹配時(shí)利用歐式空間距離法分析描述向量的相似性，運(yùn)算量大，很大程度上限制了該算法在實(shí)際硬件系統(tǒng)中的應(yīng)用。目前，針對SIFT算法簡化運(yùn)算的研究主要聚焦在如何簡化描述向量方面，如PCA-SIFT[6]，而對描述向量匹配過程中運(yùn)算量大的問題研究較少。針對該問題，本文以角度相似性分析為基本思路，提出了一種易于實(shí)現(xiàn)的圖像局部特征快速匹配算法，提升算法性能。

1 SIFT匹配算法原理

　　SIFT匹配算法主要包括特征點(diǎn)搜索、描述向量生成和特征點(diǎn)匹配三個(gè)基本步驟。

　　1.1 特征點(diǎn)搜索

　　SIFT特征點(diǎn)搜索也稱特征點(diǎn)檢測，主要分為三個(gè)基本步驟：尺度空間生成、空間鄰域極大值搜索和特征點(diǎn)精確定位[4]。

　　(1)尺度空間生成

　　目前，已經(jīng)有文獻(xiàn)用數(shù)學(xué)方法證明了高斯核是產(chǎn)生信號多尺度空間的惟一有效核[7]，由高斯核生成的尺度空間滿足尺度、平移以及旋轉(zhuǎn)不變性等。對于二維圖像I(x，y)，其尺度空間L(x，y)的定義為：

　　(2)空間鄰域極大值搜索

　　Lowe在文獻(xiàn)[4]中提出，在某個(gè)尺度上搜索圖像斑點(diǎn)，可以先在兩個(gè)相鄰的高斯尺度空間圖像之間做減運(yùn)算，求得一個(gè)DoG（Difference of Gaussian）響應(yīng)值圖像D(x，y)，D(x，y)的公式為：

　　其中，k為兩個(gè)相鄰尺度倍數(shù)的常數(shù)。

　　在實(shí)際操作中，DoG是通過建立圖像的尺度空間金字塔來實(shí)現(xiàn)的[8]。在尺度空間金字塔中，每一個(gè)像素點(diǎn)和其26個(gè)鄰域(包含同尺度相鄰點(diǎn)和上下相鄰尺度的相鄰點(diǎn)共26點(diǎn))進(jìn)行比較，實(shí)現(xiàn)空間范疇的局部極大值搜索，得到的所有極大值點(diǎn)構(gòu)成的集合即為特征點(diǎn)的備選集合。建立備選集合時(shí)，可去除對比度較低的極值點(diǎn)，由此對集合進(jìn)行初步提純。

　　(3)特征點(diǎn)精確定位

　　特征點(diǎn)精確定位時(shí)，通過三維二次函數(shù)來擬合特征點(diǎn)，由此可以獲得特征點(diǎn)的精確位置和尺度值，此外，為了確保所提取特征點(diǎn)的穩(wěn)定性，基于Hessian矩陣計(jì)算主曲率，去除在邊緣上極值點(diǎn)。

　　1.2 描述向量生成

　　SIFT描述向量生成主要包括求取特征點(diǎn)主方向和特征點(diǎn)描述兩個(gè)基本步驟。

　　(1)求取特征點(diǎn)主方向

　　對于某個(gè)特征點(diǎn)，首先在其尺度圖像中設(shè)定一定范圍為鄰域區(qū)域，在鄰域中計(jì)算每個(gè)點(diǎn)的梯度M(x，y)和方向(x，y)，其表達(dá)式分別為：

　　統(tǒng)計(jì)鄰域區(qū)域內(nèi)的梯度及方向數(shù)據(jù)，構(gòu)建直方圖，直方圖中的主峰值則為特征點(diǎn)的主方向，若在直方圖中存在一個(gè)次峰值，其能量相當(dāng)于主峰值80%以上，則將這個(gè)方向確定為特征點(diǎn)的輔方向[9]。至此，特征點(diǎn)有了四個(gè)參數(shù)信息分別為特征點(diǎn)坐標(biāo)、尺度信息、方向信息。確定主方向和輔方向的作用是使特征點(diǎn)具有旋轉(zhuǎn)不變性。

　　(2)描述向量生成

　　在對每個(gè)特征點(diǎn)進(jìn)行描述時(shí)，首先將尺度圖像坐標(biāo)軸旋轉(zhuǎn)至主方向上，在特征點(diǎn)鄰域范圍劃定4×4共16個(gè)子區(qū)域，在每個(gè)子區(qū)域，將0～360°全方向劃分為8個(gè)子方向（每個(gè)子方向?qū)挾葹?5°），統(tǒng)計(jì)各子方向梯度強(qiáng)度，構(gòu)建8維子區(qū)域描述向量。對于16個(gè)子區(qū)域，則最終生成4×4×8=128維描述向量，描述向量也稱描述子或特征向量。

　　1.3 特征點(diǎn)匹配

　　特征點(diǎn)匹配的目的是在原圖像和待匹配圖像中尋找相似程度高的特征點(diǎn)對，通常特征點(diǎn)在圖像間都是一對一關(guān)系，因此點(diǎn)對匹配時(shí)僅考慮相似度最近鄰情況。

　　目前的匹配方法主要采用歐式距離分析法[4]，對于k維向量Xi和Xj，其歐式距離公式為：

　　為刪除一些易混淆點(diǎn)對，采用最優(yōu)與次優(yōu)比值的方法，對于歐式距離來說，即為最近鄰與次近鄰比值的方法。在運(yùn)算中，若最近鄰與次近鄰比值小于預(yù)設(shè)的閾值，則認(rèn)定為正確匹配對，認(rèn)定關(guān)系式可表述為：

　　式(7)中，Min{Dis}為求得的最近鄰，secMin{Dis}為求得的次近鄰，TDis表示最近鄰與次近鄰的比值閾值。若式(7)成立，則認(rèn)定最近鄰相對應(yīng)的特征點(diǎn)對為正確匹配對。通常，TDis在0.6～0.75之間取值。

　　歐式距離分析法能夠有效實(shí)現(xiàn)特征點(diǎn)對的相似性篩選，物理意義明確，但該方法運(yùn)算速度慢，制約了SIFT算法的應(yīng)用范圍。

2 改進(jìn)的匹配算法

　　為了提升匹配速度和進(jìn)一步篩選匹配對，本文提出角度相似性分析和隨機(jī)抽樣一致性(Random Sample Consensus，RANSAC)篩選[10]相結(jié)合的方法，簡化匹配運(yùn)算并刪除不符合空間一致性關(guān)系的錯(cuò)誤匹配對。該算法以SIFT描述向量為處理對象，包括描述向量預(yù)匹配和匹配點(diǎn)對篩選兩個(gè)基本步驟。

　　2.1 描述向量預(yù)匹配

　　描述向量預(yù)匹配以角度相似性作為匹配準(zhǔn)則，該方法也可稱為角度相似性匹配。角度相似性分析的原理：對于兩個(gè)單位向量，其夾角與弧長正相關(guān)，夾角很小時(shí)，弧長與弦長近似相等，弦長即為歐式距離。因此，夾角大小與歐式距離正相關(guān)，可以利用夾角的大小來判斷單位向量之間的相似程度。對于待匹配的k維單位向量，計(jì)算向量間的空間夾角，夾角越小，則這兩個(gè)描述向量越相似。

　　k維空間中的向量夾角?椎ij計(jì)算公式為：

　　對于SIFT描述向量，描述向量生成過程中已經(jīng)進(jìn)行過歸一化運(yùn)算，因此，式（8）可簡化為：

　　因(i，j)較大時(shí)不符合相似性準(zhǔn)則，因此，首先舍棄(i，j)數(shù)值較大的情況。然后，利用最優(yōu)與次優(yōu)的比值大小來認(rèn)定是否為正確匹配對，其認(rèn)定關(guān)系可表述為：

　　式(10)中，Min表示最小夾角(即最優(yōu)夾角)，secMin表示次小夾角(即次優(yōu)夾角)，T為最小夾角與次小夾角比值閾值，當(dāng)式(10)成立時(shí)，最小夾角對應(yīng)的匹配對即被認(rèn)定為備選匹配對，經(jīng)過遍歷運(yùn)算后，建立備選匹配對集合。需要注意根據(jù)角度相似性分析原理，作為無量綱的比值閾值TDis和T?椎應(yīng)具有相同的取值區(qū)間，即T同樣可在0.6～0.75之間取值。

　　為了進(jìn)一步減化運(yùn)算，在實(shí)際算法設(shè)計(jì)中，計(jì)算向量之間夾角余弦值后僅保留最大和次大值，然后僅對最大和次大值做反余弦計(jì)算求取最小和次小角度值。

　　2.2 匹配點(diǎn)對篩選

　　由于圖像場景的復(fù)雜性，不能避免在備選匹配對集合中有錯(cuò)誤匹配對存在的情況。針對該問題，采用RANSAC算法[10]對特征點(diǎn)對進(jìn)一步篩選，保證匹配點(diǎn)對空間關(guān)系的一致性。

　　RANSAC算法原理：認(rèn)為正確的匹配對在圖像中滿足空間關(guān)系的一致性，因此，可以在備選集合中不斷地隨機(jī)性抽取匹配點(diǎn)對，利用抽取的匹配點(diǎn)對建立圖像間空間投影矩陣，然后通過空間關(guān)系的一致性度量驗(yàn)證該空間投影關(guān)系的正確性，多次抽取和計(jì)算后，獲得的一致性最強(qiáng)的空間投影矩陣即為實(shí)際的空間投影矩陣，由此可以刪除備選集合中的錯(cuò)誤匹配對。

　　RANSAC算法的基本步驟包括[10]：

　　(1)從備選集合中隨機(jī)抽取4對初始匹配點(diǎn)對（每個(gè)圖像平面上的4個(gè)點(diǎn)須滿足任意3點(diǎn)不共線），計(jì)算兩平面之間的線性投影矩陣的參數(shù)。

　　(2)對于未被抽取到的特征點(diǎn)，通過步驟(1)中計(jì)算得到的投影矩陣計(jì)算其在另一平面中的坐標(biāo)值，進(jìn)而獲得該坐標(biāo)值與它預(yù)匹配的點(diǎn)之間的距離，若該距離很小，則該匹配點(diǎn)對認(rèn)定為內(nèi)點(diǎn)，否則認(rèn)定為外點(diǎn)，記錄內(nèi)、外點(diǎn)數(shù)量。

　　(3)多次重復(fù)步驟(1)、(2)操作，選擇內(nèi)點(diǎn)數(shù)量最多時(shí)對應(yīng)的投影矩陣參數(shù)作為正確的投影矩陣參數(shù)。

　　(4)對于被確認(rèn)的投影矩陣，其相應(yīng)的內(nèi)點(diǎn)即被認(rèn)定為正確的匹配點(diǎn)對。

　　經(jīng)過上述篩選后，不滿足空間一致性關(guān)系的匹配點(diǎn)對將被成功刪除。

　　2.3 算法流程

　　本文算法的實(shí)現(xiàn)流程如圖1所示。

　　新算法結(jié)構(gòu)清晰、運(yùn)算簡便，易于向硬件系統(tǒng)移植。在實(shí)際應(yīng)用中，可采用典型的DSP+FPGA雙核心結(jié)構(gòu)實(shí)現(xiàn)硬件設(shè)計(jì)。

3 算法驗(yàn)證與分析

　　將圖2中原始圖像SCENE（分辨率：384×512）和目標(biāo)圖像BASMATI（分辨率：175×265）作為待匹配圖像，采用本文算法進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境：Intel Core i3-2 350 M 2.30 GHz CPU、4 GB（3.07 GB可用）內(nèi)存、Win7操作系統(tǒng)PC機(jī)，Matlab7.6。從圖2可以看出，原始圖像對應(yīng)區(qū)域和目標(biāo)圖像之間存在尺度、旋轉(zhuǎn)和仿射變換。

　　實(shí)驗(yàn)中，首先對SCENE圖像和BASMATI圖像進(jìn)行SIFT特征點(diǎn)搜索，然后，分別用歐式距離分析和本文的角度相似性分析進(jìn)行預(yù)匹配，當(dāng)閾值TDis和T取0.65時(shí)，輸出結(jié)果如圖3和圖4所示。

　　在描述向量預(yù)匹配過程，歐式空間匹配法耗時(shí)6.31 s，而角度相似性匹配法耗時(shí)4.19 s，運(yùn)算速度明顯提升。圖3中，預(yù)匹配對總數(shù)量和正確匹配對數(shù)量分別為39和37，圖4中，預(yù)匹配對總數(shù)量和正確匹配對數(shù)量分別為41和39。為了更好地說明算法的有效性，將比值閾值在0.6~0.75間取值，預(yù)匹配正確率統(tǒng)計(jì)結(jié)果如表1所示。

　　由于特征點(diǎn)匹配以遍歷搜索為基本流程，因此比值閾值的大小不影響匹配耗時(shí)。經(jīng)過預(yù)匹配后，再利用RANSAC空間一致性篩選刪除錯(cuò)誤匹配對，獲得的最終匹配結(jié)果（T=0.65）如圖5所示。

　　由圖5可知，錯(cuò)誤匹配對被RANSAC篩選成功刪除。實(shí)驗(yàn)表明，當(dāng)T在（0.6，0.75）范圍內(nèi)取值時(shí)，RANSAC同樣能有效刪除錯(cuò)誤匹配對。

　　分析上述實(shí)驗(yàn)可知，本文算法的預(yù)匹配速度較傳統(tǒng)方法明顯提升，預(yù)匹配點(diǎn)對總數(shù)量和正確率均優(yōu)于傳統(tǒng)方法，引入RANSAC篩選后，錯(cuò)誤的匹配對被成功刪除。上述實(shí)驗(yàn)驗(yàn)證了本文算法的有效性。

4 結(jié)論

　　針對SIFT匹配運(yùn)算速度較慢和存在錯(cuò)誤匹配對的問題，本文提出采用角度相似性分析代替?zhèn)鹘y(tǒng)的歐式距離分析，引入RANSAC篩選刪除不滿足空間一致性關(guān)系的匹配對。實(shí)驗(yàn)結(jié)果表明，新算法計(jì)算速度和預(yù)匹配正確率均優(yōu)于傳統(tǒng)方法，且能夠有效刪除錯(cuò)誤匹配對。后續(xù)的研究將重點(diǎn)著眼于如何進(jìn)一步提升算法運(yùn)算速度和算法的環(huán)境適應(yīng)性等問題。

參考文獻(xiàn)

　　[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] 堯思遠(yuǎn)，王曉明，左帥.基于SURF的特征點(diǎn)快速匹配算法[J].激光與紅外，2014，44(3)：347-350.

　　[3] 余先川，呂中華，胡丹.遙感圖像配準(zhǔn)技術(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] 白廷柱，侯喜報(bào).基于SIFT算子的圖像匹配算法研究[J].北京理工大學(xué)學(xué)報(bào)，2013，33(6)：622-627.

　　[8] 楊娜娜，哈力旦·阿布都熱依木，伊力亞爾·達(dá)吾提.基于SIFT圖像配準(zhǔn)的維吾爾語文字識別方法[J].傳感器與微系統(tǒng)，2014，33(3)：40-43.

　　[9] 王程冬，程筱勝，崔海華，等.SIFT算法在點(diǎn)云配準(zhǔn)中的應(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.