李 兵，邱儒瓊,2

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

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

李 兵1，邱儒瓊1,2

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

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

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

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

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

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

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

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

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

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

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

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

圖2 分塊抽取原理

1.2 錯誤匹配點剔除

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

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

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

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

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

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

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

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

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

1.4 算法流程

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

圖3 算法流程圖

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

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

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

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

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

2 實驗與結(jié)論

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

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

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

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

[6] 丁雅斌, 彭翔, 田勁東， 等. 一種三維數(shù)字成像系統(tǒng)的多視點姿態(tài)估計方法[J]. 光學(xué)學(xué)報, 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。

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