唐紅梅，張 恒，高金雍，王 霞，韓力英

(河北工業(yè)大學(xué)，天津 300401)

責(zé)任編輯:時(shí) 雯

圖像匹配就是通過對(duì)圖像內(nèi)容、特征、結(jié)構(gòu)、紋理及灰度等對(duì)應(yīng)關(guān)系、相似性和一致性進(jìn)行分析，尋求相同圖像目標(biāo)的方法。目前，圖像匹配技術(shù)被廣泛應(yīng)用于醫(yī)學(xué)、生物、軍事、遙感和航空航天等領(lǐng)域，是圖像處理應(yīng)用中不可或缺的技術(shù)。

基于SIFT(Scale Invariant Feature Transform)的匹配算法［1］是一種穩(wěn)定的特征匹配算法。SIFT特征是圖像的局部特征，對(duì)旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對(duì)視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性，具有良好的獨(dú)特性、多量性及可擴(kuò)展性。該算法在同類特征匹配算法中速度較快，但對(duì)于某些實(shí)時(shí)性要求較高的場合(如汽車匹配導(dǎo)航)，則無法滿足要求。

由于SIFT匹配算法復(fù)雜度高，尤其生成的特征向量是128維，使得算法效率受到影響。針對(duì)效率上的不足，不少國內(nèi)外研究學(xué)者做了不同的改進(jìn)，這些改進(jìn)主要集中在以下幾個(gè)方面:在對(duì)SIFT描述簡化上，如Mikolajczyk提出的GLOH(Gradient Location and Orientation Histogram)［2］及劉力等提出的 SSIFT 算法［3］;在降低 SIFT 向量維數(shù)上，如 Ke提出的 PCA－SIFT［4］，馬莉、韓燮將 PCASIFT技術(shù)應(yīng)用在圖像匹配中［5］，趙啟兵等提出為同心圓環(huán)劃分特征點(diǎn)鄰域的改進(jìn)算法［6］;在尺度空間簡化構(gòu)造上，如張羽等提出的基于DoM空間的SIFT改進(jìn)算法［7］，呂冀等基于Zoser金字塔的改進(jìn)算法［8］;在與其他算法結(jié)合上，如鄭永斌等的SIFT和旋轉(zhuǎn)不變LBP相結(jié)合的匹配算法［9］。然而這些算法在提高算法效率的同時(shí)，造成了算法精度和魯棒性的下降。

本文提出了一種改進(jìn)的基于SIFT特征的快速匹配算法，改進(jìn)算法首先使用D2OG算子［10］的過零檢測來生成特征向量，并針對(duì)此時(shí)可能導(dǎo)致匹配精度下降的問題，使用改進(jìn)的RANSAC(Random Sample Consensus)算法對(duì)匹配點(diǎn)對(duì)進(jìn)行二次消除錯(cuò)配。改進(jìn)算法用過零點(diǎn)檢測極值點(diǎn)代替經(jīng)典算法的局部極值點(diǎn)檢測，在保證了精度的同時(shí)，提高了SIFT匹配算法的實(shí)時(shí)性。

1 基于SIFT的匹配算法原理

SIFT匹配算法主要有3個(gè)步驟:特征點(diǎn)的檢測;特征向量的生成;特征向量的匹配。

1.1 特征點(diǎn)的檢測

高斯核被證明為唯一的可以用來產(chǎn)生尺度空間的線性卷積核。特征點(diǎn)檢測是在高斯差分尺度空間DOG(Difference of Gaussian)上進(jìn)行的，DOG是由不同尺度高斯核與圖像卷積構(gòu)造圖像的尺度空間函數(shù)相鄰層相減得到，即

