一种基于加权投票的图像匹配改进方法

张丽丽，罗 斌，汤 进，孙登第

(1.计算智能与信号处理教育部重点实验室，合肥 230039；2.安徽大学计算机科学与技术学院安徽省工业图像处理与分析重点实验室，合肥 230039)

1 概述

图像匹配是图像处理中的关键技术之一，在遥感图像分析、医学图像分析、计算机视觉等方面有着重要的应用[1]。图像的特征点是图像中灰度信号二维变化较大的图像点，对图像形变、灰度变化以及遮挡等具有较好的适应能力，因此，基于特征点的图像匹配是一种重要的图像匹配方法。而建立图像特征点之间的正确匹配是计算机视觉和模式识别领域中的一个基本问题，也是图像匹配的研究热点。事实上求解特征点之间的正确匹配是一个典型的NP问题，学者们提出了很多近似方法。目前，基于特征点的图像匹配方法主要分为2类：(1)先通过特征点之间的相似性度量得到特征点之间的初始匹配，再使用排错算法得到满足某种特性的特征点匹配，而当特征点之间的相似性度量不明显时，该种算法往往得不到满意的结果[2-3]；(2)主要考虑特征点之间的几何关系，再结合特征点之间的相似性度量直接获得特征点匹配[4-5]。

在第(2)类方法中，文献[4]提出建立以特征点集之间的候选匹配为顶点的图，再通过对所有顶点之间的亲邻矩阵进行谱分解以得到特征点之间的最优匹配。采用谱方法求解特征点匹配问题往往具有较好的匹配效果[4,6-7]，得到广泛的应用，但是其中亲邻矩阵(特别是当特征点集的规模较大时)的谱分解需要耗费大量的时间[7]。文献[7]提出使用加权投票方法，将每个候选匹配同时作为投票者和接收投票者，最后通过简单的加法运算和排序操作确定出最优匹配。虽在运行时间上明显减少，但是特征点之间的匹配精度难以保持。

投票方法是一种有效的决策方法，在图像处理与模式识别中具有广泛的应用[8-9]。本文提出一种改进的基于加权投票的图像匹配方法，认为每个候选匹配作为投票者和接收投票者，以一定的权重进行投票，并给出一种估计每个候选匹配投票权重的方法。

2 亲邻矩阵及目标函数的建立

记矩阵A、B为待匹配的2幅图像，提取的特征点集分别为：

记指标向量为：

候选匹配之间的亲邻矩阵 W=(Wij)，i, j=1,2,…,K，其中，W 的对角元表示特征点的特征描述向量之间的亲邻程度，非对角元表示候选匹配之间的几何一致性亲邻程度，即：

基于特征点的图像匹配可归结为从候选匹配中寻找满足一定限制的匹配，使得所选的匹配之间的几何一致性最大，即：

文献[4]提出对亲邻矩阵W 进行谱分解，再结合贪心算法得到特征点之间的最优匹配。

3 图像匹配方法

3.1 基于加权投票的图像匹配方法

基于加权投票的图像匹配方法[7]将每个候选匹配作为投票者，每个投票者不仅给其他候选匹配投票，还接收其他候选匹配的投票，而投票值估计为两候选匹配之间的亲邻程度 W((i,i'),(j,j'))，并将每个候选匹配接收投票的累积和作为正确匹配的评价值，即：

3.2 基于加权投票的图像匹配改进方法

基于权重的加权投票是一种普遍的投票方式，每个参与者以一定权重对其他参与者进行投票。本文提出一种改进的基于加权投票的图像匹配方法，认为每个候选匹配不仅基于亲邻程度对其他候选匹配进行投票，而且以一定的权重进行投票，如图1所示，实线表示候选匹配(1,1')，虚线表示其他与候选匹配(1,1')不冲突的候选匹配。

图1 基于加权投票的图像匹配改进方法

本文给出一种估计候选匹配投票权重的方法：计算每个候选匹配(i,i′)的接收投票值累积和c'(i,i′)并归一化，即得其投票权重c(i,i′)。这样接收投票累积和越大，表明该候选匹配为正确匹配的可能性越大，那么对其他候选匹配投票的权重也越大。

