基于支撐描述的SIFT匹配方法

鄭 紅 劉振強(qiáng) 溫天驍

(北京航空航天大學(xué) 自動化科學(xué)與電氣工程學(xué)院，北京100191)

圖像匹配從場景的兩幅或多幅圖像中確定點(diǎn)對應(yīng)關(guān)系，是計(jì)算機(jī)視覺的重要內(nèi)容，在圖像配準(zhǔn)三維重構(gòu)、目標(biāo)識別以及目標(biāo)跟蹤等領(lǐng)域有著廣泛應(yīng)用[1－5].

由于局部不變特征對圖像平移、旋轉(zhuǎn)、尺度、光照以及一定程度的視點(diǎn)變化具有不變性，基于局部不變特征的匹配方法可以獲得較為精確穩(wěn)定的圖像匹配效果.文獻(xiàn)[6]對多種局部不變特征算法進(jìn)行評估比較，發(fā)現(xiàn)尺度不變特征變換(SIFT，Scale Invariant Feature Transform)算法[7]在大多數(shù)測試中表現(xiàn)出優(yōu)秀的魯棒性和準(zhǔn)確性，可得到正確率較高的匹配結(jié)果.

但是由于SIFT只利用了特征點(diǎn)的局部鄰域梯度信息，對整體圖像中的局部相似結(jié)構(gòu)無法有效區(qū)分，當(dāng)圖像中出現(xiàn)重復(fù)的局部結(jié)構(gòu)時(shí)，極易發(fā)生誤匹配現(xiàn)象.針對這種情況，通過極幾何約束估計(jì)的方法來去除誤匹配，如 M-Estimators[8]，RANSAC(RANdom SAmple Consensus)等方法.但這些方法需要用全體匹配點(diǎn)對進(jìn)行迭代訓(xùn)練，其精度受錯(cuò)誤匹配率的影響較大[9].文獻(xiàn)[10]將全局上下文描述符與SIFT描述符通過加權(quán)方式組合在一起形成新的描述符，并通過PCA(Principal Component Analysis)降維后進(jìn)行匹配.由于需要為每個(gè)特征點(diǎn)計(jì)算新的高維特征描述符，其過程繁瑣，且PCA降維后描述符性能會有所下降.

為克服局部相似結(jié)構(gòu)等因素導(dǎo)致的錯(cuò)誤匹配，本文提出一種基于支持描述的SIFT匹配方法，利用SIFT初始匹配結(jié)果中具有較高穩(wěn)定性的匹配特征的分布信息建立支撐特征集，對穩(wěn)定性較低的匹配特征進(jìn)行支撐描述，進(jìn)而根據(jù)支撐描述符的匹配程度進(jìn)行誤匹配的剔除.算法利用了圖像中關(guān)鍵點(diǎn)分布的全局信息，能夠較好地區(qū)別局部相似結(jié)構(gòu)中的特征點(diǎn).

1 建立支撐特征集

1.1 SIFT 特征匹配

SIFT算法[7]包含了特征檢測、描述和匹配的過程，主要可分為5個(gè)步驟:尺度空間極值點(diǎn)檢測、特征點(diǎn)定位篩選、特征點(diǎn)主方向分配、特征描述向量生成及特征向量匹配.本文研究致力于SIFT特征向量的匹配過程以及誤匹配的去除，特征描述向量的生成仍采用文獻(xiàn)[7]所提出的方法.

圖像的SIFT特征描述向量生成后，文獻(xiàn)[7]采用描述向量的歐式距離作為圖像之間特征點(diǎn)的相似性判定度量.為排除因圖像遮擋和背景混亂而產(chǎn)生的無匹配關(guān)系的特征點(diǎn)，其使用最近鄰與次近鄰距離比值法進(jìn)行匹配.取圖像中的某個(gè)關(guān)鍵點(diǎn)，并找出待匹配圖像中與其歐式距離最近的前兩個(gè)關(guān)鍵點(diǎn)，如果最近鄰距離與次近鄰歐式距離的比值(r)小于閾值，則接受最近鄰點(diǎn)為匹配點(diǎn)，否則不匹配.閾值較高時(shí)，能夠得到大量匹配點(diǎn)，但錯(cuò)誤匹配率較高，取較低閾值能夠得到較高的正確匹配率，但是匹配點(diǎn)數(shù)大為減少.本文算法的目的就在于降低錯(cuò)誤匹配率的同時(shí)保留盡量多的正確匹配.

