一種改進RANSAC的基礎矩陣估計方法

甄 艷，劉學軍，王美珍

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

一、引 言

從不同視點處獲得同一場景的兩幅圖像間存在重要的幾何約束關系，即對極幾何關系。對極幾何獨立于場景結構，是在非標定情況下可以從圖像中獲得的唯一信息。基礎矩陣是對極幾何關系的代數表示，它的準確求解是解決其他視覺問題的關鍵環節之一，如三維重建[1]、運動估計、相機自標定[2]、匹配及跟蹤的基礎。目前，利用圖像間對應點來估算基礎矩陣的方法主要可以分為3類：線性方法、迭代方法和魯棒方法[3]。線性方法的特點是計算速度快，但對于噪聲和錯誤匹配非常敏感；迭代方法的精度通常比線性方法高，但計算時間長。當匹配點集中出現錯誤匹配時，線性方法和迭代方法已經不再適用，而魯棒方法可以解決這類問題，如最小中值法(least median squares，LMedS)、隨機抽樣一致性法(random sample consensus，RANSAC)及M估計算法(M-estimator sample consensus，M-Estimators)，這類方法的特點是對噪聲和錯誤匹配都有更好的魯棒性。當錯誤數據超過50%時，RANSAC仍能獲得較好的結果，近年來根據RANSAC算法的思想衍生出MINPRAN算法[4]和MLESAC[5]等算法。

傳統RANSAC算法在外點比率較大時算法效率較低，Matas和Chum[6]提出的預檢驗算法可有效提高算法效率，陳付幸[7]和田文[8]等在此基礎上重新設定預檢驗的條件，設計了自適應的預檢驗方法。RANSAC算法也存在樣本選擇的隨機性導致結果具有較大隨機性的問題，劉坤[9]和魯珊[10]等提出基于概率抽樣的方法來解決這一問題，該方法可在一定程度上提高算法的精度，但由于在模型檢驗過程中需要計算每個樣本點的抽樣概率并根據設定的閾值來選擇樣本點，計算過程較復雜。針對上述問題，本文提出了一種改進RANSAC的基礎矩陣估計算法。

二、RANSAC算法效率與精度分析

RANSAC算法的基本思想是在保證一定置信概率的前提下，經過多次抽樣取得至少一個樣本包括的點全是無污染的樣本，從而保證得到正確的參數模型。其計算過程實質上可看做是模型的假設與驗證的過程，如圖1所示。在模型假設階段，從原始數據中隨機抽取最小子集來估計模型參數；在模型驗證階段，需要對估計的模型參數進行驗證，驗證方法一般是計算原始數據中與估計的模型參數相容的樣本數量。

1. RANSAC算法效率分析

設原始數據中共有N對匹配點，從中隨機抽取一個最小子集來估計模型參數的時間，記為Cestimate，用一個數據檢驗模型參數需要的時間，記為Cfitting，則用原始數據中的全部數據檢驗模型參數的算法復雜度為O(NCfitting)。因此，RANSAC算法完成K次樣本假設與驗證的過程算法復雜度為

圖1 RANSAC算法流程圖

(1)

從式(1)可以看出，影響RANSAC算法計算效率的因素主要有兩個：抽樣次數和模型驗證所需時間。因此，要提高RANSAC算法的效率，可減少抽樣次數和減少模型驗證所需的時間。

2. RANSAC算法精度分析

由于在特征點提取與匹配過程中不可避免會含有噪聲和外點數據，在外點比率較高的情況下，隨機采樣的數據中通常都含有外點數據，因此，用含有外點的樣本數據估計得到的模型參數常常含有較大誤差。另外，在模型參數的檢驗過程中，尋找與該模型相容的樣本數據時，一般方法是通過設定的閾值來判斷的。若閾值設定過大，則會滲入大量的外點數據；若閾值設定過小，則檢驗過程會過分嚴格，進而篩選掉內點數據。因此，閾值的設定對算法的精度也有一定的影響。

