夏子山 王韋剛 吳 豪

（南京郵電大學(xué)電子與光學(xué)工程學(xué)院柔性電子（未來(lái)技術(shù)）學(xué)院 南京 210023）

1 引言

近年來(lái)，多視圖幾何成為計(jì)算機(jī)視覺(jué)領(lǐng)域的研究熱點(diǎn)，它關(guān)系到計(jì)算機(jī)視覺(jué)領(lǐng)域的許多研究，如視覺(jué)SLAM［1］、攝像機(jī)標(biāo)定［2］、立體匹配［3］、目標(biāo)識(shí)別與跟蹤［4］等。基本矩陣包含了兩視圖的幾何信息，準(zhǔn)確求解基本矩陣對(duì)于視圖幾何十分重要?；揪仃嚨那蠼馔ǔＰ枰锰卣魈崛∷惴ǖ玫絻梢晥D上的對(duì)應(yīng)點(diǎn)，常用SIFT、SURF、FLANN等算法［5～7］。通過(guò)對(duì)應(yīng)點(diǎn)估計(jì)基本矩陣的方法可以分為線性估計(jì)法、迭代估計(jì)法和魯棒估計(jì)法。線性估計(jì)法有線性最小二乘的八點(diǎn)法［8］等。文獻(xiàn)［9］根據(jù)基本矩陣的七個(gè)自由度，提出七點(diǎn)法來(lái)估計(jì)基本矩陣。若兩幅圖像之間是平移運(yùn)動(dòng)，文獻(xiàn)［10］提出用五個(gè)點(diǎn)估計(jì)基本矩陣。這些線性估計(jì)法是快速的，但是使用的點(diǎn)對(duì)較少，算法對(duì)噪聲更敏感。非線性最小二乘法［11］是經(jīng)典的迭代法，但是它抵抗錯(cuò)誤匹配的性能差，因?yàn)樵谕粓?chǎng)景中攝像機(jī)通過(guò)平移和旋轉(zhuǎn)變換視角拍攝照片時(shí)，會(huì)遇到遮擋或光線的變化。這會(huì)產(chǎn)生錯(cuò)誤匹配點(diǎn)，導(dǎo)致基本矩陣估計(jì)的不準(zhǔn)確。對(duì)此，一些研究者提出了各種抗干擾的魯棒性算法，如最大似然估計(jì)法（Maximum-likelihood Estimator，M-Estimator）和最小中值二乘法（The Least Median of Squares estimator，LmedSe）［12］和隨機(jī)抽樣一致性算法（Random Sample Consensus，RANSAC）［13］。隨機(jī)抽樣最大似然算法（Maximum Likelihood Estimation by Sample and Consensus，MLESAC）［14］是 在RANSAC 的基礎(chǔ)上結(jié)合了先驗(yàn)條件，能有效提高檢驗(yàn)準(zhǔn)確率。這些魯棒性算法的核心思想是基于假設(shè)檢驗(yàn)策略獨(dú)立地去除異常點(diǎn)。因?yàn)樾枰啻坞S機(jī)抽樣測(cè)試，每個(gè)測(cè)試過(guò)程都涉及到所有數(shù)據(jù)集來(lái)區(qū)分內(nèi)部值和異常值，所以它們的計(jì)算成本較高，處理速度較慢［15］。文獻(xiàn)［16］提出了一種快速迭代的方法，能快速剔除集合中的離群元素。文獻(xiàn)［17］受此啟發(fā)提出了一種通過(guò)對(duì)極約束快速迭代剔除錯(cuò)誤匹配點(diǎn)的基本矩陣估計(jì)法，但僅僅依靠對(duì)極約束仍會(huì)保留少量非對(duì)應(yīng)點(diǎn)。

基于上述背景，我們提出了基于梯度的離群點(diǎn)剔除約束算法（Outlier Screening by Gradient and Constraints，OSBGAC）估計(jì)基本矩陣，該算法首先針對(duì)含有非對(duì)應(yīng)點(diǎn)的情況，通過(guò)基于對(duì)極約束梯度迭代來(lái)快速剔除部分非對(duì)應(yīng)點(diǎn)。然后施加對(duì)應(yīng)點(diǎn)相關(guān)性的約束，剔除梯度迭代無(wú)法識(shí)別的非對(duì)應(yīng)點(diǎn)，得到最佳對(duì)應(yīng)點(diǎn)集合去估計(jì)基本矩陣。實(shí)驗(yàn)結(jié)果表明，相比于其他算法，本算法估計(jì)基本矩陣準(zhǔn)確度有所提升。

