利用單應變換與對極約束的基礎矩陣估計算法

佟 強，王紫瑤，楊大利，劉秀磊

(北京信息科技大學 計算機學院 北京 100101)

0 引言

隨著VR/AR技術的飛速發(fā)展，其技術要求也越來越高。除了通過建模工具構造虛擬的三維場景外，基于視覺技術將真實場景或物體直接轉化為三維數據的三維重建技術受到了大量的關注。由于互聯(lián)網海量圖片的存在，以及場景圖像的易獲取性，許多研究者考慮利用同一個場景或物體在不同視角下的圖片，根據視覺原理實現(xiàn)三維重建。

由于所使用的不同視角圖片往往來自于不同的拍照環(huán)境，沒有經過精確標定的相機參數，需要在多幅未標定的圖像中通過特征點集匹配來恢復相機位姿，從而得到三維重建結果[1]。相機位姿恢復技術也可用于圖像拼接[2]，將含有重疊部分的兩幅或多幅圖像，拼接成一幅包含各圖像信息的高分辨率、寬視角圖像?；謴投鄰垐D像中相機位姿的基礎是兩張圖像中的相機相對位姿的恢復，而相機間的相對位姿信息又包含在圖像間的基礎矩陣中，因此基礎矩陣估算成為研究的重點內容之一。

估算基礎矩陣是從一組含有粗差點的數據集中估計最優(yōu)的矩陣。早期使用的關鍵點通常為圖像中的角點，包括Harris[3]、FAST[4]等，主要根據鄰域內的灰度變化來判斷一個點是否為角點[5]。為了降低因圖像旋轉、縮放對角點檢測準確性的影響，尺度不變特征變換匹配 (scale invariant feature transform, SIFT)算法[6]以其對旋轉、縮放等因素的魯棒性，受到了廣泛的關注。特征描述符的維數越高，越會影響算法時效性，將主成分分析 (principal components analysis, PCA)算法與SIFT算法結合的PCA-SIFT方法[7]可以有效降低特征維數，提高算法速度。加速穩(wěn)健特征(speeded up robust features, SURF)算法[8]對關鍵點的提取效率做了提升，但由于拍攝環(huán)境的不同，在特征點集的匹配過程中，完全使用自動的特征點提取與匹配算法往往導致誤匹配，進而影響后續(xù)的重建精度。

建立了圖像之間的特征點匹配關系后，就可以對兩幅圖像之間的基礎矩陣進行估算。傳統(tǒng)的8點估計算法[9]計算簡單且易于實現(xiàn)，適用于簡單圖像匹配，但是對復雜情況適應性較差，實際應用比較困難。魯棒性算法因具有剔除誤匹配點、抗噪聲干擾的優(yōu)點，成為研究的主要方向。最小二乘法[10]對異常點敏感，當圖像存在大量的異常點時很難準確估計出模型，而隨機采樣一致(random sample consensus, RANSAC)算法[11]通過迭代，逐步過濾誤匹配點并取得最優(yōu)模型，是目前應用最廣泛的魯棒算法之一。為了進一步提高RANSAC算法的估計精度，文獻[12]在基礎矩陣估算過程中，引入了特征直線作為幾何約束。文獻[13]在采用對極幾何誤差來識別誤匹配點，通過去除誤匹配點提高基礎矩陣的估算精度。但這些方法本身引入了更多需要人為設定的經驗性閾值，也帶來了計算過程的不穩(wěn)定性。

本文針對多相機分別采集的多幅圖像，引入圖像之間的單應變換，實現(xiàn)對基礎矩陣的更精確計算。首先提取圖像上較強的特征點，在特征點對之間尋找一個單應變換，該單應變換意味著在圖像所對應的三維場景中存在著一個平面，而該平面在不同圖像上的投影平面之間滿足該單應變換。隨后再利用位于該平面之外的其余特征點匹配對，對兩幅圖像之間的可能基礎矩陣進行計算，并根據內點數量選擇最佳的基礎矩陣。該方法利用單應變換作為基礎矩陣估計的約束，降低了RANSAC算法對圖像間內點比率的依賴，在不提高算法復雜度的前提下，通過提高基礎矩陣內點比率來改善其估計精度。實驗結果表明，本文算法計算出的基礎矩陣在圖像點到對極線的距離誤差要優(yōu)于目前主流算法，且魯棒性較好、運算速度快。

