点模式指纹匹配算法研究与实现.pdf
- 文档编号:3437908
- 上传时间:2023-05-05
- 格式:PDF
- 页数:4
- 大小:126.95KB
点模式指纹匹配算法研究与实现.pdf
《点模式指纹匹配算法研究与实现.pdf》由会员分享,可在线阅读,更多相关《点模式指纹匹配算法研究与实现.pdf(4页珍藏版)》请在冰点文库上搜索。
第33卷第2期电子科技大学学报Vol.33No.22004年4月JournalofUESTofChinaApr.2004点模式指纹匹配算法研究与实现廖阔,杨万麟(电子科技大学电子工程学院成都610054)【摘要】指纹匹配是实现指纹识别的重要环节,针对如何提高识别率、减少算法复杂度,介绍了一种点模式的指纹匹配算法。
其优点是:
将匹配分为两步进行,减少了拒判时间;初匹配利用了细节点间的局部结构关系,既克服了图像的平移和旋转也得到了更精确的坐标校准参数;二次匹配阶段,整合多种判决条件作为识别的依据,提高了识别率。
其实验结果表明,该算法复杂度低,识别率较高,有较强实用价值。
关键词指纹识别;细节点;特征点集;局部向量;坐标校准;匹配中图分类号TP391.4文献标识码AResearchandImplementationofFingerprintMatchingMethodofMinutiaeLiaoKuo,YangWanlin(SchoolofElectronicEngineering,UESTCofChinaChengdu610054)AbstractThepurposeofthispaperistointroduceafingerprintmatchingapproachbasedonminutiae.Inthispaper,weusedthestructralinvarianceoflocalminutiaetofoundlocalvectors,thenintegratethebestmatchingpointanditsneighbourpointstogetmoreaccurateparametersofalignmentadjustment,atlast,weintegratemulti-discriminanttocompletefingerprintmatching.Theexperimentdatashowthat,ourmethodhaveachievedahigheraccuracy.Keywordsidentificationoffingerprint;minutiae;minutiaeset;localvector;alignmentadjustment;matching指纹的唯一性和终生不变性使指纹识别成为现在应用最广泛的生物识别技术。
一个自动指纹识别系统的工作流程主要有四步:
1)指纹图像的采集;2)预处理;3)特征提取;4)特征匹配。
其中,特征匹配是识别系统的关键环节,匹配算法的好坏直接影响识别的性能、速度和效率。
目前最常用的匹配方法是基于特征点的点模式匹配。
美国联邦调查局提出使用两种类型的特征点:
末梢点和分叉点,如图1所示。
通过搜索指纹图上的特征点,将指纹图像转化为由若干末梢点和分叉点所组成的点集,指纹匹配问题也相应地转变为寻找点集间的相似度(即点集匹配)的问题。
但即使是同一枚指纹,两次按捺也必然存在位置、力量和采集时噪声的变化,因此得到的特征点集间也必然存在一定的平移、旋转和局部变形。
所以,如何准确的获得点集间的坐标校准参数(平移、旋转参数)是准确识别的关键。
1匹配算法为解决以上问题,将匹配分为两个阶段:
1)初匹配阶段:
利用相邻点间的结构关系建立局部特征向量收稿日期:
20030908作者简介:
廖阔(1978),女,硕士生,主要从事模式识别技术方面的研究.末梢点分叉点图1指纹特征点类型图1指纹特征点类型第2期廖阔等:
点模式指纹匹配算法研究与实现155进行初步匹配13。
这一步可以比较准确的找到两个指纹点集间的坐标校准参数(即:
平移和旋转参数)。
这在某种程度上是模仿指纹专家手工匹配指纹的操作,专家们通过寻找指纹上一些局部特征的相对位置来对两枚指纹进行重新定位。
2)二次匹配阶段:
以初匹配的最优点对为参考,对所有特征点进行全局坐标调整,并转化到极坐标系表示。
在判断两点是否匹配时使用了可变大小的限界盒4,解决了一定范围内的变形问题。
最后整合多种判决门限完成全局特征匹配。
1.1初匹配初匹配不但可以减少拒判时间,而且可以准确获得对点集进行重新定位的校准参考点,该环节分两步实现。
1.1.1建立局部特征向量经过特征提取得到指纹图像上的所有分叉点和末梢点,每一个特征点记录了三方面信息:
点的位置(x,y);点的类型s(分叉点,末梢点);该点所在脊线的方向角度0,360。
在指纹图像发生平移、旋转或局部变形时,特征点的绝对位置信息会有很大变化。
但相邻点间的距离、穿过的脊线数目和相对角度等却不会有太大的改变。
因此,利用特征点间的脊线数目、方向差等结构关系建立局部特征向量,可以很好的解决平移及旋转问题。
对每个特征点,以该点为中心建立一个用于匹配的局部邻域特征向量,结构如图2所示。
从图中看出,取与该中心点距离大于R(这里R=10)的最近5个点),(54321nnnnn作为其邻域特征点,距离小于等于R的点(如图中a、b点)则不取。
这5个邻域点和该中心点一起用来构造局部特征向量。
每个局部特征向量记录的信息及其存储结构如图3所示。
ab邻域特征点半径R局部中心点C距离Dn3n4n5n1n2中心特征点信息),(syx第一个邻域特征点信息n11点类型2与中心点的方向差3与中心点的距离4到中心点的脊线数目第五个邻域特征点信息n51点类型2与中心点的方向差3与中心点的距离4到中心点的脊线数目图2局部特征向量结构模型图3局部特征向量存储模型1.1.2特征向量匹配假设有待识别指纹A和模版库中的任意指纹B,用点集),(,),(1111AMAMAMAMAAAAsyxsyx=A表示指纹A上的M个特征点,用点集),(,),(1111BNBMBNBNBBBBsyxsyx=B表示指纹B上的N个特征点。
则对指纹A上的每个特征点建立局部特征向量可得到一个M维的局部特征向量组,对指纹B可得到一个N维的局部特征向量组。
初匹配的过程就是将指纹A的M维向量组和指纹B的N维向量组进行比较:
把A中每一个特征点iA(i=1,2,M)的局部特征向量与B中每一个特征点jB(j=1,2,N)的局部特征向量进行一一匹配,相应的匹配分数记录在矩阵NMScore中。
匹配分数的计算方法为:
若iA,jB向量的中心点类型不一致,即BjAiss,则0=jiScore;若iA,jB向量的中心点类型一致,即BjAiss=,且其5个邻域分量中有n个邻域点匹配,则nji=Score(1n5)。
完成匹配后,在矩阵Score的每一行中标记出匹配分数最大且不为零的元素,这些元素的位置可以确立特征点iA与jB的一一对应,其分数总和称为总匹配分数记作ABG。
这里使用相对匹配分数NMGGSABAB=100作为初匹配的判决条件4。
为减少据判时间,设置初匹配门限,即最高匹配分数Smax和最低匹配分数Smin。
若SSmax则直接认为A、B来自同一指纹。
初匹配阶段主要完成了两个任务:
1)标记出匹配矩阵Score中分数值最大的元素qpScore,在第二电子科技大学学报第33卷156阶段的匹配中将以指纹A的第p个点pA和B的第q个点qB作为对两枚指纹进行全局坐标校准的最佳参考点。
2)直接剔除相差较大的输入指纹图像,缩短匹配的拒绝时间,从整体上加快系统的识别速度。
1.2二次匹配1.2.1点集的坐标调整由于点集的坐标校准涉及大量的坐标旋转,而在极坐标系统中可以方便的实现坐标旋转且易于刻画图像的局部变形,所以这里采用基于极坐标系统的坐标校准方法。
由初匹配的结果:
以pA为极坐标中心极点,对点集A进行坐标校准,得到极坐标系统下新的点集A;以qB为极坐标中心点,对点集B进行坐标校准,得到新的点集B。
极坐标变换公式为()()+=cttcctctctctttttsxxyyyyxxserarctan22
(1)式中),(ccccsyx为中心点坐标,),(ttttsyx为待转换的细节点坐标,),(ttttser分别为坐标转换后该点的极径、极角、点类型、该点所在脊线与中心点所在脊线的方向差。
式
(1)在计算每个特征点的极角te和方向差t时仅使用了中心极点的信息,但如果极点所在区域发生了小的局部变形,就会使以该点为中心的坐标变换在全局范围内出现一个很大的变形。
因此,为避免偶然误差,需要对式
(1)中角度te和t的计算进行修正:
将中心极点和5个邻域点的角度一起作为角度调整时的修正参数,该修正参数为5个对应邻域点角度差的平均值,将式
(1)中的te、t再减去该平均值即可。
1.2.2全局匹配坐标校准后得到的点集记为()MAAA=,21A、()NBBB=,21B,将A中的每个点与B中的每个点进行基于限界盒的一一匹配,建立NM维的匹配度矩阵。
同一次匹配中的方法类似,为避免一点与多点相配的情况出现,采取以匹配度由高到低的原则建立iA与jB的一一对应。
指纹图像不可避免的存在一定范围的局部变形,这是一种非线性形变,一般在变形的中心区域内变化较大,然后非线性地向外扩张。
因此,在判断平面中两点是否匹配时,还需要考虑一定范围内的变形,本算法引入限界盒的概念来解决这个问题。
限界盒就象是放在指纹特征点上的一个盒子,限界盒的大小一般由极角和极半径来刻画,这里定义其大小为可变化的,如图4所示。
从图中可看出,限界盒的大小由当前特征点和中心点间的距离来决定,在离中心点近的地方极半径应该变小,极角变大;相反,在离中心点远的地方应该极半径变大,极角变小。
因此,匹配过程中,当两个特征点iA和jB落在同一个限界盒中时则认为这两个点匹配成功。
1.2.3匹配的判决条件在判断两枚指纹的匹配程度时可以有不同的衡量依据。
文献1,57中提到:
如果两枚指纹有12个以上的点对互相匹配,即可认为两者来自同一个手指。
而实际的输入指纹图像由于噪声和其他干扰因素的影响,很难达到这个判决门限。
因此,本算法在计算匹配度矩阵时统计了以下四种信息作为判决条件:
1)成功匹配的点对数;2)配对点数和相应指纹特征点总数的比值;3)各匹配点对的差异分数总和(方向差和距离差的加权和),显然,此分数越低匹配程度越高;4)差异分数总和与相应指纹特征点总数的比值。
判决时采用将以上四种条件相结合的复合判决方法,为每个条件各定义一个阀值。
各条件间为并列关系,当14项信息中任意一项记录的值满足预定的阀值时,则认为两者匹配。
实验结果表明:
使用多判决条件的全局匹配方法,提高了识别率。
极角极半径极半径极角图4限界盒的定义第2期廖阔等:
点模式指纹匹配算法研究与实现1572实验结果一个自动指纹识别系统的性能评价参数有:
识别速度,正确率CR(correctrate),误识率FAR(falseacceptedrate),拒识率FRR(falserejectrate)。
其计算公式为匹配总次数不该识别而识别的次数=FAR;匹配总次数数该识别而没有识别的次=FRR;)(1FRRFARCR+=;
(2)FAR和FRR有相反的变化方向,当FAR增大时FRR会减小。
对于不同的系统需求,可通过改变判决阀值来满足。
实验中,对指纹识别竞赛FVC2000提供的指纹数据库DB1中的80枚指纹图像进行了7980次匹配测试。
实验结果与参考文献中给出的结果进行了比较,比较结果如表1所示。
从表中得知实验1为文献1中给出的结果,实验2为文献2中给出的结果,试验3为本算法的结果。
其结果表明,在误识率都为0的情况下,本算法的拒识率降低,正确识别率较文献1,2中使用的算法有所提高。
表1实验结果比较实验结果误识率FAR/()拒识率FRR/()正确率CR/()实验1实验2实验30002.103.331.2097.9096.6798.803结论本文介绍了一种基于点模式的指纹特征匹配算法的研究与实现。
该算法改进了文献1,2中使用的建立局部特征向量进行特征匹配的方法,其优势为:
利用相邻点的角度关系对原有的坐标调整方案进行修正,得到更加准确的坐标角度校准参数;使用可变大小的限界盒作为点匹配的标准,在二次匹配中解决了一定的局部变形问题;并且利用了多种判决条件相综合的识别模式,在一定程度上降低了拒识率,提高了识别性能。
在指纹出现大量伪特征点和大的变形时,该算法的识别率会有所下降,所以提高抗噪和抗干扰能力,是该算法下一步改进的重点。
参考文献1张洪光,刘雪梅.指纹识别中的一种局部向量匹配算法J.计算机工程,2002,28(4):
106-1082李志敏,彭志刚.基于动态全局特征的指纹匹配算法的研究J.沈阳化工学院学报,2000,14(4):
292-2953ChenZ,KuoCH.Atoplogy-basedmatching-algorithmfingerprintauthenticationJ.IEEEInternationalCarhananConferenceonSecurityTechnology,1991,31
(2):
84-874罗西平,田捷.自动指纹识别中的图像增强和细节匹配算法J.软件学报,2002,13(5):
942-9565LinH,AnilJ.IntegratingfacesandfingerprintsforpersonalidentificationJ.IEEETrans.PAMI,1998,20(12):
1295-13076姚文庆,肖雪静.指纹特征匹配方法的研究与实现J.天津大学学报,1992,4(4):
48-557DineshPM,EamKT.AnautomatedmatchingtechniqueforfingerprintidentificationJ.FirstInternationalConferenceonKnowledge-BasedIntelligentElectronicSystems,1997,5
(1):
21-23编辑刘文珍
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模式 指纹 匹配 算法 研究 实现