基于GCP的大規模無人機影像檢索方法

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

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

0 引言

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

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

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

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

1 GCP-Tree樹形空間索引

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

1.1 基本定義

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

2)影像點(image point)：指由影像GPS坐標經投影轉換后的大地平面坐標所構成的點。

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

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

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

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

圖1 GCP-Tree樹結點結構示意圖

1.2 GCP-Tree索引算法概述

首先，計算出同一測區中所有影像點的MBR，生成以該MBR左下頂點為原點的二維直角坐標系；其次，構建GCP-Rec；最后，依據GCP-Rec對當前影像數據建立索引，生成GCP-Tree。

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

對照圖3，以下為該索引的詳細構造流程。

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

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

3)流程。

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

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

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

圖3 GCP-Tree構造過程框架圖

(3)以航帶間距r為基準，構建GCP-Rec。

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

(1)

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

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

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

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

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

3)用到的封裝函數。

(1)Cre_mbr(影像數據)/*創建MBR*/

(2)Cre_gcp-rec(控制點數據，r[n])/*創建GCP-Rec*/

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

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

(5)Input(輸入數據)和Output(輸出數據)

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

(1)Cre_mbr(影像數據)

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

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

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

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

else if(n==2)

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

(5)End if

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

ListT/*聲明結果集變量*/

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

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

Leaf-NodeConstructor(T)

/*對結果集構建索引樹的葉子結點*/

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

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

2 實驗及分析

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

2.1 數據集和算法性能度量

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

表1 實驗數據信息表

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

圖4 影像數據集示例

圖5 影像數據示例

2.2 實驗及結果分析

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

圖6 GCP-Rec結果圖

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

圖7 索引構建效率實驗流程簡圖

表2 3種索引構造耗時統計表 s

圖8 3種索引構造耗時比較

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

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

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

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

表3 3種索引檢索耗時統計表 s

圖10 檢索結果示例

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

圖11 檢索耗時比較

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

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

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

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

圖13 影像數量對算法效率的影響

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

圖14 GCP數量對算法效率的影響

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

(2)

(3)

(4)

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

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

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

綜上，索引構建效率與影像數量、GCP數量均呈反比關系，其中影像數量為主要因素；影像檢索效率與GCP數量成反比關系。

3 結束語

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