董慧穎，徐友聚

(沈陽(yáng)理工大學(xué) 自動(dòng)化與電氣工程學(xué)院，沈陽(yáng)110159)

SIFT特征匹配算法優(yōu)化

董慧穎，徐友聚

(沈陽(yáng)理工大學(xué) 自動(dòng)化與電氣工程學(xué)院，沈陽(yáng)110159)

基于SIFT特征的圖像目標(biāo)匹配與檢測(cè)應(yīng)用中，特征點(diǎn)的誤匹配將直接影響系統(tǒng)對(duì)目標(biāo)檢測(cè)的靈敏度。提出了一種將二分查找法與仿射變換結(jié)合，用于目標(biāo)快速檢測(cè)的方法。先用算法復(fù)雜度較低的最近鄰-次近鄰法對(duì)SIFT特征點(diǎn)進(jìn)行粗匹配，并用匹配對(duì)中兩特征點(diǎn)與主方向角度差進(jìn)行篩選。隨機(jī)選取若干組特征點(diǎn)，計(jì)算其仿射變換參數(shù)，依據(jù)其參數(shù)的統(tǒng)計(jì)分布特點(diǎn)，用二分查找法得到最優(yōu)解，實(shí)現(xiàn)對(duì)目標(biāo)的檢測(cè)。結(jié)果顯示，算法有較高的檢測(cè)效率和穩(wěn)定性。

SIFT；二分查找法；仿射變換；統(tǒng)計(jì)分布；匹配；檢測(cè)

SIFT局部特征算法自Lowe于1999年提出并完善以來(lái)，因其具有對(duì)位置、空間尺度、旋轉(zhuǎn)、光照的一致性[1]，以及在仿射變換時(shí)的優(yōu)異的穩(wěn)定性，抗噪聲能力強(qiáng)等特點(diǎn)[2-3]，被廣泛應(yīng)用在物體識(shí)別、影像縫合、3D視覺(jué)模型、手勢(shì)辨識(shí)等領(lǐng)域[4-6]。

由于SIFT算法提取的特征點(diǎn)數(shù)量較多，在實(shí)際應(yīng)用中不可避免地存在誤匹配的情況。本文結(jié)合二分查找法與仿射變換，來(lái)降低誤匹配對(duì)目標(biāo)定位的影響。為了降低算法的復(fù)雜度，采用單向最近鄰—次近鄰法對(duì)SIFT特征點(diǎn)進(jìn)行粗匹配，并對(duì)匹配對(duì)中兩特征點(diǎn)與主方向角度差進(jìn)行篩選。然后隨機(jī)選取若干組特征點(diǎn)，計(jì)算各組的仿射變換參數(shù)，通過(guò)分析其參數(shù)的統(tǒng)計(jì)分布，選用二分查找法得到最優(yōu)的仿射變換，對(duì)目標(biāo)進(jìn)行檢測(cè)。

1 SIFT特征向量的匹配與篩選

1.1 特征向量匹配

圖1左側(cè)為包含檢測(cè)目標(biāo)的原圖像，共檢測(cè)出2434個(gè)SIFT特征算子；右側(cè)為待檢測(cè)圖像，共檢測(cè)出7358個(gè)SIFT特征算子。

圖1 標(biāo)注特征點(diǎn)的原圖像及待匹配圖像

SIFT特征算子為4×4×8=128維的特征向量，因此可以采用特征向量的歐氏距離來(lái)作兩特征向量的相似性度量判據(jù)[2]。計(jì)算原圖像的某個(gè)特征向量與待匹配圖像的各特征向量的歐氏距離，選取距離最近和次近的兩個(gè)點(diǎn)。計(jì)算最近距離與次近距離的比值 Ratio。

(1)

