周寧，楊元維，王萍，高賢君，方軍

(1.長江大學(xué) 地球科學(xué)學(xué)院，武漢 430100；2.中國科學(xué)院空天信息創(chuàng)新研究院，北京 100094；3.海南省地球觀測重點實驗室，海南 三亞 572029；4.湖南科技大學(xué) 地理空間信息技術(shù)國家地方聯(lián)合工程實驗室，湖南 湘潭 411201；5.湖南科技大學(xué) 測繪遙感信息工程湖南省重點實驗室，湖南 湘潭 411201)

0 引言

近些年來，無人機遙感[1]發(fā)展迅猛，目前已成為攝影測量與遙感領(lǐng)域的熱門發(fā)展方向之一[2-3]。在運用搭載定位定向系統(tǒng)(positioning and orientation system，POS)的無人機進行遙感作業(yè)時可獲取包含POS信息、具有高分辨率及明顯地物特征的遙感影像[4]，但影像覆蓋范圍小、重疊度高、數(shù)據(jù)規(guī)模大。當(dāng)利用這些影像及測區(qū)的地面控制點(ground control point，GCP)進行空三加密流程中的控制點校正時，如何從大量的無人機影像中快速、準(zhǔn)確地檢索出包含地面控制點的影像成為一個關(guān)鍵問題。檢索控制點影像的效率與準(zhǔn)確度對進行全自動空三處理及其后的高精度測繪、地表三維信息提取和三維重構(gòu)等應(yīng)用有著重要影響[5-6]。在具有GCP詳細(xì)信息及POS信息等初始數(shù)據(jù)的前提下，目前常用的檢索算法大致分為2類：一類是窮盡搜索法，另一類是對無人機影像建立空間索引[7]。窮盡搜索法即遍歷檢索所有影像集中的影像數(shù)據(jù)，將控制點坐標(biāo)與影像的POS信息逐一比較，尋找目標(biāo)影像。而建立空間索引是通過對影像數(shù)據(jù)進行分析，設(shè)計出有效的索引結(jié)構(gòu)，加快影像檢索，其代表為四叉樹、R樹及其變體等。2種方法各有優(yōu)缺，但對于無人機影像數(shù)據(jù)量大、要素分布密集等特點，無論是采用窮盡搜索法還是R樹等現(xiàn)有索引樹，速度都比較有限。因此，如何建立更加高效的空間索引使得從大規(guī)模無人機影像中快速檢索出目標(biāo)影像，是亟需解決的問題。

國外空間索引的研究成果最早可追溯到20世紀(jì)70年代，由Finkel等[8]于1974年提出的四叉樹索引，是一種樹形索引結(jié)構(gòu)，除葉子結(jié)點的其余結(jié)點均有4個子域，將地理空間均勻地劃分成4個象限。Bentley[9]于1975年提出多維二叉搜索樹(KD樹)，KD樹為每個點都是K維點的二叉樹，其對點對象的查找與平衡二叉樹同樣高效。1984年，Guttman[10]介紹了R-Tree這種現(xiàn)如今廣泛應(yīng)用的空間索引結(jié)構(gòu)。同年，Nievergelt[11]提出了網(wǎng)格索引的思想，通過網(wǎng)格劃分空間數(shù)據(jù)，再利用網(wǎng)格編碼檢索空間數(shù)據(jù)，但這一方法應(yīng)對數(shù)據(jù)量較大的空間檢索時所需硬盤空間巨大，具有局限性。Leutenegger等[12]于1997年提出了基于R樹的批量加載算法(sort tile recursive，STR)。

國內(nèi)空間索引技術(shù)起步于20世紀(jì)90年代，曹加恒等[13]于1998年提出了一種G-Tree空間模型，其設(shè)計實現(xiàn)了基于頁面的空間索引機制，有效地解決了多維空間數(shù)據(jù)的檢索問題。2009年，鄧紅艷等[14]提出了一種變形樹索引結(jié)構(gòu)，該索引在檢索以多重分辨率形式組織的空間數(shù)據(jù)時效果顯著。另外，付仲良等[15]于2012年提出了基于MR樹空間索引的Voronoi圖改進及其并行空間查詢方法。

