蔣中杰，程筱勝，崔海華，張益華

(南京航空航天大學(xué) 機(jī)電學(xué)院，江蘇 南京 210016)

一種面向SIFT特征匹配的過(guò)濾新算法

蔣中杰，程筱勝，崔海華，張益華

(南京航空航天大學(xué) 機(jī)電學(xué)院，江蘇 南京 210016)

針對(duì)SIFT匹配算法存在誤匹配的情況，提出了一種基于三角形相似的匹配特征點(diǎn)過(guò)濾算法，即在SIFT算法中使用歐式距離判斷特征點(diǎn)相似性后，對(duì)匹配的特征點(diǎn)構(gòu)造三角形，通過(guò)判別三角形相似對(duì)匹配特征點(diǎn)進(jìn)行進(jìn)一步過(guò)濾。實(shí)驗(yàn)結(jié)果表明，三角形相似算法能大大提高匹配精度。

圖像拼接；SIFT算法；三角形相似；匹配點(diǎn)過(guò)濾

圖像配準(zhǔn)是對(duì)有重疊區(qū)域的圖像進(jìn)行匹配，進(jìn)而獲得圖像間位置關(guān)系的分析處理技術(shù)。圖像配準(zhǔn)在很多行業(yè)都有著廣泛的應(yīng)用。但是在實(shí)際應(yīng)用中，需要匹配的兩幅圖像之間通常存在著平移、旋轉(zhuǎn)、尺度、視角等差異，這些都是圖像配準(zhǔn)會(huì)碰到并需要解決的問(wèn)題。圖像匹配算法中，基于灰度相關(guān)匹配算法(如SSDA，MMSE等)的主要缺點(diǎn)是當(dāng)圖像發(fā)生旋轉(zhuǎn)、視角、尺度、亮暗變化時(shí)，算法會(huì)很不穩(wěn)定；而基于特征的圖像匹配算法(例如SIFT，Harris等)對(duì)圖像幾何變形、亮暗變化都有很高的魯棒性。目前圖像配準(zhǔn)的主要研究方向都集中在基于特征的圖像配準(zhǔn)。文獻(xiàn)[1]、[2]對(duì)幾種具有代表性的基于特征的圖像匹配算法進(jìn)行了研究，發(fā)現(xiàn)SIFT算法是魯棒性最高的特征匹配算法。

雖然SIFT算法已經(jīng)在很多領(lǐng)域被成功應(yīng)用[1-3]，但是SIFT算法在匹配精度上還有很大改進(jìn)空間。文獻(xiàn)[4]將SIFT算法和RANSAC算法結(jié)合以去除不可靠的匹配點(diǎn)，可惜的是RANSAC算法雖然能濾除大部分的誤匹配點(diǎn)，但卻不能保證去掉所有的誤匹配點(diǎn)。文獻(xiàn)[5]、[6]提出了雙向匹配的濾除策略，但是雙向匹配需要自定義閾值。文獻(xiàn)[7]對(duì)圖像增加了彩色信息，可是在增加了彩色信息后，濾除的匹配點(diǎn)會(huì)比較多，在圖像少特征點(diǎn)的情況下可能導(dǎo)致圖像無(wú)法匹配。

本文提出了一種基于三角形相似的過(guò)濾新算法，通過(guò)判斷三角形相似甄別匹配點(diǎn)是否正確。與其他過(guò)濾算法相比，三角形相似法過(guò)濾的特征點(diǎn)較少，但是正確率卻會(huì)大大提高。

1 SIFT算法

SIFT匹配算法流程主要由4步構(gòu)成：構(gòu)建高斯尺度空間、特征點(diǎn)檢測(cè)、特征點(diǎn)描述符生成和特征匹配[8-9]。

1.1尺度空間特征點(diǎn)

