RANSAC算法求解單應(yīng)矩陣的具體研究

王博楊

摘要： 本文主要研究RANSAC算法在單應(yīng)矩陣求解中的應(yīng)用。具體方法是在單應(yīng)矩陣的求解過(guò)程中，利用RANSAC算法原理，通過(guò)不斷地取點(diǎn)、閾值判斷等迭代過(guò)程，逐步更新內(nèi)點(diǎn)集，優(yōu)化單應(yīng)矩陣的計(jì)算結(jié)果，得到更精確解。

Abstract： In this paper， we mainly study the application of RANSAC algorithm in solving single homogeneous matrix. By using the RANSAC algorithm， the interior point set is updated step by step through the iterative process of taking points and thresholds， and the result is optimized to obtain more accurate solutions.

關(guān)鍵詞： RANSAC算法；迭代；單應(yīng)矩陣

Key words： RANSAC algorithm；iteration；homography matrix

中圖分類號(hào)：TP317.4 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2017）02-0216-02

0 引言

圖像拼接技術(shù)能夠?qū)⒍嗄恳曨l圖像拼接成同一平面下的合成圖像，通過(guò)該方法的應(yīng)用可以將無(wú)畸變?nèi)氨O(jiān)控變?yōu)楝F(xiàn)實(shí)，在軍事、交通、科研等領(lǐng)域具有深遠(yuǎn)意義。圖像拼接技術(shù)的關(guān)鍵一步就是多目視頻圖像間的單應(yīng)矩陣的求解。雖然通過(guò)4對(duì)不共線坐標(biāo)就可以求出單應(yīng)矩陣，但是因?yàn)樵肼暤拇嬖冢趯?shí)際取點(diǎn)過(guò)程中，一定會(huì)存在誤差，導(dǎo)致單應(yīng)矩陣計(jì)算不夠準(zhǔn)確，會(huì)給后續(xù)的圖像拼接造成嚴(yán)重影響。

RANSAC算法（Random Sample Consensus）是一種獲得非確定樣本數(shù)據(jù)的方法，于1981年由Fischler和Bolles最先提出。對(duì)于RANSAC算法有一個(gè)基本的假設(shè)：樣本中包含正確數(shù)據(jù)（inliers，符合模型的數(shù)據(jù)）和異常數(shù)據(jù)（Outliers，不符合模型的數(shù)據(jù)），通過(guò)不斷地更新內(nèi)點(diǎn)集，找出最優(yōu)的樣本模型。

1 基于RANSAC算法的單應(yīng)矩陣求解流程

為求得單應(yīng)矩陣的精確值，我們可以通過(guò)以下步驟進(jìn)行：

第一步，先從數(shù)據(jù)集S中隨機(jī)選擇4對(duì)樣本。

第二步，根據(jù)上述單應(yīng)矩陣的求解方法，我們可以求得單應(yīng)矩陣H的初始解，并記為模型M。

第三步，通過(guò)模型M計(jì)算i點(diǎn)的投影誤差，并通過(guò)閾值比較，若d?t，則將i點(diǎn)加入內(nèi)點(diǎn)集I。

第四步，若通過(guò)模型M確定的內(nèi)點(diǎn)集所包含點(diǎn)的數(shù)量大于最優(yōu)內(nèi)點(diǎn)集，則更新最優(yōu)內(nèi)點(diǎn)集，同時(shí)迭代次數(shù)，否則從最優(yōu)內(nèi)點(diǎn)集中選擇4對(duì)樣本重復(fù)第二步。

第五步，若迭代次數(shù)大于k則結(jié)束，最后求得的單應(yīng)矩陣H是最優(yōu)解，否則重復(fù)第二步。

算法的具體流程如圖1。

2 計(jì)算參數(shù)的確定

2.1 迭代次數(shù)k

根據(jù)公式k=確定迭代次數(shù)，其中w=內(nèi)點(diǎn)數(shù)/數(shù)據(jù)總數(shù)，p為置信度，我們?nèi)≈禐?.99。

2.2 閾值t

閾值的計(jì)算可以通過(guò)公式t2=F（α）σ2求得，顯而易見當(dāng)d?t2時(shí)點(diǎn)（x，y）為內(nèi)點(diǎn)，當(dāng)d>t2時(shí)點(diǎn)（x，y）為外點(diǎn)。A是特征點(diǎn)為內(nèi)點(diǎn)的先驗(yàn)概率，為了提高精度，我們?nèi)≈禐?.9。因?yàn)槭?個(gè)自由度，所以n取值為2，通過(guò)查表，我們可得F（0.9）=4.605，σ可以通過(guò)樣本特征點(diǎn)的提取，采用樣本標(biāo)準(zhǔn)差公式σ=求出，則閾值t就可以通過(guò)計(jì)算獲得。

3 算法的優(yōu)化