1.2 支撐特征集建立

根據(jù)文獻(xiàn)[7]針對SIFT匹配正誤在不同r值下的概率密度分布統(tǒng)計(jì)結(jié)果[7]，可知:當(dāng) r較低(小于0.35)時(shí)，匹配正確率較高，錯(cuò)誤匹配幾乎為零;r較高時(shí)，錯(cuò)誤匹配數(shù)量增多，匹配正確率下降，當(dāng)r＞0.8時(shí)，錯(cuò)誤匹配急劇增加.本文采用匹配特征最近鄰與次近鄰距離比值r作為匹配穩(wěn)定性的衡量，r值越高，匹配穩(wěn)定性越低.為建立支撐特征集，首先取較高 r閾值 Tr=0.8進(jìn)行SIFT匹配，獲得初始匹配集UI.然后對初始匹配集按r值由小到大排序，提取其中r較小的匹配點(diǎn)對組成支撐特征集US，初始匹配集中的剩余匹配點(diǎn)對構(gòu)成待判別匹配集UR=UI－US.

由于從實(shí)際圖像中獲取到的匹配r范圍不定，直接使用固定閾值不利于獲取密度穩(wěn)定的支撐特征集.故對初始匹配集排序后，取其中r較小的前20%作為支撐特征集.支撐特征集中的匹配點(diǎn)對具有較高穩(wěn)定性，以其分布信息為依據(jù)，可對待判別匹配集進(jìn)行誤匹配的剔除.

2 支撐描述

2.1 支撐描述符

獲得支撐特征集后，在每幅圖像中根據(jù)待判別特征點(diǎn)周圍支撐特征點(diǎn)的分布情況，分別構(gòu)建對應(yīng)的支撐描述符.當(dāng)特征點(diǎn)對的支撐描述相符程度較低時(shí)，認(rèn)為此特征點(diǎn)對為誤匹配.

支撐描述符是對待判別特征點(diǎn)周圍支撐特征點(diǎn)分布情況的描述.構(gòu)建支撐描述符前首先對支撐特征集中的每個(gè)特征點(diǎn)對賦予標(biāo)識編號，以使兩圖像中相互匹配的支撐特征點(diǎn)標(biāo)識編號相同，且每幅圖像中各支撐特征點(diǎn)標(biāo)識編號無重復(fù).算法中使用支撐特征點(diǎn)按r值排序后的排序編號作為標(biāo)識編號.

每幅圖像中支撐描述符的建立:以待判別特征點(diǎn)p為中心，以×形劃分圖像區(qū)域，形成ABCD 4個(gè)象限，如圖1所示;在每個(gè)象限中尋找n個(gè)距中心最近的支撐特征點(diǎn)作為p的支撐描述點(diǎn)，取4個(gè)象限共4n個(gè)支撐特征點(diǎn)的標(biāo)識編號集合作為該特征點(diǎn)的支撐描述符.若象限中支撐特征點(diǎn)不足n個(gè)，所欠缺描述點(diǎn)補(bǔ)零.

支撐描述符的維數(shù)決定于每個(gè)象限所選取點(diǎn)數(shù)n，由于支撐特征點(diǎn)本身的穩(wěn)定性，較少的點(diǎn)數(shù)即可實(shí)現(xiàn)穩(wěn)定的支撐描述，從而降低了計(jì)算復(fù)雜度.象限劃分選取支撐描述點(diǎn)的方法使支撐描述點(diǎn)能在待判別特征點(diǎn)周圍均勻分布，不會因某個(gè)方向支撐特征點(diǎn)密集而使描述點(diǎn)分布集中.

圖2為具有尺度變化的兩幅圖像中一對待判別特征點(diǎn)的支撐描述結(jié)果，十字標(biāo)示出待判別特征點(diǎn)位置，其支撐描述點(diǎn)由周圍圓圈標(biāo)出，每個(gè)象限選取點(diǎn)數(shù)n=3.

