許 彪，董友強(qiáng)，張 力，孫鈺珊，劉玉軒，查 冰，韓曉霞

1. 中國測繪科學(xué)研究院，北京 100830； 2. 北京建筑大學(xué)測繪與城市空間信息學(xué)院，北京 100044； 3. 北京市建筑遺產(chǎn)精細(xì)重構(gòu)與健康監(jiān)測重點(diǎn)實(shí)驗室，北京 100044； 4. 俄亥俄州立大學(xué)工程學(xué)院土木環(huán)境和大地測量系，美國 哥倫布 43210

運(yùn)動恢復(fù)結(jié)構(gòu)(structure from motion，SfM)是利用一組具有重疊的無序影像恢復(fù)相機(jī)姿態(tài)的同時獲得場景三維結(jié)構(gòu)信息的處理過程[1]。SfM對參與排列影像的初始位姿、拍攝方式、相機(jī)參數(shù)等均沒有嚴(yán)格的限制條件，具有良好的通用性。典型的SfM方法包括兩大類：全局式SfM[2-8](global SfM,GSfM)和增量式SfM[1,9-18](incremental SfM，ISfM)。

GSfM是將所有影像整體求解，先旋轉(zhuǎn)再平移，顯著減少了優(yōu)化的次數(shù)，但當(dāng)影像姿態(tài)、尺度或者畸變較大時會出現(xiàn)解算不穩(wěn)定，甚至解算失敗[19]。不同于GSfM,ISfM以初始影像對為基礎(chǔ)，漸進(jìn)式地增加影像并擴(kuò)充場景結(jié)構(gòu)，穩(wěn)健性較高[19-22]，當(dāng)前大規(guī)模影像的SfM解決方案也多采用ISfM框架，比如COLMAP[9]、VisualSfM[22]等。但I(xiàn)SfM也有其缺點(diǎn)，主要包括：①對初始像對的依賴性高，選取不同的初始像對可能會得到差異較大的重建結(jié)果；②大場景處理效率低，增量過程中每次添加單張影像，為了消除累積誤差，每次添加后都要執(zhí)行光束法平差，消耗了大量的時間；③難以兼容分布式并行處理。ISfM算法屬于串行模式，后續(xù)處理依賴前步結(jié)果，難以利用分布式并行計算節(jié)點(diǎn)提高效率。隨著影像獲取手段、效率的不斷提高，場景影像數(shù)據(jù)量不斷增加，以城市級三維建模的實(shí)際應(yīng)用來說，幾萬張甚至幾十萬張影像的超大場景已變得很普遍，傳統(tǒng)的ISfM方法越來越難以滿足大規(guī)模影像三維重建的應(yīng)用需求。

文獻(xiàn)[23—24]嘗試兼顧兩種算法各自的優(yōu)點(diǎn)，采用全局與增量的混合模式，提出基于分區(qū)與融合的混合式SfM方法，并將其應(yīng)用于商業(yè)軟件3DFZephyr。首先，將輸入影像劃分為多個重建單元，每個重建單元內(nèi)僅包含部分影像數(shù)據(jù)；然后，利用傳統(tǒng)的ISfM方法對每個分區(qū)單元進(jìn)行重建；最后，將不同分區(qū)單位的重建結(jié)果進(jìn)行融合得到完整的三維模型。通過將大影像集劃分為多個計算單元，無論是分區(qū)重建還是融合過程，均可將其分配至多個計算節(jié)點(diǎn)實(shí)現(xiàn)分布式并行。這種做法不僅提高計算效率，而且避免了過多的參數(shù)的同時求解。但是，目前影像分區(qū)與融合方法研究還在起步階段，一旦出現(xiàn)錯誤分區(qū)或不可靠分區(qū)重建結(jié)果，會嚴(yán)重影響最終重建精度，限制了當(dāng)前混合式SfM方法在不同影像數(shù)據(jù)集上的應(yīng)用。

為充分挖掘混合式SfM的優(yōu)勢，實(shí)現(xiàn)大規(guī)模無序影像的穩(wěn)定快速高精度稀疏三維重建，本文提出分區(qū)優(yōu)化的混合式SfM方法。具體內(nèi)容包括：

(1) 提出一種基于影像關(guān)聯(lián)度的分區(qū)方法，無須GPS/INS等其他輔助信息，僅利用影像間的匹配結(jié)果計算得到的關(guān)聯(lián)度實(shí)現(xiàn)場景分區(qū)。

