一種改進的視圖幾何基本矩陣估計法?

夏子山 王韋剛 吳 豪

（南京郵電大學電子與光學工程學院柔性電子（未來技術）學院 南京 210023）

1 引言

近年來，多視圖幾何成為計算機視覺領域的研究熱點，它關系到計算機視覺領域的許多研究，如視覺SLAM［1］、攝像機標定［2］、立體匹配［3］、目標識別與跟蹤［4］等。基本矩陣包含了兩視圖的幾何信息，準確求解基本矩陣對于視圖幾何十分重要。基本矩陣的求解通常需要利用特征提取算法得到兩視圖上的對應點，常用SIFT、SURF、FLANN等算法［5～7］。通過對應點估計基本矩陣的方法可以分為線性估計法、迭代估計法和魯棒估計法。線性估計法有線性最小二乘的八點法［8］等。文獻［9］根據基本矩陣的七個自由度，提出七點法來估計基本矩陣。若兩幅圖像之間是平移運動，文獻［10］提出用五個點估計基本矩陣。這些線性估計法是快速的，但是使用的點對較少，算法對噪聲更敏感。非線性最小二乘法［11］是經典的迭代法，但是它抵抗錯誤匹配的性能差，因為在同一場景中攝像機通過平移和旋轉變換視角拍攝照片時，會遇到遮擋或光線的變化。這會產生錯誤匹配點，導致基本矩陣估計的不準確。對此，一些研究者提出了各種抗干擾的魯棒性算法，如最大似然估計法（Maximum-likelihood Estimator，M-Estimator）和最小中值二乘法（The Least Median of Squares estimator，LmedSe）［12］和隨機抽樣一致性算法（Random Sample Consensus，RANSAC）［13］。隨機抽樣最大似然算法（Maximum Likelihood Estimation by Sample and Consensus，MLESAC）［14］是 在RANSAC 的基礎上結合了先驗條件，能有效提高檢驗準確率。這些魯棒性算法的核心思想是基于假設檢驗策略獨立地去除異常點。因為需要多次隨機抽樣測試，每個測試過程都涉及到所有數據集來區分內部值和異常值，所以它們的計算成本較高，處理速度較慢［15］。文獻［16］提出了一種快速迭代的方法，能快速剔除集合中的離群元素。文獻［17］受此啟發提出了一種通過對極約束快速迭代剔除錯誤匹配點的基本矩陣估計法，但僅僅依靠對極約束仍會保留少量非對應點。

基于上述背景，我們提出了基于梯度的離群點剔除約束算法（Outlier Screening by Gradient and Constraints，OSBGAC）估計基本矩陣，該算法首先針對含有非對應點的情況，通過基于對極約束梯度迭代來快速剔除部分非對應點。然后施加對應點相關性的約束，剔除梯度迭代無法識別的非對應點，得到最佳對應點集合去估計基本矩陣。實驗結果表明，相比于其他算法，本算法估計基本矩陣準確度有所提升。

2 對極幾何與基本矩陣的線性解

兩視圖幾何的場景如圖1 所示，點P 是三維空間中的一點，平面π′是平面π在空間中作旋轉平移變換后的另一平面。點P 在平面π和π′上的投影 點 分 別 是mi和m′i，li和li′是 對 應 點 的 極 線。對極幾何描述的是兩幅圖像之間點與線之間的關系，可以用基本矩陣來描述。對極幾何僅由攝像機和它們的相對位置、內部參數決定，而非場景結構。對應點的齊次坐標可表示為mi=(ui,vi,1)T和。則有對極約束如式（1）所示：

圖1 兩視圖幾何

式（1）也可以寫成式（2）的形式：

式中Ai是1×9 的向量，可由像素點齊次坐標的克羅 內 克 積 表 示 為Ai=(u′i,v′

i,1)?(ui,vi,1)=(uiu′i,uiv′

i,ui,viu′

i,viv′

i,vi,u′

i,v′

i,1)。f由基本矩陣F的元素構成，f=(F11,F12,F13,F21,F22,F23,F31,F32,F33)T，Fij是基本矩陣F第i行j列的元素。根據八點法可知，已知八對匹配點的情況下可以求解向量f，進而計算出基本矩陣，但圖像易受噪聲干擾使得點對存在偏差。針對這一情況，通過從多組點對估計出基本矩陣，能有效地減少誤差［18］。將一對點拓展到n對點可得到下式：

