基于差分制约耦合三角网约束的图像匹配算法∗

黄源，张福泉

(1.重庆航天职业技术学院计算机系，重庆400021；2.北京理工大学软件学院，北京100081)

0 引言

数字图像作为信息的一种载体，已被应用于生活中多个领域[1]．随着计算机应用技术的不断发展，数字图像处理技术也成为了人们所研究的热点．图像匹配是通过一定的方法，将多幅图像中的感兴趣内容进行匹配的数字图像处理技术[2]．目前图像匹配技术已被人们广泛应用于模式识别、商标检索以及信息安全等多个技术领域．

近年来，国内外专家学者提出了多种图像匹配方法．例如Chen[3]等人通过对SIFT算法进行研究，提出了一种基于特征统计分布以及一致性约束的图像匹配算法，利用SIFT算法提取特征点，通过特征统计分布方法获取特征描述符，再利用一致性约束完成图像匹配．由于SIFT算法提取的特征点存在较多的伪特征点，导致算法的匹配正确率较为低下．Zhao[4]等人通过线分割方法，提出了一种基于多模态鲁棒线分割描述子的图像匹配方法，通过对图像中高等效角点以及分割线段进行提取，建立线分割描述子，接着通过多模态图像的线分割描述子进行相似度测量实现图像匹配，实验结果显示该方法能够实现图像的匹配，但是由于该方法过度依赖于图像中的线段关系，没有很好的考虑图像的灰度等特征，使得匹配结果中存在一定的错误匹配．Kahaki[5]等人通过从图像的空间特征出发，提出了一种基于空间特征相异性的图像匹配方法，通过像素点之间的不同路径，在遍历路径时跟随信号的变化，提取特征值，接着通过对特征内容的空间三元相似度进行判断，测试数据验证了其方案的合理性，然而，其对光照度变换的图像进行匹配时存在一定的错误匹配．吴鹏[6]等人通过对归一化互相关方法进行研究，提出了一种基于结合小波金字塔的快速NCC图像匹配算法，通过小波变换对图像进行分层后，采用Harris算子提取特征点，再通过快速NCC进行特征匹配完成图像匹配，实验结果表明，该方法具有一定的匹配效果，而且匹配效率较高，但是该方法没有对特征点进行描述，而且没有对匹配特征点进行错误剔除，导致匹配结果的正确度不高．

对此，本文提出了一种基于差分制约模型耦合三角网约束的图像匹配算法．利用差分高斯函数构造差分制约模型，以完成图像的特征点提取．通过计算圆形邻域内的Harr小波响应值以及梯度、灰度特征获取特征点的特征描述符，通过求取特征点之间的最近邻与次近邻比值实现特征点匹配．并通过匹配特征点在空间结构上构成的三角形关系，设计三角网约束规则，依据三角形边界线的拓扑关系，搜索误匹配点对，并将其过滤掉．

图1 本文图像匹配算法过程

1 本文图像匹配算法

所提的图像匹配算法过程见图1．由图可见，本文算法大致可划分为以下三个主要部分：

提取特征点．本文算法在差分高斯函数的基础上构造了差分制约模型，对相邻图像层次间灰度量级进行约束，将相邻图像层次间像素点引入特征点的提取过程中，从而提高了特征点提取的准确性以及算法的匹配正确度．

生成特征描述符．通过求取以特征点为中心构造的圆形邻域内的Harr小波响应值以求取特征点主方向，求取圆形邻域内的梯度特征以及灰度特征以求取特征向量，从而生成15维的特征描述符，以提高算法的匹配效率．

特征匹配．特征匹配包含特征点的匹配以及剔除错误匹配特征点两个部分．特征点的匹配是通过将特征点的最近欧氏距离与次近欧氏距离进行比较，通过比较结果获取匹配点对．通过获取匹配点对构成的空间结构，构建三角网约束规则提纯匹配结果．

1.1 提取特征点

基于高斯差分函数(DoG)的特征点提取方法为目前使用较为广泛的特征点提取方法之一．DoG通过将连续函数离散化，使得特征点提取过程的计算复杂度得以降低，提高了特征点提取的效率．

DoG函数提取特征点时首先需要构建图像的高斯尺度空间．图像的高斯尺度空间L(x,y,β)可通过将输入图像I(x,y)与变尺度高斯核函数G(x,y,β)进行卷积运算而得到[7,8]．

其中，变尺度高斯核函数G(x,y,β)的表述如下：

式中，β为空间尺度因子．

随后，根据Gauss金字塔中相邻图像的差值获取DoG函数．

其中，J为表示相邻高斯尺度空间倍数的一个常数．

最后，在DoG图像中将目标像素点与同一尺度空间的8个邻点以及上、下相邻尺度对应的18个像素点进行灰度值比较，若目标像素点的灰度值与这26个像素点的灰度值相比为极值，则目标像素点被视为候选特征点．获取候选特征点后，再采用三维二次拟合函数将低对比度等伪特征点进行剔除精确获取特征点，以提高算法的抗噪能力．

