RANSAC估算基礎矩陣的不確定性評價

卞 玉 霞,劉 學 軍,劉 丹

(南京師范大學虛擬地理環境教育部重點實驗室，江蘇 南京 210023)

?

RANSAC估算基礎矩陣的不確定性評價

卞 玉 霞,劉 學 軍,劉 丹

(南京師范大學虛擬地理環境教育部重點實驗室，江蘇 南京 210023)

RANSAC是計算機視覺領域內應用最廣泛的基礎矩陣估算方法，如何實現RANSAC估算基礎矩陣的不確定性評價值得探討。該文在研究RANSAC估算基礎矩陣模型的基礎上，提出采用基礎矩陣的錯誤率和平均對極距離的標準差作為評價RANSAC估算基礎矩陣不確定性的指標，并構建RANSAC估算基礎矩陣不確定性評價方法，實現RANSAC估算基礎矩陣不確定性評價。

RANSAC;基礎矩陣;錯誤率;平均對極距離;標準差

0 引言

基礎矩陣是序列圖像三維建模技術的核心命題之一，其不確定性直接影響攝像機標定、三維點云恢復等序列圖像三維建模后續環節的參數精度。現有的估算基礎矩陣方法主要有：線性方法[1,2]、迭代方法[3]和魯棒方法。考慮到線性和迭代方法不適用于存在錯誤匹配點的情況，目前序列圖像三維重建中主要采用魯棒方法估計基礎矩陣。在最小平方中值法[4,5]、M-estimators方法[6,7]、隨機抽樣一致算法(Random Sample Consensus，RANSAC)[8-11]等眾多的魯棒方法中，RANSAC是計算機視覺領域內應用最廣泛的[9]，是存在錯誤匹配點時較合適、常用的估算基礎矩陣的魯棒方法。

在RANSAC估算基礎矩陣不確定性研究方面，有學者針對GUM(Guide to the expression of Uncertainty in Measurement)方法評估基礎矩陣的不確定性，如：基于協方差矩陣表達基礎矩陣的不確定性[12,13]、采用八點線性算法估算基礎矩陣的不確定性[14]等。Silva等[15]認為“目前不確定性主要基于GUM方法進行評估，今后可以用蒙特卡羅方法進行不確定性評估”。蒙特卡羅模擬RANSAC估算基礎矩陣不確定性研究中，如何實現RANSAC估算基礎矩陣的不確定性評價是一個值得研究的問題。

為了解決上述問題，本文在研究RANSAC估算基礎矩陣模型基礎上，提出RANSAC估算基礎矩陣不確定性的評價指標，并構建RANSAC估算基礎矩陣不確定性評價方法，最后通過實驗方法實現RANSAC估算基礎矩陣不確定性評價。

1 RANSAC估算基礎矩陣

RANSAC是計算機視覺中關于魯棒參數估計的一種典型方法，它最早被Torr用于基礎矩陣估計。RANSAC估算基礎矩陣的主要思想是隨機選取最小樣本子集，計算該樣本子集得到初始基礎矩陣，并進一步判斷該初始基礎矩陣條件下一定距離閾值內所包含的數據點集，重復隨機采樣，最后選取最大的數據點集估算基礎矩陣，該值即作為RANSAC估算基礎矩陣的最終結果。

為了實現基礎矩陣模型與含有野值的魯棒擬合，本文研究Silva的RANSAC估算基礎矩陣模型及開源程序庫，該過程實質上可以看做是模型假設和驗證的過程。如圖1所示，具體的工作流程為：1)從樣本集S中隨機選擇7個匹配點對作為最小樣本子集，采用7點線性算法估算初始基礎矩陣F1。2)確定與F1相關的距離閾值內所包含的數據點集。3)重復步驟1和2，確定N次采樣中與各個初始基礎矩陣相關的距離閾值內所包含的數據點集。4)從步驟3中選擇最大的數據點集，并采用最小二乘原理計算基礎矩陣，該值即作為RANSAC估算基礎矩陣的最終結果。

2 RANSAC估算基礎矩陣的不確定性

本文擬采用基礎矩陣的錯誤率和平均對極距離的標準差作為基礎矩陣不確定性的評價指標，并構建RANSAC估算基礎矩陣不確定性的評價方法。

圖1 RANSAC估算基礎矩陣

Fig.1 The estimation of fundamental matrix based on RANSAC

2.1 評價指標

基礎矩陣的錯誤率和平均對極距離的殘差是基于平均對極距離進行量化的。平均對極距離是立體像對中所包含的每一匹配點的對極線與該點在另一幅圖像上的匹配點之間的距離(對匹配中的兩點都計算)平方和的均值U。如圖2所示，U具體表達為[16]：