圖2 特征點(diǎn)對的支撐描述

由圖2可見對于兩幅含有尺度及視角變化圖像中的這一對待匹配特征點(diǎn)，其周圍支持描述點(diǎn)的分布基本一致，所對應(yīng)的支撐描述符可表示為

式中D(1pnew)與D(2pnew)分別為圖2所示左右圖中支撐描述點(diǎn)(圓圈標(biāo)出)的標(biāo)識編號的集合，標(biāo)識編號由支撐特征集按r值升序排序后相應(yīng)支撐特征點(diǎn)的序位得出.

2.2 支撐描述符的匹配

獲得待判別特征點(diǎn)對 pl，pr的支持描述符D(pl)，D(pr)后，通過衡量支持描述符的相似程度F(D(pl)，D(pr))，來判斷該特征點(diǎn)對是否匹配正確.兩支撐描述符的相似程度由其相同支撐描述點(diǎn)的比例決定，可通過式(1)獲得.

式中Num()表示集合中不為0元素個(gè)數(shù)的統(tǒng)計(jì).

通過式(2)判斷待判別特征點(diǎn)對是否匹配正確，如果滿足式(2)，認(rèn)為匹配正確，否則為誤匹配.

式中，r(pl，pr)表示SIFT匹配確定該特征點(diǎn)對時(shí)的最近鄰與次近鄰距離比值;λ為正比例常數(shù)，一般取λ=1.

由式(2)可見，匹配所需支撐描述的相似度與其所對應(yīng)r值成正比，r值越大，即特征點(diǎn)對匹配穩(wěn)定性越低時(shí)，需要支撐描述符的相似度越大，而對于r值較低的相對穩(wěn)定特征點(diǎn)對，支撐描述符的相似度要求較低.λ值是對支撐描述符相似度的整體調(diào)整，當(dāng)λ增大意味著需要更強(qiáng)的支撐描述.經(jīng)支撐描述符匹配判定正確的特征點(diǎn)對與支撐特征集中的特征點(diǎn)對合并，即獲得全部的正確匹配結(jié)果.

2.3 支撐特征集的動態(tài)擴(kuò)展

支撐特征集中特征點(diǎn)的數(shù)量及分布狀況直接影響支撐描述符的生成.當(dāng)初始匹配集中匹配點(diǎn)數(shù)目較多時(shí)，取穩(wěn)定性較高的前20%即可作為有效的支撐特征集.但是當(dāng)初始匹配點(diǎn)數(shù)目較少時(shí)，只取20%匹配點(diǎn)得到的支撐特征集可能存在特征點(diǎn)過少的問題，若任意提高從初始匹配集中取特征點(diǎn)的百分比，又會降低支撐特征集中支撐特征的穩(wěn)定性，導(dǎo)致生成支撐描述符的有效性降低.

針對上述情況，提出基于動態(tài)擴(kuò)展支撐特征集的支撐描述判別方法.

1)按1.2節(jié)方法獲得支撐特征集;

2)從待判別匹配集取出r值最小的匹配特征點(diǎn)對，使用當(dāng)前支撐特征集，按2.1節(jié)方法進(jìn)行支撐描述符的生成.

3)按2.2節(jié)方法進(jìn)行支撐描述符匹配，若經(jīng)支撐描述匹配判定為正確匹配，則將此特征點(diǎn)對加入支撐特征集中，否則舍棄;

4)重復(fù)步驟2)和3)，直至待判別匹配集為空，最終得到的支撐特征集即全部特征匹配結(jié)果.

支撐特征集的動態(tài)擴(kuò)展隨匹配的進(jìn)行不斷擴(kuò)展支撐特征集的規(guī)模，有利于提高支撐描述精確度.對于支撐特征集中可能存在的錯(cuò)誤匹配點(diǎn)對(無論來自初始支撐特征集還是動態(tài)擴(kuò)展中加入)，由于支撐描述符由多個(gè)描述點(diǎn)共同組成，少量支撐描述點(diǎn)的匹配錯(cuò)誤對于支撐描述符的匹配不會產(chǎn)生顯著影響，并且其影響只局限于錯(cuò)誤點(diǎn)所在的局部區(qū)域，不會導(dǎo)致全局匹配判定效果的累積惡化.因此支撐特征集動態(tài)擴(kuò)展能夠得到穩(wěn)定的匹配結(jié)果.

