结合Delaunay三角网的自适应多尺度图像重叠域配准方法

陈永胜 许建龙 汪亚明

摘 要：為改进随机采样一致性算法模型参数估计可能不是最优导致图像特征点配准率不高的问题，缩短特征点提取时间，提出一种结合Delaunay三角网格约束的自适应多尺度图像重叠域配准方法。采用自适应通用加速分割检测算法，快速检测出均匀稳定的特征点，并且用二进制特征描述子解决尺度不变性和旋转不变性问题。因传统随机采样一致性算法阈值选取和迭代次数的局限性，会掺杂部分难筛的误配点，在此前提下借助Delaunay算法剖分粗匹配点集，遍历计算网格间对应三角形相似度并储存在相似性度量矩阵中。依据Delaunay三角网特性，剔除相似度差异大的三角形，重构网格保存余下的匹配点集。实验结果表明，该方法特征点提取速率比FAST快15%～20%，特征点正确配准率比随机采样一致性算法提高约4.9%，不仅可自适应多尺度快速提取特征点，而且在保证特征点正确配准率基础上尽量多地保留有效特征点数量。

关键词：重叠域;自适应;图像配准;Delaunay 三角网;相似性度量;计算机视觉

DOI：10. 11907/rjdk. 201398                                                                  开放科学（资源服务）标识码（OSID）：

中图分类号：TP317.4   文献标识码：A                文章编号：1672-7800（2020）011-0206-06

Adaptive Multi-scale Image Overlap Region Registration Method Combining with Delaunay Triangulation

CHEN Yong-sheng， XU Jian-long， WANG Ya-ming

（School of Information， Zhejiang Sci-Tech University， Hangzhou 310018， China）

Abstract： The estimation of model parameters of random sampling consistency algorithm may not be optimal， which leads to the low rate of correct registration of image feature points. In order to solve this problem， an adaptive multi-scale image overlap registration method combined with Delaunay triangular mesh constraint is proposed. The adaptive universal accelerated segmentation detection algorithm is used to quickly detect the uniformity. Moreover， the binary feature descriptor is used to solve the scale invariance and rotation invariance. Due to the limitation of threshold selection and iteration times of traditional random sampling consistency algorithm， some mismatching points which are difficult to screen will be mixed. On this premise， Delaunay algorithm is used to divide the coarse matching point set， traverse and calculate the similarity of corresponding triangles between grids， and store them in the similarity measurement matrix. According to the characteristics of Delaunay triangulation， triangles with large similarity difference are eliminated， and the mesh protection is reconstructed to save the remaining set of matching points. The experimental results show that the extraction rate of feature points is 15% - 20% faster， and the correct registration rate of feature points is about 4.9% higher than that of random sampling consistency algorithm. The proposed method can not only adaptively extract feature points from multi-scale images， but also keep the number of effective feature points as much as possible while ensuring the correct registration rate of feature points.

Key Words： overlap region; adaptive; image registration; Delaunay triangulation; similarity measurement; computer vision

0 引言

图像配准是图像处理领域不可或缺的一环，是图像处理应用研究的基础，在目标识别、图像拼接[1]、可视化三维重建[2]和基于内容的图像检索[3]领域有着广泛应用。图像配准方法总体上归纳为基于灰度的图像配准[4-5]和基于图像特征的配准两类方法[6-8] 。前一类基于像素的算法，顾名思义是利用图像的灰度信息完成图像内容的匹配运算。正是得益于此类算法无需考虑图像内容的结构特征而极其依赖点像素信息特性，可最大程度降低预处理图像造成的精度损失，但对于图像中出现的旋转、视差、灰度和尺寸变化鲁棒性较差，且此类方法运算繁复，很大程度上限制了适用性。而后一类基于特征的算法依赖特征检测算子优化，如经典的SIFT、SURF 和 FAST 算子等，虽然算子对特征点提取有不同程度改进，但后续匹配点对进一步筛选搭配的几乎都是传统的随机采样一致性（Random Sample Consensus，RANSAC）算法[9]。关键点对筛选依赖阈值选取，对于低纹理特征少的图像可能导致保留的有效特征点数量较少，反而大幅降低特征点的正确配准率。