如圖1所示，為了得到局部極值點(diǎn)，每組除底層和頂層的圖像，其他同組圖像的每個(gè)像素點(diǎn)都要進(jìn)行檢測，具體做法是每個(gè)待檢測像素點(diǎn)跟同層相鄰的8個(gè)像素點(diǎn)及其上一層和下一層相鄰的各9個(gè)像素點(diǎn)總共26個(gè)像素點(diǎn)相比較，若其比較結(jié)果都大于或都小于這26個(gè)像素點(diǎn)，則該點(diǎn)被看作一個(gè)空間局部極值點(diǎn)，并記錄該點(diǎn)所在的位置和尺度。對(duì)檢測到的初始極值點(diǎn)進(jìn)行三維二次函數(shù)曲線擬合以及一個(gè)2×2的Hessian矩陣來去除低對(duì)比度以及邊緣響應(yīng)點(diǎn)，以精確極值點(diǎn)的位置和尺度。利用鄰域像素梯度方向分布統(tǒng)計(jì)特性作為每一個(gè)特征點(diǎn)指定方向參數(shù)，以確保算子的旋轉(zhuǎn)不變性。至此提取的特征點(diǎn)具有位置、尺度、方向三個(gè)參數(shù)，且具有尺度和旋轉(zhuǎn)不變性。

圖1 DOG金字塔的構(gòu)造及局部極值點(diǎn)檢測

1.2 特征向量的生成

用特征描述符對(duì)特征點(diǎn)進(jìn)行描述，增加特征點(diǎn)的穩(wěn)定性與獨(dú)特性，使其對(duì)亮度、視角等變化保持不變，最終形成128維的特征向量。

1.3 特征向量的匹配

算法采用優(yōu)先k－d樹近似的BBF(Best Bin First)搜索算法快速搜索每個(gè)特征點(diǎn)的最近鄰與次近鄰，并計(jì)算它們的比值進(jìn)行匹配，最后利用RANSAC算法消除錯(cuò)配。

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

在特征點(diǎn)檢測的過程中，LOG與DOG的構(gòu)造占據(jù)80%左右的時(shí)間，簡化金字塔結(jié)構(gòu)、簡化特征點(diǎn)檢測方法，可以有效減少檢測時(shí)間，提高算法運(yùn)行速度。文獻(xiàn)［10］結(jié)合幾何學(xué)理論，提出了基于D2OG的特征點(diǎn)檢測算子。然而該算法在提高速度的同時(shí)，匹配精度有所下降，為此本文先用D2OG進(jìn)行極值點(diǎn)檢測，然后采用改進(jìn)的RANSAC算法來確保匹配的精度。這樣在保證算法精度的同時(shí)達(dá)到了提高算法速度的目的。

2.1 基于D2OG的過零檢測

2.1.1 D2OG過零檢測的理論依據(jù)

根據(jù)平面幾何學(xué)理論，原函數(shù)的極值點(diǎn)就是該函數(shù)一階導(dǎo)數(shù)等于零的點(diǎn)。由此可見，經(jīng)典算法在DOG金字塔中檢測的局部極值點(diǎn)對(duì)應(yīng)于DOG函數(shù)的一階導(dǎo)數(shù)的過零點(diǎn)。

對(duì)DOG進(jìn)行一次差分運(yùn)算得到D2OG函數(shù)，即

式中，D2(x，y，σ)為高斯二階差分函數(shù)。

由于

則

且 kσ － σ ≠0 ，故可知:D2(x，y，σ)=0?=0可見，D2OG函數(shù)的過零點(diǎn)就是DOG函數(shù)一階導(dǎo)數(shù)為零的點(diǎn)，也就是DOG的局部極值點(diǎn)。

2.1.2 D2OG 特征檢測過程

D2OG金字塔構(gòu)建如圖2所示。

圖2 D2OG金字塔構(gòu)造過程

同DOG構(gòu)建相同，每一組的DOG相鄰層相減得到一層D2OG圖像，該層的尺度為DOG層中減數(shù)的尺度?？梢?，D2OG金字塔擁有相同的組數(shù)，但每組層數(shù)比DOG少一層。

在D2OG每層中檢測零點(diǎn)時(shí)需要設(shè)一個(gè)閾值T，對(duì)每一層的絕對(duì)值與T進(jìn)行比較，小于等于T的像素點(diǎn)作為特征點(diǎn)，記錄該點(diǎn)的信息(x，y，σ)。閾值T的選擇是關(guān)鍵，過大或過小都可能會(huì)影響匹配的精度，還會(huì)帶來程序運(yùn)行時(shí)間的增加。考慮算法精度和速度兩個(gè)因素，T在［200，500］內(nèi)可實(shí)現(xiàn)較好的折中。精確定位時(shí)，為了獲得亞像素級(jí)精度，需要將D2OG中檢測到的特征點(diǎn)映射回DOG空間中。

