一種估計基礎矩陣的新魯棒算法

甄艷，劉學軍，王美珍

（南京師范大學地理科學學院，南京師范大學虛擬地理環(huán)境教育部重點實驗室，江蘇 南京 210046）

從兩個不同視點處獲得的同一場景的兩幅圖像間存在著一定的約束關系，即對極幾何關系。對極幾何獨立于場景結(jié)構(gòu)，是在非標定情況下可以從圖像中獲得的唯一信息，包括攝像機所有的內(nèi)部參數(shù)和外部參數(shù)信息?；A矩陣是對極幾何關系的代數(shù)表示，它的準確求解是三維重建［1］、運動估計、相機自標定［2］、匹配及跟蹤的基礎［3］。

由于在特征點的提取與匹配過程中，不可避免的含有噪聲和outliers（粗差數(shù)據(jù)或異常數(shù)據(jù)）［4］，因此，利用圖像間對應點進行基礎矩陣估計，其精度總會受到影響。雖然人們已經(jīng)在如何精確、魯棒地估計基礎矩陣方面做了大量的研究，但是至今沒有一種估算方法可以完全消除誤匹配及噪聲對估算精度的影響，因此，準確求解基礎矩陣仍然是計算機視覺中的難點之一。本文基于RANSAC方法的隨機抽樣思想，提出了一種估計基礎矩陣的新魯棒算法，以便準確反映對極幾何關系，進而提高三維重建的質(zhì)量。

1 對極幾何與基礎矩陣

如圖1所示，假設C和C′分別為兩個攝像機的光心，兩個攝像機拍攝獲得的圖像分別為I和I′，m和m′是三維空間點M 在兩幅圖像上的投影點，空間點M和兩個攝像機的光心C和C′所在的平面用π表示，該平面稱為對極平面（Epipolar Plane）。對極平面π與兩個圖像平面I和I′的交線分別為l和l′，這兩條交線稱為極線（Epipolar Line），則點m的對應點m′必然在m的對極線l上，反之亦然。

圖1 對極幾何Fig.1 Epipolar geometry

目前，利用圖像間對應點估算基礎矩陣的方法主要可分為3類：線性方法、迭代方法和魯棒方法［5］。線性方法計算速度快，復雜度低，對噪聲和錯誤數(shù)據(jù)非常敏感，主要有7點法［6，7］和8點法［8－10］；迭代方法［11，12］精度比線性方法高，但計算時間長，并且不能處理錯誤匹配點；當匹配點集中出現(xiàn)錯誤匹配時，線性方法和迭代方法不再適用，而魯棒方法可以解決這類問題，如最小中值法（Least Median Squares，LMedS）［6］、隨機抽樣一致性法（Random Sample Consensus，RANSAC）［13］以及 M 估計算法（M－Estimator Sample Consensus，M－Estimators）［14］。魯棒方法的特點是對噪聲和錯誤匹配都有更好的魯棒性，但每種魯棒方法都有其自身的局限性，如MEstimators方法對初始值依賴較大，受錯誤數(shù)據(jù)影響較大；LMedS方法對outliers的魯棒性較好，但當原始匹配點集合中錯誤數(shù)據(jù)率接近50%時，該方法的誤差很大［6］；RANSAC方法是計算機視覺中關于魯棒參數(shù)估計的一個典型方法，應用較為廣泛，錯誤數(shù)據(jù)超過50%時仍能獲得較好的結(jié)果，但在某些情況下，容易陷入局部最小。另外，胡明星等［15，16］將遺傳算法引入基礎矩陣的估計方法中，可在一定程度上提高求解的精度，但遺傳算法計算復雜，使得整體算法的復雜度較高。

2 內(nèi)點集及基礎矩陣估計

從現(xiàn)有研究看，目前沒有一種方法可以做到完全消除噪聲和錯誤匹配對基礎矩陣估計的影響，提高基礎矩陣估算精度的關鍵是獲得一個好的內(nèi)點集，在該內(nèi)點集中應盡可能少的包含誤差點。解決這一問題的一個可行方法是在一個好的初始內(nèi)點集的基礎上，采用魯棒擴充算法［17］，對初始內(nèi)點集進行擴充獲得一個較優(yōu)內(nèi)點，基于該較優(yōu)內(nèi)點集，重新估計基礎矩陣獲得較優(yōu)的解算結(jié)果。