图像配准主旨是将在有一定时段间隔、硬件设备差异或参数变化时完成空间上的内容匹配操作，研讨在不同场景或不同视角下的图像内容存在深度变化情况下提高正确匹配率。当前配准算法研究思路向特征提取算子结合约束条件控制匹配并行的方向突破，文献[10]提出一种结合海森仿射区域检测器、局部 Delaunay 三角剖分和仿射不变几何约束的健壮性图像匹配方法，得到一定优化。但提取的是SIFT特征点，导致算法整体耗时过长且计算繁复;文献[11]提出一种基于三维Delaunay 三角剖分的立体视觉跟踪算法，充分利用空间几何约束特征点建立目标跟踪判别模型。本文以高速率、广覆盖提取多尺度特征点为前提，以追求更高配准率为目标，提出结合Delaunay剖分的图像重叠域配准方法，提高在重叠域过渡部分特征点匹配的正确率。

1 相关工作

关于尺度变化图像的配准，Xu[12]提出基于Harris角点检测结合鲁棒性较强的SIFT算法，可以提取具有尺度、光照和旋转不变性的特征点，但存在算法耗时长、实时性差和有效特征点少等问题;文献[13]提出融合特征的SURF算法，相比之前被認为效果最好的SIFT 算法，运算速度得到大幅度提高，但该算法在匹配时没有利用特征点云包含的任何有关结构特征信息，在处理差异较大的对象时误配情况尤为突出;Zhao等[14]提出一种新的双图匹配法，对基于尺度不变特征变换的匹配进行改进，使梯度方向标准化，使所有对应点的相似度比例最大化，生成Delaunay图去除离群点，特别适用于区域低重叠、内容转变大的多光谱、多时相图像。基于SIFT的改进对特征点分布考虑不够合理，有效特征点较为集中，影响最终配准效果。

随着基于特征的匹配算法向着添加约束控制条件的方向改进，Yan等[15]引入Delaunay剖分图像提取SURF特征点集，通过票决算法解决未运用结构特征信息及搜索效率较低的问题，但是SURF处理图像内容变化大的弊端依然存在。因此，在具有尺度变化和深度变化的重叠域图像对中快速提取分布均匀、定位准确的有效特征点，同时保证较高的特征点配准率是本文内容研究的主要。在特征提取速度方面，Biadgie 等[16]使用自适应加速分割检测法，虽然大幅加快了特征检测的计算速度，但FAST只单纯考虑特征点检测，未涉及有关点的特征描述;Kybic等[17]描述一种计算超像素特征向量快速配准方法，用空间正则化构造三角划分找到全局最优转换。在特征点的最终匹配阶段，传统的RANSAC阈值选取缺陷是在过滤误匹配的同时可能会剔除正确匹配点，这在有效特征点本就不多的图像中效果表现差强人意。

综上所述，各种方法的配准效果参差不齐，主要原因在两个方面：①在特征点检测环节选用的提取算法相对老旧，导致提取的特征点数量和质量不理想;②在特征匹配环节搭配使用的都是RANSAC算法滤除错误匹配点，但RANSAC弊端没有去除，导致最终正确配准率不高。本文选用改进的自适应通用加速分割检测（Adaptive and Generic Accelerated Segment Test，AGAST）特征提取算法，可以更快、更多、更好地提取特征点。在特征点匹配环节沿用传统RANSAC算法基础上，灵活运用Delaunay三角剖分控制特征匹配，弥补RABSAC算法不足。将计算机视觉与图形学结合是本文创新之处。

2 本文方法模型

2.1 AGAST特征检测与生成描述子

AGAST算法[18]改进了加速分割检测算法（Accelerated Segment Test，AST）的决策树，通过构造高效的二叉决策树替代原贪心算法（Iterative Dichotomiser3，ID3）构造的三叉树[19]，因为比较而言二叉树可以更高效地应用于二元目标。通过寻找特定决策树完成最佳搭配组合，即针对选定区域分配最适应的决策树，在不同尺寸掩膜下获得自适应，同时还能根据处理图像特征的情况动态且高效率地求解当前方案的通用解，进一步加快特征点检测速度。该方法不仅弥补了FAST角点在训练集检测步骤中可能消失的缺陷，而且具备FAST算法的可重复性。不同尺寸的AST如图1所示（彩图扫描OSID码可见），红色为8像素，绿色为16像素，蓝色的正方形和菱形为12像素，中间的黑色方块为掩膜中心像素点。

（1）构建更为精细的尺度空间金字塔，由n个octave层ci和n个中间层di组成（i=0，1，？，n-1）。ci是对基准图像c0的一次半采样得到，中间层d0是对c0的1.5倍采样得到，其余内层依次对d0半采样得到，如图2所示。

