孫海迅，羅健欣，張艷艷，鄭義桀，潘志松

（中國人民解放軍陸軍工程大學(xué) 指揮控制工程學(xué)院，江蘇 南京 210001）

0 引言

三維重建是指在計(jì)算機(jī)中建立現(xiàn)實(shí)物體或場(chǎng)景三維模型的關(guān)鍵技術(shù)。隨著計(jì)算機(jī)視覺的發(fā)展，三維重建在醫(yī)學(xué)影像判讀、文物修復(fù)、自動(dòng)駕駛、虛擬現(xiàn)實(shí)等領(lǐng)域有著廣泛應(yīng)用。按照重建方法，可將其分為傳統(tǒng)方法和深度學(xué)習(xí)方法兩大類。傳統(tǒng)方法主要是對(duì)于在不同視角獲取的物體照片，利用相關(guān)算法，恢復(fù)其三維結(jié)構(gòu)。深度學(xué)習(xí)方法是通過訓(xùn)練神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)物體的三維模型［1］。深度學(xué)習(xí)方法對(duì)算力要求較高，而傳統(tǒng)基于圖像的三維重建價(jià)格低廉且算法相對(duì)成熟，因而應(yīng)用更加廣泛。

基于圖像的三維重建主要包括以下流程：圖像特征點(diǎn)檢測(cè)與匹配、稀疏點(diǎn)云重建、稠密點(diǎn)云重建、三維表面重建、表面紋理貼圖。本文針對(duì)以上流程中的關(guān)鍵環(huán)節(jié)，選取幾種代表性方法進(jìn)行綜述。

1 特征點(diǎn)檢測(cè)與匹配

特征點(diǎn)是圖像中亮度變化劇烈的點(diǎn)或圖像邊緣曲線上曲率的極大值點(diǎn)，它同周圍的鄰近點(diǎn)有著明顯差異［2］，目前已有多種特征點(diǎn)檢測(cè)方法［3］。在三維重建過程中，可以通過對(duì)不同視角下圖像特征點(diǎn)的檢測(cè)與匹配，求解相機(jī)姿態(tài)，進(jìn)而獲取三維點(diǎn)云。本文重點(diǎn)介紹兩種經(jīng)典方法——Harris角點(diǎn)檢測(cè)［4］和SIFT 特征點(diǎn)檢測(cè)［5］。

1.1 Harris角點(diǎn)檢測(cè)

角點(diǎn)指圖像上兩個(gè)方向上邊緣線的接合點(diǎn)。在一幅圖像上取一小塊特征區(qū)域，如果區(qū)域的灰度沿各方向都有較大變化，則認(rèn)為窗口內(nèi)存在角點(diǎn)。

設(shè)（x，y）為圖像上某處像素坐標(biāo)，I（x，y）代表該點(diǎn)處對(duì)應(yīng)的光度，（u，v）代表位移，I（x+u，y+v）代表位移后的光度，w（x，y）代表權(quán)重函數(shù)，本文選擇高斯函數(shù)，則可用E（u，v）度量特征區(qū)域位移后與位移前的光度差異，以此判斷區(qū)域內(nèi)是否包含角點(diǎn)。

其中，對(duì)I(x+u，y+v)進(jìn)行一階泰勒展開，即：

其中，Ix、Iy表示圖像在(x，y)坐標(biāo)點(diǎn)處的亮度分別對(duì)x、y的偏導(dǎo)數(shù)，因而可將上式重寫為：

通過對(duì)M矩陣的特征值進(jìn)行分析即可判斷Ω 區(qū)域是否包含角點(diǎn)，當(dāng)M的兩個(gè)特征值λ1、λ2都比較大時(shí)，則認(rèn)為Ω 區(qū)域包含角點(diǎn)。同時(shí)，文獻(xiàn)［4］給出了如下判別方法，當(dāng)R大于某閾值，認(rèn)為Ω 區(qū)域存在角點(diǎn)。

1.2 SIFT特征點(diǎn)檢測(cè)

文獻(xiàn)［5］提出了一種對(duì)旋轉(zhuǎn)、縮放、明暗保持不變的特征點(diǎn)檢測(cè)方法，通過高斯差分算子（Difference of Gaussian，簡(jiǎn)稱DOG 算子）尋找特征點(diǎn)。高斯空間與高斯差分空間如圖1所示。

Fig.1 Gaussian space and Gaussian difference space圖1 高斯空間與高斯差分空間

首先對(duì)原始圖像進(jìn)行降采樣形成不同的組（octave），在每組內(nèi)對(duì)圖像用不同的高斯核函數(shù)（標(biāo)準(zhǔn)差分別為σ、kσ、k2σ......）做卷積形成多張圖像。計(jì)算方法為：

其中，I(x，y)表示原圖像，G(x，y，σ)表示標(biāo)準(zhǔn)差為σ的核函數(shù)，L(x，y，σ)表示卷積之后生成的一幅高斯圖像，以此構(gòu)建高斯圖像空間（Gussian Space）。

同一組內(nèi)相鄰兩幅圖像相減得到高斯差分圖像空間（DoG Space），計(jì)算方法為：

D(x，y，σ)表示生成的一幅高斯差分圖像，并且每一組內(nèi)有效差分?jǐn)?shù)S與高斯圖像空間的層數(shù)N滿足如下關(guān)系：

在高斯差分圖像空間求極值得到圖像特征點(diǎn)，即對(duì)每個(gè)點(diǎn)與它所在圖像與上下相鄰兩層圖像周圍26 個(gè)像素點(diǎn)的亮度進(jìn)行比較，如果大于或者小于這26 個(gè)點(diǎn)，則作為極值點(diǎn)。

進(jìn)一步地，通過在亞像素位置上尋找極值點(diǎn)的更精確位置能夠從本質(zhì)上改善特征點(diǎn)的匹配穩(wěn)定性［5］，圖像極值點(diǎn)如圖2 所示。于是，在x0=(x0，y0，σ0)T處對(duì)函數(shù)D(x，y，σ)進(jìn)行泰勒展開得：

Fig.2 Extremum point of the image圖2 圖像極值點(diǎn)

令δx=x-x0，將D(x)對(duì)其求偏導(dǎo)使之為0，得：

于是精確的極值位置為x=x0+δx，對(duì)應(yīng)的函數(shù)值：

其中，偏導(dǎo)數(shù)矩陣?DT(x0)、?2D(x0)是用像素點(diǎn)附近點(diǎn)的差分形式近似表示［5］。

此外，類似于Harris 角點(diǎn)檢測(cè)的方法，對(duì)圖像平面上x處的二階Hessian 矩陣的特征值施加一定約束，能剔除某些只在一個(gè)方向上與其他點(diǎn)有明顯差異的點(diǎn)，使得檢測(cè)到的特征點(diǎn)更加穩(wěn)定。約束條件為：

圖像的主方向通過統(tǒng)計(jì)梯度直方圖的方法確定，將圖像的x軸旋轉(zhuǎn)到主方向上，算法才具有旋轉(zhuǎn)不變性。

SIFT 特征描述子（128 維）同樣是統(tǒng)計(jì)局部區(qū)域梯度信息而生成，通過最近鄰搜索方式進(jìn)行匹配，并將最近鄰與次近鄰的距離之比限定在較小范圍內(nèi)，以此得到較為精確的匹配對(duì)。

SIFT 特征點(diǎn)檢測(cè)比Harris 角點(diǎn)檢測(cè)更魯棒，對(duì)旋轉(zhuǎn)、尺度縮放、亮度變化能保持不變，但實(shí)時(shí)性不高、運(yùn)算速度較慢，因而出現(xiàn)了諸如SURF［6-7］等方法的改進(jìn)。

2 稀疏點(diǎn)云重建

稀疏點(diǎn)云重建是根據(jù)圖像上特征點(diǎn)的匹配關(guān)系，通過運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)（SFM）生成稀疏點(diǎn)云的方法。運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)是指通過圖像間的對(duì)應(yīng)關(guān)系，重構(gòu)相機(jī)外部參數(shù)（位置和姿態(tài)）和內(nèi)部參數(shù)（焦距和徑向畸變）。在實(shí)現(xiàn)SFM 的過程中，通常包含三角測(cè)量，以此求解三維點(diǎn)坐標(biāo)，得到稀疏點(diǎn)云。

2.1 基本概念

2.1.1 針孔相機(jī)模型