2.1 內(nèi)點集定義

本文提出一種獲取內(nèi)點集的新方法，首先選擇被標記為內(nèi)點次數(shù)與抽樣次數(shù)相同的點，即選擇在每次抽樣過程中都被判定為內(nèi)點的這部分點（當這部分點的數(shù)量小于8時，選擇被標記為內(nèi)點次數(shù)最多的前8對匹配點）構(gòu)成初始集合。盡管初始集合中點的概率基本可達到100%的內(nèi)點，但由于RANSAC方法在判斷是否為內(nèi)點這一問題的解決方案是通過設定一個閾值確定的。因此，從理論上并不能保證初始集合中的點全部是內(nèi)點，只是使初始集合中盡可能多的由內(nèi)點構(gòu)成。為進一步提高精度，在魯棒擴充過程中，采用C－Step方法［17］對當前集合進行調(diào)整。

圖2 點到極線的對極距離Fig.2 Epipolar distance from point to epipolar line

內(nèi)點集B的擴充過程可以用數(shù)學模型表示為：

2.2 內(nèi)點集獲取

初始內(nèi)點集性能的好壞直接決定了最終獲得內(nèi)點集的質(zhì)量，本文方法在每次抽樣判斷的過程中標記出每對匹配點是否為內(nèi)點，完成多次抽樣后，最后統(tǒng)計每個點被判定為內(nèi)點的次數(shù)。選擇次數(shù)較多的匹配點構(gòu)成初始集合，采用魯棒擴充方法對初始內(nèi)點集進行擴充獲得一個較優(yōu)內(nèi)點集。

設初始集合用Sj表示，采用魯棒擴充方法，以點的對極距離和作為判斷準則對初始子集進行擴充。在初始集合Sj的基礎上，需要對匹配點集中剩余的匹配點進行考核。在每次考核過程中，首先將當前被考核匹配點添加到集合Sj中生成新的集合Sj＋1，然后利用Sj＋1計算基礎矩陣Fsj＋1，并計算目標函數(shù)值Z（FSj＋1）。如果目標函數(shù)值Z（FSj＋1）＜Z（FSj），說明當前被考核匹配點可以接受，并采用C－Step方法對當前的內(nèi)點集進行調(diào)整，否則該匹配點需要從集合Sj＋1中刪除，進而判斷下一個匹配點。

2.3 基礎矩陣估計

針對傳統(tǒng)RANSAC算法獲得的基礎矩陣并不一定就是最優(yōu)解這一問題，本文提出了一種估計基礎矩陣的新魯棒算法。基本原理是：在每次抽樣過程中記錄每個點是否被判定為內(nèi)點，完成多次抽樣后，統(tǒng)計每對匹配點被標記為內(nèi)點的次數(shù)，并降序排列。選擇內(nèi)點次數(shù)與抽樣次數(shù)相同的點（若這部分點的數(shù)量小于8，則選擇被標記為內(nèi)點次數(shù)最多的前8對匹配點）構(gòu)成初始集合。在多次抽樣的內(nèi)點判定過程中，如果該點被認為是內(nèi)點的次數(shù)較多，那么從概率上講，它為內(nèi)點的可能性也應較大，因此，在初始集合的構(gòu)成時，就保證了盡可能多的選擇內(nèi)點。在初始內(nèi)點集的基礎上，采用魯棒擴充算法，以點到極線的對極距離和作為擴充準則，對初始內(nèi)點集進行擴充。為了提高算法的魯棒性與解算精度，在每一次迭代擴充過程中，若有滿足約束條件的點添加到當前集合，則需要采用C－Step方法對當前內(nèi)點集進行調(diào)整優(yōu)化。最后根據(jù)獲得的內(nèi)點集估計基礎矩陣，整個流程如圖3所示。

圖3 基礎矩陣估計流程Fig.3 Flowchart of the fundamental matrix estimation

3 實驗結(jié)果與分析

3.1 實驗設計

