邱亞輝，李長(zhǎng)青，崔有幀

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

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

邱亞輝，李長(zhǎng)青，崔有幀

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

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

SIFT算法；誤匹配點(diǎn)；RANSAC算法

1 引言

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

圖1 匹配點(diǎn)一對(duì)多

圖2 匹配點(diǎn)多對(duì)一

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

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

2 RANSAC算法

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

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

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

圖4 RANSAC算法流程圖

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

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

3 總結(jié)

本文主要是研究了剔除特征點(diǎn)誤匹配，首先是初步的介紹了誤匹配點(diǎn)產(chǎn)生的原因，為了提高配準(zhǔn)的精度，我們應(yīng)用了RANSAC算子，并且介紹了RANSAC算子的基本思想以及如何求解二維圖像的變換矩陣，最后分別運(yùn)用上述三種剔除外點(diǎn)的方法刪除了配準(zhǔn)中的誤匹配點(diǎn)，最后給出匹配結(jié)果，從而達(dá)到更加精確的配準(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)過(guò)程中的應(yīng)用研究［J］.沈陽(yáng)理工大學(xué)學(xué)報(bào)，2009，28（5）：26-29.

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

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

P237;TP751

B

10.3969/j.issn.1001-0270.2014.04.20

2014-02-25