1 對極幾何原理

1.1 單應矩陣

當圖像中的場景存在平面或近似平面，或者存在低時差區(qū)域的情況時，可以使用單應變換將該區(qū)域位于圖像平面上的一個坐標點，映射到另一個圖像平面上。這種變換可以表示為

Hx1=x2，

(1)

其中：x1和x2分別為兩張圖像上的坐標點x1和x2的齊次坐標形式；H是一個3×3的非奇異矩陣。當已知某個三維空間點在一幅圖像上的投影點位置后，通過單應矩陣，可求出其在另一幅圖像上的投影點位置。

如圖1所示，空間平面P上的一個點p，在圖像I1上的投影點為x1，則根據公式1可以得到其在圖像I2上的成像點x2。通過公式(1)求出平面P在兩幅圖像之間的單應矩陣H。

1.2 基礎矩陣

以上我們分析了在三維空間中位于平面P上的點p在不同圖像上的投影成像點所滿足的約束。對于不在平面P上的點p′，當對它采用矩陣H進行轉換的時候，如圖1所示，會得到錯誤的投影成像點x2，而實際的投影成像點應當為x′2。也就是說，即使已知p′在圖像I1上的投影成像點x1，也無法通過單應矩陣H計算出p′在圖像I2上的對應投影成像點。但是，對于兩個成像點x2和x′2，它們的連線為直線l2，即x1在圖像I2上的對極線。由于拍攝兩幅圖像的相機參數不同，可通過基礎矩陣來描述圖像I1上任意一點在圖像I2上對應的對極線。

圖1 單應變換Figure 1 Homography transformation

圖2 對極幾何約束Figure 2 Constraint on epipolar geometry

在任意場景多種結構的兩幅圖像間對極約束都成立。根據圖像上的像點位置，可找到另一幅圖像上的對應像點所位于的對極線，

(2)

為了求解公式(2)中的基礎矩陣F，通常使用8點法，即需要獲取8個點對坐標。與單應矩陣的求解方法類似，通過使用RANSAC迭代過濾誤匹配點，提高基礎矩陣的求解魯棒性。

2 利用單應變換的基礎矩陣求解算法

2.1 算法原理

從前述的分析中得知，當圖像場景內的點位于相同平面或近似平面時，可以根據某點p在圖像I1中的投影點x1的位置，通過單應矩陣H計算出其在圖像I2中的對應投影點x2的準確位置。同時，也可以通過基礎矩陣F來獲得該點在I2中的對極線l2。而x2必然位于l2上。也就是說，該點p在不同圖像上的投影坐標應當同時滿足公式(1)和公式(2)。

再整理成類似公式(2)的形式，即

(3)

進而可以將公式(3)簡寫為

(4)

其中M1、M2均為由H的參數所構成的矩陣。

如前所述，空間中位于平面P上的點p在不同圖像上的投影坐標應當同時滿足公式(1)和公式(2)，利用這一性質，建立基礎矩陣F的各項與單應矩陣H的系數關系。由于基礎矩陣F的秩為2，因此將其與公式(4)聯(lián)立為

F=aM1+bM2,

(5)

將公式(5)代入公式(2)，得到

(6)

為了求解公式(6)中的兩個未知量a和b，進一步將公式(6)整理為

(7)

ah13+bh23=-1。

(8)

式(7)和(8)表示了基礎矩陣F的各項與單應矩陣H的系數關系。為了進一步求解其中的兩個未知量，需要用到不屬于平面P的點p′，其在不同圖像上的投影坐標滿足公式(2)但不滿足公式(1)。將p′在圖像I1和I2上的投影成像點坐標代入公式(7)和(8)求解系數a和b，從而根據公式(5)來計算得到基礎矩陣F的值。