文獻(xiàn)[10]證明了高斯核函數(shù)是可以實(shí)現(xiàn)尺度變化的唯一核函數(shù)。采集的圖像經(jīng)過(guò)不同尺度高斯模糊，將采樣生成N層高斯尺度空間金字塔，然后將高斯尺度空間金字塔中每一層的圖像再做不同參數(shù)的高斯模糊，使得高斯尺度空間金字塔每一層都有多張圖像，其中同一層的圖像大小相同。然后把同層高斯尺度空間金字塔中的相鄰金字塔層圖像相減，得到DoG(Difference of Gaussian，簡(jiǎn)稱DoG算子)差分金字塔。DoG差分空間函數(shù)D(x,y,σ)定義如下：

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ)×I(x,y))=L(x,y,kσ)-L(x,y,σ)

式中：G(x,y,σ)為高斯函數(shù)(尺度可變)；I(x,y)為原始圖像；L(x,y,σ)為經(jīng)過(guò)高斯模糊的圖像；k為不變尺度比例因子；σ為高斯尺度。

DoG差分金字塔建立后，比較每個(gè)像素點(diǎn)的周圍8個(gè)像素點(diǎn)，以及它相鄰尺度圖像中的各9個(gè)像素點(diǎn)。如果該點(diǎn)為極值點(diǎn)，那么把該點(diǎn)作為候選特征點(diǎn)。

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

通過(guò)上述方法檢測(cè)到的極值點(diǎn)是離散空間的極值點(diǎn)，由于DoG算子會(huì)產(chǎn)生較強(qiáng)的邊緣響應(yīng)，所以通過(guò)擬合三維二次函數(shù)來(lái)精確確定關(guān)鍵點(diǎn)的位置和尺度，去除低對(duì)比度的關(guān)鍵點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)，能增強(qiáng)匹配穩(wěn)定性，提高抗噪聲能力。

1.3特征點(diǎn)主方向

為了讓描述子具有旋轉(zhuǎn)不變性，需要利用局部特征為特征點(diǎn)確定一個(gè)方向。利用圖像梯度，可求得特征點(diǎn)的方向。梯度的幅值與方向角計(jì)算公式如下：

m(x,y)=[L(x+1)-L(x-1,y)]2+[L(x,y+1)-L(x,y-1)2]1/2

式中：m(x,y)為梯度幅值；θ(x,y)為梯度方向。

完成特征點(diǎn)的梯度值計(jì)算后，用直方圖統(tǒng)計(jì)出領(lǐng)域像素梯度和方向。梯度直方圖把360°的方向范圍平均分成36柱。直方圖的梯度幅值中的峰值代表特征點(diǎn)的主方向。同時(shí)保留其他梯度幅值大于主方向梯度幅值80%的作為輔方向。特征點(diǎn)可以有多個(gè)方向。

1.4計(jì)算特征點(diǎn)描述子

(1)選取特征點(diǎn)領(lǐng)域，然后把選取的鄰域均勻地分為4×4個(gè)窗口，對(duì)每個(gè)窗口計(jì)算梯度方向直方圖。(2)對(duì)4×4個(gè)窗口的8個(gè)方向的梯度直方圖以位置依次排序，得到一個(gè)4×4×8共128維的向量，這個(gè)向量是圖像信息的一種表示，是具有唯一性的。(3)把特征描述子歸一化，除去亮暗變化的影響，最終得到對(duì)尺度變化、亮暗變換和旋轉(zhuǎn)有較高魯棒性的SIFT局部特征描述子。

1.5特征點(diǎn)匹配

因?yàn)樘卣鼽c(diǎn)可能有較強(qiáng)的獨(dú)特性，其匹配點(diǎn)對(duì)特征向量的歐式距離較大是正常的。一種比較有效的方法是在匹配時(shí)比較與關(guān)鍵點(diǎn)的特征向量最近的和次近的關(guān)鍵點(diǎn)。取圖像1中的某個(gè)關(guān)鍵點(diǎn)，并找出其與圖像2中歐式距離最近的前2個(gè)關(guān)鍵點(diǎn)，在這2個(gè)關(guān)鍵點(diǎn)中，如果最近的距離除以次近的距離少于某個(gè)比例閾值，則接受這一對(duì)匹配點(diǎn)。

2 基于三角形相似的過(guò)濾算法

