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

孫坤

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

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

1 引言

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

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

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

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

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

3 RANSAC算法簡(jiǎn)介

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

3.1 RANSAC算法思想

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

3.2 RANSAC算法的具體步驟

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

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

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

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

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

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

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

3.3 RANSAC算法評(píng)價(jià)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

參考文獻(xiàn)

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

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

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

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

作者單位

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