基于分段式序列圖片集的運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)

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

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

2.上海宇航系統(tǒng)工程研究所，上海 201100

3.上海航天技術(shù)研究院，上海 201109

1 引言

運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)（SFM）是三維重建流程的第一步，也是最重要的一步。它計(jì)算每張圖片所對(duì)應(yīng)的相機(jī)的位置與朝向，在后續(xù)步驟中使用該參數(shù)計(jì)算三維點(diǎn)云的坐標(biāo)，而相機(jī)參數(shù)直接決定了三維重建的精度。SFM過(guò)程分為四部分：特征提取，特征匹配，姿態(tài)估計(jì)，參數(shù)優(yōu)化，這四部分共同決定SFM的重建速度與精度。

在通常的三維重建流程中，SFM使用一種增量式的方法[1-2]，逐個(gè)初始化相機(jī)姿態(tài)，每個(gè)新的相機(jī)姿態(tài)要根據(jù)之前已初始化的相機(jī)姿態(tài)進(jìn)行恢復(fù)，導(dǎo)致花費(fèi)的時(shí)間會(huì)隨著輸入圖片的數(shù)量增多而大幅增加。如表1所示，用Visual SFM[3]軟件對(duì)不同圖片集進(jìn)行稀疏重建所花費(fèi)的時(shí)間?？梢钥闯?，隨著圖片集數(shù)目的增大，重建時(shí)間增長(zhǎng)很快。同時(shí)，由于建筑物的正面視圖與背面視圖幾乎不同，它們之間的計(jì)算不但耗費(fèi)計(jì)算時(shí)間，還可能因?yàn)樵肼暥档椭亟ň?，這些圖片之間的計(jì)算是完全沒(méi)有必要的。

表1 重建時(shí)間與圖片集數(shù)量

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

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

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

隨著后續(xù)圖片的加入，相機(jī)參數(shù)誤差的漂移越來(lái)越大，對(duì)于閉合循環(huán)的圖片集，經(jīng)常會(huì)導(dǎo)致最后的閉合失敗，添加了BA優(yōu)化步驟也不一定能夠解決這一問(wèn)題。因?yàn)锽A優(yōu)化通常使用LM（Levenberg Marquard）方法最小化總重投影誤差，優(yōu)化結(jié)果很大程度上取決于初始圖片對(duì)的選擇和后續(xù)圖片的添加順序，容易收斂到局部最優(yōu)值。

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

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

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

本文提出了一種分段式的SFM方法，介紹了該方法的組成與實(shí)現(xiàn)，并通過(guò)實(shí)驗(yàn)分析了該方法在精度和速度方面與普通方法的優(yōu)劣性，最后說(shuō)明了該方法的不足之處與未來(lái)展望。

2 分段式運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)

考慮一個(gè)有序的圖片集，此處有序指圖片由相機(jī)環(huán)繞場(chǎng)景逐幀得到，相鄰圖片間存在一定的順序?qū)?yīng)關(guān)系。策略是把相機(jī)姿態(tài)朝向接近的圖片劃分到一個(gè)圖片集，將總圖片集分為多個(gè)互有交集的子圖片集，對(duì)子圖片集分別進(jìn)行獨(dú)立的重建（易于實(shí)現(xiàn)并行化），最后再將各模型之間共有的部分完成融合，進(jìn)行全局優(yōu)化。方法分為四個(gè)步驟：初始集合劃分，連接集合確定，稀疏重建合并，全局參數(shù)優(yōu)化。

圖3 初始集合劃分示意圖

2.1 初始集合劃分

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

為保證局部重建效果與全局合并效果，每個(gè)子圖片集需要有一定數(shù)量的圖片（最少圖片數(shù)），經(jīng)實(shí)驗(yàn)，本文將這個(gè)數(shù)量設(shè)置為8?？梢愿鶕?jù)CPU核數(shù)與線程數(shù)確定集合數(shù)，簡(jiǎn)單地可以一核一線程劃分為一個(gè)集合，當(dāng)劃分后的子圖片集中圖片數(shù)量大于8時(shí)，稱為大圖片集，反之稱為小圖片集。小圖片集可以根據(jù)圖片總數(shù)及每個(gè)集合8張圖片確定集合數(shù)。

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

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

然后計(jì)算剩余圖片數(shù)，最后將剩余圖片從最后一個(gè)集合往前逐集合加入：

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

2.2 連接集合確定

當(dāng)劃分好初始集合后，需要確定相鄰圖片集之間的連接關(guān)系，為獨(dú)立重建后的合并過(guò)程做準(zhǔn)備。

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

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

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

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