上述空間索引技術(shù)及其變種是針對不同應(yīng)用環(huán)境、不同需求及不同類型的空間數(shù)據(jù)，在某些特定領(lǐng)域有其自身的優(yōu)勢，并不適用于本文的應(yīng)用需求。經(jīng)實驗分析，上述索引在構(gòu)建時均未利用到已知控制點的信息，致使構(gòu)建及檢索效率均不夠理想。因此，本文從已知GCP(參考點)的信息入手，提出了一種基于GCP數(shù)據(jù)的樹形索引算法(ground control point tree，GCP-Tree)。經(jīng)大量實驗，該算法能很好地適用于參考點已知的影像檢索，并與普適性較高的R-Tree索引及四叉樹索引進行實驗對比，驗證了本文所提算法的良好性能。

1 GCP-Tree樹形空間索引

本文提出的GCP-Tree索引從已知GCP信息及影像POS信息角度出發(fā)，通過空間求交等運算，逐步生成GCP-Tree索引。

1.1 基本定義

1)影像GPS坐標(biāo)：指搭載于無人機上的多光譜等遙感相機在對地拍攝的瞬間所記錄的POS信息中的GPS坐標(biāo)數(shù)據(jù)。因此，每幅影像均唯一對應(yīng)一條POS信息。

2)影像點(image point)：指由影像GPS坐標(biāo)經(jīng)投影轉(zhuǎn)換后的大地平面坐標(biāo)所構(gòu)成的點。

3)最小面積外包矩形(minimum area bounding rectangle，MBR)：指所在測區(qū)中獲得的所有影像點所構(gòu)成凸多邊形的外包矩形中面積最小的矩形。

4)矩形方向：指與矩形中短邊平行的方向，若4邊等長則為平行于其中任意一邊的方向。

5)索引矩形(ground control point rectangle，GCP-Rec)：指與MBR同向，以GCP為中心、以航帶間距為邊長基準(zhǔn)的矩形。

GCP-Tree索引結(jié)構(gòu)共包含3種結(jié)點：根結(jié)點、子結(jié)點和葉子結(jié)點。根結(jié)點和子結(jié)點主要存儲孩子結(jié)點的位置，葉子結(jié)點主要存儲影像的名稱數(shù)組。3種結(jié)點的結(jié)構(gòu)如圖1所示。

圖1 GCP-Tree樹結(jié)點結(jié)構(gòu)示意圖

1.2 GCP-Tree索引算法概述

首先，計算出同一測區(qū)中所有影像點的MBR，生成以該MBR左下頂點為原點的二維直角坐標(biāo)系；其次，構(gòu)建GCP-Rec；最后，依據(jù)GCP-Rec對當(dāng)前影像數(shù)據(jù)建立索引，生成GCP-Tree。

對影像數(shù)據(jù)分析后知，包含同一GCP的影像90%分布于距GCP最近的2條平行航帶上，為獲取該類目標(biāo)影像集，需將GCP-Rec的方向調(diào)整至與航帶平行或垂直且其邊長需大于航帶間距。經(jīng)實驗，同一影像集所求的MBR唯一，且其方向始終與航帶方向平行或垂直，故設(shè)定GCP-Rec與MBR同向，即可獲得目標(biāo)影像集。圖2表示GCP-Tree索引的生成過程實例。對空間區(qū)域中編號為P1～P28的影像點求出其MBR，然后建立平面直角坐標(biāo)系，分別以G1～G4為中心，以2倍航帶間距2r為邊長構(gòu)造出GCP-Rec，再進行空間求交，填充索引樹的葉子結(jié)點，直至GCP-Tree構(gòu)建完成。

對照圖3，以下為該索引的詳細(xì)構(gòu)造流程。

1)輸入。計算機中無人機影像物理路徑與M個地面實測控制點數(shù)據(jù)。

2)輸出。包含M個分枝的GCP-Tree索引。

3)流程。

(1)計算影像點的MBR，對樹結(jié)點的各項信息做初始化操作。

(2)以MBR的西南角點為坐標(biāo)原點O，MBR中相交于該點的2條直角邊分別為x軸與y軸構(gòu)建二維直角坐標(biāo)系。

注：左圖中指影像點；指地面控制點；以G1～G4為中心的方框為GCP-Rec。圖2 GCP-Tree索引樹的生成過程實例

圖3 GCP-Tree構(gòu)造過程框架圖