為了排除因?yàn)閳D像遮擋和背景混亂而產(chǎn)生的無(wú)匹配關(guān)系的關(guān)鍵點(diǎn)，Lowe提出了比較最近鄰距離與次近鄰距離的方法，距離比率ratio小于某個(gè)閾值的認(rèn)為是正確匹配。因?yàn)閷?duì)于錯(cuò)誤匹配，由于特征空間的高維性，相似的距離可能有大量其他的錯(cuò)誤匹配，從而導(dǎo)致它的ratio值比較高。Lowe推薦ratio的閾值為0.8。本文針對(duì)特征點(diǎn)比較少的牙模圖像進(jìn)行拼接，比例閾值選取0.9。特征點(diǎn)數(shù)目較多時(shí)，誤匹配也較多。

2.1三角形定義

三角形由2個(gè)基本點(diǎn)和1個(gè)變換點(diǎn)構(gòu)成。經(jīng)過(guò)歐式距離法后，兩幅圖像中的匹配點(diǎn)分別在點(diǎn)集P和點(diǎn)集Q中。在點(diǎn)集P中的每一個(gè)特征點(diǎn)，在點(diǎn)集Q中都有特征點(diǎn)與之對(duì)應(yīng)。在點(diǎn)集P中隨機(jī)選取2個(gè)特征點(diǎn)P1，P2作為基本點(diǎn)，在剩余點(diǎn)中按照順序選取一個(gè)點(diǎn)Px(x為剩余點(diǎn)中的一個(gè))與基本點(diǎn)組成三角形。如圖1所示，可以理解為三角形底邊不變，頂點(diǎn)不斷發(fā)生變化。在點(diǎn)集Q中選出的點(diǎn)為點(diǎn)集P中選取點(diǎn)的對(duì)應(yīng)匹配點(diǎn)，同樣操作，可以得到一個(gè)個(gè)對(duì)應(yīng)的三角形。

圖1 構(gòu)造三角形

2.2三角形相似判斷

判斷兩三角形相似的方法有3種，分別是：(1)三邊對(duì)應(yīng)成比例；(2)兩個(gè)對(duì)應(yīng)角相等；(3)一個(gè)對(duì)應(yīng)角相等，對(duì)應(yīng)角的鄰邊對(duì)應(yīng)成比例。實(shí)際情況中，圖像會(huì)有尺度、旋轉(zhuǎn)等變化，在圖像旋轉(zhuǎn)過(guò)程中，三角形的角度變化會(huì)很大，所以選擇三邊對(duì)應(yīng)成比例作為判斷三角形相似的依據(jù)。圖像經(jīng)過(guò)變化，三角形不可能完全相似，因此需要設(shè)定一個(gè)允許的誤差范圍。經(jīng)過(guò)實(shí)驗(yàn)，發(fā)現(xiàn)誤差閾值κ設(shè)定在0.9的時(shí)候，能夠在保證正確率的同時(shí)，保留很多的特征點(diǎn)。

三角形相似過(guò)濾流程如下：

第一步，取點(diǎn)集P中任意2個(gè)點(diǎn)P1,P2，與在剩余點(diǎn)中取一個(gè)點(diǎn)P3組成三角形，定義為△P1P2P3，那么點(diǎn)集Q中能有3個(gè)點(diǎn)Q1，Q2，Q3，與點(diǎn)集P中的P1,P2,P3為對(duì)應(yīng)的匹配特征點(diǎn)，點(diǎn)Q1，Q2，Q3也組成一個(gè)三角形△Q1Q2Q3。

第二步，如果△P1P2P3∽△Q1Q2Q3，將P1,P2作為基礎(chǔ)點(diǎn)，并將P3放入正確點(diǎn)集I中。繼續(xù)從剩余點(diǎn)中取出變換點(diǎn)，與基礎(chǔ)點(diǎn)判斷相似，相似就為正確點(diǎn)，不相似就為誤匹配點(diǎn)?；A(chǔ)點(diǎn)同樣是正確點(diǎn)。如果△P1P2P3與△Q1Q2Q3不相似，那么把這3個(gè)點(diǎn)都作為變換點(diǎn)，在剩下的點(diǎn)中重新選取基礎(chǔ)點(diǎn)和變換點(diǎn)，直到所取3個(gè)點(diǎn)與對(duì)應(yīng)3個(gè)點(diǎn)組成的三角形相似。