(2) 提出一種改進(jìn)的快速增量式SfM方法(improved-ISfM)，每次重建多張影像，實(shí)現(xiàn)分區(qū)內(nèi)影像的快速重建。在重建過程中，提出一種不可靠分區(qū)的自動檢測方法，自動剔除不穩(wěn)定分區(qū)，并將這些分區(qū)內(nèi)的影像進(jìn)行動態(tài)調(diào)整，重新劃分入相鄰分區(qū)。

(3) 提出一種穩(wěn)健可靠的分區(qū)融合方法。利用分區(qū)間的公共地面點(diǎn)計算兩兩分區(qū)間的空間三維線性變換參數(shù)，利用變換參數(shù)將小分區(qū)合并成大分區(qū)，大分區(qū)合并成更大的分區(qū)，逐步獲得完整的場景重建結(jié)果。同時，針對不同分區(qū)中可能包含同一相機(jī)拍攝影像的情況，采用了一種先融合場景后融合相機(jī)的策略，實(shí)現(xiàn)了相機(jī)參數(shù)、影像姿態(tài)和恢復(fù)三維信息的統(tǒng)一。多組具有挑戰(zhàn)性的典型數(shù)據(jù)試驗表明所提方法能夠自適應(yīng)于不同影像類型、不同場景和不同規(guī)模的影像數(shù)據(jù)，大大提高了重建效率的同時保證了較高的精度，尤其適用于包含幾萬甚至幾十萬張影像的大場景影像數(shù)據(jù)集。

1 基于分區(qū)優(yōu)化的混合式SfM

借鑒攝影測量解析空三分區(qū)“接邊”的思路，本文提出一種基于分區(qū)優(yōu)化的混合式SfM方法。解析空三通常在兩個“接邊”區(qū)域量測公共的地面控制點(diǎn)并重疊少量影像，以提高接邊處的加密精度，而本文方法即使在分區(qū)間不存在重疊影像時，也可完成重建過程。具體算法流程如圖1所示，其中圖1(a)為本文所提方法的整體技術(shù)流程，圖1(b)為圖1(a)中所使用的ISfM方法流程。不同于傳統(tǒng)ISfM的是，本文的ISfM中分區(qū)動態(tài)調(diào)整的影像是從后方交會步驟開始。

圖1 整體算法流程Fig.1 Overallflow chart of theproposed method

1.1 基于影像關(guān)聯(lián)度的場景分區(qū)

場景分區(qū)將整個場景影像劃分為多個存在關(guān)聯(lián)的小塊，分區(qū)過程無須飛行架次、GPS/INS等輔助信息，僅利用影像間的匹配結(jié)果。首先，利用SIFT[25]算法對影像對進(jìn)行匹配，利用文獻(xiàn)[26—27]所述方法找到待匹配影像對，并根據(jù)匹配點(diǎn)個數(shù)和點(diǎn)位分布計算兩兩影像間的關(guān)聯(lián)度得分。其次，將場景中每張影像看作一個獨(dú)立的分區(qū)，合并其鄰域內(nèi)關(guān)聯(lián)度得分最高的同名影像，完成初次劃分，此時每個分區(qū)內(nèi)應(yīng)包含至少兩張影像。然后，取不同分區(qū)間影像關(guān)聯(lián)度得分的最大值作為兩個分區(qū)的關(guān)聯(lián)度得分，依次合并關(guān)聯(lián)度最大的兩個分區(qū)，重復(fù)此過程，獲得初始分區(qū)結(jié)果。最后，剔除弱連接分區(qū)，動態(tài)調(diào)整后完成整個場景分區(qū)。如圖2所示，圖2(a)為分區(qū)過程，場景影像經(jīng)初次劃分后，得到n個分區(qū)，根據(jù)關(guān)聯(lián)度得分將這n個分區(qū)進(jìn)行重新劃分，合并關(guān)聯(lián)最好的分區(qū)后得到包含m個分區(qū)的初始分區(qū)結(jié)果，經(jīng)弱連接分區(qū)剔除后最終得到圖2(b)所示的6個分區(qū)，圖中每個方框圈定的區(qū)域代表一個分區(qū)，區(qū)域面積的差異描述為各分區(qū)包含不同的影像數(shù)，分區(qū)間無重疊影像。

圖2 場景分區(qū)Fig.2 The scene partition

算法具體過程描述如下：