針孔相機(jī)模型的坐標(biāo)系包括：世界坐標(biāo)系、相機(jī)坐標(biāo)系、歸一化像平面坐標(biāo)系和物理像平面坐標(biāo)系。世界坐標(biāo)系是物體所在現(xiàn)實(shí)世界的坐標(biāo)系，實(shí)際計(jì)算時(shí)常用相機(jī)的初始位置建立世界坐標(biāo)系；相機(jī)坐標(biāo)系是在以相機(jī)中心為坐標(biāo)原點(diǎn)建立的坐標(biāo)系，其Z軸通常指向要拍攝的物體。世界坐標(biāo)系到相機(jī)坐標(biāo)系的坐標(biāo)變換如圖3 所示，相機(jī)坐標(biāo)系下的坐標(biāo)變換如圖4所示。

Fig.3 Coordinate transformation from world coordinate system to camera coordinate system圖3 世界坐標(biāo)系到相機(jī)坐標(biāo)系的坐標(biāo)變換

Fig.4 Coordinate transformation in camera coordinate system圖4 相機(jī)坐標(biāo)系下的坐標(biāo)變換

設(shè)世界坐標(biāo)系下某一點(diǎn)Xw（xw，yw，zw），在相機(jī)坐標(biāo)系下坐標(biāo)為Xc（xc，yc，zc），二者可通過旋轉(zhuǎn)平移變換得到，于是滿足以下關(guān)系：

寫成齊次形式：

歸一化像平面是人為設(shè)置的虛擬平面，將其z坐標(biāo)（距離相機(jī)光心距離）設(shè)為1。設(shè)點(diǎn)Xc的歸一化坐標(biāo)為（x，y），則：

物理像平面平行于歸一化平面，指相機(jī)CCD 陣列所在的平面。物理像平面坐標(biāo)也即圖像的像素坐標(biāo)，歸一化坐標(biāo)乘上焦距f和分辨率α（可以合并寫為fα），再進(jìn)行坐標(biāo)平移后（因?yàn)槲锢硐褡鴺?biāo)通常以圖像左上方為原點(diǎn)）即可得到物理像平面坐標(biāo)。

因此，從空間點(diǎn)的世界坐標(biāo)Xw到圖像坐標(biāo)的變換關(guān)系為：

其中，K為內(nèi)參矩陣，［R t］為外參矩陣。

2.1.2 徑向畸變矯正

相機(jī)的針孔模型與真實(shí)的相機(jī)成像不盡相同，真實(shí)的相機(jī)會(huì)由于透鏡形狀引起圖像畸變——徑向畸變。因此，要從二維圖像中準(zhǔn)確提取度量信息，必須進(jìn)行攝像機(jī)標(biāo)定。Zhang［8］提出一種利用棋盤格標(biāo)定相機(jī)的方法，標(biāo)定過程僅需打印棋盤格，并從不同方向拍攝圖片，不僅靈活方便，而且魯棒性好，如圖5所示。

Fig.5 Comparison before and after correction of radial distortion圖5 徑向畸變矯正前后對(duì)比

該方法假設(shè)畸變后的歸一化坐標(biāo)與畸變之前坐標(biāo)存在如下關(guān)系：

其中，k1、k2為徑向畸變系數(shù)，r為坐標(biāo)點(diǎn)到歸一化平面中心點(diǎn)的半徑。畸變后的圖像坐標(biāo)為：

在理想情況下：

聯(lián)立以上等式，可得：

其中，、是通過觀察棋盤格上已知的某點(diǎn)在未矯正圖像上的位置而得到，u、v是理想情況下利用前面的投影關(guān)系計(jì)算得到，r是該點(diǎn)到棋盤中心的距離。在棋盤格上選定多點(diǎn)，即可利用最小二乘法解方程得到k1、k2。之后，在矯正后的圖像上，即可利用如下關(guān)系得到點(diǎn)（u，v）對(duì)應(yīng)的、，并將矯正前坐標(biāo)（、）處的顏色值作為矯正后圖像上（u，v）坐標(biāo)的顏色值，生成矯正后的圖像。

2.2 相機(jī)姿態(tài)恢復(fù)

在對(duì)極幾何［9］中，常通過圖像坐標(biāo)點(diǎn)的對(duì)應(yīng)關(guān)系，求解基本矩陣或單應(yīng)性矩陣進(jìn)而求解相機(jī)姿態(tài)。

2.2.1 通過基本矩陣與本質(zhì)矩陣求解相機(jī)姿態(tài)

如圖6 所示，X為一空間三維點(diǎn)，O1、O2為兩個(gè)相機(jī)中心，則XO1O2所在的平面稱為極平面，π1、π2為兩個(gè)相機(jī)的物理像平面，x1、x2分別為X在兩個(gè)物理像平面的像素坐標(biāo)。設(shè)、分別為x1、x2對(duì)應(yīng)的歸一化平面坐標(biāo)，[R，t]為O2坐標(biāo)系相對(duì)于O1坐標(biāo)系的坐標(biāo)變換矩陣，兩個(gè)相機(jī)的內(nèi)參矩陣分別為K1、K2，則有如下約束關(guān)系：

Fig.6 Diagram of epipolar geometry圖6 對(duì)極幾何示意圖

在圖像特征點(diǎn)檢測(cè)與匹配的基礎(chǔ)上，利用以上約束關(guān)系，即可求得基本矩陣和本質(zhì)矩陣，進(jìn)而得到相機(jī)的外參數(shù)（相機(jī)姿態(tài)）。文獻(xiàn)［10］給出了利用8 對(duì)在圖像上匹配的特征點(diǎn)計(jì)算基本矩陣F的方法，稱為8點(diǎn)法。具體為：

設(shè)x1=(u1，v1，1)T，x2=(u2，v2，1)T為一對(duì)匹配的特征點(diǎn)，根據(jù)約束1=0，即：

若令f=(F11，F(xiàn)12，F(xiàn)13，F(xiàn)21，F(xiàn)22，F(xiàn)23，F(xiàn)31，F(xiàn)32，F(xiàn)33)T，則有：

也即每一對(duì)匹配點(diǎn)能對(duì)F矩陣提供一個(gè)約束，而若令F的任一元素歸一化（所有元素同時(shí)除以某一元素），并不影響1=0 的成立，即F有8 個(gè)自由度，因此至少需要8對(duì)匹配的特征點(diǎn)即可求得F，當(dāng)匹配的特征點(diǎn)大于8 時(shí)，也可得利用最小二乘法求解。

為增加8 點(diǎn)法的魯棒性，文獻(xiàn)［11］采用了將圖像坐標(biāo)歸一化的方法，也稱為歸一化8 點(diǎn)法。文獻(xiàn)［12］提出要對(duì)F矩陣增加奇異值約束。文獻(xiàn)［13］提出了一種根據(jù)奇異值約束對(duì)矩陣F進(jìn)行重構(gòu)的方法，即在利用8 點(diǎn)法得到F的基礎(chǔ)上，將F進(jìn)行SVD分解：

利用奇異值約束將基本矩陣重構(gòu)為：F，=Udiag(σ1，σ2，σ3)VT，這樣可以使得F-F，的Frobenius 范數(shù)最小。

在實(shí)際應(yīng)用中，特征點(diǎn)可能因噪聲產(chǎn)生誤匹配而使得基本矩陣的估計(jì)不準(zhǔn)確。為解決這一問題，文獻(xiàn)［14］采用隨機(jī)抽樣一致性（RANSAC［15］）方法估計(jì)基本矩陣，具體為：

（1）計(jì)算采樣次數(shù)。

其中，z代表期望采樣達(dá)到的成功率，M代表為達(dá)到這一成功率至少需要的采樣次數(shù)，k代表每次采樣求解基本矩陣所需要的點(diǎn)數(shù)，p代表所有樣本點(diǎn)中內(nèi)點(diǎn)（匹配準(zhǔn)確的特征點(diǎn)）的概率。

（2）對(duì)匹配的特征點(diǎn)集中隨機(jī)采樣8 對(duì)，利用8 點(diǎn)法估計(jì)初始矩陣F。

（3）用Sampson 距離［16］度量點(diǎn)集中所有點(diǎn)，將點(diǎn)劃分為內(nèi)點(diǎn)和外點(diǎn)（誤匹配的特征點(diǎn)），并記錄當(dāng)前計(jì)算所得F矩陣對(duì)應(yīng)的內(nèi)點(diǎn)個(gè)數(shù)。一對(duì)特征點(diǎn)的Sampson 距離可表示為：

