鄒云龍, 楊 杰

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

0 引 言

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

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

1 基礎(chǔ)矩陣與RANSAC

1.1 基礎(chǔ)矩陣

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

p′FTp=0

(1)

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

1.2 RANSAC

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

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

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

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

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

(2)

2 初始值計算

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

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

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

3 加權(quán)估計

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

(3)

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

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

(4)

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

I=f/j

(5)

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

(6)

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

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

(7)

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

(8)

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

(9)

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

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

為了更加直觀地表示算法的精確度，選取其中一組，比較前2張圖像的未估計基礎(chǔ)矩陣的匹配圖，優(yōu)化后的匹配圖以及極線圖。從圖2中可以看出，經(jīng)過算法處理后的匹配點(diǎn)有明顯的改善，幾乎去除了所有的誤匹配點(diǎn)，匹配點(diǎn)也都落在相應(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為本文算法。從表中看出本文算法相比先進(jìn)算法ORSA，大致相當(dāng)，在室外一的數(shù)據(jù)上的表現(xiàn)甚至超過該算法，而LMedS在室外一的數(shù)據(jù)上表現(xiàn)很差，因?yàn)檫@組數(shù)據(jù)的誤匹配率超過50 %，相對而言傳統(tǒng)RANSAC雖然總體上不如LMedS算法，但當(dāng)數(shù)據(jù)誤匹配率較大時，RANSAC比LMedS更魯棒，而本文算法在誤匹配率較大的數(shù)據(jù)上依然有較好的表現(xiàn)。

表1 算法精度比較 像素

6 結(jié) 論

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