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

【摘 要】本文介紹了目前常用的基本矩陣求解技術(shù)，并提出新的求解方法；通過(guò)對(duì)一個(gè)墻面進(jìn)行三維重構(gòu)，證明了新的方法的有效性。

【關(guān)鍵詞】三維物體重建；八點(diǎn)算法；基本矩陣；求解法

一、現(xiàn)階段基本矩陣的估計(jì)技術(shù)

對(duì)于一個(gè)給定的匹配關(guān)系集合，可以用集合中的匹配點(diǎn)估計(jì)出基本矩陣，估計(jì)技術(shù)平等地“看待”每對(duì)匹配點(diǎn)，認(rèn)為它們均是正確的匹配關(guān)系。常用的估計(jì)算法有七點(diǎn)算法和八點(diǎn)算法，后者最為常用。

（一）八點(diǎn)算法

八點(diǎn)算法是Longuet-Higgins首先提出的，原本用來(lái)計(jì)算本質(zhì)矩陣，這一算法后來(lái)被推廣到計(jì)算基本矩陣，它是線性運(yùn)算，計(jì)算簡(jiǎn)單、速度快。

假如我們檢測(cè)到的每一組圖像特征點(diǎn)絕對(duì)精確，匹配結(jié)果也完全正確，那么無(wú)論A包含了多少個(gè)點(diǎn)，它的秩一定是8，但是實(shí)際上，由于特征點(diǎn)檢測(cè)的位置不準(zhǔn)確、存在誤匹配等原因，A的秩總是9，AFs=0無(wú)解析解，這時(shí)用最小二乘法來(lái)求出使

‖AFs‖最小的解，同時(shí)滿足約束‖F(xiàn)‖=1，最小二乘解就是

ATA的最小奇異值對(duì)應(yīng)的向量，也可以對(duì)A進(jìn)行奇異值分解得到A=UDVT，取V的最后一列，這樣求得的解滿足約束‖F(xiàn)‖

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

（二）規(guī)一化的八點(diǎn)算法

八點(diǎn)算法計(jì)算簡(jiǎn)單，缺點(diǎn)是對(duì)噪聲敏感， 對(duì)于這個(gè)批評(píng)，Richard I. Hartley于1997發(fā)表論文認(rèn)為：八點(diǎn)算法對(duì)噪聲敏感是因?yàn)榫仃嘇條件數(shù)不好，是個(gè)病態(tài)矩陣，他提出在使用矩陣A計(jì)算F之前，先通過(guò)平移和各向縮放變換使數(shù)據(jù)規(guī)一化。

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

具體算法如下：假設(shè)兩幅圖像I和I′各自對(duì)應(yīng)的特征點(diǎn)集是S和S′，p和p′是S和S′中一組匹配點(diǎn)p∈S，p′∈S′，S和

S′中包含的匹配點(diǎn)對(duì)多于8組且這些匹配點(diǎn)對(duì)不位于同一個(gè)平面上。

二、改進(jìn)的奇異基本矩陣求解法

下面給出一個(gè)直接求解奇異基本矩陣的算法，本論文在實(shí)驗(yàn)過(guò)程中就使用了這種方法，算法思路是：設(shè)

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

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

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

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，原最小化問(wèn)題就變成了：在約束條件‖Em‖

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

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

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

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

‖f′‖=1的f′。

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

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

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

第一，利用規(guī)一化算法，求出基本矩陣的第一個(gè)近似值F0，然后求出極點(diǎn)e0，F(xiàn)0的作用只是求出e0，與后面的計(jì)算無(wú)關(guān)。

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

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

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

最后求出的就是最優(yōu)化的解，它滿足def（F）=0和‖F(xiàn)‖=1兩個(gè)約束條件。

三、實(shí)例驗(yàn)證

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

a）左圖像 （b）右圖像

圖1 兩幅匹配圖像

（a）（b）兩幅圖中一共找到86個(gè)配對(duì)角點(diǎn)，重建三維墻面就是以這些配對(duì)角點(diǎn)為輸入基本信息而展開(kāi)的逆向工程，其中最關(guān)鍵的步驟就是使用86對(duì)角點(diǎn)求解基本矩陣，我們使用本文提出的奇異基本矩陣求解法計(jì)算基本矩陣，然后求解本質(zhì)矩陣、攝像機(jī)運(yùn)動(dòng)參數(shù)等等，最后得到三維墻面結(jié)構(gòu)圖如下：

（a） 三維墻面 （b）旋轉(zhuǎn)后的三維墻面

（c）貼圖后的三維墻面 （d）旋轉(zhuǎn)后的墻面

圖2 OpenGL環(huán)境下的重建結(jié)果

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

參 考 文 獻(xiàn)

[1]張廣軍.機(jī)器視覺(jué)[M].北京：科學(xué)出版社，2004：105～107h