張 馳，李鑄洪，劉 舟，沈未名*

（1.測繪遙感信息工程國家重點實驗室（武漢大學(xué)），武漢 430079；2.華中科技大學(xué)軟件學(xué)院，武漢 430074；3.武漢大學(xué)計算機學(xué)院，武漢 430072）

0 引言

從20 世紀(jì)60 年代至今，遙感（Remote Sensing，RS）技術(shù)作為一門新興的科學(xué)技術(shù)迅速發(fā)展，如今已在地圖測繪、環(huán)境監(jiān)測、國土資源調(diào)查、城市三維重建等諸多領(lǐng)域發(fā)揮著舉足輕重的作用。傳統(tǒng)的遙感方式主要包括有人航空遙感和衛(wèi)星遙感，盡管這些可以方便的獲取大范圍的地理信息數(shù)據(jù)，但在面對應(yīng)急測繪、小范圍的精細(xì)測繪等任務(wù)時，傳統(tǒng)的遙感方式難以達(dá)到實際要求。近年來，在無人機（Unmanned Aerial Vehicle，UAV）、計算機、導(dǎo)航與定位技術(shù)不斷發(fā)展的背景下，應(yīng)運而生的無人機遙感（UAV Remote Sensing，UAVRS）技術(shù)有效地彌補了有人航空遙感和衛(wèi)星遙感的缺陷，憑借其結(jié)構(gòu)簡單、靈活機動、實時性強以及成本低的優(yōu)勢，在應(yīng)急測繪、小范圍的精細(xì)測繪以及自然災(zāi)害救援中發(fā)揮了關(guān)鍵性的作用［1-3］。

無人機影像定位是無人機遙感技術(shù)中的一個十分關(guān)鍵的任務(wù)，主要利用無人機影像以及無人機平臺獲取到的一些輔助信息，計算出無人機相機和地面物體的相對位置關(guān)系，從而實現(xiàn)地面目標(biāo)的精確定位。部分研究學(xué)者對傳統(tǒng)航空攝影測量技術(shù)進(jìn)行了改進(jìn)，提出了一些適用于無人機的攝影測量方法。袁修孝等［4］提出基于全球定位系統(tǒng)（Global Positioning System，GPS）精密單點定位的低空遙感GPS 輔助空中三角測量方法，利用搭載在無人機中的動態(tài)GPS接收機獲取的GPS攝站取代地面控制點進(jìn)行攝影測量，并通過實驗證明了這種方法的有效性以及優(yōu)越性。郭復(fù)勝等［5］提出了一種無人機影像批處理三維重建方法，充分利用了無人機平臺的輔助信息，包括低精度的位置信息、姿態(tài)信息以及粗略的地形高程信息，實現(xiàn)了大規(guī)模的無人機影像快速魯棒的三維重建。Rhee等［6］針對無人機立體測繪中比較重要的3 個問題（外方位元素精度不高、拍攝不穩(wěn)定和圖像覆蓋范圍?。_發(fā)了一個攝影測量增量光束法平差程序，基本可以達(dá)到1∶1 000測圖的精度要求。

