基于單目視頻幀的基礎(chǔ)矩陣魯棒估計算法

鄒云龍, 楊 杰

(青島大學(xué) 機電工程學(xué)院，山東 青島 266000)

0 引 言

同一場景中的2個不同角度所拍攝的圖像，具有相應(yīng)的幾何約束關(guān)系，即対極幾何約束，在數(shù)學(xué)上用代數(shù)表示為基礎(chǔ)矩陣?；A(chǔ)矩陣在三維重建[1]、相機標(biāo)定[2]等諸多方面具有重要的地位，如何獲得精確的基礎(chǔ)矩陣，也是目前計算機視覺領(lǐng)域的研究熱點。研究者們對此提出了各種算法，目前，主要估算基礎(chǔ)矩陣的方法有魯棒法和迭代法。典型的算法有RANSAC(random sample consensus)[3]，通過隨機抽取，去除異常點，再通過內(nèi)點集估算基礎(chǔ)矩陣，具有穩(wěn)健的效果。但效率較低，尤其隨著誤匹配率的增加，計算時間也隨著大量增加。迭代法的代表有M估計法[4]，通過定義權(quán)重函數(shù)，加權(quán)迭代整個數(shù)據(jù)集，對噪聲較大的點有良好的抑制效果。但需要良好的初始值，對誤匹配率較大的數(shù)據(jù)集處理，效果較差。顏坤等人[5]將野值去除融入到計算基礎(chǔ)矩陣的過程中，從而實現(xiàn)穩(wěn)定的基礎(chǔ)矩陣估計。張永祥等人[6]提出對M估計法引入動態(tài)懲罰加權(quán)的思想，提高估計的精度，但增加了運行時間。WANG L等人[7]在M估計法上重定義加權(quán)函數(shù)來估計基礎(chǔ)矩陣。

本文基于前人的工作提出了一種新的適用于視頻的基礎(chǔ)矩陣魯棒估計算法，先確定最優(yōu)和次優(yōu)的2個子樣本集，在次優(yōu)的樣本集上RANSAC擬合模型，并對最優(yōu)子集中的測試數(shù)據(jù)進行檢測，達到閾值，則標(biāo)記為成功模型，利用成功模型對全體樣本進行檢測，能夠有效減少錯誤的模型檢測時間，成功模型的數(shù)量達到一定值，則將包含最大內(nèi)點集的基礎(chǔ)矩陣，作為初始矩陣。然后引入匹配點的分數(shù)和內(nèi)點率，作為權(quán)重因子，進行加權(quán)估計，得到待優(yōu)化矩陣。最后利用第一幀和第三幀在中間幀的兩條極線交于一點的關(guān)系，進行光束平差法優(yōu)化。

1 基礎(chǔ)矩陣與RANSAC

1.1 基礎(chǔ)矩陣

從2個不同的相機角度觀察空間中的3D點X，在2個成像平面I和I′分別成像于p和p′，并形成對極約束

p′FTp=0

(1)

式中F可以用一個秩為2，3×3的奇異矩陣表示，即基礎(chǔ)矩陣，自由度為7，至少需要7對點求解。并且不與相機內(nèi)參產(chǎn)生聯(lián)系，只與場景有關(guān)。

1.2 RANSAC

傳統(tǒng)的RANSAC算法通過大量的隨機抽樣數(shù)據(jù)點來擬合模型F，然后用F求出所有匹配點到極線的距離，與設(shè)定的閾值作比較，確定內(nèi)點集，經(jīng)過多次采樣后，得到數(shù)量最多的內(nèi)點集N，再對N進行歸一化八點算法，求出基礎(chǔ)矩陣。該方法存在一些缺陷，1)隨著誤匹配率增加，迭代次數(shù)增長過快，2)每次采樣擬合的模型，都會對所有的匹配點進行檢測，即使該模型是錯誤的，這樣將造成計算效率不高。針對這個問題，本文對此提出了新的預(yù)檢驗方法，能夠有效的減少計算時間。

1.3 新的預(yù)檢驗方法

傳統(tǒng)RANSAC每次迭代都會檢測所有內(nèi)點，當(dāng)擬合的是錯誤模型時，這樣的步驟是毫無意義的。然而可以使用少數(shù)的點去預(yù)檢測模型，便能夠有效地減少計算時間，于是如何找到這些少數(shù)點，以及確定它們的準(zhǔn)確性，又是一個需要面對的問題。