其中，x1、x2表示不同圖像上的一對(duì)特征點(diǎn)，F(xiàn)為步驟（2）計(jì)算得到的矩陣，下標(biāo)x、y分別表示某一向量的x分量和y分量。

（4）重復(fù)步驟（2）（3）M次，選擇內(nèi)點(diǎn)個(gè)數(shù)最多的F矩陣和相應(yīng)的內(nèi)點(diǎn)。

（5）對(duì)所有內(nèi)點(diǎn)重新執(zhí)行步驟（2）得到基本矩陣F’。

相機(jī)姿態(tài)的恢復(fù)需要求解本質(zhì)矩陣。本質(zhì)矩陣E是一個(gè)秩為2 的矩陣，具有5 個(gè)自由度，有兩個(gè)相等的奇異值和一個(gè)0 奇異值［17］。與求解基本矩陣F所用的8 點(diǎn)法類似，本質(zhì)矩陣的求解可以采用5 點(diǎn)法［18］，也可在求得基本矩陣F的基礎(chǔ)上，利用以下關(guān)系求本質(zhì)矩陣初始解：

同樣地，要對(duì)E施加奇異值約束并重構(gòu)［9］：

在文獻(xiàn)［9］中證明，SVD 分解不唯一，如果可以分解為式（30），則也一定可以分解為：E=Udiag(1，1，0)VT。如果可以將本質(zhì)矩陣進(jìn)行SVD 分解，則E=[t]×R有如下4 種可能情況：

從圖7 可以看出，4 種情況中只有一種情況是空間點(diǎn)X同時(shí)位于兩個(gè)相機(jī)的鏡頭前方，因而只要用一個(gè)點(diǎn)做測(cè)試，看它是否位于兩個(gè)相機(jī)的前方，即可選擇出正確的相機(jī)姿態(tài)。

Fig.7 Choice of camera pose圖7 相機(jī)姿態(tài)選擇

2.2.2 用單應(yīng)性矩陣求相機(jī)姿態(tài)

文獻(xiàn)［19］指出，當(dāng)圖像上匹配的特征點(diǎn)均來自于空間中同一個(gè)平面時(shí)，無論有多少這樣的匹配點(diǎn)，它們對(duì)基本矩陣F的約束不會(huì)多于4 個(gè)，這將導(dǎo)致求解基本矩陣F的結(jié)果不穩(wěn)定。此外，當(dāng)相機(jī)姿態(tài)只有旋轉(zhuǎn)沒有平移時(shí)（從O1變換到O2是純旋轉(zhuǎn)，t=0），E=[t]×R=0，難以通過對(duì)E的分解求解R。

如圖8 所示，若空間中一平面π 方程為：nTX+d=0，則空間點(diǎn)X 對(duì)應(yīng)的兩幅圖像上的投影x1、x2有如下關(guān)系：

Fig.8 Diagram of homography transformation圖8 單應(yīng)性變換示意圖

其中K1、K2分別為兩個(gè)相機(jī)的內(nèi)參矩陣。若相機(jī)為純旋轉(zhuǎn)變換，即t=0，則H=K2RK1-1。對(duì)于H的求解方法，同樣可以采用類似于求解基本矩陣F的方法，利用兩幅視圖上匹配點(diǎn)的約束關(guān)系x2=Hx1，H矩陣有8 個(gè)自由度，而一對(duì)匹配點(diǎn)能提供兩個(gè)約束，因此至少要4 對(duì)匹配點(diǎn)即可求解H［20］。此外，可以采用RANSAC 的方法估計(jì)H，然后便可對(duì)H進(jìn)行分解以求解R和t［20］。

2.3 三角測(cè)量

在已知相機(jī)參數(shù)和匹配點(diǎn)的前提下，即可利用三角測(cè)量恢復(fù)空間點(diǎn)的三維坐標(biāo)，具體方法如下：

2.3.1 直接線性變換法

文獻(xiàn)［9］提出了直接線性變換法。設(shè)第i個(gè)相機(jī)的投影矩陣為：Pi=Ki[Ri，ti]，空間點(diǎn)的三維坐標(biāo)為X=[x，y，z，1]T，對(duì)應(yīng)在第i個(gè)視角的圖像坐標(biāo)為xi=[ui，vi，1]T，di表示X點(diǎn)在第i個(gè)視角下的深度，即相機(jī)坐標(biāo)系下的坐標(biāo)zc。則：

兩邊同時(shí)叉乘xi，得：

其中，第3 個(gè)方程與前兩個(gè)線性相關(guān)，則一個(gè)觀測(cè)視角能對(duì)X提供兩個(gè)約束，而X有3個(gè)自由度，因此要求解X，至少需要圖像上一對(duì)匹配點(diǎn)，也即至少要從兩個(gè)視角對(duì)其進(jìn)行觀測(cè)。當(dāng)點(diǎn)數(shù)N 大于2 時(shí)，還可以構(gòu)建方程組利用最小二乘法求解：

2.3.2 RANSAC方法

在存在外點(diǎn)的情況下，可以用RANSAC 方法求解［15］。主要步驟如下：①RANSAC 采樣次數(shù)，設(shè)置內(nèi)點(diǎn)閾值（重投影誤差）；②隨機(jī)采樣一對(duì)視角，計(jì)算空間點(diǎn)三維坐票；③計(jì)算每個(gè)視角中的重投影誤差，統(tǒng)計(jì)內(nèi)點(diǎn)個(gè)數(shù)；④重復(fù)步驟②、③直到滿足采樣次數(shù)，選擇內(nèi)點(diǎn)數(shù)最多的視角；⑤利用所有內(nèi)點(diǎn)重新計(jì)算三維點(diǎn)坐標(biāo)。

此外，在利用相機(jī)匹配對(duì)進(jìn)行三角測(cè)量計(jì)算三維點(diǎn)時(shí)，可以從圖像中提取EXIF 初始值以獲取焦距［21-22］。

2.4 PnP問題

PnP 問題指根據(jù)已知的三維點(diǎn)坐標(biāo)和對(duì)應(yīng)的二維點(diǎn)，求解相機(jī)內(nèi)外參數(shù)的問題，這在增量式SFM 中經(jīng)常被用到［21］。

常用的方法為直接線性變換法，設(shè)相機(jī)的投影矩陣為：P=K[R，t]，空間點(diǎn)的三維坐標(biāo)為X=[x，y，z，1]T，對(duì)應(yīng)的圖像坐標(biāo)為x=[u，v，1]T，d表示X點(diǎn)的深度，即相機(jī)坐標(biāo)系下的坐標(biāo)zc。則：

P矩陣共有12 個(gè)參數(shù)，而一對(duì)3D-2D 對(duì)應(yīng)點(diǎn)能提供2個(gè)約束，因此至少需要6 對(duì)匹配點(diǎn)即可求解P。因?yàn)镻[：，1：3]=KR，且K為上三角陣，而R為正交矩陣，可以對(duì)P[：，1：3]-1進(jìn)行QR 分解，即可求得R-1和K-1，進(jìn)而求得K和R。又P[：，4]=Kt，則t=K-1P[：，4]，得平移向量t。

文獻(xiàn)［23］提出一種計(jì)算PnP 問題的Kneip 算法，利用三維點(diǎn)構(gòu)建一個(gè)平面作為過渡坐標(biāo)系，進(jìn)而求解相機(jī)的內(nèi)外參數(shù)。此外，同樣可以用RANSAC 方法實(shí)現(xiàn)Kneip 算法。求解PnP 問題還有其他幾種方法，如用4 對(duì)不共面的點(diǎn)進(jìn)行求解的P3P 方法［24］，利用4 對(duì)以上不共面或者3 對(duì)共面點(diǎn)進(jìn)行求解的ePnP 法［25］，以及利用深度學(xué)習(xí)與傳統(tǒng)方法相結(jié)合的EPro-PnP 方法［26］，實(shí)現(xiàn)端到端的三維位姿預(yù)測(cè)。

2.5 捆綁調(diào)整

由于噪聲的影響，以上初步求得相機(jī)內(nèi)外參數(shù)和三維點(diǎn)坐標(biāo)還不夠準(zhǔn)確，捆綁調(diào)整（Bundle Adjustment）［27］可以同時(shí)對(duì)三維點(diǎn)坐標(biāo)和相機(jī)參數(shù)進(jìn)行非線性優(yōu)化。捆綁調(diào)整如圖9所示。

Fig.9 Diagram of bundle adjustment圖9 捆綁調(diào)整示意圖

