论文推荐｜赵红蕊：基于特征尺度分布与对极几何约束的高清影像快速密集匹配方法

《测绘学报》

构建与学术的桥梁 拉近与权威的距离

赵红蕊, 陆胜寒

清华大学3S中心土木系地球空间信息研究所, 北京 100084

收稿日期：2017-12-09；修回日期：2018-03-19

基金项目：国家自然科学基金（41571414）

第一作者简介：赵红蕊(1969-), 女, 博士, 教授, 研究方向为遥感与摄影测量。E-mail:[email protected]

摘要：本文重点阐述了基于机器视觉的智能摄影测量的效率基础问题之三：高清影像快速智能匹配处理。图像特征匹配是影响数字摄影测量坐标空间计算效率的基础数据处理过程。为了解决高分辨率数据匹配校验计算成本更高及相似特征干扰等影像产品生成效率负面影响问题，本文通过研究影像尺度不变特征的数学本质，结合多视图相机几何模型，推导并验证了图像特征点的降采样尺度分布规律。根据图像空间几何关系在降采样尺度上的匹配映射关系，缩减图像匹配过程中的计算量并筛选有效待匹配点集，将特征点数量10⁵量级的快速全局特征距离初匹配时长限制在亚秒级。在此基础上结合特征尺度分布信息改进的对极几何约束，改进特征匹配算法，辅助缩小匹配搜索范围，通过特征索引与分区并行处理，实现高清影像同名特征的高精度快速密集匹配，提升特征点基数、匹配特征点对数量与正确率。本文使用intel i7-4720HQ与NVIDIA GTX970M进行试验，基于尺度分布特性的特征匹配方法，以亚秒级的计算时间，获取符合多约束条件的10

Dense High-definition Image Matching Strategy Based on Scale Distribution of Feature and Geometric Constraint

ZHAO Hongrui , LU Shenghan

Abstract: This paper mainly expounds the basic issue three about the intelligent photogrammetry based on machine vision:the intelligent and fast matching process among high-definition images.Image feature matching, as a fundamental data processing procedure, plays an important role in the computational efficiency of computing the digital photogrammetry coordinate space.There are challenges for image feature match including high computational expense due to high-resolution data and similar feature interference.Concerning these problems, the mathematical nature of the invariant feature of image scale was studied, and the geometric model of multi-view camera was used to derive and verify the scale distribution of image feature points.The information interaction process of the scale component in the feature extraction and the matching process was determined.Through the equal-scale feature matching, the calculation amount in the image matching process was reduced and the effective information was retained, which greatly reduced the time of the initial distance matching progress among 10⁵points in 1 second.On this basis, combining the feature scale distribution and the geometric constraint, the improved feature matching algorithm was used to reduce the matching search range under the limited time and the computational scale.Fast and dense matching achieves through the feature index and the partition parallel processing.Using intel i7-4720HQ and NVIDIA GTX970M, the experiment shows that the feature matching method based on the scale distribution feature has a great advantage in improving the speed and accuracy of automatic image matching and matches thousands of points in less than one second.It provides a new idea for the fast and high precision processing of digital images, which can not only meet the accuracy of digital photogrammetry but greatly improve the efficiency of production.

Key words: scale invariant feature scale constraint epipolar geometry dense matching

随着航空摄影平台的普及，倾斜摄影测量以其便捷的数据采集方式，在地形建模等应用中发挥巨大的作用。最初，高清影像为空载LiDAR建模提供纹理^[1]，随着计算机视觉理论在该领域的深入应用，直接基于影像、平台坐标与地面控制点的空中三角测量技术使得影像数据具备建立场景空间结构的功能。随着影像数据在质与量的升级，以及自由度更高的无定姿影像智能建模等应用的兴起，三维重建算法对影像特征匹配的正确率、匹配点数量与精度均提出更高的要求。

