基于交比不變性約束的快速隨機(jī)抽樣一致性算法

王 萍，曹 楠，操曉春，歐陽(yáng)健飛

(1. 天津大學(xué)理學(xué)院，天津 300072；2. 天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300072；3. 天津大學(xué)精密測(cè)試技術(shù)及儀器國(guó)家重點(diǎn)實(shí)驗(yàn)室，天津 300072)

在多種魯棒性估計(jì)算法中，標(biāo)準(zhǔn)隨機(jī)抽樣一致性(RANSAC)算法[1]憑借其強(qiáng)大的噪聲處理能力脫穎而出．然而，隨著模型估計(jì)要求的提高，標(biāo)準(zhǔn)RANSAC算法的不足之處也日益彰顯出來(lái)[2-5]．其中，效率低是其最為突出的一個(gè)缺點(diǎn)[6-7]．在模型估計(jì)過程中，算法采用隨機(jī)取樣策略，通過迭代估計(jì)模型[8]．這種全局撒網(wǎng)式的搜索方法，隨著數(shù)據(jù)中外點(diǎn)比例的增加，勢(shì)必造成迭代次數(shù)的激增，從而影響算法效率．如果能在初始取樣時(shí)直接篩選出可能的內(nèi)點(diǎn)，就會(huì)縮小搜索范圍，減少不必要的計(jì)算過程，從而提高RANSAC算法的效率．基于此想法，筆者提出了一種基于模型約束的改進(jìn)算法，即利用射影變換下共線4點(diǎn)的交比不變性，處理高噪聲數(shù)據(jù)下的平面單應(yīng)矩陣估計(jì)問題．

1 概率統(tǒng)計(jì)分析

Guo等[9]提出，模型性質(zhì)可以用來(lái)約束有效采樣策略，解決大量外點(diǎn)存在情況下的模型估計(jì)問題．

令 Zl是由Z中元素組成的l元組的子集，對(duì)于每個(gè) zl∈Zl，Izl代表全為內(nèi)點(diǎn)的l點(diǎn)組，Ozl代表至少有1個(gè)點(diǎn)是外點(diǎn)的l點(diǎn)組．定義 Zl上的性質(zhì)Q，且有

在 s個(gè)點(diǎn)組成的隨機(jī)樣本中，P ( Isl)為隨機(jī)選取到l點(diǎn)組是內(nèi)點(diǎn)的概率，由貝葉斯定理可知，

設(shè)m是估計(jì)模型所需要的最少元素個(gè)數(shù)，ρ代表在隨機(jī)樣本中多次采樣至少1次沒有外點(diǎn)的概率，通常取為0.99，P ( Is)為隨機(jī)選取到內(nèi)點(diǎn)的概率，則在標(biāo)準(zhǔn)RANSAC下迭代次數(shù)為

而改進(jìn)后的算法估計(jì)模型所需要的最少迭代次數(shù)為

式中 ml是估計(jì)l點(diǎn)組模型所需要的最少元素個(gè)數(shù)．要提高改進(jìn)算法的效率，就要減少不必要的迭代次數(shù)．令(,)J l QJ＜，由式(3)、式(4)可知，有

與式(2)比較，可得

由此可知，要找到好的模型約束，就要滿足上述的概率條件．在這種模型約束思想的引導(dǎo)下，筆者提出了利用射影變換下共線 4點(diǎn)的交比不變性提高單應(yīng)矩陣估計(jì)效率的方法．

2 算法模型的建立

式中 P ( Q ( f ) |Of)代表外點(diǎn)中存在共線且保持交比性質(zhì)的 4點(diǎn)組的概率．顯然，這個(gè)概率可以通過估計(jì)平面上任意 4點(diǎn)共線且滿足某一交比的概率近似得到．下面分2步求得這個(gè)概率．

2.1 計(jì)算平面上任意4點(diǎn)共線的概率