設(shè)χij=1 表示第i個(gè)點(diǎn)在第j個(gè)相機(jī)中可見，χij=0 表示第i個(gè)點(diǎn)在第j個(gè)相機(jī)中不可見；Xi=(xw，yw，zw，)T表示第i個(gè)三維點(diǎn)的世界坐標(biāo)；Pj表示第j個(gè)相機(jī)的內(nèi)參以及世界坐標(biāo)系與第j個(gè)相機(jī)的外參數(shù)；表示第i個(gè)點(diǎn)在第j個(gè)相機(jī)中的觀測(cè)點(diǎn)；uij表示第i個(gè)點(diǎn)在第j個(gè)相機(jī)中的投影點(diǎn)。

則在有n個(gè)三維點(diǎn)和m個(gè)視角時(shí)，可構(gòu)建損失函數(shù)：

其中，θ=(P1，...Pm，X1，...Xn)為待優(yōu)化的量。對(duì)無約束非線性最小優(yōu)化問題對(duì)于最優(yōu)化問題g(θ)=通?？捎靡韵聨追N方法。

2.5.1 最速下降法

假設(shè)g(θ)在θt處可微，則它在θt處有泰勒展開（展開到一階）。

其中，θ=θt+δθ，當(dāng)(?g(θt))Tδθ＜0 時(shí)可保證g(θ)的值在下降，當(dāng)δθ取梯度的反方向時(shí)，可達(dá)到最快下降速度。

算法流程如下：

Step1：給定初始點(diǎn)θ0，迭代終止閾值ε和步長(zhǎng)λ，令t=0。

Step2：計(jì)算?g(θt)，若‖ ‖?g(θt) ≤ε停止迭代，輸出θt，否則轉(zhuǎn)下一步。

Step3：取θt+1=θt-λ?g(θt)，t=t+1，轉(zhuǎn)Step2。

2.5.2 牛頓法

最速下降法是收斂的，但最終的收斂是線性的，而且通常很慢，并且在某些情況下無法找到二階多項(xiàng)式的最小值，此時(shí)可用牛頓法［28］。

假設(shè)g(θ)在θt處二階可微，且假定二階導(dǎo)數(shù)?2g(θ)總是正定，則以它在θt處二階近似函數(shù)Q(θ)極小值作為下一次迭代點(diǎn)θt+1。同樣，將Q(θ)泰勒展開為：

對(duì)θ求梯度令其為0，可得：

算法流程如下：

Step1：給定初始點(diǎn)θ0，迭代終止閾值ε和步長(zhǎng)λ，令t=0。

Step2：計(jì)算?g(θt)，若‖ ?g(θt) ‖≤ε，停止迭代，輸出θt，否則轉(zhuǎn)下一步。

Step3：取θt+1=θt-λ(?2g(θt))-1?g(θt)，t=t+1，轉(zhuǎn)Ste p2。

2.5.3 高斯—牛頓法

牛頓法雖然速度快但計(jì)算量大，需要保存二階Hessian 矩陣的逆矩陣，高斯—牛頓法與牛頓法類似，但區(qū)別是它基于f(θ)在θ附近的線性近似［29］，即設(shè)p(θ)=f(θ)-x，對(duì)其泰勒展開為：

令JT(θt)=?f(θt)=?p(θt)，則：

與牛頓法相比，用JT(θt)J(θt)代替?2g(θt)，降低了運(yùn)算復(fù)雜度。

2.5.4 Levenberg-Marquardt法

最速下降法是用平面在局部擬合損失函數(shù)，牛頓法是用二次曲面擬合，當(dāng)?2g(θ)在某區(qū)域負(fù)定時(shí)，牛頓法可能收斂到局部極大值，高斯—牛頓法在J(θ)不滿秩時(shí)可能失效［28］。Levenberg-Marquardt 法［30-31］是將最速下降法和高斯—牛頓法有機(jī)結(jié)合，使用“信賴閾”控制下降速度的方法。當(dāng)收斂速度較快時(shí)，信賴閾增大，算法趨向于高斯—牛頓法；當(dāng)收斂速度慢時(shí)，信賴閾減小，算法趨向于最速下降法，優(yōu)點(diǎn)是只用到一階雅各比矩陣，計(jì)算速度快，對(duì)初始值有一定的魯棒性。

通過求解增量正規(guī)方程得到δθ?？梢?，當(dāng)λ趨向無窮大時(shí)，(JT(θt)J(θt))δθ=-?g(θt)，近似于高斯—牛頓法；當(dāng)λ趨近于0時(shí)，δθ=-?g(θt)，近似于最速下降法。

Levenberg-Marquardt 法的主要流程為：

Step4：通過求解增量正規(guī)方程，得到δθ。

2.6 運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)分類

典型的運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)方法有增量式（Incremental SFM）［32-35］、全局式（Global SFM）［36-37］、分層式［38-39］。

2.6.1 增量式運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)

主要步驟包括：圖像特征點(diǎn)檢測(cè)與匹配、構(gòu)建圖像連接圖、初始化、增量式重建新的視角、全局捆綁調(diào)整。

（1）圖像特征點(diǎn)檢測(cè)與匹配。采用上文所述方法，SIFT 方法檢測(cè)的特征點(diǎn)比較穩(wěn)定，其應(yīng)用較廣泛［33-34］。

（2）圖像連接圖構(gòu)建。每一張圖像形成圖上的一個(gè)結(jié)點(diǎn)，具有特征匹配點(diǎn)的兩幅圖像之間有邊相連，結(jié)點(diǎn)的邊越多，表示與其具有匹配的特征點(diǎn)的其他圖像越多。從圖10 可以看出，白天和夜晚拍攝的圖像因?yàn)楣舛炔町悤?huì)在連接圖上形成兩個(gè)簇［33］。

（3）初始化。選擇一對(duì)初始相機(jī)進(jìn)行Tracks 重建（三角測(cè)量）恢復(fù)三維點(diǎn)坐標(biāo)，然后進(jìn)行Tracks 濾波和捆綁調(diào)整以優(yōu)化估計(jì)的三維點(diǎn)坐標(biāo)和相機(jī)內(nèi)外參數(shù)。

其中，初始相機(jī)對(duì)的選取要遵循一定的原則：匹配點(diǎn)足夠多、基線足夠長(zhǎng)、滿足單應(yīng)性的匹配點(diǎn)盡量少［33-34］。文獻(xiàn)［34］指出，由于冗余數(shù)據(jù)的存在，從圖像連接圖中的密集位置進(jìn)行初始化通常會(huì)使得重建更加魯棒和準(zhǔn)確。

Tracks 濾波是指濾除Tracks 重建中生成的錯(cuò)誤點(diǎn)（包括無窮遠(yuǎn)處的點(diǎn)和重投影誤差過大的點(diǎn)）［21，33］，以降低后續(xù)運(yùn)算復(fù)雜度。

（4）新的視角增量式重建。選擇能看到已被估計(jì)的三維點(diǎn)最多的視角，利用PnP 方法［21］或者RANSAC 方法［33］求解新視角的相機(jī)姿態(tài)，然后對(duì)單個(gè)相機(jī)姿態(tài)進(jìn)行捆綁調(diào)整。下一步對(duì)新視角能看到的點(diǎn)進(jìn)行Tracks 重建和濾波，以此優(yōu)化三維點(diǎn)的坐標(biāo)。

（5）全局捆綁調(diào)整。對(duì)所有已加入的相機(jī)內(nèi)外參數(shù)和三維點(diǎn)坐標(biāo)進(jìn)行一次全局的非線性優(yōu)化，由于這一方法運(yùn)行時(shí)間較長(zhǎng)，可以在加入多個(gè)視角之后運(yùn)行一次［21］。

增量式運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)如圖11 所示。其主要優(yōu)點(diǎn)是：對(duì)誤匹配的特征點(diǎn)魯棒、場(chǎng)景結(jié)構(gòu)可在調(diào)整中不斷優(yōu)化。缺點(diǎn)是：對(duì)初始視角的選取和視角添加順序敏感、大場(chǎng)景下的累計(jì)誤差會(huì)導(dǎo)致場(chǎng)景漂移、捆綁調(diào)整重復(fù)進(jìn)行導(dǎo)致效率低。文獻(xiàn)［35］提出一種與RANSAC 相結(jié)合提升精度的增量式運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)方法。

Fig.11 Incremental structure from motion圖11 增量式運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)

2.6.2 全局式運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)