式中A=[A1;A2;…;An]。計算AT A的最小特征值所對應的特征向量即可得到向量f。

3 算法原理

3.1 基于梯度的基本矩陣估計

一般情況下最小化對極約束得到基本矩陣解的誤差很大，只有在每對點的對極約束方差相同時才能得到準確的解。為避免這種情況，可通過式（4）最小化對極約束的加權平方和去求解基本矩陣：

其中σi是每對點對極約束的方差。因為圖像上的點是由同一算法提取，每個點可以看作受到的噪聲都服從獨立的高斯分布，可由式（5）表示噪聲的協方差矩陣：

噪聲通常是未知的，可以通過一階近似得到方差的表達式：

每一項同乘常數不影響優化問題的求解，式（4）問題則可以寫成式（7）：

3.2 OSBGAC基本矩陣估計法

在理想狀態下，矩陣A對應的秩是1。在兩幅不同圖像上的對應點通常用匹配算法得出，但實際中總含有錯誤匹配的點對。錯誤的匹配點使得矩陣A的特征值均不為零，而影響求解基本矩陣的準確程度［19］。為去除不匹配點，提高基本矩陣F的求解準確度，我們提出OSBGAC算法。首先將求解F矩陣轉換為式（8）最優化問題的表達式：

式中W=diag(w1,w2,…,wn)權重矩陣用于選擇剔除異常的對應點。通過迭代求解最優矩陣W和向量f。算法初始時將全部對應點帶入計算，并將矩陣W初始值設置為單位矩陣In×n。通過計算每一對匹配點的迭代誤差εi去更新權重矩陣W。εmax是從上一輪迭代的誤差值排序后選取下五分位Q20%(εi)，δ為經驗值，則有：

由上節可知，迭代誤差εi僅依靠最小化對極約束不足以得到最優解，第i對匹配點的第n次迭代誤差表示為式（10），用來計算權重矩陣。

經上述迭代篩選匹配點后，仍存在少量符合對極約束的但并非匹配的點對。誤差通常是由圖像中的噪聲引起，導致匹配算法不穩定。一般情況下，匹配點對的誤差可分為定位誤差和離群誤差。定位誤差是指配點有少量的偏移，通常在幾個像素內。離群誤差是指特征點的錯誤匹配，點對不能成為對應點。離群點通常會帶來很大的誤差，即使只有少數點對也會嚴重降低圖像幾何估計的精度。

為盡可能地剔除離群點，提高基本矩陣估計精度，所以需要再尋找新的約束［20］。由于同一空間下的兩幅圖像之間存在旋轉平移關系，正確匹配點對的位置關系也存在一定的相關性。根據對應點的這一特征，設計篩選算法用于剔除剩余非對應點。已知點對和mi的m′齊次坐標，計算點對之間的歐式距離di：

其中點對之間連線與水平方向的夾角為

我們提出用向量ci來描述點對的關系特征。

其中n對點的關系特征矩陣可以表示為C=[c1,c2,…,cn]，進而可以由下式計算每對點特征之間的皮爾森相關系數rj,k。

式中cj,i是矩陣C中第j行i列的元素，cˉj是矩陣C第j行元素的均值。通過計算可得到的相關系數，再剔除相關性較小的點對，而保留相互相關性強的點對再次更新權重矩陣W。計算ATWA的最小特征值所對應的特征向量即可得到向量f。OSBGAC基本矩陣估計算法流程如下：

計算最后用來估計基本矩陣的匹配點的誤差，然后通過均值衡量算法的準確度。

4 實驗評估

為了驗證算法求解基本矩陣的精度，本文在四個場景下各選取兩幅圖像進行實驗。通過SURF算法取多維特征，使用K值近鄰算法匹配特征最相近的點作為對應點去估計基本矩陣。實驗硬件環境：AMD Ryzen 5 3500U，主頻2.1GHz，內存16GB。實驗軟件環境為Matlab R2018a。

