譚仁龍,萬幼川

（1.武漢大學(xué) 遙感信息工程學(xué)院，湖北 武漢 430079）

基于主方向的SIFT誤匹配點(diǎn)剔除方法

譚仁龍1,萬幼川1

（1.武漢大學(xué) 遙感信息工程學(xué)院，湖北 武漢 430079）

針對RANSAC方法在剔除SIFT誤匹配點(diǎn)方面的不足，提出了一種基于主方向的SIFT誤匹配點(diǎn)剔除方法。結(jié)果表明，該算法與RANSAC相比，耗時(shí)較少，剔除效果更好，保留的正確匹配點(diǎn)數(shù)更多，且當(dāng)誤匹配點(diǎn)數(shù)量多于正確匹配點(diǎn)時(shí)也能得到很好的剔除效果。

影像匹配；SIFT算法；主方向；最小二乘；誤匹配剔除

影像匹配即通過一定的匹配算法在2幅或多幅影像之間識別同名點(diǎn)的過程，是計(jì)算機(jī)視覺及數(shù)字?jǐn)z影測量的核心問題[1]。大多數(shù)情況下，基于特征的SIFT[2]匹配算法能取得較好的結(jié)果，但當(dāng)圖像中存在大量相似結(jié)構(gòu)時(shí)，匹配結(jié)果中會出現(xiàn)大量的誤匹配。目前國內(nèi)學(xué)者對于誤匹配點(diǎn)的剔除提出了許多算法[3-6]，較常用的方法是用隨機(jī)抽樣一致性（RANSAC）隨機(jī)選擇樣本點(diǎn)反復(fù)迭代計(jì)算來剔除誤匹配點(diǎn)，但此方法在剔除誤匹配點(diǎn)的同時(shí)也剔除了大量正確匹配點(diǎn)，且在初始匹配的內(nèi)點(diǎn)少于50%時(shí)這種方法就會失效[2]。鑒于此，本文利用特征點(diǎn)間的主方向夾角近似相等作為初始約束條件，迭代使用最小二乘增加正確匹配點(diǎn)，最后實(shí)現(xiàn)誤匹配點(diǎn)的剔除，以此提高SIFT匹配算法的可靠性和準(zhǔn)確性。

1 SIFT影像匹配

SIFT算法主要包括尺度空間的極值探測、關(guān)鍵點(diǎn)的精確定位、確定關(guān)鍵點(diǎn)的主方向和生成關(guān)鍵點(diǎn)的描述子及匹配等內(nèi)容。

在建立多尺度空間時(shí)，高斯卷積核已被證明是唯一的線性核[7]。為了有效提取穩(wěn)定的關(guān)鍵點(diǎn)，Lowe提出了利用高斯差分函數(shù)對原始影像進(jìn)行卷積，在高斯差分金字塔影像中將每個(gè)采樣點(diǎn)與它所在的同一層比例尺空間的周圍8個(gè)相鄰點(diǎn)和相鄰上、下比例尺空間中相應(yīng)位置上的9×2個(gè)相鄰點(diǎn)進(jìn)行比較，如果該點(diǎn)是所有點(diǎn)中的極值，則作為一個(gè)候選點(diǎn)。通過擬合三維二次函數(shù)以精確確定關(guān)鍵點(diǎn)的位置，同時(shí)需要剔除低對比度的特征點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)，以保證特征點(diǎn)的穩(wěn)健性。

在以關(guān)鍵點(diǎn)為中心的16像素×16像素鄰域窗口內(nèi)，利用高斯函數(shù)對各像素的梯度大小進(jìn)行加權(quán)，用直方圖統(tǒng)計(jì)窗口內(nèi)的梯度方向，將直方圖的主峰值方向設(shè)為關(guān)鍵點(diǎn)的主方向；然后以特征點(diǎn)為中心，在鄰域內(nèi)計(jì)算生成128維特征描述符；提取SIFT描述子之后，采用歐氏距離來計(jì)算描述子之間的相似度，對于參考圖像中的某個(gè)關(guān)鍵點(diǎn)，找到其與待匹配圖像中歐氏距離最近的前2個(gè)點(diǎn)，若最近距離除以次近距離小于某個(gè)設(shè)定的閾值，則認(rèn)為這是一對正確匹配點(diǎn)。

2 基于主方向的誤匹配點(diǎn)剔除

目前，影像誤匹配點(diǎn)剔除算法主要是利用特征點(diǎn)的鄰域灰度信息，而很少考慮特征點(diǎn)的主方向性質(zhì)。如果任意2對特征點(diǎn)是正確匹配點(diǎn)，那么不僅對應(yīng)正確匹配點(diǎn)對的鄰域灰度信息類似，2個(gè)特征點(diǎn)的主方向的夾角也應(yīng)是近似相等的。而錯誤匹配點(diǎn)對間雖然描述子的歐氏距離相隔很近，但是主方向的夾角一般偏差較大，因此，正確匹配點(diǎn)對間必須滿足約束條件：