（2）在尺度空间金字塔的每一层和内插层分别使用阈值大小为εd的FAST-9-16（opencv库默认值）算子检测关键点，在固定半径的圆周上选取16个像素点标记为xi，i=1，2，？，16，如图3所示。分别与圆中心像素点p的像素值Ip做差，统计比点p亮或暗的圆周上点的个数，记为N，公式如下：

N=countIxi-Ip>εd （1）

若N≥9（图3中为FAST-12，则N≥12），则此关键点可作为一个焦点候选，这样把一个圆形区域划分成比中心像素亮、比中心像素暗以及与中心像素值近似的3类像素点，称为分割测试法。然后构建二叉树寻找最优决策树组合，确定候选角点，最后用非极大值抑制排除不稳定角点。由于非极大值抑制不能直接影响提取的特征点，考虑上述分割测试法特性及对计算速度要求，定义一个角点响应函数Λ：

Λ=maxA，BA=∑（Ixi-Ip），Ixi>Ip+εdB=∑（Ip-Ixi），Ixi

即定义角点强度值为圆周上像素点与中心像素点像素差值的累加和。先检测可能存在的感兴趣域，然后用非极大值抑制剔除尺度空间内不稳定的特征点，保留强度值最大的角点，抑制其余点。AGAST算法对尺度空间内检测出的所有极大值均进行连续尺度优化和亚像素校正[20]，以此尽可能精确定位特征点。

通过上述步骤记录特征点定位和尺度。AGAST虽然比FAST速度快，但同样缺乏特征点的其它描述信息，尚不具备旋转不变性，因此需要根据提取的角点位置计算特征向量矩阵，赋予特征点描述符。本文选择二进制健壮的尺度不变关键点（Binary Robust Invariant Scalable Keypoints，BRISK）作为特征描述算子。BRISK是一种特征提取算法，还是一种二进制的特征描述算子，具有较好的旋转不变性和尺度不变性，鲁棒性较强[21]。

2.2 Delaunay控制约束细匹配

在生成具有尺度不变性的特征点描述符之后，通过估量二进制特征描述符的相似性实现初步匹配，然后采用 RANSAC 法滤除大量不正确匹配点。传统的 RANSAC 虽然在多数情况下能够通过迭代估计出一个最优模型滤除大量错误匹配点，但如果迭代次数受限或阈值选取不当则会影响匹配点质量。如果阈值选取偏小，会导致好的匹配点被滤除;反之，则导致错误匹配点被保留，以上情况都是不能忽视的匹配效果干扰因素。针对此情况，本文借助Delaunay三角剖分控制网格变形策略，进一步提高特征点匹配正确率。提取细匹配点关键步骤如下：

（1）Delaunay 三角剖分。创建两个迭代器分别存储两幅待匹配图像，采用 RANSAC 筛选出的粗匹配关键点集，用点插法构建两幅待匹配图像的 Delaunay 三角网格。

（2） 计算 Delaunay 三角网格相似度。由于图像的特征点集被剖分成单个三角形构成的网格，遍历计算每个三角形对的相似度，筛选出匹配度更高的特征点。首先，设遍历的第一个三角形对记为ΔABC和ΔA'B'C'，其顶点A（x1，y1）、B（x2，y2）、C（x3，y3）和A'（x1'，y1'）、B'（x2'，y2'）、C'（x3'，y3'）对应的顶角度数分别记为θa和θa'？，以此类推，由两点距离公式计算三角形边长：

l1=x1-x22+y1-y22 （3）

依次计算出其余边的长度l2、l3和l1'、l2'、l3'，则有

cos（θa）=l21+l22+l232l1l2 （4）

则

θa=arccos（cos（θa）） （5）

同理求出所有三角形内角度数。第一对三角形之间的相似度记为U1，三角形对应内角的相似度记为Ua、Ub和Uc，则角的相似度公式为

Ua=cos3（π2（1-ed（θa'））） （6）

d（θa'）=-12q2（θa'-θa）           （7）

同理，计算出Ub和Uc，则两个三角形之间的相似度取3对内角相似度的平均值

U1=（Ua+Ub+Uc）3 （8）

即所求三角形之间的相似度U1不小于一个先验值，则判定其为相似三角形，反之则不是。

（3）确定精确匹配点对。遍历 Delaunay 三角剖分网格中的所有三角形，依次求出对应的相似值U1并构造一个相似矩阵，用来存储所有相似三角形的索引。该索引指向的三角形对是相互匹配的三角形，每个索引都具有唯一性，保证不会有重疊状况发生，进而确定精确点。