由于捆綁調(diào)整比較耗時(shí)，全局式運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)同時(shí)估計(jì)所有相機(jī)的旋轉(zhuǎn)矩陣和平移向量，生成三維點(diǎn)后，只運(yùn)用一次捆綁調(diào)整進(jìn)行優(yōu)化。文獻(xiàn)［36］提出一種估計(jì)全局相機(jī)姿態(tài)的方法。

首先，在生成圖像連接圖之后，利用任意兩幅圖像的特征點(diǎn)匹配關(guān)系，計(jì)算兩個(gè)相機(jī)的相對(duì)旋轉(zhuǎn)矩陣Rij和平移向量tij，通過最小化如下關(guān)系求解所有相機(jī)相對(duì)于世界坐標(biāo)系的旋轉(zhuǎn)矩陣。

其次，進(jìn)行全局旋轉(zhuǎn)矩陣濾波，根據(jù)求得的Ri與Rj優(yōu)化圖像連接圖，即當(dāng)時(shí)，認(rèn)為相機(jī)i與j之間存在錯(cuò)誤的連接邊，要?jiǎng)h除。

最后，利用求得的相機(jī)姿態(tài)求解三維點(diǎn)并進(jìn)行一次全局的捆綁調(diào)整。

文獻(xiàn)［37］提出一種多種信息融合的方法，在求解過程加入了GPS等輔助信息，對(duì)結(jié)果進(jìn)行優(yōu)化。

全局式運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)如圖12 所示。其主要優(yōu)點(diǎn)是：沒有誤差積累，誤差均勻分布在連接圖上；對(duì)初始相機(jī)選取和相機(jī)添加順序不敏感；捆綁調(diào)整僅執(zhí)行一次，重建效率高。不足之處主要體現(xiàn)在：相機(jī)位置求解時(shí)對(duì)匹配外點(diǎn)敏感，魯棒性不足；連接圖邊界被過濾，容易造成部分圖像丟失，導(dǎo)致重建不完整。

Fig.12 Global structure from motion圖12 全局式運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)

2.6.3 分層式運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)

文獻(xiàn)［38］提出基于聚類方式的分層式運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)，如圖13 所示。其主要步驟為：利用已知視角創(chuàng)建一個(gè)局部模型進(jìn)行捆綁調(diào)整，加入一個(gè)新的視角，兩個(gè)模型融合捆綁調(diào)整。這種方法計(jì)算效率高，且算法穩(wěn)定，不依賴初始相機(jī)的選取，避免了大場(chǎng)景中的誤差積累和漂移，但規(guī)則設(shè)計(jì)較為復(fù)雜。

Fig.13 Hierarchical structure from motion圖13 分層式運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)

3 稠密點(diǎn)云重建

基于圖像的三維重建中，稠密點(diǎn)云的獲取通?；诙嘁晥D立體技術(shù)（Multi-view Stereo，MVS）。該技術(shù)的優(yōu)點(diǎn)是成本低、精度較高、圖像來源廣；缺點(diǎn)是計(jì)算速度慢。

MVS 中常用的一個(gè)基本假設(shè)是光度一致性假設(shè)（Photo-Consistency），是指同一空間的點(diǎn)在不同視角的投影，光度應(yīng)該相同，重建的關(guān)鍵是恢復(fù)光度一致性的點(diǎn)。光度一致性度量方式有：誤差平方和（SSD，Sum of Squared Difference）、歸一化交叉協(xié)方差（NCC，Normalized Cross Correlation）。具體為：

其中，f和g分別為特征描述子的特征向量、為描述子的均值向量，δf、δg為描述子向量標(biāo)準(zhǔn)差。

基于多視圖立體技術(shù)（MVS）的稠密點(diǎn)云重建主要有基于體素的方法、基于深度圖融合的方法和基于空間patch 擴(kuò)散的方法。

3.1 基于體素的方法

基于體素的方法是指將空間劃分為很多體素，通過圖像序列的約束計(jì)算體素內(nèi)三維點(diǎn)的方法?？臻g劃分包括兩種類型：一種是規(guī)則體素的劃分［40］，即將空間劃分為小立方體；另一種是不規(guī)則體素的劃分［41-42］，即將空間劃分為小四面體，如圖14所示。

Fig.14 Dense reconstruction based on voxels圖14 基于體素的稠密重建

這種方法的優(yōu)點(diǎn)是：生成規(guī)則的點(diǎn)云、便于提取物體的平面。其缺點(diǎn)是：精度受到空間劃分分辨率的影響，僅適用于小場(chǎng)景，單個(gè)物體，遮擋較少的場(chǎng)景，難以處理高精度、大規(guī)模的場(chǎng)景。

3.2 基于深度圖融合的方法

基于深度圖融合的方法［43］是利用SFM 產(chǎn)生的稀疏點(diǎn)云構(gòu)建種子?xùn)鸥瘢╬atch），通過區(qū)域生長(zhǎng)對(duì)patch 進(jìn)行優(yōu)化后生成不同視角下的深度圖，再將不同視角深度進(jìn)行融合的稠密點(diǎn)云重建方法。該方法主要包括以下3 個(gè)步驟：數(shù)據(jù)預(yù)處理、區(qū)域生長(zhǎng)、深度圖融合，如圖15所示。

Fig.15 Dense reconstruction based on depth map fusion圖15 基于深度圖融合的稠密重建

3.2.1 數(shù)據(jù)預(yù)處理

patch 是以空間中的3D 點(diǎn)中心建立一個(gè)很小的柵格，柵格的分辨率與圖像分辨率以及3D 點(diǎn)的位置相關(guān)。patch的中心點(diǎn)即為3D 點(diǎn)的位置，patch 的朝向即為3D 點(diǎn)的法向量，patch 上的每個(gè)點(diǎn)可以投影到不同視角中計(jì)算NCC 用于度量光度一致性。

其預(yù)處理包括：通過SFM 重建的稀疏點(diǎn)構(gòu)建種子patch、構(gòu)建不同分辨率的圖像以處理圖像分辨率不同情況、全局視角選擇。全局視角選擇是指選擇滿足特定條件的視角用于區(qū)域生長(zhǎng)。一般要滿足以下條件：①圖像具有相同的內(nèi)容，外觀——通過共享sift 特征點(diǎn)的個(gè)數(shù)；②圖像具有足夠大的視差（寬基線）——通過視線的夾角；③圖像具有相似的分辨率——通過計(jì)算投影球半徑。

為使得計(jì)算加速，在生成某一視角的深度圖時(shí)，文獻(xiàn)［43］從以上全局視角中選擇4 個(gè)視角，稱為局部視角。局部視角的選擇要求：NCC值大于一定的閾值，并且和已經(jīng)選擇的視角的極平面要足夠分散（不共面），如圖16所示。

Fig.16 Diagram of view selection圖16 視角選擇示意圖

3.2.2 區(qū)域生長(zhǎng)

在建立初始種子patch 后，可以利用種子patch 逐步擴(kuò)張的方法在其鄰域生成新的patch。其主要步驟包括：①對(duì)稀疏點(diǎn)云中的種子patch 以置信度（光度一致性）建立優(yōu)先級(jí)隊(duì)列；②估計(jì)初始稀疏種子點(diǎn)的深度；③對(duì)每個(gè)種子點(diǎn)進(jìn)行非線性深度優(yōu)化；④每次優(yōu)化完后，如果圖像上的對(duì)應(yīng)像素沒有深度值或當(dāng)前像素的置信度值高于鄰域像素一定范圍，則將其像素添加到隊(duì)列中。

其中，非線性優(yōu)化的數(shù)學(xué)模型為：

其中，i、j是patch 中的采樣點(diǎn)，k為視角個(gè)數(shù)。IR(i，j)表示點(diǎn)在參考圖像上的光度，ck是顏色尺度，由于IK(i，j)表達(dá)式中含有深度信息，因而可以利用梯度下降等優(yōu)化方法對(duì)E 進(jìn)行優(yōu)化，進(jìn)而求解像素點(diǎn)深度。優(yōu)化求解結(jié)果如圖17所示［43］。

Fig.17 Reconstruction effect based on depth map fusion圖17 基于深度圖融合的重建效果

3.2.3 深度圖融合

深度融合是指在三維空間合并位置相近的點(diǎn)。融合過程同樣要對(duì)點(diǎn)施加一定的約束，通常包括一致性約束、可視性約束。一致性約束是指相同的點(diǎn)在不同視角下的深度應(yīng)當(dāng)具有一致性；可視性約束是指在圖像上可視的三維點(diǎn)在融合后的深度圖上不能被遮擋。如圖18 所示，A 和C 將被認(rèn)為是錯(cuò)誤的點(diǎn)，予以剔除，B 將被選擇為正確的點(diǎn)。

