基于分段式序列圖片集的運動恢復結構

羅 米，趙 霞，陳 萌，郭 松，倪穎婷

1.同濟大學 電子與信息工程學院（控制科學與工程系），上海 201804

2.上海宇航系統工程研究所，上海 201100

3.上海航天技術研究院，上海 201109

1 引言

運動恢復結構（SFM）是三維重建流程的第一步，也是最重要的一步。它計算每張圖片所對應的相機的位置與朝向，在后續步驟中使用該參數計算三維點云的坐標，而相機參數直接決定了三維重建的精度。SFM過程分為四部分：特征提取，特征匹配，姿態估計，參數優化，這四部分共同決定SFM的重建速度與精度。

在通常的三維重建流程中，SFM使用一種增量式的方法[1-2]，逐個初始化相機姿態，每個新的相機姿態要根據之前已初始化的相機姿態進行恢復，導致花費的時間會隨著輸入圖片的數量增多而大幅增加。如表1所示，用Visual SFM[3]軟件對不同圖片集進行稀疏重建所花費的時間。可以看出，隨著圖片集數目的增大，重建時間增長很快。同時，由于建筑物的正面視圖與背面視圖幾乎不同，它們之間的計算不但耗費計算時間，還可能因為噪聲而降低重建精度，這些圖片之間的計算是完全沒有必要的。

表1 重建時間與圖片集數量

為了加快SFM的重建速度，Schonberger等[4]提出了一種基于學習的圖片配對方法，通過訓練分類器將圖片配對編碼，實現成對圖片的快速重建，但需要進行額外的訓練步驟。Ni等[5]使用二分結構將SFM視圖轉化為相機超圖，然后根據遞歸分割得到子圖并形成樹狀結構，最后采用自底而上的優化方法，減輕了相機的初始化計算，但是由于額外添加了子圖，仍需要大量的BA優化。

另外，在增量式SFM中，首先基于兩張或三張圖片計算初始的相機姿態，使用五點法或六點法[6-7]，根據圖片間的特征點計算相應的相機外參數矩陣，然后以一張圖片的相機坐標系或自定義坐標系作為世界坐標系，隨后將新的圖片添加到世界坐標系中表示。該方法若不添加局部BA優化過程，會導致重建精度低下。圖1為使用增量SFM對噴泉圖片集進行重建的結果，（a）為噴泉圖片集中的四張圖片，（b）為經過BA優化的相機姿態圖片，（c）為不使用BA優化的相機姿態圖片，可以看出不使用BA優化會使重建結果遠離真實值。因此，為了確保能夠成功重建，需要在每次添加新圖片時使用局部BA進行優化，但是由于添加了大量的局部BA，又會導致效率低下。

圖1 增量SFM的噴泉圖片集重建示意圖

隨著后續圖片的加入，相機參數誤差的漂移越來越大，對于閉合循環的圖片集，經常會導致最后的閉合失敗，添加了BA優化步驟也不一定能夠解決這一問題。因為BA優化通常使用LM（Levenberg Marquard）方法最小化總重投影誤差，優化結果很大程度上取決于初始圖片對的選擇和后續圖片的添加順序，容易收斂到局部最優值。

圖2為閉合圖片集正常閉合和閉合失敗的例子，（a）為由于誤差積累，相機姿態右上角部分閉合失敗，（b）為閉合的相機姿態。

圖2 閉合圖片集重建示意圖

為了解決增量式方法中的漂移誤差，并提高效率，Sinha等[8]提出基于點和消失點對圖片進行匹配，最后進行全局相機姿態優化，不需要局部BA優化，但這種方法需要額外的消失點檢測算法。Cui等[9-12]提出了一種全局式的SFM。與增量式的方法相比，它同時恢復所有相機的位置與方向信息，考慮了全局誤差的均勻分布，不會產生誤差漂移，同時效率較高。但是這種方法的圖片集需要由三個相機得到，在圖片集中構成一定的約束關系，而且全局式的方法對抗噪聲的能力較差，容易因為圖像噪聲而產生錯誤的重建點，影響到全局相機位置恢復。

本文提出了一種分段式的SFM方法，介紹了該方法的組成與實現，并通過實驗分析了該方法在精度和速度方面與普通方法的優劣性，最后說明了該方法的不足之處與未來展望。

2 分段式運動恢復結構

考慮一個有序的圖片集，此處有序指圖片由相機環繞場景逐幀得到，相鄰圖片間存在一定的順序對應關系。策略是把相機姿態朝向接近的圖片劃分到一個圖片集，將總圖片集分為多個互有交集的子圖片集，對子圖片集分別進行獨立的重建（易于實現并行化），最后再將各模型之間共有的部分完成融合，進行全局優化。方法分為四個步驟：初始集合劃分，連接集合確定，稀疏重建合并，全局參數優化。

圖3 初始集合劃分示意圖

