点匹配算法（精选7篇）
点匹配算法 篇1
图像匹配是机器视觉关键技术之一, 广泛应用于图像拼接、全景视图、对象识别等领域。基于特征点的匹配方法是目前图像匹配的主流方法, 而如何有效提取特征点及建立特征点间对应关系一直是这类方法的研究热点与难点。
深入分析研究广泛的两种典型特征点提取算法可知, 本文将Harris算法和SIFT算法两种算法取长补短, 提出了一种新的H/S (Harris/SIFT) 特征点提取算法, 并提出传统三角形匹配算法的改进。
一、基于H/S的特征点匹配算法改进
由于三角形抗平移、旋转和缩放, 对于处理图像间存在平移、旋转、缩放等情况, 具有很好的优越性。但当模板点集中一个点与目标点集中多个点匹配这种情况出现时, 特征点的对应关系不易找出。根据以上分析, 引入基线及基线三角形组的概念, 以采用H/S算法提取得到特征点为基础, 合理选择基线提高搜索效率, 然后由复数相乘的几何意义, 将图像特征点转移到复数向量空间中求解, 将传统方法中被动的搜索相似三角形变为选择基线后主动构造相似三角形组, 提高匹配准确性。
二、相似三角形匹配方法实现
运用H/S提取稳定特征点后进行图像匹配, 图2为实物图存在噪声且模板图像发生旋转、缩放时匹配结果, 结果表明在实物图受噪声干扰情况下, 该算法仍能准确找到发生旋转、缩放情况的模板图像;图3为使用Google Earth上截得的摇感图像进行图像匹配, 图3中的模板图像经过90度旋转, 并存在一定尺度放大, 结果表明该方法准确的在实物图中找到模板图像, 体现该算法在复杂背景下识别出目标物体的适用性, 验证了改进H/S算法提取特征点的有效性。
结论
本文在对现有特征点提取与匹配方法进行研究基础上, 提出一种新的H/S特征点提取算法, 并使用H/S特征点提取算法得到图像中的特征点后, 针对传统相似三角形匹配算法的局限性进行改进, 提高了算法的稳定性、准确性和快速性。
参考文献
[1]王红梅、张科、李言俊:《图像匹配研究进展》, 《计算机工程与应用》, 2004年19 (4) :42-45。
[2]甘玲、郑一帆:《基于改进的模板匹配的图像拼接算法》, 《计算机科学》, 2008, 35 (4) :332-333。
点匹配算法 篇2
自动指纹识别系统[1](Automated Fingerprint Identification System,简称AFIS)己经被广泛应用。用于罪犯身份鉴定的指纹识别系统,对可靠性要求较高。而一般民用的指纹识别系统对可靠性要求并不是很高,其设计要求是保证一定可靠性的前提下,具有很高的实时性,因此识别速度是最关心的问题。指纹匹配是识别系统的核心环节,匹配算法的好坏直接影响识别的性能、速度和效率。
2 指纹图像的匹配
指纹匹配要解决的问题是,对从两幅给定的指纹图像中提取出来的特征信息进行匹配,判断这两枚指纹是否来自同一个指头。
为了能够实现准确、快速的指纹匹配,前人已对指纹匹配技术进行了深入而细致的研究,到目前为止,已经提出了很多指纹匹配算法。目前指纹匹配的方法可以分成两大类[2,3]:一类是基于图形的匹配方法,另一类是采用人工神经网络的匹配方法。最常用的方法是FBI提出的特征点坐标模型来做细节匹配,即使用两种类型的特征点:分叉点和末梢点,来鉴定指纹。
本文深入讨论了基于特征点坐标模型匹配的点模式匹配算法,提出了两级指纹匹配算法。
2.1匹配算法描述
本文将指纹匹配分成粗细两个等级进行,有效减少匹配运算计算量,加快匹配速度。2.1.1参考点的定位及图像校准2.1.1.1参考点的定位
2.1.1参考点的定位及图像校准
2.1.1.1参考点的定位
为使特征具有旋转、平移不变性,依赖于参考点的准确定位。
选择分叉点所在脊线进行离散采样:从分叉点开始对它所在的脊线进行跟踪,若当前点与前一个抽样点的欧氏距离等于脊线平均距离λ,则把当前点作为一个抽样点。记录下该采样点与特征点的欧式距离di和连接该点与对应特征点的直线与对应特征点的方向夹角αi,沿着脊线连续采样N5次,如果采样过程中遇到其他特征点,则放弃该分叉点。设输入图像中第m个分叉点所在脊线的实际抽样点数为Nm,模板图像中第n个分叉点所在脊线的实际抽样点数为Nn,有0
将模板图像集合P和待识图像集合Q中的所有采样脊线逐一进行匹配。对于模板点集中的点Pi和输入点集中的点Qj,如果他们均为分叉点,且均进行了纹线采样,则计算两点所在纹线的相似度。定义Sim_dist,Sim_angle,来衡量脊线的相似度。
模板中第m条脊线(即第m个分叉点对应脊线)和输入点集中第n条脊线(即第n个分叉点对应脊线)的相似度:
所有采样脊线逐一匹配后,(Sim_dist+Sim_angle)最小时对应的m,n即为所求的参考点对。
2.1.1.2图像校准
虽然选定了参考点对,但参考点对所在的脊线还存在着差异,还应对其进行参考点所在脊线的旋转和平移。
估计模板图像和输入图像中与特征点相关的脊线之间的平移,旋转角度,如图2所示。将以参考点N为基点的输入脊线向上平移,使N与模板中M点重合,且两条脊线相差的旋转角度为△θ。
令(xn,yn)T为输入图像细节参考点坐标值,(xm,ym)T为模板图像细节基准点坐标值,则脊线平移公式为:
旋转角度△θ的计算公式为:
L为输入细节参考点所在的脊线长度和模板细节参考点所在脊线长度的最小值;αi,βi分别为输入细节参考点和模板细节参考点所在脊线第i点的径向角。
输入图像的每一个细节特征点Qj可根据(△x,△y,△θ)三个参数进行校正,其计算公式为:
校正过的输入图像细节点转化为极坐标形式,具体公式为:
其中(xi*,yi*,θi*)T是待转换节点的坐标,(xr,yr,θr)T是参考点的坐标,(ri,ei,θi)T是节点在极坐标中的表示,利用该节点对齐方法,得到了节点的极坐标表示形式。
2.1.2第一级匹配
以参考点为圆心,固定长度为半径,在模板指纹图像和输入指纹图像分别划出一个相等的感兴趣区(ROI),作为第一级匹配区间。选取ROI作用:一来可以抵抗指纹形变;二来可以方便匹配。
1)取的ROI半径为96,单位为像素。
2)搜索ROI内端点和分叉点的个数,记录模板指纹图像的分叉点个数和端点个数分别为Pb,Pe,输入指纹图像特征点个数为Qb,Qe。
3)计算│Pb-Qb│,│Pe-Qe│:
如果│Pb-Qb│<ε1且│Pe-Qe│<ε2,则进入下一级匹配。否则,直接认为不匹配。其中ε1=0.5min(Pb,Qb),ε2=0.5min(Pe-Qe)。
2.1.3第二级匹配
按指纹时,由于用力的差异等多种因素,必然会使得两幅指纹图像间存在非线性形变,即使经过校准,输入图像中的细节点也不可能和模板图像中的对应细节点完全重合。因此,细节点匹配算法应该能够在一定
程度上容忍由于提取出来的细节点位置不精确或图像的非线性形变造成的对应点位置差异。
本文采用一种称为可变限界盒的方法,对模板指纹特征点集中的每一个特征点,选取它周围的一个矩形区域作为它的限界盒,其中盒子极半径radius_size与盒子极角angle_size值将随着节点的极半径大小而改变。如果模板节点的极半径比较大,它的限界盒将有一个较大的radius_size和较小的angle_size。可变限界盒如图3所示。
只要校准后的待识别指纹中的特征点落在这个区域之内,而且方向基本一致,我们就可以认为这个特征点对是一对匹配的特征点。该算法对非线性形变更为鲁棒,能处理含有非线性畸变、角度旋转和缺损的指纹图像。
3 算法实验结果
为验证本文方法的实际性能,选择杭州中正生物认证技术有限公司生产的电感指纹仪来采集指纹图像,一共对10个人进行了指纹采集,每个手指选取10幅图像,共获得1000幅指纹图像(图像大小为192×192像素,分辨率为500dpi)。在PC机上实现了上述算法。
为了计算据识率(如果同一手指的两枚指纹没有确认,就是拒识),让每个指纹样本与同一手指的其他指纹图像进行匹配,共进行了(10×9/2)×100=4500次实验。为计算误识率(如果不同手指的两枚指纹确认了,就是误识),让每一个手指样本与不同手指的每个样本进行匹配,共进行了(99×10)/2×100=49500次,对这1000枚指纹进行识别的实验结果是:错误拒绝次数为105次,拒识率为2.3%,错误识别次数为295次,误识率为0.6%,平均每次匹配时间为0.01秒。
4 结束语
本文介绍讨论了一种基于点模式的快速指纹匹配算法。采用两级匹配,一级粗略匹配中,只统计ROI中端点和分叉点的个数,算法简单,快速排除不匹配的指纹,克服了传统指纹匹配算法的大量冗余计算;第二级精确匹配中,利用了可变限界盒的算法,该算法很好地抑制了指纹采集过程中的非线性形变给匹配造成的影响。
参考文献
[1]N.Yamaguchi,Advanced Automated Fingerprint Identification System[J].32ndAnnua l998International Carnahan Conference on Securi-ty Technology.1998,10:154-157.
[2]A.WahabS.H.Chin,E.C.Tan.Novel approach to automated fingerprint recognition.IEE Proc.Vis.Image Signal Process,1998,145(3):160-166.
[3]王业琳,宁新宝,尹义龙,一种新的指纹匹配方法[J].中国图像图形学报,2003,8(2):203-208.
[4]尹义龙,宁新宝,张晓梅.一种基于纹线相似度的指纹匹配算法[J].模式识别与人工智能,2002,15(4):502-506.
点匹配算法 篇3
微创外科手术机器人系统由医学成像设备、微操作装置、传感器、计算机和机械手器具等辅助协同构成,凭借着各种视觉图像设备,将先进灵巧的手术操作设备通过微小的切口进入人体,对器官进行手术诊断及治疗。由此,使外科手术从一个开放式的全人工手术过程,向借助手术机器人辅助医生完成最小侵入式手术转变[3]。通过此种手术方式,医生在选择最佳的手术方案、执行复杂手术的能力和手术的成功率等方面受益匪浅。
在机器人实施手术过程中,机器人辅助导航系统可使手术医师看到手术部位病变的具体情况,避免了医生因为经验不足而造成的手术失败,确保手术更加安全、可靠。对于主从式机器人,在手术中,手术医生的方案来自视频图像获取患者器官信息;医生直接操控控制台上手柄、按钮等主手设备,通过计算机将相关指令传送给从手器械臂;医师通过监控从手的运动情况,及时调节或修整以实现预期结果;最终完成微创手术。手术机械臂是直接接触病患进行操作的。因此,其性能指标的高低将直接影响整个手术机器人系统的性能、效果以及安全性能等。另一方面,医生是通过手术臂上的两个高清摄像头实时了解患者手术部位的情况,所传送的图像的清晰度,准确度直接影响医生对于患者情况的判断;图像的高清晰度,高准确度同样是手术导航系统的一个重要研究趋势。因此,深入研究微创外科手术机器人双目立体视觉的各项图像处理技术,对临床医学有着重要的理论和实际应用价值。
基于特征点的图像匹配因具有计算量小、适应能力强和匹配精度高的特点而得到了广泛应用。目前,比较常用的特征点检测方法有Harris角点检测方法和SIFT图像特征点算法[4]。用Harris角点检测法不仅尺度可变且抗噪声能力较差,而SIFT算法与之相比,具有良好的尺度、光照、空间旋转不变性[5]。因此,SIFT算法普遍应用于图像匹配领域[6,7,8]。但是,SIFT算法也有如下缺陷:(1)特征向量的维数过高,达128维,匹配时由于计算数据量大、所以耗时长。(2)使用的仅是图像灰度信息,忽略了彩色的信息,故图像信息未能得到充分利用,这在微创外科手术中存在较大的弊端。为解决上述缺陷,有人在对特征描述及匹配阶段进行了改进,但没有改变算法本身,治标不治本。于是,Bay等人[9]提出了SURF(Speed -Up Robust Features)图像特征点算法,该算法可广泛应用于实时性要求高的物体识别、图像拼接等方面,特别适用于微创外科手术中。为此,本文采用了一种基于SURF的图像特征点匹配算法,不仅能满足匹配精度要求,同时具有较快的匹配速度。为微创外科手术中医生检查、判断、手术和术后信息资料查找提供了良好的基础。
1 SURF特征点检测和特征描述
SURF算法是对SIFT算法的改进和优化。SIFT算法中用差分高斯金字塔代替高斯金字塔,以提高算法性能;与此类似,SURF算法中用方框滤波近似代替高斯滤波,用积分图像加速卷积提高运算速度,以损失较小的精度为代价,获得更快的特征点检测速度[10]。SURF算法主要分成3 部分:(1) 特征点提取。即在积分图像的基础上,利用方框滤波近似代替二阶高斯滤波,计算待选特征点及其周围点的Hessian值,如果最大,则为特征点。(2)特征点描述。即在特征点周围小区域上计算Haar小波,并计算其4 种和以构成特征描述。(3)利用特征点描述向量进行配准。
1. 1 特征点检测
SURF算法对特征点的检测基于Hessian矩阵。对于图像中的某一点p=(x,y)以及高斯滤波器的尺度σ,其Hessian矩阵H(,σ)表达式如下
其中,Lxx(p,σ),Lxy(p,σ),Lyy(p,σ)是图像中p点与高斯二阶偏导数的卷积。Hessian矩阵的行列式为
实际运算中由于高斯滤波器须离散化,故随着尺度 σ 的增大图像细节逐渐被过滤。采用SURF算法以方框滤波(Box Filter)近似代替高斯二阶导数,用积分图像加速卷积后式(2)的近似表达式为
其中,Dxx,Dyy,Dxy是图像中p点与方框滤波的卷积。
为在不同尺度上寻找特征点,须建立图像的尺度空间。SIFT算法中构造尺度空间是对原图不断进行高斯平滑和降采样,计算图像金字塔中相邻尺度空间函数的差值得到DOG尺度空间,此过程中高斯滤波器的大小不变,改变的是图像大小。SURF算法中,图像大小保持不变,改变滤波器大小,利用积分图像快速计算大幅提高了效率,且由于未对图像进行降采样而不存在混叠现象。在三维(x,y,σ)空间中,每个3 ×3 ×3的区域内进行非极大值抑制。选取比相邻26 个点的响应值都大的点为特征点,即可得到稳定的SURF特征点位置及其所在的尺度值[11,12,13,14]。
1. 2 特征描述
用每一个特征点为圆心、6σ 为半径的圆形区域计算x和y方向的Hear小波(Hear小波边长取4σ)响应,继而以特征点为中心对这些响应进行高斯加权。采用1 个 π/3 的扇形区域的滑动窗口,计算窗口内x和y方向的响应总和,得到1 个局部的方向向量。转动扇形遍历整个圆,选择最长的向量方向作为特征点的主方向。
以特征点为中心,首先将坐标轴旋转到主方向,按主方向选取边长为20σ 的正方形区域,将该区域划分成4 ×4 个子区域;对每个子区域计算25 个空间归一化采样点的Hear小波响应。假设dx和dy分别表示水平与垂直方向上的Hear小波响应,为增强鲁棒性,可对dx和dy进行高斯滤波,以滤波器中心为特征点,在每一子区域对dx,dy,|dx|,|dy|求和,得到1 个4 维向量v(∑dx,∑dy,∑ dx,∑ dy) ,所有子区域的向量构成该点的特征向量,长度为64,对其归一化所得的特征向量具有旋转、尺度和光照不变性。
2 特征点匹配
获取SURF特征向量后即可进行特征点匹配。Beis和Lowe曾经提出了一种近似算法,称为BBF的k - d树的近似算法。这种算法的优点是能以较高的概率找到最近邻点。将这种搜索方法做进一步改进,即仅搜索近似的邻近点,则可提高搜索的效率。这种方法称为Best Bin First算法。该算法的主要思想是:沿着k - d树的某一分支查找,将记录每一个节点的信息,放入到一个优先队列中,直至查找到该分支的叶节点;然后在这个优先队列中取出距离值最小的节点信息存储到近邻点数组中;在另一分支中重复上述过程,直至找到第nmax个叶子节点;最后,在近邻点数组中取出距离最短和次短的两个点,计算得到的距离比值,如果小于设定的阈值,则距离最短的点是被检索点的最近邻点,即匹配点。
对待配准图像中每一个特征点,用BBF算法在参考图像中寻找与其特征向量最近邻和次近邻的两个点,判断这两点与特征点的距离比值是否小于阈值0. 8。如果小于,则这个最近邻点就是该特征点的匹配点;反之,该特征点就没有匹配点。
采用最近邻搜索算法(Best Bin First,BBF)在欧式空间搜索查找每个特征点的两个最近邻特征点。在这两个特征点中,如果最近距离与次近距离的比值小于某个比例阈值(试验取0. 7),则接受这对匹配点。
采用优化的BBF算法,可加快匹配点的搜索过程,减少了大量的计算量,加速了匹配进程。
在计算Hessian矩阵行列式的同时计算出Hessian矩阵迹t,判断t符号,若>0,则对描述子赋值1;若<0,则对描述子赋值- 1。将每幅图像的特征点按描述子的值分为两组,对相同类型数据进行比较,如果两个描述子的值不同即表示不匹配,则无须继续比较。
针对特征点匹配得到的匹配点中存在误匹配问题,利用随机抽样一致性算法(RANSAC)将匹配质量较差的点作为外点去除,然后在程序中设定选取相似度最高的前n对匹配特征点,通过对n赋值以满足匹配精度的要求。
3 实验结果及分析
实验环境为Pentium(R)Dual - Core CPU,4 GB内存,Matlab软件7. 0,图像处理工具箱。先采用标准的Lina图提取特征点。对Lina图像以及旋转过20°后的Lina图像提取特征点,具体结果如图1 和图2 所示。
为验证SURF算法的时效性,分别采用SIFT和SURF算法对同一组医学图像进行特征点提取[8],并统计出所提取特征点的个数及特征点检测消耗的时间,结果如表1 所示。通过对比可知,SURF算法提取特征点效率高,且能满足精度要求。表2 给出对一组图像进行SURF特征点提取后分别采用BBF算法和本文算法进行特征点匹配的时间比较。如表2 所示,基于SURF的匹配算法进行图像特征点提取和匹配时比传统的算法速度更快,因此有利于进行实时的物体识别或图像拼接。
4结束语
为证明SURF算法比SIFT算法优异。采用标志医学图像进行实验,利用SIFT和SURF算法进行比较。得出结论:SURF算法剔除了较多不必要的点,提高了有效性,并且SURF算法时间更短,在实时性较强的手术中实用性良好。然后利用优化的BBF算法进行特征点匹配效果改善显著。实验结果验证了该算法的有效性。并且当图像存在平移、旋转影响时,具有较好的鲁棒性。然而,在实际手术过程中,图像采集会受到光照强度改变、相机抖动、被手术人的肌肉运动,血液流动等因素,图像的纹理信息有所减少,加大了匹配难度,今后将对算法作进一步的研究,以提高其鲁棒性和图像稳定性,使该技术更成熟,以适应微创外科手术的实际需要。
摘要：微创外科手术中的图像特征点快速匹配,可使计算机具备图像实时识别能力,提高手术成功率。但由于在手术中所运用的图像匹配算法具有计算量大、耗时长等缺点,提出一种基于SURF的图像特征点快速匹配算法。首先对图像采用SURF算法提取特征点,然后通过Hear小波变换确定特征点的主方向和特征点的描述子,并使用改进的最近邻搜索算法进行特征点匹配,最终根据实际需要选取相似度最高的前50~100对匹配点进行对比实验。实验结果 表明,该算法鲁棒性强、速度快、匹配准确性高,且在医学图像处理中具有较大的应用价值。
点匹配算法 篇4
图像匹配技术是图像处理和计算机视觉领域的一项重要技术。图像匹配,就是在机器识别事物的过程中,将已知图像与陌生图像的全部或部分在空间上对准,根据已知模式的图像在一幅陌生图像中寻找对应该模式的子图像过程。图像匹配所涉及的应用领域包括工业检测、遥感地形匹配、光学和雷达图像跟踪、工业流水线自动监控、交通管理、医疗诊断、图像检索等诸多领域。
目前,图像匹配技术有基于与像素灰度相关的匹配、基于图像特征的匹配、基于语义网络的匹配以及基于神经网络和遗传算法的匹配等多类方法。近年来,基于局部不变量描述符的方法在图像匹配领域取得了显著进展。SIFT[1](scale invariant feature transform)方法是Lowe在2004年提出的一种局部不变特征点的提取方法。SIFT特征是图像的局部特征,对旋转、尺度缩放和亮度变化保持不变,对视角变化、仿射变换和噪声也保持一定程度的稳定性。SIFT还具有独特性、多量性和可扩展性等多项特点。基于SIFT特征的算法目前在图像拼接[2]、遥感图像[3]的配准等很多领域都得到了应用。
1 SIFT算法
SIFT是通过在图像的尺度空间内,将定位极值点作为匹配候选关键点,并提取极值点的方向参数,最后获得匹配所需关键点描述符的一种算法。使用SIFT算法实现图像匹配主要有以下几个步骤:
1.1 检测尺度空间极值点
尺度空间(Scale space)思想最早由Iijima于1962年提出,20世纪80年代Witkin和Koenderink[4]的奠基性工作使得尺度空间方法获得较快发展。1994年Lindeberg等人建立的线性尺度空间方法被广泛采用[5,6]。
尺度空间方法的基本思想是:在视觉信息的处理过程中引入一个尺度参数,通过连续变化的尺度参数获得不同尺度下的视觉处理信息,然后综合这些信息以便深入挖掘图像的本质特征[5]。
给定图像I(x,y),其所对应的尺度空间表示L(x,y)可以由一个卷积核和图像卷积得到[7]。
式中:g(x,y;δ)是高斯卷积核,也是尺度变换惟一的线性核[8],其中,δ是尺度参数,对应高斯核函数的方差,改变δ的值可以获得一组图像的尺度空间表示[2]。
对相邻尺度的图像做差分,可以获得一组DoG(difference of gauss)图像D(x,y;δ)。
图像的空间极值点是该点与其相邻8个点及相邻两个尺度所对应位置的18个点共27个点中的最大值点[9],如图1所示。
1.2 精确定位极值点
DoG算子会产生较强的边缘响应,且在1.1节中检测到的极值点精度为像素级。
通过拟合三维二次函数可以将极值点插值定位到亚像素精度。将D(x,y;δ)Taylor展开可得:
式中:D及其导数是采样点的估计值;X是距采样点的偏移量。此时,极大值点的位置X′可以由下式确定:
一个定义不好的高斯差分算子的极值在横跨边缘处有较大的主曲率,而在垂直边缘的方向有较小的主曲率。主曲率是通过一个2×2的Hessian矩阵H求出的。即:
导数由采样点相邻差估计得到。主曲率由H的特征值计算得出,令α为最大特征值,β为最小特征值,令α=rβ,则主曲率由下式确定:
选取合适的主曲率阈值,可以去除不稳定的边缘响应点,从而获得精确定位的极值点作为关键点。
1.3 指定关键点方向参数
利用关键点邻域像素的梯度方向分布特性为每个点指定方向参数,可以使算子具有旋转不变性。
梯度m(x,y)和方向θ(x,y)可以由下面的公式计算:
实际计算时,在以关键点为中心的邻域窗口内采样,并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0～360°,其中每10°为一个柱。直方图的峰值代表了该关键点处邻域梯度的主方向,即作为该关键点的方向。
当存在另一个相当于主峰值80%能量的峰值时,将这个方向认为是该关键点的辅方向。一个关键点可以被指定具有多个方向,这可以增强匹配的鲁棒性。
至此,每个关键点已经检测完毕,每个关键点具有3个信息:位置、所处尺度和方向,由此可以确定1个SIFT特征区域。
1.4 生成关键点描述符
先将坐标轴旋转为关键点的方向,以确保旋转不变性;再以关键点为中心取8×8的窗口,图2左边的中央黑点为当前关键点的位置,每个小格代表关键点邻域所在尺度空间的一个像素,箭头方向代表该像素的梯度方向,长度代表梯度模值,圆形区域为高斯加权范围;然后在4×4的小区域上计算8个方向的梯度方向直方图,绘制每个梯度方向的累加值,即可形成1个种子点,如图的右部分所示。此图中一个关键点由2×2共4个种子点组成,每个种子点共有8个方向向量信息。邻域方向性信息联合的思想增强了算法的抗噪声能力,同时对于含有定位误差的特征匹配提供了较好的容错性。
这样,对于一个关键点就可以产生2×2×8共32个数据,形成一个32维的特征向量。此时的SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响。再继续将特征向量规一化,可以去除光照变化的影响。
1.5 匹配
生成2幅图像的特征向量后,采用关键点特征向量的欧几里德距离作为两幅图像中关键点相似性的判定度量。取一幅图像中的某个关键点,并找出其与另一幅图像中距离最近的前2个关键点,在这两个关键点中,如果最近的距离除以次近距离小于某个阈值Th,则接受这一对匹配点。降低这个比例阈值,匹配点数量会减少,但匹配过程更稳定。反之,匹配点数量会增多,但稳定性随之会变得稍差。
1.6 实验及结果
在图3(a)和图3(b)中各包含了两幅图像,每幅图像大小均为326×245像素。其中,右边为待匹配物品的图像,左边为待匹配物品放入复杂场景后所形成的图像。图中连线的两端是两幅图像中对应的匹配点。
为了增强匹配的稳健性,在匹配过程中,对每个关键点使用4×4共16个种子点描述,这样对于一个关键点会产生一个128维的特征向量。匹配过程中采用阈值Th=0.6,在去除不稳定响应点时采用r=10。
在图3(a)左边的图像中,除了匹配区域的尺度有变化外,被匹配的目标区域还发生了遮挡,但未遮挡部分仍与右侧图像中的模板图像正确匹配。图3(b)中的待匹配图像区域是物体在发生约90°旋转后所形成的,此时仍能正确匹配。
2 结 语
通过原理分析和实验结果验证,用SIFT算法提取的匹配关键点是一种局部描述符。使用SIFT算法实现图像匹配具有对尺度变化、旋转、光照和视角变化的稳定性。当发生部分遮挡时,仍可实现有效匹配。基于SIFT特征点实现图像匹配是一种有效方法。SIFT可进一步应用于图像检索,视频跟踪等多个领域。
参考文献
[1]LOWE D.Distinctive image features from scale-invariantkeypoints[J].International Journal of Computer Vision,2004;60(2):91-110.
[2]张朝伟,周焰,吴思励,等.基于SIFT特征匹配的监控图像自动拼接[J].计算机应用,2008,28(1):191-194.
[3]李晓明,郑链,胡占义.基于SIFT特征的遥感影像自动配准[J].遥感学报,2006,10(6):885-891.
[4]WITKIN A P.Scale-space filtering[C]//Proc.7th Interna-tional Joint Conference on Artificial Intelligence.[S.l.]:IJ-CAI,1993:1019-1022.
[5]孙剑,徐宗本.计算机视觉中的尺度空间方法[J].工程数学学报,2005,22(6):951-962.
[6]LOWE D.Object recognition from local scale-invariant fea-tures[C]//International Conference on Computer Vision.Greece:ICCV,1999:1150-1157.
[7]LINDEBERG T P.Internal report TRI TA-NA-P8808[R].Stockholm,Sweden:Royal Institute of Technology,2000.
[8]BABAUD J,WITKIN AP,BAUDIN M,et al.Uniquenessof the Gaussian kernel for scale-space filtering[J].IEEETransactions on Pattern Analysis and Machine Intelligence,1986,8(1):26-33.
[9]LINDEBERG Tony.discrete derivative approximations withscale-space properties:a basis for low-level feature extrac-tion[J].Journal of Mathematical Imaging and Vision,1993,3(4):349-376.
点匹配算法 篇5
特征点匹配[1]是计算机视觉中的关键技术,在运动估计、图像识别等领域有着重要的应用。特征点是图像局部灰度值发生剧变的点,包含丰富的图像信息,特征点匹配就是对图像上提取的特征点在另一图像上找到该特征点的精确位置。基于上述因素,本文提出了在Harris特征点提取[2]的结果上再进行匹配算法验证的思路。而传统的基于图像灰度的相关匹配算法[3 - 5]主要是逐像素地把一个以一定大小的实时图像窗口的灰度矩阵与参考图像对应位置的窗口灰度阵列按某种相似性度量方法进行搜索比较,寻找出相关性最大的点。但经典相关匹配算法的运算量大,对尺度变化后的图像进行特征点匹配精确度较差,在一定程度上影响了它的实用性。因此探索易理解、易实现的能够克服尺度变化的图像特征点匹配算法是必要的。本文提出的匹配算法,主要利用两幅图像特征点间欧氏距离[6]的关系来确定匹配点集,极大地减少了灰度相关计算的次数,也排除了一部分的误匹配点,并使用特征点的梯度相关法进行精确匹配,结果达到了较好的精确效果。
2基于灰度的相关匹配算法［7 －8］
在检测出特征点之后,利用角点矩形领域窗口内像素的灰度信息,通过互相关函数来判断是否匹配。两幅图像不同特征点的相似程度采用互相关函数来评价,互相关关系定义为
式中:是图像Ik上点(u,v)的邻域灰度平均值;σ(Ik)是图像Ik中(2n+1)×(2m+1)邻域内点的标准偏差。R值越大,说明两个特征点越相似。
对于图像I1上的特征点m1和图像I2上的特征点m2,图像坐标分别为( u1,v1) 和( u2,v2) ,给定以m1为中心的相关性窗口( 2n + 1) × ( 2m + 1) ,在I2相应于m1的位置选定( 2du+ 1) × ( 2dv+ 1) 的搜索窗口,通过上述的互相关公式计算所有在搜索窗口内的特征点m2与m1的相关系数,最后为计算出来的相关系数设定阈值k来判断,在计算结果大于设定的阈值时,认为两点是相互匹配的点。
虽然,这种相关法匹配容易理解并实现,但是,它在理论上假定了两幅图像没有光照的变化,同时没有太大的平移和旋转,无法精确做到发生尺度变化后的图像匹配。这样必然限定了该算法的应用范围,同时固定的阈值导致了整个系统的误判性增高,大的阈值使得很多匹配点被漏检,小的阈值导致更多的一对多的误匹配点出现。
3相关算法理论
3. 1欧氏距离
在二维图像当中的欧氏距离主要是指两点之间的距离,本文采用欧氏距离主要是来计算一幅图像中两个特征点的距离,计算公式为
式中:(x1,y1)和(x2,y2)是一幅图像特征点集中的点;d是在该图像上的两点之间的欧氏距离。考虑到图像特征点之间最为直接的关系就是距离的关系,因此,无论需要匹配的两幅图像有无尺度变化,它们在特征点之间距离关系上是不会变的。本文采用欧氏距离来约束特征点集的匹配,主要思想是在第一幅图像上如果离特征点A最近的距离就是特征点B,那么在对应需要匹配的另一幅图像上肯定有与A匹配的点A1,如果特征点A与特征点A1是正确的匹配点,那么在A1对应的图像上必然能找到距离A1最近的点,该点有可能就是B所匹配的点。
3.2梯度算法
图像的梯度在图像的边缘检测,图像滤波等方面的应用已十分成熟,本文主要是把梯度作为图像特征点匹配的一个新的衡量标准,主要考虑如果两幅图像上的某个点是匹配的,那么它们各自的梯度值应该是相关的。
在计算图像梯度时,主要是把图像看成二维离散函数,图像的梯度其实就是二维离散函数的求导,即
式中:G(i,j)就是梯度值;dx和dy分别是二维图像的两个方向的导数值;I是图像像素的值;(i,j)为像素的坐标。不过,图像梯度一般也可以用中值差分来计算,即
本文主要利用匹配特征点的梯度相关性来实现特征点的匹配。首先,分别计算两幅图像特征点的梯度,然后对需要匹配的特征点集进行梯度相关性的计算,梯度相关性计算主要利用相关法的计算公式,只是把灰度值的相关性比对变成梯度值的相关性比对,见式(8)。最后,计算出相关系数R,R越大,则相关性越大。
其中,各部分的计算方法同灰度相关法计算方法类似,在这里不再赘述。
3.3本文提出的改进的特征点匹配算法
1)对于获得的两幅图像的特征点集,首先需要对每组点集进行去除相同坐标点的初始化处理。然后,选择初始的第一组精准的匹配点,该初始的匹配点组可以在基于一幅图像的一个特征点的基础上,通过手动地自助选择另一幅图像上对应点,主要操作是通过主动观察的方法,选定相对应需要匹配的特征点在这幅图像上大概的匹配位置,获得一些对应的匹配点集。
2)开始对步骤1)产生的一对多的点集进行细化,首先用灰度相关法计算每两个点之间的灰度相关系数,该相关系数小于阈值k时,认为原计算的那个点是误匹配点,从而去除部分误匹配点,然后对剩余点用梯度相关法来精确匹配点,主要是通过计算两点之间的梯度相关系数,如果该系数大于阈值l,则认定该点为对应的匹配点。这样,最终获得初始的、精确的、一对一的匹配点。
3)在获得初始的一组精确的匹配点组后,在第一幅图像上用欧氏距离来计算离第一个匹配成功的特征点最近的点,该点被确定为需要匹配的第二个点。针对这个需要匹配的点,在第二幅图像上同样寻找离第一个匹配成功的特征点最近的点,因为需要考虑图像发生尺度变化后可能引起的图像畸变,因此,在这幅图像上把该最近的距离的n倍作为阈值g,计算第一个点到其他点的欧氏距离,把在这个阈值g范围内的点认为是第一幅图像上第二个点可能匹配的点。然后按照步骤2)一对多地匹配点的方法来精确匹配点。
4)剩余的两幅图像上的特征点集,按照步骤3)的方法处理,直到特征点全部匹配完成。实现的算法流程图如图1所示。
4实验结果及分析
本文采用了MATLAB2011版本工具对新算法和经典的灰度相关匹配算法进行仿真实验。两幅图中需要对300个特征点对进行匹配,但为了在图像中能清楚看到匹配结果,避免过多的线被遮挡,所以在图中选用部分点来显示。图2与图3是在旋转尺度变化下,按照传统的灰度相关法所进行的特征点匹配结果图和改进算法所进行的特征点匹配结果图。图4与图5是在旋转和缩放同时变化下传统的灰度相关法所进行的特征点匹配结果图和改进算法所进行的特征点匹配结果图。表1为两种算法的比较。
图 4 传统的灰度相关法匹配算法的结果( 旋转 + 缩放)
图 5 改进的匹配算法的结果图( 旋转 + 缩放)
结合图2~图5和表1明显可看出,灰度相关法在对尺度变化的图像中匹配特征点应用上基本失效,同时,从本文改进算法的实验结果可知,仍存在极少数的误匹配点,但是与传统算法的匹配结果相比,获得了比较理想的结果,不过也同样增大了运算的时间复杂度。
5结语
本文在传统的灰度相关法匹配特征点的思想上,提出了可以克服图像尺度变化的特征点匹配的算法,该算法在实现和理解上都比较简单,结果也比较理想。但同时为获得更简单、实用以及具有更好鲁棒性的特征点匹配算法,本文算法还需进行深入研究。
摘要：通过对灰度相关法特征点匹配算法的理论研究和实验分析,提出了一种能够克服图像尺度变化的特征点匹配算法。该算法主要根据图像特征点间欧氏距离的关系,结合传统的特征点灰度相关法和特征点的梯度相关法进行精确匹配。实验证明,该算法容易理解,易于实现,匹配结果较精确,误匹配点较少。
点匹配算法 篇6
近些年,在数字图像鉴别方面已有了一系列的研究成果,这些成果可以被分为两大类:主动鉴别(Active Authentication)和被动鉴别(passive Authentication)。主动鉴别包括数字水印技术和数字签名技术,这种技术的优点是准确性高,但也有一个限制:必须在建立数据时进行人为的预处理,更重要的是,这种主动鉴别的技术会降低图像质量[2]。被动鉴别是从目标图像的固有特性出发寻找篡改检测和定位。例如Fridrich等人提出了一种有效的分块方法,将量化的DCT系数代替图像各分块像素信息,然后对分块系数排序,最后找到相似的部分[3]。Popescu和Farid在Fridrich的基础上利用主分量分析的方法来对图像进行篡改鉴别[4]758。但是这种方法的鲁棒性较差,将图像进行一定的处理后(例如压缩)鉴别结果会出现较高的误判率。Lin和Wu利用DCT系数和SURF特征来对图像进行篡改鉴别,但这种方法的局限性很高,其只对JPEG图片有效[5]1086,对其他格式的图片失效,Zhang等人则利用相机特性的统计特征来检测图像是否经过篡改, 但是当篡改部分和原始图像来自同一台相机时,此算法失效[6]335。
本文给出了一种基于特征点的图像篡改鉴别算法,该算法首先计算图像的关键点位置与方向,并通过特征向量的形式描述关键点的相关特征,最后对特征向量进行匹配,通过匹配结果来判断档案图像是否遭到篡改。
一、SIFT 特征提取算法
SIFT特征由Lowe在1999年提出[7]1150,并于2004年进行了更深入地发展和完善[8]91,SIFT特征是图像的局部特征,该特征对平移、旋转、遮挡、噪声、尺度缩放和亮度变化等具有良好的鲁棒性,对视觉变化、仿射变换也保持了一定的稳定性。
1.尺度空间极值点检测。在连续的尺度空间中提取图像的极值点,可以保证极值点具有一定的尺度不变形,而高斯核是实现尺度变换的唯一线性核[9]225,因此SIFT算法利用高斯核对原始图像进行尺度变换,获得该图像在多尺度下的尺度空间,平滑时尺度因子越小表示图像被平滑的越小,越大表示图像被平滑的越大。
为了提高算法的效率,Lowe提出了在高斯差分尺度空间Do G(difference-of-Gaussian)中提取极值点。高斯差分尺度空间是由高斯尺度空间中两个相邻的尺度相减得到,在建立高斯金字塔的过程中,通过高斯滤波,可以获得连续尺度下的多组图像,其中每组图像都有多层。在每一组图像中,第s+1层图像的尺度是s层图像尺度的k倍。由于第o+1组图像的第1层是由第o组图像的第S-1层通过隔点采样生成的,这样既使得第o+1组图像的第s层是由第o组图像的第s层图像尺度的k的s次方倍,也保证了高斯金字塔尺度的连续性。由于对原始图像进行高斯平滑会导致图像丢失高频信息,因此在建立尺度空间前,需对原始图像扩展一倍,以保留原始图像信息,增加特征点的数量。
SIFT的特征点是由Do G尺度空间中的极值点组成,为了寻找Do G尺度空间中的极值点,每个像素都要与它同尺度的8个相邻点和上下相邻尺度对应的9×2个点相比较,以确保在尺度空间和二维图像空间都检测到极值点。由于每组图像的顶层和底层无法进行极值比较,因此需对每组图像的顶层继续用高斯滤波生成3幅图像,这样高斯金字塔的每一组有S+3层图像,Do G金字塔的每组有S+2层图像。
2.确定极值点的位置。由于Do G算子对噪声较敏感,且具有较强的边缘响应。因此,需要对检测到的极值点进行过滤,以剔除对比度较低的极值点以及不稳定的边缘点,保证特征点的稳定性。为了提高特征点的稳定性,对尺度空间函数进行曲线拟合,将Do G算子在尺度空间进行泰勒展开,计算出展开式在极值点处的函数值,若该函数值小于0.03,则保留该极值点,否则,剔除该极值点,实验结果表明该方法对剔除低对比度的不稳定极值点效果显著。由于Do G算子的极值在沿边缘的方向上有较大的主曲率,而在垂直边缘的方向有较小的主曲率,因此可以通过计算主曲率来剔除边缘处的极值点。主曲率可以通过计算在该点位置尺度的2×2的Hessian矩阵得到。
3.计算特征点的主方向。通过高斯尺度空间计算出的特征点具有尺度不变的性质,通过梯度直方图统计法,统计以特征点为中心,一定区域内的图像像素点对特征点方向所做的贡献,最终计算出的特征点方向具有旋转不变的性质。在高斯差分尺度空间中,每一层图像具有相同的尺度,要计算图像上的各像素点的梯度大小和梯度方向。在生成的梯度方向直方图中,梯度直方图的范围为0-360度,其中每10度一个柱子,半径为3×1.5×σ。以每个采样点的梯度大小为权值,累加到特征点邻域的梯度方向直方图中,最终选取梯度方向直方图中主峰值的方向最为特征点的主方向。为增强匹配的鲁棒性,在梯度直方图中,当存在另一个相当于主峰值80%能量的峰值时,则将这个方向作为该特征点的辅方向。
4.生成SIFT特征向量。对于每一个特征点,都需要用一个向量来描述其相关特征,使其具有一定的独特性。生成SIFT特征向量时,首先以特征点为中心,在其所在的尺度空间中去16×16的窗口,为保证特征点的方向不变性,以特征点的主方向为坐标轴,计算每个像素点的梯度大小和梯度方向。再在4×4的窗口内计算8个方向的梯度直方图,如图2所示,这样就形成了4×4×8=128维的SIFT特征向量。由于SIFT向量是通过对特征点周围图像区域分块,计算块梯度直方图所生成的,因此其具有独特性。最后,将SIFT特征向量归一化,使其具有对光照条件的不变性。
二、SIFT 特征向量的匹配
通过上述过程,已经得到了图像的SIFT特征向量,接下来需要对生成的SIFT特征向量进行特征匹配。针对特征向量的匹配,一般有两种方法,最容易的方法是穷举法。即依次计算样本集中每一个样本到输入实例点的距离,然后将计算出来的最小距离的点作为最近邻点。该方法虽然简单直白,但是当样本集很大时,它的缺点就暴露出来了。另一种方法是构建数据索引。因为实际数据一般都会呈现簇状的聚类形态,因此可以先建立数据索引,然后再进行快速匹配。而BBF(Best-Bin-First)最近邻查询算法中的K-d(K-dimension tree)树就是一种树结构索引方式。本文采用BBF最近邻查询算法对SIFT特征向量进行匹配,然后再用RANSAC算法剔除误匹配。
1.BBF(Best-Bin-First)算法。BBF最近邻查询算法是由Beis和Lowe在1997年的一篇文章中针对高维数据提出的一种近似算法,它是对K-d树最近邻域搜索算法进行了改进[10]1000。在K-d树最近邻域搜索算法中,为了能够找到结点在数据集合中的最近邻点,会进行回溯查找,即在未被访问过的且与结点所在的超平面相交的子树分支中查找可能存在的最近邻点。但是随着数据维度的增大,与结点所在的超平面相交的子树分支就会增加,这就意味着需要回溯判断的子树分支就会增多,从而查找效率便会下降很大。而BBF算法则是通过设定最大回溯次数方法来避免由于维度过大而导致的查找效率下降的问题。由于查找结果的精度很大程度上取决于数据的分布和回溯次数,为了使算法的查找结果的精度不会因限制了回溯的次数而下降,BBF算法将子树分支上的结点按与查询点之间距离进行排序,构成优先级队列。回溯检查总是从优先级最高(Best Bin),即距离最短的子树结点开始,直到子树结点的叶子结点,并记录下查询点与该叶子结点的距离。这样循环下去,直到达到最大的回溯次数或优先级队列为空。最后得到的距离最短的叶子结点即为所要找的邻域点。
2.剔除误匹配。通过BBF最近邻查询算法获得的特征匹配可能会存在部分的误匹配,本文采用RANSAC算法来剔除误匹配,以提高图像篡改鉴别的准确率。RANSAC(Random Sample Consensus随机抽样一致)最早由Fischler和Bolles于1981年提出[11]381。该算法的基本假设是,样本中包含正确数据和异常数据,给定一组正确的数据,存在可以计算出符合这些数据的模型参数的方法,且该模型能够解释或适用于样本中的正确数据。本文通过随机选取匹配结果中的三个匹配对进行组合,计算出仿射变换系数。再通过计算出的仿射变换系数去检测其他的匹配对,若某个仿射系数适应的匹配对最多,则认为该仿射系数是所需的模型参数,而能够符合该仿射系数的匹配对即为正确匹配,其他为误匹配,应当剔除。
三、实验结果与分析
本文选取了2007年英国文化、新闻和体育大臣James.Purnell合照造假事件中的图像来进行实验。其中图3(a)为5名嘉宾的真实合影照,图3(b)Purnell在同一地点的单人照,图3(c)为篡改后的“合影照”。根据本文提到的方法,首先分别对Purnell在同一地点的单人照和篡改后的“合影照”提取SIFT特征向量。结果显示,在单人照中提取了79个特征点“,合影照”中提取了250个特征点。随后采用BBF最近邻查询算法对提取到的特征向量进行匹配,共得到22个匹配对,如图4所示。通过分析,可以看到实验结果中存在明显的误匹配。采用RANSAC算法,可以剔除这些误匹配,如图5所示,最终获得10对正确的匹配对。
根据图5所示的实验结果,可以看出,两张图片上的Purnell存在大量的匹配对,而在两张图片中存在大量相似的地方如背景,地面等,但这些地方没有匹配对,由此可以排除匹配对是由于人物相似产生的。从而可以判定“合影照”中的Purnell是从图3(a)中复制过来的“,合影照”是经过篡改得来。
由于本算法是基于SIFT特征来对图像篡改进行鉴别,因此其对图像的尺度、旋转、光照条件等具有良好的鲁棒性。同时,本算法采用BBF最近邻查询算法来对SIFT特征点进行匹配,解决了原SIFT算法效率低的问题,提升了算法的效率。最后通过RANSAC算法对匹配对进行检测,剔除误匹配,提升了算法的准确率。
摘要：为了提高算法的准确性,本文用RANSAC算法剔除误匹配。最后根据匹配结果判断档案图像是否经过篡改。实验结果表明,本算法具有较好的鲁棒性。
立体匹配算法的比较 篇7
局部匹配算法主要包括区域匹配法、特征法。
1.1 区域匹配算法原理
区域匹配算法是以基准图像中待匹配点为中心像素创建一个大小为m×n窗口, 由该窗口内的像素灰度值来表征该像素。在第二幅图像中, 沿极线在视差搜索范围内取出与基准点同样大小的邻域, 依次与匹配点的窗口进行比较, 其最大相似性对应的点就是最佳匹配。
区域匹配算法的重点是匹配代价的计算和匹配代价的累积。匹配代价计算就是选取相似性测度函数, 而匹配代价的累积体现在支撑窗口的选取上。几乎所有的区域匹配算法都要关注这两个问题:
1) 选取相似性测度函数。常用的相似性测度函数如下:
(1) 最小绝对差算法SAD
(2) 最小平方差算法SSD
2) 选取支撑窗口大小。一方面窗口的尺寸要尽量的大, 以便为可靠的匹配包容足够的灰度变化;另一方面, 窗口太大则包含视差的较大变化, 则会因左右图像上不同的投影畸变, 使得匹配位置不准确。
1.2 区域匹配实验结果
分别用SAD相似性测度函数对Tsukuba匹配源图像对进行匹配, 采用3×3、5×5两种窗口。实验结果如图1.1所示:
2. 全局匹配算法
大部分全局算法基于能量最小化的思想, 寻找视差函数d, 使全局能量最小化。本文对一种常用的全局算法--动态规划法做重点研究, 与区域匹配算法进行比较。
2.1 动态规划算法
动态规划匹配算法在外极线单调顺序约束下寻找视差空间图像 (DSI) 上的最小代价路径。最优路径的代价是所有子路径的和, 这些子路径所经过点的匹配代价由相似性度量因子决定。
2.2 动态规划实验结果
针对Birchfield的动态规划算法, 所产生的视差图如图2.1所示。
3. 总结
基于区域匹配中匹配窗口较小时, 误匹配较多, 而窗口较大时, 边缘处又显得很模糊, 所以窗口大小与形状必须具有较强的适应性。动态规划是对一条扫描线计算全局匹配代价, 提高了匹配的准确性。但是动态规划有一个很大的局限性, 它缺乏对水平连续性约束和垂直连续性约束的融合。从匹配性能上看, 动态规划算法在边缘不连续区域有较高的误匹配, 而在其它区域的误匹配百分比都较基于区域匹配算法低;从匹配速度上看, 基于区域匹配相对于全局匹配较小的计算量, 使其匹配速度明显加快, 更适合对实时性要求较高的应用。
摘要：立体匹配是立体视觉中的关键技术之一, 能否有效地解决该问题影响着立体视觉的发展。本文研究了相似性测度函数和邻域窗口对基于区域匹配算法的影响, 实现了具有代表性的全局匹配算法——动态规划, 并与基于区域匹配算法进行了比较。
关键词：立体匹配,基于区域的匹配算法,动态规划
参考文献
[1]张广军.机器视觉[M].北京:科学出版社, 2005.