Fig.18 Diagram of consistent point selection圖18 一致點(diǎn)選擇示意圖

深度圖融合方法的特點(diǎn)為：鄰域視角選擇提升了深度估計(jì)的準(zhǔn)確度，對(duì)一些有遮擋、障礙物較多的場(chǎng)景能較好地進(jìn)行處理，適用場(chǎng)景廣泛，只用到光度一致性約束和可視性約束，算法實(shí)現(xiàn)簡(jiǎn)單。

3.3 基于空間patch擴(kuò)散的方法

與深度圖中在二維圖像上進(jìn)行patch 擴(kuò)張不同的是，基于空間patch 擴(kuò)散的方法［44］采用的是在空間中對(duì)三維patch（大小為5x5 共25 個(gè)三維點(diǎn)）進(jìn)行擴(kuò)散，最終使patch覆蓋物體表面。

重建流程如圖19所示。

Fig.19 Reconstruction process based on patch diffusion圖19 基于空間patch擴(kuò)散重建流程

初始種子點(diǎn)生成采用SIFT 等特征點(diǎn)；擴(kuò)張過程對(duì)已重建三維點(diǎn)的鄰域進(jìn)行匹配，濾波過程采用兩種約束去除噪聲點(diǎn)：光度一致性約束和可視性約束。

初始3D patch 的生成步驟：①在圖像上均勻計(jì)算SIFT/Harris 特征；②沿極線進(jìn)行搜索找到匹配特征點(diǎn)；③對(duì)匹配對(duì)，通過三角化建立patch，法向量指向參考圖像，通過光度一致性約束對(duì)可視圖像進(jìn)行篩選；④對(duì)patch 位置和法向量進(jìn)行優(yōu)化。

空間patch 擴(kuò)散步驟為：①將三維patch 投影到圖像上；②如果相鄰cell 沒有patch 且深度連續(xù)，則進(jìn)行patch 擴(kuò)散，新建patch 的法向量初始值等于領(lǐng)域patch，新建patch的位置設(shè)置為當(dāng)前cell 的視線和鄰域patch 所在平面的交點(diǎn)；③計(jì)算初始patch 的可視圖像，并進(jìn)行優(yōu)化。

擴(kuò)張過程中并沒有考慮到可視性的情況，濾波過程的主要目的是利用各種約束對(duì)這些不合理的點(diǎn)進(jìn)行篩選?？捎玫募s束包括可視性約束，可視圖像個(gè)數(shù)小于一定閾值，圖像鄰域中的cell同時(shí)也是空間鄰域，其比例小于一定閾值（0.25）。對(duì)于每一個(gè)patch，統(tǒng)計(jì)它所在及相鄰image cell 中的所有patch。如果3D 空間中與相鄰的patch 比例小于一定值（0.25），則認(rèn)為是孤立點(diǎn)，將被移除。

PMVS 和基于深度圖的重建方法類似，基本原理也是基于光度一致性，并且采用區(qū)域生長(zhǎng)的方式進(jìn)行稠密重建，同樣適用于雜亂有遮擋的大規(guī)模場(chǎng)景。算法優(yōu)點(diǎn)是：適用性強(qiáng)，適用于各種形狀的物體，能夠直接重建出完整的稠密點(diǎn)云，不需要進(jìn)行單獨(dú)的深度圖融合；重建過程中同時(shí)考慮了可視性約束，能夠得到更加準(zhǔn)確的重建結(jié)果。其缺點(diǎn)是不適用于非朗伯面（Non-Lambertian），并容易產(chǎn)生空洞，計(jì)算量非常大。

近年來，也有針對(duì)以上算法不足的改進(jìn)方法，如：文獻(xiàn)［35］利用并行計(jì)算提升點(diǎn)云重建速度；文獻(xiàn)［45］針對(duì)在小范圍場(chǎng)景三維重建過程中存在離群點(diǎn)的現(xiàn)象，將PMVS 算法與統(tǒng)計(jì)分析法相融合提出一種改進(jìn)的點(diǎn)云濾波算法，提高了重建精度。

當(dāng)前，稠密點(diǎn)云重建面臨的主要問題與挑戰(zhàn)是：①弱紋理和朗伯面——不能滿足光度一致性約束；通常需要先驗(yàn)形狀約束進(jìn)行重建；②細(xì)長(zhǎng)結(jié)構(gòu)重建——很難得到像素級(jí)別精度的深度值；通常的解決方法需要進(jìn)行語義級(jí)別的重建；③動(dòng)態(tài)場(chǎng)景重建——圖像序列的重建方式可以捕捉動(dòng)態(tài)場(chǎng)景，但是基本只適合于實(shí)驗(yàn)室環(huán)境；動(dòng)態(tài)物體的重建需要結(jié)合形狀先驗(yàn)、高級(jí)語義信息等。

4 三維表面重建

在得到稠密點(diǎn)云后，利用各種算法可以從點(diǎn)云重建物體表面。三維物體的表面表達(dá)方式包括：邊界表示法、空間劃分法、構(gòu)造體素法。邊界表示法用四邊形、三角形、參數(shù)曲面或者非參數(shù)的曲面表示物體形狀，具有穩(wěn)定性強(qiáng)、靈活性強(qiáng)、有助于表示表面細(xì)節(jié)。空間劃分法將物體內(nèi)部劃分成細(xì)小連續(xù)實(shí)體以描述物體形狀。構(gòu)造體素法通過集合運(yùn)算（并、交、差）將簡(jiǎn)單形狀組合成復(fù)雜形狀，只能用來表示較為簡(jiǎn)單的實(shí)體，無法用于形狀復(fù)雜或表面精細(xì)的物體。

計(jì)算機(jī)視覺中最常用的三維模型表示方式為三角網(wǎng)格（Triangular Mesh）。其基本結(jié)構(gòu)包括：頂點(diǎn)（Vertex）、面片（Facet）、邊（Edge）。點(diǎn)、線和面上的各種屬性包括：顏色、法向量、紋理坐標(biāo)（Texture Coordinate）。

常用的三維表面重建方法有：基于二元分割的表面重建方法、基于符號(hào)距離場(chǎng)的表面重建方法。

4.1 基于二元分割的表面重建方法

其主要思想是將空間劃分成一組小單元（體素/四面體），采用二元分割思想將這些小單元?jiǎng)澐殖蓛?nèi)部和外部?jī)深悾橛趦?nèi)部和外部之間的面即為物體表面，如圖20所示［43］。

Fig.20 Surface reconstruction based on binary segmentation圖20 基于二元分割的表面重建

在稠密點(diǎn)云的基礎(chǔ)上進(jìn)行表面重建主要經(jīng)歷的步驟如下：

4.1.1 德勞內(nèi)三角剖分

德勞內(nèi)三角剖分（Delaunay Triangulation）是指將點(diǎn)云中的相鄰點(diǎn)用一種特定的方式連線，使得任意相鄰的4 個(gè)點(diǎn)構(gòu)成空間中的一個(gè)四面體。德勞內(nèi)三角剖分具有以下特性：

（1）空球特性。任意4 個(gè)點(diǎn)的外接球內(nèi)都不含有其他點(diǎn)。

（2）最大化最小角。德勞內(nèi)三角剖分最大化四面體上三角形的最小角。

（3）對(duì)偶性。德勞內(nèi)三角剖分和維諾圖（Voronoi Diagram）是互為對(duì)偶的關(guān)系，如圖21所示［43］。

Fig.21 Duality of Delaunay triangulation and Voronoi diagram圖21 德勞內(nèi)三角剖分與維諾圖的對(duì)偶關(guān)系

文獻(xiàn)［46］給出了一種增量式進(jìn)行德勞內(nèi)三角剖分的方法。

三維表面的生成問題將轉(zhuǎn)化為四面體的二元標(biāo)記問題，即將一剖分四面體標(biāo)記為“外部”，另一剖分四面體標(biāo)記為“內(nèi)部”，內(nèi)外交界處的空間曲面即為物體表面。

4.1.2 用圖分割方法提取物體表面