本文方法步骤如下：①读入一组图像，利用式（1）检测所有候选角点G;②对候选角点G利用式（2）角点响应函数，保留强度值最大的角点K;③完成特征点初步匹配，采用RANSAC估计模型挑选得到粗匹配点集 Q;④以读取图像的左上角为坐标原点、图像长度为横轴、高度为纵轴建立坐标系，逐点插入剖分点集 Q构建 Delaunay 三角网格;⑤利用式（3）-式 （8）遍历计算网格中对应三角形的相似度，判定为相似的储存到相似性度量矩阵S中;⑥重复步骤④重构Delaunay 网格，剩余顶点即为精细匹配点集。

3 实验结果与分析

依据上述算法步骤设计实验进行图像精细匹配实验结果对比。

3.1 实验数据与实验环境

图像配准是研究图像拼接的重要环节，改进图像配准算法可间接优化图像拼接算法。实验数据取自Chang等[22]提出的保持半投影变形方法实验，如图4所示。取包含远深背景和近景平面图像，图像重叠区域具有一定视差变化，即场景过渡具有视角转移的情形（拍摄镜头角度旋转导致），图像重叠域不在相同的二维平面，如图5所示。从这个角度切入，考虑提高图像重叠区域的配准率，则图像拼接效果必能得到改善。

本文实验基于Windows 10操作系统，联合虚拟机VMware 搭载Ubuntu 16.04LTS系统跨平台运行完成，计算机配置为Intel（R） Core（TM） i7-6700HQ 2.60 GHzCPU，内存16GB，使用Microsoft VS2017实现编程运行。

3.2 实验结果与对比

3.2.1 特征点提取速率对比

本文对两组图像进行基准图像及待匹配图像特征点提取，如图6所示。由图中可以看出，同一幅图像中，与经典的SIFT、SURF 和快速的 FAST 算法相比，改进的 AGAST算法提取的有效特征点个数最多，而且提取特征点用时最短。

3.2.2 特征点匹配方法改进

本文采用构建 Delaunay三角网方法，利用三角形相似性度量法与传统的RANSAC算法对两组图像实验效果进行对比。图7为采用传统的RANSAC 算法对基准图像和待匹配图像筛选出的匹配点集，图8（彩图扫描OSID码可见）为匹配连线图， 图中绿框圈出的是明显错误的匹配点，图9为采用RANSAC筛选的匹配点集对基准图像和待匹配图像进行Delaunay剖分构建的三角网格图像，图10是对上一步构建的Delaunay三角剖分网格采用三角形相似性度量法进行校正后的三角网格图像，剔除了差异明显的三角形，图11是经过三角形相似性度量后保留的精确匹配点集。

图7-图11详细展示了两组图像特征匹配点的精细筛选过程。可以看到在传统的RANSAC算法初步滤除误配点后，还有少数明显错误的匹配点被保留，RANSAC可以滤除模型外的点，但不能滤除模型内的坏点。本文结合 Delaunay 三角剖分法从图形学角度剔除不合理特征点，最终得到精确匹配点集，精确剔除了更多的错误匹配点，特征点正确匹配率高于RANSAC算法，具体数据如表1所示。

从表1可看出，本文借助Delaunay三角剖分约束特征点匹配后，在不减少RANSAC初步滤除后保留的正确匹配点个数情况下，减少了参与匹配的错误匹配点对数，提高了特征点对的正确匹配率。

4 结语

针对具有一定视差的重叠域且内容具有深度变化的图像配准，采用一般基于特征的配准算法特征提取速率较低、正确配准率不高问题，本文提出一种结合Delaunay三角剖分的自适应多尺度快速图像配准方法，分特征提取、粗匹配和精细匹配3个阶段完成。首先运用比FAST更快的自适应寻找最优决策树的AGAST算法，降低特征点提取方法的时间成本，然后在 RANSAC 控制的特征点粗匹配后引入Delaunay三角剖分法，在筛选图像重叠区域粗匹配点集基础上构建Delaunay三角网格，利用三角形相似性度量进一步筛选匹配点对，保留精细匹配特征点。

多组实验数据表明，在特征提取阶段，该方法提升了有效特征点提取数量，明显减少了特征点提取时间。在特征匹配阶段，在保证正确匹配点个数不减的同时减少了错误匹配点数量，提高了特征点对正确匹配率。本文方法主要针对有视差、内容有深度变化的图像，在图像拼接领域运用效果较好，但对于处理遥感拍摄等内容特征变化不明显的图像，算法配准效果还有待进一步提升。

