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

孫坤

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

【關鍵詞】圖像匹配 RANSAC算法 視差梯度約束

1 引言

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

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

2 圖像配準技術

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

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

3 RANSAC算法簡介

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

3.1 RANSAC算法思想

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

3.2 RANSAC算法的具體步驟

（1）計算抽樣數量M

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

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

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

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

（4）根據每組抽樣獲得的精確匹配點對的數量和誤差方差的大小，選擇最優的抽樣及抽樣數據所對應的模型參數；

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

3.3 RANSAC算法評價

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

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

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

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

其中，（n1，m）和（n1，n）是對應角點的圖像坐標向量，||p||表示向量p的模。

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

（1）計算抽樣數量M

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

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

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

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

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

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

（6）根據每組抽樣獲得的精確匹配點對的數量和誤差方差的大小，選擇最優的抽樣及抽樣數據所對應的模型參數；

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

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

5 結束語

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

參考文獻

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

[2]楊占龍.基于特征點的圖像配準與拼接技術研究[D].西安電子科技大學，2008.

[3]靳峰.基于特征的圖像配準關鍵技術研究[D].西安電子科技大學，2015.

[4]廖斌.基于特征點的圖像配準技術研究[D].國防科學技術大學，2008.

作者單位

西北工業大學 陜西省西安市 710000