低空无人机影像匹配像对的提取方法

任超锋，彭晓东

(1. 长安大学 地质工程与测绘学院，陕西 西安 710054;2. 长安大学 西部矿产资源与地质工程教育部重点实验室，陕西 西安 710054)

在传感器技术高速发展的信息化测绘时代，利用无人机(unmanned aerial vehicle，UAV)低空遥感平台快速地获取地表数据成为研究的热点[1]。目前，除了搭载单镜头相机进行垂直航空摄影外，机载倾斜多相机系统的发展也已成为城市三维重建的主要数据源。由于无人机影像像幅较小，相机数量多，导致测区内的航片数量剧增。因此，一种通用且快速的无人机影像匹配算法，成为制约低空无人机影像数据生产的关键步骤之一。

总体上可将无人机影像匹配分为三步：第一步，选择待匹配像对，提取各影像特征点；第二步，对当前像对进行粗匹配，获取初始同名点对；第三步，对当前像对进行精匹配，剔除同名点对中的误配点。

针对第一步，brute-force search是最稳定、最可靠的待匹配像对选择方法，它采用穷举法判定数据集内所有可能存在的像对，也称为盲匹配，但该方法效率太低，不具有可操作性。文献[2-4]利用倾斜相机的检校参数及定位定向系统 (Positioning and Orientation System，POS系统) 数据，计算各个子相机的粗略外方位元素，利用平均高计算每张影像在“水平面”的脚印范围，进而确定相邻影像是否重叠。文献[5]则是利用下视影像进行空三获取精确外方位元素后，进而扩展至各个子相机，获取其相应外方位元素。上述几种方法的核心环节是采用地面平均高方式计算每张影像的脚印图，进而判定像对是否具有重叠区。然而，受地形起伏及飞行平台稳定性等综合因素影响，采用这类方法往往会遗漏一定数量的待匹配像对，使后续的自动空中三角测量存在严重隐患。此外，倾斜相机设计参数及测区先验知识也不宜获得，进一步降低该类方法的适用性。当选择一对影像作为待匹配像对后，需分别对其进行特征点提取。文献[2]对比常用的SIFT[6],ASIFT[7],AIF[3]等3种特征提取算子。其区别在于是否根据相机的设计参数，将“倾斜”影像纠正为近似“水平”影像，然后在“水平”影像上提取SIFT特征，之后再根据子相机相对关系将特征点反算回原始影像。采用这类方法，可有效提高特征点数量，改善匹配效果，但直接在原始影像上提取SIFT特征，理论更严密，且试验结果表明，直接在原始影像上提取特征点，其数量及分布也可满足精度需求。

针对粗匹配阶段，文献[8]提出一种利用GPU进行双向穷举法进行同名点粗匹配，但该方法耗时随特征点数量的提升呈指数增长。文献[9]根据多维空间最临近搜索方法，获取当前特征点的同名像点，但需要首先创建特征空间搜索索引，两种方法各有适用范围。最后，利用随机一致性约束算法[10](Random Sample Consensus, RANSAC)剔除同名点粗差，完成同名像点匹配。

鉴于此，本文设计一种通用的无人机影像匹配算法，从选择待匹配像对入手，以影像的初始空间位置关系为依据，完成部分像对的影像匹配。之后，根据同名点列表跟踪连接点，利用连接点信息对遗漏的像对进行自动识别，同时构建CPU与GPU混合模式，以提高影像粗匹配效率。最后选取常规无人机影像与倾斜影像进行对比试验，以证实本文方法的适应性和高效性。

1 无人机影像快速匹配流程

本文提出的无人机影像快速匹配算法流程，如图1所示。

图1 无人机影像快速匹配算法流程图

1)导入POS信息中的影像位置信息，计算当前第i张影像与之后所有影像投影中心之间的空间距离，并按照降序排列；

2)以第i张影像为左影像，以降序影像集合为右影像，顺次构成待匹配像对；

3)对当前选择的像对进行粗匹配与精匹配，获取其同名点列表；

4)判定当前匹配过程中，是否已经超过最大搜索深度；

5)利用两两匹配结果，跟踪测区内连接点关系；

6)根据连接点结构信息，搜索遗漏的待匹配像对；

7)完成遗漏像对影像匹配，并输出匹配结果。

2 无人机影像快速匹配算法

2.1 选择待匹配像对

由于无人机影像有效覆盖范围小、数量庞大，且影像间的重叠关系随着地形、地貌的变化而变化，因此以最小的计算量，稳健、可靠的选择待匹配像对是影响匹配算法效率的关键环节。空间距离上越近的影像具有重叠区的可能性越高，因此本文首先根据影像初始POS信息中的X,Y,Z坐标，计算当前影像与其后所有影像的欧式空间距离，然后按照距离关系进行降序排列，之后，依次完成当前影像与排序影像之间的影像匹配。

