0 引言

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

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

    本文設(shè)計(jì)并實(shí)現(xiàn)的無人機(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é)合無人機(jī)序列圖像本身的時(shí)空序列特性改進(jìn)匹配策略，從而提高匹配效率,。特征提取模塊和光束法平差部分通過挖掘原有算法中的可并行性,，進(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è)由粗到精的匹配過程,。通過這種由粗到精的匹配方法可以極大地提高特征點(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)制編碼，然后通過特征點(diǎn)對(duì)應(yīng)的編碼對(duì)所有圖像特征點(diǎn)進(jìn)行聚類,，編碼相同的視為同一類,。最后查找所有包含點(diǎn)p的類組成匹配搜索的概略范圍。

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

2.1.2 哈希重映射

    獲取了粗略的匹配范圍后，可以通過直接計(jì)算點(diǎn)p與所有候選匹配點(diǎn)描述符之間的歐氏距離，比較歐氏距離的大小來確定最終匹配點(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)行分類,。然后計(jì)算點(diǎn)p與所有候選類別的編碼之間的漢明距離（hamming distance），并按照距離大小排序（見2.1.3小節(jié)）,。漢明距離越小，說明該類別里的候選匹配點(diǎn)與點(diǎn)p越相似,。

2.1.3 哈希排序

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

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

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

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

    如果能充分利用這種時(shí)空序列特性,，可以大大減少圖像匹配耗費(fèi)的時(shí)間,。在處理無人機(jī)序列圖像時(shí)，可以通過飛行文件獲取每張圖像的曝光時(shí)間,，并據(jù)此生成按時(shí)間排序的圖像序列,。因?yàn)闊o人機(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)生（例如無人機(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)的主方向并通過計(jì)算特征點(diǎn)周圍128維的特征向量構(gòu)造特征描述符,。

    在SIFT特征提取的過程中，有以下幾個(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)造特征描述符,。

    通過這5個(gè)部分進(jìn)行并行化可以有效提高特征提取的效率。在實(shí)驗(yàn)過程中發(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ì),，通過不斷地迭代過程擬合出更優(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表示通過場(chǎng)景點(diǎn)j進(jìn)行三維空間相似變換和投影到第i個(gè)面上獲得的二維坐標(biāo)值,。

    在平差過程中,，由于每張圖像所對(duì)應(yīng)的相機(jī)參數(shù)獨(dú)立且對(duì)應(yīng)的場(chǎng)景三維點(diǎn)的重投影誤差計(jì)算互不干涉，所以可以對(duì)平差算法進(jìn)行并行化設(shè)計(jì),。在實(shí)際計(jì)算過程中,，為了加快運(yùn)算效率，將這個(gè)非線性優(yōu)化問題轉(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組圖像集均來源于無人機(jī)航拍。實(shí)驗(yàn)結(jié)果見表1,，其中，T_l為圖片加載時(shí)間,，T_f為特征提取時(shí)間,，T_m為特征匹配時(shí)間，T_b為光束法平差消耗時(shí)間,，Σ為總消耗時(shí)間,。

    為了比較重建結(jié)果的精度，F(xiàn)DroneMap和VisualSfM系統(tǒng)分別在3組公開數(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)相比沒有太大差異,，圖3,、圖5幾乎保持一致，圖4總估計(jì)誤差FDroneMap略低于VisualSfM系統(tǒng),。

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

5 結(jié)論

    通過對(duì)算法的優(yōu)化和對(duì)重建模塊的并行化設(shè)計(jì),，F(xiàn)DroneMap在計(jì)算效率和處理精度方面都有較好的表現(xiàn)。在大量實(shí)驗(yàn)過程中發(fā)現(xiàn)一個(gè)問題,，當(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ù)勝，高偉.基于輔助信息的無人機(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.

作者信息:

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

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