采用改進(jìn)算法構(gòu)造金字塔時(shí)，每組可減少一層高斯濾波圖像，構(gòu)建幾組就可以減少幾層，前面提到，在特征檢測環(huán)節(jié)，金字塔的構(gòu)造占據(jù)80%的時(shí)間，因此改進(jìn)算法簡化了金字塔的構(gòu)造。另外，D2OG算子的二維平面檢測在算法復(fù)雜度上也低于經(jīng)典算法的三維空間局部檢測。因此，理論上改進(jìn)算法實(shí)時(shí)性高于經(jīng)典算法。

2.2 改進(jìn)的RANSAC算法

當(dāng)提供的特征點(diǎn)數(shù)目較少時(shí)，RANSAC性能可能有所降低。由于受本文D2OG中閾值T的選取影響，特征點(diǎn)數(shù)目少于經(jīng)典算法從而生成的匹配點(diǎn)對(duì)數(shù)目減少，而匹配點(diǎn)對(duì)數(shù)目的減少可能導(dǎo)致匹配中存在誤匹配對(duì)，導(dǎo)致的匹配精度降低。

針對(duì)以上問題，采用改進(jìn)的RANSAC算法進(jìn)行特征點(diǎn)對(duì)提純，消除誤匹配對(duì)，從而提高匹配精度。改進(jìn)算法的具體步驟如下:

1)在n個(gè)數(shù)據(jù)點(diǎn)集中隨機(jī)抽取4對(duì)特征點(diǎn)對(duì)，并將其設(shè)為初始內(nèi)點(diǎn)集合，計(jì)算出變換矩陣H。將集合外的n－4個(gè)點(diǎn)看作外點(diǎn)，依次計(jì)算經(jīng)過H變換后到對(duì)應(yīng)匹配點(diǎn)的距離，小于閾值距離，則將當(dāng)前點(diǎn)納入內(nèi)點(diǎn)集合。記錄在此H下的內(nèi)點(diǎn)數(shù)量。

2)重復(fù)步驟1)操作k次，選擇具有內(nèi)點(diǎn)數(shù)量最多的集合并將該集合的內(nèi)點(diǎn)作為估計(jì)的初始值，再使用RANSAC算法將新求出的內(nèi)點(diǎn)集合與原來的內(nèi)點(diǎn)集合并集為新的內(nèi)點(diǎn)集合。

3)選取兩次內(nèi)點(diǎn)并集后內(nèi)點(diǎn)數(shù)量最多的集合作為最佳集合，將該集合下的變換矩陣作為最佳估計(jì)的變換矩陣。

改進(jìn)的RANSAC算法對(duì)提取的匹配點(diǎn)進(jìn)一步檢驗(yàn)并消除誤匹配點(diǎn)對(duì)，以消耗小部分時(shí)間為代價(jià)，保證了匹配的精度。

下文通過實(shí)驗(yàn)對(duì)經(jīng)典算法與改進(jìn)算法的性能進(jìn)行比較，以驗(yàn)證上述思路。

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

在進(jìn)行實(shí)驗(yàn)之前，為了表述方便，將經(jīng)典算法稱為SIFT，將基于D2OG檢測算子的 SIFT匹配算法稱為DSIFT，并將繼續(xù)加入改進(jìn)RANSAC算法后的改進(jìn)算法稱為DRSIFT。所有的程序?qū)嶒?yàn)都是以VC++6.0為平臺(tái)，在操作系統(tǒng)為Windows7，主頻為Inter(R)Core(TM)2 Duo CPU T6600 2.2 GHz，內(nèi)存為4 Gbyte的PC機(jī)上完成。實(shí)驗(yàn)所用圖像均由筆者使用手機(jī)數(shù)碼相機(jī)實(shí)際拍攝。

3.1 程序流程圖

改進(jìn)算法程序流程圖如圖3所示。

圖3 改進(jìn)算法流程圖

3.2 基于D2OG算子的閾值選取