第三步，將過(guò)濾過(guò)一次的所有正確點(diǎn)按照上述方法再過(guò)濾一遍。經(jīng)過(guò)兩次過(guò)濾后，剩下的匹配點(diǎn)就認(rèn)為都是正確的匹配特征點(diǎn)。

2.3算法流程

圖像經(jīng)過(guò)構(gòu)建尺度空間、特征點(diǎn)檢測(cè)、特征點(diǎn)描述得到了特征點(diǎn)。經(jīng)由歐氏距離相似性度量后得到匹配的特征點(diǎn)。此時(shí)的匹配點(diǎn)對(duì)中存在很多的錯(cuò)誤匹配點(diǎn)，用三角形相似算法對(duì)匹配點(diǎn)進(jìn)行過(guò)濾。經(jīng)過(guò)這些步驟，得到了準(zhǔn)確性更高的匹配點(diǎn)對(duì)。

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

為了驗(yàn)證本文算法對(duì)圖像偏轉(zhuǎn)以及圖像放大縮小的適應(yīng)性，下面分別對(duì)這兩種情況進(jìn)行驗(yàn)證。實(shí)驗(yàn)圖像大小為1 024×768像素，由IMAGINGSOURCE相機(jī)采集。

第一組3幅實(shí)驗(yàn)圖對(duì)圖像的偏轉(zhuǎn)進(jìn)行了驗(yàn)證。圖2(a)為原圖，圖2(b)為圖2(a)偏轉(zhuǎn)20°左右拍攝的圖，圖2(c)為圖2(a)偏轉(zhuǎn)40°左右拍攝的圖。圖3中的3幅圖為經(jīng)過(guò)RANSAC算法過(guò)濾的特征點(diǎn)匹配圖，其中圖3(a)為圖2(a)與圖2(b)特征點(diǎn)匹配圖，圖3(b)為圖2(a)和圖2(c)特征點(diǎn)匹配圖。圖4中的2幅圖為經(jīng)過(guò)本文三角形過(guò)濾的特征點(diǎn)匹配圖，其中圖4(a)為圖2(a)與圖2(b)特征點(diǎn)匹配圖，圖4(b)為圖2(a)和圖2(c)特征點(diǎn)匹配圖。表1為圖2(a)與圖2(b)匹配結(jié)果比對(duì)，表2為圖2(a)與圖2(c)匹配結(jié)果比對(duì)。

圖2 圖像旋轉(zhuǎn)配準(zhǔn)

表1 圖2(a)與圖2(b)匹配結(jié)果

圖3 旋轉(zhuǎn)20°配準(zhǔn)圖像

圖4 旋轉(zhuǎn)40°配準(zhǔn)圖像

表2 圖2(a)與圖2(c)匹配結(jié)果

在多次偏轉(zhuǎn)圖像實(shí)驗(yàn)中，經(jīng)過(guò)三角形相似過(guò)濾的特征點(diǎn)的準(zhǔn)確率能保持在98%以上。

第二組2幅實(shí)驗(yàn)圖對(duì)圖像的放大縮小進(jìn)行了驗(yàn)證。圖5(a)為原圖，圖5(b)為圖5(a)放大圖。圖6所示為經(jīng)過(guò)RANSAC算法過(guò)濾的特征點(diǎn)匹配圖。圖7所示為經(jīng)過(guò)本文三角形過(guò)濾的特征點(diǎn)匹配圖。表3為圖5(a)與圖5(b)匹配結(jié)果比對(duì)。

圖5 圖像大小變化

圖6 RANSAC算法配準(zhǔn)圖 圖7 三角形相似配準(zhǔn)圖

表3 圖5(a)與圖5(b)匹配結(jié)果

從實(shí)驗(yàn)結(jié)果來(lái)看，三角形過(guò)濾與RANSAC算法相比在正確率方面有比較大的優(yōu)勢(shì)，在運(yùn)算時(shí)間上也有一定優(yōu)勢(shì)。只不過(guò)三角形過(guò)濾是在犧牲了很多正確點(diǎn)的情況下才保證了正確率，同時(shí)在特征點(diǎn)比較多的時(shí)候，三角形相似算法正確率也會(huì)有所下降。