本文通過Sift匹配對的歐氏距離判斷它們的優(yōu)劣程度，并作為先驗信息。隨機測試5組真實圖像的匹配對，并按照匹配對的歐氏距離由低到高排序，采用人工判斷和算法后驗，統(tǒng)計各自前5 %匹配對的內(nèi)點率。實驗結(jié)果表明這5組的內(nèi)點率變化隨著匹配對的增加，前5 %匹配對的內(nèi)點率大都維持在70 %以上。因測試數(shù)據(jù)有限，不能代表所有圖像匹配對的前5 %內(nèi)點率均在70 %以上，依然可以作一個可行性假設(shè)。本文假設(shè)圖像匹配對的前5 %的內(nèi)點率在50 %以上，以此為前提，提出新的預(yù)檢驗方法。

首先，去除匹配距離過大以及重匹配的匹配對，然后根據(jù)匹配點的歐式距離，將匹配點由低到高排序，選取前5 %匹配點為最優(yōu)子集S1，前10 %為次優(yōu)子集S2，設(shè)置迭代次數(shù)為300，每次對S1子集隨機抽取8個點擬合模型，利用該模型對S1子集內(nèi)的匹配點由式(2)進行內(nèi)點判定，當(dāng)r小于等于閾值T時，T設(shè)為3，判定為內(nèi)點，否則為外點。統(tǒng)計當(dāng)前模型的內(nèi)點總數(shù)N，如果內(nèi)點總數(shù)N與S1集合中的數(shù)量的比值大于50 %,則將這8個點作為測試點，退出迭代。否則繼續(xù)采樣，直至達到最大迭代次數(shù)，若依然沒有得出測試點，則上述假設(shè)失敗，將測試點設(shè)為空

(2)

2 初始值計算

經(jīng)過預(yù)檢驗后，便可計算初始基礎(chǔ)矩陣，初始矩陣計算步驟如下：對子集S2進行RANSAC,迭代次數(shù)設(shè)為1 000，隨機采樣8個點，并用歸一化八點法[8]擬合模型。

1)如果預(yù)檢驗后的測試點不為空：則通過式(2)對模型用這8個測試點進行檢測，并求這8個點的平均值。當(dāng)誤差平均值大于T時，拋棄模型，繼續(xù)采樣。當(dāng)誤差均值小于等于T時，記為成功模型Fj，j為檢測內(nèi)點的次數(shù)，初始值設(shè)為0，檢測次數(shù)j加1，接著對所有匹配點進行內(nèi)點檢測，若為內(nèi)點，該匹配點被標(biāo)定為內(nèi)點的次數(shù)f加1，f初始值為0，并記下當(dāng)前擬合的Fj的內(nèi)點集的數(shù)目Nj，當(dāng)j≥10，退出循環(huán)迭代。循環(huán)結(jié)束后j大于0，則取出最大內(nèi)點集所對應(yīng)的基礎(chǔ)矩陣作為初始矩陣。否則失敗，退出程序。

2)如果預(yù)檢驗后的測試點為空：則退化為一般的RANSAC結(jié)構(gòu)，每次擬合模型，測試所有匹配點，記錄該模型對應(yīng)的內(nèi)點數(shù)，以及更新匹配對被標(biāo)記為內(nèi)點的次數(shù)f，直至達到最大迭代次數(shù)，取出擁有最大內(nèi)點數(shù)的模型，作為初始矩陣，此時檢測次數(shù)j為1 000。

3 加權(quán)估計

通過上一步驟獲得的初始矩陣，需要優(yōu)化。受文獻[10]啟發(fā)，提出改進方法，將匹配點分數(shù)和內(nèi)點率結(jié)合作為權(quán)重因子，為內(nèi)點集的匹配點分配不同的權(quán)重，對初始矩陣的內(nèi)點集進行一次加權(quán)估計,可以得到更精確的基礎(chǔ)矩陣。本文采用Sampson誤差作為最小化函數(shù)

(3)

式中wi為權(quán)重函數(shù)。對權(quán)重函數(shù)重新定義，并將匹配點的分數(shù)和內(nèi)點率引入。匹配點分數(shù)G定義如下

G=G(p,p′)=e-t,t∈[0,1]

(4)

式中t為匹配對的歸一化歐氏距離，取值范圍為[0,1]。內(nèi)點率I定義

I=f/j

(5)

