一种利用邻近特征点夹角一致性约束的匹配提纯方法

罗 媺,孙 涵,刘宁钟

(南京航空航天大学 计算机科学与技术学院,南京 211106)

1 引 言

特征匹配[1]是检验图像相似性的一个重要方法,广泛应用在目标识别、跟踪等领域.特征匹配的精度和速度一直是研究关注的重点.到目前为止,多数特征匹配的方法在利用局部特征点匹配时,未考虑到全局信息,很容易出现误匹配,因此如何筛选出正确的匹配点对是提高匹配正确率的关键问题.

1987年,Fischler[2]等人提出了随机抽样一致性(RANSAC)方法,该方法通过迭代抽取观测数据子集,用其来拟合模型参数,直到模型能满足足够多的样本点,则认为该子集是正确的.该方法是目前主流的匹配点提纯方法.2008年,龚声蓉[3]等提出了基于视差梯度约束的匹配点提纯算法,该方法在RANSAC的基础上,在计算变换模型之前,加入基于视差梯度约束的预检验过程,先检验随机选取的点是否存在误匹配,若存在,则重新选取.2015年,谢亮[4]等人提出了一种利用Hough变换的匹配点对提纯算法.先观察两幅图像的对应关系,选择一个合适的数学模型,利用Hough变换确定模型方程参数的解.然后检验最开始的匹配点对,剔除不符合模型方程的匹配点对.

车型分类[5]作为智能交通的一个研究分支,是近年来研究的热点问题.2003年,刘怡光[6]等人利用多层前向神经网络进行目标识别,介绍了网络拓扑结构并应用在车型分类上,该方法结合模式识别和模糊逻辑,进行了监督学习,通过大量实验表明对车型的轮廓分类有较高的准确率,并且对像素的干扰有一定抵抗能力.2004年,陈爱斌[7]提出了一种利用K-L变换提取车辆特征,得到降维特征子空间,再用BP神经网络进行车型分类的方法.2010年,黄灿[8]提出一种基于局部特征的车辆识别方法,利用SIFT特征将车型精确分类至48种.

利用神经网络解决车型分类问题虽然有很强的拟合能力,但不能直观地观察到推理过程,信息丢失也较为严重.利用特征匹配解决车型分类问题时,先用传统方法提取特征,再计算两幅图像特征描述子欧氏距离,误匹配较多.针对车辆这类特定目标的对称性强、局部区域相似较多的特性,本文提出了一种基于邻近特征点夹角一致性约束的匹配提纯方法,并应用于车型分类上.该方法充分考虑了特定目标几何结构上重复性较多的特点,通过邻近点夹角约束和空间区块约束,不仅能剔除一些明显错误的匹配点,还能将局部相似但空间位置不同的误匹配点剔除.

2 特征点的匹配和提纯

2.1 特征点匹配方法

提取出特征点后,需要根据一定的规则判定两幅图像中哪些特征点为匹配点对.常用的方法是先利用KD-Tree查询,找到最近距离和次近距离的点,若最近距离与次近距离之比大于某个比率,则判定这两个特征点为匹配点对.计算KD-Tree时,最简单的是每一个特征点与另一幅图中所有特征点逐一比较,计算出所有的距离,即穷举法,这种方法虽然省去了数据预处理时间,但因为检测出的特征点往往数目很多,穷举法效率很低,如何利用一种数据结构,提升检索效率是需要解决的问题.

KD-Tree是目前在特征匹配上应用最广泛的一种数据结构,它通过将空间划分为互不重叠的子空间,提高了检索效率.对所有特征点,给定一个数据点时,为了在这组数据中快速找到其近邻,KD-Tree采用分治思想,将空间划分为两部分.在子空间中,又将其划分为两部分,如此直到所有数据点都归类.

2.2 匹配提纯方法

在匹配点提纯上,随机抽样一致性RANSAC(Random Sample Consensus)是目前公认的准确率比较高的模型估计算法.它通过采样和验证两个步骤,求解使大部分特征点都能满足的数学模型参数.然而,RANSAC算法的缺点是效率不高,至少需要4个匹配点对来估计模型参数;而且它计算参数的迭代次数没有上限,如果设置迭代次数的上限,可能得不到最优的结果,甚至会偏差很大.

