先簡單介紹一下三維重建（Structure from Motion，SfM）的流程。

1. 照片拍攝

如果想與地圖對齊，需要采集的圖像文件exif字段有g(shù)ps信息或者添加對應(yīng)的地面控制點（Ground Control Point）

2. 提取特征點

從照片中提取具有一定不變性的特征點，在多張照片中都能找到的特征點將被用于后續(xù)圖像匹配和全局模型生成。

常用的特征點提取算法有SIFT，SURF，ORB等。

3. 特征匹配

可以進行兩兩匹配，這樣會導(dǎo)致 N2的時間復(fù)雜度。

也可以基于時序信息或GPS位置進行匹配，這樣在照片很多的時候會顯著減少用時，但可能導(dǎo)致誤差積累。

成功匹配到足夠多特征點的照片將被認為有相鄰關(guān)系。每對成功匹配圖像之間將可以計算一組相對位置關(guān)系，用于表示相機從一張圖的拍攝位置到另一張圖的相對位置需要經(jīng)過怎樣的運動。這樣的運動通常可以表示為一個三維旋轉(zhuǎn)矩陣R和一個位移向量t。旋轉(zhuǎn)矩陣也可以用單位四元數(shù)緊湊表示。

4. 最優(yōu)化過程

理論上如果匹配關(guān)系是一條鏈，可以直接計算每個點的位置。但如果照片之間的匹配是一張“網(wǎng)”（數(shù)據(jù)結(jié)構(gòu)中的連通無向圖），則每張照片對應(yīng)的相機位置解算結(jié)果不是唯一的。雖然真實的相機位置是唯一的，但由于對同一個相機位置進行了多次觀測，一定會產(chǎn)生誤差。一般地，假設(shè)未知分布的誤差項服從高斯分布（同方差下高斯分布信息熵最大），因此構(gòu)造的三維點還原不重疊損失函數(shù)都是關(guān)于距離的平方的。此時最優(yōu)化類似于彈簧網(wǎng)（能量正比于誤差平方）的結(jié)構(gòu)。如果有外部位置信息，可以理解成彈簧網(wǎng)固連在建筑物上，因此最優(yōu)位置是確定的；如果沒有則只有“彈簧”之間的位置是有最優(yōu)解的，這張“彈簧網(wǎng)”在哪里則是可以任意解釋的，與最優(yōu)化過程無關(guān)。

解這種優(yōu)化問題的方法是建立優(yōu)化圖，構(gòu)造對應(yīng)的雅克比矩陣J和海森矩陣H。進行Gauss-Newton或Levenberg–Marquardt下降。這里有一些把有冗余的旋轉(zhuǎn)陣（李群）變成無冗余的向量（李代數(shù)）之類的數(shù)學(xué)技巧，就不過多介紹了。

經(jīng)過多次下降，一般會得到一個較接近最優(yōu)解的結(jié)果。

5. 點云生成

經(jīng)過最優(yōu)化，每張照片相機的位置和特征點對應(yīng)的空間位置已經(jīng)確定（這里注意，如果照片的exif信息沒有GPS位置，也沒有提供GCP的話，圖像中物體的大小是不知道的。此時SE（3）變換退化成Sim（3）變換）。可以重建較為稀疏的點云，將特征點的位置通過三角計算還原到3d空間中。

6. 點云稠密化及過濾

通過上一步的粗匹配和粗點云，逐步求精的細化局部，提取更多的特征（不一定是特征點，也可能是區(qū)域塊），進行匹配，得到較為稠密的點云。

一般的，一張圖像的SIFT/SURF特征點只有幾十個到幾百個。這種匹配是很魯棒的，但顯然即使這些點全部匹配上也不足以恢復(fù)任何有價值的圖形。這就需要稠密化點云，利用之前的相機位置姿態(tài)信息（后簡稱位姿）逐步求精的恢復(fù)出更稠密的點云。

由于是局部匹配，即使不使用SIFT，SURF等特別魯棒的算法，產(chǎn)生誤匹配的影響也不大。一般采用Patch Matching的方法一次匹一塊區(qū)域。經(jīng)過這步處理，模型的表面會產(chǎn)生許多三維頂點（Vertex）。這些頂點將出現(xiàn)在最終的三維模型中。

在特征點匹配和點云稠密化的過程中，一定會產(chǎn)生很多和模型本地沒關(guān)系的雜點。這些點分布在三維空間的各個位置，如不去除，將嚴重影響后面面片的生成（會產(chǎn)生很多很大的，形狀詭異的面，使模型無法觀看）。因此需要使用一些濾波算法，過濾掉明顯是錯誤的點。（如離主體建筑很遠，孤立在空中的一個或幾個點，在一個大凸包體內(nèi)的離其他點群較遠的點）

7. 三角剖分生成面片與面片精修

經(jīng)過上面的操作，我們已經(jīng)獲得了數(shù)目在幾萬個到幾千萬個之間的三維頂點（取決于圖像的數(shù)量和分辨率，場景的大小和紋理是否多變等）。此時通過Delaunay三角剖分，即可獲得一組均勻三角形，這組三角形將包含三維圖中的每一個頂點。這時場景的表面結(jié)構(gòu)將清晰可見，只是這些面片（Face）還沒有顏色，僅有頂點有顏色。

這時生成的面片可能較為粗糙，且包含較多雜散的不屬于物體的部分。可以使用一些精修算法精修這些面片，獲得更合理的模型。

8. 填充紋理

每個剖分得到的三角形將會對應(yīng)原圖像中一個部分。將這些部分裁剪下來，貼入對應(yīng)的小三角形，即可獲取顏色，紋理都較為逼真的三維模型。至此，三維還原重建的整個流程已經(jīng)走完。

責任編輯：lq6