(3)以航帶間距r為基準(zhǔn)，構(gòu)建GCP-Rec。

(4)構(gòu)造GCP-Rec時，其邊長L根據(jù)航道類型的不同有式(1)所示的2種情況，此處的2倍航帶間距是經(jīng)實驗得出的最優(yōu)邊長。

(1)

(5)運用空間求交算法求出包含在索引矩形中的影像，并對GCP-Tree的葉子結(jié)點進行填充。

(6)按照步驟(1)～步驟(5)，自上至下，按順序構(gòu)建。至此，整棵GCP-Tree構(gòu)建完成。

1.3 GCP-Tree索引算法偽代碼描述

1)輸入。影像數(shù)據(jù)、控制點數(shù)據(jù)和航帶間距r[n](n為航帶數(shù)，n<=2)。

2)輸出。GCP-Tree空間索引。

3)用到的封裝函數(shù)。

(1)Cre_mbr(影像數(shù)據(jù))/*創(chuàng)建MBR*/

(2)Cre_gcp-rec(控制點數(shù)據(jù)，r[n])/*創(chuàng)建GCP-Rec*/

(3)Intersect(影像數(shù)據(jù)，索引矩形)/*空間求交*/

(4)Leaf-NodeConstructor(單個影像編號)/*構(gòu)建葉子結(jié)點*/

(5)Input(輸入數(shù)據(jù))和Output(輸出數(shù)據(jù))

4)過程。GCP-Tree(影像數(shù)據(jù)，控制點數(shù)據(jù)，r[n])→GCP-Tree空間索引樹。

(1)Cre_mbr(影像數(shù)據(jù))

(2)Input(r[n])/*輸入航帶間距*/

(3)ListTGCP-Rec/*聲明索引矩形集合變量*/

(4)if(n==1)/*根據(jù)航帶確定GCP-Rec邊長*/

TGCP-Rec=Cre_gcp-rec(控制點數(shù)據(jù)，r[0])

else if(n==2)

TGCP-Rec=Cre_gcp-rec(控制點數(shù)據(jù)，r[0]，r[1])

(5)End if

(6)for(i=1；i<=M；i++)/*遍歷GCP-Rec*/

ListT/*聲明結(jié)果集變量*/

T=Intersect(影像數(shù)據(jù)，TGCP-Rec[i])

/*將空間求交結(jié)果存入結(jié)果集中，TGCP-Rec[i]為第i+1個索引矩形*/

Leaf-NodeConstructor(T)

/*對結(jié)果集構(gòu)建索引樹的葉子結(jié)點*/

(7)Output(GCP-Tree)/*輸出整棵樹*/

在GCP-Tree索引構(gòu)造算法中，影像點MBR的構(gòu)建采用郭慶勝等[16]提出的解算空間幾何對象的最小外包矩形算法進行構(gòu)建，空間疊加求交過程是在肖茁建等[17]提出的基于預(yù)存交點的矢量空間疊加分析算法基礎(chǔ)上略作修改后進行實現(xiàn)的。

2 實驗及分析

為了驗證本文算法的可行性，通過使用不同數(shù)據(jù)量以及不同實驗田的影像數(shù)據(jù)集對本文提出的GCP-Tree索引算法進行測試，并且與傳統(tǒng)的R樹索引算法以及四叉樹索引算法進行實驗對比，討論其空間查詢性能以及影響其算法性能的潛在因素。在硬件方面，實驗設(shè)備為華碩-K55VD電腦，搭載的是Windows 10操作系統(tǒng)，基本配置為i5-3210M雙核處理器，處理速度為主頻2.5 GHz至3.05 GHz，466 GB機械硬盤，RAM的容量為12 GB。

2.1 數(shù)據(jù)集和算法性能度量

本文所用實驗數(shù)據(jù)來源于多個實驗田的無人機采集。在效率對比實驗中，運用這些影像數(shù)據(jù)集構(gòu)造GCP-Tree、R樹以及四叉樹；在影響因素對照實驗中，僅構(gòu)造GCP樹索引結(jié)構(gòu)。上述實驗均以檢索耗時、構(gòu)建索引耗時作為衡量索引結(jié)構(gòu)優(yōu)劣的指標(biāo)。詳細(xì)的無人機航拍影像數(shù)據(jù)信息如表1所示。