4 結(jié)束語(yǔ)

文中所提算法是基于SIFT算法的一種改進(jìn)過(guò)濾算法，該算法在SIFT算法用歐式距離判斷相似性的基礎(chǔ)上，用三角形相似對(duì)匹配點(diǎn)進(jìn)行進(jìn)一步過(guò)濾。實(shí)驗(yàn)結(jié)果表明，該算法在匹配特征點(diǎn)的準(zhǔn)確率上有了很大提高，同時(shí)也縮短了匹配時(shí)間。但是該算法在過(guò)濾了錯(cuò)誤匹配點(diǎn)的同時(shí)也過(guò)濾了很多正確的匹配點(diǎn)對(duì)，在今后的研究中，將努力改進(jìn)此過(guò)濾算法，在保證準(zhǔn)確率的同時(shí)，保留更多的正確匹配點(diǎn)。

[1] Mikolajczyk K，Tuytelaars T，Schmid C，et al．A comparison of affine region detectors[J]．International Journal of Computer Vision，2005，65(1/2)：43-72.

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

[3] Foroosh H，Zerubia J B，Berthod Marc．Extension of phase correlation to sub pixel registration[J]．IEEE Transactions on Image Processing，2002，11(3)：188-200.

[4] 常青，張斌，邵金玲．基于SIFT和RANSAC的特征圖像匹配方法[J]．華東理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，38(6)：747-751.

[5] 劉煥敏，王華，段慧芬．一種改進(jìn)的SIFT雙向匹配算法[J]．兵工自動(dòng)化，2009，28(6)：89-91.

[6] 霍春雷，周志鑫，劉青山，等．基于SIFT特征和廣義緊互對(duì)原型對(duì)距離的遙感圖像配準(zhǔn)方法[J]．遙感技術(shù)與應(yīng)用，2007，22(4)：524-530.

[7] 張銳娟，張建奇，楊翠，等．基于CSIFT的彩色圖像配準(zhǔn)技術(shù)研究[J]．光學(xué)學(xué)報(bào)，2008，28(11)：2097-2103.

[8] 袁杰．基于SIFT的圖像配準(zhǔn)與拼接技術(shù)研究[D]．南京：南京理工大學(xué)，2013.

[9] 吳慧蘭，劉國(guó)棟，劉炳國(guó)，等．基于SIFT算法的圓心快速精確定位技術(shù)研究[J]．光電子·激光，2008，19(11)：1512-1515.

[10] Lowe D G．Distinctive image features from scale-invariant keypoints[J]．International Journal of Computer Vision，2004，60(2)：91-110.

ANewAlgorithmforFilteringSIFTFeatureMatching

JIANG Zhongjie, CHENG Xiaosheng, CUI Haihua, ZHANG Yihua

(Nanjing University of Aeronautics & Astronautics, Jiangsu Nanjing, 210016, China)

It proposes a SIFT matching algorithm presence of mismatch based on triangle similarity matching feature points filtering algorithms. This algorithm uses the feature points in the Euclidean distance to determine the similarity of the SIFT algorithm for matching feature points structure triangle, discriminates the feature points further filtration to realize the triangle similarity matching. The experimental results show that the algorithm is similar to the triangle, and greatly improves the matching accuracy.

Image Mosaic; SIFT Algorithm; Triangle Similarity; Match Point Filter

10.3969/j.issn.2095-509X.2014.09.010

2014-08-09

國(guó)家863計(jì)劃資助項(xiàng)目(SS2013AA040802)；江蘇省博士后科學(xué)基金資助項(xiàng)目(1301104C)；江蘇省數(shù)字化制造技術(shù)重點(diǎn)實(shí)驗(yàn)室開放基金資助項(xiàng)目(HGDML-1103)；南京市產(chǎn)學(xué)研項(xiàng)目(201306007)

蔣中杰(1989—)，男，江蘇江陰人，南京航空航天大學(xué)碩士研究生，主要從事為圖像處理、圖像拼接等方面的研究。

TP751

A

2095-509X(2014)09-0040-04