同名匹配点为计算不同影像对极几何关系提供依据，也是算得投影矩阵后，通过前方交会获取三维点云的基础数据。若识别每一像素点在其余影像中的同名匹配点，可生成像素密度的点云模型。然而，由于影像深度、被摄物体几何特征与纹理特征等信息的缺失，同名点匹配存在多解及误匹配等复杂现象，导致最终确定的匹配点分布稀疏，浪费了大量分布的特征点信息，在此基础上计算所得的三角网无法充分表现被摄物体复杂的局部细节结构。高清影像具有更多特征点，改善了此类情况，但又导致特征匹配的计算规模增大。

基于特征距离，在另一幅图像中搜索当前特征点的匹配同名点，需要遍历特征向量，搜索最临近数值。由于图像特征信息为高维向量^[2]，随着特征点数量的增加，影像匹配的计算量成为其主要矛盾^[3]。对128维SIFT特征向量，在两图像各有10⁵数量的特征点时，全局特征匹配所需的计算空间达到100 GB以上，不利于高密度点云建模方法在小型计算机上的推广。

随着相机画幅与分辨率的提升，同名点匹配搜索过程中，理论上的唯一匹配点将受到更多潜在可行解的干扰。图 1显示了直接特征匹配中由于搜索集中的相似特征造成的错误匹配。为提高大量特征点之间的匹配正确率，需通过筛选匹配结果等方式改进特征匹配算法^[4]，进一步增大计算量。因此，高清影像的无定姿匹配对同名点匹配算法提出了高效、抗干扰与计算规模的新需求^[5]。为提高匹配结果的正确率，现有方法通过增加约束，如滑动窗口^[6]进行匹配点的筛选；结合仿射变换扩展的SIFT特征

图 1 直接特征匹配中包含错误与误差Fig. 1 Direct feature matching contains errors

图选项

为控制特征匹配时空开销，采用了以下几种方式：

使用内核投影等方法，对特征向量降维，减少特征的存储与运算开支^[12]；通过距离计算方式的简化，以准欧氏距离代替欧氏距离等方法减少特征向量距离计算的计算量^[13]；采用更高效的数据结构，使用KD-Tree^[14]及其改进SP-Tree执行最临近匹配点的搜索，以损失部分匹配点为代价提升整体匹配速度^[15]；通过改进硬件方案，使用GPU提升计算速度^[16]等。随着GPU技术的发展，其在此类任务中相对CPU的优势越发明显^[17]，以及相关开源库^[18]和CUDA编程环境的出现^[19]，传统特征提取算法的计算速度得到了显著提升，甚至实现了实时匹配^[20-21]。此类方法都通过减少搜索过程中的计算时间实现匹配速度的提升。但是，缩小潜在的计算规模，才是真正兼顾计算速度与准确性的方法。

由于影像具有全局结构特征，通过简单分割限制空间搜索域的方式将造成同名点分布断裂与匹配错误^[22]。而特征点信息除特征向量与图像坐标外，还包括尚未被发现和应用的尺度分量和主方向分量，其具有限制计算规模、提供多余约束的潜力。通过简单的等尺度匹配，可在尺度变化较小的图像中更快建立同名点匹配关系^[23]。可见，研究尺度约束的严格理论推导以及对一般位置关系影像匹配计算的推广有重要意义。

此外，图像同名点在三维重建各阶段的作用不同。计算图像对极几何约束，恢复投影矩阵所需的同名点对数量远小于图像特征点数量，而恢复被摄场景密集三维点云所需的同名点对数量应接近图像分辨率。因此，同名特征点对的匹配算法需要动态适应不同计算阶段的功能需求，实现计算资源的合理利用。

针对以上高清影像特征匹配中，计算规模庞大，相似特征干扰下匹配正确率较低等问题，以及适应相机与场景建模的不同需求，本文通过改进图像分块匹配中，分块边界的割裂产生的特征不完整与匹配区域不连续问题，结合尺度不变特征的数学本质，提出针对相机空间高精度估计的基于特征尺度分布的快速高精度特征点初匹配，以及针对高密度点云建模的基于多约束条件的高精度匹配加密方法，在显著改进匹配正确率与数量的同时，使匹配总时长与计算空间可控。

