李 兵，邱儒瓊,2

（1.湖北省基礎(chǔ)地理信息中心，湖北 武漢 430074；2.中國地質(zhì)大學(xué)（武漢），湖北 武漢430073）

一種分塊的基礎(chǔ)矩陣魯棒計(jì)算方法

李 兵1，邱儒瓊1,2

（1.湖北省基礎(chǔ)地理信息中心，湖北 武漢 430074；2.中國地質(zhì)大學(xué)（武漢），湖北 武漢430073）

針對基礎(chǔ)矩陣計(jì)算過程存在異常數(shù)據(jù)的問題，提出了一種新的匹配點(diǎn)分塊的基礎(chǔ)矩陣魯棒計(jì)算方法。該方法首先對特征點(diǎn)集進(jìn)行分塊處理，然后以點(diǎn)到基線的距離為最優(yōu)化準(zhǔn)則獲得較為準(zhǔn)確的特征點(diǎn)匹配集，最后以8點(diǎn)算法獲得結(jié)果值。實(shí)驗(yàn)表明，設(shè)計(jì)的算法切實(shí)可行，對特征點(diǎn)錯誤匹配所造成的誤差影響有較大的壓制效果。

計(jì)算機(jī)視覺；極線幾何；基礎(chǔ)矩陣；魯棒估計(jì)法

從二維影像中獲取所拍攝場景的三維信息是攝影測量與計(jì)算機(jī)視覺等學(xué)科研究的熱點(diǎn)內(nèi)容之一[1]。對于某個場景的單幅影像，通常無法簡單地從中獲得所拍攝場景三維信息。為了獲得場景中的三維信息，傳統(tǒng)的方法是采用2個相機(jī)組成的立體視覺系統(tǒng)，或者使用單個相機(jī)從不同角度拍攝同一場景2次以上，才有可能達(dá)到目的。在無其他場景先驗(yàn)知識或者相機(jī)運(yùn)行信息的情況下，2幅影像是通過極線幾何關(guān)系來關(guān)聯(lián)的，它的代數(shù)表示就是基礎(chǔ)矩陣[2]。基礎(chǔ)矩陣以一種簡潔的方式將同一場景的2幅影像關(guān)聯(lián)起來，它的精確計(jì)算問題是計(jì)算機(jī)視覺領(lǐng)域中的一個重要問題，也在其他的學(xué)科領(lǐng)域中廣泛應(yīng)用[3-6]。

目前，針對基礎(chǔ)矩陣常用的計(jì)算方法可以分為線性方法、迭代方法和魯棒方法[7]。其中，線性方法計(jì)算速度最快，但由于它在計(jì)算過程中忽略參數(shù)間的約束關(guān)系并且其最小化準(zhǔn)則缺乏物理意義，因此估計(jì)精度較差。迭代方法所獲得的計(jì)算精度較高，但計(jì)算時間相對較長，且不能消除特征點(diǎn)錯誤匹配所造成的影響。為此，許多學(xué)者引入統(tǒng)計(jì)學(xué)中的魯棒回歸分析理論，提出了一些估計(jì)基礎(chǔ)矩陣的魯棒方法，如RANSAC方法[8]、M-estimators方法和最小平方中值（LMeds）方法[9]等。

由于魯棒方法能夠有效地抑制異常數(shù)據(jù)的影響，因此得到了更加廣泛的應(yīng)用。針對原始匹配點(diǎn)對基礎(chǔ)矩陣的不同影響，本文改進(jìn)了經(jīng)典算法，提出了一種新的魯棒算法，其基本思想就是利用分塊的策略進(jìn)行抽樣，然后以點(diǎn)到極線的距離最小為最優(yōu)化準(zhǔn)則得到誤差相對較小的內(nèi)點(diǎn)集，最后以分塊基礎(chǔ)矩陣的魯棒擴(kuò)充算法獲得最終結(jié)果。

1 數(shù)學(xué)模型

1.1 基于分塊的隨機(jī)抽樣策略

如圖1所示。首先量測出所有待匹配點(diǎn)的平面坐標(biāo)，并獲得坐標(biāo)值中的最大值和最小值，然后由最大值與最小值把第一幅圖像中的匹配點(diǎn)劃分成b×b塊。各個塊中若有匹配點(diǎn)則保留，若沒有則剔除掉。為了獲得8個點(diǎn)的子樣本，在第一幅影像上隨機(jī)抽取互不相同的8個數(shù)據(jù)塊。其后在每塊中隨機(jī)抽出1個匹配點(diǎn)，從8個數(shù)據(jù)塊中共得到8對分布比較均勻的匹配點(diǎn)，用這樣的8對匹配點(diǎn)計(jì)算基礎(chǔ)矩陣相對來說較為穩(wěn)定。

圖1 數(shù)據(jù)分塊示意圖