表1 實驗數(shù)據(jù)信息表

圖4展示了數(shù)據(jù)集2的原始無人機影像數(shù)據(jù)(部分)；圖5展示了數(shù)據(jù)集3的影像航帶圖，圖中箭頭指示為航行方向，圖5(a)與圖5(b)中各點均為影像點，紅色點與灰色點代表的影像分別為第一次航行時拍攝與第二次航行時拍攝所得。

圖4 影像數(shù)據(jù)集示例

圖5 影像數(shù)據(jù)示例

2.2 實驗及結(jié)果分析

首先，使用GCP-Tree空間索引，對樹中子結(jié)點所代表的GCP-Rec進行展示(以數(shù)據(jù)集3為例)。如圖6所示，圖中最大的矩形是以所有影像點為基準(zhǔn)構(gòu)造的MBR；形狀上較大與較小的點分別為GCP與影像點；以GCP為中心的矩形為GCP-Rec。其次，通過實現(xiàn)R樹與四叉樹索引作為對比用來驗證GCP-Tree應(yīng)用于大規(guī)模無人機影像檢索的優(yōu)越性能。最后，分別從影像大小、影像數(shù)、GCP數(shù)以及GCP-Rec邊長這4個有可能影響算法效率的因素來測試本文所提算法的性能。

圖6 GCP-Rec結(jié)果圖

1) 索引構(gòu)建效率對比實驗。對7組不同規(guī)模的無人機影像數(shù)據(jù)分別構(gòu)建R樹、四叉樹與GCP-Tree索引并比較其構(gòu)建效率，實驗流程如圖7所示。為了使其具有可比性，所有構(gòu)建過程在單線程環(huán)境下進行。在構(gòu)建索引時，R樹索引采用STR算法批量構(gòu)建[18-19]，四叉樹與GCP-Tree索引均采用插入方式構(gòu)建。測試結(jié)果如表2所示，將數(shù)據(jù)轉(zhuǎn)為柱狀圖，如圖8所示。

圖7 索引構(gòu)建效率實驗流程簡圖

表2 3種索引構(gòu)造耗時統(tǒng)計表 s

圖8 3種索引構(gòu)造耗時比較

由圖8中7組不同規(guī)模的無人機影像數(shù)據(jù)索引構(gòu)建時間對比可知，相比四叉樹與R樹，GCP-Tree具有更高的構(gòu)建效率。隨著數(shù)據(jù)集要素量的逐漸增加，R樹與四叉樹索引構(gòu)建耗時明顯上升，而GCP-Tree索引構(gòu)建耗時上升相對平緩，這是因為GCP-Tree索引構(gòu)建時在數(shù)據(jù)插入過程中無需進行平衡樹結(jié)構(gòu)與結(jié)點分裂等耗時操作。

2)影像檢索效率對比實驗。實驗流程如圖9所示。首先，算法根據(jù)輸入的物理路徑獲取已知的GCP名稱與坐標(biāo)信息，經(jīng)過不同索引結(jié)構(gòu)的檢索；之后，輸出在歐氏空間中距離與GCP較近的影像數(shù)據(jù)集。

圖9 空間查詢效率實驗流程簡圖

按照圖9流程進行實驗后所得數(shù)據(jù)在表3中列出。檢索結(jié)果示例如圖10所示，圖中方框為GCP。圖11為3種索引應(yīng)用于7組不同規(guī)模影像數(shù)據(jù)的檢索耗時對比。從整體趨勢來看，這3種索引的檢索耗時都隨著影像數(shù)的增大而增加；且數(shù)據(jù)量較小時，3種索引的檢索效率相當(dāng)；隨著數(shù)據(jù)量的增大，GCP-Tree索引體現(xiàn)出較大的性能優(yōu)勢。

表3 3種索引檢索耗時統(tǒng)計表 s

圖10 檢索結(jié)果示例