3 實(shí)驗(yàn)分析

實(shí)驗(yàn)圖像采用富含相似結(jié)構(gòu)的4種場景圖像(圖3)，圖像場景中包含平移、尺度、旋轉(zhuǎn)及視角變化.算法運(yùn)行軟硬件環(huán)境為:CPU 2.60 GHz，內(nèi)存 2 GB，Windows XP 系統(tǒng)，Matlab 7.11.

圖3 富含相似結(jié)構(gòu)的場景圖像對

為了比較算法的性能，對各圖像對分別采用SIFT算法、SIFT結(jié)合RANSAC去除誤匹配算法(簡稱SIFT+RANSAC)以及本文所提出的使用固定支撐集/擴(kuò)展支撐集的基于支撐描述的SIFT匹配算法(簡稱SIFT+SD/SIFT+ESD)進(jìn)行匹配性能對比.其中SIFT算法分別選擇Tr為0.8和0.6以比較不同閾值下的匹配效果;SIFT+RANSAC算法通過RANSAC方法擬合圖像間的基本矩陣去除誤匹配，歸一化后的距離閾值取為0.001;SIFT+SD算法取 SIFT初始匹配(Tr=0.8)r值較小的前20%為作為固定支撐特征集，每個(gè)象限支撐描述點(diǎn)數(shù)n=3，比例常數(shù)λ=1;SIFT+ESD算法采用動態(tài)擴(kuò)展的支撐特征集，取SIFT初始匹配(Tr=0.8)r值較小的前20%為作為初始支撐集，每個(gè)象限支撐描述點(diǎn)數(shù)n=3，比例常數(shù)λ=1.

表1～表4分別給出了各算法針對圖3所示4對場景圖像匹配正誤的具體數(shù)值比較.綜合對比可以看出，SIFT算法(Tr=0.8)匹配正確率最低，調(diào)低r閾值(Tr=0.6)雖然提高了匹配正確率，但是也消除了較多正確匹配.SIFT+RANSAC算法與所提SIFT+ESD算法都能夠保留原SIFT算法中的大部分正確匹配，但相比 SIFT+RANSAC算法，SIFT+ESD算法錯(cuò)誤匹配數(shù)量更少，匹配正確率維持在96%以上，表現(xiàn)出最好的效果.特別是當(dāng)原SIFT算法匹配錯(cuò)誤比例較高的情況下(表2、表3)，SIFT+RANSAC算法匹配結(jié)果不穩(wěn)定，錯(cuò)誤匹配明顯增多，而SIFT+ESD算法匹配效果則保持穩(wěn)定.同時(shí)，相對于動態(tài)擴(kuò)展支撐特征集的SIFT+ESD算法，使用固定支撐特征集的SIFT+SD算法效果略差.

表1 場景1圖像各算法匹配結(jié)果比較

表2 場景2圖像各算法匹配結(jié)果比較

表3 場景3圖像各算法匹配結(jié)果比較

表4 場景4圖像各算法匹配結(jié)果比較

為進(jìn)一步評估所提出算法的匹配效果，將各算法對正確匹配的保留效果和錯(cuò)誤匹配的消除效果進(jìn)行比較.以SIFT算法(Tr=0.8)獲得的正確和錯(cuò)誤匹配為基準(zhǔn)，根據(jù)表1～表4中數(shù)據(jù)得到低閾值SIFT算法(Tr=0.6)、SIFT+RANSAC算法、SIFT+SD算法以及SIFT+ESD算法的正確匹配保留率和錯(cuò)誤匹配消除率，如表5和表6所示.其中正確匹配保留率及錯(cuò)誤匹配消除率的計(jì)算如式(3)、式(4)所示.

表5 各算法正確匹配保留率比較 %