上述原理的偽代碼實(shí)現(xiàn)如下所示：

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

圖4 連接集合確定示意圖

2.3 稀疏重建合并

在連接集合確定之后，可以對(duì)每個(gè)集合進(jìn)行獨(dú)立SFM重建，得到每個(gè)集合的相機(jī)姿態(tài)。由于集合與相鄰集合之間存在相同圖片的相機(jī)姿態(tài)信息，可以根據(jù)此對(duì)所有圖片集進(jìn)行拼接。計(jì)算相鄰集合中相同圖片之間的相對(duì)旋轉(zhuǎn)矩陣，取均值后得到圖片集之間的旋轉(zhuǎn)矩陣，最后再經(jīng)過(guò)旋轉(zhuǎn)平移尺度變換等將所有圖片集轉(zhuǎn)換到同一坐標(biāo)系。

偽代碼實(shí)現(xiàn)如下：

end

備注：

（2）將圖片集Ni+1所有相機(jī)姿態(tài)使用旋轉(zhuǎn)到與Ni同一個(gè)坐標(biāo)系，最后所有圖片集與N1處于同一個(gè)坐標(biāo)系。

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

2.4 全局參數(shù)優(yōu)化

經(jīng)過(guò)稀疏重建合并后的模型只使用了簡(jiǎn)單的拼接，精度會(huì)比較低，需要用全局BA[14]進(jìn)行優(yōu)化。即將合并后的稀疏點(diǎn)云經(jīng)投影矩陣重投影回圖片中，計(jì)算投影位置與實(shí)際位置的誤差和，再使用非線性最小二乘算法最小化這個(gè)誤差和。公式為：

其中，Pi為第i張圖片的投影矩陣；Mj為第 j個(gè)重建3D點(diǎn)；n為重建的3D點(diǎn)個(gè)數(shù)；m為圖片數(shù)，mij為點(diǎn)Mj在圖i中對(duì)應(yīng)的二維點(diǎn)坐標(biāo)；ψ(PiMj)表示點(diǎn)Mj在圖片i中的投影。

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

3 實(shí)驗(yàn)結(jié)果與分析

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

圖5 旋轉(zhuǎn)矩陣計(jì)算示意圖

3.1 分段重建

以QingHua.D數(shù)據(jù)集為例，它包括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]。相似度的計(jì)算使用了開(kāi)源計(jì)算機(jī)視覺(jué)庫(kù)OpenCV的GPU_SURF模塊，添加連接集合后分為4個(gè)集合[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]，集合中的數(shù)字代表數(shù)據(jù)集中的圖片序號(hào)。添加連接集合后的第4個(gè)子圖片集如圖6所示。

圖6 QingHua.D數(shù)據(jù)集中第4個(gè)子圖片集

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

該方法能在全局優(yōu)化后獲得所有的姿態(tài)信息和相對(duì)位置關(guān)系，能成功完成閉合相機(jī)姿態(tài)的重建。而傳統(tǒng)SFM軟件可能會(huì)因?yàn)槠普`差而不能判斷相對(duì)位置關(guān)系，特別是正面背面較為相似的物體重建時(shí)，錯(cuò)誤更加明顯。圖9顯示了一種錯(cuò)誤的相機(jī)姿態(tài)，導(dǎo)致密集重建時(shí)背面部分不能正確重建。

3.2 定量對(duì)比

圖7 相機(jī)姿態(tài)合并示意圖

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

圖9 錯(cuò)誤的相機(jī)姿態(tài)重建

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

3.3 實(shí)驗(yàn)分析

實(shí)驗(yàn)結(jié)果表明，分段式SFM在時(shí)間效率上有較大提升。相較于普通SFM需要對(duì)整個(gè)圖片集進(jìn)行匹配重建，分段式SFM只需要對(duì)子圖片集內(nèi)的圖片進(jìn)行匹配重建，TMatch時(shí)間大大減少。TLBA所花費(fèi)的時(shí)間也隨著圖片集的增大，有著比較明顯的減少。因?yàn)樵谌諦A優(yōu)化中使用的方法為多核集束調(diào)整，所以花費(fèi)時(shí)間也較少。相比普通SFM，分段式SFM在大數(shù)據(jù)集上所花費(fèi)的時(shí)間大大減少，適合應(yīng)用于需要快速建模的大型場(chǎng)景中。

表2 增量式SFM與分段式SFM的運(yùn)行時(shí)間比較

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

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

4 結(jié)束語(yǔ)

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