各级安全参与人员可在线创建和启动检查计划，系统生成并推送对应的检查表至检查人的手持终端，检查人持手持终端按照标准检查表进行比对检查，并反馈问题。

按照此种方式得到的每个候选匹配的综合投票值构成其为正确匹配的评价值，即：

其中，c(j,j′)为候选匹配(j,j′)投票的权重。因此，特征点i的最优匹配为

综上所述，基于加权投票的图像匹配方法具体描述如下：

Step1 利用式(1)、式(2)计算亲邻矩阵W ，根据式(5)、式(6)计算所有候选匹配投票的权重c。

Step2 利用式(7)计算每个候选匹配的评价值，记作向量 x∗；初始化解向量x为K×1的零向量；初始化候选匹配矩阵L。

Step4 从矩阵L中删除所有与匹配a∗相冲突的匹配，即如果 a∗=(i,i′)，那么所有形如 (i,j′)与 (j,i′)的匹配都与a∗相冲突。

Step5 如果L已空，则返回解向量x；否则，返回至Step3。

4 实验结果与分析

为验证本文方法的有效性和稳定性，本文进行了模拟数据实验和真实图像实验。选择谱匹配方法(SM)[4]和基于加权投票的图像匹配方法(WVPC)[7]与本文改进的基于加权投票的图像匹配方法(IWVPC)进行对比，通过匹配精度和目标函数值来评估算法的性能，其中，匹配精度=实际正确的匹配数/总的匹配数；目标值根据式(3)计算而得。

4.1 模拟数据实验

模拟数据通过以下方式产生：由计算机随机产生np=25个服从均匀分布的模板集P，其中，均匀分布的区域大小为，保证每个大小为256×256的区域内有10个点。实验通过点的位置抖动和增加噪声点2种方式来验证该算法的抗噪性能和抗出格点性能。在点的位置随机扰动实验中，对模板集P在每个点位置上增加高斯噪声来得到目标集Q，即Q=P+ε( ε～N(0,σ2)，σ表示高斯噪声水平)。在增加噪声点实验中，对模板集P所在区域内随机增加出格点来构造目标集Q。本文对生成的模板集和目标集进行模拟仿真，每组实验均进行50次蒙特卡罗实验。实验中的参数设定如下：亲邻矩阵中的对角元为0，亲邻矩阵的非对角元中 σd=10。

图2、图3分别给出了模板集与目标集之间仅存在位置扰动，且位置扰动逐渐增大(噪声水平σ从 1变化到 10)和仅存在出格点，且出格点逐渐增加(出格点从 0增加到 30)时，3种算法得到的模板集与目标集之间的匹配精度和目标函数值；而图4表示出格点数固定为15，模板集与目标点集之间还存在位置扰动，且位置扰动逐渐增大(噪声水平σ从1变化到10)时，3种算法得到的模板集与目标集之间的匹配精度和目标函数值。

图2 点集之间仅存在位置扰动的匹配结果

图3 点集之间仅存在出格点的匹配结果

图4 点集之间存在位置扰动和出格点的匹配结果

从图2～图4中可以看出，SM算法对点集的位置扰动和出格点的存在具有良好的鲁棒性，IWVPC算法比WVPC算法在匹配精度和目标函数值上都具有较大的提高，与SM算法的匹配精度和目标函数值接近，验证了增加候选匹配投票的权重以得到的综合投票结果的有效性。因此，候选匹配权重的引入使 WVPC算法的匹配效果有了较大的提升。

4.2 真实图像实验

为了验证本文方法解决实际图像匹配问题的能力，从Caltech-101和 MSRC数据集中选取了 30组图像，用MSER[10]及 SIFT[2]描述子生成候选匹配，使用相互映射误差[11]来度量特征区域之间的相似性，令SIFT算法中确定候选匹配的阈值δ=0.6。该部分实验中的参数设定如下：亲邻矩阵中的对角元为0，亲邻矩阵的非对角元中 σd=5。