設(shè)定一個(gè)閾值，當(dāng)Ratio大于該閾值時(shí)，則剔除該匹配對(duì)；如果Ratio小于該閾值，則認(rèn)為原圖像中該向量與待匹配圖像中距離其最近的特征點(diǎn)匹配。閾值設(shè)為0.4時(shí)，得到的匹配點(diǎn)較少，適用于準(zhǔn)確度要求高的匹配；閾值設(shè)為0.6時(shí)，存在較多誤匹配點(diǎn)，適用于匹配點(diǎn)數(shù)目要求較多的匹配；閾值設(shè)為0.8時(shí)，相較于最小距離法，可以去除90%的誤匹配，但正確匹配也會(huì)丟失5%左右。根據(jù) Lowe的實(shí)驗(yàn)結(jié)果[2]，本文將閾值設(shè)為0.8對(duì)特征進(jìn)行匹配，可以獲取較多的匹配對(duì)。圖2為原圖像中某特征向量a與待匹配圖像中各特征向量的歐氏距離。

圖2 原圖像中特征向量a與待匹配圖像中各特征向量的歐氏距離

比較圖2所示原圖像中某特征向量a與待匹配圖像中各特征向量的歐氏距離，可以得到距a最近與次近的兩個(gè)特征向量，分別是待匹配圖像的第1302個(gè)特征向量和第705個(gè)特征向量，距離分別是0.9031和1.846。代入公式(1)，算得Ratio的值為0.4892，小于設(shè)定的閾值0.8，因此特征向量a與待匹配圖像的第1302個(gè)特征向量匹配。

通過(guò)對(duì)原圖像2434個(gè)特征向量重復(fù)上述計(jì)算，得到如圖3所示結(jié)果。共得到71個(gè)特征向量匹配對(duì)，剔除了大量不能穩(wěn)定匹配的特征向量。其中誤匹配對(duì)19個(gè)，匹配的正確率為73.24%。

圖3 粗匹配結(jié)果

1.2 特征向量匹配對(duì)篩選

理想狀況下，目標(biāo)的形狀變化不劇烈，匹配的兩個(gè)特征向量與其各自主方向夾角的差值應(yīng)該是相近的[7-8]，因此可以作為特征點(diǎn)匹配的篩選判據(jù)。統(tǒng)計(jì)上一步所得特征向量匹配列表中每對(duì)特征向量相對(duì)主方向夾角的差值，得到分布直方圖，并計(jì)算直方圖的最大值對(duì)應(yīng)的角度差值Delta。圖4為粗匹配所得71個(gè)特征向量匹配對(duì)中兩特征向量與其各自主方向夾角的差值；在圖5中顯示了夾角差值的分布直方圖。

由圖5所示的分布直方圖可知，Delta的值為0.0873(弧度制)?？紤]到旋轉(zhuǎn)、空間尺度，特別是仿射引入的誤差，以Delta為中心，設(shè)定一鄰域作為匹配對(duì)篩選的判據(jù)[9]。當(dāng)匹配對(duì)的主方向角度差值在該鄰域內(nèi)，則保留，否則刪除該匹配對(duì)，以此改善匹配的正確率。

圖4 相對(duì)主方向夾角的差值

圖5 相對(duì)主方向夾角差值的分布直方圖

將鄰域范圍設(shè)為Delta±0.175，對(duì)圖3所示的結(jié)果進(jìn)行篩選后，得圖6所示結(jié)果。剩余51個(gè)特征向量匹配對(duì)，其中誤匹配對(duì)5個(gè)，匹配的正確率為90.20%，篩選效果明顯。

圖6 篩選后匹配結(jié)果

2 二分查找法求解最優(yōu)仿射變換

2.1 仿射變換公式

原圖像中一點(diǎn)[xy]T與待匹配圖像對(duì)應(yīng)點(diǎn)[uv]T的仿射關(guān)系[2,10]：

(2)

式中，[txty]T是位移模型，mi(i=1,2,3,4)表示仿射的旋轉(zhuǎn)、放縮與拉伸關(guān)系。

上述公式可改寫為

(3)

將上式寫為線性形式

AX=b

(4)

仿射變換矩陣X是含有6個(gè)參數(shù)的變換矩陣，因此該矩陣可以由3個(gè)匹配對(duì)求得。其公式如下：

X=[ATA]-1ATb

(5)

2.2 仿射變換參數(shù)分布