即使是滿足約束的內(nèi)點(diǎn)，由于噪聲等影響，也不可能精確共線．Guo等[9]給出了平面上任意3點(diǎn)共線的概率的模型和計(jì)算方法，在此基礎(chǔ)上，提出計(jì)算平面上任意4點(diǎn)共線的概率．具體模型如圖1所示．設(shè)距離最遠(yuǎn)的2點(diǎn)為B和H，剩下的2點(diǎn)必然在ABH區(qū)域內(nèi)(由對(duì)稱性可將 BH左側(cè)的點(diǎn)翻轉(zhuǎn)到 ABH區(qū)域內(nèi))；否則超出這個(gè)范圍，BH距離就不是最遠(yuǎn)的．根據(jù)文獻(xiàn)[9]定義距離閾值 γ，則另外兩點(diǎn)到 BH的最短距離至少是

圖1 4點(diǎn)共線約束模型Fig.1 Model using for the constraint of four points being collinear

令OE h= ，過 E點(diǎn)做平行于 BH的直線，當(dāng)另外2點(diǎn)在圍成的區(qū)域BHFD內(nèi)時(shí)，4點(diǎn)近似共線．由此，根據(jù)圖1，平面上任意4點(diǎn)共線比例可以估計(jì)為

式中S代表區(qū)域的面積．由于經(jīng)過射影變換后，4個(gè)點(diǎn)的相對(duì)位置要保持不變，所以所求概率為

2.2 計(jì)算共線4點(diǎn)滿足某一交比的概率

首先，確定最遠(yuǎn)的2點(diǎn) p1和 p4，連接2點(diǎn)得到線段L，根據(jù)定義，p2和 p3在 p1和 p4之間的直線L上．在確定 p3的位置之前，p2可以在L上除了 p1和p4的任意位置．由于直線L滿足均勻分布，因此，可以得到 p2定位的概率是 1．一旦確定了 p2的位置，為了滿足交比k，p3的定位就不再是任意的．設(shè) p1、p2、 p3、 p4的坐標(biāo)分別為0、x2、x3、1，則交比為

由式(11)，可以得出3p的位置為

故2p的坐標(biāo)2x和K確定后，3p的定位概率為

這樣，可以得到最后只依賴于閾值γ和δ的 4點(diǎn)共線且滿足某一交比的概率為

將式(16)代入式(7)中，有

這些滿足約束的點(diǎn)最終構(gòu)成了 1個(gè)子集，這個(gè)子集中的每個(gè)元素都是由共線且滿足某一交比的 4點(diǎn)組成．要估計(jì)1個(gè)單應(yīng)矩陣，則至少需要2組這樣的 4點(diǎn)組，即 8對(duì)點(diǎn)進(jìn)行計(jì)算．由式(4)可知，改進(jìn)后算法的最少迭代次數(shù)為因此，只要選擇合適的閾值γ和δ，這種模型約束的采樣方法就可以有效提高算法的迭代速度．例如，當(dāng)γ和δ分別取0.06和0.09時(shí)，要想提高算法效率只需要υ＞0.01，也就是說，只要數(shù)據(jù)中的外點(diǎn)比例不大于99%，改進(jìn)的算法就比標(biāo)準(zhǔn)RASAC算法更有效率．

3 實(shí)驗(yàn)結(jié)果對(duì)比和分析

為了進(jìn)一步證明改進(jìn)算法的正確性與高效性，本節(jié)用一些實(shí)驗(yàn)結(jié)果來(lái)驗(yàn)證上述的一些結(jié)論．

3.1 驗(yàn)證改進(jìn)算法的正確性