在理想情況下，錯誤匹配在空間中均勻分布，每塊中有相同數(shù)目的匹配點(diǎn)且隨機(jī)抽取是均勻分布的。但實(shí)際情況中卻并非如此。某一塊中的匹配點(diǎn)數(shù)目和另一塊中的匹配點(diǎn)數(shù)目可能并不一致。所以，一個在含有較少匹配點(diǎn)的塊里，匹配點(diǎn)被抽取的概率要比在含有很多匹配點(diǎn)的塊里大得多。為了讓所有的匹配點(diǎn)被抽取的概率盡量相同，本文采取一種新的策略來保證隨機(jī)采樣的均勻性，具體方法如下：

假設(shè)一共有l(wèi)個特征點(diǎn)塊，將數(shù)值區(qū)間[0,1]分成l個間隔，并設(shè)定第i個間隔的寬度等于其中ni為第i個塊中的匹配點(diǎn)個數(shù)。在數(shù)據(jù)塊的隨機(jī)抽取中，如果產(chǎn)生的一個0～1的隨機(jī)數(shù)落在第i個間隔上，那么第i個塊就認(rèn)為被選中了。由此，可以保證匹配點(diǎn)隨機(jī)抽樣的均勻性，用該策略代替普通的隨機(jī)采樣去獲得特征點(diǎn)子集，計(jì)算得到基礎(chǔ)矩陣的結(jié)果會比較穩(wěn)定和準(zhǔn)確，如圖2。

圖2 分塊抽取原理

1.2 錯誤匹配點(diǎn)剔除

要進(jìn)行基礎(chǔ)矩陣的估計(jì)，首先要剔除誤差較大的匹配點(diǎn)?；诟倪M(jìn)的最小平方中值算法獲得內(nèi)點(diǎn)集的思路如下：

首先，利用上一節(jié)介紹的特征點(diǎn)分塊隨機(jī)抽樣策略進(jìn)行多次隨機(jī)采樣以獲得多個子樣本，并采用改進(jìn)的8點(diǎn)線性算法估計(jì)基礎(chǔ)矩陣的近似值，并作為后續(xù)迭代運(yùn)算的初始值。

然后，計(jì)算所有匹配點(diǎn)的對極距離，并把對極距離（計(jì)算方法如式（1）所示）作為匹配點(diǎn)的誤差值。由于誤差受很多因素的影響，可以假定它是服從高斯分布的，即99.87%的誤差分布在3σ（σ是均方差）以內(nèi)，把誤差大于3 σ的匹配點(diǎn)作為異常匹配點(diǎn)，并把它們剔除掉，得到一組新的匹配點(diǎn)。

最后，用這組新的匹配點(diǎn)計(jì)算基礎(chǔ)矩陣新的近似值，并一直循環(huán)下去，直到相鄰2個基本矩陣的近似值偏差小于一定的閾值或循環(huán)已經(jīng)達(dá)到一定的次數(shù)。那么，去除異常數(shù)據(jù)點(diǎn)后得到的點(diǎn)集就認(rèn)為是內(nèi)點(diǎn)集。

1.3 基于分塊基礎(chǔ)矩陣的魯棒擴(kuò)充算法

對原始匹配點(diǎn)進(jìn)行異常點(diǎn)剔除操作后，可以獲得一個誤差相對比較小的內(nèi)點(diǎn)集。但是，用該內(nèi)點(diǎn)集中的匹配點(diǎn)去求解基礎(chǔ)矩陣所得到的結(jié)果，很有可能并不是最優(yōu)解，其原因主要有以下2點(diǎn)：

1）內(nèi)點(diǎn)集中每個特征點(diǎn)的誤差并不完全相同，用誤差較小的部分特征點(diǎn)去求解基礎(chǔ)矩陣，所獲得結(jié)果的精度肯定要高于用內(nèi)點(diǎn)集中所有匹配點(diǎn)計(jì)算獲得的結(jié)果。

2）最小二乘法的最優(yōu)化準(zhǔn)則是通過極小化由特征點(diǎn)坐標(biāo)構(gòu)成的系數(shù)方程而進(jìn)行迭代計(jì)算的。但是，這種極小化的原理沒有具體的物理意義，其計(jì)算獲得的解不能代表真正的最優(yōu)解。

所以，如果能夠在內(nèi)點(diǎn)集中獲得誤差比較小的部分子集，那么該子集可以稱之為最優(yōu)子集。同時，由該子集按照具有實(shí)際物理意義的最優(yōu)化準(zhǔn)則進(jìn)行計(jì)算所獲得結(jié)果就可以解決上述兩個問題，認(rèn)為是最優(yōu)解。

1.4 算法流程

具體的算法步驟可以分為以下5步，如圖3所示。

圖3 算法流程圖

1）獲得特征點(diǎn)的內(nèi)點(diǎn)集合。