隨著計算機視覺技術(shù)的不斷發(fā)展，運動恢復(fù)結(jié)構(gòu)技術(shù)不斷成熟，相較于攝影測量技術(shù)，運動恢復(fù)結(jié)構(gòu)（Structure From Motion，SFM）技術(shù)不需要無人機平臺提供任何輔助信息，也不需要額外的控制點信息，要求較低且通用性強，因此基于SFM 的無人機影像定位技術(shù)逐漸成為國內(nèi)外學(xué)者的關(guān)注熱點。尹雙雙等［7］針對移動全景影像，利用GPS 信息對影像匹配、場景初始化以及光束法平差等主要步驟進(jìn)行了優(yōu)化，提高了影像位姿和場景模型的精度。陳銳等［8］對SFM 技術(shù)中的圖像特征提取、特征匹配以及光束法平差進(jìn)行了優(yōu)化，在較短時間內(nèi)計算出較高精度的拼接影像，實時性較好。Lhuillier［9］提出了兩種光束法平差I(lǐng)BA（Bundle Adjustment with Inequality constraint）和EBA（Bundle Adjustment with Equality constraint）用來融合GPS信息和SFM數(shù)據(jù)，為了保證較小的重投影誤差，在光束法平差中引入了重投影誤差的上界限。面對長序列無人機影像和低精度的GPS 信息，該方法仍然可以計算出較為準(zhǔn)確的相機位姿。Irschara 等［10］利用GPS 和慣性測量單元（Inertial Measurement Unit，IMU）輔助信息加速SFM 的計算，實現(xiàn)了更加魯棒和高效的三維重建。Qu 等［11］提出了一種基于圖像隊列的快速精確的三維重建方法，利用主成分分析、加權(quán)光束法平差等技術(shù)，在圖像數(shù)量較多的情況下，較大提高了重建速度。

盡管這些方法結(jié)合無人機影像的特點對SFM 技術(shù)進(jìn)行了有效的擴展，但在實際應(yīng)用中，基于SFM 的無人機影像定位技術(shù)仍然存在一些問題：一方面，由于無人機影像規(guī)模的不斷擴大，SFM技術(shù)流程中的圖像匹配、光束法平差優(yōu)化等步驟的計算量大大增加，導(dǎo)致無人機影像定位需要消耗大量的時間；另一方面，對于長序列無人機影像，由于SFM 固有的誤差累計問題，每加入一張圖像都會引入新的誤差，導(dǎo)致最終的誤差過大且難以全局優(yōu)化。

針對上面所描述的問題，本文對基于SFM 的無人機影像定位算法進(jìn)行了優(yōu)化，主要貢獻(xiàn)如下：1）提出了基于場景圖劃分的無人機影像定位算法，利用分而治之的思想，通過場景圖的構(gòu)建與劃分對無人機影像進(jìn)行分組，利用光束法平差進(jìn)行融合；2）利用無人機平臺獲取的GPS 信息縮小圖像匹配的空間搜索范圍并且為光束法平差添加新的約束。實驗結(jié)果表明，對于大規(guī)模長序列的無人機影像，優(yōu)化后的方法可以更快速地完成更精確的影像定位。

1 基于運動的結(jié)構(gòu)恢復(fù)

運動恢復(fù)結(jié)構(gòu)是計算機視覺領(lǐng)域多視圖重建中的核心問題，主要任務(wù)是根據(jù)對物體或場景拍攝的多視圖像，利用特征匹配、三角化以及光束法平差等技術(shù)，計算出相機位置和姿態(tài)信息以及同名點的世界坐標(biāo)。SFM技術(shù)可分為增量式SFM和全局SFM。增量式SFM首先挑選一個初始相對進(jìn)行重建從而得到一個初始三維模型，之后不斷添加新的圖像，并對新加入的同名點進(jìn)行三角化同時利用光束法平差重新進(jìn)行優(yōu)化，直至所有圖像處理完畢［12-15］。全局SFM 則同時估計所有相機的位姿信息并且光束法平差只執(zhí)行一次［16-19］，因此，相較于增量式SFM，全局SFM 計算速度較快，但同時全局SFM 缺乏誤差剔除的機制，因而其重建結(jié)果受匹配誤差的影響很大。本文主要針對增量式SFM進(jìn)行優(yōu)化。

增量式SFM 的重建流程如圖1 所示，主要包括同名點獲取和增量重建兩個階段。

圖1 增量式SFM重建流程Fig.1 Flowchart of SFM incremental reconstruction