式中，θ1和θ2分別為參考影像和待匹配影像上兩對應(yīng)匹配點(diǎn)間主方向的夾角；λθ為單角度差閾值，這個(gè)性質(zhì)對影像的平移、旋轉(zhuǎn)、縮放甚至仿射變換都具有穩(wěn)定性。影像之間的仿射變換滿足公式：

為求解6個(gè)位置參數(shù)，方程變形為：

求解此方程至少需要3對匹配點(diǎn)，因此遍歷所有匹配點(diǎn)每次挑選3對匹配點(diǎn)，計(jì)算2幅影像對應(yīng)匹配點(diǎn)兩兩主方向夾角差值的絕對值和f（θ）,當(dāng)滿足條件：式中，θ1、θ2、θ3為參考影像3個(gè)主方向夾角；θ1′、θ2′、θ3′為待匹配影像對應(yīng)3個(gè)主方向夾角；σθ為三角差值和閾值。

為減少運(yùn)算時(shí)間，對3個(gè)夾角差分別設(shè)置閾值，任意一個(gè)超過閾值則停止計(jì)算，尋找下一個(gè)匹配點(diǎn)。實(shí)際計(jì)算中由于閾值設(shè)定的差異，可能找不到不止3個(gè)最初匹配點(diǎn)，將這些初始點(diǎn)代入式（3）用最小二乘解算6個(gè)參數(shù)的初始值，再遍歷所有匹配點(diǎn)，根據(jù)仿射變換方程計(jì)算出變換后每點(diǎn)坐標(biāo)，與實(shí)際對應(yīng)匹配點(diǎn)計(jì)算坐標(biāo)差絕對值|Δ x|和|Δ y|，當(dāng)兩者同時(shí)小于設(shè)定閾值時(shí)認(rèn)為其為正確匹配點(diǎn)，加入到正確匹配點(diǎn)集中，一次遍歷完成后重新利用最小二乘計(jì)算6個(gè)參數(shù)，不斷重復(fù)上述迭代計(jì)算過程，直到?jīng)]有新的正確匹配點(diǎn)加入點(diǎn)集時(shí)停止計(jì)算。

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

為了驗(yàn)證方法的有效性，將本方法與RANSAC方法在不同數(shù)據(jù)下進(jìn)行對比實(shí)驗(yàn)與分析。

實(shí)驗(yàn)1：實(shí)驗(yàn)數(shù)據(jù)包括近景影像和SPOT衛(wèi)星影像，近景影像存在著旋轉(zhuǎn)和縮放變化，衛(wèi)星影像則存在平移變化。影像大小為：425像素×340像素、400像素× 300像素，實(shí)驗(yàn)中最近距離和次近距離的比例閾值設(shè)為0．4，單角差閾值設(shè)為0．05，三角差值和閾值設(shè)為0．003。實(shí)驗(yàn)結(jié)果如圖1、圖2所示。

從圖1、圖2可以看出，2種方法在剔除誤匹配點(diǎn)的同時(shí)都剔除了一些正確匹配點(diǎn)，但本文方法保留的正確匹配點(diǎn)更多。圖1a中SIFT匹配后船體右上角附近有一些正確點(diǎn)，但是經(jīng)過RANSAC方法處理后均被剔除，本文方法處理后則大部分得到了保留，同時(shí)在船體其他部分的匹配點(diǎn)也比RANSAC方法留下的點(diǎn)要密集，圖1d中RANSAC處理后左影像一匹配點(diǎn)在門內(nèi)，而右影像上相對應(yīng)的匹配點(diǎn)卻在門外，明顯是一對誤匹配點(diǎn)卻沒有被剔除，而本文方法在相同位置附近則找到了2對正確匹配點(diǎn)，如圖1e所示。對比圖2a和b衛(wèi)星影像可以發(fā)現(xiàn)，RANSAC處理后左片右側(cè)部分損失了大量的正確匹配點(diǎn)，而左側(cè)部分殘留的點(diǎn)較原始SIFT匹配結(jié)果也稀疏了很多。經(jīng)本文方法處理后，左側(cè)殘留點(diǎn)更加密集，右側(cè)大多數(shù)點(diǎn)也得到了很好的保存，同時(shí)可在圖2d中看到RANSAC處理后在道路上的匹配點(diǎn)位置存在明顯偏差，本文方法則在相同位置附近找到了3對正確匹配點(diǎn)。2種方法處理的結(jié)果如表1所示，可以看到本文方法能剔除更多的誤匹配點(diǎn)，同時(shí)能留下更多的正確匹配點(diǎn)，使得誤匹配率大大降低，且對比實(shí)驗(yàn)1和實(shí)驗(yàn)2可知，處理速度相比RANSAC也有一定的優(yōu)勢。

圖1 近景影像處理結(jié)果圖

圖2 衛(wèi)星影像處理結(jié)果圖

表1 2種方法剔除誤匹配點(diǎn)結(jié)果比較表