由于RANSAC方法通過隨機選擇若干個點作為內點進行基礎矩陣估計，其精度較為依賴于內點比率。當圖像之間的內點比率較低時，RANSAC方法難以準確找到適合用于估算基礎矩陣的若干內點，往往陷于局部最優(yōu)解。而使用單應變換作為基礎矩陣變換估計的前置約束，則有效地利用了滿足單應變換的平面信息，在降低計算復雜度的同時，也降低了對內點選擇的困難度，并通過最大化基礎矩陣的內點數量來確保其更加適應圖像上各個像素的變換，也就是提高了基礎矩陣的估計精度。

2.2 算法步驟

首先在圖像I1和I2上采用SURF算法檢測特征點，然后通過K-最近鄰方法建立兩幅圖像上特征點的匹配關系，該匹配關系包含一定的噪聲。我們對全部匹配對進行過濾，將偏轉角度過大或距離過遠的匹配對去除。

在對各個特征點的坐標進行歸一化[14]之后，通過RANSAC算法可以求得圖像I1和I2之間的單應矩陣H。將閾值設為1個像素，即圖像I1上的特征點經過單應矩陣變換后，所得到的像素坐標與圖像I2上的匹配特征點的距離不應超過1個像素。該約束會傾向于將更多的特征點匹配對標記為外點，并保證所求得的單應矩陣能夠很好地滿足內點的變換。根據前文的分析，如果1個三維空間中的點p，在圖像I1與I2上的投影點x1和x2滿足公式1，則點p應當位于平面P上。此時得到的內點即位于該平面上。為了進一步獲得平面P在圖像之間更準確的單應矩陣H，我們對全部內點根據變換像素與實際特征點之間的誤差進行排序，然后利用誤差最小的50個內點重新計算單應矩陣H。

我們根據第一次計算H時的外點集合，和第二次計算得到的H，來進行對基礎矩陣F的計算。根據式(5)、(7)和(8)，對圖像之間的各個像素點匹配對計算相應的基礎矩陣，并通過統(tǒng)計各個基礎矩陣所擁有的內點數量，選擇具有最多內點的基礎矩陣F。具體算法步驟如下。

for pair(x1,x2)∈Outlier(H)

a,b←solve(x1,x2,M1,M2) // 將匹配對的像素齊次坐標代入公式(7)和(8)

Fpair(x1,x2)←aM1+bM2// 根據公式(5)計算基礎矩陣

for every pair(xi,xj)

d ←distance(x,l) // 計算特征點到相應對極線的距離

if d<δ

Inlier(Fpair(x1,x2)).append(pair(xi,xj)) // 將該點對標記為內點

else

Outlier(Fpair(x1,x2)).append(pair(xi,xj)) // 將該點對標記為外點

N(Fpair(x1,x2)) ←count(Inlier(Fpair(x1,x2))) // 統(tǒng)計內點數量

通過采用上述的算法步驟，我們最大化了F的內點數量，找到符合最多特征點匹配對的基礎矩陣變換。在實際中，特征點到對極線的距離閾值δ通常設為1個像素。

3 實驗

3.1 數據集

我們使用了Middlebury數據集中的2001和2003兩部分[14-15]作為實驗數據集。該數據集共包含了8個場景，每個場景由9張圖像組成。由于該數據集中的場景圖像主要為平移運動，缺少旋轉和縮放變換，所以我們在其基礎上，另外采集了一組場景圖像，將其命名為Building，作為Middlebury數據集的補充，如圖3所示。

圖3 場景Building圖像Figure 3 Scene Building image

我們首先對所有圖像進行了裁剪和縮放，將分辨率統(tǒng)一為512×512。然后在各個場景的圖像之間建立SURF特征點匹配對，并將其中的部分匹配顯示如圖4所示。當對特征點匹配對進行過濾后，部分匹配顯示如圖5所示。

圖4 場景圖像之間的特征點匹配Figure 4 Feature point matching between scene images