第一階段為同名點獲取。首先通過特征提取技術(shù)計算出圖像中特征點的位置以及對應(yīng)的特征描述子。尺度不變特征變換（Scale-Invariant Feature Transform，SIFT）［20］及其派生物［21］因具有較好的穩(wěn)定性和不變性被廣泛使用。之后對圖像進(jìn)行特征匹配，即比較兩幅圖像中特征點的相似程度，通常使用兩個特征描述子之間的歐氏距離進(jìn)行描述，從而得到可能的重疊圖像對以及它們相匹配的特征。由于匹配僅僅依賴于特征描述子之間的相似程度，很可能相匹配的一對點并不對應(yīng)于場景中的同一點，所以需要對匹配點進(jìn)行幾何驗證，即使用一個幾何變換來描述兩幅圖像相匹配的特征點間的映射關(guān)系。通常隨機抽樣一致（RANdom SAmple Consensus，RANSAC）算法［22］被使用來濾除不滿足幾何變換的錯誤匹配點。這一階段的輸出為經(jīng)過幾何驗證的重疊圖像對以及經(jīng)過外點濾除后的相匹配的特征點。這一輸出也被表示為場景圖，場景圖的節(jié)點為圖像，場景圖的邊連接了幾何驗證后的圖像對。

第二階段為增量重建，即根據(jù)第一階段得到的場景圖進(jìn)一步恢復(fù)出相機的位姿以及三維模型。這一階段首先選取一個圖像對進(jìn)行重建從而實現(xiàn)初始化，被選取的圖像對應(yīng)當(dāng)具有較多的同名點以及較長的基線以便于得到一個分布較好的初始三維模型。之后不斷從剩余圖像中選擇新的圖像添加進(jìn)來，利用直接線性變換（Direct Linear Transform，DLT）、EPnP［23］等求解PnP（Perspective-n-Point）問題的方法計算新加入圖像的位姿信息，同時利用三角化計算出新的同名點對應(yīng)的世界坐標(biāo)。由于相機的位姿計算和三角化是分開進(jìn)行的，同時隨著新加入圖像的不斷增多，誤差會不斷累積，因此需要光束法平差進(jìn)行進(jìn)一步的優(yōu)化。光束法平差主要通過對相機參數(shù)Pc以及投影得到的三維空間點Xk進(jìn)行聯(lián)合優(yōu)化從而達(dá)到最小化重投影誤差的目的。重投影誤差表示為：

其中：π為投影函數(shù)，可將三維空間點Xk投影到圖像平面上；xj為對應(yīng)的特征點的坐標(biāo)；ρj為損失函數(shù)。光束法平差問題通常使用LM（Levenberg-Marquardt）算法求解。直至所有的圖像都添加完畢，最終可以獲得所有圖像對應(yīng)的相機位姿以及完整的三維模型。

2 基于場景圖劃分的層次式SFM算法

2.1 算法流程

本文在增量式SFM 的基礎(chǔ)上，結(jié)合無人機圖像的特點以及無人機平臺的輔助信息，提出了基于場景圖劃分的層次式SFM算法，算法流程如圖2所示。

圖2 基于場景圖劃分的層次式SFM算法流程Fig.2 Flowchart of hierarchical SFM algorithm based on scene graph division

對于輸入的無人機圖像以及圖像對應(yīng)的GPS 信息，首先進(jìn)行同名點提取以獲取場景圖，與上文所述不同的是，在特征匹配階段，由于GPS信息一定程度上反映了圖像的空間關(guān)系，因此本文分別計算兩兩圖像間的GPS 距離，GPS 距離較遠(yuǎn)的兩幅圖像被視為不重疊圖像，之后不對其進(jìn)行特征匹配。相較于暴力匹配，即對所有圖像進(jìn)行兩兩特征匹配，結(jié)合GPS的匹配策略極大降低了時間復(fù)雜度，提高了運行效率。