為了驗證本文算法的有效性和魯棒性，通過對模擬數(shù)據(jù)和文獻［17］中的真實圖像數(shù)據(jù)進行實驗，將本文的算法與現(xiàn)有主要的魯棒方法RANSAC、LMedS和M－Estimators進行比較，以平均對極距離作為算法的評價標準。

模擬數(shù)據(jù)的生成：采用程序生成模擬同一場景不同視角的兩幅圖像的100對匹配點。模擬數(shù)據(jù)實驗部分從兩個不同的角度進行：1）分別添加不同強度的高斯噪聲。為了模擬真實圖像特征點提取與匹配的效果，在模擬數(shù)據(jù)中，添加20%的外點數(shù)據(jù)。2）驗證在不同外點比率下算法的精度。為盡量模擬真實圖像特征點匹配效果，在模擬數(shù)據(jù)中分別為每對匹配點疊加均值為0、方差為1的高斯噪聲。

另外，由于本文算法以傳統(tǒng)的RANSAC算法的抽樣思想為基礎，結(jié)合魯棒擴充方法，將尋求內(nèi)點集的過程分為多個階段完成，在每次擴充過程中，算法都希望添加到內(nèi)點集中的點能夠優(yōu)化計算結(jié)果。因此，在整個尋優(yōu)過程中，一方面可以提高算法的精度和魯棒性，另一方面，卻增加了時間上的開銷，降低了求解的效率。為了比較算法的效率，本文給出了幾種算法的時間比較。

3.2 結(jié)果分析

（1）模擬數(shù)據(jù)實驗結(jié)果。圖4為匹配點在不同噪聲誤差下4種算法計算精度的比較，圖5給出了在不同外點比率下不同算法計算精度的比較。

通過實驗結(jié)果可以看出，與其它3種方法相比，本文算法精度最高。圖4中，當匹配點集中包含不同強度的高斯噪聲時，LMedS與RANSAC算法的精度相當，但隨著噪聲增強，RANSAC算法的精度略優(yōu)于LMedS方法，M－Estimators算法的精度最差，這主要是由于M－Estimators方法的結(jié)果依賴于由線性方法估算得到的初始值，而隨著誤差的增大，由線性算法估算得到的結(jié)果精度較差，這導致 MEstimators方法的精度也隨之降低。通過圖5可以看出，隨著外點率的增加，本文的算法一直都能保持較高的精度，具有較好的魯棒性，當外點率超過40%時，其它3種算法的精度都有較大幅度的降低，外點率接近50%時，LMedS方法的精度迅速降低。

（2）真實圖像實驗結(jié)果。由于篇幅所限，在此以2幅真實圖像為例，圖像1包含99對匹配點，圖像2包含156對匹配點，4種方法的精度及魯棒性比較結(jié)果如表1所示，圖6為通過本文算法提取的部分對極線。從表1和圖6真實圖像的實驗結(jié)果看，本文提出的方法對基礎矩陣的估計精度和穩(wěn)定性均優(yōu)于其它3種方法。

表1 真實圖像的精度及魯棒性比較Table 1 The precision and robustness of different methods with real images

圖6 2幅真實圖像通過本文算法提取的部分對極線Fig.6 Part of the epipolar lines of the real images by the proposed algorithm

（3）計算時間比較。為了驗證本文算法的效率，以2幅真實圖像為例，本文分別計算了包含不同匹配點數(shù)量時4種算法各自所需的計算時間，圖7為4種算法計算效率的比較結(jié)果。

圖7 不同匹配點數(shù)量下4種算法所需計算時間Fig.7 Comparing the computing time of 4 methods

本文算法最大的不足在于提高解算精度和魯棒性的同時，降低了求解的效率，增加了計算時間。在魯棒擴充過程中，始終需要滿足目標函數(shù)值保持最小這一約束條件，通過保證局部的最優(yōu)實現(xiàn)整體最優(yōu)。從圖7可知，M－Estimators方法的效率最高，其次是RANSAC方法和LMedS方法。與其它3種魯棒方法相比，盡管本文方法的效率相對較低，但在保證解算精度的前提下，可考慮引入并行技術及優(yōu)化方法對其進行改進。

4 結(jié)論