1 研究方法

以建立图像密集匹配关系为目的，在特征提取方面，通过对图像分块加密特征点方法^[24]的改进，提取高清图像的密集特征点集合。研究尺度不变特征的计算过程，建立影像特征点数量与图像降采样尺度分布关系模型，通过不同尺度影像同名点对匹配试验对模型进行验证，量化分析尺度分量在缩减潜在匹配集合规模的能力。

在特征匹配方面，通过初匹配结果建立额外约束，控制匹配计算的规模，确保匹配集合的稳定性、数量与精度。具体包括：①根据中位数截断法保留相似概率更低的大尺度特征点，实现初始特征匹配过程中计算规模的指数级缩减；②利用稳定的初始匹配点计算两视图基础矩阵与尺度约束比例因子，缩小潜在匹配点的分布范围，建立密集匹配；③采用并行处理方法与GPU加速实现多幅图像中匹配数量的快速初步估计，筛选高重叠度图像并建立密集匹配关联，为后续三维重建步骤提供可靠的基础数据。

1.1 改进的分块图像特征提取与特征索引结构

特征点匹配的最终目的是确定图像之间密集的同名点对。为实现此目标，作为匹配过程的基础数据，各图像特征点应具备较高的密度。图像分块匹配方法限制计算规模与相似特征的检索范围，一定程度上解决高清影像的高密度特征匹配问题，且图像不同区块间关联度低，适用于GPU并行加速计算。然而，分块边缘的不连续点将产生如图 2所示匹配点断层。此外，对于存在旋转、仿射变换的图像，潜在匹配点分布区域的变形也将降低分块匹配正确率。本文对文献[24]中图像分块匹配方法进行改进，提出针对高分辨率影像特征的分块并行提取方法。

图 2 直接分块导致的匹配点断裂带Fig. 2 Direct blockage caused by the matching point fault zone

图选项

本文对原始高清影像划定重叠分块，通过限制单个分块的大小，控制特征提取的计算时间与数据规模，如图 3所示。分块内只提取中部的特征点，删除分块边缘图像不连续产生的错误特征点。各分块存在重叠的公共区，确保特征点的提取范围在图像内分布的均匀和连续。对于图像边界的区块，将原有的特征提取区扩大到各编号分块对应的划分范围，实现高清影像的密集特征提取。

图 3 高清影像并行分块特征提取方法Fig. 3 Parallel block feature extraction method for high resolution images

图选项

使用本文的分块SIFT与SURF针对相同影像的特征点提取结果如图 2所示。图中，本文方法提取特征点数量为134 407，而相同试验数据在所得的SURF特征点数量为15 432，本文所得特征点数量大于直接SURF方法。通过图像放大可知，本文方法在相同计算时间内捕获了更多高频的图像细节特征点。正确建立这些特征点的匹配关系，恢复其对应的空间位置可提升场景建模的精度与细节。

图 4 本文分块SIFT与全局SURF特征点提取结果对比Fig. 4 The comparison between the extracted feature points through the proposed block SIFT and global SURF

图选项

为避免计算过程中反复读取高维特征向量，对点坐标与特征向量、尺度参数与特征方向建立编号索引。计算过程中仅根据索引保存匹配关系，减少中间计算结果的数据量。

1.2 尺度不变特征与图像分辨率限制下的特征幂率分布

现有的尺度不变特征提取方法，通过改变特征响应模板与图像的比例，得到不同尺度下的特征响应

(1)