在增量重建階段，隨著圖像的不斷增多，光束法平差的時間復(fù)雜度急劇增大，此外考慮到不重疊的兩張圖像彼此依賴關(guān)系較小，故而本文采用分而治之的思想對此問題進(jìn)行了優(yōu)化。本文首先結(jié)合匹配關(guān)系和GPS信息重新構(gòu)建了場景圖并進(jìn)行了劃分（2.2 節(jié)將詳細(xì)介紹場景圖的構(gòu)建與劃分），為了方便之后的融合，劃分出的相鄰兩組間應(yīng)當(dāng)存在多張重疊圖像。之后使用多核CPU 并行進(jìn)行各組的增量重建，一方面并行化充分利用了計算資源；另一方面，光束法平差的時間復(fù)雜度隨圖像規(guī)模的減小而減小，故而大大加速了重建過程。最后基于重疊區(qū)域?qū)Ω鹘M的重建結(jié)果進(jìn)行融合，因為各組間存在著不同的誤差，所以需要對整體進(jìn)行光束法平差進(jìn)一步優(yōu)化重建結(jié)果。

2.2 場景圖的構(gòu)建與劃分

場景圖是一種圖結(jié)構(gòu)，場景圖的節(jié)點表示圖像，邊表示圖像之間的關(guān)系。在傳統(tǒng)的SFM 之中，場景圖的邊連接了兩幅具有重疊區(qū)域的圖像。本文對場景圖進(jìn)行了擴展，即根據(jù)兩幅圖像之間的視覺關(guān)系和空間關(guān)系為場景圖的邊賦予了權(quán)重，表示如下：

其中：eij表示圖像i和j相連的邊；Wvis表示兩幅圖像的視覺一致性，與兩幅圖像的同名點數(shù)量成正比；Wgeo表示兩幅圖像的空間一致性，與兩幅圖像的GPS距離成反比，即同名點數(shù)量越多，GPS坐標(biāo)越相近，這兩幅圖像相連的邊的權(quán)重就越大；α用來控制Wvis和Wgeo的權(quán)重。

構(gòu)建完場景圖之后，本文采用歸一化割（Normalized Cut，Ncut）［24］算法進(jìn)行場景圖的劃分。定義場景圖為G=(V，E)，其中V為頂點，E為邊。假設(shè)需要將場景圖分割成互不相交的兩個子集A和B，那么歸一化割可表示為：

其中cut（A，B）為集合A和B相連的邊的權(quán)重之和：

assoc（A，V）和assoc（B，V）分別為集合A和B中的點到圖中所有其他點的權(quán)重之和：

因此，歸一化割既追求不同子集間權(quán)重最小，同時還追求同一子集內(nèi)權(quán)重最大。歸一化割的結(jié)果如圖3所示。

圖3 歸一化割Fig.3 Normalized cut

考慮到增量重建所需的圖像規(guī)模，歸一化割的具體步驟為：設(shè)定子集的最大節(jié)點數(shù)為M，不斷迭代地對場景圖進(jìn)行歸一化割，直至所有子集的節(jié)點數(shù)均不超過M。

經(jīng)過上述場景圖的創(chuàng)建和劃分，重疊度更高以及空間距離更近的圖像將更有可能被劃分為同一子集，這不僅為后續(xù)的增量重建提供了足夠的冗余度，同時保證了重建盡可能少地受到錯誤信息的干擾。

2.3 GPS輔助光束法平差

根據(jù)運動恢復(fù)結(jié)構(gòu)一節(jié)中所述，計算機視覺中的光束法平差通過最小化重投影誤差實現(xiàn)對相機位姿、相機內(nèi)參以及三維場景點坐標(biāo)的優(yōu)化，但是對于無人機拍攝的大規(guī)模長序列影像，僅僅依靠重投影誤差，不僅會導(dǎo)致較大的誤差偏移，而且可能出現(xiàn)多種重建結(jié)果同時滿足視覺約束的情況。圖4為僅僅依靠視覺約束對兩組長序列影像進(jìn)行重建出現(xiàn)的歧義性結(jié)果。

圖4 歧義性結(jié)果Fig.4 Ambiguous result

