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

1. 照片拍攝

如果想與地圖對齊，需要采集的圖像文件exif字段有gps信息或者添加對應的地面控制點（Ground Control Point）

2. 提取特征點

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

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

3. 特征匹配

可以進行兩兩匹配，這樣會導致 N2的時間復雜度。

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

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

4. 最優化過程

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

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

經過多次下降，一般會得到一個較接近最優解的結果。

5. 點云生成

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

6. 點云稠密化及過濾

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

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

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

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

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

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

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

8. 填充紋理

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

責任編輯：lq6