0 引言

    近年來(lái)，隨著民用無(wú)人機(jī)的快速發(fā)展和消費(fèi)級(jí)數(shù)碼相機(jī)的快速普及，高分辨率無(wú)人機(jī)序列圖像成為基于圖像的三維重建的重要數(shù)據(jù)來(lái)源。無(wú)人機(jī)序列圖像的大范圍、高分辨率的特性使得高細(xì)節(jié)紋理的城市級(jí)別三維重建成為現(xiàn)實(shí)。

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

    本文設(shè)計(jì)并實(shí)現(xiàn)的無(wú)人機(jī)序列圖像快速三維重建系統(tǒng)FDroneMap主要從兩方面提升系統(tǒng)的運(yùn)行效率，一方面是對(duì)重建算法進(jìn)行重新設(shè)計(jì)和優(yōu)化，另一方面是對(duì)重建模塊進(jìn)行并行化設(shè)計(jì)^[2]。

1 系統(tǒng)簡(jiǎn)介

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

2 重建算法優(yōu)化

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

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

2.1.1 哈希查找

    以圖2中的圖像I、J為例，哈希查找的目的是獲取圖像I中的特征點(diǎn)p在圖像J中匹配搜索的粗略范圍。為了實(shí)現(xiàn)這一目的，首先將點(diǎn)p以及圖像J中所有的特征點(diǎn)描述符進(jìn)行哈希映射，生成m位的二進(jìn)制編碼，然后通過(guò)特征點(diǎn)對(duì)應(yīng)的編碼對(duì)所有圖像特征點(diǎn)進(jìn)行聚類(lèi)，編碼相同的視為同一類(lèi)。最后查找所有包含點(diǎn)p的類(lèi)組成匹配搜索的概略范圍。

    查找過(guò)程中使用的編碼位數(shù)m的大小會(huì)直接影響聚類(lèi)的結(jié)果，一方面編碼越長(zhǎng)分類(lèi)規(guī)則越復(fù)雜，特征點(diǎn)也越容易被區(qū)分開(kāi)，落在每個(gè)分類(lèi)中的特征點(diǎn)數(shù)也越少（待選匹配點(diǎn)也隨之減少），這會(huì)大大縮小匹配范圍，很大程度上減少下一步精確匹配的時(shí)間；另一方面編碼位數(shù)過(guò)長(zhǎng)會(huì)導(dǎo)致落在每個(gè)類(lèi)別的特征點(diǎn)個(gè)數(shù)過(guò)少，待匹配的范圍太小，從而降低匹配結(jié)果的精度。因此在實(shí)際查找過(guò)程中選擇編碼位數(shù)時(shí)需要權(quán)衡效率和精度，本文實(shí)驗(yàn)中采用的編碼位數(shù)為10。

2.1.2 哈希重映射

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

2.1.3 哈希排序

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

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

2.2 結(jié)合時(shí)空序列特性的圖像匹配策略

    不同于一般的來(lái)源于互聯(lián)網(wǎng)的圖像集，無(wú)人機(jī)序列圖像之間存在了很強(qiáng)的時(shí)空序列性。在拍攝時(shí)間上有著前后關(guān)系的兩張圖像必定在空間上也有著相互重疊的關(guān)系。

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

3 并行設(shè)計(jì)

    對(duì)系統(tǒng)模塊的并行設(shè)計(jì)包含從圖像加載到模型導(dǎo)出的整個(gè)流程。其中對(duì)系統(tǒng)效率影響最大的是圖像特征提取模塊以及SfM模塊中的光束法平差（Bundle Adjust，BA）部分。

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

    圖像特征提取是基于圖像的三維重建技術(shù)的基礎(chǔ)內(nèi)容，也是FDroneMap系統(tǒng)的核心模塊。圖像三維重建中最常用的圖像特征提取算子為SIFT^[5]（Scale Invariant Feature Transform）算子。SIFT特征點(diǎn)檢測(cè)的主要步驟如下：首先對(duì)原始圖像進(jìn)行DOG濾波處理，然后對(duì)濾波后的圖像進(jìn)行極大值和極小值檢測(cè)，這些極值的像素坐標(biāo)即為特征點(diǎn)的坐標(biāo)，最后計(jì)算特征點(diǎn)的主方向并通過(guò)計(jì)算特征點(diǎn)周?chē)?28維的特征向量構(gòu)造特征描述符。

    在SIFT特征提取的過(guò)程中，有以下幾個(gè)部分可以做并行化設(shè)計(jì)^[6]：（1）將顏色信息轉(zhuǎn)換為強(qiáng)度信息，（2）對(duì)圖像進(jìn)行上采樣和下采樣，（3）建立DOG金字塔，（4）特征點(diǎn)檢測(cè)，（5）計(jì)算特征點(diǎn)主方向并構(gòu)造特征描述符。

    通過(guò)這5個(gè)部分進(jìn)行并行化可以有效提高特征提取的效率。在實(shí)驗(yàn)過(guò)程中發(fā)現(xiàn)，并不是所有的部分都是使用GPU加速效率更高，其中（1）、（2）部分使用CPU多核并行效率更高。

3.2 基于多核并行的BA

    SfM模塊主要包含三部分：相機(jī)運(yùn)動(dòng)估計(jì)、場(chǎng)景結(jié)構(gòu)重建以及光束法平差優(yōu)化。其中光束法平差部分是對(duì)前兩個(gè)部分獲得的參數(shù)進(jìn)行平差估計(jì)，通過(guò)不斷地迭代過(guò)程擬合出更優(yōu)的估計(jì)結(jié)果。下式為光束法平差的估計(jì)模型：