表1给出了30组图像之间的平均匹配精度和相对目标函数值，部分图像匹配结果如图 5所示。其中，图 5(b)的匹配精度为9/9，目标函数值为16.3972；图5(c)的匹配精度为7/9，目标函数值为13.7917；图5(d)的匹配精度为9/9，目标函数值为16.1435。从表1可以看出，本文的IWVPC算法在匹配精度和目标函数值上远高于WVPC算法，接近SM算法的结果。

表1 30组真实图像的匹配性能比较

图5 部分图像匹配结果

4.3 运行时间分析

与SM、WVPC方法相比，本文提出的IWVPC方法区别在于候选匹配为正确匹配评价值的计算上。为比较 3种方法的时间效率，本文在主频2 GHz、内存1 GB的PC机上比较 3种方法在亲邻矩阵的大小变化时的运行时间，比较结果如表2所示。

表2 3种方法的运行时间比较 s

在表2中，随着候选匹配之间的亲邻矩阵大小的增加，SM方法中对亲邻矩阵进行谱分解所需运行时间显著增加，而WVPC方法和IWVPC方法在计算候选匹配为正确匹配的评价值时仅需较少的运行时间。虽与WVPC方法相比，IWVPC方法的运行时间有微小的增加，但是根据前面的实验结果，IWVPC方法却具有接近SM方法的匹配效果。

5 结束语

本文给出一种改进的基于加权投票的图像匹配方法。首先建立特征点候选匹配之间的亲邻矩阵，然后对每个候选匹配投票的权重进行估计，再将其他候选匹配对其投票结果的积累和作为该候选匹配为正确匹配的评价值，最后通过简单的数学运算和排序操作来确定最优匹配。模拟和真实实验结果表明，本文方法具有较好的匹配效果和较少的运行时间。今后的工作将主要研究新的图像匹配方法，以进一步提高图像匹配的匹配精度和时间效率。

[1]Liu Zhaoxia,An Jubai.A Robust Point Matching Algorithm for Image Registration[C]//Proc.of the 3rd International Conference on Machine Vision.Hong Kong,China: [s.n.],2010.

[2]David G L.Distinctive Image Features from Scale-invariant Keypoints[J].International Journal of Computer Vision,2004,60(2): 91-110.

[3]郑雪梅,范 勇,石琦凯,等.一种基于点的快速图像配准算法[J].计算机工程,2012,38(1): 220-221.

[4]Marius L,Martial H.A Spectral Technique for Correspondence Problems Using Pairwise Constraints[C]//Proc.of the 10th IEEE International Conference on Computer Vision.Beijing,China: [s.n.],2005.

[5]张昌芳,杨宏文,胡卫东,等.一种用于点模式匹配的改进型谱方法[J].计算机工程,2009,35(2): 10-12.

[6]Tao Dacheng,Li Xuelong,Wu Xindong,et al.Geometric Mean for Subspace Selection[J].IEEE Transactions on Pattern Analysis Machine Intelligence,2009,31(2): 260-274.

[7]Yuan Yuan,Pang Yanwei,Wang Kongqiao,et al.Efficient Image Matching Using Weighted Voting[J].Pattern Recognition Letters,2012,33(4): 471-475.

[8]Yaron L,Thomas F.Möbius Voting for Surface Correspondence[J].ACM Transactions on Graphics,2009,28(3): 1-12.

[9]Oscar K A,Tai Chiew-Lan,Daniel C,et al.Electors Voting for fast Automatic Shape Correspondence[J].Computer Graphics Forum,2010,29(2): 645-654.

[10]Jiri M,Ondrej C,Martin U,et al.Robust Wide-baseline Stereo from Maximally Stable Extremal Regions[J].Image and Vision Computing,2004,22(10): 761-767.

[11]Minsu C,Lee Jungmin,Kyoung M L.Feature Correspondence and Deformable Object Matching via Agglomerative Correspondence Clustering[C]//Proc.of the 12th IEEE International Conference on Computer Vision.Kyoto,Japan:[s.n.],2009.