實(shí)驗(yàn)2：所用的航空影像紋理比較均勻，且有較多的相似結(jié)構(gòu)，影像間只存在上下平移的變化，影像大小為400像素×300像素，實(shí)驗(yàn)中最近距離和次近距離的比例閾值設(shè)為0．8。由于特征點(diǎn)周圍影像紋理較均勻，一定程度上對主方向的生成精度造成了影響，考慮到可能存在的角度偏差，將角度差閾值設(shè)置較為寬松，單角差閾值設(shè)為0．1，三角差值和閾值設(shè)為0．15。用SIFT原始匹配結(jié)果及用RANSAC和本文方法分別處理的結(jié)果如圖3所示，實(shí)驗(yàn)對比數(shù)據(jù)如表2所示。

圖3 航空影像處理結(jié)果

表2 實(shí)驗(yàn)2處理結(jié)果對比數(shù)據(jù)表

從SIFT匹配結(jié)果可知，影像中存在大量的誤匹配點(diǎn)，數(shù)量超過了正確匹配點(diǎn)。由于RANSAC方法是按照不斷隨機(jī)選取樣本點(diǎn)計(jì)算模型參數(shù)，用模型來確認(rèn)內(nèi)點(diǎn)，以得到內(nèi)點(diǎn)數(shù)最多的模型作為正確模型，然后用內(nèi)點(diǎn)重新修改模型的方法來剔除誤匹配的，當(dāng)正確匹配點(diǎn)數(shù)量少于誤匹配點(diǎn)時(shí)，RANSAC隨機(jī)選取的樣本中正確匹配點(diǎn)的比例會變得很低甚至沒有正確匹配點(diǎn)，這樣計(jì)算出的模型參數(shù)往往不準(zhǔn)確，難以用得到的模型區(qū)分正確點(diǎn)和錯誤點(diǎn)，因此該方法不再有效。由圖3 b、圖3 d可知，RANSAC處理后得到的4對匹配點(diǎn)只有1號點(diǎn)是正確點(diǎn)，其余3對點(diǎn)全是錯誤匹配點(diǎn)，而本文方法卻可很好利用主方向夾角差幾乎相等這一條件穩(wěn)定地找到最初的幾對正確匹配點(diǎn)，然后計(jì)算仿射模型參數(shù)，通過迭代使用最小二乘不斷添加正確匹配點(diǎn)，最后實(shí)現(xiàn)誤匹配點(diǎn)的剔除。從圖3 c、圖3 e中可知，本文方法找到了13對正確匹配中的12對，完全剔除了誤匹配點(diǎn)，體現(xiàn)出了優(yōu)勢之處。

4 結(jié) 語

通過對基于主方向的誤匹配點(diǎn)剔除方法和傳統(tǒng)RANSAC方法在不同數(shù)據(jù)下進(jìn)行實(shí)驗(yàn)，得出如下主要結(jié)論：

1）影像中正確匹配點(diǎn)多于誤匹配點(diǎn)時(shí)，2種方法都能得到較好的剔除效果，相比于RANSAC方法，本文算法處理過后殘留的誤匹配點(diǎn)更少，保留的正確匹配點(diǎn)更多，耗時(shí)更少，因此效果更好。

2）影像中誤匹配點(diǎn)多于正確匹配點(diǎn)時(shí)，RANSAC方法不再適用，而本文算法依然能夠得到較好的剔除效果，彌補(bǔ)了RANSAC方法的不足。

3）本文算法中所涉及到的閾值參數(shù)均為人工設(shè)定，不同的影像需要不同的參數(shù)才能得到較好的剔除效果，如何能找到一種根據(jù)不同影像自適應(yīng)計(jì)算最佳閾值的算法，是進(jìn)一步的研究方向。

[1] 張劍清，潘勵，王樹根．?dāng)z影測量學(xué)[M]．武漢：武漢大學(xué)出版社，2002

[2] Lowe D G． Distinctive Image Features from Scale-Invariant Key Points[J]．International Journal of Computer Vision, 2004,60(2):91-110

[3] 張潔玉，白小晶，徐麗燕，等．基于空間描述符的SIFT誤匹配校正方法[J]．中國圖像圖形學(xué)報(bào),2009,14(7):1 369-1 377

[4] 陳敏，邵振峰，慎于藍(lán)．基于基準(zhǔn)點(diǎn)和基準(zhǔn)方向的SIFT誤匹配校正方法[J]．測繪通報(bào)，2012(3):16-18

[5] 張東興，祝明波，鄒建武，等．基于相似三角形的SIFT錯誤匹配點(diǎn)剔除算法研究[J]．計(jì)算機(jī)工程與科學(xué)，2012，34(4):66-70

[6] 李參海，王光輝．多源遙感影像誤匹配點(diǎn)剔除的粗糙模糊C-均值方法[J]．測繪與空間地理信息，2008，31(5)：47-51

[7] Lindeberg T． Scale-Space Theory: A Basic Tool Analyzing Structures at Different Scales[J]．Journal of Applied Statistics,1994,21(2):224-270

P231.5

B

1672-4623（2014）01-0101-03

10.11709/j.issn.1672-4623.2014.01.035

譚仁龍，碩士，主要從事數(shù)字?jǐn)z影測量與遙感方面的研究。

2013-05-27。

項(xiàng)目來源：國家科技支撐計(jì)劃資助項(xiàng)目(2012BAH34B02、2012BAJ15B04、2011BAH12B03)。