(1) 計算影像間關(guān)聯(lián)度得分，分?jǐn)?shù)的高低表征影像與其鄰域的關(guān)聯(lián)程度。設(shè)影像對同名像點(diǎn)數(shù)量hnum，按像幅劃分格網(wǎng)(如10×10)，如果同名點(diǎn)落在某個格網(wǎng)內(nèi)，則格網(wǎng)內(nèi)數(shù)值累加1，所有同名點(diǎn)劃分完畢后，累加值小于閾值的格網(wǎng)為無效格網(wǎng)。如圖3所示，藍(lán)色圓圈為有效格網(wǎng)，粉色圓圈為無效格網(wǎng)。統(tǒng)計有效格網(wǎng)內(nèi)像點(diǎn)的外接矩形面積S(圖3中紅色框選區(qū)域)，S與像幅面積的比值即為scoredistribute。按照式(1)計算影像間的關(guān)聯(lián)度得分corr

圖3 點(diǎn)位分布得分Fig.3 Point distribution score diagram

(1)

式中，pairhleft、pairhright為左右影像構(gòu)成的像對中最多同名點(diǎn)數(shù)；w1和w2為權(quán)重(本文選取0.7和0.3的經(jīng)驗值)。

(2) 影像初劃分。統(tǒng)計每張影像關(guān)聯(lián)度得分最高的一張同名影像，按分?jǐn)?shù)從高到低排列，遍歷排序結(jié)果，依次將未分區(qū)的影像與得分最高的同名影像劃分到同一個分區(qū)。

(3) 遍歷循環(huán)完成初始分區(qū)。分區(qū)間同名影像關(guān)聯(lián)度得分最大值定義為兩個分區(qū)的關(guān)聯(lián)度得分，類似步驟(2)方法將小分區(qū)逐步合并為大分區(qū)，重復(fù)此過程，得到場景的初始分區(qū)結(jié)果。為了避免分區(qū)內(nèi)影像過多或過少的情況出現(xiàn)，預(yù)設(shè)分區(qū)內(nèi)影像數(shù)閾值范圍(如15～75)，如小于閾值，將其劃歸至關(guān)聯(lián)度得分最高的分區(qū)中，如大于閾值，回溯分區(qū)影像匯聚過程，將其拆分成兩個或更多個滿足閾值的分區(qū)。

(4) 剔除不可靠分區(qū)。統(tǒng)計兩兩分區(qū)間的公共地面點(diǎn)數(shù)量及分區(qū)與其鄰域的點(diǎn)數(shù)最大值，排序所有分區(qū)的統(tǒng)計最大值，選取0.25倍的中值作為閾值，如某分區(qū)與其鄰域的公共點(diǎn)數(shù)小于閾值，視為弱連接分區(qū)將其剔除，影像重新劃分至其他分區(qū)中。至此，得到場景分區(qū)結(jié)果。

圖4為一組包含372張低空攝影影像的數(shù)據(jù)。圖4(a)為影像攝站點(diǎn)的平面位置圖，粉色圈定的兩張影像為ISfM選取的初始像對；圖4(b)為場景分區(qū)結(jié)果。從結(jié)果可以看出，整個場景共劃分為7個分區(qū)，不同分區(qū)利用不同顏色加以區(qū)分，每個分區(qū)內(nèi)圈定的兩張影像為選定的初始像對。

圖4 實(shí)際數(shù)據(jù)的場景分區(qū)結(jié)果Fig.4 Partition result of actual data

1.2 獨(dú)立分區(qū)執(zhí)行改進(jìn)ISfM

不同于傳統(tǒng)的ISfM每次添加一張影像，本文通過每次添加多張影像，提出了Improved-ISfM算法，大大提高了每個分區(qū)內(nèi)重建的效率。整體流程如圖1(b)所示，具體如下：①選取兩張影像作為初始像對，估計影像相對位姿和結(jié)構(gòu)信息；②統(tǒng)計所有剩余影像后方交會的有效點(diǎn)數(shù)并排序，點(diǎn)數(shù)大于0.25倍中值的影像作為備選影像，然后統(tǒng)計備選影像進(jìn)行前方交會得到的有效點(diǎn)數(shù)并排序，大于0.5倍中值的影像將增加至場景，完成新添加影像的位姿估計(image registration)；③前方交會得到更多的結(jié)構(gòu)信息(triangulation)，增大場景的覆蓋范圍；④光束法優(yōu)化使得重投影誤差和最?。虎葸^濾掉不可靠的外點(diǎn)(outlier filtering)，通常情況下，光束法優(yōu)化和外點(diǎn)過濾均需循環(huán)執(zhí)行多次，光束法優(yōu)化后過濾外點(diǎn)，利用過濾結(jié)果再進(jìn)行光束法優(yōu)化，提高重建精度。循環(huán)②—⑤步直至無法增加更多影像至場景中為止。

