基于視差梯度約束的RANSAC算法

孫坤

圖像拼接技術(shù)中的圖像配準(zhǔn)階段存在計算量過大的缺陷，這是由于計算變換模型矩陣時，傳統(tǒng)的RANSAC算法計算了全部匹配特征點（包括偽匹配點對）對應(yīng)的模型參數(shù)，本文在RANSAC算法前設(shè)計了基于視差梯度約束的預(yù)檢驗過程，篩選掉大量偽匹配特征點，大大提高了圖像配準(zhǔn)效率。

【關(guān)鍵詞】圖像匹配 RANSAC算法 視差梯度約束

1 引言

我們知道，圖像拼接的過程一般分為三個步驟：圖像預(yù)處理（特征提取）、圖像配準(zhǔn)以及圖像融合。其中，圖像配準(zhǔn)是圖像拼接過程中的核心內(nèi)容。通過相似性度量準(zhǔn)則找到匹配的特征點對，然后通過匹配的特征點對求解圖像之間的變換矩陣，使圖像的內(nèi)容在拓撲和幾何上對齊，最終完成圖像的拼接。

如今，在圖像配準(zhǔn)領(lǐng)域常用的的方法有：像素差平方和法、互相關(guān)法和RANSAC算法。本文主要對RANSAC法進行相應(yīng)的研究和改進。在使用RANSAC法對粗匹配的特征角點進行提純時，由于偽匹配特征點的存在，算法在變換模型計算和檢驗上花費了大量的時間。本文通過在計算變換模型前增加基于視差梯度約束的預(yù)檢測過程，篩選掉偽匹配特征點，再進行模型計算和檢驗，大大提高了圖像配準(zhǔn)效率。

2 圖像配準(zhǔn)技術(shù)

欲將兩幅圖像進行無縫拼接，需要求出兩幅圖像之間的幾何對應(yīng)關(guān)系，包括平移、旋轉(zhuǎn)、縮放等。兩幅圖像A和A1的一般變換模型可表示為：

求解變換模型，就是求解變換矩陣的參數(shù)λ0……λ7。在求解過程中需要一定數(shù)量的精確匹配點對，這與圖像拼接的最終結(jié)果密切相關(guān)。圖像的拼接效果取決于變換矩陣參數(shù)估計的精確度，而參數(shù)估計的關(guān)鍵在于獲取精確匹配的特征點對。在特征點匹配過程中獲得的“匹配特征點集合”往往存在一定數(shù)量的偽匹配特征點，即在第一幅圖像中的某個特征點會對應(yīng)于第二個圖像中的多個特征點。為了獲得更精確的匹配特征點對，人們通常用RANSAC算法對匹配特征點進行提純。

3 RANSAC算法簡介

RANSAC算法（隨機抽樣一致性算法）是一種非常有效的估計算法，如果精確的數(shù)據(jù)占大多數(shù)，偽匹配點對只是少量時，可以用最小二乘法來求解模型的參數(shù)和誤差；如果偽匹配點對很多，如偽匹配點對的數(shù)目超過了50%，最小二乘法就不適用了，而RANSAC算法卻可以求解。

3.1 RANSAC算法思想

在模型參數(shù)的求解過程中，偽匹配點對的存在是造成結(jié)果出現(xiàn)偏差的重要原因，為了提高結(jié)果的準(zhǔn)確度，需要從原始數(shù)據(jù)中提取出一組不包含偽匹配點對的數(shù)據(jù)樣本進行模型參數(shù)求解，而這需要遍歷數(shù)據(jù)的不同組合，計算量太大。RANSAC算法認為在一定置信概率下，只需要搜索M組抽樣（M足夠大），就可以認為這組抽樣中至少有一組抽樣不包含偽匹配點對，利用找出的這組抽樣數(shù)據(jù)來求解出模型的參數(shù)，然后將參數(shù)代入模型作為假設(shè)模型，對其它原始數(shù)據(jù)進行篩選，篩選掉偏差大的特征點，用保留的精確匹配特征點再次求解模型，得到精確的參數(shù)。

3.2 RANSAC算法的具體步驟

（1）計算抽樣數(shù)量M

P=1-（1-（1-ε）m）M

P：置信概率；ε：數(shù)據(jù)錯誤率；m：求解模型參數(shù)需要的最小數(shù)據(jù)量

（2）從原始數(shù)據(jù)中隨機抽取m個數(shù)據(jù)組成一個抽樣，將抽樣點數(shù)據(jù)代入方程，求解模型參數(shù)；