綜合分析，影響RANSAC算法計算精度的因素主要有兩個：樣本選擇與閾值設定，而閾值一般是根據經驗值進行設定的，目前沒有更好的解決方案。若原始匹配點集合的質量較好，無論采用何種方式選擇樣本數據都能得到較好的估計結果，而事實上，到目前為止，沒有一種算法可以完全消除外點的影響。要從根本上提高RANSAC算法的計算精度，需要較全面地檢測和剔除外點數據。

三、改進RANSAC的基礎矩陣估計算法

在基礎矩陣的計算過程中，估計模型參數所需的樣本數量基本是固定的，一般采用7點法或8點法來估計初始值。算法在保證一定置信概率的前提下，抽樣次數與數據錯誤率有關，一旦數據錯誤率確定了，算法所需的抽樣次數也就隨之確定了，很難再改變。因此，通過上述分析，要提高基礎矩陣的計算效率，可考慮從減少模型參數的檢驗時間入手，而預檢驗算法在不改變算法精度的前提下，可以很大限度地減小計算量，提高算法效率。根據前面對影響RANSAC算法精度的因素分析可知，檢測并剔除外點數據是提高算法精度的關鍵，而一個好的模型參數更有利于檢測出外點數據。提高RANSAC算法精度的一個可行方法是在樣本選擇時盡可能選擇內點數據來估計模型參數。

1. 預檢驗

在RANSAC算法的計算過程中，大部分抽樣都會受到外點的影響，對受到外點影響的這部分模型，每次都用全部數據去檢驗，這無疑浪費了大量的計算時間。預檢驗方法可有效減少模型參數的檢驗時間，其基本思想是：用少量樣本數據來評估模型參數，如果該模型可以通過預檢驗，則認為當前模型是一個好模型，可接著進行后續的全部數據檢驗；否則認為該模型受到外點數據的污染，不再參與后續檢驗。加入預檢驗后，雖然不能改善算法精度，其精度與原RANSAC算法基本保持一致，而效率方面卻可大幅提升。

2. 樣本選擇

采用傳統RANSAC算法估計基礎矩陣時，每次抽樣都是一個相對獨立的過程，并沒有考慮前面已完成過程的反饋信息。而實際上，在前面已完成的抽樣過程中，每次都需要對原始匹配點集中每個點是否為內點進行判斷，對于每對匹配點質量的好壞，已經有了初步的判斷。如果能夠利用前面累積的反饋信息來指導下次抽樣，這無疑將提高抽取樣本的質量，從而可以更好地檢測內點和外點數據。在多次循環驗證的過程中，傳統的RANSAC算法只記錄每個基礎矩陣初始值對應的內點總數，而實際上，在整個判斷過程中可同時記錄下每對點是否為內點。統計每對匹配點被標記為內點的次數，選擇被標記為內點的次數較多的這部分點構成候選集合。在下一次樣本抽取時，可直接從候選集合中進行。由于候選集合中的數據是根據被判斷為內點的次數來確定的，因此，該集合的中的點作為內點的概率也大于其他點。每次驗證過程結束后，需要重新計算每對匹配點被標記為內點的次數并更新候選集合，以便指導下一次抽樣。

3. 算法過程

本文算法的基本思想是以傳統RANSAC算法為框架，為提高算法效率與計算精度，結合預檢驗方法，選擇被標記為內點次數較多的樣本來估計基礎矩陣初始值。計算過程可分為初始候選集合構成和內點集的確定兩個部分，具體描述如下：

(1) 初始候選集合生成

1) 計算所需抽樣次數K。

2) 在前K/3次抽樣中，從原始匹配點集合中隨機選擇8個樣本點，用改進的8點算法計算基礎矩陣的初始值。

3) 加入預檢驗步驟，在對通過預檢的初始值進行驗證的過程中，計算對應的內點數量的同時標記每對匹配點是否為內點。