考慮到影像匹配精度、地形起伏、飛行方式、相機(jī)檢校特性及其他不確定性因素，為保證完整重建結(jié)果的正確性，需進(jìn)一步檢測相互獨(dú)立的分區(qū)重建結(jié)果，剔除可能存在的不穩(wěn)定項，具體包含以下幾個方面：

(1) 統(tǒng)計誤差過大的分區(qū)。選用點(diǎn)位平均誤差MSE作為統(tǒng)計指標(biāo)，即分區(qū)內(nèi)有效點(diǎn)點(diǎn)位誤差的平均值，取所有分區(qū)MSE中值的2.0倍作為閾值，刪除MSE大于閾值的分區(qū)。

(2) 相機(jī)檢校參數(shù)不可靠的分區(qū)。如果分區(qū)結(jié)果正確，不同分區(qū)中同源相機(jī)的檢校參數(shù)(包括焦距、主點(diǎn)、畸變參數(shù))應(yīng)表現(xiàn)出大體一致的結(jié)果，剔除包含異常檢校結(jié)果的分區(qū)。

(3) 成功排列影像占比低的分區(qū)。如果某分區(qū)內(nèi)成功排列的影像數(shù)與總數(shù)比值小于閾值(如0.5)，認(rèn)為重建結(jié)果不可靠，將其剔除。

(4) 弱關(guān)聯(lián)分區(qū)。實(shí)際應(yīng)用中，考慮到匹配粗差、相機(jī)檢校、幾何條件等因素的綜合作用，不能保證重建后的每個分區(qū)間依然存在足夠的公共地面點(diǎn)，參照2.1節(jié)中剔除弱連接分區(qū)策略，剔除可能存在的孤立分區(qū)。

將被剔除分區(qū)涉及的影像和其他未成功排列的影像追加至其他分區(qū)中，實(shí)現(xiàn)分區(qū)的動態(tài)調(diào)整，增加特定影像至指定的分區(qū)后，從后方交會開始執(zhí)行ISfM流程完成影像排列。上述算法策略不僅降低了ISfM對初始像對的高依賴性，而且通過選取多個初始像對降低了重建失敗的風(fēng)險。與此同時，由于分區(qū)動態(tài)調(diào)整后額外重建所需的計算量不大，不會降低整體效率，避免了傳統(tǒng)ISfM中因重選初始像對而必須放棄所有已完成重建結(jié)果的問題。

1.3 光束法融合場景分區(qū)

場景不同分區(qū)重建結(jié)果存在坐標(biāo)系和比例尺不一致的問題，需通過融合獲得統(tǒng)一坐標(biāo)系和比例尺下的完整重建結(jié)果。本文利用重建后分區(qū)間的公共地面點(diǎn)，采用循環(huán)的方式，將小分區(qū)逐步融合成大分區(qū)，完成分區(qū)融合，具體過程如圖1(a)右側(cè)融合循環(huán)部分所示。

(1) 計算兩兩分區(qū)間的空間三維相似變換參數(shù)。通過分區(qū)間公共的地面點(diǎn)計算兩兩分區(qū)的三維線性變換7參數(shù)，統(tǒng)一待融合分區(qū)的坐標(biāo)系和比例尺。

(2) 確定待融合的分區(qū)。任一分區(qū)可能鄰接多個分區(qū)，且分區(qū)間的公共地面點(diǎn)數(shù)量通常不一致，需設(shè)計合理的策略，在保證算法穩(wěn)健性的同時確保每個分區(qū)均參與合并。視每個分區(qū)與其鄰域有效點(diǎn)數(shù)累加和為關(guān)聯(lián)性指標(biāo)，按從小到大順序排列，簡記為S1、S2、…、Sx，優(yōu)先融合關(guān)聯(lián)度指標(biāo)小的分區(qū)。首先，選取S1作為基準(zhǔn)，有效點(diǎn)數(shù)最多的Si與其融合，標(biāo)記S1和Si為已處理；然后，對于尚未標(biāo)記的Sj，設(shè)其有效點(diǎn)數(shù)最多的為Sk，若Sk已標(biāo)記，則將Sj追加至Sk的融合列表中，否則Sj與Sk融合，并標(biāo)記為已處理分區(qū)；最后，不斷重復(fù)該過程，直至所有分區(qū)被標(biāo)記，得到了融合任務(wù)列表。