從圖11可以看出，隨空間數(shù)據(jù)量的增加R樹的檢索耗時增幅最大。這是由于在構(gòu)建R樹時，隨著空間數(shù)據(jù)量的增加其葉子結(jié)點中存儲的空間實體對象MBR數(shù)量就會增加，超過結(jié)點的最大容量后會自動分裂，使樹的深度增加，空間查詢路徑增長，查詢效率也就降低了。四叉樹同理，隨著空間數(shù)據(jù)量的增加，更易滿足對某一區(qū)塊一分為四的條件，一分為四后樹的深度隨之增加，檢索路徑增長，使得檢索效率降低。使用GCP-Tree檢索時間增幅最小是因為無論空間數(shù)據(jù)量如何增加，樹的深度永遠(yuǎn)為3，且樹枝的個數(shù)與GCP個數(shù)保持一致，在查詢時僅需遍歷GCP-Tree的第2層結(jié)點數(shù)據(jù)域找到與輸入GCP名稱相同的分支即可。因此，從理論上分析可初步得出結(jié)論，GCP-Tree索引在檢索時間上的小幅增長是由于GCP個數(shù)增長引起的，但不排除其他潛在因素的影響。

圖11 檢索耗時比較

3) 潛在影響因素對照實驗。在GCP-Tree的構(gòu)建與應(yīng)用過程中，影像大小、影像數(shù)量、GCP的數(shù)量及GCP-Rec邊長的設(shè)定等可變因素在一定程度上均會對算法效率造成影響。在本節(jié)中，通過設(shè)置多組對照實驗，逐一討論上述多個可變因素在索引構(gòu)造與檢索影像過程中的影響。

圖12所示實驗為影像大小(寬與高)對算法效率的影響實驗，所用數(shù)據(jù)為數(shù)據(jù)集3～數(shù)據(jù)集7。在保證影像與GCP分布均勻的前提下，將數(shù)據(jù)集4～數(shù)據(jù)集7的影像數(shù)與GCP數(shù)調(diào)整到與數(shù)據(jù)集3一致，確保僅影像大小為變量。由圖中各數(shù)據(jù)集的索引構(gòu)造時間與影像檢索時間所構(gòu)成的點線圖走勢近乎水平可知，影像大小并不會對算法的效率造成影響。這是由于本文算法在構(gòu)建索引與檢索影像時用影像點代替了影像本身，未用到影像的寬與高，故在不同數(shù)據(jù)集影像數(shù)與GCP數(shù)均保持一致的情況下，其構(gòu)造時間與檢索時間均穩(wěn)定于某數(shù)值，無明顯浮動。

圖12 影像大小對算法效率的影響

圖13所示實驗為影像數(shù)量對算法效率的影響實驗，所用數(shù)據(jù)為數(shù)據(jù)集5～數(shù)據(jù)集7。在保證影像分布均勻的前提下，對數(shù)據(jù)集5～數(shù)據(jù)集7的影像數(shù)分別調(diào)整為5組影像，影像數(shù)量由少到多，其余變量均保持不變。由圖中各數(shù)據(jù)集的索引構(gòu)造時間與影像檢索時間所構(gòu)成的點線圖走勢可知，索引構(gòu)造時間與影像數(shù)量成正比關(guān)系，影像檢索時間不受影像數(shù)量的影響。這是由于本文算法在構(gòu)建索引時需對所有影像進行遍歷，而在影像檢索時僅需遍歷GCP，故在同一數(shù)據(jù)集中，GCP-Tree索引構(gòu)造時間隨著影像數(shù)量的增加而增加，而影像檢索時間幾乎穩(wěn)定不變。

圖13 影像數(shù)量對算法效率的影響

圖14所示實驗為GCP數(shù)量對算法效率的影響實驗，所用數(shù)據(jù)為數(shù)據(jù)集5～數(shù)據(jù)集7。在保證GCP分布均勻的前提下，對數(shù)據(jù)集5～數(shù)據(jù)集7的GCP數(shù)分別調(diào)整為5組，GCP數(shù)量由少到多，其余變量均保持不變。由圖中各數(shù)據(jù)集的索引構(gòu)造時間與影像檢索時間所構(gòu)成的點線圖走勢可知，構(gòu)造時間和檢索時間均隨GCP數(shù)量增加而增加，構(gòu)造時間增幅較小，檢索時間增幅較大。這是由于本文算法在構(gòu)建索引階段對影像遍歷的同時需逐一對每個GCP分枝進行葉子結(jié)點填充，但影像數(shù)量遠(yuǎn)遠(yuǎn)大于GCP數(shù)量，故GCP數(shù)量對構(gòu)造時間的影響較小，而在影像檢索時僅需遍歷GCP，此時GCP數(shù)量對檢索時間影響較大。因此，在同一數(shù)據(jù)集中，GCP-Tree構(gòu)造時間與影像檢索時間均隨GCP數(shù)量的增加而增加，構(gòu)造時間增幅小，檢索時間增幅大。

