0 引言

    近年來，隨著民用無人機的快速發展和消費級數碼相機的快速普及，高分辨率無人機序列圖像成為基于圖像的三維重建的重要數據來源。無人機序列圖像的大范圍、高分辨率的特性使得高細節紋理的城市級別三維重建成為現實。

    中科院自動化所的郭復勝^[1]等人利用GPS、IMU、地面概略高程數據等輔助信息計算圖像之間的概略重疊度，縮小影像匹配范圍，從而提升無人機圖像三維重建的效率。輔助信息的獲取需要從網絡上查找或者通過飛行文件解析。本文試圖通過一種更加便捷的方式提高無人機序列圖像的重建效率，并且更加自動化。

    本文設計并實現的無人機序列圖像快速三維重建系統FDroneMap主要從兩方面提升系統的運行效率，一方面是對重建算法進行重新設計和優化，另一方面是對重建模塊進行并行化設計^[2]。

1 系統簡介

    通常的基于圖像的三維重建系統一般包含以下幾個模塊：圖像特征提取、圖像特征匹配、從運動恢復結構（Struture from Motion，SfM）。其中圖像特征匹配模塊耗時最長。在三維重建系統中為了充分利用圖像信息，常用的特征匹配策略是暴力匹配（brute force matching），其時間復雜度為O(N²)。特征匹配所消耗的時間會占總處理時間的一半以上，如果待處理的圖像尺寸增大，特征匹配所占的時間比例還會持續增加。其次是特征提取模塊及SfM模塊中的光束法平差^[3]（Bundle Adjust）部分，這兩部分模塊的處理時間也會隨著圖像尺寸的增加而劇增。因此為了提高處理速度，FDroneMap主要針對這三部分進行改進和優化。其中特征匹配模塊采用了一種新的基于哈希表的匹配方法，并結合無人機序列圖像本身的時空序列特性改進匹配策略，從而提高匹配效率。特征提取模塊和光束法平差部分通過挖掘原有算法中的可并行性，進行并行化設計，充分利用CPU/GPU的并行計算能力，提升處理速度（別的例如圖像加載等部分也進行了并行設計，這里不一一贅述）。本文系統的處理流程如圖1所示。

2 重建算法優化

2.1 基于哈希表的圖像特征匹配方法

    FDroneMap采用基于哈希表的特征匹配方法^[4]，該特征匹配方法分為3個步驟：哈希搜索、哈希重映射、哈希排序，圖2為匹配流程，其中L表示哈希表總個數。這3個步驟是一個由粗到精的匹配過程。通過這種由粗到精的匹配方法可以極大地提高特征點匹配的效率。

2.1.1 哈希查找

    以圖2中的圖像I、J為例，哈希查找的目的是獲取圖像I中的特征點p在圖像J中匹配搜索的粗略范圍。為了實現這一目的，首先將點p以及圖像J中所有的特征點描述符進行哈希映射，生成m位的二進制編碼，然后通過特征點對應的編碼對所有圖像特征點進行聚類，編碼相同的視為同一類。最后查找所有包含點p的類組成匹配搜索的概略范圍。

    查找過程中使用的編碼位數m的大小會直接影響聚類的結果，一方面編碼越長分類規則越復雜，特征點也越容易被區分開，落在每個分類中的特征點數也越少（待選匹配點也隨之減少），這會大大縮小匹配范圍，很大程度上減少下一步精確匹配的時間；另一方面編碼位數過長會導致落在每個類別的特征點個數過少，待匹配的范圍太小，從而降低匹配結果的精度。因此在實際查找過程中選擇編碼位數時需要權衡效率和精度，本文實驗中采用的編碼位數為10。

2.1.2 哈希重映射

    獲取了粗略的匹配范圍后，可以通過直接計算點p與所有候選匹配點描述符之間的歐氏距離，比較歐氏距離的大小來確定最終匹配點。但由于粗略匹配的范圍相對還是很大，直接計算所有候選點的歐氏距離會耗費相對長的時間。因此為了提升計算的效率，在計算出粗略的匹配范圍后，首先對點p以及所有的候選匹配點重新進行更高維度的哈希映射，每個候選匹配點獲得一個更多位數的二進制編碼。利用該二進制碼對所有特征點重新進行分類。然后計算點p與所有候選類別的編碼之間的漢明距離（hamming distance），并按照距離大小排序（見2.1.3小節）。漢明距離越小，說明該類別里的候選匹配點與點p越相似。