式中f為該點被標(biāo)記為內(nèi)點的次數(shù)，j為擬合模型成功的總次數(shù)，最終的權(quán)重函數(shù)wi定義如下

(6)

式中r由式(2)解出，η為當(dāng)前內(nèi)點集數(shù)量占全部匹配對的百分比例，α，β，φ均為常數(shù)，α設(shè)為0.2，β設(shè)為0.8，φ,σ參照文獻[10]。

4 光束平差法優(yōu)化

(7)

式中ξ(i)為公共集中第i組特征點產(chǎn)生的殘差值。該方程依然存在一些問題，即可能會產(chǎn)生退化情形，當(dāng)兩條極線趨于重合時，該殘差方程會失效，即當(dāng)pi2與兩個極點ei12,ei32趨于共線時。為防止退化情形對優(yōu)化結(jié)果產(chǎn)生不利的影響，定義退化閾值χi

(8)

分別為極線L12，L32的斜率。最終優(yōu)化的目標(biāo)函數(shù)

(9)

5 實驗結(jié)果比較與分析

為驗證算法的魯棒性和精確性，用真實的圖像數(shù)據(jù)進行驗證，并將本算法與傳統(tǒng)算法RANSAC，LMedS[9],以及最近的ORSA[10]算法進行比較，因基礎(chǔ)矩陣不存在唯一性，相差一個常數(shù)因子下，具有等效性。采用點到對應(yīng)極線的平均距離作為評價標(biāo)準(zhǔn)，用式(10)表示，間接地反映基礎(chǔ)矩陣的估計準(zhǔn)確性。實驗平臺基于OpenCV,操作系統(tǒng)為Ubuntu

(10)

選取4個場景的視頻，包含2個室內(nèi)環(huán)境，以及2個室外環(huán)境，如圖1所示，并從每個視頻中任意截取具有重疊區(qū)域的3幀，獲得4組數(shù)據(jù)。

圖1 4組測試圖像

5.1 實驗效果

為了更加直觀地表示算法的精確度，選取其中一組，比較前2張圖像的未估計基礎(chǔ)矩陣的匹配圖，優(yōu)化后的匹配圖以及極線圖。從圖2中可以看出，經(jīng)過算法處理后的匹配點有明顯的改善，幾乎去除了所有的誤匹配點，匹配點也都落在相應(yīng)的極線上。

圖2 室內(nèi)一圖像的算法處理效果

5.2 算法比較

本文算法與RANSAC，LMedS,以及近期ORSA算法分別應(yīng)用于這4個場景，比較它們的平均差，及其標(biāo)準(zhǔn)差。本文算法計算了2個基礎(chǔ)矩陣，因篇幅有限，取前2幀的基礎(chǔ)矩陣作為比較對象。表1中mea代表平均值，std代表標(biāo)準(zhǔn)差，斜杠/表示數(shù)據(jù)過大。Proposed為本文算法。從表中看出本文算法相比先進算法ORSA，大致相當(dāng)，在室外一的數(shù)據(jù)上的表現(xiàn)甚至超過該算法，而LMedS在室外一的數(shù)據(jù)上表現(xiàn)很差，因為這組數(shù)據(jù)的誤匹配率超過50 %，相對而言傳統(tǒng)RANSAC雖然總體上不如LMedS算法，但當(dāng)數(shù)據(jù)誤匹配率較大時，RANSAC比LMedS更魯棒，而本文算法在誤匹配率較大的數(shù)據(jù)上依然有較好的表現(xiàn)。

表1 算法精度比較 像素

6 結(jié) 論

本文提出了一種適用于視頻幀的基礎(chǔ)矩陣魯棒估計算法，使用新的預(yù)檢驗方法減少了傳統(tǒng)RANSAC的計算時間，并將匹配點的分數(shù)和內(nèi)點率結(jié)合，作為權(quán)重因子，對內(nèi)點集加權(quán)估計，并利用對極轉(zhuǎn)移構(gòu)建殘差方程，然后利用光束平差法進行優(yōu)化，在不同的真實圖像數(shù)據(jù)上，相比以前算法，均有不錯的提升。本文算法依然有些許不足，假設(shè)全部匹配點前5%的內(nèi)點率超過50%的情況，在某些數(shù)據(jù)上，存在失敗的可能，導(dǎo)致預(yù)檢驗失效。另外使用光束平差法優(yōu)化，也會稍微增加計算時間，因此，提高算法的精度和計算效率，依然是下一個研究方向。