(1)

圖2 點到相應對極線的距離

Fig.2Thedistancebetweenmatchpointandcorrespondingepipolarline

(1)基礎矩陣的錯誤率。RANSAC估算基礎矩陣是采用隨機抽樣法抽取樣本進行估算的，其計算過程具有隨機性，特別是當最大數據點集中包含野值時，估算的基礎矩陣會存在錯誤基礎矩陣。估算基礎矩陣正確與否可以作為評價基礎矩陣不確定性的指標之一。

基于式(1)，將平均對極距離較大時的基礎矩陣定義為錯誤基礎矩陣。采用統計學原理分析RANSAC估算基礎矩陣不確定性時，基礎矩陣的錯誤率Err可以表示為：

(2)

式中：e表示平均對極距離較大時的基礎矩陣數量；M表示模擬次數。

(2)平均對極距離的標準差。不同矩陣之間不存在均值和方差等統計意義，基礎矩陣線性化是實現基礎矩陣不確定性統計分析的方法之一。已知基礎矩陣，可以計算匹配點到相應對極線的距離，該值是由于匹配點位置不確定性引起的。當已知匹配點位置，可以計算匹配點到相應對極線的距離，該值是由于基礎矩陣的不確定性引起的。基于這樣的思考，本文將評價基礎矩陣不確定性轉化為求平均對極距離U的標準差(σU)，公式為：

(3)

2.2 評價方法

在統計學中，不確定性主要包含誤差和粗差。本文假設基礎矩陣的錯誤率相當于統計學中的粗差，而平均對極距離的標準差相當于統計學中的誤差，它們共同表達了RANSAC估算基礎矩陣的不確定性。結合RANSAC估算基礎矩陣模型，本文在選用基礎矩陣的錯誤率和平均對極距離的殘差這兩個評價指標的基礎上，設計了圖3所示的RANSAC估算基礎矩陣不確定性的評價方法。

圖3 RANSAC估算基礎矩陣的不確定性評價方法

RANSAC估算基礎矩陣的不確定性評價方法是基于立體像對中提取的匹配點對，通過執行RANSAC模型獲得基礎矩陣的條件下，根據式(1)計算立體像對中提取的匹配點對的平均對極距離，進而判斷與該平均對極距離相對應的基礎矩陣是錯誤基礎矩陣還是正確基礎矩陣。當執行M次模擬后，統計錯誤基礎矩陣的數量，進而根據式(2)計算基礎矩陣的錯誤率,并根據式(3)計算正確基礎矩陣所對應的平均對極距離的標準差。

3 實驗分析

為了實現基于基礎矩陣的錯誤率和平均對極距離的標準差來評價RANSAC估算基礎矩陣不確定性，本實驗選用RANSAC開源程序庫中的立體像對，用SIFT特征匹配模型提取的匹配點對作為本實驗的數據源。如圖4所示，圖中線段的兩端點表示提取的匹配點對。

圖4 數據源

Fig.4 The data source

本次實驗設M=1 000，執行如圖3所示的RANSAC估算基礎矩陣的不確定性評價方法，其結果如圖5所示。圖5中橫坐標是模擬次數M，縱坐標是每次模擬所計算的平均對極距離，可以看出，平均對極距離主要分布在0～1和80～140等區域。顯然，80～140區域中平均對極距離過大，這是由于RANSAC估算基礎矩陣錯誤而引起的。文獻[17]中指出大多數匹配點的誤差會控制在3個像素以內，因此本實驗規定基礎矩陣的錯誤率是平均對極距離大于3個像素的基礎矩陣與M的比值。

圖5中有149個平均對極距離大于3，即有149個錯誤基礎矩陣，根據式(2)可以認為本實驗中RANSAC估算基礎矩陣的錯誤率為15%。當剔除149個錯誤基礎矩陣時，圖5中有851個正確基礎矩陣，根據式(3)統計分析可以得出：正確基礎矩陣對應的平均對極距離為0.31，標準差為0.001。圖5中的局部放大圖展示的是第3～23次的模擬結果，它代表與正確基礎矩陣相對應的平均對極距離的分布情況，圖中各平均對極距離及其變化趨勢清晰地表明上述計算平均距離標準差的正確性。

圖5 平均對極距離

Fig.5 The mean distance of epipolar

4 結論

