基于GCP的大規(guī)模無人機(jī)影像檢索方法

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

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

0 引言

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

國(guó)外空間索引的研究成果最早可追溯到20世紀(jì)70年代，由Finkel等[8]于1974年提出的四叉樹索引，是一種樹形索引結(jié)構(gòu)，除葉子結(jié)點(diǎn)的其余結(jié)點(diǎn)均有4個(gè)子域，將地理空間均勻地劃分成4個(gè)象限。Bentley[9]于1975年提出多維二叉搜索樹(KD樹)，KD樹為每個(gè)點(diǎn)都是K維點(diǎn)的二叉樹，其對(duì)點(diǎn)對(duì)象的查找與平衡二叉樹同樣高效。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)對(duì)數(shù)據(jù)量較大的空間檢索時(shí)所需硬盤空間巨大，具有局限性。Leutenegger等[12]于1997年提出了基于R樹的批量加載算法(sort tile recursive，STR)。

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

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

1 GCP-Tree樹形空間索引

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

1.1 基本定義

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

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

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

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

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

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

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

1.2 GCP-Tree索引算法概述

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

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

對(duì)照?qǐng)D3，以下為該索引的詳細(xì)構(gòu)造流程。

1)輸入。計(jì)算機(jī)中無人機(jī)影像物理路徑與M個(gè)地面實(shí)測(cè)控制點(diǎn)數(shù)據(jù)。

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

3)流程。

(1)計(jì)算影像點(diǎn)的MBR，對(duì)樹結(jié)點(diǎn)的各項(xiàng)信息做初始化操作。

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

注：左圖中指影像點(diǎn)；指地面控制點(diǎn)；以G1～G4為中心的方框?yàn)镚CP-Rec。圖2 GCP-Tree索引樹的生成過程實(shí)例

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

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

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

(1)

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

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

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

1)輸入。影像數(shù)據(jù)、控制點(diǎn)數(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(控制點(diǎn)數(shù)據(jù)，r[n])/*創(chuàng)建GCP-Rec*/

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

(4)Leaf-NodeConstructor(單個(gè)影像編號(hào))/*構(gòu)建葉子結(jié)點(diǎn)*/

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

4)過程。GCP-Tree(影像數(shù)據(jù)，控制點(diǎn)數(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邊長(zhǎng)*/

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

else if(n==2)

TGCP-Rec=Cre_gcp-rec(控制點(diǎn)數(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個(gè)索引矩形*/

Leaf-NodeConstructor(T)

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

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

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

2 實(shí)驗(yàn)及分析

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

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)信息表

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

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

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

2.2 實(shí)驗(yàn)及結(jié)果分析

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

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

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

圖7 索引構(gòu)建效率實(shí)驗(yàn)流程簡(jiǎn)圖

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

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

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

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

圖9 空間查詢效率實(shí)驗(yàn)流程簡(jiǎn)圖

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

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

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

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

圖11 檢索耗時(shí)比較

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

圖12所示實(shí)驗(yàn)為影像大小(寬與高)對(duì)算法效率的影響實(shí)驗(yàn)，所用數(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)造時(shí)間與影像檢索時(shí)間所構(gòu)成的點(diǎn)線圖走勢(shì)近乎水平可知，影像大小并不會(huì)對(duì)算法的效率造成影響。這是由于本文算法在構(gòu)建索引與檢索影像時(shí)用影像點(diǎn)代替了影像本身，未用到影像的寬與高，故在不同數(shù)據(jù)集影像數(shù)與GCP數(shù)均保持一致的情況下，其構(gòu)造時(shí)間與檢索時(shí)間均穩(wěn)定于某數(shù)值，無明顯浮動(dòng)。

圖12 影像大小對(duì)算法效率的影響

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

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

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

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

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

(2)

(3)

(4)

圖15 GCP-Rec邊長(zhǎng)對(duì)算法效率的影響

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

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

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

3 結(jié)束語

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