基于D2OG檢測算子在過零點(diǎn)檢測過程中引入閾值T，閾值大小的選取是檢測的關(guān)鍵。閾值過大會(huì)引入錯(cuò)誤的特征點(diǎn)并增加算法運(yùn)行時(shí)間;閾值過小，會(huì)漏掉部分正確的特征點(diǎn)，影響匹配精度。下面以一張大小為371×352的圖像為實(shí)驗(yàn)對(duì)象，為了選取合適的閾值，實(shí)驗(yàn)以經(jīng)典算法作對(duì)比，分別在T=200，T=400，T=500時(shí)統(tǒng)計(jì)極值點(diǎn)數(shù)及運(yùn)行時(shí)間，如圖4所示。

圖4 不同閾值下的DRSIFT與SIFT極值點(diǎn)檢測對(duì)比

實(shí)驗(yàn)數(shù)據(jù)如表1所示，分析表1數(shù)據(jù)可以發(fā)現(xiàn):閾值T的選取決定了極值點(diǎn)的數(shù)目和運(yùn)行時(shí)間。閾值為500時(shí)，引入錯(cuò)誤特征點(diǎn)，同時(shí)增加運(yùn)行時(shí)間;閾值為200時(shí)，檢測的極值點(diǎn)數(shù)目很少，特征點(diǎn)是從極值點(diǎn)中得到的，因此，不能提供足夠的極值點(diǎn)會(huì)影響后期的匹配工作，影響匹配精度。由此可見，閾值選取由小到大，匹配精度是先升后降的過程。本文在綜合考慮算法的精度和速度兩個(gè)因素后，認(rèn)為T=400時(shí)可實(shí)現(xiàn)較好的折中。

表1 DRSIFT閾值T的選取及與經(jīng)典算法的比較

3.3 改進(jìn)算法的綜合性能比較

為了檢驗(yàn)改進(jìn)算法的匹配性能，本文將SIFT，DSIFT和DRSIFT進(jìn)行比較。實(shí)驗(yàn)使用的圖片包括不同尺度縮放圖片、不同的旋轉(zhuǎn)圖片、不同視角變化的圖片以及添加了噪聲和光照等復(fù)雜變化的圖片。為了較全面地驗(yàn)證算法的性能，實(shí)驗(yàn)以特征點(diǎn)數(shù)、特征點(diǎn)檢測時(shí)間、匹配點(diǎn)對(duì)數(shù)、錯(cuò)配點(diǎn)對(duì)數(shù)、正確匹配率以及運(yùn)行總時(shí)間6個(gè)方面對(duì)SIFT，DSIFT和DRSIFT進(jìn)行比較。其中，特征點(diǎn)數(shù)是指基準(zhǔn)圖像的特征點(diǎn)數(shù)目;特征點(diǎn)檢測時(shí)間是基準(zhǔn)圖像特征點(diǎn)檢測所消耗的時(shí)間;匹配點(diǎn)對(duì)數(shù)是SIFT與DSIFT經(jīng)過RANSAC算法以及DRSIFT經(jīng)過改進(jìn)RANSAC算法后保留的匹配點(diǎn)對(duì)數(shù)。

實(shí)驗(yàn)匹配效果如圖5～8，其中線段端點(diǎn)分別是基準(zhǔn)圖像與待匹配圖像對(duì)應(yīng)的匹配點(diǎn)。

實(shí)驗(yàn)數(shù)據(jù)如表2所示，算法中的參數(shù)均為Lowe原文中推薦的參數(shù)。DISFT與DRSIFT選取的閾值為T=400。