4) 完成K/3次抽樣后，計算到目前為止每對匹配點被標記為內點的次數，選擇被標記內點次數較多的匹配點對構成初始候選集合。

(2) 內點集確定

1) 在余下的抽樣過程中，采用前面介紹的樣本選擇方法，從候選集合中選擇最小子集來估計基礎陣的初始值。

2) 結合預檢驗方法，若當前模型參數通過預檢驗，計算其對應的內點數量并重新計算初始集合中每對匹配點被標記為內點的次數。

3) 更新候選集合。

4) 完成K次抽樣后，選擇包含內點數量最多的集合作為內點集。

5) 根據確定的內點集，采用M-Estimators方法重新估計基礎矩陣，并將結果作為最優值返回。

四、試驗結果與分析

為了驗證本文算法的有效性和魯棒性，分別對大量的模擬數據和真實圖像數據進行了試驗，將本文算法與M-Estimators、LMedS和RANSAC 3種經典魯棒方法進行對比，用點到對應極線的平均對極距離來精確反映基礎矩陣的估計精度，對極距離越小，說明基礎矩陣的估計精度越高。由于篇幅所限，本文直接給出部分試驗結果。

1. 模擬數據和真實圖像試驗

模擬數據是采用程序生成同一場景不同視角兩幅圖像的匹配點對，數量為100。添加均值為0，方差為1.0的高斯噪聲后，不同外點比率下4種算法的計算精度比較結果如圖2所示。表1為在外點比率為20%的情況下，不同噪聲下4種算法的計算精度比較。

圖2 4種方法在不同比率外點數據情況下的平均對極距離

表1 不同噪聲情況下的平均對極距離 像素

圖3為采用SIFT算法對兩幅圖像進行特征提取與匹配獲得初始匹配集合的效果圖。其中，場景1包含的匹配點數量相對較多，共1247對；場景2包含147對，相對少一些。之所以選擇這兩幅圖像，是由于其包含的匹配點數量有較大差別，可驗證在不同匹配點數量下算法的魯棒性。表2給出了每個場景通過上述4種算法獲得的平均對極距離和標準偏差。

圖3 兩幅圖像特征提取與匹配效果圖

表2 4種方法對真實圖像數據的計算結果 像素

2. 計算精度分析

從上述試驗結果來看，無論模擬數據還是真實圖像試驗數據，本文算法的結果均優于其他3種方法。在不同比率的外點數據下，M-Estimators方法隨著外點比率的增大誤差最大，LMedS方法的精度略優于RANSAC方法，本文算法一直能保持較高精度。從表1的試驗結果可以看出，隨著噪聲的增大，4種算法的精度都有所降低，M-Estimators方法受噪聲影響最大。當噪聲強度超過1.0時，LMedS方法和RANSAC方法的誤差較大，而本文方法在噪聲強度為3.0時，仍能保持較高的精度。從真實圖像試驗結果來看，無論匹配點數量的多少，本文算法的結果都優于其他3種方法。當匹配點數量較少，且外點率較高時，算法體現出更好的性能。

綜合分析，本文算法的計算精度優于其他3種方法，這主要得益于兩個方面：一方面是本文算法在樣本選擇時從被判斷為內點次數較多的點中抽取樣本點來估計模型參數，選擇的樣本點作為內點的概率較大，為下一步處理提供了較好的模型參數，可以更準確地判斷內外點；另一方面是在獲得內點集的基礎上，采用M-Estimators方法迭代處理不斷優化，進一步去除對結果影響較大的匹配點，從而提高了算法的估計精度。

3. 計算效率分析

為考察本文算法的計算效率，分別計算不同外點比率和不同匹配點數量下4種算法的計算時間。不同外點比率下算法的計算時間如圖4所示，試驗數據中添加有均值為0，方差為1.0的高斯噪聲。不同匹配點數量下算法的計算時間以場景1為例，圖5為試驗結果。