立體像對中提取的匹配點對存在正確匹配點對和錯誤匹配點對，其作為RANSAC估算基礎矩陣的數據源時，會影響RANSAC估算基礎矩陣結果的正確性；且RANSAC估算基礎矩陣的結果是矩陣的形式，它不具備統計意義。為了解決以上問題，本文提出用基礎矩陣的錯誤率和平均對極距離的標準差作為評價RANSAC估算基礎矩陣不確定性的指標，并在此基礎上構建了RANSAC估算基礎矩陣不確定性評價方法，實現了RANSAC估算基礎矩陣不確定性的評價。

[1] HARTLEY R.Projective reconstruction from line correspondence[A].Computer Vision and Pattern Recognition[C].1994.

[2] LONGUET H C.A computer algorithm for reconstructing a scene from two projections[J].Nature,1981,293(10):133-135.

[3] LUONG Q T,FAUGERAS O D.Determining the fundamental matrix with planes:Unstability and new algorithm[A].Computer Vision and Pattern Recognition[C].1993.489-494.

[4] ROUSSEEUW P,LEROY A.Robust Regression and Outlier Detection[M].New York：John Wiley & Sons,1987.

[5] ZHOU H,GREEN P R,WALLACE A M.Estimating of epipolar geometry by linear mixed-effect modeling[J].Neurocomputing,2009,72(6):3881-3890.

[6] HUBER P J.Robust Statistics[M].New York:John Wiley & Sons,1981.

[7] 張潔玉,陳強,劉復昌,等.一種改進的M-Estimators基礎矩陣魯棒估計法[J].中國圖象圖形學報，2009,14(8):1663-1668.

[8] FISCHLER M,BOLLES R.Random sample consensus:A paradigm for model fitting with applications to image analysis and automated cartography[J].Communications of the ACM,1981,24:381-385.

[9] 陳付幸,王潤生.基于預檢驗的快速隨機抽樣一致性算法[J].軟件學報,2005,16(8):1431-1437.

[10] 田文,王宏遠,徐帆,等.RANSAC算法的自適應Tc,d預檢驗[J].中國圖象圖形學報,2009,14(5):973-977.

[11] 周駿.陳雷霆.劉啟,等.基于序貫概率及局部優化隨機抽樣一致性算法[J].儀器儀表學報,2012,33(9):2037-2044.

[12] CSURKA G,ZELLER C,ZHANG Z,et al.Characterizing the uncertainty of the fundamental matrix[J].Computer Vision and Image Understanding,1997,68(1):18-36.

[13] RAGURAM R,FRAHM J M,POLLEFEYS M.Exploiting uncertainty in random sample consensus[A].Computer Vision[C].2009.2074-2081.

[14] SUR F,NOURY N,BERGER M O.Computing the uncertainty of the 8 point algorithm for fundamental matrix estimation[C].BMVC,2008.

[15] SILVA H P,CATEN C S.Measurement uncertainty:Literature review and research trends[J].Instrumentation and Measurement,2012,61(8):2116-2124.

[16] 韋穗,楊尚駿,章權冰,等.計算機視覺中的多視圖幾何[M].合肥:安徽大學出版社,2002.198-199.

[17] 鐘慧湘.基礎矩陣計算方法的研究[D].吉林:吉林大學,2005.32-33.

Estimation of Fundamental Matrix Uncertainty Based on Random Sample Consensus

BIAN Yu-xia，LIU Xue-jun，LIU Dan

(KeyLaboratoryofVirtualGeographicEnvironment(NanjingNormalUniversity),MinistryofEducation,Nanjing210023,China)

It is the most widely method for Random Sample Consensus to estimate the fundamental matrix in the field of computer vision.And meanwhile,the estimation of fundamental matrix uncertainty based on Random Sample Consensus was paid more attention to.As for this problem,the estimation fundamental matrix of Random Sample Consensus has been studied here.And based on this,error rate of fundamental matrix and the standard deviation of epipolar mean distance have been chosen as the evaluation index of fundamental matrix uncertainty.And then,the methodology can be built to achieve the estimation of fundamental matrix uncertainty based on Random Sample Consensus.

Random Sample Consensus;fundamental matrix;error rate;mean distance of epipolar;standard deviation

2014-03-05；

2014-07-15

國家科技支撐計劃項目(2012BAH35B02)；江蘇省普通高校研究生科研創新計劃項目(KYZZ_0213)

卞玉霞(1987-)，女，博士研究生,主要研究方向為視頻三維建模及其質量評價。E-mail:byx310@163.com

10.3969/j.issn.1672-0504.2015.01.008

TP391.41

A

1672-0504(2015)01-0037-04