在第2節(jié)中計(jì)算了平面上任意4點(diǎn)共線且滿足某一交比的概率，但這些理論值是否與實(shí)際情況相符，還需進(jìn)一步驗(yàn)證．圖2是用訓(xùn)練數(shù)據(jù)模擬的4點(diǎn)共線和共線 4點(diǎn)滿足某一交比的驗(yàn)證結(jié)果，其中圖2(a)為 4點(diǎn)共線的驗(yàn)證結(jié)果，可以看出，實(shí)際值保持在理論值上下波動(dòng)，閾值γ的值越小，擬合效果越好；圖2(b)則為共線4點(diǎn)滿足某一交比的驗(yàn)證結(jié)果．

由圖 2可知，實(shí)際值與理論值十分接近，它們之間的誤差可近似認(rèn)為是魯棒的．

3.2 驗(yàn)證改進(jìn)算法的高效性

當(dāng)ρ= 0 .999時(shí)，取γ和δ分別為 0.04和 0.09，在不同噪聲的訓(xùn)練數(shù)據(jù)下，比較 RANSAC、CONSAC[9]和本文改進(jìn)算法的迭代次數(shù)，如表1所示．

從表1可以看出，當(dāng)內(nèi)點(diǎn)比例為1.5%時(shí)，CONSAC算法的效率比標(biāo)準(zhǔn)RANSAC算法低，也就是說CONSAC算法在外點(diǎn)比例大于98.5%的情況下不再有效率．而本文提出的改進(jìn)算法相對(duì) CONSAC而言，在解決高噪聲數(shù)據(jù)方面的優(yōu)勢(shì)更加明顯．

圖2 4點(diǎn)共線與共線4點(diǎn)滿足交比概率的理論值與實(shí)際值的比較Fig.2 Comparison between theoretical and practical probability of four points being collinear and four collinear points satisfied certain cross ratio

表1 3種算法的理論迭代次數(shù)的比較Tab.1 Comparison of theoretical iteration number among three distinct algorithms

為了使對(duì)比更加直觀，將3種算法迭代次數(shù)的比較以坐標(biāo)圖的形式給出．如圖 3所示，橫坐標(biāo)代表不同的內(nèi)點(diǎn)比例；由于隨著訓(xùn)練數(shù)據(jù)中內(nèi)點(diǎn)比例的變化，迭代次數(shù)變化很大，這里將迭代次數(shù)取以10為底的對(duì)數(shù)作為縱坐標(biāo)．圖3中的3條連線，自上而下分別代表標(biāo)準(zhǔn) RANSAC、CONSAC和本文提出的改進(jìn)算法在不同內(nèi)點(diǎn)比例情況下迭代次數(shù)的變化．

由圖3可知，本文提出的算法在很大程度上減少了RANSAC算法的迭代次數(shù)，在CONSAC算法的基礎(chǔ)上，進(jìn)一步提高了處理高噪聲數(shù)據(jù)的能力與效率．

4 算法應(yīng)用

RANSAC估計(jì)單應(yīng)矩陣在計(jì)算機(jī)視覺和圖像處理方面有許多用途，如圖像拼接、圖像融合和紋理渲染等，這里以圖像拼接為例介紹本文改進(jìn)算法的應(yīng)用.

圖像拼接是計(jì)算機(jī)視覺領(lǐng)域的一個(gè)重要分支，它是將兩幅以上具有部分重疊的圖像進(jìn)行拼接，從而得到較高分辨率或?qū)捯暯菆D像的一種技術(shù)[10]．這里給出圖像拼接的系統(tǒng)框架，如圖4所示．

圖4 圖像拼接的系統(tǒng)框架Fig.4 Frame diagram of image stitching

圖像拼接過程包括如下4個(gè)步驟．

(1) 輸入兩幅圖像，如圖5所示．

為了體現(xiàn)本文改進(jìn)算法對(duì)高噪聲數(shù)據(jù)的處理能力，盡量選擇干擾大的圖像，如圖5的兩幅圖像，樓前面的樹枝就是噪聲，在提取特征點(diǎn)后，很容易將樓的特征點(diǎn)誤匹配到樹枝上，而本文算法在處理這些干擾方面是有效率的．

