基于奇異基本矩陣求解法的三維物體重建

【摘 要】本文介紹了目前常用的基本矩陣求解技術，并提出新的求解方法；通過對一個墻面進行三維重構，證明了新的方法的有效性。

【關鍵詞】三維物體重建；八點算法；基本矩陣；求解法

一、現階段基本矩陣的估計技術

對于一個給定的匹配關系集合，可以用集合中的匹配點估計出基本矩陣，估計技術平等地“看待”每對匹配點，認為它們均是正確的匹配關系。常用的估計算法有七點算法和八點算法，后者最為常用。

（一）八點算法

八點算法是Longuet-Higgins首先提出的，原本用來計算本質矩陣，這一算法后來被推廣到計算基本矩陣，它是線性運算，計算簡單、速度快。

假如我們檢測到的每一組圖像特征點絕對精確，匹配結果也完全正確，那么無論A包含了多少個點，它的秩一定是8，但是實際上，由于特征點檢測的位置不準確、存在誤匹配等原因，A的秩總是9，AFs=0無解析解，這時用最小二乘法來求出使

‖AFs‖最小的解，同時滿足約束‖F‖=1，最小二乘解就是

ATA的最小奇異值對應的向量，也可以對A進行奇異值分解得到A=UDVT，取V的最后一列，這樣求得的解滿足約束‖F‖

=1，同時使‖AFs‖最小。然后將Fs還原為即可，是基本矩陣的最初值。

（二）規一化的八點算法

八點算法計算簡單，缺點是對噪聲敏感， 對于這個批評，Richard I. Hartley于1997發表論文認為：八點算法對噪聲敏感是因為矩陣A條件數不好，是個病態矩陣，他提出在使用矩陣A計算F之前，先通過平移和各向縮放變換使數據規一化。

規一化的思路：首先對圖像中的坐標進行平移使點集的質心移到原點；其次對坐標系進行縮放，各個不同的坐標方向均選擇相同的縮放因子，使點（x，y，z）T到質心的平均距離等于，這就使得縮放后的點（x，y，z）T中的x、y和z總體上有一樣的平均值，意味著所有點的坐標的平均位置為（1，1，1）T。

具體算法如下：假設兩幅圖像I和I′各自對應的特征點集是S和S′，p和p′是S和S′中一組匹配點p∈S，p′∈S′，S和

S′中包含的匹配點對多于8組且這些匹配點對不位于同一個平面上。

二、改進的奇異基本矩陣求解法

下面給出一個直接求解奇異基本矩陣的算法，本論文在實驗過程中就使用了這種方法，算法思路是：設

F= f=（f f f f f f f f f），在滿足det（F）=0和‖f‖=1的兩個約束條件下，求解F使‖Af‖最小，這樣求出的F自然是奇異的，并把解出的F作為初值進一步迭代優化。

由于det（F）=0是三次約束，所以不能用線性的非迭代算法直接求初值F，但是仍然能夠找到一個比較簡單的算法。

任何一個奇異矩陣，包括基本矩陣，可以寫成F=[e]xM，其中M是一個非奇異矩陣，[e]x是第一幅圖像上的極點的反對稱矩陣。現在要計算F=[e]xM且滿足‖f‖=1，由于基本矩陣F是用F=[e]xM求得的，[e]x的秩為2，M的秩為3，所以F的秩為2，det（F）=0約束自動滿足。在F=[e]xM中，e和M均未知，先假設e已知，將F=[e]xM改寫成下列形式：

f=E·m，其中F= ，M=，[e]= E=，f=（f f f f f f f f f）m=（m m m m m m m m m）

由于f=E·m，原最小化問題就變成了：在約束條件‖Em‖

=1下最小化‖AEm‖，A就是公式4.14中的N×9矩陣，解決這個問題的算法如下：

首先，對E奇異值分解：E=UDAT，其中對角矩陣D的非零奇異值排列在零值前面。

其次，將U的前r列構成矩陣U′，r=rank（K）。

再次，用奇異值分解求使‖AU′f′‖最小化的且滿足

‖f′‖=1的f′。

最后，令f=U′f′，f就是需要的解，用f可以組成F。

按照上述方法解出了F的初值后，還要做迭代優化。

奇異基本矩陣求解法的全部步驟如下：

第一，利用規一化算法，求出基本矩陣的第一個近似值F0，然后求出極點e0，F0的作用只是求出e0，與后面的計算無關。

第二，用極點e0構建出E0，在約束條件下‖E0m‖=1最小化‖AE0m‖，約束det（F1）=0自動滿足，用前面給出的算法求出f1=E0·m。

第三，用f1組成F1，求出e1，以便于下一次求f2使用。

第四，計算誤差ε0=‖AE0m‖，如果ε0比較大，就循環到第二步再一次計算f2，這樣迭代的變化ei、fi以便最小化ε0，整個迭代過程使用Levenberg-Marquardt算法。

最后求出的就是最優化的解，它滿足def（F）=0和‖F‖=1兩個約束條件。

三、實例驗證

為了檢測奇異基本矩陣求解法的效果，本文重建了一個三維墻面，先使用普通數碼相機拍攝了兩張圖片，圖像如下：

a）左圖像 （b）右圖像

圖1 兩幅匹配圖像

（a）（b）兩幅圖中一共找到86個配對角點，重建三維墻面就是以這些配對角點為輸入基本信息而展開的逆向工程，其中最關鍵的步驟就是使用86對角點求解基本矩陣，我們使用本文提出的奇異基本矩陣求解法計算基本矩陣，然后求解本質矩陣、攝像機運動參數等等，最后得到三維墻面結構圖如下：

（a） 三維墻面 （b）旋轉后的三維墻面

（c）貼圖后的三維墻面 （d）旋轉后的墻面

圖2 OpenGL環境下的重建結果

圖2（a）是墻面的三維結構圖，為了便于觀看，圖中已經將其三角化，圖2（b）是它在空間旋轉后的效果；圖2（c）是三維墻面貼紋理后的效果；圖2（d）是貼紋理后的墻面在空間旋轉的效果，重建的結果是令人滿意的，這證明了本文提出的奇異基本矩陣求解法的有效性。

參 考 文 獻

[1]張廣軍.機器視覺[M].北京：科學出版社，2004：105～107h