2013年,王亚伟[12]等人提出了一种改进的匹配点提纯算法mRANSAC.它针对数字图像离散采样导致匹配点不能对应,一个变换矩阵往往不能模拟出所有正确匹配点的缺点,利用多个变换矩阵增加匹配点数,并根据具体应用环境,设计了并集法、减集法、自适应内点数阈值法三种策略,使匹配提纯结果比RANSAC高出60%到300%.但是对于形变较大的图像,由于无法自适应设置距离误差,可能会出现正确率不高或较多错误匹配点对没有剔除的情况.

2014年,赵洋洋[13]等人提出了一种基于偏移空间局部一致性的匹配点对提纯算法,也是一种RANSAC的改进算法.在计算模型参数之前,首先计算将初始匹配点映射到偏移空间,保持偏移空间局部一致性的点会落入集中的几个Bin内,只保留落入这些Bin内的点.然后再利用RANSAC算法对这些点进行提纯.该算法能剔除一些噪音,但当形变大,落入Bin内的点集中度不高时,可能会剔除很多正确的匹配点对.

本文采用主流的RANSAC算法进行对比实验,RANSAC在SIFT特征筛选中的流程是:

第1步.从样本集中随机选取一个包含4个匹配点对的RANSAC样本集.

第2步.根据这4个匹配点对计算模型M.

第3步.根据样本集、模型M和误差度量函数计算满足当前模型的一致集,并记录一致集中元素个数.

第4步.根据当前一致集中元素个数判断是否最优一致集,即包含最多元素个数的集,若是则更新当前最优一致集.

第5步.更新当前错误概率p,如果p小于允许最小错误概率则停止,否则继续步骤1到步骤4.

2.3 常见误匹配情况分析

在有光照、颜色变化的车辆图片上,初步利用SIFT特征点建立KD-Tree结构,寻找到最近和次近邻,使用距离比值法初步筛选出匹配点对后,对错误的匹配点对观察,总结其规律,归为两类:某些含有重复结构的地方,如车牌的四个角,车标,前挡板处的特征点很容易误匹配到相似结构处.

针对以上两种情况, 都是因为没有考虑全局信息引起的.为了尽可能减少这两种误匹配, 本文利用了特征点和其邻近点的约束关系, 将那些错误的匹配点对初步筛选出来.通过观察发现误匹配点中心小区域内图像差异很大, 利用这个特性, 再进行小区域内直方图对比, 可以进一步确定是否为误匹配.

3 邻近特征点集夹角一致性约束与度量

3.1 邻近特征点夹角定义

3.2 邻近特征点集夹角一致性约束

特征点与其周围邻近点夹角一致原则基本思想如下:

若待匹配图像和模板图像的某对特征点是正确匹配点对,通过3.1节描述分别计算出θ和θ＾′,得到夹角差α后,应当有如下关系:

1)当图像没有明显的仿射变换时,α为零;

2)当图像仅有缩放变换时,α为零;

在本方法中,为了排除图像的噪声干扰,设置了2个松弛参数,分别是偏移角度上限θ和容错个数nError.仅当偏移夹角差超过偏移角度上限,并且超过这个阈值的邻近点个数大于容错个数时,才判定该对中心点为误匹配点对.

3.3 基于相关系数的度量方法

相关系数即归一化的协方差.它的定义为两个向量的协方差除以它们的标准差:

(1)

相关系数的范围在-1到1之间浮动,不会因为计量单位的变化数值太大或太小,相对于协方差有便于横向比较的优势.

图1 邻近特征点夹角Fig.1 Adjacent points′ angles

在本文中, 为了计算出两幅图像的相似性, 我们先获取匹配点对周围1/M*Width*Height大小窗口的区块, 得到其灰度化图像的直方图, 计算两幅直方图的归一化相关系数[14]d:

(2)

4 利用邻近特征点集夹角一致性约束的匹配提纯算法

4.1 算法描述

算法1.利用邻近特征点集夹角一致性约束的匹配提纯算法(见表1)

4.2 实验结果与分析

4.2.1 实验设置与算法性能评价指标

本文在Mikolajczyk[15]的特征数据集和CompCars[16]数据集上实验.通过考察正确率,召回率等指标,分析算法性能.由于nError与偏移角度上限θ互相独立,偏移角度上限θ和容错个数nError的设定通过控制变量,在保证其他参数不变的情况下,将一个参数在一定范围内浮动,利用准确率和召回率的ROC曲线,计算曲线下面积AUC评估性能.应用于车型分类时,将待识别图片与模板车辆图片匹配,归入经本文算法剔除后余下匹配点对最多的一组.