因此，所有尺度不变特征提取算子的计算过程，都体现出小尺度特征点的采样计算次数远大于大尺度特征点的性质，造成特征点数量在尺度上呈现类似幂律分布的结果。而可提取的特征点为其中的极值点，是模板位置集合的子集，因此其数量随尺度变化呈近似幂率关系，如图 5所示。尽管SIFT与SURF等特征具有尺度不变性，不同方法存在精度与计算速度的差异^[25]，但亚像素细节的损失，使其失去了对应的小尺度特征。图 3中左右视图已匹配同名点的连接线数量，随着同一物体在相同分辨率图像中所占面积的缩小而减少，匹配点对应的尺度分量差距则随之增大。因此，特征的尺度分量，是决定特征分布与潜在匹配点集的重要参数。

图 5 影像特征点数量在尺度分量遵循幂律分布Fig. 5 The number of image feature points follows the power law distribution in the scale component

图选项

1.3 基于特征幂率分布的搜索集快速收敛方法

特征匹配时，图像k₁中，第i₁个特征点对应的特征向量以式(2)表示

(2)

其与图像k₂中，第i₂个特征点对应特征向量的内积以式(3)表示

(3)

式中，归一化特征向量内积即为向量夹角θ的余弦值。通过最临近与次临近夹角余弦值的比例，以式(3)结果决定是否选择最临近夹角对应向量作为匹配的特征向量。可见，比例限值ratio越小，所得匹配点相比其余点的相似度更高，匹配筛选更严格。在大量相似特征存在的情况下，小ratio值只能匹配极少量的匹配点

(4)

本文针对尺度不变特征点的生成过程，推导并验证了此类特征点在尺度分量上的近似幂率的分布规律。在仅已知特征信息的初匹配过程中，通过尺度降采样，在特征点数量庞大的高清影像中，获取数量稀少、潜在相似点较少但代表图像整体结构特征的大尺度特征点，避免因特征点数量稀少、位置包含大量粗差等情况引起的匹配错误。在缩减计算规模的筛选点中，选择更小的ratio进行严格匹配，实现快速高精度初匹配。图 1试验结果采用ratio=0.6进行匹配，图中存在大量的错误匹配点对。而当ratio取0.2或更小数值时，部分正确匹配结果也因最优匹配距离无法达到此显著性指标而被删去。为在确保匹配正确率基础上保留更多匹配点对，全局匹配过程中ratio取值为0.4。

尺度参数越大，对应的降采样程度越高，相应特征点对图像整体结构的概括能力越强。通过筛选大尺度特征点，在缩减计算规模的同时，确保特征点在图像全境的散布，大量减少高频小尺度特征点中常见的相似特征干扰，实现无先验信息下的高精度快速匹配。通过筛选特征点集合尺度分量大于其中位数的点集进行二分筛选，本文将待匹配图像初匹配特征点规模控制在1000以下，基于NVIDIA GTX970M显卡的CUDA加速，单次特征匹配时长在1 s以内解算影像中可靠基础矩阵、估计图像重叠度并建立尺度比例约束的初匹配点集。相比图 1的直接匹配结果，基于本文快速匹配方法所得的匹配结果如图 6所示，采样后的点集消除了明显错误的交叉匹配线。此外，本文方法避免了对原有匹配点集合的检索与优化等二次计算过程，在保证摄影测量精度的前提下提升了计算效率。

图 6 基于尺度筛选的快速特征匹配结果Fig. 6 The results of rapid matched image feature points using scale component selection

图选项

1.4 基于特征索引与多约束条件下的密集特征点快速匹配技术

根据初步匹配点可计算基础矩阵F，并根据对极几何限制潜在匹配点的位置分布，但通过式(5)计算的大量特征点之间对极线距离d的计算量仍然庞大，其直接应用于匹配的耗时较长。式中fir表示基础矩阵F中的第i行。因此，本文通过尺度比例约束，缩小待匹配点集规模，使计算量可控

(5)

