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

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

0 引言

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

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

1 特征點檢測與匹配

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

1.1 Harris角點檢測

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

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

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

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

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

1.2 SIFT特征點檢測

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

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

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

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

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

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

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

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

Fig.2 Extremum point of the image圖2 圖像極值點

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

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

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

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

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

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

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

2 稀疏點云重建

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

2.1 基本概念

2.1.1 針孔相機模型

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

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

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

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

寫成齊次形式：

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

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

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

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

2.1.2 徑向畸變矯正

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

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

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

其中，k1、k2為徑向畸變系數(shù)，r為坐標(biāo)點到歸一化平面中心點的半徑?；兒蟮膱D像坐標(biāo)為：

在理想情況下：

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

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

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

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

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

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

Fig.6 Diagram of epipolar geometry圖6 對極幾何示意圖

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

設(shè)x1=(u1，v1，1)T，x2=(u2，v2，1)T為一對匹配的特征點，根據(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，則有：

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

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

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

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

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

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

（2）對匹配的特征點集中隨機采樣8 對，利用8 點法估計初始矩陣F。

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

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

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

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

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

同樣地，要對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 種情況中只有一種情況是空間點X同時位于兩個相機的鏡頭前方，因而只要用一個點做測試，看它是否位于兩個相機的前方，即可選擇出正確的相機姿態(tài)。

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

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

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

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

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

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

2.3 三角測量

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

2.3.1 直接線性變換法

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

兩邊同時叉乘xi，得：

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

2.3.2 RANSAC方法

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

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

2.4 PnP問題

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

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

P矩陣共有12 個參數(shù)，而一對3D-2D 對應(yīng)點能提供2個約束，因此至少需要6 對匹配點即可求解P。因為P[：，1：3]=KR，且K為上三角陣，而R為正交矩陣，可以對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］提出一種計算PnP 問題的Kneip 算法，利用三維點構(gòu)建一個平面作為過渡坐標(biāo)系，進(jìn)而求解相機的內(nèi)外參數(shù)。此外，同樣可以用RANSAC 方法實現(xiàn)Kneip 算法。求解PnP 問題還有其他幾種方法，如用4 對不共面的點進(jìn)行求解的P3P 方法［24］，利用4 對以上不共面或者3 對共面點進(jìn)行求解的ePnP 法［25］，以及利用深度學(xué)習(xí)與傳統(tǒng)方法相結(jié)合的EPro-PnP 方法［26］，實現(xiàn)端到端的三維位姿預(yù)測。

2.5 捆綁調(diào)整

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

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

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

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

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

2.5.1 最速下降法

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

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

算法流程如下：

Step1：給定初始點θ0，迭代終止閾值ε和步長λ，令t=0。

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

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

2.5.2 牛頓法

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

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

對θ求梯度令其為0，可得：

算法流程如下：

Step1：給定初始點θ0，迭代終止閾值ε和步長λ，令t=0。

Step2：計算?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 高斯—牛頓法

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

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

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

2.5.4 Levenberg-Marquardt法

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

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

Levenberg-Marquardt 法的主要流程為：

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

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

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

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

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

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

（2）圖像連接圖構(gòu)建。每一張圖像形成圖上的一個結(jié)點，具有特征匹配點的兩幅圖像之間有邊相連，結(jié)點的邊越多，表示與其具有匹配的特征點的其他圖像越多。從圖10 可以看出，白天和夜晚拍攝的圖像因為光度差異會在連接圖上形成兩個簇［33］。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 稠密點云重建

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

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

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

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

3.1 基于體素的方法

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

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

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

3.2 基于深度圖融合的方法

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

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

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

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

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

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

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

3.2.2 區(qū)域生長

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

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

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

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

3.2.3 深度圖融合

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

Fig.18 Diagram of consistent point selection圖18 一致點選擇示意圖

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

3.3 基于空間patch擴散的方法

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

重建流程如圖19所示。

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

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

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

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

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

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

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

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

4 三維表面重建

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

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

常用的三維表面重建方法有：基于二元分割的表面重建方法、基于符號距離場的表面重建方法。

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

其主要思想是將空間劃分成一組小單元（體素/四面體），采用二元分割思想將這些小單元劃分成內(nèi)部和外部兩類，介于內(nèi)部和外部之間的面即為物體表面，如圖20所示［43］。

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

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

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

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

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

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

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

Fig.21 Duality of Delaunay triangulation and Voronoi diagram圖21 德勞內(nèi)三角剖分與維諾圖的對偶關(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）是指對一特殊的有向加權(quán)圖的某些邊進(jìn)行切分，將圖分割為沒有交集的兩個部分，使得邊的權(quán)重?fù)p失最?。?6-48］。這一圖的特殊之處在于包含兩個特殊的節(jié)點：源節(jié)點和匯節(jié)點，其中源節(jié)點只有出邊，而匯節(jié)點只有入邊，如圖22 所示，邊的粗細(xì)表示權(quán)重大小，切分目標(biāo)是選取權(quán)重最小的邊切分。

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 基于符號距離場的表面重建方法

基于符號距離場的表面重建流程如圖25所示。

Fig.25 Surface reconstruction based on symbol distance field圖25 基于符號距離場的表面重建流程

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

4.2.1 空間劃分

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

4.2.2 符號距離場構(gòu)建

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

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

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

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

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

局部符號距離場結(jié)果如圖28所示［49］。

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

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

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

4.2.3 移動立方體算法生成表面

移動立方體算法（Marching Cube）最早由文獻(xiàn)［51］提出，在得到每個體素8 個頂點的符號距離值后，通過插值方法生成三角形面片，每個頂點有兩種狀態(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)所對應(yīng)的結(jié)果（其中3種情況），如圖30所示。

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

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

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

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

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

5.1 視角選擇

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

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

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

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

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

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

5.3 泊松圖像編輯

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

這種方法最初用于圖像融合。如圖31 所示［57］，要將源圖像g插入到目標(biāo)圖像S的區(qū)域Ω中，該區(qū)域具有邊界?Ω，目標(biāo)圖像的像素值與像素坐標(biāo)的關(guān)系可表示為一個函數(shù)f*，而合成后的圖像在區(qū)域Ω中的像素值與像素坐標(biāo)關(guān)系用f描述，v代表一個引導(dǎo)梯度場，實際上是指源圖像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ū)域擴充3 個像素作為前景進(jìn)行計算），從而減少計算復(fù)雜度。泊松圖像編輯還應(yīng)用于圖像拼接，如文獻(xiàn)［58］提出一種對無人機影像的拼接技術(shù)，取得了良好效果。

6 結(jié)語

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

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