本文結(jié)合GPS 信息對光束法平差進(jìn)行了優(yōu)化，考慮到SFM 計算得到的三維模型所處的坐標(biāo)系B 與世界地理坐標(biāo)系W并不一致，為了方便之后的光束法平差和場景融合，這里需要將場景模型轉(zhuǎn)換到世界地理坐標(biāo)系下以實現(xiàn)地理配準(zhǔn)。因為模型坐標(biāo)系與世界地理坐標(biāo)系之間僅僅存在旋轉(zhuǎn)、平移和縮放的關(guān)系，所以本文采用最小二乘法計算相似變換矩陣來實現(xiàn)這一轉(zhuǎn)換。

完成地理配準(zhǔn)之后，本文結(jié)合GPS 對光束法平差中的代價函數(shù)進(jìn)行了擴展：

其中：Evis為重投影誤差，與運動恢復(fù)結(jié)構(gòu)一節(jié)中所述一致。Egps為計算出的相機中心點cj與實際GPS坐標(biāo)之間的誤差，表示為：

Ediff為計算出的相機中心點的相對距離和實際GPS 坐標(biāo)的相對距離的誤差，表示為：

在GPS 精度不高的情況下，相對距離誤差受噪聲的影響較小，可以對實際誤差起到一定的補償作用。另外，w1、w2和w3為這3項誤差的權(quán)重。總的來說，Egps和Ediff的引入為光束法平差添加了相機位置的約束，有效避免了模型收斂到局部極小值的情況，使得對大規(guī)模長序列無人機影像的重建和定位更加魯棒和精確。

3 實驗與結(jié)果分析

3.1 實驗準(zhǔn)備

為了充分驗證本文所提算法的魯棒性和有效性，本文選取了四個無人機影像數(shù)據(jù)集進(jìn)行實驗，分別為果子溝數(shù)據(jù)集、賽里木湖數(shù)據(jù)集、武大數(shù)據(jù)集以及NPU_Monticules 數(shù)據(jù)集，如圖5 所示。其中，果子溝和賽里木湖數(shù)據(jù)集為長序列無人機影像，而武大和NPU_Monticules 數(shù)據(jù)集為無人機陣列式拍攝獲取的影像。4 個數(shù)據(jù)集均包含GPS 信息，其中賽里木湖數(shù)據(jù)集的GPS精度為0.2 m，其他3個數(shù)據(jù)集的GPS精度為2 m。4個數(shù)據(jù)集均不包含任何地面控制點。

圖5 無人機影像數(shù)據(jù)集Fig.5 UAV image datasets

此外，本文所有的實驗所采用的PC 平臺配置為Intel Core i7-6700HQ CPU 2.6 GHz，內(nèi)存為16 GB，顯卡為GeForce GTX 1060，系統(tǒng)為Ubuntu 16.04。

3.2 定量評價

為了驗證本文提出的基于場景圖劃分的無人機影像定位算法的有效性，本文在上述4 個數(shù)據(jù)集上進(jìn)行了對比實驗，對比算法分別為COLMAP［13］、OpenMVG［25］以及OpenSFM［26］，其中，COLMAP 和OpenMVG 未利用GPS 輔助信息，OpenSFM 利用絕對GPS誤差來優(yōu)化光束法平差。定量評價指標(biāo)為重投影誤差，即三維點云的投影點和其對應(yīng)的特征點之間的距離，具體定義可參照第1章。表1展示了4種算法在4個數(shù)據(jù)集上的重投影誤差結(jié)果。

表1 四種算法的重投影誤差結(jié)果 單位：像素Tab.1 Reprojection error results of four algorithms unit：px