2.1 初始集合劃分

根據圖片集的數量和硬件的計算能力確定劃分的集合數。確定中心圖片：由于圖片集有序，隨機選取一張圖片作為中心圖片，根據集合數，其他集合的中心圖片也隨之確定，即初始圖片集劃分完畢。

為保證局部重建效果與全局合并效果，每個子圖片集需要有一定數量的圖片（最少圖片數），經實驗，本文將這個數量設置為8。可以根據CPU核數與線程數確定集合數，簡單地可以一核一線程劃分為一個集合，當劃分后的子圖片集中圖片數量大于8時，稱為大圖片集，反之稱為小圖片集。小圖片集可以根據圖片總數及每個集合8張圖片確定集合數。

設每個子圖片集基本圖片數量為n，中心圖片為Imid（mid∈[1,S]，S為集合數），M 為圖片集總數量，構成圖片集合Ni，在大圖片集中，有：

而在小圖片集中，需要首先確定集合數，有：

然后計算剩余圖片數，最后將剩余圖片從最后一個集合往前逐集合加入：

初始集合劃分示意圖如圖3所示：

2.2 連接集合確定

當劃分好初始集合后，需要確定相鄰圖片集之間的連接關系，為獨立重建后的合并過程做準備。

連接圖片的確定：本文使用SIFT（Scale Invariant Feature Transform）[13]算法提取并匹配中心圖片和連接圖片的特征點，再將經過隨機采樣一致性算法過濾后剩余的匹配點對數目作為相似度的量度，相似度高表明兩圖片對應的相機姿態較為接近，在獨立重建時匹配點對較多，重建精度也較高。首先計算相鄰圖片集連接處圖片與圖片集中心圖片的相似度，然后使用與中心圖片的相對相似度作為約束條件，滿足條件的定為連接圖片，最后將連接圖片集添加到各圖片集之中。

（1）針對相鄰圖片集，設第i個和i+1個圖片集的圖片數量都為n，將第i個圖片集的最后一張圖片Nni和第i+1個圖片集的第一張圖片加入連接圖片集，即：

（2）先計算第i+1個圖片集第一張圖片與第i個圖片集中心圖片的相似度，然后依次用第2張至第張圖片，計算其與第i個圖片集中心圖片的相似度。若當前圖片的相似度大于前一圖片相似度，則將此圖片加入中，繼續比較；若當前圖片的相似度小于上一圖片的相似度，則說明相似度呈下降趨勢，結束該步驟（例如先計算第一張圖片的相似度，再計算第二張圖片的相似度，若第二張圖片的相似度大于第一張，則將第二張圖片加入到連接圖片集中，然后計算第三張相對第二張的相似度，當相似度小于第二張時，退出當前步驟，反之繼續將第三張圖片加入連接圖片集）。

再計算第i個圖片集最后一張圖片與第i+1個圖片集中心圖片的相似度，然后依次用第n-1至n/2張圖片，計算其與第i+1個圖片集中心圖片的相似度。若當前圖片的相似度大于前一圖片相似度，則將此圖片加入中，繼續比較；若當前圖片的相似度小于上一圖片相似度，則結束該步驟。

上述原理的偽代碼實現如下所示：

連接集合確定示意圖如圖4所示。

圖4 連接集合確定示意圖

2.3 稀疏重建合并

在連接集合確定之后，可以對每個集合進行獨立SFM重建，得到每個集合的相機姿態。由于集合與相鄰集合之間存在相同圖片的相機姿態信息，可以根據此對所有圖片集進行拼接。計算相鄰集合中相同圖片之間的相對旋轉矩陣，取均值后得到圖片集之間的旋轉矩陣，最后再經過旋轉平移尺度變換等將所有圖片集轉換到同一坐標系。

偽代碼實現如下：

end

備注：

（2）將圖片集Ni+1所有相機姿態使用旋轉到與Ni同一個坐標系，最后所有圖片集與N1處于同一個坐標系。

（3）經過尺度變換、平移變換等，將所有子圖片集變換到同一尺度空間中，如圖5所示。

2.4 全局參數優化

經過稀疏重建合并后的模型只使用了簡單的拼接，精度會比較低，需要用全局BA[14]進行優化。即將合并后的稀疏點云經投影矩陣重投影回圖片中，計算投影位置與實際位置的誤差和，再使用非線性最小二乘算法最小化這個誤差和。公式為：

其中，Pi為第i張圖片的投影矩陣；Mj為第 j個重建3D點；n為重建的3D點個數；m為圖片數，mij為點Mj在圖i中對應的二維點坐標；ψ(PiMj)表示點Mj在圖片i中的投影。

本文提出的方法將集合分為多個子集合，子集合可以進行SFM并行處理，充分利用已有硬件條件，以提升重建速度。這種方法的重建精度不局限于最初的圖片對，每個子圖片集中，都是不同的初始化圖片，在最后全局BA優化中，更可能收斂到全局的最優值。