式中，R_i、t_i分別表示第i個(gè)圖像所對(duì)應(yīng)相機(jī)的旋轉(zhuǎn)和平移參數(shù)，K_i表示第i個(gè)圖像的內(nèi)參數(shù)矩陣，X_j表示第j個(gè)場(chǎng)景三維點(diǎn)在全局坐標(biāo)系中的坐標(biāo)，N_c表示進(jìn)行重建的圖像總數(shù)，N_3D表示重建的三維場(chǎng)景點(diǎn)總數(shù)，x_ji表示第j個(gè)三維場(chǎng)景點(diǎn)對(duì)應(yīng)于第i個(gè)圖像平面上的二維坐標(biāo)，g表示通過(guò)場(chǎng)景點(diǎn)j進(jìn)行三維空間相似變換和投影到第i個(gè)面上獲得的二維坐標(biāo)值。

    在平差過(guò)程中，由于每張圖像所對(duì)應(yīng)的相機(jī)參數(shù)獨(dú)立且對(duì)應(yīng)的場(chǎng)景三維點(diǎn)的重投影誤差計(jì)算互不干涉，所以可以對(duì)平差算法進(jìn)行并行化設(shè)計(jì)。在實(shí)際計(jì)算過(guò)程中，為了加快運(yùn)算效率，將這個(gè)非線性優(yōu)化問(wèn)題轉(zhuǎn)換成簡(jiǎn)單矩陣向量的計(jì)算，并且將計(jì)算任務(wù)分配到多個(gè)線程加速運(yùn)算（本文實(shí)驗(yàn)采用8線程計(jì)算）。

4 實(shí)驗(yàn)

    在當(dāng)前的基于圖像的三維重建系統(tǒng)中，VisualSfM系統(tǒng)在計(jì)算效率和重建結(jié)果的精度方面都具有一定的優(yōu)越性。因此本文將VisualSfM系統(tǒng)作為參照對(duì)象，在系統(tǒng)運(yùn)行效率和重建結(jié)果精度兩方面與FDroneMap進(jìn)行比較。

4.1 實(shí)驗(yàn)結(jié)果

    為了比較系統(tǒng)的運(yùn)行效率，F(xiàn)DroneMap和VisualSfM系統(tǒng)分別在6組不同大小尺度的圖像集上進(jìn)行了測(cè)試。這6組圖像集均來(lái)源于無(wú)人機(jī)航拍。實(shí)驗(yàn)結(jié)果見(jiàn)表1，其中，T_l為圖片加載時(shí)間，T_f為特征提取時(shí)間，T_m為特征匹配時(shí)間，T_b為光束法平差消耗時(shí)間，Σ為總消耗時(shí)間。

    為了比較重建結(jié)果的精度，F(xiàn)DroneMap和VisualSfM系統(tǒng)分別在3組公開(kāi)數(shù)據(jù)集^[7]上進(jìn)行了測(cè)試。這3組數(shù)據(jù)集均帶有真實(shí)的地面數(shù)據(jù)（ground truth），可解析出每張圖像曝光時(shí)相機(jī)的真實(shí)位置。為了將比較結(jié)果進(jìn)行量化，實(shí)驗(yàn)比較了FDroneMap和VisualSfM系統(tǒng)的相機(jī)位置估計(jì)誤差（與ground truth比較），結(jié)果如圖3～圖5所示。

4.2 結(jié)果分析

    從表1中可以看出，F(xiàn)DoneMap在處理時(shí)間上明顯低于VisualSfM系統(tǒng)，而且隨著圖像數(shù)量和大小的增加兩者處理時(shí)間之間的差值進(jìn)一步擴(kuò)大。5組數(shù)據(jù)處理時(shí)間分別相差了5、7.5、7、16、11、35倍。

    從圖3～圖5可以看出，F(xiàn)DroneMap相機(jī)位置估計(jì)誤差與VisualSfM系統(tǒng)相比沒(méi)有太大差異，圖3、圖5幾乎保持一致，圖4總估計(jì)誤差FDroneMap略低于VisualSfM系統(tǒng)。

    綜上，對(duì)比實(shí)驗(yàn)結(jié)果表明：FDroneMap顯著提高了無(wú)人機(jī)序列圖像的三維重建的效率，并且沒(méi)有損失重建結(jié)果的精度。

5 結(jié)論

    通過(guò)對(duì)算法的優(yōu)化和對(duì)重建模塊的并行化設(shè)計(jì)，F(xiàn)DroneMap在計(jì)算效率和處理精度方面都有較好的表現(xiàn)。在大量實(shí)驗(yàn)過(guò)程中發(fā)現(xiàn)一個(gè)問(wèn)題，當(dāng)FDroneMap處理的圖像序列中存在模糊或者扭曲圖像時(shí)，重建的結(jié)果會(huì)不完整。當(dāng)前的處理策略是將原序列拆成多個(gè)圖像序列分別進(jìn)行場(chǎng)景結(jié)構(gòu)重建。因此下一步的工作是主要是研究如何對(duì)多序列生成的多場(chǎng)景模型進(jìn)行最優(yōu)化的融合。

參考文獻(xiàn)

[1] 郭復(fù)勝，高偉.基于輔助信息的無(wú)人機(jī)圖像批處理三維重建方法[J].自動(dòng)化學(xué)報(bào)，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.

作者信息:

謝理想，萬(wàn)  剛，曹雪峰，王慶賀

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