4.2.2 实验结果及分析

分别获得两组最优实验结果:控制偏移角度上限不变,容错个数nError从0到5变化时,召回率和准确率如图2(a)所示.在nError=3时,曲线下面积达到最大,此时性能最好;控制容错个数不变,偏移角度上限θ从0到60°变化时,召回率和准确率如图2(b)所示.在θ=15°时.曲线下面积达到最大,此时性能最好.

在Mikolajczyk特征数据集上实验,本文的算法与RANSAC算法对比如图3(a),图3(b)和图3(c)所示,图3(a)表示所有匹配点对,图3(b)表示本文算法剔除的10个点对,图3(c)表示RANSAC算法剔除的14个点对.可以看出,本文剔除的10个点有8个为误匹配点对,RANSAC算法剔除的14个点中,有8个为真实误匹配点.

表1 利用邻近特征点集夹角一致性约束的匹配提纯算法
Table 1 Matched points purification algorithm based on the consistency constraint of adjacent feature points′ angles

输入：模板图像中特征点坐标Oi(i=1…N)，待匹配图像中对应匹配点坐标O′i(i=1…N)；Oi的邻近点坐标Pj(j=1…M)，待匹配图像中对应点坐标P′j(j=1…M)．输出：true⁃判定为正确匹配对；false⁃判定为误匹配对．Begin1．fori=1toN2． forj=1toM3． αij=cos-1(OiPj，O′iP′j)4． end5． end6． β=∑Ni=1∑Mj=1αij/(N×M)7． b=08． fori=1toN9． forj=1toM10． ifαij>β+θ11． b++12． endif13． end14． ifb

在CompCars数据集上实验.连线表示原始匹配特征点对,其中本文算法剔除的特征点对用加粗线表示.同一车型如图4(a),图4(c),图4(e),图4(g)所示,不是同一车型的情况如图4(b),图4(d),图4(f),图4(h)所示,其正确匹配数目明显少于前一组.

图2 参数与性能Fig.2 Parameters and performance

图3 RANSAC和本文方法提纯示例Fig.3 RANSAC and the proposed method purify examples

对100张包含旋转、缩放、模糊、马赛克、光照变换的图像分别进行RANSAC和本文算法提纯,如表2所示,本文算法提纯的正确率和对于许多包含旋转缩放的数据集有很高的鲁棒性,相比之下,RANSAC方法提纯的正确率总体相当,但不稳定,两次同样的输入可能筛选出不同的匹配点对,召回率上RANSAC算法略高一些,在时间复杂度上,本文算法因为避免了迭代计算,较RANSAC有明显优势,节省约2/3时间.

图4 车型分类Fig.4 Vehicle classification

对250张包含5种车型正视视角的图片分类统计结果如表3所示,对车型的分类准确率达到了90%以上.

表2 本文和RANSAC算法对比
Table 2 Proposed method and RANSAC purification contrast

ResidEast＿ParkBikeTreesInriaCompCarsRANSAC本文RANSAC本文RANSAC本文RANSAC本文RANSAC本文RANSAC本文准确率0．790．780．920．920．950．930．890．900．920．910．900．92召回率0．820．730．930．870．830．710．750．640．860．810．890．76时间/S21．87．47．31．82．00．420．65．82．60．79．73．4

5 结 论

本文提出了一种利用邻近特征点夹角一致性约束的匹配提纯方法,并应用于车型识别.该方法针对特定目标对称性强、相似特征点多时容易产生误匹配的情况,根据两幅待匹配图像中对应邻近特征点夹角应当一致的原则,并利用局部图像块直方图信息,对SIFT特征点匹配结果提纯.本文方法对各种仿射变换有很强的抗干扰能力,并对一些滤镜变换也有较强的鲁棒性,与主流RANSAC方法的对比结果表明,准确率相当的情况下,耗时更少.此方法应用到车型分类上,达到了百分之九十以上的准确率.

表3 本文算法车型分类正确率
Table 3 Proposed algorithm vehicle classification precision