以3個(gè)匹配對(duì)為一組，計(jì)算其仿射變換矩陣X。為了有相對(duì)準(zhǔn)確的仿射結(jié)果，需將原圖像中三個(gè)點(diǎn)的距離限制在一定區(qū)間內(nèi)。本文選用計(jì)算復(fù)雜度較小的D8(棋盤距離)作為距離標(biāo)準(zhǔn)。設(shè)像素p和q的坐標(biāo)分別為(x,y)和(s,t)，其距離計(jì)算公式[11]如下:

D8(p,q)=max(|x-s|,|y-t|)

(6)

如果D8小于設(shè)定閾值，則舍棄，并另選一組數(shù)據(jù)。通過(guò)實(shí)驗(yàn)測(cè)試，D8閾值設(shè)定為20時(shí)，仿射的結(jié)果穩(wěn)定，且隨機(jī)選取數(shù)據(jù)容易滿足閾值要求。

為了分析誤匹配對(duì)仿射結(jié)果的影響，本文從圖5所示有較多誤匹配的結(jié)果中，隨機(jī)選取了2000組初始數(shù)據(jù)，計(jì)算其仿射變換矩陣X。對(duì)X的6個(gè)分量進(jìn)行統(tǒng)計(jì)分析，發(fā)現(xiàn)各分量具有相似的統(tǒng)計(jì)分布，如圖7所示。

圖7 仿射變換矩陣分量m1的分布

2.3 二分查找法求解

m1分量的分布中，峰值處的值對(duì)應(yīng)最佳的仿射變換。從左右兩側(cè)遠(yuǎn)離峰值時(shí)，其頻數(shù)基本是遞減的。因此可以采用二分查找法來(lái)確定最佳的仿射變換。

具體步驟如下：

(1) 計(jì)算出當(dāng)前所有仿射變換矩陣特定分量的最大值MAX和最小值MIN，計(jì)算出中間值MID。圖7所示結(jié)果中，MAX=9.88， MIN=-7.64，MID=(MAX+MIN)/2=1.12。

(2) 將變換矩陣分為該分量大于和小于MID的兩類，并統(tǒng)計(jì)各類中矩陣個(gè)數(shù)，分別記為Num_H和Num_L。計(jì)得Num_H=636，Num_L=1364。

(3)比較Num_L和Num_H的大小，保留數(shù)量較多的一類。如果兩類個(gè)數(shù)相等，則隨機(jī)保留一類。因此，這里保留m1小于MID的部分。

(4)選取變換矩陣的下一個(gè)分量，重復(fù)以上步驟，至只剩下一個(gè)變換矩陣，即為最優(yōu)解。

圖8為應(yīng)用所得仿射變換矩陣對(duì)原圖像的邊框進(jìn)行變換，得到新的邊框，在待匹配圖像中可以很好地將目標(biāo)標(biāo)記出。

圖8 檢測(cè)結(jié)果

3 實(shí)驗(yàn)結(jié)果與分析

圖9為更換新的原圖像后的檢測(cè)結(jié)果。

圖9 新圖像匹配的結(jié)果

經(jīng)過(guò)篩選后，23對(duì)特征點(diǎn)匹配結(jié)果中仍存在大量的誤匹配點(diǎn)，其正確匹配率不足70%，系統(tǒng)依然得到了準(zhǔn)確的仿射結(jié)果，并在待匹配圖像中將目標(biāo)標(biāo)記出來(lái)。

為了詳細(xì)研究該算法的性能，本文通過(guò)設(shè)置不同的隨機(jī)選取數(shù)據(jù)組的數(shù)目，對(duì)圖9所示的匹配結(jié)果進(jìn)行分析，得出圖10所示，不同情況下算得正確仿射結(jié)果的概率。

圖10 不同初始化組數(shù)所得結(jié)果的正確率

結(jié)果顯示，正確率隨著選取的初始數(shù)據(jù)組數(shù)的增加而增大。大的初始組數(shù)將導(dǎo)致過(guò)大的算法開銷。當(dāng)初始組數(shù)達(dá)到128組時(shí)，系統(tǒng)的正確率超過(guò)95%，接近最佳正確率。

