甄艷，劉學(xué)軍，王美珍

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

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

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

1 對極幾何與基礎(chǔ)矩陣

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

圖1 對極幾何Fig.1 Epipolar geometry

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

2 內(nèi)點(diǎn)集及基礎(chǔ)矩陣估計(jì)

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

2.1 內(nèi)點(diǎn)集定義

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

圖2 點(diǎn)到極線的對極距離Fig.2 Epipolar distance from point to epipolar line

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

2.2 內(nèi)點(diǎn)集獲取

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

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

2.3 基礎(chǔ)矩陣估計(jì)

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

圖3 基礎(chǔ)矩陣估計(jì)流程Fig.3 Flowchart of the fundamental matrix estimation

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

3.2 結(jié)果分析

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

［3］ 孫鳳梅，胡占義.攝像機(jī)簡化模型對三維重構(gòu)的影響——分析與實(shí)驗(yàn)［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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ì)基礎(chǔ)矩陣的一個(gè)新方法［J］.儀器儀表學(xué)報(bào)，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ì)［J］.電子學(xué)報(bào)，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ì)算法［J］.計(jì)算機(jī)研究與發(fā)展，2006，43（3）：483－488.