從定量評價結(jié)果可以看出，相較于其他三種算法，本文提出的算法可以獲得更小的重投影誤差。對于果子溝和賽里木湖這兩個長序列無人機影像數(shù)據(jù)集，融合了GPS 輔助信息的算法優(yōu)勢十分明顯。尤其對于果子溝數(shù)據(jù)集，因其GPS 定位精度不高，本文提出的GPS 相對誤差輔助平差有效消除了GPS噪聲的影響，相較OpenSFM優(yōu)化提升顯著。

3.3 場景劃分結(jié)果分析

為了驗證本文提出的基于場景劃分的層次式重建的優(yōu)化效果，本文對四組無人機影像數(shù)據(jù)集分別進(jìn)行了增量式重建和層次式重建。為了控制實驗變量，除了場景圖的劃分與融合，層次式重建的其他實現(xiàn)過程與增量式重建保持一致。表2展示了增量式SFM和層次式SFM的運行時間。

表2 增量式SFM和層次式SFM運行時間 單位：sTab.2 Running times of incremental SFM and hierarchical SFM unit：s

可以看出，相較于增量式重建，基于場景圖劃分的層次式重建所需的時間要少得多，這主要因為：一方面并行化充分利用了計算資源；另一方面，光束法平差的時間復(fù)雜度隨圖像規(guī)模的減小而大幅降低。

3.4 GPS輔助平差結(jié)果分析

為了進(jìn)一步驗證GPS 輔助平差的優(yōu)化效果，本文對有無GPS輔助下的重建結(jié)果進(jìn)行了對比，如圖6所示。

圖6 有無GPS輔助的重建結(jié)果Fig.6 Reconstruction results with or without GPS assistance

對于果子溝數(shù)據(jù)集和賽里木湖數(shù)據(jù)集這種長序列無人機影像，由于航向重疊率不高且僅僅依賴視覺信息進(jìn)行重建，導(dǎo)致隨著圖像的不斷加入，誤差不斷累積以致出現(xiàn)了嚴(yán)重的誤差漂移的情況，即圖中所示重建結(jié)果出現(xiàn)了嚴(yán)重的彎曲。而GPS 的引入幫助對相機位置做進(jìn)一步的約束，避免了出現(xiàn)歧義性的結(jié)果。

為了進(jìn)一步分析定位誤差的大小，本文將果子溝數(shù)據(jù)集的定位結(jié)果在x，y，z三個坐標(biāo)軸上的投影繪制成折線圖的形式，如圖7所示。

從圖7 可以看出，無GPS 輔助下兩條線相隔較大，有GPS輔助下兩條線近乎重合，因而在GPS的幫助下，相機的運動軌跡得到了很好的約束，誤差漂移問題得到了很好的解決。

圖7 有無GPS輔助的果子溝數(shù)據(jù)集定位結(jié)果對比Fig.7 Comparison of positioning results with or without GPS-assisted Guozigou dataset

4 結(jié)語

本文針對無人機影像定位問題，提出了一種基于場景圖劃分的層次式SFM 方法，結(jié)合視覺一致性和空間一致性進(jìn)行場景圖的創(chuàng)建同時利用歸一化割實現(xiàn)對場景圖的劃分。此外，本文對光束法平差的代價函數(shù)進(jìn)行了擴展，加入了GPS絕對位置誤差和相對位置誤差。實驗結(jié)果表明，基于場景圖劃分的層次式SFM 方法大幅提高了無人機影像的定位速度，同時，相對和絕對GPS 誤差輔助平差對相機位姿起到了很好的約束作用，解決了誤差漂移的問題，避免了出現(xiàn)歧義性的結(jié)果，也因此本算法相較同類算法有較為顯著的優(yōu)化提升。

然而，本文提出的算法是基于增量式SFM 重建實現(xiàn)的，增量式SFM 重建中固有的誤差累計問題仍然不可避免，考慮到全局SFM 重建有效避免了誤差累計問題但帶來了較大的不穩(wěn)定性，因此如何有效地結(jié)合增量式SFM 重建和全局SFM重建，提高影像定位的準(zhǔn)確性和穩(wěn)定性是未來的研究趨勢。