2 對(duì)極幾何與基本矩陣的線性解

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

圖1 兩視圖幾何

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

式中Ai是1×9 的向量，可由像素點(diǎn)齊次坐標(biāo)的克羅 內(nèi) 克 積 表 示 為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的元素構(gòu)成，f=(F11,F12,F13,F21,F22,F23,F31,F32,F33)T，F(xiàn)ij是基本矩陣F第i行j列的元素。根據(jù)八點(diǎn)法可知，已知八對(duì)匹配點(diǎn)的情況下可以求解向量f，進(jìn)而計(jì)算出基本矩陣，但圖像易受噪聲干擾使得點(diǎn)對(duì)存在偏差。針對(duì)這一情況，通過(guò)從多組點(diǎn)對(duì)估計(jì)出基本矩陣，能有效地減少誤差［18］。將一對(duì)點(diǎn)拓展到n對(duì)點(diǎn)可得到下式：

式中A=[A1;A2;…;An]。計(jì)算AT A的最小特征值所對(duì)應(yīng)的特征向量即可得到向量f。

3 算法原理

3.1 基于梯度的基本矩陣估計(jì)

一般情況下最小化對(duì)極約束得到基本矩陣解的誤差很大，只有在每對(duì)點(diǎn)的對(duì)極約束方差相同時(shí)才能得到準(zhǔn)確的解。為避免這種情況，可通過(guò)式（4）最小化對(duì)極約束的加權(quán)平方和去求解基本矩陣：

其中σi是每對(duì)點(diǎn)對(duì)極約束的方差。因?yàn)閳D像上的點(diǎn)是由同一算法提取，每個(gè)點(diǎn)可以看作受到的噪聲都服從獨(dú)立的高斯分布，可由式（5）表示噪聲的協(xié)方差矩陣：

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

每一項(xiàng)同乘常數(shù)不影響優(yōu)化問(wèn)題的求解，式（4）問(wèn)題則可以寫成式（7）：

3.2 OSBGAC基本矩陣估計(jì)法

在理想狀態(tài)下，矩陣A對(duì)應(yīng)的秩是1。在兩幅不同圖像上的對(duì)應(yīng)點(diǎn)通常用匹配算法得出，但實(shí)際中總含有錯(cuò)誤匹配的點(diǎn)對(duì)。錯(cuò)誤的匹配點(diǎn)使得矩陣A的特征值均不為零，而影響求解基本矩陣的準(zhǔn)確程度［19］。為去除不匹配點(diǎn)，提高基本矩陣F的求解準(zhǔn)確度，我們提出OSBGAC算法。首先將求解F矩陣轉(zhuǎn)換為式（8）最優(yōu)化問(wèn)題的表達(dá)式：

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

由上節(jié)可知，迭代誤差εi僅依靠最小化對(duì)極約束不足以得到最優(yōu)解，第i對(duì)匹配點(diǎn)的第n次迭代誤差表示為式（10），用來(lái)計(jì)算權(quán)重矩陣。

經(jīng)上述迭代篩選匹配點(diǎn)后，仍存在少量符合對(duì)極約束的但并非匹配的點(diǎn)對(duì)。誤差通常是由圖像中的噪聲引起，導(dǎo)致匹配算法不穩(wěn)定。一般情況下，匹配點(diǎn)對(duì)的誤差可分為定位誤差和離群誤差。定位誤差是指配點(diǎn)有少量的偏移，通常在幾個(gè)像素內(nèi)。離群誤差是指特征點(diǎn)的錯(cuò)誤匹配，點(diǎn)對(duì)不能成為對(duì)應(yīng)點(diǎn)。離群點(diǎn)通常會(huì)帶來(lái)很大的誤差，即使只有少數(shù)點(diǎn)對(duì)也會(huì)嚴(yán)重降低圖像幾何估計(jì)的精度。

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