参考文献：

[1] 许天成，李兆飞. 智能手机全景图像拼接算法研究[J]. 软件导刊，2016，15（2）：55-57.

[2] 钟军，巫海峰，李建宏，等. 新生雄性小鼠泌尿生殖系统的显微组织三维重建研究[J].  华小儿外科杂志，2018，39（11）：857-861.

[3] 何佳蓉，苏赋. 基于内容的图像检索发展方向的探索[J]. 信息通信，2015，14（1）：85-86.

[4] APTE A，WANG Y，DEASY J. SU-E-I-66：radiomics and image registration updates for the computational environment for radiotherapy research （CERR）[J]. Medical Physics，2014，41（6Part5）：145-151.

[5] ZHOU Z，YAN M，CHEN S，et al. Image registration and stitching algorithm of rice low-altitude remote sensing based on Harris corner self-adaptive detection[J].  Nongye Gongcheng Xuebao/Transactions of the Chinese Society of Agricultural Engineering，2015，31（14）：186-193.

[6] PATEL M I，THAKAR V K，SHAH S K. Image registration of satellite images with varying illumination level using HOG descriptor based SURF[J].  Procedia Computer Science，2016，93（5）：382-388.

[7] 鄒北骥，戴玉兰，朱承璋，等. 具有仿射不变性的视网膜图像配准方法[J]. 计算机辅助设计与图形学学报，2019，31（6）：943-950.

[8] MA J，JIANG J J，ZHOU H B，et al. Guided locality preserving feature matching for remote sensing image registration[J]. IEEE Transactions on Geoscience & Remote Sensing，2018，45（99）：1-13.

[9] WANG Y，ZHENG J，XU Q Z，et al. An improved RANSAC based on the scale variation homogeneity [J].  Allis Well WP，2016，40（PB）：751-764.

[10] DOU J F，LI J X. Image matching based local delaunay triangulation and affine invariant geometric constraint[J].  Optik  International Journal for Light and Electron Optics，2014，125（1）：526-531.

[11] LIUG D，LIU S，LI J X. A stereo vision tracking algorithm based on 3-dimensional delaunay triangulation[C].  Proceedings of Control & Decision Conference，2016：3779-3784.

[12] XU J J. Fast image registration method based on harris and sift algorithm[J].  Chinese Optics，2015，8（4）：574-581.

[13] 罗天健，刘秉瀚. 融合特征的快速SURF配准算法[J]. 中国图像图形学报，2019，20（1）：95-103.

[14] ZHAO M，AN B，WU Y，et al. A robust delaunay triangulation matching for multispectral/multidate remote sensing image registration[J].  IEEE Geoscience and Remote Sensing Letters，2015，12（4）：711-715.

[15] YAN Z G，JIANG J G，GUO D. Image matching based on surf feature and delaunay triangular meshes[J].  Acta Automatica Sinica，2014，40（6）：1216-1222.

[16] BIADGIE Y，SOHN K A. Speed-up feature detector using adaptive accelerated segment test[J].  IETE Technical Review，2016，33（5）：492-504.

[17] KYBIC J，JI？íB. Automatic simultaneous segmentation and fast registration of histological images[C].  Proceedings of International Symposium on Biomedical Imaging，2014：974-977.

[18] ELMAR M， GREGORY D H， DARIUS B， et al. Adaptive and generic corner detection based on the accelerated segment test[C].   Proceedings of ECCV，2010：183-196.

[19] BALDWINJ F，LAWRY J，MARTIN T P. A mass assignment based id3 algorithm for decision tree induction[J].  International Journal of Intelligent Systems，2015，12（7）：523-552.

[20] WANG H，LI L，YANG J. A modified self-correction subpixel registration algorithm for passive millimeter wave images[C]. Proceedings of International Conference on Computational Problem-solving （ICCP），IEEE，2013：151-154.

[21] MANEL L，GAO Q，TAREK B. Making bayesian tracking and matching by the brisk interest points detector/descriptor cooperate for robust object tracking[C]. Proceedings of International Conference on Signal and Image Processing，2016：731-735.

[22] CHANG C H，SATO Y，CHUANG Y Y. Shape-preserving half-projective warps for image stitching[C].  Proceedings of Conference on Computer Vision and Pattern Recognition，2014：3254-3261.

（責任编辑：杜能钢）