(3) 確定融合分區(qū)影像位姿和結(jié)構(gòu)信息坐標(biāo)初值。步驟(1)中僅計算了兩兩分區(qū)間的變換參數(shù)，假如融合任務(wù)僅涉及兩個分區(qū)，可任選其中一個為基準(zhǔn)，將另一個變換至基準(zhǔn)分區(qū)即可。當(dāng)存在3個及以上分區(qū)需融合至一起時，選取關(guān)聯(lián)性指標(biāo)最大的分區(qū)為基準(zhǔn)，如果其他分區(qū)與基準(zhǔn)存在有效的變換參數(shù)時，直接將其變換至基準(zhǔn)分區(qū)。當(dāng)某分區(qū)與基準(zhǔn)分區(qū)無法直接變換時，則根據(jù)空間相似變換的剛體特性及兩兩間的變換參數(shù)，以傳遞的方式通過多次變換將其轉(zhuǎn)換至基準(zhǔn)分區(qū)。

(4) 光束法優(yōu)化。場景分區(qū)時，多張同相機(jī)的影像可能會被劃分至不同的分區(qū)中，導(dǎo)致同一相機(jī)在不同分區(qū)中得到不同的檢校參數(shù)。為了保證融合后參數(shù)的唯一性，遵循先融合場景再融合相機(jī)的原則。融合場景時每個分區(qū)的相機(jī)檢校參數(shù)相互獨(dú)立，光束法優(yōu)化影像位姿和結(jié)構(gòu)信息坐標(biāo)。融合相機(jī)則是將同一相機(jī)的多套檢校參數(shù)合并為一套，即選取或重新估計一套檢校參數(shù)作為初值，再進(jìn)行光束法優(yōu)化，使得相機(jī)檢校參數(shù)唯一。前述過程為一個融合循環(huán)，不斷重復(fù)該過程，直至所有分區(qū)融合成完整場景為止。

需要說明的是，為了提高融合算法的穩(wěn)健性同時保證分區(qū)融合結(jié)果的精度，本文采用了兩種優(yōu)化方案。①步驟(3)獲取初值時，首先確定影像的位姿，然后通過多片前方交會計算結(jié)構(gòu)信息的初值，用于提高初值精度。②步驟(4)光束法優(yōu)化時，采用執(zhí)行多次的策略，每執(zhí)行一次光束法優(yōu)化后，還需進(jìn)行外點(diǎn)過濾及新插入2D、3D點(diǎn)的處理。一方面，降低外點(diǎn)對光束法優(yōu)化結(jié)果的影響；另一方面，場景中新增的2D、3D點(diǎn)可進(jìn)一步改善平差網(wǎng)的幾何條件，有助于提高平差精度。

圖5為圖4所示數(shù)據(jù)的融合過程。7個分區(qū)各自完成重建處理后，利用分區(qū)間的公共地面點(diǎn)進(jìn)行兩次融合。圖5(a)為影像的融合過程，第1次融合時將左側(cè)圖中的①④、②③⑥、⑤⑦融合成3個分區(qū)，再將右側(cè)圖中的①②③融合成完整的場景。圖5(b)為結(jié)構(gòu)的融合過程。為便于顯示，已將每個分區(qū)的結(jié)果轉(zhuǎn)換至比例尺一致且原點(diǎn)統(tǒng)一的坐標(biāo)系下。

圖5 實(shí)際數(shù)據(jù)描述的分區(qū)融合過程Fig.5 Fusion process of actual data

需要注意的是，因受多種因素的影響或干擾，融合可能會發(fā)生失敗。為了保證算法的穩(wěn)健性，出現(xiàn)融合失敗時，按前文所述分區(qū)動態(tài)調(diào)整的策略進(jìn)行處理。實(shí)際上本文的分區(qū)僅僅是在邏輯上指定了影像的“歸屬”，每張影像仍然可以靈活歸入其他存在關(guān)聯(lián)的分區(qū)中。

1.4 分布式并行