如图2所示，假设测区包含n张影像，影像i为当前选择的左影像，影像jk,k∈[0,7]为影像i之后的待选右影像。对所有jk影像按照距离进行降序排列，结果为(j2

图2 待匹配像对选择方法

2.2 像对同名点匹配

当确定一组像对后，分别提取其SIFT特征及特征向量，并利用特征向量的距离比值作为同名像点的相似性判定测度，获取像对的初始同名点列表，之后利用RANSAC剔除误配点。其中，获取初始同名点列表总体上可分为两种：穷举法、构建索引法。

穷举法依次完成左影像至右影像特征向量之间的距离对比，若左、右影像中特征向量数目均为N，则该算法的时间复杂度为O(N2)。为了进一步提高该算法效率，本文利用GPU对穷举法匹配进行并行加速。

构建索引法首先利用K-D树建立右影像特征向量的空间索引，再计算特性向量之间的距离比值。该算法耗时主要包含两部分，构建索引和计算距离比值，其时间复杂度为O(N+N)。穷举法耗时随着特征数量增加呈指数增加，前者适合特征点数量较少情况，后者适合特征点数量较多情况。本文采用穷举法与构建索引法相组合的方法完成同名点的初始匹配，并分别以GPU粗匹配与CPU粗匹配进行标识，其算法流程如图3所示。

图3 像对同名点匹配流程

2.3 识别遗漏待匹配像对

先验知识的不确定性会造成测区内遗漏一定数量的待匹配像对。根据连接点的结构信息，自动识别遗漏的待匹配像对。首先，按照文献[12]中数据结构算法，获得的同名点列表中跟踪搜索连接点。在同一连接点内，按照排列计算方式，任意选择两幅影像构成待匹配像对。若该像对从未匹配过，则该像对为遗漏待匹配像对。

如图4中所示，假设测区内的4张影像A，B，C，D已完成两两匹配。即AB，BC，CD像对同名点列表已知。之后进行连接点跟踪获得4度连接点P，该连接点在影像A，B，C，D上的像点坐标依次为pa，pb，pc，pd。从连接点的结构信息中可知，A，B，C，D影像对同一地面点P均有成像，即同一连接点内所有影像之间均具有重叠度，因此，从该连接点内任意提取两张影像即可构成待匹配像对。如图4所示，AC，AD，BD为遗漏的待匹配像对。

图4 识别遗漏待匹配像对

按照图4所示方法，依次对所有连接点进行识别，获取所有遗漏像对信息，按照2.2节方法完成剩余像对的匹配工作。

3 试验与分析

3.1 试验数据

为了验证本文算法的有效性，试验选取典型的3种相机数据：单相机、双相机、五相机影像数据。其中单相机为索尼ILCE-5100拍摄的下视影像。双相机由2台索尼ILCE-QX1相机组成，构成一左、一后排列，采集数据时按照航线往返飞行，模拟出倾斜四相机影像。五相机由5台索尼ILCE-5100相机组成，1台采集下视数据，4台分别采集前、后、左、右倾斜影像数据。试验数据的相关属性描述见表1。硬件平台为Windows7 64位操作系统、处理器为i7-4910MQ、主频2.9 GHz、显卡为英伟达Quadro K2100M 2G独立显存、内存32 GB。本文匹配算法基于VC++ 2015、CUDA8.0进行开发。

表1 试验数据影像描述

3.2 试验过程与分析

3.2.1 影像分块大小对SIFT特征提取效率的影响

当获取原始影像后，首先依次提取影像的SIFT特征。文献[6]提出一种GPU并行加速的SIFT特征提取算子SiftGPU，提升SIFT特征算子的计算效率。然而由于显卡存储资源有限，SiftGPU算子无法直接对原始影像进行处理。本文采用分块提取的策略，将原始影像划分为规则格网，依次提取格网内影像的SIFT特征，之后将所有SIFT特征进行合并。为了能将影像划分为整数格网，格网宽度设置为2的倍数。以100张索尼ILCE-5100影像为例，统计不同格网大小时SIFT特征提取的总耗时(包含影像读取)，按平均值计算其单张影像耗时如表2所示。

表2 不同格网大小时影像SIFT特征提取时间

从表2可知，格网越大单张影像的SIFT特征提取效率越高，其主要原因在于格网划分太小单次提取SIFT特征无法充分发挥显卡的运算能力。因此在显存允许前提下，SIFT特征提取时格网越大越好。基于表1影像尺度信息及表2结果，本文算法将所有原始无人机影像划分4块分块子影像提取SIFT特征。

3.2.2 特征点数量对粗匹配效率的影响

由SIFT算法原理可知，SIFT特征点是在差分高斯差分金字塔影像中进行提取，最终获得的特征点也分布于不同的高斯差分金字塔影像中。通常，一张普通无人机影像可提取数万个特征点，对于大部分应用而言数据量过大，因此实际使用中会根据具体的应用需求对特征点进行取舍。SiftGPU在高斯差分金字塔影像中采用从上往下的方式，分层保留提取的特征点，直至满足用户设置的特征点数量。

当获取像对SIFT特征点之后，即可按照GPU并行、或者CPU索引两种方式进行像对粗匹配。为了评价特征点数量对粗匹配效率的影响，本文依次设置保留2 000、4 000、6 000、8 000、10 000个特征点，从双相机影像中提取200组(400张)影像，按照图3所示流程，分别统计两种粗匹配方式的耗时，如图5所示。

从图5中可知，当特征点数量逐渐增加时，GPU并行方式耗时急剧增高，而CPU索引方式耗时与特征点数量成线性比例关系，且两种方式的特征点阈值约为7 000个。

3.2.3 算法可靠性对比分析

验证本文匹配方法的可靠性，分别采用盲匹配、脚印图和本文方法对表1所示的3种数据进行匹配，分别统计待匹配像对数量、最终匹配成功的像对数量、并计算其相应的可靠度。本文将待匹配像对完成匹配后，获得的同名点数量不小于16对时认定为具有重叠区的像对，结果如表3所示。

由于盲匹配是将测区所有影像进行两两匹配，可靠性最高，其结果可作为测区数据的真实情况进行对比分析，因此其可靠度为100%。其它两种方法的最终匹配结果与盲匹配的结果进行比值，计算其相应的可靠度。由表3可知，按照脚印图方法选择待匹配像对时会有少量遗漏像对，其原因主要在于该算法对输入的POS数据、地形参数、及相机设计信息高度相关，而这些数据的不准确性导致遗漏了一定数量的待匹配像对。与脚印图算法相比，本文算法的可靠性均得到提升。其中，单相机数据提升2.4%，双相机数据提升5.3%，五相机数据提示24.3%。可靠度提升的原因在于本文算法选择的待匹配像对数量较多，同时无效匹配也相应减少，且相机镜头数量越多，可靠度提示幅度越大。此外，括号内为自动识别的遗漏待匹配像对，可见本文的识别遗漏像对算法有效，进一步提升算法的可靠度。

图5 不同特征点数量的粗匹配耗时

单相机双相机五相机盲匹配脚印图本文方法盲匹配脚印图本文方法盲匹配脚印图本文方法待匹像对/个108 34516 85524 042499 50078 93162 96424 042323 111411 080最终像对/个8 5188 3128 518(775)22 39917 41518 600(1 397)41 51430 50840 583(3 905)可靠度/%10097.610010077.783.010073.597.8

3.2.4 算法效率对比分析

为了评价本文算法的效率，提取SIFT特征时将特征点数量设置为2 000个，分别统计特征提取、粗匹配、精匹配阶段的耗时，结果如表4所示。

表4 3种匹配方法分阶段耗时 s

分析表4可知，特征提取阶段用时比较固定，主要与影像数量相关，精匹配环节所占时间也非常少，匹配算法中耗时最多的为粗匹配过程，因此，决定无人机影像匹配算法效率的关键环节在于，是否能够高效选出真正具有重叠度的待匹配像对。本文算法总体耗时与脚印图算法相比略有增加，其中单相机耗时增加19.6%，五相机耗时增加16.4%。由于双相机为一种特殊类型相机，同一站点的4张倾斜影像通过往返飞行而得，造成同一组影像之间空间姿态的不确定性增大，因此利用POS数据计算所得脚印图精度也更低。而本文算法不考虑影像的空间姿态，得到的待匹配像对总体数量上少于脚印图算法，所以总体耗时减少了16.2%。

4 结束语

本文针对低空无人机影像的自动匹配算法进行研究，试验选取典型的3种影像数据，结果表明：

1)本文算法具有较高的适用性。不需要相机、地形、航摄等参数即可自动完成无人机影像匹配。

2) 本文算法具有较高的可靠性。与脚印图算法相比，单相机数据提升2.4%，双相机数据提升5.3%，五相机数据提示24.3%。

3)本文算法效率适当。与脚印图算法相比，单相机耗时增加19.6%，五相机耗时增加16.4%，双相机耗时减少16.2%。