不同尺度影像的匹配关联关系，在视差变化不显著的航空印象中，其各自对应特征响应模板近似为缩放变换。结合归一化8点法，快速初匹配计算过程中，获取匹配关系正确、位置确定的点位作为建立后续对极约束、尺度比例约束的初匹配结果。通过ratio=0.2的严格筛选，得到各组影像对的特征匹配点，其尺度分量的比值如表 1所示。由此可知，其较小的标准差验证了本文的结论，体现出两视图中匹配的特征点在尺度分量上呈现出一个常数引子的稳定关联，可将其作为图像匹配的关键约束引入后续的匹配计算过程中。

表 1 多组影像数据尺度比统计Tab. 1 Multiple sets of image data scale ratio statistical tables

表选项

根据初匹配结果计算对极线距离与尺度比例的均值和标准差，在匹配加密过程中由式(6)确定99.74%符合尺度限值约束的潜在匹配点集，在此集合下计算对极线距离，筛选符合式(7)的匹配点，最后根据式(4)确定匹配点。计算过程中根据索引搜索对应数据，在各数据最多只计算一次的情况下遍历全部特征点集合，实现全局匹配。

(6)

(7)

尺度比例约束只需实现尺度分量中一维信息的双侧判断，其计算量相比对极线距离计算进一步缩小，进而实现潜在特征点的快速稳定筛选。基于大量特征提取，尺度降采样的快速初匹配，以及本节实现的多约束密集匹配流程如图 7所示。针对其中大量重复的图像分块、特征搜索等过程，采用并行加速提升计算速度。

图 7 基于综合约束的特征点匹配加密流程Fig. 7 The flowchart of feature point matching method based on synthetic constraints

图选项

为验证算法的可靠性，采用图 1中直接匹配出现大量错误的两幅高清航空影像进行试验，计算其特征分布、初匹配与密集匹配。

在建立尺度筛选的初匹配中，左右两视图特征数据量在134 407与101 713的情况下，根据尺度分割将样本容量降低到1000并建立280对稳定匹配点，用时12 ms；在增大样本容量到20 000后，基于对极约束与尺度比例约束在63 s内完成6709对点对的匹配。在采用GPU加速后，本文算法将以上计算时长缩短到亚秒级，为762 ms。

由于尺度筛选避免了搜索规模在待测点数量增长时的扩张，本文算法规避了特征匹配过程中的无效计算，其计算时长小于特征全局匹配与对极线搜索匹配，并根据计算结果自动修正了仅通过对极约束匹配时的错误情况，计算结果如图 8所示。试验表明，基于尺度分布特性的特征匹配方法在数据规模较大的高清影像中，提高了特征提取的数量与精度，并在数据规模大幅增加的情况下控制了匹配时长的增长。

图 8 基于对极约束与尺度比例约束的密集匹配结果Fig. 8 Intensive matching results based on constraints of polar and scales constraints

图选项

2 试验与分析

本文以Visual Studio 2017+CUDA9.1作为编程环境，采用intel i7-4720HQ与NVIDIA GTX970M进行计算，对图 8所示试验数据的总特征点数、初匹配点对数量、匹配时长等参数列表分析。试验数据为无姿态信息的手持相机拍摄近景影像与无人机航空拍摄影像。

为检验特征点提取算法的性能，本文针对以上不同分辨率影像数据进行特征提取，并与目前稳定的全局SURF特征检测进行试验对比，如表 2所示。其中，本文方法用到了大量多次的SIFT特征提取算法，在GPU并行计算下，其计算时间近似于Matlab实现的全局SURF方法。本文方法检测所得特征点数量在各分辨率下均为SURF方法的5~10倍，获取到更密集的匹配点。本文方法中单幅影像的特征提取在整个重建过程中仅计算一次，在单张影像多次计算匹配关系的三维重建计算过程中具有优势。通过在此基础上建立的高精度初匹配提供的2个额外约束，缩小了每个匹配点的待选匹配集合，所得匹配点将通过对极线距离、尺度与特征相似度的检核，进而去除仅通过特征向量距离匹配产生的误匹配情况。