本文針對傳統(tǒng)RANSAC方法估計基礎矩陣獲得的解并不是最優(yōu)解的問題，提出了一種估計基礎矩陣的新魯棒方法。本文方法在多次抽樣過程中，通過記錄每對匹配點被判定為內(nèi)點的次數(shù)來確定初始集合，然后采用魯棒擴充方法獲得內(nèi)點集。從初始集合的選取開始就保證了算法的精度，內(nèi)點集的確定是經(jīng)過在擴充過程中各階段的局部最優(yōu)選擇實現(xiàn)最后的整體最優(yōu)得到的。實驗結(jié)果表明，本文方法對特征點的匹配精度沒有特殊的要求，能有效剔除錯誤匹配點，適用于錯誤數(shù)據(jù)率和高斯噪聲較大的情況，其解算結(jié)果的精度和魯棒性均優(yōu)于現(xiàn)有的魯棒方法。本文算法的不足之處在于整個擴充過程中增加了計算時間上的開銷，下一步工作將進一步研究如何在保持計算精度的前提下，盡可能提高算法的計算效率。

［1］ 鄭順義，張祖勛，翟瑞芳.基于非量測相機的復雜物體三維重建［J］.武漢大學學報（信息科學版），2008，33（5）：446－449.

［2］ 盧玥，劉學軍，王美珍，等.基于數(shù)位的相機徑向畸變參數(shù)計算［J］.地理與地理信息科學，2011，27（6）：18－22.

［3］ 孫鳳梅，胡占義.攝像機簡化模型對三維重構(gòu)的影響——分析與實驗［J］.計算機輔助設計與圖形學學報，2005，17（10）：2257－2262.

［4］ BRANDT S.Maximum likelihood robust regression with known and unknown residual models［A］.Proceedings of the ECCV 2002［C］.Copenhagen，Denmark，2002.97－102.

［5］ XAVIER A，JOAQUIM S.Overall view regarding fundamental matrix estimation［J］.Image and Vision Computing，2003，21：205－220.

［6］ ZHANG Z.Determining the epipolar geometry and its uncertainty：A review［J］.International Journal of Computer Vision，1998，27（2）：161－195.

［7］ 鐘慧湘，龐云龍，馮月萍.估計基礎矩陣的一個新方法［J］.儀器儀表學報，2005，25（4）：411－413.

［8］ LONGUET－HIGGINS H C.A computer algorithm for reconstructing a scene from two projections［J］.Nature，1981（293）：133－135.

［9］ HARTLEY R I.In defence of the 8－point algorithm［A］.Pro－ceedings of the International Conference on Computer Vision，IEEE Computer Society Press［C］.Boston，1995.1064－1070.

［10］ WU F C，HU Z Y，DUAN F Q.8－point algorithm revisited：Factorized 8－point algorithm［A］.IEEE Int.Conf.on Computer Vision［C］.2005.

［11］ ZHANG Z，DERICHE R，F(xiàn)AUGERAS O，et al.A robust technique for matching two uncalibrated images through the recovery of the unknown epipolar geometry［J］.Artificial Intelligence，1995，78（10）：87－119.

［12］ LUONG Q－T，F(xiàn)AUGERAS O D.The fundamental matrix：Theory，algorithms and stability analysis［J］.International Journal of Computer Vision，1996，1（17）：43－76.

［13］ ONDREJ C，TOMAS W，JIRI M.Epipolar geometry estimation via RANSAC benefits from the oriented epipolar constraint［A］.Proceedings of the 17th International Conference on Pattern Recognition［C］.Los Alamitos，2004.112－115.

［14］ TORR P H S，MURRAY D W.The development and comparison of robust methods for estimating the fundamental matrix［J］.International Journal of Computer Vision，1997，24（3）：271－300.

［15］ 胡明星，袁保宗，唐曉芳.基于混合遺傳算法的對極幾何估計［J］.電子學報，2003，31（10）：1481－1485.

［16］ TANG C Y，WU Y.Fundamental matrix estimation using evolutionary algorithm with multi－objective functions［J］.Information Science and Engineering，2008，24：785－800.

［17］ 胡玉鎖，陳宗海.一種新的基于線性EIV模型的魯棒估計算法［J］.計算機研究與發(fā)展，2006，43（3）：483－488.