圖分割（Graph Cut）是指對(duì)一特殊的有向加權(quán)圖的某些邊進(jìn)行切分，將圖分割為沒有交集的兩個(gè)部分，使得邊的權(quán)重?fù)p失最?。?6-48］。這一圖的特殊之處在于包含兩個(gè)特殊的節(jié)點(diǎn)：源節(jié)點(diǎn)和匯節(jié)點(diǎn)，其中源節(jié)點(diǎn)只有出邊，而匯節(jié)點(diǎn)只有入邊，如圖22 所示，邊的粗細(xì)表示權(quán)重大小，切分目標(biāo)是選取權(quán)重最小的邊切分。

Fig.22 Diagram of graph cut圖22 圖分割示意圖

在對(duì)稠密點(diǎn)云進(jìn)行德勞內(nèi)三角剖分后，根據(jù)其與維諾圖的對(duì)偶關(guān)系生成維諾圖：即使四面體的中心作為維諾圖各小區(qū)域的中心，四面體的三角形表面作為維諾圖的邊。在一定約束條件下，對(duì)維諾圖的邊賦予一定權(quán)重并將其看作有向加權(quán)圖，于是便可進(jìn)行圖分割提取物體表面，如圖23所示［43］。

Fig.23 Surface reconstruction based on graph cut圖23 基于圖分割的表面重建

對(duì)維諾圖的邊賦予權(quán)重的方法包括以下幾種：可見性約束、光度一致性約束、平滑性約束［46］、剪影約束［43］、表面質(zhì)量約束［47］。

重建結(jié)果如圖23所示［43］。

4.1.3 網(wǎng)格細(xì)節(jié)優(yōu)化

用二元分割方法提取的物體表面，由于點(diǎn)云存在噪聲或者空洞，會(huì)導(dǎo)致原始網(wǎng)格存在噪聲或者空洞，無法捕捉場(chǎng)景細(xì)節(jié)，因而需要對(duì)網(wǎng)格細(xì)節(jié)進(jìn)行優(yōu)化（Mesh Refinement）。

文獻(xiàn)［44］提出一種基于光度一致性的網(wǎng)格細(xì)節(jié)優(yōu)化方法，即利用多視角圖像再次計(jì)算相同點(diǎn)在不同視角下的重投影誤差，通過同時(shí)或者逐個(gè)移動(dòng)網(wǎng)格頂點(diǎn)的位置，使重投影誤差最小，也使光度一致性最好。度量光度一致性的能量函數(shù)為：

其中，h(Ii，)(x)表示圖像i和j之間在像素x處與光度一致性呈單調(diào)遞減的某一函數(shù)；表示將圖像i通過曲面S重投影到圖像i上；表示重投影的有效區(qū)域；Eerror(S)的含義即為所有兩兩視角對(duì)下相同區(qū)域的重投影誤差之和；Eerror(S)越小，說明生成的網(wǎng)格越準(zhǔn)確。

要優(yōu)化網(wǎng)格頂點(diǎn)位置，即要求以上能量函數(shù)關(guān)于網(wǎng)格頂點(diǎn)的梯度，應(yīng)利用梯度下降法進(jìn)行優(yōu)化。但由于網(wǎng)格頂點(diǎn)的位置變化實(shí)際上會(huì)影響其周圍三角面片上點(diǎn)的位置，于是先計(jì)算關(guān)于某頂點(diǎn)周圍三角面片點(diǎn)的梯度，再采用插值方法計(jì)算這一頂點(diǎn)的梯度，插值方法采用重心坐標(biāo)法。Eerror（S）對(duì)［Xi］的梯度為其對(duì)網(wǎng)格上Xi一周所有點(diǎn)梯度的加權(quán)和具體如圖24所示。

Fig.24 Grid vertex position optimization圖24 網(wǎng)格頂點(diǎn)位置優(yōu)化

其中，v(x)表示頂點(diǎn)Xi一周三角網(wǎng)格上的任意一點(diǎn)，φi(x)表示v(x)相對(duì)于Xi的重點(diǎn)坐標(biāo)，?E是Eerror(S)相對(duì)于v(x)的梯度。

基于二元分割的表面重建方法具有以下特點(diǎn)：①算法流程簡(jiǎn)單，容易實(shí)現(xiàn)；②適用于大規(guī)模場(chǎng)景以及小物體重建，能夠處理復(fù)雜表面；③重建效果依賴德勞內(nèi)三角剖分的質(zhì)量，容易受到噪聲和外點(diǎn)影響；④通常需要結(jié)合網(wǎng)格細(xì)節(jié)優(yōu)化獲取更加精細(xì)的表面細(xì)節(jié)。

4.2 基于符號(hào)距離場(chǎng)的表面重建方法

基于符號(hào)距離場(chǎng)的表面重建流程如圖25所示。

Fig.25 Surface reconstruction based on symbol distance field圖25 基于符號(hào)距離場(chǎng)的表面重建流程

Fig.26 Uniform（left）and non-uniform（right）spatial division圖26 均勻（左）與非均勻（右）的空間劃分

4.2.1 空間劃分

空間劃分主要是用于對(duì)空間中的隱函數(shù)進(jìn)行離散化，以便于對(duì)劃分區(qū)域的每個(gè)頂點(diǎn)計(jì)算一個(gè)符號(hào)距離值。空間劃分方式可以采用均勻和非均勻兩種。均勻劃分是將空間劃分為大小相等的體素網(wǎng)格（Grid），非均勻方式是用八叉樹（Octree）結(jié)構(gòu)將空間進(jìn)行劃分，即在點(diǎn)密集處空間劃分較細(xì)，樹的頂點(diǎn)較小；點(diǎn)稀疏處空間分辨率較低，樹的頂點(diǎn)較大，點(diǎn)的分辨率可以根據(jù)三維點(diǎn)到相鄰點(diǎn)的平均距離確定。

4.2.2 符號(hào)距離場(chǎng)構(gòu)建

文獻(xiàn)［49］提出一種局部的符號(hào)距離場(chǎng)構(gòu)建方法，用符號(hào)距離函數(shù)（Signed Distance Function，SDF）計(jì)算空間中各處的符號(hào)距離值，然后提取等值面作為物體表面。

符號(hào)距離函數(shù)是某度量空間中點(diǎn)X 到某一邊界的距離關(guān)于X 位置的函數(shù)，當(dāng)X 在邊界內(nèi)時(shí)，SDF 為正；當(dāng)X 在邊界外時(shí)，SDF 為負(fù)。如圖27所示，0所在位置即可認(rèn)為是物體表面。

Fig.27 Diagram of symbol distance function圖27 符號(hào)距離函數(shù)示意圖

文獻(xiàn)［49］所用的符號(hào)距離函數(shù)為：

即在點(diǎn)x附近鄰域取i個(gè)點(diǎn)pi，在pi處建立局部坐標(biāo)系（x軸與pi點(diǎn)的法向量ni方向相同，y軸與z軸分別與x軸垂直），再利用旋轉(zhuǎn)矩陣Ri將x旋轉(zhuǎn)到局部坐標(biāo)系下，得到xi=Ri·(x-pi)，對(duì)以下基函數(shù)f(xi)用ciwi(xi)加權(quán)計(jì)算即可得到點(diǎn)x處的符號(hào)距離值，其中，wi(xi)權(quán)重函數(shù)，ci為點(diǎn)pi的置信度（NCC 值）。

局部符號(hào)距離場(chǎng)結(jié)果如圖28所示［49］。

Fig.28 Boundaries computed by symbolic distance function圖28 符號(hào)距離函數(shù)計(jì)算邊界

文獻(xiàn)［50］提取了一種全局的符號(hào)距離場(chǎng)構(gòu)建方法，將有向點(diǎn)看作是對(duì)隱函數(shù)梯度的采樣，如圖29 所示。全局的方法優(yōu)點(diǎn)是魯棒，能夠很好地處理噪聲和空洞，缺點(diǎn)是計(jì)算量大，需要求解大規(guī)模的方程。

Fig.29 Poisson surface reconstruction圖29 泊松表面重建

4.2.3 移動(dòng)立方體算法生成表面

移動(dòng)立方體算法（Marching Cube）最早由文獻(xiàn)［51］提出，在得到每個(gè)體素8 個(gè)頂點(diǎn)的符號(hào)距離值后，通過插值方法生成三角形面片，每個(gè)頂點(diǎn)有兩種狀態(tài)，總共有256種，但由于反轉(zhuǎn)狀態(tài)不變，因此可以減少一半，為128 種，再根據(jù)旋轉(zhuǎn)不變形，又可以減少到14 種情況?？梢哉J(rèn)為這14 種類似于基，經(jīng)過旋轉(zhuǎn)、反轉(zhuǎn)可以得到256 種狀態(tài)所對(duì)應(yīng)的結(jié)果（其中3種情況），如圖30所示。