圖14 GCP數(shù)量對算法效率的影響

圖15所示實驗為GCP-Rec邊長對算法效率的影響實驗，所用數(shù)據(jù)為數(shù)據(jù)集5～數(shù)據(jù)集7。通過設(shè)定不同的GCP-Rec邊長對影像的檢索時間、檢索數(shù)量及其精確率進行測定。圖中橫軸為航帶間距的倍數(shù)(如r指航帶間距；2r指2倍航帶間距)，左縱軸為檢索時間，右縱軸為檢索精確率(式(2))與平均檢索量(式(3))的比值R(式(4))。式中的檢索總量是指對各個GCP進行檢索后得到的所有影像數(shù)之和。

(2)

(3)

(4)

圖15 GCP-Rec邊長對算法效率的影響

隨著GCP-Rec邊長的增加，檢索總量會大幅增加，故檢索精確率將大幅降低，平均檢索量將逐步增加，單獨用其中一個做實驗太過片面，采用二者比值R來衡量檢索的精確度更全面科學(xué)。通過分析現(xiàn)有數(shù)據(jù)發(fā)現(xiàn)，在各影像數(shù)據(jù)集中包含GCP的影像數(shù)均接近GCP個數(shù)的6倍，因此，在保證檢索精確率在80%～100%的前提下平均檢索量應(yīng)保持在6～8幅，即R保持在0.1～0.16之間時最優(yōu)。從圖中可知，R值在上述范圍內(nèi)所對應(yīng)的邊長范圍均為2.0r～2.4r，因此，當(dāng)GCP-Rec邊長為2.0r～2.4r時檢索精度最高。這也是上文使用2倍航帶間距作為GCP-Rec邊長的原因。

由圖中各數(shù)據(jù)集的檢索時間所構(gòu)成的點線圖走勢可知，檢索時間不受GCP-Rec邊長的影響，這是由于本文算法在影像檢索時僅遍歷GCP，通過GCP對應(yīng)的指針域找到目標(biāo)影像數(shù)據(jù)集，無需再使用GCP-Rec，故在同一數(shù)據(jù)集中，影像檢索時間隨著GCP-Rec邊長的增加幾乎穩(wěn)定不變。

綜上，索引構(gòu)建效率與影像數(shù)量、GCP數(shù)量均呈反比關(guān)系，其中影像數(shù)量為主要因素；影像檢索效率與GCP數(shù)量成反比關(guān)系。

3 結(jié)束語

無人機遙感以其應(yīng)用便捷、實時性強、所獲影像分辨率高等特點近些年受到了廣泛關(guān)注。為了從具有GCP信息及POS信息的大規(guī)模無人機影像數(shù)據(jù)集中快速、準(zhǔn)確地檢索出包含指定GCP的目標(biāo)影像，本文提出了一種基于GCP的大規(guī)模無人機影像檢索算法。該算法可以根據(jù)輸入的無人機影像在計算機中的物理路徑，在較短時間內(nèi)自動地構(gòu)建出樹形空間索引，并可根據(jù)輸入的參考點(GCP)信息，快速檢索出包含該GCP的目標(biāo)影像。實驗結(jié)果表明，對于大規(guī)模的無人機影像，利用本文方法檢索影像的效率高，檢索花費的時間保持在秒級以內(nèi)，較大程度緩解了空三加密中人工選取目標(biāo)影像進行控制刺點的工作量，提高了刺點的效率。目前，本文提出的GCP-Tree空間索引方法已實踐應(yīng)用，在影像檢索方面效果顯著。然而，該方法仍存在一定局限性，針對超大規(guī)模測區(qū)中布設(shè)的地面控制點數(shù)量M較多(如M>1 000)的情況，索引構(gòu)建效率及影像檢索效率不是特別理想，可能需要設(shè)置自適應(yīng)控制點數(shù)量閾值，分區(qū)塊或分層建立多個索引樹進行影像檢索。在今后的研究中，將進一步深入研究控制點數(shù)量閾值自動選取并設(shè)置的問題，以提高該檢索算法的適用性。