2.1.3 哈希排序

    在計算出點p與所有候選匹配類別編碼之間的漢明距離后，為了進行高效的排序，建立一個哈希表，分別使用漢明距離和其關聯的類別作為表的鍵和值。再對表進行檢索，得到漢明距離最小的前k個候選類別。最后通過計算點p與這k個候選類別中包含的候選匹配點之間的歐式距離確定最終匹配點（一般選擇兩個匹配點）。在整個排序過程，哈希表只需要建立一次，時間復雜度僅為O(N+k)。

    要獲取圖像I中特征點p在圖像J中匹配點，通常的匹配過程是首先分別計算圖像J中所有特征點與p點特征描述符之間的歐氏距離，然后選取歐式距離最小的作為點p在圖像J中的匹配點。整個過程的時間復雜度是O(N²)。而基于哈希表的特征點匹配方法在整個匹配過程中，只在最后一步對有限的k個候選類中的候選點進行了歐氏距離的計算，這會大大提升特征點匹配的效率。

2.2 結合時空序列特性的圖像匹配策略

    不同于一般的來源于互聯網的圖像集，無人機序列圖像之間存在了很強的時空序列性。在拍攝時間上有著前后關系的兩張圖像必定在空間上也有著相互重疊的關系。

    如果能充分利用這種時空序列特性，可以大大減少圖像匹配耗費的時間。在處理無人機序列圖像時，可以通過飛行文件獲取每張圖像的曝光時間，并據此生成按時間排序的圖像序列。因為無人機序列圖像分辨率很高，只需要對圖像序列中前后相鄰的圖像進行匹配就可以獲取充分多的匹配點，這足以保證后續的相機運動估計及場景稀疏結構恢復的精度。這種匹配策略的時間復雜度僅為O(N)，極大地加快了圖像匹配的速度。只對圖像序列中的相鄰圖像之間進行匹配，也減少了誤匹配的產生（例如無人機飛行場景中經常有形狀紋理相似的房頂，如果使用暴力匹配很可能會產生誤匹配），這也能一定程度提高重建結果的精度。

3 并行設計

    對系統模塊的并行設計包含從圖像加載到模型導出的整個流程。其中對系統效率影響最大的是圖像特征提取模塊以及SfM模塊中的光束法平差（Bundle Adjust，BA）部分。

3.1 基于GPU/CPU并行加速的特征提取

    圖像特征提取是基于圖像的三維重建技術的基礎內容，也是FDroneMap系統的核心模塊。圖像三維重建中最常用的圖像特征提取算子為SIFT^[5]（Scale Invariant Feature Transform）算子。SIFT特征點檢測的主要步驟如下：首先對原始圖像進行DOG濾波處理，然后對濾波后的圖像進行極大值和極小值檢測，這些極值的像素坐標即為特征點的坐標，最后計算特征點的主方向并通過計算特征點周圍128維的特征向量構造特征描述符。

    在SIFT特征提取的過程中，有以下幾個部分可以做并行化設計^[6]：（1）將顏色信息轉換為強度信息，（2）對圖像進行上采樣和下采樣，（3）建立DOG金字塔，（4）特征點檢測，（5）計算特征點主方向并構造特征描述符。

    通過這5個部分進行并行化可以有效提高特征提取的效率。在實驗過程中發現，并不是所有的部分都是使用GPU加速效率更高，其中（1）、（2）部分使用CPU多核并行效率更高。

3.2 基于多核并行的BA

    SfM模塊主要包含三部分：相機運動估計、場景結構重建以及光束法平差優化。其中光束法平差部分是對前兩個部分獲得的參數進行平差估計，通過不斷地迭代過程擬合出更優的估計結果。下式為光束法平差的估計模型：