3 實驗結果與分析

本文使用兩類圖片數據集[15-16]進行實驗：第一類包括QingHua.D（33張）、Teaching.B（78張）、Science.B（102張）、ZhanTan.T（158張）4個數據集，由于這類數據集圖片數量比較多，用其進行了普通SFM和分段式SFM的時間效率比較實驗。第二類數據集包含Fountain（11張）、Herz-Jesu（25張）、Castle-L（30張）3個數據集，這類集合中包含每張圖片的真實相機姿態，可以用來評估普通SFM與分段式SFM的精度。

圖5 旋轉矩陣計算示意圖

3.1 分段重建

以QingHua.D數據集為例，它包括33張圖片。選取第二張圖片作為中心圖片，先劃分初始集合得到基本集合為[31 32 33 1 2 3 4 5]、[6 7 8 9 10 11 12 13]、[14 15 16 17 18 19 20 21]、[22 23 24 25 26 27 28 29 30]。相似度的計算使用了開源計算機視覺庫OpenCV的GPU_SURF模塊，添加連接集合后分為4個集合[30 31 32 33 1 2 3 4 5 6]、[5 6 7 8 9 10 11 12 13 14 15]、[13 14 15 16 17 18 19 20 21 22 23]、[21 22 23 24 25 26 27 28 29 30 31 32]，集合中的數字代表數據集中的圖片序號。添加連接集合后的第4個子圖片集如圖6所示。

圖6 QingHua.D數據集中第4個子圖片集

添加各子集的連接集合后，使用SFM同時進行重建，得到各集合的相機姿態信息，計算集合之間的相對旋轉變換矩陣R，將所有相機姿態使用R進行變換，再經過尺度、平移變換之后，并將所有的輸出轉化為CMVS（Clustering Views for Multi-view Stereo）[17]的要求輸入格式，最后進行PMVS（Patch-based Multi-view Stereo Software）[18]密集重建。圖7為相機姿態合并示意圖，圖8為合并后的重建模型示意圖。

該方法能在全局優化后獲得所有的姿態信息和相對位置關系，能成功完成閉合相機姿態的重建。而傳統SFM軟件可能會因為漂移誤差而不能判斷相對位置關系，特別是正面背面較為相似的物體重建時，錯誤更加明顯。圖9顯示了一種錯誤的相機姿態，導致密集重建時背面部分不能正確重建。

3.2 定量對比

圖7 相機姿態合并示意圖

圖8 合并后的重建模型示意圖

圖9 錯誤的相機姿態重建

本文使用的CPU為I5-6400核心，共4核4線程，顯卡為GTX1060，將集合數定為4。在第一類數據集中評估了普通SFM和分段式SFM的時間效率，如表2所示；在第二個數據集中包含了具體每張圖片的真實相機姿態，故使用第二個數據集評估了普通SFM和分段式SFM的精度，如表3所示。

3.3 實驗分析

實驗結果表明，分段式SFM在時間效率上有較大提升。相較于普通SFM需要對整個圖片集進行匹配重建，分段式SFM只需要對子圖片集內的圖片進行匹配重建，TMatch時間大大減少。TLBA所花費的時間也隨著圖片集的增大，有著比較明顯的減少。因為在全局BA優化中使用的方法為多核集束調整，所以花費時間也較少。相比普通SFM，分段式SFM在大數據集上所花費的時間大大減少，適合應用于需要快速建模的大型場景中。

表2 增量式SFM與分段式SFM的運行時間比較

表3 增量式SFM與分段式SFM的精度比較

在精度方面，由于是子圖片集獨立重建，漂移誤差較小，同時旋轉矩陣誤差與尺度、平移變換無關，Rerr誤差較普通方法有所減少。Terr誤差由于相鄰圖片集之間的連接圖片對應的相機位置有一定誤差，在經過尺度、平移變換后進行合并拼接時，需要對相機位置進行一定程度的近似處理，因此Terr誤差有所增加。而三維點經過變換后，同樣由于尺度、平移變換誤差等，導致MSEGBA有所增加。雖然部分誤差有所增加，但是仍然能夠完成密集重建，滿足大部分建模應用需求。

4 結束語

本文提出的方法適用于有序的閉合圖片集，重建速度較普通SFM有較大提升，同時重建精度與普通方法接近，適用于重建精度要求不是特別高的大型數據集的三維重建。接下來需要將整個方法拆分并進行模塊化，添加到三維重建流程中，同時可以考慮改進子圖片集的合并方法，結合點云匹配使用G-ICP（Generalized-Iterative Closest Point）算法，將文章中計算得到的旋轉矩陣與平移矩陣作為G-ICP算法的迭代初值，利用子模型間共有的部分進行點云融合，可以進一步提高重建結果的精度。