RANSAC算法因?yàn)樾枰M(jìn)行的大量的迭代計(jì)算和數(shù)據(jù)處理，因此在某些復(fù)雜場(chǎng)景拼接過(guò)程中，效率會(huì)比較低下?，F(xiàn)在學(xué)術(shù)界一些優(yōu)化算法，如2004年由中國(guó)科學(xué)院的趙向陽(yáng)、杜利民等人提出的一種全自動(dòng)穩(wěn)健的圖像融合拼接算法，該方法通過(guò)RANSAC算法迭代計(jì)算出最大內(nèi)點(diǎn)集合后，利用LM（Levenberg-Marquardt）算法對(duì)單應(yīng)矩陣進(jìn)行優(yōu)化估計(jì)，但是在實(shí)際運(yùn)算過(guò)程中并沒有提高多少精度，反而計(jì)算效率進(jìn)一步降低；2012年寧德師范學(xué)院計(jì)算機(jī)系的張世良對(duì)算法進(jìn)行優(yōu)化，在采集數(shù)據(jù)樣本的時(shí)候通過(guò)用K-means聚類算法把N對(duì)角點(diǎn)進(jìn)行分組，每次4對(duì)數(shù)據(jù)求單應(yīng)矩陣1對(duì)數(shù)據(jù)進(jìn)行檢驗(yàn)，不符合要求的數(shù)據(jù)組直接剔除，運(yùn)用這種方式減少迭代次數(shù)，實(shí)際上剔除數(shù)據(jù)組的計(jì)算量并沒有實(shí)質(zhì)性的減少，所以整體算法的效率沒有提高。但是上述兩種方法為我們提高的優(yōu)化思路有兩點(diǎn)：

一是若是圖像采集質(zhì)量較低偽匹配點(diǎn)較多的情況下，在選取子集S時(shí)可以根據(jù)樣本特性等采用特定的選取方案，使用有約束的隨機(jī)選取來(lái)代替原來(lái)的完全隨機(jī)選取。

攝像機(jī)在同一平面水平排開，攝像機(jī)在水平和垂直方向沒有旋轉(zhuǎn)，那么匹配點(diǎn)間一定有x=xi+λdi+Δxi及y=y+Δyi的約束關(guān)系，其中λ為比例系數(shù)。通過(guò)約束關(guān)系很容易把偽匹配點(diǎn)排除掉，極大地減少出錯(cuò)概率和迭代次數(shù)。

二是若是圖像采集質(zhì)量較高偽匹配點(diǎn)較少的情況下在合理的基礎(chǔ)上簡(jiǎn)化運(yùn)算步驟，上述運(yùn)算過(guò)程中，我們采集每對(duì)點(diǎn)坐標(biāo)都進(jìn)行了閾值檢測(cè)，完全可以采用多點(diǎn)同時(shí)檢測(cè)的方法：

圖像質(zhì)量越高，m取值越大，同時(shí)檢測(cè)的點(diǎn)就越多，算法效率越高。通過(guò)實(shí)驗(yàn)，使用上述RANSAC算法，可以快速排除噪聲干擾，準(zhǔn)確地求出單應(yīng)矩陣。

4 結(jié)束語(yǔ)

如圖1所示，左側(cè)圖像顯示的是沒有使用RANSAC算法的圖像特征點(diǎn)匹配，可以看出出現(xiàn)個(gè)別錯(cuò)誤匹配，這將可能導(dǎo)致后續(xù)圖像拼接出現(xiàn)嚴(yán)重錯(cuò)誤。右側(cè)圖像是采用了RANSAC算法優(yōu)化的特征點(diǎn)匹配，完全排除了錯(cuò)誤干擾，符合運(yùn)用需求。

參考文獻(xiàn)：

[1]陳藝蝦.改進(jìn)的ransac算法在圖像配準(zhǔn)中的應(yīng)用[J].計(jì)算機(jī)科學(xué)與探索，2010.

[2]黃梅.基于改進(jìn)ransac算法的圖像拼接技術(shù)[J].海南大學(xué)學(xué)報(bào)，2011.

[3]WeiJei Huang， An Improved RANSAC Algorithm of Color Image Stitching， 2013.

[4]Xiaowei Li， Computing Homography with RANSAC Algorithm：A Novel Method of Registration， 2004.

[5]曲天偉.改進(jìn)的ransac算法在圖像配準(zhǔn)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用，2010.

[6]AditiMajumder， Rick Stevens. Perceptual Photometric Seamlessness inProjection-Based Tiled Displays， ACM Transactions on Graphics， Vol. 24， No.1 January 2005.

[7]賈瑩.基于Harris角點(diǎn)檢測(cè)算法的圖像拼接技術(shù)研究[D].吉林大學(xué)，2010.

[8]曾琦.Image registration method based on improved Harris corner detector， 2010.

[9]Mark Hereld， Ivan R. Judson， and Rick Stevens. A Measurement Engine for Aligning Multi-Projector Display Systems， Argonne National Laboratory preprint ANL/MCSP958-0502， 2002.

[10]A Way Based On Within-class Scatter Matrix to Improve RANSAC Algorithm， 2012.

[11]Liang Sun.An Improved Harris Corner Detection Algorithm For Low Contrast Image， 2014.

[12]黃梅.面向全景拼接的ransac算法改進(jìn)[D].海南大學(xué)，2011.

[13]陳利軍.圖像角點(diǎn)檢測(cè)和匹配算法的研究[J].通信與信息系統(tǒng)，2005.