2）獲得基礎(chǔ)矩陣的當(dāng)前近似值所對應(yīng)的8個匹配點(diǎn)為初始子集,用其中的元素計(jì)算基礎(chǔ)矩陣以及點(diǎn)到極線的距離平方總和。

3）下述過程重復(fù)N-8次（N是特征點(diǎn)的個數(shù)，減去8是因?yàn)殚_始已經(jīng)選取了8個特征點(diǎn)）。①從集合S中取出一對不存在的匹配點(diǎn)，加入其中形成新的子集，并計(jì)算和；②若是則接受該匹配點(diǎn)，否則剔除該匹配點(diǎn)。

4）對子集進(jìn)行優(yōu)化調(diào)整。

5）使用該最優(yōu)子集并采用8點(diǎn)算法計(jì)算出基礎(chǔ)矩陣的最終值。

2 實(shí)驗(yàn)與結(jié)論

如圖4所示，使用走廊立體像對影像作為實(shí)驗(yàn)數(shù)據(jù)來驗(yàn)證本文的算法。圖中畫出了由本文算法得到的部分極線，表1以平均余差和平均對極距離指標(biāo)為評價依據(jù)，分別列出了改進(jìn)的8點(diǎn)算法、LMedS算法以及本文算法的計(jì)算結(jié)果?？紤]到誤差的隨機(jī)性，對圖4的影像進(jìn)行了多次實(shí)驗(yàn)，每次選取不同數(shù)目的匹配點(diǎn)，以多次計(jì)算結(jié)果的平均值作為最終結(jié)果進(jìn)行比較。

從表1可以看出，改進(jìn)的8點(diǎn)算法由于難以應(yīng)對錯誤匹配點(diǎn)的影響，所以計(jì)算獲得的誤差較大，由此得出的基礎(chǔ)矩陣結(jié)果值不可靠。LMedS算法去掉了絕大部分的錯誤匹配點(diǎn)，計(jì)算得到的精度明顯比改進(jìn)的8點(diǎn)算法好。但是，由于LMedS算法在去掉部分匹配點(diǎn)后，剩余的匹配點(diǎn)所采用的計(jì)算策略相同，沒有區(qū)分它們的誤差大小而統(tǒng)一地進(jìn)行計(jì)算，所以得到的結(jié)果并不是最優(yōu)的。而本文算法依據(jù)其誤差大小運(yùn)用擴(kuò)充模型在內(nèi)點(diǎn)集中選取最優(yōu)子集后再進(jìn)行計(jì)算，所以獲得的基礎(chǔ)矩陣結(jié)果精度最高，偏差最小。

表1 3種不同算法的結(jié)果

圖4 走廊的立體像對

[1] Hartley R, Zisserman A, Ebrary I. Multiple View Geometry in Computer Vision [M]. Cambridge Univ Press, 2003

[2] Armangu X, SalvI J. Overall View Regarding Fundamental Matrix Estimation [J]. Image and Vision Computing, 2003, 21(2): 205-214

[3] 徐巧玉, 葉東, 車仁生. 基于光學(xué)參考棒的立體視覺測量系統(tǒng)現(xiàn)場標(biāo)定技術(shù)[J]. 光學(xué)學(xué)報(bào), 2008, 28(1): 81-86

[4] 徐巧玉,車仁生. 基于光學(xué)測棒的立體視覺坐標(biāo)測量系統(tǒng)的研究[J]. 光學(xué)學(xué)報(bào), 2008, 28(11): 2 181-2 186

[5] 張旭蘋, 汪家其, 張益昕， 等. 大尺度三維幾何尺寸立體視覺測量系統(tǒng)實(shí)現(xiàn)[J]. 光學(xué)學(xué)報(bào), 2012, 32(3):148-155

[6] 丁雅斌, 彭翔, 田勁東， 等. 一種三維數(shù)字成像系統(tǒng)的多視點(diǎn)姿態(tài)估計(jì)方法[J]. 光學(xué)學(xué)報(bào), 2007, 27(3): 451-456

[7] Zhang Z. Determining the Epipolar Geometry and Its Uncertainty: A Review[J]. International Journal of Computer Vision, 1998, 27(2): 161-195

[8] Fischler M A, Bolles R C. Random Sample Consensus: a Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J]. Communications of the ACM, 1981, 24(6): 381-395

[9] 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

P231.5

B

1672-4623（2015）01-0012-02

10.3969/j.issn.1672-4623.2015.01.004

李兵，正高職高級工程師，現(xiàn)主要從事地理信息系統(tǒng)等科研和應(yīng)用方面的工作。

2014-05-26。

項(xiàng)目來源：數(shù)字制圖與國土信息應(yīng)用工程國家測繪地理信息局重點(diǎn)實(shí)驗(yàn)室開放研究基金資助項(xiàng)目（GCWD201204）。