车型1车型2车型3车型4车型5总正确分类数4645414647225图片总数5050505050250正确分类率0．920．900．820．920．940．90

[1] Xu Yi,Zhou Jun,Zhou Yuan-hua.On stereo matching technology[J].Computer Engineering & Applications,2003,39(15):1-5.

[2] Fischler M A,Bolles R C.Random sample consensus:a paradigm for model fitting with applications to image analysis and automated cartography[M].Readings in Computer Vision:Issues,Problems,Principles,and Paradigms,Morgan Kaufmann Publishers Inc.,1987:726-740.

[3] Gong Sheng-rong,Zhao Wan-jin,Liu Chun-ping.Matched points purify algorithm based on gradient of disparity constraint[J].Journal of System Simulation,2008(S1):407-410.

[4] Xie Liang,Chen Shu,Zhang Jun,et al.Purifying algorithm for rough matched pairs using hough transform[J].International Journal of Image & Graphics,2015,20(8):1017-1025.

[5] Ki Y K,Baik D K.Vehicle-classification algorithm for single-loop detectors using neural networks[J].IEEE Transactions on Vehicular Technology,2006,55(6):1704-1711.

[6] Liu Yie-guang,You Zhi-sheng.An neural network for image object recognition and its application to car type recognition[J].Computer Engineering,2003,29(3):30-32.

[7] Chen Ai-bin.Vehicle recognition based on eigen-vehicle[J].Information Technology,2004,28(5):44-45.

[8] Huang Can.Vehicle recognition based on local feature[D].Shanghai:Shanghai Jiao TongUniversity,2010.

[9] Smith P L.New technique for estimating the MTF of an imaging system from its edge response[J].Applied Optics,1972,11(6):2974.

[10] Yue Si-cong,Zhao Rong-chun,Zheng Jiang-bin.MERF based edge detection with adaptive threshold[J].Dianzi Yu Xinxi Xuebao/journal of Electronics & Information Technology,2008,30(4):957-960.

[11] Caffarelli L,Nirenberg L,Spruck J.The dirichlet problem for nonlinear second order elliptic equations,III:Functions of the eigenvalues of the hessian[J].Acta Mathematica,1985,155(1):261-301.

[12] Wang Ya-wei,Xu Ting-fa,Wang Ji-hui.Improved matching point purification algorithm mRANSAC[C].Dongnan Daxue Xuebao,2013:163-167.

[13] Zhao Yang-yang,Li Xiao-qiang.Matching points purification based on offst space local consensus[J].Computer Applications & Software,2014,31(7):149-151.

[14] Lin L I.A concordance correlation coefficient to evaluate reproducibility[J].Biometrics,1989,45(1):255-268.

[15] Mikolajczyk K,Tuytelaars T,Schmid C,et al.A comparison of affine region detectors[J].International Journal of Computer Vision,2005,65(1-2):43-72.

[16] Yang L,Luo P,Loy C C,et al.A large-scale car dataset for fine-grained categorization and verification[C].Computer Vision and Pattern Recognition.IEEE,2015.

附中文参考文献：

[1] 徐 奕,周 军,周源华.立体视觉匹配技术[J].计算机工程与应用,2003,39(15):1-5.

[3] 龚声蓉,赵万金,刘纯平.基于视差梯度约束的匹配点提纯算法[J].系统仿真学报,2008(S1):407-410.

[4] 谢 亮,陈 姝,张 钧,等.利用Hough变换的匹配对提纯[J].中国图象图形学报,2015,20(8):1017-1025.

[6] 刘怡光,游志胜.一种用于图像目标识别的神经网络及其车型识别应用[J].计算机工程,2003,29(3):30-32.

[7] 陈爱斌.基于特征车的汽车车型识别[J].信息技术,2004,28(5):44-45.

[8] 黄 灿.基于局部特征的车辆识别[D].上海:上海交通大学,2010.

[10] 岳思聪,赵荣椿,郑江滨.基于多尺度边缘响应函数的自适应阈值边缘检测算法[J].电子与信息学报,2008,30(4):957-960.

[12] 王亚伟,许廷发,王吉晖.改进的匹配点提纯算法mRANSAC[C].中国智能自动化学术会议,2013:163-167.

[13] 赵洋洋,李晓强.基于偏移空间局部一致性的匹配点提纯[J].计算机应用与软件,2014,31(7):149-151.