邱亞輝，李長青，崔有幀

（北京工業(yè)職業(yè)技術(shù)學(xué)院，北京100042）

RANSAC算法在剔除圖像配準(zhǔn)中誤匹配點的應(yīng)用

邱亞輝，李長青，崔有幀

（北京工業(yè)職業(yè)技術(shù)學(xué)院，北京100042）

在遙感圖像中存在很多相似地物、地貌，SIFT算法本身只利用了特征點的局部鄰域梯度信息，通過SIFT算法提取到的特征點存在很多誤匹配點，通過RANSAC算法剔除誤匹配點，可以提高配準(zhǔn)的精度。

SIFT算法；誤匹配點；RANSAC算法

1 引言

SIFT特征對所提取出來的特征點進行特征點粗匹配，由于SIFT算法本身只利用了特征點的局部鄰域的梯度信息，而且影像中的地形、地貌有時候會出現(xiàn)相似的地方，經(jīng)過SIFT算法提取到的特征點并經(jīng)過粗匹配后，在基準(zhǔn)影像中的某個特征點在待配準(zhǔn)影像中會提到多個相似的特征點，即一對多的現(xiàn)象（如圖1所示），同時基準(zhǔn)影像中的多個特征點也會對應(yīng)待配準(zhǔn)影像中一個特征點，即多對一的現(xiàn)象（如圖2所示）。

圖1 匹配點一對多

圖2 匹配點多對一

圖3 刪除一對多和多對一后的匹配結(jié)果

通過配準(zhǔn)結(jié)果可以看出，用SIFT算法提取特征點后，即使剔除一對多和多對一的誤匹配點以后，依然存在太多的錯誤，為了提高配準(zhǔn)的精度，必須應(yīng)用合適算法剔除全部錯誤的匹配點。

2 RANSAC算法

經(jīng)過SIFT特征粗匹配后，我們得到了大量的匹配點對，剔除了一對多和多對一的點后其中仍舊存在部分錯誤匹配點，經(jīng)過斜率約束后可以將明顯錯誤的匹配點剔除，利用極線約束可以刪除小部分錯誤不太明顯的匹配點對。至此，匹配點對已經(jīng)相對準(zhǔn)確，但卻仍舊存在部分外點，需進一步通過RANSAC（隨機取樣一致性）算法進行剔除外點，并且可以通過該算法對某個模型進行穩(wěn)定估計。RANSAC算法最早由Fischler和Bolles于1981年提出，它可以從一組包含“外點”的觀測數(shù)據(jù)集中，通過迭代方式估計數(shù)學(xué)模型的參數(shù)，并通過設(shè)定相關(guān)閾值，可以穩(wěn)定地將整個樣本當(dāng)中的“外點”或者“噪聲”剔除，RANSAC算法是魯棒性很高的算法，該算法先隨機的從整個數(shù)據(jù)集當(dāng)中選取最小抽樣集，并通過這些抽樣集計算出相關(guān)模型參數(shù)的初始值，再通過計算出來的模型來尋找數(shù)據(jù)集中的其他內(nèi)點，并將外點剔除，以此來最大程度的消除外點對整體估計的影響。

對于每一對相鄰的影像，已知存在M對同名點，由于經(jīng)過前面一系列的約束后，M對同名點中只存在極少量的錯誤匹配點，對于本文所采用的RANSAC算法，我們設(shè)定以下參數(shù)：最大內(nèi)點數(shù)max_inliner=0，反投影誤差閾值threshold=4，min_std=10e5，最大循環(huán)次數(shù)max_circle=1000，p= 0.99，當(dāng)前內(nèi)點距離標(biāo)準(zhǔn)差cur_std，numof_inliner為當(dāng)前所對應(yīng)的內(nèi)點數(shù)，根據(jù)當(dāng)前一H?所計算出的各對同名點的反投影距離為：

具體的RANSAC算法流程圖如圖4所示：

圖4 RANSAC算法流程圖

圖4表示了本文所采用的RANSAC算法的基本流程。首先設(shè)置相關(guān)初始化的參數(shù)，然后從樣本中選取四對不共線的匹配點對組成一個隨機樣本，并采用歸一化線性變換計算局部變換矩陣H的8個未知參數(shù)，再通過計算出的局部H來計算其余特征點對的反投影誤差距threshold的內(nèi)點個數(shù)numof_inliner，若numof_inliner>=max_inlier，更新當(dāng)前H，計算所有內(nèi)點，最后根據(jù)所有內(nèi)點數(shù)重新計算H。RANSAC算法本身可以從含有較多錯誤點對的點集中穩(wěn)定的估計出相應(yīng)模型的參數(shù)，但前提是將循環(huán)次數(shù)設(shè)置成無窮大，而在本文中，我們將最大循環(huán)次數(shù)max_circle直接設(shè)置成1000，這是因為我們的樣本集已經(jīng)是經(jīng)過了一系列的剔除錯誤點步驟后而得來的，樣本集內(nèi)部的錯誤點已經(jīng)很少，這就可以使得其在循環(huán)了1000次后必定能夠估算出很穩(wěn)定的模型參數(shù)，并剔除相應(yīng)的外點。這也是將RANSAC算法放在前面的一系列步驟之后的原因。經(jīng)RANSAC算法剔除外點后，其結(jié)果如圖5所示，圖中白線即為剔除的外點。

圖5 RANSAC剔除外點結(jié)果

3 總結(jié)

本文主要是研究了剔除特征點誤匹配，首先是初步的介紹了誤匹配點產(chǎn)生的原因，為了提高配準(zhǔn)的精度，我們應(yīng)用了RANSAC算子，并且介紹了RANSAC算子的基本思想以及如何求解二維圖像的變換矩陣，最后分別運用上述三種剔除外點的方法刪除了配準(zhǔn)中的誤匹配點，最后給出匹配結(jié)果，從而達到更加精確的配準(zhǔn)精度。

［1］H.P.Moravec.Visual Mapping by a Robot Rover［C］. International Joint Conference on Artificial Intelligence,1979: 598-600.

［2］C.Harris,M.Stephens.A combined corner and edge detector［C］.Fourth Alvey Vision Conference,1988:147-151.

［3］S.M.Smith,M.Brady.SUSAN-a new approach to low level image processing［J］.Interational Journal of Computer Vision,Vol.23,No.1,1997:45-78.

［4］David G.Lowe.Object recognition from local scale-invariant features［C］.In ICCV,1999:1150-1157.

［5］David G.Lowe.Distinctive Image Features from Scale-Invariant Key points［J］.International Journal of Computer Vision,2004,60(2):91-110.

［6］林婧，郝永平，華宇寧.SIFT特征在圖像配準(zhǔn)過程中的應(yīng)用研究［J］.沈陽理工大學(xué)學(xué)報，2009，28（5）：26-29.

［7］陸菲菲，奚玲，岳春生.利用幾何精校正進行多尺度數(shù)字柵格地圖配準(zhǔn)［J］.計算機應(yīng)用，2006，26（12）：115-117.

［8］李柏林.基于特征點圖像拼接的配準(zhǔn)算法研究［D］.天津：天津大學(xué)碩士論文，2008.

P237;TP751

B

10.3969/j.issn.1001-0270.2014.04.20

2014-02-25