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

1. 照片拍攝

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

2. 提取特征點(diǎn)

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

常用的特征點(diǎn)提取算法有SIFT，SURF，ORB等。

3. 特征匹配

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

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

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

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

理論上如果匹配關(guān)系是一條鏈，可以直接計(jì)算每個(gè)點(diǎn)的位置。但如果照片之間的匹配是一張“網(wǎng)”（數(shù)據(jù)結(jié)構(gòu)中的連通無向圖），則每張照片對(duì)應(yīng)的相機(jī)位置解算結(jié)果不是唯一的。雖然真實(shí)的相機(jī)位置是唯一的，但由于對(duì)同一個(gè)相機(jī)位置進(jìn)行了多次觀測(cè)，一定會(huì)產(chǎn)生誤差。一般地，假設(shè)未知分布的誤差項(xiàng)服從高斯分布（同方差下高斯分布信息熵最大），因此構(gòu)造的三維點(diǎn)還原不重疊損失函數(shù)都是關(guān)于距離的平方的。此時(shí)最優(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)造對(duì)應(yīng)的雅克比矩陣J和海森矩陣H。進(jìn)行Gauss-Newton或Levenberg–Marquardt下降。這里有一些把有冗余的旋轉(zhuǎn)陣（李群）變成無冗余的向量（李代數(shù)）之類的數(shù)學(xué)技巧，就不過多介紹了。

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

5. 點(diǎn)云生成

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

6. 點(diǎn)云稠密化及過濾

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

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

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

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

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

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

這時(shí)生成的面片可能較為粗糙，且包含較多雜散的不屬于物體的部分?？梢允褂靡恍┚匏惴ň捱@些面片，獲得更合理的模型。

8. 填充紋理

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

責(zé)任編輯：lq6