基于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)的情况，索引构建效率及影像检索效率不是特别理想，可能需要设置自适应控制点数量阈值，分区块或分层建立多个索引树进行影像检索。在今后的研究中，将进一步深入研究控制点数量阈值自动选取并设置的问题，以提高该检索算法的适用性。