從圖4可以看出，在外點比率小于40%時，4種算法的計算時間差別不大，隨著外點比率的增大，M-Estimators算法一直保持較高的計算效率，而RANSAC算法的計算時間呈指數增長；當外點比率超過50%時，除M-Estimators算法外，其他3種方法的計算時間會隨著外點比率的增加而增大；當外點比率增加到60%時，本文算法所需計算時間遠小于RANSAC方法與LMedS方法。從圖5可以看出，隨著匹配點數量的增多，4種算法的計算時間也隨之增長，LMedS方法的計算時間增加最快，M-Estimators的計算時間雖然也有所增加，但其計算效率仍是4種方法中最高的。而本文算法的計算效率仍優于LMedS方法與RANSAC方法。

圖4 不同外點比率下4種算法的計算時間

圖5 不同匹配點數量下4種算法的計算時間

4. 本文算法與PARANSAC算法比較

魯珊[10]等針對隨機抽樣一致性算法效率低的問題，提出了一種基于概率分析的隨機抽樣一致性算法(PARANSAC)。為進一步驗證本文算法的精度與效率，將本文算法與PARANSAC算法對比，試驗數據采用文獻[10]中的真實圖像數據，結果如圖6所示。從表3的試驗結果來看，本文算法在計算精度與效率上均優于PARANSAC算法。本文算法樣本選擇策略簡單，不增加額外的計算開銷，而PARANSAC算法在每次迭代過程中都需要計算每對匹配點的概率，并且在計算過程中需要設置合適的閾值，閾值設置不當將嚴重影響計算結果。

圖6 不同角度的2組真實圖像

表3 計算精度與效率比較

五、結束語

本文針對采用傳統RANSAC算法進行基礎矩陣計算時效率較低和樣本選擇隨機性的問題，提出了一種改進RANSAC的基礎矩陣計算方法。該算法通過加入預檢驗步驟去除明顯錯誤的模型，減少了大量的無用計算，提高了算法效率。由于被標記為內點次數較多的點作為內點的概率要大于其他數據，因此，根據被標記為內點次數的多少為標準來指導后續抽樣，提高了獲得好的模型參數的概率，從而可以更好地檢測并剔除外點數據。最后在確定內點的基礎上，采用M-Estimators方法進一步提高解算精度。試驗結果表明，本文算法不僅可以有效剔除錯誤匹配點，提高基礎矩陣的計算精度，并且在魯棒性和計算效率方面也較優。

參考文獻：

[1] 宋宏權，劉學軍，閭國年，等. 地理參考下未標定圖像序列的三維點云精度分析[J]. 測繪通報，2012(7)：14-16,20.

[2] 季錚，張劍清，詹總謙. 基于序列影像和積分法的復雜物體三維重建[J]. 測繪通報，2008(1)：26-29.

[3] ARMANGUE X, SALVI J. Overall View Regarding Fundamental Matrix Estimation[J]. Image and Vision Computing，2003，21(2): 205-220.

[4] STEWART C V. MINPRAN: A New Robust Operator for Computer Vision:Application to Range Data[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1995, 17(10): 925-938.

[5] TORR P H S, ZISSERMAN A. MLESAC: A New Robust Estimator with Application to Estimating Image Geometry[J]. Computer Vision and Image Understanding, 2000, 78(1): 138-156.

[6] MATAS J, CHUM O. Randomized RANSAC withTd,dTest[J]. Image and Vision Computing, 2004, 22(10): 837-842.

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

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

[9] 劉坤，葛俊鋒，羅予頻，等. 概率引導的隨機采樣一致性算法[J]. 計算機輔助設計與圖形學學報，2009，21(5):657-662.

[10] 魯珊，雷英杰，孔韋韋，等. 基于概率抽樣一致性算法的基礎矩陣估計算法[J]. 控制與決策，2012，27(3): 425-430.