分析實(shí)驗(yàn)數(shù)據(jù)可以發(fā)現(xiàn):在不同幾何變換或光學(xué)畸變下，DRSIFT算法特征點(diǎn)檢測時(shí)間要低于SIFT算法，可見，D2OG算子實(shí)時(shí)性優(yōu)于DOG算子。DRSIFT算法總運(yùn)行時(shí)間低于SIFT算法，可見DRSIFT算法復(fù)雜度低于SIFT算法，速度更快。DRSIFT算法正確匹配率與SIFT算法相當(dāng)，DRSIFT算法匹配點(diǎn)對(duì)數(shù)少于SIFT算法，錯(cuò)誤匹配點(diǎn)對(duì)數(shù)少于SIFT算法，可見采用改進(jìn)的RANSAC算法在進(jìn)行二次估計(jì)時(shí)消除了部分誤匹配。DRSIFT算法與DSIFT算法總運(yùn)行時(shí)間相差不大，可見改進(jìn)RANSAC算法運(yùn)行時(shí)間與初始匹配點(diǎn)對(duì)數(shù)有關(guān)并且時(shí)間消耗很少，以犧牲小部分時(shí)間為代價(jià)，提高了匹配精度。

表2 SIFT，DSIFT和DRSIFT性能比較

由此可以得出DRSIFT算法的優(yōu)點(diǎn)在于:在基本保持高精度、幾何形變、光照等不變性的基礎(chǔ)上，降低算法的復(fù)雜度和時(shí)間代價(jià)，提高了算法的運(yùn)行速度。

與SIFT經(jīng)典算法相比，DRSIFT算法的缺點(diǎn)在于:盡管引入改進(jìn)RANSAC算法提高匹配精度，但當(dāng)DRSIFT算法在圖像輪廓邊界信息較少或存在復(fù)雜畸變時(shí)，匹配精度與經(jīng)典算法相比仍然有所下降。

4 結(jié)論

本文提出了一種改進(jìn)的基于SIFT特征的快速匹配算法。改進(jìn)算法通過簡化金字塔結(jié)構(gòu)、降低特征檢測算子復(fù)雜度，二次篩選匹配點(diǎn)對(duì)，在保證算法高精度的同時(shí)提高了算法的速度。改進(jìn)算法適用于圖像信息較豐富且對(duì)實(shí)時(shí)性有一定要求的場合。改進(jìn)算法的缺點(diǎn)在于匹配點(diǎn)對(duì)數(shù)目相對(duì)較少，限制了算法處理的圖像類型(如邊緣輪廓較少的圖像)。因此，如何提高匹配點(diǎn)對(duì)數(shù)目以及在匹配點(diǎn)對(duì)數(shù)目較少的情況下如何進(jìn)行更準(zhǔn)確的參數(shù)估計(jì)是需要進(jìn)一步學(xué)習(xí)研究的問題。

［1］LOWE D G.Distinctive image from scale－invariant keypoint［J］.International Journal of Omputer Vision，2004，60(2):20.

［2］MIKOLAJCZYK K，SCHMID C.A performance evaluation of local descriptors［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，2005，27(10):1615－1630.

［3］劉力，彭復(fù)員，趙坤，等.采用簡化SIFT算法實(shí)現(xiàn)快速推向匹配［J］.紅外與激光工程，2008，37(1):186－189.

［4］KE Y ，SUKTHANKAR R.PCA－sift:A more distinctive representation for local image descriptors［C］//Proc.CVRP 2004.［S.l.］:IEEE Press，2004:506－513.

［5］馬莉，韓燮.主成分分析法(PCA)在SIFT匹配算法中的應(yīng)用［J］.電視技術(shù)，2012，36(1):129－132.

［6］趙啟兵，王養(yǎng)柱，胡永浩.基于改進(jìn)SIFT算法的無人機(jī)遙感影像匹配［J］.光電與控制，2012，19(3):36－39.

［7］張羽，朱丹，王玉良.一種改進(jìn)的快速SIFT特征匹配算法［J］.微計(jì)算機(jī)信息，2008，24(33):226－228.

［8］呂冀，高洪民，汪渤，等.圖像制導(dǎo)的目標(biāo)匹配算法與系統(tǒng)設(shè)計(jì)［J］.彈箭與制導(dǎo)學(xué)報(bào)，2009，29(5):43－45.

［9］鄭永斌，黃新生，豐松江.SIFT和旋轉(zhuǎn)不變LBP相結(jié)合的圖像匹配算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2010，22(2):286－292.

［10］曹娟，李興瑋，林偉廷，等.SIFT特征匹配算法改進(jìn)研究［J］.系統(tǒng)仿真學(xué)學(xué)報(bào)，2010，22(11):2760－2763