文獻(xiàn)標(biāo)識(shí)碼： 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 引言
圖像匹配是指通過(guò)圖像分析方法在兩幅或者多幅圖像中尋找同名點(diǎn)的過(guò)程[1]。圖像匹配是機(jī)器視覺(jué)和圖像處理領(lǐng)域的核心問(wèn)題之一，是目標(biāo)識(shí)別技術(shù)的重要研究?jī)?nèi)容，廣泛應(yīng)用于遙感影像處理、目標(biāo)識(shí)別與跟蹤、醫(yī)學(xué)圖像處理和圖像制導(dǎo)技術(shù)等領(lǐng)域。目前，常用的圖像匹配算法主要有基于區(qū)域統(tǒng)計(jì)性特征的圖像匹配和基于局部特征的匹配兩大類(lèi)[2]，而由于圖像場(chǎng)景的復(fù)雜性和局部特征具有更好的魯棒性，基于局部特征的圖像匹配算法日益成為該領(lǐng)域研究的主流方向[3]。
迄今為止，SIFT（Scale Invariant Feature Transform）算法[4]被公認(rèn)為具有很好的魯棒性，是最適合在復(fù)雜場(chǎng)景中應(yīng)用的一種局部特征匹配算法，已成為目前最主流的圖像匹配算法之一[5]。根據(jù)SIFT算法的原理，SIFT算法能夠很好地抵御圖像尺度變換、旋轉(zhuǎn)變換和仿射變換，當(dāng)圖像存在一定程度的噪聲時(shí)，也能夠?qū)崿F(xiàn)圖像匹配，因此該算法常常被用于一些復(fù)雜場(chǎng)景的圖像匹配問(wèn)題。但是，SIFT需要生成很高維度的描述向量，匹配時(shí)利用歐式空間距離法分析描述向量的相似性，運(yùn)算量大，很大程度上限制了該算法在實(shí)際硬件系統(tǒng)中的應(yīng)用。目前，針對(duì)SIFT算法簡(jiǎn)化運(yùn)算的研究主要聚焦在如何簡(jiǎn)化描述向量方面，如PCA-SIFT[6]，而對(duì)描述向量匹配過(guò)程中運(yùn)算量大的問(wèn)題研究較少。針對(duì)該問(wèn)題，本文以角度相似性分析為基本思路，提出了一種易于實(shí)現(xiàn)的圖像局部特征快速匹配算法，提升算法性能。
1 SIFT匹配算法原理
SIFT匹配算法主要包括特征點(diǎn)搜索、描述向量生成和特征點(diǎn)匹配三個(gè)基本步驟。
1.1 特征點(diǎn)搜索
SIFT特征點(diǎn)搜索也稱(chēng)特征點(diǎn)檢測(cè)，主要分為三個(gè)基本步驟：尺度空間生成、空間鄰域極大值搜索和特征點(diǎn)精確定位[4]。
(1)尺度空間生成
目前，已經(jīng)有文獻(xiàn)用數(shù)學(xué)方法證明了高斯核是產(chǎn)生信號(hào)多尺度空間的惟一有效核[7]，由高斯核生成的尺度空間滿(mǎn)足尺度、平移以及旋轉(zhuǎn)不變性等。對(duì)于二維圖像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是通過(guò)建立圖像的尺度空間金字塔來(lái)實(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í)，可去除對(duì)比度較低的極值點(diǎn)，由此對(duì)集合進(jìn)行初步提純。
(3)特征點(diǎn)精確定位
特征點(diǎn)精確定位時(shí)，通過(guò)三維二次函數(shù)來(lái)擬合特征點(diǎn)，由此可以獲得特征點(diǎn)的精確位置和尺度值，此外，為了確保所提取特征點(diǎn)的穩(wěn)定性，基于Hessian矩陣計(jì)算主曲率，去除在邊緣上極值點(diǎn)。
1.2 描述向量生成
SIFT描述向量生成主要包括求取特征點(diǎn)主方向和特征點(diǎn)描述兩個(gè)基本步驟。
(1)求取特征點(diǎn)主方向
對(duì)于某個(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)描述向量生成
在對(duì)每個(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ū)域描述向量。對(duì)于16個(gè)子區(qū)域，則最終生成4×4×8=128維描述向量，描述向量也稱(chēng)描述子或特征向量。
1.3 特征點(diǎn)匹配
特征點(diǎn)匹配的目的是在原圖像和待匹配圖像中尋找相似程度高的特征點(diǎn)對(duì)，通常特征點(diǎn)在圖像間都是一對(duì)一關(guān)系，因此點(diǎn)對(duì)匹配時(shí)僅考慮相似度最近鄰情況。
目前的匹配方法主要采用歐式距離分析法[4]，對(duì)于k維向量Xi和Xj，其歐式距離公式為：
為刪除一些易混淆點(diǎn)對(duì)，采用最優(yōu)與次優(yōu)比值的方法，對(duì)于歐式距離來(lái)說(shuō)，即為最近鄰與次近鄰比值的方法。在運(yùn)算中，若最近鄰與次近鄰比值小于預(yù)設(shè)的閾值，則認(rèn)定為正確匹配對(duì)，認(rèn)定關(guān)系式可表述為：
式(7)中，Min{Dis}為求得的最近鄰，secMin{Dis}為求得的次近鄰，TDis表示最近鄰與次近鄰的比值閾值。若式(7)成立，則認(rèn)定最近鄰相對(duì)應(yīng)的特征點(diǎn)對(duì)為正確匹配對(duì)。通常，TDis在0.6～0.75之間取值。
歐式距離分析法能夠有效實(shí)現(xiàn)特征點(diǎn)對(duì)的相似性篩選，物理意義明確，但該方法運(yùn)算速度慢，制約了SIFT算法的應(yīng)用范圍。
2 改進(jìn)的匹配算法
為了提升匹配速度和進(jìn)一步篩選匹配對(duì)，本文提出角度相似性分析和隨機(jī)抽樣一致性(Random Sample Consensus，RANSAC)篩選[10]相結(jié)合的方法，簡(jiǎn)化匹配運(yùn)算并刪除不符合空間一致性關(guān)系的錯(cuò)誤匹配對(duì)。該算法以SIFT描述向量為處理對(duì)象，包括描述向量預(yù)匹配和匹配點(diǎn)對(duì)篩選兩個(gè)基本步驟。
2.1 描述向量預(yù)匹配
描述向量預(yù)匹配以角度相似性作為匹配準(zhǔn)則，該方法也可稱(chēng)為角度相似性匹配。角度相似性分析的原理：對(duì)于兩個(gè)單位向量，其夾角與弧長(zhǎng)正相關(guān)，夾角很小時(shí)，弧長(zhǎng)與弦長(zhǎng)近似相等，弦長(zhǎng)即為歐式距離。因此，夾角大小與歐式距離正相關(guān)，可以利用夾角的大小來(lái)判斷單位向量之間的相似程度。對(duì)于待匹配的k維單位向量，計(jì)算向量間的空間夾角，夾角越小，則這兩個(gè)描述向量越相似。
k維空間中的向量夾角?椎ij計(jì)算公式為：
對(duì)于SIFT描述向量，描述向量生成過(guò)程中已經(jīng)進(jìn)行過(guò)歸一化運(yùn)算，因此，式（8）可簡(jiǎn)化為：
因(i，j)較大時(shí)不符合相似性準(zhǔn)則，因此，首先舍棄(i，j)數(shù)值較大的情況。然后，利用最優(yōu)與次優(yōu)的比值大小來(lái)認(rèn)定是否為正確匹配對(duì)，其認(rèn)定關(guān)系可表述為：
式(10)中，Min表示最小夾角(即最優(yōu)夾角)，secMin表示次小夾角(即次優(yōu)夾角)，T為最小夾角與次小夾角比值閾值，當(dāng)式(10)成立時(shí)，最小夾角對(duì)應(yīng)的匹配對(duì)即被認(rèn)定為備選匹配對(duì)，經(jīng)過(guò)遍歷運(yùn)算后，建立備選匹配對(duì)集合。需要注意根據(jù)角度相似性分析原理，作為無(wú)量綱的比值閾值TDis和T?椎應(yīng)具有相同的取值區(qū)間，即T同樣可在0.6～0.75之間取值。
為了進(jìn)一步減化運(yùn)算，在實(shí)際算法設(shè)計(jì)中，計(jì)算向量之間夾角余弦值后僅保留最大和次大值，然后僅對(duì)最大和次大值做反余弦計(jì)算求取最小和次小角度值。
2.2 匹配點(diǎn)對(duì)篩選
由于圖像場(chǎng)景的復(fù)雜性，不能避免在備選匹配對(duì)集合中有錯(cuò)誤匹配對(duì)存在的情況。針對(duì)該問(wèn)題，采用RANSAC算法[10]對(duì)特征點(diǎn)對(duì)進(jìn)一步篩選，保證匹配點(diǎn)對(duì)空間關(guān)系的一致性。
RANSAC算法原理：認(rèn)為正確的匹配對(duì)在圖像中滿(mǎn)足空間關(guān)系的一致性，因此，可以在備選集合中不斷地隨機(jī)性抽取匹配點(diǎn)對(duì)，利用抽取的匹配點(diǎn)對(duì)建立圖像間空間投影矩陣，然后通過(guò)空間關(guān)系的一致性度量驗(yàn)證該空間投影關(guān)系的正確性，多次抽取和計(jì)算后，獲得的一致性最強(qiáng)的空間投影矩陣即為實(shí)際的空間投影矩陣，由此可以刪除備選集合中的錯(cuò)誤匹配對(duì)。
RANSAC算法的基本步驟包括[10]：
(1)從備選集合中隨機(jī)抽取4對(duì)初始匹配點(diǎn)對(duì)（每個(gè)圖像平面上的4個(gè)點(diǎn)須滿(mǎn)足任意3點(diǎn)不共線(xiàn)），計(jì)算兩平面之間的線(xiàn)性投影矩陣的參數(shù)。
(2)對(duì)于未被抽取到的特征點(diǎn)，通過(guò)步驟(1)中計(jì)算得到的投影矩陣計(jì)算其在另一平面中的坐標(biāo)值，進(jìn)而獲得該坐標(biāo)值與它預(yù)匹配的點(diǎn)之間的距離，若該距離很小，則該匹配點(diǎn)對(duì)認(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í)對(duì)應(yīng)的投影矩陣參數(shù)作為正確的投影矩陣參數(shù)。
(4)對(duì)于被確認(rèn)的投影矩陣，其相應(yīng)的內(nèi)點(diǎn)即被認(rèn)定為正確的匹配點(diǎn)對(duì)。
經(jīng)過(guò)上述篩選后，不滿(mǎn)足空間一致性關(guān)系的匹配點(diǎn)對(duì)將被成功刪除。
2.3 算法流程
本文算法的實(shí)現(xiàn)流程如圖1所示。
新算法結(jié)構(gòu)清晰、運(yùn)算簡(jiǎ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可以看出，原始圖像對(duì)應(yīng)區(qū)域和目標(biāo)圖像之間存在尺度、旋轉(zhuǎn)和仿射變換。
實(shí)驗(yàn)中，首先對(duì)SCENE圖像和BASMATI圖像進(jìn)行SIFT特征點(diǎn)搜索，然后，分別用歐式距離分析和本文的角度相似性分析進(jìn)行預(yù)匹配，當(dāng)閾值TDis和T取0.65時(shí)，輸出結(jié)果如圖3和圖4所示。
在描述向量預(yù)匹配過(guò)程，歐式空間匹配法耗時(shí)6.31 s，而角度相似性匹配法耗時(shí)4.19 s，運(yùn)算速度明顯提升。圖3中，預(yù)匹配對(duì)總數(shù)量和正確匹配對(duì)數(shù)量分別為39和37，圖4中，預(yù)匹配對(duì)總數(shù)量和正確匹配對(duì)數(shù)量分別為41和39。為了更好地說(shuō)明算法的有效性，將比值閾值在0.6~0.75間取值，預(yù)匹配正確率統(tǒng)計(jì)結(jié)果如表1所示。
由于特征點(diǎn)匹配以遍歷搜索為基本流程，因此比值閾值的大小不影響匹配耗時(shí)。經(jīng)過(guò)預(yù)匹配后，再利用RANSAC空間一致性篩選刪除錯(cuò)誤匹配對(duì)，獲得的最終匹配結(jié)果（T=0.65）如圖5所示。
由圖5可知，錯(cuò)誤匹配對(duì)被RANSAC篩選成功刪除。實(shí)驗(yàn)表明，當(dāng)T在（0.6，0.75）范圍內(nèi)取值時(shí)，RANSAC同樣能有效刪除錯(cuò)誤匹配對(duì)。
分析上述實(shí)驗(yàn)可知，本文算法的預(yù)匹配速度較傳統(tǒng)方法明顯提升，預(yù)匹配點(diǎn)對(duì)總數(shù)量和正確率均優(yōu)于傳統(tǒng)方法，引入RANSAC篩選后，錯(cuò)誤的匹配對(duì)被成功刪除。上述實(shí)驗(yàn)驗(yàn)證了本文算法的有效性。
4 結(jié)論
針對(duì)SIFT匹配運(yùn)算速度較慢和存在錯(cuò)誤匹配對(duì)的問(wèn)題，本文提出采用角度相似性分析代替?zhèn)鹘y(tǒng)的歐式距離分析，引入RANSAC篩選刪除不滿(mǎn)足空間一致性關(guān)系的匹配對(duì)。實(shí)驗(yàn)結(jié)果表明，新算法計(jì)算速度和預(yù)匹配正確率均優(yōu)于傳統(tǒng)方法，且能夠有效刪除錯(cuò)誤匹配對(duì)。后續(xù)的研究將重點(diǎn)著眼于如何進(jìn)一步提升算法運(yùn)算速度和算法的環(huán)境適應(yīng)性等問(wèn)題。
參考文獻(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)的維吾爾語(yǔ)文字識(shí)別方法[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.