表 2 本文方法与全局SURF方法在不同影像数据中的计算结果Tab. 2 The results of this method and the global SURF method in different image data

表选项

图 9 试验数据Fig. 9 Data in the experiments

图选项

在大量特征点基础上，使用本文方法与直接特征匹配结果进行对比分析，如表 3所示。在本次采用的影像数据中，存在大量的小尺度重复特征，造成图 1所示的错误匹配现象。此外，无约束的直接特征匹配与直接对极线约束匹配的计算时长均由于计算规模的扩大而增大到不可控。在未经优化的情况下，其单次计算的实际内存开销也远大于试验机的8 GB内存。本文方法通过控制特征尺度因子，逐步增大匹配范围的方式，在实现10⁵数量级特征点匹配过程中，实现计算时长与计算空间的有效控制。通过尺度分量控制匹配点容量，在速度与精度上产生不同的匹配效果，其中，容量越少、匹配时长越短，但其所得匹配点对在图像细部的分布越少。

表 3 本文方法与全局特征匹配方法在不同影像数据中的计算结果Tab. 3 The results of this method and the global feature matching method in different image data

表选项

3 结论和展望

本文通过分析尺度不变特征检测方法的计算过程本质，推导并验证了图像特征点的尺度分布规律，实现初匹配过程中搜索集的高精度收敛，保证匹配正确率的同时缩减图像匹配过程中的计算量。在后续匹配加密过程中，利用快速初匹配得到的尺度约束，缩小搜索范围，将高分辨率影像内大量特征点的总匹配时间缩减到秒级和亚秒级。针对高清无定姿影像的密集匹配问题，优化匹配算法，实现特征提取与匹配计算过程在精度与计算时间上的改进，并剔除大量特征点匹配过程中普遍发生的错误匹配。在计算过程中，对极约束与尺度约束来自于自适应优化的快速初匹配结果，解决了高清影像特征数据匹配的时空开销问题，并能基于过程中筛选的尺度阈值，优化同系列图像的同名特征点匹配效率，为后续三维建模过程提供分布稠密、位置可靠的匹配点基础数据。

尺度比例约束在视差变化不显著的航空影像与一般近景影像中可提供有效约束，提升匹配计算效率。根据本文推导结果，在视差变化巨大的情况下，两视图特征尺度不再满足简单的比例约束，但其变化趋势仍然可以预测：距离成像点更近实物对应的特征点，由于其降采样程度更高，使匹配尺度比例更大，反之亦然，可通过线性拟合等方式确定二者之间更精确的对应关系。此外，本文特征计算过程中仍然存在进一步提升速率的空间，如数据结构、分块方法、特征提取算法的改进等。

【引文格式】赵红蕊, 陆胜寒. 基于特征尺度分布与对极几何约束的高清影像快速密集匹配方法[J]. 测绘学报，2018，47(6)：790-798. DOI: 10.11947/j.AGCS.2018.20170630

精

彩

回

顾

院士论坛︱李德仁院士：展望大数据时代的地球空间信息学（论文版）

学术前沿| 龚健雅院士：摄影测量与深度学习

李德仁院士：老师教我做人做学问

院士论坛| 杨元喜：微PNT与综合PNT

院士论坛| 杨元喜：我国海洋大地测量基准与海洋导航技术研究进展与展望（英文版）

院士论坛| 龚健雅：高分辨率光学卫星遥感影像高精度无地面控制精确处理的理论与方法

院士论坛 | 龚健雅:中国高分辨率对地观测系统的成长与突破

书讯 | 杨元喜院士：自适应动态导航定位（第二版）

李德仁院士论夜光遥感数据挖掘

权威 | 专业 | 学术 | 前沿

微信公众号中搜索「测绘学报」，关注我们，长按上图二维码，关注学术前沿动态。

进群请备注：姓名+单位+稿件编号

閱讀更多 測繪學報 的文章

關鍵字: 地球空间 基金 杨元喜