圖2 中4 個子圖是室內環境下，不同視角的兩張圖片在算法各個階段篩選匹配點的過程。圖2（a）是由SURF算法初始得到的匹配點對，并圈出將其用連線連接。可以看到初始匹配點中含有大量的錯誤匹配，因為圖像不可避免受到光線變化和噪聲等影響，使匹配算法產生錯誤匹配。錯誤匹配點會嚴重影響基本矩陣計算的準確程度，需進一步處理以剔除錯誤匹配點。

圖2 場景下算法各個階段篩選匹配點

圖2（b）是經過迭代剔除誤差較大匹配點對迭代后的情況，可以看出圖2（a）中雜亂的錯誤匹配大部分被剔除，匹配點間的連線也都呈現同一方向。但仍有少部分的錯誤和與其它連線交叉的匹配點對，如書籍與電腦屏幕和水杯上下不同位置的錯誤匹配。圖2（c）是在前兩個過程剩余點對上施加點對特征的約束后得到的，可以看出錯誤的匹配點基本消除，圖片只存在少量鍵盤位置的錯誤匹配點對。再經過一次迭代篩選，圖2（d）獲取了最佳匹配點對集。

為了測試不同算法在四個場景下的性能，我們列出表1 估計基本矩陣的誤差均值和方差，同一場景中表現最好的數據已用粗體標出。所對比的算法有：本文算法OSBGAC、M-Estimator、LmedSe、RANSAC、MLESAC 和 本 文 未 加 約 束 的OSBG 算法。從表中數據可以得出，本文的迭代估計在加上匹配點約束后在每一個場景下誤差都得到了減小。場景一中本文算法性能最好，其次是LMedSe和RANSAC 算法。因為場景錯誤匹配點較多，M-Estimator 和MLESAC 算法表現并不理想。圖3場景的特征明顯，初始匹配準確度高，各算法表現都不錯，其中本文算法誤差最小。圖4 場景在光照差異影響下個算法誤差整體相比場景一和二都有增加。本文算法相比其他算法誤差最小，效果最好。MLESAC 算法與本文算法性能接近。其余算法受影響較大表現不穩定，誤差較大。圖5 場景處于強曝光環境，本文算法在此場景中性能最佳，較其他算法誤差均值至少降低20%。其次是LMedSe和MLESAC算法。

表1 四個場景下各算法表現

圖3 圖畫高相似場景

圖4 建筑晝夜場景

圖5 雕塑強曝光場景

從以上實驗結果看，M-Estimator 和RANSAC算法在有干擾的情況下表現不佳，LMedSe 和MLESAC算法表現較好，本文算法在上述四個場景中估計基本矩陣最佳。

當在場景一的圖像上分別增多添了30%、50%和70%比例的異常點時，測試各算法的魯棒性如表2 所示。異常像素點是在原有的像素上添加均值為0，方差為0.1 的高斯噪聲。從表2 中可以看出，不同情況下的同一算法性能浮動很大。這是因為噪聲嚴重影響匹配過程，錯誤匹配點會導致基本矩陣估計的誤差增大。當異常點高于50%時，M-Estimator和RANSAC算法以超過其處理能力的邊界，誤差過大。LmedSe 和MLESAC 算法在不同情況下的誤差浮動很大。本文算法表現較好，魯棒性能力最佳。

表2 異常點比例不同情況下的各算法表現

表3 是各算法在四個場景下的平均運算時間和算法復雜度。傳統算法中MLESAC 的樣本抽樣次數最多，運行時間最長，但其估計基本矩陣誤差小。其他傳統算法抽樣次數少，運行時間短，但準確度低。本文算法迭代次數少，在保證準確度的情況下運行時間較MLESAC算法下降了64.4%。

表3 算法復雜度和平均運算時間

5 結語

針對錯誤匹配點影響基本矩陣估計這一問題，本文改進了基本矩陣估計算法，并在迭代的過程中給匹配點添加新的特征約束，能有效剔除殘留錯誤匹配點。本文算法處理不同場景下的圖像與其他算法估計基本矩陣相比，有更高的準確度。對于處理帶有噪聲異常點的圖像，本文算法也具有更好的魯棒性。然而，在篩選錯誤匹配點的過程中有很多正確匹配點被剔除，使得剩余對應點都較為集中。對此，也為今后研究如何盡可能利用圖像的全局信息估計基本矩陣奠定了基礎。