該算法的復(fù)雜度與初始數(shù)據(jù)的組數(shù)是正比關(guān)系。當(dāng)匹配點(diǎn)數(shù)數(shù)量較多時(shí)，相比于RANSAC算法[12]，本文提供的算法開銷更小，效率更高。

4 結(jié)論

對(duì)SIFT特征向量的匹配與篩選做了簡(jiǎn)單的討論，降低了誤匹配率。在此基礎(chǔ)上分析了原圖像與待匹配圖像的仿射變換矩陣各分量的統(tǒng)計(jì)分布，提出用二分查找法來(lái)求解最優(yōu)仿射變換的方法。該方法在特征向量誤匹配率較高的情況下，能夠快速得到最優(yōu)仿射變換，實(shí)現(xiàn)圖像目標(biāo)的檢測(cè)，且具有較高的穩(wěn)定性。

[1]Lowe D G.Object recognition from local scale-invariant features[C]//International Conference on Computer Vision.Washington,1999:1150-1157.

[2] David G Lowe.Distinctive image features from scale-invariant key-points[J].International Journal of Computer Vision,2004,60(60):91-110.

[3] Mikolajczyk K,Schmid C.Scale &Affine invariant interest point detectors[J].International Journal of Computer Vision,2004,60(1):63- 86.

[4] Kumar N A M,Sathidevi P S.Wavelet SIFT Feature Descriptors for Robust Face Recognition[C]//Advances in Computing and Information Techno-logy,Heidelberg:Springer Berlin Heidelberg,2013:851-859.

[5] WANG Meng,HONG Richang,LI Guangda,et al.Event driven web video sum-marization by tag localization and key-shot identification [J].IEEE Transactions on Multimedia(S1520- 9210),2012,14(4):975-985.

[6] WANG Meng,LI Hao,TAO Dachen,et al.Multimodal Graph-Based Reranking for Web Image Search [J].IEEE Transactions on Image Proces- sing(S1057-7149),2012,21(11):4649-4661

[7] Richard Szeliski.計(jì)算機(jī)視覺(jué)-算法與應(yīng)用[M].北京:清華大學(xué)出版社,2012.

[8] David A Forsyth,Jean Ponce.計(jì)算機(jī)視覺(jué)一種現(xiàn)代方法[M].北京:電子工業(yè)出版社,2004.

[9] Zhao Aigang,Wang Hongli,Yang Xiaogang,et al.Compressed sense SIFT descriptor mixed with geom-etrical feature[J].Infrared and Laser Engineering,2015,44(3):1085- 1091.

[10]傅衛(wèi)平,秦川,劉佳,等.基于SIFT 算法的圖像目標(biāo)匹配與定位[J].儀器儀表學(xué)報(bào),2011,32(1):163-169.

[11]岡薩雷斯.數(shù)字圖像處理[M].北京:電子工業(yè)出版社,2003.

[12]LI Bin,MING De-lie,YAN Wen-wen,et al.Image matching based on two-column histogram hashing and improved RANSAC[J].IEEE Geoscience and Remote Sensing Letters,2014,11 (8):1433-1437.

(責(zé)任編輯：馬金發(fā))

Optimization of SIFT Feature Matching Algorithm

DONG Huiying,XU Youju

(Shenyang Ligong University,Shenyang 110159,China)

Based on SIFT feature matching and image target detection applications,mismatching feature points on the target system will directly affect detection sensitivity.A binary search and affine transformation combined method is presented for rapidly detection of the target.Firstly，rough match is performed with a lower computational complexity nearest neighbor - next nearest neighbor method of SIFT feature points.Then,screening has been done with two matching feature points in main direction of the angular difference.Based on the statistical distribution of its parameters，some set of feature points are selected randomly to calculate the affine transformation parameters within the binary search method,by which the optimal solution is obtained and target detection is realized.The results show that the algorithm has higher detection efficiency and stability. Key words： SIFT;binary search;affine transform;probability distribution;matching;detection

2016-06-24

董慧穎(1962—)，女，教授，博士，研究方向：機(jī)器視覺(jué)與模式識(shí)別，人工智能。

1003-1251(2017)03-0054-04

TP391

A