(2) 應(yīng)用 SIFT等特征提取算法，分別提取兩幅圖像的特征點(diǎn)并匹配．

(3) 應(yīng)用本文的改進(jìn) RANSAC算法，消除高噪聲數(shù)據(jù)下的誤匹配對(duì)，計(jì)算單應(yīng)矩陣．

(4) 實(shí)現(xiàn)最終圖像轉(zhuǎn)換與拼接，如圖6所示．

圖5 輸入圖像Fig.5 Input images

圖6 兩幅圖像拼接的結(jié)果Fig.6 Result of image stitching

RANSAC算法在拼接過程中的作用主要有 2點(diǎn)：一是在提取并匹配特征點(diǎn)后，消除其中的誤匹配對(duì)，即算法中剔除外點(diǎn)的過程；二是計(jì)算出兩幅圖像之間的單應(yīng)矩陣，對(duì)相應(yīng)圖像進(jìn)行變換．而本文對(duì)RANSAC算法的改進(jìn)，增強(qiáng)了算法處理高噪聲圖像的能力和速度，進(jìn)一步提高了RANSAC算法的效率.

5 結(jié) 語(yǔ)

本文提出了一種基于采樣的模型約束方法，在使用 RANSAC估計(jì)單應(yīng)矩陣時(shí)，利用射影變換下共線4點(diǎn)的交比不變性，提前篩選出可能的內(nèi)點(diǎn)，并使用這些候選點(diǎn)而不是全部的數(shù)據(jù)點(diǎn)進(jìn)行迭代計(jì)算，很大程度上減少了迭代次數(shù)，從而提高了算法的效率．

除了理論分析，本文還選取了一系列訓(xùn)練數(shù)據(jù)，對(duì)算法改進(jìn)的關(guān)鍵部分進(jìn)行驗(yàn)證，以理論和實(shí)際結(jié)果來(lái)驗(yàn)證改進(jìn)算法的正確性．同時(shí)，選取適當(dāng)?shù)拈撝担垢倪M(jìn)算法在處理外點(diǎn)比例不大于99%的高噪聲數(shù)據(jù)時(shí)，比標(biāo)準(zhǔn)RANSAC算法和CONSAC算法效率更高．

［1］Fischler M A，Bolles R C. Random sample consensus：A paradigm for model fitting with applications to image analysis and automated cartography[C]//European Conference on Computer Vision. Cambridge，UK，1996：683-695.

［2］Matas J，Chum O. Randomized RANSAC with Td,dtest[J].Image and Vision Computing，2004，22(10)：837-842.

［3］Chum O，Matas J. Optimal randomized RANSAC[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30(8)：1472-1482.

［4］Tordoff B，Murray D W. Guided sampling and consensus for motion estimation[C]//European Conference on Computer Vision.Copenhagen，Denmark，2002：82-98.

［5］Nister D. Preemptive RANSAC for live structure and motion estimation[C]//International Conference on Computer Vision.Beijing，China，2003：199-206.

［6］Zhang W，Kosecka J. A new inlier identification procedure for robust estimation problems[C]//Robotics：Science and Systems Conference.Philadelphia，USA，2006：137-144.

［7］Raguram R，F(xiàn)rahm J，Pollefeys M. A comparative analysis of RANSAC techniques leading to adaptive real-time random sample consensus[C]//European Conference on Computer Vision. France，2008：500-513.

［8］Hartley R I，Zisserman A.Multiple View Geometry in Computer Vision[M]. Cambridge：Cambridge University Press，2000.

［9］Guo Feng，Aggarwal Gaurav，Shaque Khurram，et al. An efficient data driven algorithm for multi-sensor alignment[C]//ECCV Workshop on Multi Camera and Multi-Modal Sensor Fusion Algorithms and Applications.France，2008：Inria-00326738.

［10］Brown M，Lowe D G. Automatic panoramic image stitching using invariant features[J].International Journal of Computer Vision，2007，74(1)：59-73.