通过（3）式可见，空间尺度因子β决定了高斯核函数的窗口大小．当高斯核函数的窗口变动较大时，窗口内的像素点数量也会随之变动较大，可能引起相邻图像层次间的灰度量级不一致，使得相邻图像层次间的邻域像素点可比性较差，从而导致较多漏检特征点以及错检特征点的产生[9,10]．为了避免相邻图像层次间的灰度量级不一致而引起上述不足，构造了以下差分制约模型．

其中M、N分别为图像的行、列数．

通过差分制约模型式（4）可见，相邻图像层次间的灰度量级得以一致性制约在[0,1]范围内．利用式（4）替代式（3）从而避免了相邻图像层次间灰度量级不一致而引起的不足，保证了特征点的准确提取．

1.2 生成特征描述符

在此将通过求取以特征点为中心构造的圆形邻域内的Haar小波响应值以及圆形邻域内的梯度特征和灰度特征以生成特征描述符．

选取任一特征点作为中心，以6β作为半径，构建一个特征点的圆形邻域T．在该圆形邻域内用尺寸为4β的Haar小波，求取x和y方向上的Haar小波响应值．以被选取的特征点作为中心构建一个60˚的扇形区域，然后将该扇形区域在特征点的圆形邻域内进行旋转，接着求取扇形区域内Haar小波响应值的和，从而形成一系列的矢量，最后选取最长矢量对应的方向作为特征点的主方向[11,12]．

图2 求取特征向量示意图

获取到主方向后，将求取特征向量以生成特征点的描述符．将坐标轴旋转至主方向上，以主方向为起点，30˚为间隔，在圆形邻域T内建立12个方向的指针，如图2（a）所示．求取每个指针方向上的梯度累加值，形成一个12维的向量P．

为了适应光照不变性，将P进行归一化操作：

接着分别以半径2β、4β构建圆形邻域T的同心圆区域，以将圆形邻域T均分成三个圆形邻域，如图2（b）所示．求取每个邻域内的灰度值累加和ei(i=1,2,3)后，并将灰度值累加和进行归一化处理，形成一个3维的向量．

1.3 特征匹配

根据特征描述符，计算特征点之间欧氏距离的比值，对两幅图像完成配准，并构建三角网约束规则，实现配准结果的提纯．

令W与V分别为图像A与图像B中提取出来的两个特征点集合，B与Q分别为W与V中的一个特征点，B与Q的特征描述符分别为BS与QS，BSi与QSi分别为BS与QS中的第i个分量，则特征点B与Q的欧氏距离Dis(B,Q)为：

在特征点集V中搜索与特征点B最近欧氏距离Dismin与次近欧氏距离Discmin相对应的特征点Qmin、Qcmin，若则将特征点集V中的特征点Qmin，视为点B的候选匹配点．为了避免V中存在若干个点与特征点B进行匹配，接着通过同样的方法在特征点集W中搜索与特征点集V中特征点Qmin相对应的候选匹配特征点Bmin，若Bmin与B为同一个特征点，则判定Qmin与B为一对匹配特征点．µ为小于1的一个阈值，不失一般性，取µ=0.7[13,14]．

由于通过特征点之间欧氏距离比值的方法形成的匹配特征点对中，会存在少许错误匹配特征点对，在此将利用匹配特征点构成的空间结构，构建三角网约束规则将错误匹配特征点进行剔除．

首先，对异常拓扑结构进行判断．不管图像经过缩放还是仿射变换以及旋转，正确匹配特征点对构成的三角网上的边界线应该具有相似的拓扑结构，而错误匹配的特征点对将使得边界线出现异常的拓扑结构．当三角网上任意两个三角形的边界线有两条或者两条以上同时出现相交，则判定该边界线出现了异常拓扑结构[16,17]．边界线的拓扑结构示意图如图3所示，其中图3（a）与图3（b）为相似的正常拓扑结构，图3（c）中边界线为异常拓扑结构．

图3 边界线拓扑结构示意图

然后，对边界线进行二值化．将异常拓扑结构的边界线用0进行标示，正常拓扑结构的边界线用1进行标示．其表述如下：

最后，对错误匹配特征点进行剔除．令特征点vi构成的边界线数量为SL，其中异常拓扑结构的边界线数量为ASL，若下式成立，则判定vi与wi为一对错误匹配特征点，将其剔除．

其中λ∈(0,1)为预定阈值．

2 实验结果与分析

采用Intel i3处理器、4GB内存、操作系统为Windows7的PC机为硬件平台，MATLAB7.10为仿真环境进行仿真实验．实验中将文献[18]和文献[19]中的算法设立为对照组．其中，文献[18]通过利用图像区域的熵阈值来定义特征点筛选机制，对经典的SURF方法进行改进，准确提取图像的特征点，并引入改进的快速近邻搜索算法与RANSAC策略实现特征的匹配优化，SURF特征与SIFT特征类似，是当前图像匹配技术中最为常用的方法之一，而且该技术对SURF方法进行了改进，具有良好的代表性与新颖性．文献[19]主要是利用SIFT方法与仿射不变坐标系统来完成图像匹配，利用SIFT技术提取图像的特征点，再根据仿射不变坐标系统对特征点进行匹配，这种仿射不变坐标系统约束了特征点的坐标，对旋转与缩放具有较高的匹配精度，且SIFT技术是当前图像匹配中较为经典的方法，因此，该技术具有良好的代表性与新颖性．