式中，R_i、t_i分別表示第i個圖像所對應相機的旋轉和平移參數，K_i表示第i個圖像的內參數矩陣，X_j表示第j個場景三維點在全局坐標系中的坐標，N_c表示進行重建的圖像總數，N_3D表示重建的三維場景點總數，x_ji表示第j個三維場景點對應于第i個圖像平面上的二維坐標，g表示通過場景點j進行三維空間相似變換和投影到第i個面上獲得的二維坐標值。

    在平差過程中，由于每張圖像所對應的相機參數獨立且對應的場景三維點的重投影誤差計算互不干涉，所以可以對平差算法進行并行化設計。在實際計算過程中，為了加快運算效率，將這個非線性優化問題轉換成簡單矩陣向量的計算，并且將計算任務分配到多個線程加速運算（本文實驗采用8線程計算）。

4 實驗

    在當前的基于圖像的三維重建系統中，VisualSfM系統在計算效率和重建結果的精度方面都具有一定的優越性。因此本文將VisualSfM系統作為參照對象，在系統運行效率和重建結果精度兩方面與FDroneMap進行比較。

4.1 實驗結果

    為了比較系統的運行效率，FDroneMap和VisualSfM系統分別在6組不同大小尺度的圖像集上進行了測試。這6組圖像集均來源于無人機航拍。實驗結果見表1，其中，T_l為圖片加載時間，T_f為特征提取時間，T_m為特征匹配時間，T_b為光束法平差消耗時間，Σ為總消耗時間。

    為了比較重建結果的精度，FDroneMap和VisualSfM系統分別在3組公開數據集^[7]上進行了測試。這3組數據集均帶有真實的地面數據（ground truth），可解析出每張圖像曝光時相機的真實位置。為了將比較結果進行量化，實驗比較了FDroneMap和VisualSfM系統的相機位置估計誤差（與ground truth比較），結果如圖3～圖5所示。

4.2 結果分析

    從表1中可以看出，FDoneMap在處理時間上明顯低于VisualSfM系統，而且隨著圖像數量和大小的增加兩者處理時間之間的差值進一步擴大。5組數據處理時間分別相差了5、7.5、7、16、11、35倍。

    從圖3～圖5可以看出，FDroneMap相機位置估計誤差與VisualSfM系統相比沒有太大差異，圖3、圖5幾乎保持一致，圖4總估計誤差FDroneMap略低于VisualSfM系統。

    綜上，對比實驗結果表明：FDroneMap顯著提高了無人機序列圖像的三維重建的效率，并且沒有損失重建結果的精度。

5 結論

    通過對算法的優化和對重建模塊的并行化設計，FDroneMap在計算效率和處理精度方面都有較好的表現。在大量實驗過程中發現一個問題，當FDroneMap處理的圖像序列中存在模糊或者扭曲圖像時，重建的結果會不完整。當前的處理策略是將原序列拆成多個圖像序列分別進行場景結構重建。因此下一步的工作是主要是研究如何對多序列生成的多場景模型進行最優化的融合。

參考文獻

[1] 郭復勝，高偉.基于輔助信息的無人機圖像批處理三維重建方法[J].自動化學報，2013，39(6)：834-845.

[2] WU C.VisualSFM：A visual structure from motion system[EB/OL].(2012-02-15)[2016-10-22].http：//www.ccw.me/vsfm.html.

[3] TRIGGS B，MCLAUCHLAN P F，HARTLEY R I，et al.Bundle adjustment—a modern synthesis[C].International workshop on vision algorithms.Springer Berlin Heidelberg，1999：298-372.

[4] CHENG J，LENG C，WU J，et al.Fast and accurate image matching with cascade hashing for 3d reconstruction[C].IEEE Conference on Computer Vision and Pattern Recognition(CVPR2014).2014；1-8.

[5] LOWE D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60(2)：91-110.

[6] WU C.SiftGPU: A GPU implementation of scale invariant feature transform(SIFT)[EB/OL].(2009-08-27)[2012-10-18].http：//cs.unc.edu/~ccwu/siftgpu.html.

[7] STRECHA C，HANSEN W V，GOOL L V，et al.On bench-marking camera calibration and multi-view stereo for high resolution imagery[C].Computer Vision and Pattern Recog-nition，2008.IEEE Conference on，2008：1-8.

作者信息:

謝理想，萬  剛，曹雪峰，王慶賀

（信息工程大學 地理空間信息學院，河南 鄭州450001）