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

鄒云龍, 楊 杰

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

0 引 言

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

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

1 基礎矩陣與RANSAC

1.1 基礎矩陣

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

p′FTp=0

(1)

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

1.2 RANSAC

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

1.3 新的預檢驗方法

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

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

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

(2)

2 初始值計算

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

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

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

3 加權估計

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

(3)

式中wi為權重函數。對權重函數重新定義，并將匹配點的分數和內點率引入。匹配點分數G定義如下

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

(4)

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

I=f/j

(5)

式中f為該點被標記為內點的次數，j為擬合模型成功的總次數，最終的權重函數wi定義如下

(6)

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

4 光束平差法優化

(7)

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

(8)

分別為極線L12，L32的斜率。最終優化的目標函數

(9)

5 實驗結果比較與分析

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

(10)

選取4個場景的視頻，包含2個室內環境，以及2個室外環境，如圖1所示，并從每個視頻中任意截取具有重疊區域的3幀，獲得4組數據。

圖1 4組測試圖像

5.1 實驗效果

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

圖2 室內一圖像的算法處理效果

5.2 算法比較

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

表1 算法精度比較 像素

6 結 論

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