2.1 选取最优阈值

牛津大学仿射协变标准图像集由包含了平移、尺度变化、旋转、模糊等变换在内的八个子集组成，每个子集中又由同一场景不同情况下的六张图像组成．现从该图像集中任意选取五组图像，在不同阈值λ下进行匹配，并将匹配图像的平均匹配正确率进行记录，用以确定阈值λ的最优值．

图4为不同λ值下匹配图像的平均匹配正确率测试结果．从图4中可见，当λ为0.4时匹配图像的平均匹配正确率最高，为0.82．因此确定最优阈值λ=0.4．

图4 不同λ值下匹配图像的平均匹配正确率测试结果

2.2 图像匹配算法性能分析

图5∼图7分别是本文算法与对照组技术对噪声、旋转、缩放+噪声攻击图像的配准情况．根据测试效果可知，三种技术的匹配特征点数都很多，仔细将本文算法的匹配情况（见图5(e)）与文献[18]、文献[19]技术（分别如图5(c)、5(d)所示）进行对比可以发现，本文算法的匹配效果图中匹配的特征点数最多，而且错误匹配特征点数量最少．图6中各算法都具有一定的匹配效果．通过将对比图6(c)∼6(e)可知，文献[18]算法以及文献[19]算法的匹配结果中比本文算法的匹配结果存在更多的漏匹配以及错误匹配点．将图7中不同算法的匹配效果图进行对比可见，本文算法的匹配精度要高于文献[18]、文献[19]，如图7(c)∼7(e)所示．

图5 不同算法对噪声图像的匹配结果

图6 不同算法对旋转变换图像的匹配结果

为了更直观的体现出不同算法的匹配结果，将不同算法在图5、图6和图7中的正确匹配特征点总数、错误匹配特征点总数以及耗时进行了统计，结果分别如表1、表2、表3所示．从表1中可见，对于噪声干扰，所提算法具有更强的鲁棒性，其正确匹配点数为372个，其错误匹配与漏匹配数量最少，同时本文算法的匹配耗时为3.52s，较文献[18]与文献[19]中算法的耗时为最少．从表2中可见，对于旋转变换，由于文献[19]采用了仿射变换系统，使其对旋转干扰具有更高的鲁棒性，其正确匹配特征点数量为283，错误匹配数量仅为9个，但是时间较长，达到了4.17s；但是，所提技术的正确匹配点数为274个，比文献[19]稍低一些，但其配准速度最快，所耗时间为2.31s．从表3可见，对于缩放干扰，本文算法的匹配精度最高，其正确数量为339，错误匹配点数仅为6个，较对照组算法为最少，且其匹配耗时为3.19s．这些测试数据均显示了所提方法具有较高的匹配精度与鲁棒性．由于本文算法通过差分高斯函数构造了差分制约模型，将相邻图像层次间像素点引入特征点的提取过程中，提高了特征点提取的准确性．同时本文还通过求取Haar小波响应值以及梯度特征和灰度特征以生成较低维度的特征描述符，以及通过匹配特征点构成的空间结构，构建三角网约束规则滤除了误匹配点，降低了算法的匹配耗时．文献[18]算法利用改进的SURF方法来获取图像的特征点，根据快速近邻搜索算法完特征点粗匹配，基于RANSAC策略实现匹配优化，但是，SURF机制只利用了特征点周围3/8的信息量(即特征点周围8个邻居中的3个：右方、下方和右下方子块)，使其对图像特征的描述能力不强，且在求取其主方向阶段太过于依赖局部区域像素的梯度方向，在遇到旋等几何变换时，易导致主方向不准确，使其匹配精度不理想，另外，SURF生成一个64维的特征向量，维度较大，增加了匹配时耗．文献[19]算法中通过SIFT方法获取特征点以及特征描述符，再通过仿射不变坐标系方法来实现图像匹配，由于SIFT方法提取的特征点中存在较多的伪特征点以及冗余特征点，而且SIFT方法生成的特征描述符的维度很大，是一个128维的特征向量，从而影响了其配准精度与效率．

图7 不同算法对缩放+噪声图像的匹配结果

表1 不同算法在图5中匹配结果的统计

表2 不同算法在图6中匹配结果的统计

表3 不同算法在图7中匹配结果的统计表

3 结论

本文设计了一种采用差分制约模型和三角网约束的图像匹配方案．在提取图像特征点时，通过差分高斯函数构造差分制约模型，提高相邻图像层次间像素点的可比性，使得所检测特征点的正确度得以提高．计算Haar小波响应值、梯度和灰度特征，形成特征描述符．通过求取欧氏距离比值完成特征点匹配后，再利用三角网约束规则对错误匹配特征点进行剔除．实验结果表明，本文算法具有较高的匹配正确度以及匹配效率，对噪声、旋转以及缩放具有更好的鲁棒性．