圖5 場景圖像之間過濾后的特征點匹配Figure 5 Matching of filtered feature points between scene images

可以看到，經過過濾后，剩余的匹配對具有相似的角度和距離。這對建立兩幅圖之間的單應矩陣變換有很大幫助。

3.2 基礎矩陣投影

為了驗證本文提出的基礎矩陣計算方法的有效性和魯棒性，將本文方法與RANSAC算法[10]作對比實驗。將圖像在不同基礎矩陣上的Sampson距離作為對基礎矩陣估計精度的評價誤差。由于在本文算法中，對于檢測出的特征點匹配對進行了過濾，在對比實驗中，我們采用了有過濾RANSAC和無過濾RANSAC兩種不同的策略。

表1給出了不同算法在各個圖像場景中的平均誤差，單位為0.1像素。能夠看到3種算法在該項指標上的性能較接近。在大部分場景中，最好與最差結果之間的差距約為0.01像素。

表2給出了不同算法在各個圖像場景中的內點率，即到對極線的距離小于1個像素的特征點。應當注意的是，該評價是在全部特征點上進行，也就是包含了被過濾的特征點?？梢钥吹剑疚乃惴ㄔ趦赛c率上取得了最好的效果，在大部分場景中均提高了2%。

表 1 各算法的整體平均誤差Table 1 The overall average error of each algorithm 單位：10-1 像素

表 2 各算法的內點率Table 2 The interior point rate of each algorithm 單位：%

表3給出了不同算法在各個圖像場景中的平均內點誤差，單位為0.000 1像素。本文算法在幾乎全部場景中的該項指標上均取得了最佳結果，與其他幾種算法相比有明顯的改進。相應地，有過濾的RANSAC算法平均誤差比無過濾時也有所降低。考慮到幾種算法在整體平均誤差上的差距不大，但在內點率上具有一定差距，說明本文算法所計算出的基礎矩陣更好地符合場景中內點的變換，而放大了外點的誤差。

表4給出了不同算法在各個圖像場景中的平均外點誤差，單位為1像素?？梢钥吹?，本文算法在大部分場景中獲得了最大的外點誤差，這也再次驗證了前面的分析結論，即本文算法通過更好地擬合內點變換，同時進一步排斥外點，以計算出場景中不同圖像之間的基礎矩陣。

表 3 各算法在內點上的平均誤差Table 3 The average error of each algorithm on interior point 單位：10-4像素

表 4 各算法在外點上的平均誤差Table 4 The average error of each algorithm on outer point 單位：10-4像素

通過對以上各表中的數據進行分析，本文算法在提高了內點率的同時，顯著降低了內點的平均誤差，從而體現(xiàn)出了更好的有效性和魯棒性。這是由于RANSAC方法通過隨機選擇若干個點作為內點估算基礎矩陣，其精度較為依賴于內點比率，容易陷于局部最優(yōu)解。本文方法將單應變換作為基礎矩陣變換估計的前置約束，有效地利用了場景中滿足單應變換的平面部分信息，降低了對內點選擇的困難度，并通過最大化基礎矩陣的內點數量來確保其更適應圖像上各個像素的變換，提高了基礎矩陣的估計精度。

4 結語

本文針對圖像場景內的多幅不同視點圖像，提出了一種通過單應變換和對極約束的基礎矩陣估計算法。該方法利用場景內位于相同平面或近似平面上的空間點，計算圖像間的單應變換，再根據對極幾何約束，通過平面外的其余空間點，從單應矩陣進一步計算出圖像間的基礎矩陣。通過在公開圖像數據集與自行采集圖像數據上進行對比實驗，實驗結果說明了本文算法的有效性和魯棒性，能夠很好地過濾特征點匹配對中的噪聲并去除誤匹配，計算出更可靠精度的基礎矩陣。在未來的工作中，本文算法可推廣至規(guī)模更大的圖像集上應用，并為不同相機位姿測算、圖像拼接、點云恢復、三維重建等工作提供了良好的基礎。