（3）將上一步求出的參數(shù)代入模型，用這個假設(shè)模型來篩選原始數(shù)據(jù)，去除偏差較大的數(shù)據(jù)，獲得精確匹配點對；重復(fù)（2）、（3）步，將M組抽樣數(shù)據(jù)都做相同的處理；

（4）根據(jù)每組抽樣獲得的精確匹配點對的數(shù)量和誤差方差的大小，選擇最優(yōu)的抽樣及抽樣數(shù)據(jù)所對應(yīng)的模型參數(shù)；

（5）用這個最優(yōu)模型篩選掉原始數(shù)據(jù)中偏差大的點，用剩下的精確匹配點計算最終的模型參數(shù)。

3.3 RANSAC算法評價

當(dāng)M很大時，RANSAC算法的計算量也會很大，其中包含了大量計算偽匹配點對所對應(yīng)的參數(shù)，做了許多無用功。下面我們將從減少計算錯誤的參數(shù)方面對RANSAC算法進行改進。

4 基于視差梯度約束的RANSAC算法

若要使用RANSAC算法來提純原數(shù)據(jù)中粗匹配的特征角點，由于可能會存在一定數(shù)量的偽匹配點，所以在實際的匹配過程中會在計算錯誤的模型參數(shù)和檢驗上浪費大量時間。針對這一不足，我們在計算變換模型前額外增加了一個預(yù)檢驗過程，先檢驗所選的抽樣中是否有偽匹配點對的存在。若沒有偽匹配點對，再開始進行模型計算和檢驗，否則，重新抽樣。

根據(jù)視差梯度的定義，若當(dāng)前圖像中兩個相鄰角點m、n分別匹配于另一幅圖像中的角點m1和n1，它們計算得出的視差梯度應(yīng)該小于2。如果經(jīng)計算，它們視差梯度大于2，則我們可以認為這兩對角點并不十分匹配。視差梯度的公式為：

其中，（n1，m）和（n1，n）是對應(yīng)角點的圖像坐標(biāo)向量，||p||表示向量p的模。

根據(jù)以上分析，改進的RANSAC算法步驟如下：

（1）計算抽樣數(shù)量M

P=1-（1-（1-ε）m）M

P：置信概率；ε：數(shù)據(jù)錯誤率；m：求解模型參數(shù)需要的最小數(shù)據(jù)量

（2）從原始數(shù)據(jù)中隨機抽取m個數(shù)據(jù)組成一個抽樣；

（3）在第（2）步選擇的隨機抽樣中，任意選擇兩對匹配點，計算它們的視差梯度，若其視差梯度大于2，則返回步驟（2）；否則，轉(zhuǎn)入步驟（4）；

（4）將抽樣點數(shù)據(jù)代入方程，求解模型參數(shù)；

（5）將上一步求出的參數(shù)代入模型，用這個假設(shè)模型來篩選原始數(shù)據(jù)，去除偏差較大的數(shù)據(jù)，獲得精確匹配點對；重復(fù)（2）、（3）、（4）步，將M組抽樣數(shù)據(jù)都做相同的處理；

（6）根據(jù)每組抽樣獲得的精確匹配點對的數(shù)量和誤差方差的大小，選擇最優(yōu)的抽樣及抽樣數(shù)據(jù)所對應(yīng)的模型參數(shù)；

（7）用這個最優(yōu)模型篩選掉原始數(shù)據(jù)中偏差大的點，用剩下的精確匹配點計算最終的模型參數(shù)。

在具體實驗過程中，我們發(fā)現(xiàn)，采用基于視差梯度約束的RANSAC算法能夠有效地提高算法效率，極大地縮短了模型參數(shù)檢驗需要的時間。

5 結(jié)束語

本文通過在應(yīng)用變換模型前增加基于視差梯度的預(yù)處理過程，減少了偽匹配特征點的數(shù)量，降低了變換模型計算與檢驗的時間，進而提高了RANSAC算法的效率，從而提高了圖像配準(zhǔn)的效率，進一步為后期的圖像融合的準(zhǔn)確性做鋪墊。

參考文獻

[1]杜志斌.基于角點檢測與匹配的圖像拼接設(shè)計與實現(xiàn)[D].東北大學(xué)（學(xué)位論文），2011.

[2]楊占龍.基于特征點的圖像配準(zhǔn)與拼接技術(shù)研究[D].西安電子科技大學(xué)，2008.

[3]靳峰.基于特征的圖像配準(zhǔn)關(guān)鍵技術(shù)研究[D].西安電子科技大學(xué)，2015.

[4]廖斌.基于特征點的圖像配準(zhǔn)技術(shù)研究[D].國防科學(xué)技術(shù)大學(xué)，2008.

作者單位

西北工業(yè)大學(xué) 陜西省西安市 710000