表6 各算法錯(cuò)誤匹配消除率比較 %

由表5及表6可見，調(diào)低Tr的SIFT算法能夠?qū)崿F(xiàn)較高的錯(cuò)誤匹配消除率，但是其正確匹配保留率明顯下降.SIFT+RANSAC算法能保證一定的正確匹配保留率，但其正確匹配保留率較高時(shí)，相應(yīng)錯(cuò)誤匹配消除率會明顯降低.本文提出的使用動態(tài)擴(kuò)展支撐特征集的基于支撐描述的SIFT匹配方法(SIFT+ESD)在不同場景圖像中都實(shí)現(xiàn)了較高的正確匹配保留率(90%以上)和錯(cuò)誤匹配消除率(90%以上)，在保留正確匹配的同時(shí)，能夠剔除更多錯(cuò)誤匹配.使用固定支撐特征集的SIFT+SD算法相對于動態(tài)擴(kuò)展支撐特征集的SIFT+ESD方法匹配效果略有不足，但與SIFT+RANSAC算法相當(dāng).

4 結(jié)論

本文提出了基于支持描述的SIFT匹配方法.通過針對不同場景圖像的匹配實(shí)驗(yàn)，得到以下結(jié)論:

1)支撐描述符能夠較好地區(qū)別局部相似結(jié)構(gòu)中的特征點(diǎn)，所提出方法能夠?qū)崿F(xiàn)較高的正確匹配保留率和錯(cuò)誤匹配消除率;

2)在初始誤匹配比例較大的情況下，所提出方法相比RANSAC方法有著更好的穩(wěn)定性;

3)根據(jù)不同特性建立支撐特征集，所提出支撐描述方法的思想可以較容易地?cái)U(kuò)展到其他特征匹配方法中.

References)

[1]蔡曉東，葉培建.基于特征點(diǎn)集的匹配算法應(yīng)用于衛(wèi)星姿態(tài)確定[J].北京航空航天大學(xué)學(xué)報(bào)，2006，32(2):171 －175

Cai Xiaodong，Ye Peijian.Image matching algorithm based on feature point set for satellite attitude calculation[J].Journal of Beijing University of Aeronauticsand Astronautics，2006，32(2):171－175(in Chinese)

[2]Piccinini P，Prati A，Cucchiara R.Real-time object detection and localization with SIFT-based clustering[J].Image and Vision Computing，2012，30(8):573 －587

[3]Ha S W，Moon Y H.Multiple object tracking using sift features and location matching[J].International Journal of Smart Home，2011，5(4):17 －26

[4]趙龍，肖軍波.一種改進(jìn)的運(yùn)動目標(biāo)抗遮擋跟蹤算法[J].北京航空航天大學(xué)學(xué)報(bào)，2013，39(4):517－520

Zhao Long，Xiao Junbo.Improved algorithm of tracking moving objects under occlusions[J].Journal of Beijing University of Aeronautics and Astronautics，2013，39(4):517 － 520(in Chinese)

[5]田越，張永梅，李波.遙感圖像的快速配準(zhǔn)方法[J].北京航空航天大學(xué)學(xué)報(bào)，2008，34(11):1356－1359

Tian Yue，Zhang Yongmei，Li Bo.Fast remote sensing image registration algorithm[J].Journal of Beijing University of Aeronautics and Astronautics，2008，34(11):1356 －1359(in Chinese)

[6]Mikolajczyk K，Schmid C.A performance evaluation of local descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(10):1615 －1630

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

[8]Chen J H，Chen C S，Chen Y S.Fast algorithm for robust template matching with M-estimators[J].IEEE Transactions on Signal Processing，2003，51(1):230 －243

[9]Sidibe D，Montesinos P，Janaqi S.Fast and robust image matching using contextual information and relaxation[C]//Avenida D.Proceedings of 2nd International Conference on Computer Vision Theory and Applications.Esquerdo，Setubal，Portugal:INSTICC Press，2007:68 －75

[10]Mortensen E N，Deng H，Shapiro L.A sift descriptor with global context[C]//Cordelia Schmid.IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Los Alamitos，CA:IEEE Computer Society，2005，1:184 －190