無論是分區(qū)ISfM還是融合分區(qū)，每一步均是相互獨(dú)立的過程，因此可將每個處理過程分配至多個計算節(jié)點(diǎn)，實(shí)現(xiàn)分布式并行處理，以提高大場景的處理效率?；镜牟⑿姓{(diào)度方案設(shè)計包括主機(jī)端和計算節(jié)點(diǎn)端。主機(jī)端負(fù)責(zé)數(shù)據(jù)組織、場景分區(qū)、確定融合任務(wù)列表、計算任務(wù)劃分、分區(qū)動態(tài)調(diào)整與結(jié)果回收。計算節(jié)點(diǎn)端負(fù)責(zé)接受主機(jī)端指定的任務(wù)，包括單獨(dú)分區(qū)重建和分區(qū)間融合兩部分，同時將計算結(jié)果返還至主機(jī)端。

2 試驗與結(jié)果分析

2.1 試驗數(shù)據(jù)和環(huán)境

為了驗證本文算法的有效性和實(shí)際性能，選取低空攝影、多視傾斜攝影和近景等共計5組試驗數(shù)據(jù)。如圖6所示，試驗場景覆蓋了環(huán)拍辦公樓、狹長河道、城區(qū)和城區(qū)山地混合地形等多種地形，同時影像數(shù)量、連接點(diǎn)平均重疊度和地面分辨率均不相同。場景A為辦公樓，利用SONY NEX-7相機(jī)環(huán)繞拍攝獲取的204張近景影像，GSD為1.5 cm；場景B為長春某校園，利用大疆精靈3拍攝獲取了1292張低空影像，GSD為4.8 cm；場景C為10 km長的漢北河分支河道，利用大疆精靈4拍攝13架次獲取了4099張低空影像，GSD為5 cm，因存在拍攝間隔，按飛行架次定義了13組相機(jī)；場景D為城區(qū)和山地混合的四川省某市，利用SONY ILCE-5100z相機(jī)獲取了29 754張5視傾斜影像，GSD為2 cm；場景E為建筑物密集的江蘇省某市城區(qū)，利用SONY ILCE-5100z相機(jī)獲取了121 506張5視傾斜影像，GSD為5 cm。

圖6 本文試驗數(shù)據(jù)影像截圖Fig.6 Screenshot of test data sets

表1 試驗數(shù)據(jù)概況Tab.1 Basic information of test data sets

所有試驗均在如下配置的計算機(jī)上進(jìn)行：操作系統(tǒng)為Windows10 64位專業(yè)版，處理器為Intel(R) Xeon(R) CPU E5 2.4 GHz 2處理器24核，內(nèi)存為64 GB，顯卡為Quadro K2200。

2.2 分區(qū)數(shù)量對算法效率的影響

為了評估本文方法中分區(qū)影像數(shù)大小對處理效率的影響，分別選取了[15,75]、[25,100]和[50,125]3種預(yù)設(shè)范圍進(jìn)行試驗。統(tǒng)計結(jié)果如表2所示，每組試驗場景3種分區(qū)大小的效率對比如圖7所示。

圖7 不同分區(qū)大小下處理效率對比Fig.7 Comparison of processing efficiency under different partition sizes

表2 不同分區(qū)大小下處理效率統(tǒng)計Tab.2 Comparison of processing efficiency under different partition sizes

(1) 本文方法重建精度與分區(qū)影像數(shù)預(yù)設(shè)范圍無關(guān)。試驗中，3種不同預(yù)設(shè)范圍下，5組場景的重建精度一致，其中，場景C的1和2試驗最大差異為0.01像素，場景分區(qū)大或小僅是將高關(guān)聯(lián)度得分的同名影像劃分多與少的問題，每個分區(qū)的內(nèi)部幾何條件均較為理想，并沒有改變整個網(wǎng)形的幾何條件，即便存在部分初始劃分不合理的情況，分區(qū)動態(tài)調(diào)整機(jī)制的使用，也會將不合理部分修正，不會引起精度的明顯差異。

(2) 分區(qū)影像數(shù)預(yù)設(shè)范圍與處理效率無關(guān)。對于影像數(shù)較少的場景A、B、C來說，可認(rèn)為處理效率一致。效率差異最大的為場景E的試驗1和2，相差87 min。以試驗1為參考，試驗2效率提升5%，但是隨著預(yù)設(shè)范圍的增大，處理效率并沒有得到進(jìn)一步提升。其原因主要是因為分區(qū)與融合作為一個整體性的算法，不能簡單地按兩步拆分去看待，分區(qū)數(shù)的減少使得分區(qū)重建的處理時間增多。盡管融合循環(huán)及每次循環(huán)的融合次數(shù)減少了，但更多影像的融合使得光束法優(yōu)化計算量也更大，還不足以明顯提升效率。

2.3 對比試驗分析

為驗證本文方法的有效性，設(shè)計了3組對比試驗。為了驗證improved-ISfM方法的精度和效率，試驗1對比了采用ISfM方法的著名開源軟件COLMAP和本文提出的improved-ISfM方法；試驗2對比了本文方法(包含整個算法流程)和improved-ISfM的精度和效率，由于本文算法內(nèi)的分區(qū)重建內(nèi)采用了improved-ISfM方法，因此結(jié)果的不同來源于所采用分區(qū)融合框架，該試驗驗證了分區(qū)融合策略的性能；試驗3將本文方法與商業(yè)軟件AgisoftPhotoscan(V 1.6.1)和3DF Zephyr Aerial(V 4.519)進(jìn)行了對比，其中3DFZephyr Aerial采用了混合式SfM，可以與本文的混合式SfM方法進(jìn)行更直接的對比。為方便起見，將以上兩個軟件分別簡稱為Photoscan和3DF。

2.3.1 試驗1：COLMAP與Improved-ISfM對比

表3給出了對比試驗結(jié)果。從結(jié)果可以看到，improved-ISfM精度明顯優(yōu)于COLMAP。在重建連接點(diǎn)更多的情況下，improved-ISfM對場景A、B、C的處理效率分別是COLMAP方法的6.93、4.42和7.93倍。效率提升的主要原因是improved-ISfM在每次增量過程中都加入了更多的影像和結(jié)構(gòu)信息，進(jìn)而改善了用于光束法優(yōu)化的網(wǎng)形條件。這種做法在減少迭代次數(shù)加快收斂的同時，降低了外點(diǎn)過濾和光束法優(yōu)化的循環(huán)次數(shù)。圖8描述了improved-ISfM中連接點(diǎn)平均重疊度與每次增量增加影像數(shù)的關(guān)系?？梢钥吹?，算法效率與連接點(diǎn)平均重疊度和攝影方式兩個因素有關(guān)。連接點(diǎn)平均重疊度越大，表征影像間的關(guān)聯(lián)性越強(qiáng)，每次增量處理能夠插入更多的影像，處理效率也會更高。

表3 COLMAP與Improved-ISfM重建對比Tab.3 Reconstruction comparison between COLMAP and Improved-ISfM

圖8 Improved-ISfM平均每次增加影像數(shù)與連接點(diǎn)平均重疊度的變化關(guān)系Fig.8 The correlation between the average number of images addedeachtime and average overlap of connection points of improved-ISfM

2.3.2 試驗2：本文算法與improved-ISfM對比

為了驗證分區(qū)融合策略的性能，分別應(yīng)用improved-ISfM方法以及本文方法分別處理整個數(shù)據(jù)集。表4給出了對比試驗結(jié)果，從中可以看到：

表4 本文方法與improved-ISfM重建對比Tab.4 Reconstruction comparison between proposed methodandimproved-ISfM

(1) 本文方法能夠適用于各種類型的場景。試驗數(shù)據(jù)包括近景、低空攝影、傾斜攝影3種類型，包括山區(qū)、城區(qū)、河道、環(huán)拍建筑物、植被覆蓋等場景，影像數(shù)從204張到12萬張，尤其是試驗場景C，狹長形狀且飛行架次間存在弱連接區(qū)域，所提算法均能得到可靠的重建結(jié)果，說明了算法具有良好的穩(wěn)健性，適用于各種類型的場景數(shù)據(jù)。

(2) 本文方法與improved-ISfM精度基本保持一致。最大的精度差別僅有0.05像素(場景A)，這種細(xì)微的差別主要是由初值差異、坐標(biāo)系定義、部分臨界誤差像點(diǎn)、計算舍與誤差、RANSAC算法等因素造成的。

(3) 對于包含影像數(shù)較少的場景，本文方法與improved-ISfM效率差異不大。如圖9所示，對于場景A和B，兩種方法的單位處理時間對比分別為1∶1.25和1∶1.31，相差較小。其主要原因是，ISfM增量處理過程中，每次新增影像和結(jié)構(gòu)信息后，光束法優(yōu)化所需計算開銷有限，因此對整體效率的影響不顯著。

圖9 不同場景影像數(shù)下本文方法與improved-ISfM處理效率對比Fig.9 Comparison of processing efficiency under different number of scene images

(4) 對于大數(shù)量影像集，本文方法具有明顯的效率優(yōu)勢。隨著場景影像數(shù)的不斷增加，本文方法效率顯著提升。相較于improved-ISfM方法，本文方法在場景C、D、E上效率分別提升1.79、2.85和5.05倍?？梢灶A(yù)見的是，當(dāng)場景影像規(guī)模進(jìn)一步增大時，本文方法的效率優(yōu)勢會更加明顯，這是由于增加的影像僅會增加分區(qū)和融合的時間開銷，不會導(dǎo)致處理時間的顯著增長。

2.3.3 試驗3：本文方法與商業(yè)軟件對比試驗

分別利用Photoscan和3DF處理前述試驗場景，其中場景A、B和C，利用3.1節(jié)所述配置計算機(jī)進(jìn)行處理。由于Photoscan和3DF在此配置下無法進(jìn)行重建，故利用內(nèi)存擴(kuò)大至128 GB且其他配置相同的計算機(jī)進(jìn)行處理。此時，Photoscan依然無法獲得場景E的重建結(jié)果，而3DF無法獲得場景D和E的重建結(jié)果。

試驗過程中，Photoscan參數(shù)設(shè)置采用該軟件推薦的默認(rèn)設(shè)置，具體描述為：accuracy(high)、generic preselection、key point limit(40 000)及tie point limit(4000)。3DF利用高級設(shè)置，具體參數(shù)為：關(guān)鍵點(diǎn)密度(高)、匹配類型(精確)、匹配階段深度(高)、照片排序(未排序)。表5給出了對比分析試驗結(jié)果，每個指標(biāo)最好的結(jié)果進(jìn)行了加粗顯示。由表5可以看出：

表5 不同方法對比試驗結(jié)果Tab.5 Comparative experimental resultsof different methods

(1) 本文方法兼具精度和穩(wěn)健性優(yōu)勢。僅有本文方法成功處理了所有試驗場景，而在所有方法都成功重建的影像集上，本文方法精度與Photoscan基本一致，優(yōu)于3DF軟件。

(2) 本文方法效率優(yōu)于Photoscan。從總體處理時間來看，本文方法在場景B和D上消耗的時間稍長；但相對于Photoscan，本文方法在場景A、B、C、D上單位時間內(nèi)可處理的連接點(diǎn)個數(shù)分別提高2.59、2.44、1.12和1.34倍，而單位時間內(nèi)可處理的像點(diǎn)個數(shù)分別提高1.55、2.45、1.09和1.33倍，重建效率更高。

(3) 從效率、連接點(diǎn)數(shù)量和精度幾方面來看，本文方法都明顯優(yōu)于同樣采用分區(qū)融合策略的3DF軟件。尤其是在效率方面，本文方法在場景A、B、C上效率相對于3DF分別提高了2.09、3.26和4.58倍，隨著影像數(shù)的增多，效率提升更為明顯。一方面是因為improved-ISfM方法提高了分區(qū)重建的效率；另一方面，本文方法充分利用了分區(qū)間的關(guān)聯(lián)性指標(biāo)，而且每次融合任務(wù)中能夠包含更多的分區(qū)，大大減少了融合循環(huán)次數(shù)，因此降低了時間消耗。另外，本文先融合“場景”再“相機(jī)”的策略，提高了光束法優(yōu)化的收斂速度。

圖10為本文分區(qū)融合算法對試驗場景的重建結(jié)果，顯示軟件為FugroViewer(V 3.3)。

圖10(a)、(e)的上部，圖10(b)、(c)、(d)的左側(cè)為影像攝站點(diǎn)的平面位置；圖10(a)、(e)的下部，圖10(b)、(c)、(d)的右部為結(jié)構(gòu)信息。

圖10 試驗場景重建結(jié)果，包括影像攝站點(diǎn)平面位置和結(jié)構(gòu)信息Fig.10 The reconstruction results including plane positions of cameras and reconstructed 3D points

3 結(jié) 語

本文提出了一種基于分區(qū)優(yōu)化的混合式SfM方法，以應(yīng)對大規(guī)模無序影像稀疏三維重建。處理過程中，無須GPS/INS等其他輔助信息，影像數(shù)量越大，本文方法的效率優(yōu)勢越大。多組不同規(guī)模、不同場景的無序影像試驗驗證了本文方法的有效性和穩(wěn)健性，其中包括一組包含12萬張5視傾斜影像的數(shù)據(jù)，在這組數(shù)據(jù)上僅有本文方法重建成功，商業(yè)軟件AgisoftPhotoscan和同樣運(yùn)用了混合式SfM的商業(yè)軟件3DF Zephyr Aerial均重建失敗。

本文方法為大規(guī)模無序影像稀疏三維重建提供了可靠、實(shí)用的解決方案，可以促進(jìn)相關(guān)應(yīng)用的發(fā)展。后續(xù)工作主要包括兩方面：一是改進(jìn)融合算法，當(dāng)場景中分區(qū)結(jié)果比較穩(wěn)定時，將多個分區(qū)同時融合減少計算冗余；二是將所提方法分布式并行化，充分利用多計算節(jié)點(diǎn)進(jìn)一步提高重建效率。