其中點(diǎn)對(duì)之間連線與水平方向的夾角為

我們提出用向量ci來(lái)描述點(diǎn)對(duì)的關(guān)系特征。

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

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

計(jì)算最后用來(lái)估計(jì)基本矩陣的匹配點(diǎn)的誤差，然后通過(guò)均值衡量算法的準(zhǔn)確度。

4 實(shí)驗(yàn)評(píng)估

為了驗(yàn)證算法求解基本矩陣的精度，本文在四個(gè)場(chǎng)景下各選取兩幅圖像進(jìn)行實(shí)驗(yàn)。通過(guò)SURF算法取多維特征，使用K值近鄰算法匹配特征最相近的點(diǎn)作為對(duì)應(yīng)點(diǎn)去估計(jì)基本矩陣。實(shí)驗(yàn)硬件環(huán)境：AMD Ryzen 5 3500U，主頻2.1GHz，內(nèi)存16GB。實(shí)驗(yàn)軟件環(huán)境為Matlab R2018a。

圖2 中4 個(gè)子圖是室內(nèi)環(huán)境下，不同視角的兩張圖片在算法各個(gè)階段篩選匹配點(diǎn)的過(guò)程。圖2（a）是由SURF算法初始得到的匹配點(diǎn)對(duì)，并圈出將其用連線連接。可以看到初始匹配點(diǎn)中含有大量的錯(cuò)誤匹配，因?yàn)閳D像不可避免受到光線變化和噪聲等影響，使匹配算法產(chǎn)生錯(cuò)誤匹配。錯(cuò)誤匹配點(diǎn)會(huì)嚴(yán)重影響基本矩陣計(jì)算的準(zhǔn)確程度，需進(jìn)一步處理以剔除錯(cuò)誤匹配點(diǎn)。

圖2 場(chǎng)景下算法各個(gè)階段篩選匹配點(diǎn)

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

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

表1 四個(gè)場(chǎng)景下各算法表現(xiàn)

圖3 圖畫高相似場(chǎng)景

圖4 建筑晝夜場(chǎng)景

圖5 雕塑強(qiáng)曝光場(chǎng)景

從以上實(shí)驗(yàn)結(jié)果看，M-Estimator 和RANSAC算法在有干擾的情況下表現(xiàn)不佳，LMedSe 和MLESAC算法表現(xiàn)較好，本文算法在上述四個(gè)場(chǎng)景中估計(jì)基本矩陣最佳。

當(dāng)在場(chǎng)景一的圖像上分別增多添了30%、50%和70%比例的異常點(diǎn)時(shí)，測(cè)試各算法的魯棒性如表2 所示。異常像素點(diǎn)是在原有的像素上添加均值為0，方差為0.1 的高斯噪聲。從表2 中可以看出，不同情況下的同一算法性能浮動(dòng)很大。這是因?yàn)樵肼晣?yán)重影響匹配過(guò)程，錯(cuò)誤匹配點(diǎn)會(huì)導(dǎo)致基本矩陣估計(jì)的誤差增大。當(dāng)異常點(diǎn)高于50%時(shí)，M-Estimator和RANSAC算法以超過(guò)其處理能力的邊界，誤差過(guò)大。LmedSe 和MLESAC 算法在不同情況下的誤差浮動(dòng)很大。本文算法表現(xiàn)較好，魯棒性能力最佳。

表2 異常點(diǎn)比例不同情況下的各算法表現(xiàn)

表3 是各算法在四個(gè)場(chǎng)景下的平均運(yùn)算時(shí)間和算法復(fù)雜度。傳統(tǒng)算法中MLESAC 的樣本抽樣次數(shù)最多，運(yùn)行時(shí)間最長(zhǎng)，但其估計(jì)基本矩陣誤差小。其他傳統(tǒng)算法抽樣次數(shù)少，運(yùn)行時(shí)間短，但準(zhǔn)確度低。本文算法迭代次數(shù)少，在保證準(zhǔn)確度的情況下運(yùn)行時(shí)間較MLESAC算法下降了64.4%。

表3 算法復(fù)雜度和平均運(yùn)算時(shí)間

5 結(jié)語(yǔ)

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