Fig.30 Surfaces generated by marching cube method圖30 移動(dòng)立方體法生成表面

文獻(xiàn)［52］提出一種專門針對(duì)八叉樹的方法，旨在解決相鄰節(jié)點(diǎn)分辨率不一致時(shí)可能出現(xiàn)的裂縫問題。通過引入一組從八叉樹的拓?fù)渫茖?dǎo)而來的二叉邊樹，可以在不約束八叉樹的拓?fù)浣Y(jié)構(gòu)或修改頂點(diǎn)值的情況下，直接提取水密的多邊形網(wǎng)格。

文獻(xiàn)［53］提出一種將平面投影與區(qū)域生長(zhǎng)相結(jié)合的表面重建方法，降低了表面重建復(fù)雜度。文獻(xiàn)［54］用統(tǒng)計(jì)濾波器對(duì)點(diǎn)云簡(jiǎn)化去噪，并建立點(diǎn)云間拓?fù)浣Y(jié)構(gòu)，緩解了重建表面粗糙、孔洞等問題。

5 紋理圖像創(chuàng)建

為了生成更加逼真的場(chǎng)景和物體，可以對(duì)生成的三維模型貼上紋理圖像。文獻(xiàn)［56］在文獻(xiàn)［55］的基礎(chǔ)上提出創(chuàng)建紋理圖像管線，主要分為如下步驟：視角選擇、全局顏色調(diào)整、泊松圖像編輯。

5.1 視角選擇

為每個(gè)三角面片選擇唯一的視角，用于獲取紋理信息，視角的選擇應(yīng)當(dāng)考慮到以下因素：圖像尺度、圖像細(xì)節(jié)豐富程度、圖像可視性、鄰域平滑性。具體方法為：將視角選擇建模成多標(biāo)簽分配問題，為每一個(gè)三角形分配一個(gè)標(biāo)簽（視角），在網(wǎng)格上建立馬爾可夫隨機(jī)場(chǎng)，每個(gè)面片代表一個(gè)頂點(diǎn)，通過優(yōu)化能量函數(shù)得到最優(yōu)視角選擇。能量函數(shù)分為數(shù)據(jù)項(xiàng)Edata和平滑項(xiàng)Esmooth，即：

其中，F(xiàn)i表示第i個(gè)三角面片，li表示分配給它的視角標(biāo)簽，數(shù)據(jù)項(xiàng)Edata通過三角面片對(duì)應(yīng)的二維圖像上三角形內(nèi)的平均像素梯度進(jìn)行度量，旨在選擇圖像分辨率較大的視角；平滑項(xiàng)約束希望相鄰三角形有相同的視角以保持鄰域的平滑性，從而減少縫隙，為后續(xù)處理提供便利。選擇好對(duì)應(yīng)的視角后，即可將網(wǎng)格投影到對(duì)應(yīng)視角的可視圖像上，截取對(duì)應(yīng)圖像作為紋理圖像，經(jīng)過坐標(biāo)歸一化處理后，即可作為三角面片的紋理坐標(biāo)，后期通過紋理坐標(biāo)可找到紋理圖像上對(duì)應(yīng)的貼片。

5.2 全局顏色調(diào)整

由于不同視角間存在相機(jī)曝光或者光照差異導(dǎo)致不同的紋理圖像邊界處存在明顯縫隙，因而要為邊界處的每個(gè)像素添加一個(gè)顏色調(diào)整量使得縫隙處的顏色差異盡量小，紋理圖像內(nèi)部相鄰像素的調(diào)整量盡量相似。

具體方法：首先為三角面片的每個(gè)頂點(diǎn)對(duì)應(yīng)像素添加一個(gè)調(diào)整量，再通過插值方式得到三角面片內(nèi)部對(duì)應(yīng)的每個(gè)像素的調(diào)整量，然后將縫隙處的頂點(diǎn)拆分成n個(gè)（n為標(biāo)簽個(gè)數(shù)），對(duì)其施加n個(gè)調(diào)整量，最后通過優(yōu)化以下能量函數(shù)得到調(diào)整后的結(jié)果：

其中，Es(g)的約束目標(biāo)是使不同視角下同一頂點(diǎn)調(diào)整后的顏色盡量接近，而Ei(g)的約束目標(biāo)是使相同視角下不同頂點(diǎn)的調(diào)整量盡量接近，λ為可調(diào)整系數(shù)。

5.3 泊松圖像編輯

對(duì)于縫隙比較嚴(yán)重的區(qū)域，全局顏色調(diào)整并不能保證完全去除縫隙，還需要作進(jìn)一步處理。泊松圖像編輯算法原理為對(duì)前景圖像和背景圖像進(jìn)行混合，使得融合后的圖像滿足：邊界上的像素值與背景圖像相同，前景區(qū)域內(nèi)的梯度與引導(dǎo)梯度場(chǎng)相同［57］。

這種方法最初用于圖像融合。如圖31 所示［57］，要將源圖像g插入到目標(biāo)圖像S的區(qū)域Ω中，該區(qū)域具有邊界?Ω，目標(biāo)圖像的像素值與像素坐標(biāo)的關(guān)系可表示為一個(gè)函數(shù)f*，而合成后的圖像在區(qū)域Ω中的像素值與像素坐標(biāo)關(guān)系用f描述，v代表一個(gè)引導(dǎo)梯度場(chǎng)，實(shí)際上是指源圖像g的梯度。其中，g、S、Ω、?Ω、f*、v都是已知量，而f是待求函數(shù)（融合后在區(qū)域Ω 中的圖像）。

Fig.31 Poisson image fusion圖31 泊松圖像融合示意圖

優(yōu)化的函數(shù)為：

其中，?f表示圖像融合后f的梯度，優(yōu)化目標(biāo)是使f邊界上的像素值與背景圖像相同，f的梯度與源圖像g的梯度v相同。求解以上優(yōu)化函數(shù)可以轉(zhuǎn)化為求解以下泊松方程：

其中，Δf表示f的拉普拉斯濾波結(jié)果，在某一像素處可以用相鄰像素線性表示，而divv==Δg，于是可將泊松方程轉(zhuǎn)化成Δf=Δg，用線性方程快速求解。泊松圖像融合效果如圖32所示［57］。

Fig.32 Effect of Poisson image fusion圖32 泊松圖像融合效果

進(jìn)行全局顏色調(diào)整后，只需在縫隙處進(jìn)行泊松編輯即可得到邊界平滑的紋理圖像。此外，可以通過控制內(nèi)部區(qū)域的范圍（如由當(dāng)前邊界往前景區(qū)域擴(kuò)充3 個(gè)像素作為前景進(jìn)行計(jì)算），從而減少計(jì)算復(fù)雜度。泊松圖像編輯還應(yīng)用于圖像拼接，如文獻(xiàn)［58］提出一種對(duì)無人機(jī)影像的拼接技術(shù)，取得了良好效果。

6 結(jié)語

與深度學(xué)習(xí)的三維重建方法相比，基于圖像的三維重建算法流程清晰，具有明確的中間結(jié)果，是典型的“白盒”模型，不需要預(yù)訓(xùn)練神經(jīng)網(wǎng)絡(luò)，對(duì)各種場(chǎng)景和物體適應(yīng)性強(qiáng)，可以全流程優(yōu)化改善，增強(qiáng)實(shí)現(xiàn)效果。但也存在計(jì)算速度慢、過分依賴于圖像特征點(diǎn)，且對(duì)弱紋理、朗伯面、纖細(xì)物體重建效果不佳等缺點(diǎn)。

鑒于以上不足，以下工作可能取得重要進(jìn)展：①圖像數(shù)據(jù)與視覺里程計(jì)、激光雷達(dá)等多傳感器信息融合，不再依賴于純圖像，增加信息來源，既提升運(yùn)算速度，又提高計(jì)算精度；②與深度學(xué)習(xí)方法相結(jié)合，實(shí)現(xiàn)在沒有圖像特征點(diǎn)或匹配對(duì)很少的情況下，得到相機(jī)的相對(duì)位置關(guān)系，并對(duì)弱紋理區(qū)域、朗伯面重建具有魯棒性；③算法軟件提升與基于GPU 的硬件加速相結(jié)合，提升算法運(yùn)行效率，逐步實(shí)現(xiàn)大場(chǎng)景下的實(shí)時(shí)三維重建。