（计算机应用技术专业论文）指纹识别算法研究.pdf

指纹蕾u 甜舅- 孛研究 指纹识别算法研究 摘要 指纹识别是基于生物特征的身份认证方式之一，虽然指纹识别领域已 有许多研究成果，但随着社会对指纹识别的迫切需要，以及指纹识别技术 在实际应用和测试中表现出的不足，近年来，许多研究机构都在十分活跃 地进一步深入研究指纹识别领域的各种关键技术，以提高指纹识别的性能 和解决实际应用中的问题，从而加速指纹识别技术的普及。本文对指纹识 别领域的主要关键技术进行了深入研究，主要包括指纹图像的预处理技术、 指纹特征提取和匹配技术。 本文的主要工作如下： 1 、针对纹线较宽的指纹和含有较多汗孔的低质量指纹图像，提出了 种改进的基于g a b o r 滤波的指纹增强算法。首先对纹线方向提取方法进行了 改进，获得了较准确的方向图；然后对纹线频率的提取方法进行了改进， 有效地避免了g a b o r 滤波后在脊线中留下伪纹线和小孔的问题。实验结果表 明，该算法对低质量指纹图像具有显著的增强效果。 2 、提出一种改进的索引表细化算法，该法利用模板比较对分叉点细化 结果进行修正，从而解决了现有索引表细化算法在处理指纹图像后存在的 绞线分叉点处细化不彻底的问题，有效去除了伪特征点。细化后的指纹骨 架在纹线中心线。该方法运算速度快且易于实现。 3 、对指纹特征提取和指纹匹配算法进行7 研究。首先采用交叉数算法 对指纹进行特征提取，然后采用基于编辑距离原理的指纹细节特征匹配方 法对指纹库进行了实验，实验结果表明该方法能够有效的进行指纹特征提 取和指纹匹配。 关键词：指纹g a b o r 滤波细化特征提取指纹匹配 h ，1 曩，“斡马k b 孽啦截汶指釉报是l 囊b 去研究 r e s e a r c ho nm e t h o do fn n g e r p r l n t r e c o g n i t i o n a b s t r a c t f i n g e r p r i n tr e c o g n i t i o ni so n eo f t h et e c h n o l o g i e so fb i o m e t r i cr e c o g n i t i o n i tp l a y sam o r ea n dm o r ei m p o r t a n tr o l ei nm a n yr e g i o n $ a l t h o u g h ，f i n g e r p r i n t r e c o g n i t i o nh a sb e e ne x t e n s i v e l ys t u d i e da n dm a n ya d v a n c e sh a v eb e e nm a d e0 1 1 i t , t h e r e a r es t i l l p r o b l e m s w h i c ha r es h o w ni n a c t u a l a p p l i c a t i o n sa n d e v a l u a t i o n s i nr e c e n ty e a r s ，m a n ya c a d e m i e sa n di n d u s t r i e sh a v eb e e nm a k i n g a l li n - d e p t hr e s e a r c ho nf i n g e r p r i n tr e c o g n i t i o nt e c h n o l o g i e s t h i st h e s i sh a s s t u d i e dt h em a i nt e c h n o l o g i e so ff i n g e r p r i n tr e c o g n i t i o n ，m a i n l yi n c l u d i n g f i n g e r p r i n tp r e t r e a t m e n t f e a t l l r ee x t r a c t i o na n df i n g e r p r i n tm a t c h i n g 1 r i 坞m a i nc o n t r i b u t i o nw o e sa r e 勰f o l l o w s ： 1 a ni m p r o v e df i n g e r p r i n te n h a n c e m e n ta l g o r i t h mb a s e do ng a b o rf i l t e ri s p r o p o s e d am e t h o df o rr i d g eo r i e n t a t i o na c q u i r e m e n ti si m p r o v e d ，a n dt h e o r i e n t a t i o nm a pi sm o r ea c c u r a t e 。am e t h o df o rr i d g ef r e q u e n c ya c q u i r e m e n ti s i m p r o v e d , a n dt h ef a l s er i d g el i n e sa r ea v o i d e d e x p e r i m e mr e s u l t si n d i c a t et h a t t h em e t h o dh a sd r a m a t i ce f f e c tt ol o wq u a l i t yf i n g e r p r i n ti m a g e s 2 a ni m p r o v e di n d e xt a b l ef i n g e r p r i n tt h i m f i n ga l g o r i t h mi sp r o p o s e d t h e 1 1 1 广西大掣唾士掣q 电地i 文指纹讽剔算法研究 n o n - t h o r o u g ht h i n n i n gb i f u r c a t i o n sa r et h i n n e dt h o r o u g h l y t h ef a l c h a r a c t e r p o i n t sa r ee f f e c t i v e l yr e m o v e d t h ef i n g e r p r i n ts k e l e t o ni si nt h ec e n t r eo fr i d g e l i n e s i ti sf a s t e ra n de a s i e rt oi m p l e m e n t 3 t h ea l g o r i t h m so ff i n g e r p r i n tf e a z ee x t r a c t i o na n df m g e r p r i n tm a t c h i n g a r er e s e a r c h e d t h ec r o s sn u m b e ra l g o r i t h mi su s e df o rf i n g e r p r i n tf e a t u r e e x t r a c t i o n t h ef i n g e r p r i n tm a t c h i n gm e t h o db a s e do ne d i td i s t a n c ei su s e df o r f m g e r p f i n tm a t c h i n g e x p e r i m e n tr e s u l t si n d i c a t et h a tt h em e t h o d sa r ee f f e c t i v e f o rf i n g e r p r i n tf e a t u r ee x t r a c t i o na n df i n g e r p r i n tm a t c h i n g k e y w o r d s ：f i n g e r p r i n t ；g a b o rf i l t e r ；t h i n n i n g ；f e a t u r ee x t r a c t i o n ；f i n g e r p r i n t m a t c h i n g ，西大掣u 曩吐叫阻位鼬曙旨纹讽嚣_ 算法研究 1 1 课题研究的背景及意义 第一章绪论 日常生活中的许多场合都需要进行身份认证：比如登录操作系统，使用某些应用软 件，登录网络站点，到银行取钱，鉴别疑犯，进入军事要地等。 传统的身份认证方式包括基于知识( 如密码、口令) 的身份认证和基于令牌( 如钥匙、 身份证) 的身份认证【”。传统的身份认证方式存在许多缺点，密码和口令存在容易忘记、 容易攻击、容易泄漏等问题，钥匙和身份证等存在容易被盗、容易丢失、容易伪造、容 易冒用等问题。传统的身份认证方式的这些缺点给我们的生活带来了诸多不便和很多安 全问题。比如口令的盗取，舜j 人只要留意用户在计算机终端前输入口令时的击键动作就 可以知道用户的口令，甚至可以通过你的生日、年龄、姓名或者其他一些信息猜出你的 口令，因为许多人使用自己的生日等信息作为口令。尽管现行系统通过要求用户及时改 变他们的口令来防止盗用口令的行为，但这种方法不但增加了用户的记忆负担，也不能 从根本上解决问题。基于令牌的身份认证不要求用户费力地记住口令，但令牌存在容易 丢失、容易被盗、容易伪造，如证件的伪造和盗用、不正当的转借等。一些罪犯通过伪 造证件进入机密场所以窃取机密信息，有的罪犯伪造签证和护照非法入境或移民，这是 因为传统的证件使用了易于伪造、未经加密的纸制证件。因此，必须寻找更加方便、更 加安全可靠的身份认证方式。 基于生物特征的身份认证方式可以克服传统身份认证方式的许多缺点。每个人都具 有多种生物特征。生物特征包括生理特征和行为特征，生理特征是指与生俱来的特征， 如指纹、虹膜、d n a 等。行为特征是指后天习惯形成的特征，如步态、笔迹等。每个 人都拥有许多种生物特征，生物特征不会被忘记和丢失。对于每一种生物特征的性质， 可以用一些参数来描述，包括： ( 1 ) 普遍性，是否每个人都具有这种特征。 ( 2 ) 唯一性，是否任何两个人的这种特征都不同： ( 3 ) 恒久性，是否终生不变。 ( 4 ) 可采集性，是否容易采集。 ( 5 ) 性能，识别的正确性如何。 ( 6 ) 接受程度，用户是否愿意接受这种身份认证方式。 ( 7 ) 防欺骗性，防止环境欺骗的能力。 。 表l l ”铡出了常用生物特征的参数比较，每个参数分h i g i l ，m e d i u m 和l o w 三个 描劈口凡捌奢：寅l 研究 等级，其中h i 曲最好，l o w 最差。如果根据性能等级给每个参数打分：h i 曲为3 分， m e d i u m 为2 分，l o w 为1 分。各生物特征总的得分分别为：人脸1 4 分、指纹1 8 分、 手形1 5 分、虹膜1 8 分、视网膜1 6 分、签名1 1 分、声音1 1 分。指纹和虹膜的得分最 高，而虹膜的用户接受程度为l o w ，指纹中没有等级为l o w 的参数。可见，众多生物 特征中指纹是较为理想的一种用于身份认证的生物特征。在各种基于生物特征的身份认 证方法中，指纹识别所占有的市场份额最大，在国际生物识别组织i b g ( i n t e m a t i o n a l b i o m e t r i cc r o u p ，简写为m g ) 【2 】对2 0 0 4 年各种生物特征的市场份额的比较报告中，指 纹识别的市场份额为4 8 。同时，基于生物特征的身份认证方法的市场收入额在逐年上 升，可见社会越来越需要基于生物特征的身份认证，尤其是基于指纹的身份认证方式。 表1 - 1 常用生物特征的比较 t a b l e1 - 1c o m p a r i s o no f b i o m e u i cc h a “k ；0 盯 生物特征普遍性独特性稳定性可采集性性能接受程度防欺骗性 人脸 h i g l l l o wm e d i u m h i g i l l o w h i g l l l o w 指纹m e d i u m 1 t i g hh i g h m e d i u m h i g h m e d i u m h i g h 手形m e d i m nm e d i u mm e d i u m h i g h m e d i u mm e d i u mm e a i u m 虹膜h 曲 h i g hh j g l l m e d i u m h i g i l l o w h i g l 视网膜 h i g l lh i g i i m e d i u ml o w h i g i l l o w h i g l l 签名l o wl o wl o w h i g l l l o w h i 曲 l o w 声音 m e d i ml o wl o wm e x l i u ml o w h i g l l l o w 计算机的出现使指纹识别进入了自动化阶段。近些年来，国内外自动指纹识别技术 已取得了许多进展1 3 l 。同时许多人存在一个错误观念，认为自动指纹识别技术中的问题 已经得到彻底解决。然而事实恰恰相反，国际指纹验证竞赛f v c ( f i n g e r p r i mv e d f i c a t i o n c o m p e t i t i o n ，简写为f v c ) 1 4 】删的测试结果表明，自动指纹识别仍有许多问题等待解决， 仍然是一个具有挑战性的重要的研究课题。f v c 从2 0 0 0 年开始每两年举行一次i q _ 唧， 参赛算法中许多都代表着世界领先的算法。从比赛结果来看，指纹识别算法的正确率远 远低于市场上所宣传的指纹识别产品的正确率；正确率较高的算法所需的运算时间也相 对较长，消耗的存储空间较多，有些算法虽然能达到较高的正确率，但消耗的系统时间、 空间资源在实际的应用中是难以让人接受的；低质量指纹图像的匹配还是一个挑战性的 难题；扭曲指纹的识别问题还有待进一步解决 4 h 9 。 目前的自动指纹识别系统的正确率还远远达不到指纹鉴别专家用肉眼进行识别的 正确率，因为自动识别系统难以实现用人眼进行识别时所用的复杂模型，人眼可以从低 质量的指纹图像中准确提取特征，而自动识别系统在低质量图像中往往提取错误特征或 无法提取特征。可见，自动指纹识别技术的研究仍然是具有挑战性的研究课题。 由于社会对指纹识别有着日益迫切的需求，由于指纹识别领域仍然存在许多难题， 近年来，指纹识别领域的研究十分活跃。与指纹识别有关的国内外活动有国际指纹验证 比赛f v c ，国际生物认证会议i c b a ( i n t e m a t i o n a lc o n f e r e n c eo nb i o m e t r i ea u t h e n t i c a t i o n 。 2 指纹母u 鲫算法研究 简写为i c b a ) ，中国生物识别学术会议c c b r ( c h i n c s ec o n f e r e n c e o l lb i o m c t r i c r e c o g n i t i o n ，简写为c c b r ) ，国际模式识别会议i c p r ( i n t c m a t i o n a lc o n f e r e n c eo np a t t e r n r e c o g n i t i o n ，简写为i c p r ) ，教育部还特别在2 0 0 4 年举办了一个生物识别研讨班。目前 正致力于研究指纹识别技术的学术机构和工业机构有许多，学术界有中科院自动化所、 清华大学、北京邮电大学、南京大学、武汉大学、香港理工大学、密歇根州立大学( 美 国) 、波伦亚大学( 意大利) 、南洋科技大学( 新加坡) 、t w e n t e 大学( 荷兰) 等：工业界有汉 王( 中国) ，m i a x i sb i o m e t r i c s ( 中国) 、b i o s c r i p t ( 加拿大) 、n e u r o t e c h n o l o g i j a ( 立陶宛) 、s i e m e n s a g ( 德国) 、s a g e m ( 法国) 、s o n d a ( 俄罗斯) 、o e v a r i u s ( 俄罗斯) 、s u p r e m a ( 韩国) 等。 1 2 国内外研究现状 日前，国外从事指纹识别研究的公司，学校，科研机构共有2 0 0 多家i l ”。其中，较 为著名的公司有：i b m ，i n t e l ，n e c ，i d e n t i x ，d i g i t a l p c r s o n a ，韩国现代，朝鲜培富士 等。学校有：加州理工学院，密歇根州立大学模式识别与图像处理实验室，意大利b o l o g n a 大学特征识别系统实验室等。研究机构有：美国国家标准局视觉图像处理研究组，m m 沃特生研究中心等。这些国外公司、研究机构在指纹的采集、图像处理、识别、比对等 方面的技术已经比较成熟。各种相应的产品也已投放市场多年。 国内从上个世纪8 0 年代初期开始研究指纹自动识别技术。从事指纹识别的研究机 构有：北京大学信息中心，清华大学自动化系，北京邮电大学，中科院，长春光机所等。 从事自动指纹识别系统开发的公司有：西安青松，北京中控，厦门宝利铬，北京培富士 等。其中部分公司拥有自主知识产权的技术和产品。 目前指纹识别软件系统的研究主要包括以下几个方面： 1 2 1 指纹图像预处理 常用的图像预处理包括了三个方面：增强、二值化与细化 1 图像增强 数字图像处理中一些通用的图像增强方法【b l 如均值滤波、低通滤波、边缘增强等对 指纹图像的增强效果不理想，这是因为这些方法主要针对图像中的随机噪声，而模糊指 纹图像中的指纹纹线缺陷属于结构性噪声。 理想的指纹图像由脊线和谷线交替构成，脊线和谷线粗细均匀1 1 0 1 。除了在细节点、 奇异点等区域出现不规则形状外，在大部分区域，脊线之间和谷线之间互相平行，且呈 现连续的、方向平缓变化的曲线形态。当指纹图像质量较差时，指纹纹线不再具有上述 性状。然而对质量较差的指纹图像，指纹专家仍然能定位出其中的细节点和判断指纹的 类型，这是因为他们在观察时依据了一些重要的视觉线索，如局部纹线方向、纹线的连 续性、纹线的走势等等，这些特性反映了指纹纹线的结构。受此启发，人们利用这些视 指纹识嚣蚂| 法习n 电 觉线索设计出很多专门针对指纹图像的增强方法。 很多指纹增强算法对细化指纹周像进行增强1 1 4 】1 1 5 j 。这类方法的基本做法是在对原始 灰度指纹图像用低通滤波、直方图变换等通用图像增强方法进行处理后，依次进行二值 化和细化处理，得到细化指纹纹线，然后通过对细化纹线拓扑结构的分析，结合指纹纹 线的方向、纹线之间的距离等特性，修正细化纹线的结构。这种方式的根本缺陷是二值 化和细化处理不仅会损失很多有用的图像信息，而且也会带来很多新的误差，从而在此 基础上所恢复的指纹纹线结构可能不能反映指纹的原始面貌。 还有一些算法是在原始灰度指纹图像上进行指纹增科1 6 1 1 7 g 明1 1 9 1 1 2 0 1 。指纹图像由脊 线和谷线交替构成，理想情况下，指纹图像局部区域中的指纹纹线形成一个具有固定频 率和方向的平面正弦波。基于这一特性，人们提出了采用具有方向和频率选择特性的带 通滤波器进行指纹增强处理的思想。与基于细化纹线增强方法相比，这类方法具有较好 的效果。下面对采用这种思想的几种方法进行简要介绍。 s h e r l o c k 等i ”1 的方法利用b u t t e r w o r t h 带通滤波器和一种角度选择滤波器的组合来 构造滤波器，滤波器的主要参数有中心频率、中心方向、频率通带大小和方向通带大小。 滤波处理在频域进行。该方法首先选择1 6 个均匀分布的中心方向，用以它们所确定的 1 6 个滤波器分别对原始图像进行滤波，得到若干幅滤波后指纹图像。由于这些滤波器的 频率通带设置较大，从而不必构造不同中心频率的滤波器。然后采用方向灰度投影法估 计每个像素点处的纹线方向，并根据方向图求出奇异点位置。对每个像素点，选择若干 滤波方向与该像素点方向接近的滤波后图像，以这些图像中对应像素点的加权平均值作 为该像素点最终增强结果。所选滤波后图像的数目与该像素点与奇异点的距离有关，与 奇异点越近，其方向性越差，需选用较多滤波后图像，反之，距奇异点越远，其方向性 越好，故只需选用较少的滤波后图像进行组合，这样做的实质是根据像素点处方向性强 弱调整滤波器的方向通带大小。 k a m e i 等l ”j 方法的滤波处理也是在频域进行。滤波器形式上为两个高斯带通滤波器 的乘积，它们分别对方向和频率进行选择。该方法首先用若干不同中心频率和中心方向 的滤波器对原始图像进行滤波，得到若干滤波后图像。然后从这些滤波后图像确定每个 像素点增强后的值，与s h e r l o c k 等根据像素点方向进行滤波后图像选择的方法不同，该 方法搜索一种使增强后图像的方向连续性最好的增强像素点选取组合方法，增强图像中 像素点的方向为它所来自的滤波后图像所对应的滤波器的方向。方向连续性通过准则函 数度量，利用贪婪算法搜索使准贝l j 函数最小化的组合方式。 h o n g 等m 】的方法采用g a b o r 滤波器在空间域进行滤波，c a b o r 滤波器具有良好的 方向和频率选择特性。该方法首先求出局部区域中纹线的主导方向，每个像素点处的方 向取为其所在局部区域的方向，然后用投影分析法求局部区域的纹线频率，最后用中心 频率和中心方向与像素点的方向和频率相同的g a b o r 滤波器对每个像素点进行滤波处 理。 上述各种方法之间的不同之处主要体现在以下几个方面： 4 指纹蕾u 哪算法司”宅 ( 1 ) 所采用的滤波器形式不同。 ( 2 ) 滤波处理所采用的方式不同。有的在空间域通过卷积实现，有的在傅立叶频谱空 间进行。 ( 3 ) 采用不同的估计方向图方法，以及使用不同分辨率的方向图。有的求出每个像素 点处的方向，有的求局部区域内的主导方向；有的将方向量化为少数几个均匀分布的方 向，有的采用连续方向值。 ( 4 ) 采用不同的增强策略。有的对每个像素点使用不同参数的滤波器进行逐点滤波， 有的先用若干固定特性的滤波器对整幅图像进行滤波，然后根据像素点的特征从不同滤 波后图像中选择该像素点增强后的值。 2 图像二值化 ， 该步骤将增强后的指纹图像转化成只有0 ，l 取值的二值图像。传统的二值化方法 有固定阈值法、自适应阈值法、局部自适应阈值法等，这些方法利用图像的灰度信息实 现图像的二值化，实现起来比较简单，但处理速度上有所欠缺。文献【2 l 】采用了动态阙 值二值化方法，它结合指纹图像自身的方向结构特点和图像灰度值变化特点，对图像中 每一个像素点的二值化进行动态阈值。此方法处理速度上有优势。 3 图像细化 细化是删除二值化指纹图像的边缘像素，使其转变成只有单像素的骨架图像，以便 于细节特征的提取。细化时应保证纹线的连接性、方向性和特征点不变。此外，还应保 持纹线的中心基本不变。指纹纹线的细化从实现上可分为两大类：一类是从外到内逐点 剥去二值图像的边界点，如文献 2 2 】中的h i l d t h 算法；另一类是从内到外，找到某一中 间点，然后按扫描方向寻找其八邻域内也为指纹条纹中间像素的点，逐次取得细化线。 前一种方法中间定位性较好，易于实现，但往往要经过若干次迭代算法，速度较慢。后 一种方法能保持较好的连通性，但情况复杂，有时中间定位不准，较难实现。 1 2 2 指纹特征提取 该步骤对细化后的指纹图提取分叉点、断点等特征点，建立相应的特征向量，以便 进行指纹匹配工作。特征提取中常用的方法是交叉数计算法【硎。该算法通过计算像素点 的交叉数来判定该点的特征类型，实现容易，执行效率高有较好的应用效果。 1 2 3 指纹匹配 指纹匹配是用当前输入的指纹特征与事先保存的模板特征相比对，从而判断这两个 指纹特征是否来源于同一个手指。英国学者h e r r ) , 1 2 5 l 认为，只要有1 2 1 3 个特征点重合， 就可以确认为是同一个指纹。指纹匹配基本上是指纹自动识别系统的最后一关，因此匹 配算法是整个指纹识别系统中至关重要的步骤。 指纹讽射算法訇| 竞 在基于细节点的指纹识别中，指纹匹配的问题可以简化为点模式匹配问题。在理想 的情况下，如果指纹图像具有以下特点：第一，两个指纹没有发生诸如平移、旋转、残 缺等变形。第二，每个细节点能够准确的定位和表达第三，模板指纹的细节点模型和 输入指纹的细节点模型的对应关系已知，那么指纹匹配问题就是简单地统计空间范围内 的匹配点数。但实际上，判断两个指纹是否来自同一个手指是十分困难的一件事，这种 困难主要有两个原因：第一，即使输入指纹和模板指纹是匹配的，但彼此细节点表达式 的对应关系事先并非是已知的。第二，成像系统本身有很多特殊的情况，在实际应用中 难以避免的不利因素会对指纹匹配构成不同程度的影响【l o j ： ( 1 ) 指纹采集是将手指的三维结构映射到二维平面上的过程，这种映射函数无法用一 个准确的数学表达式表达。由于手指按压力度不同，手指和指纹采集器的接触面积不同 等原因造成每次获得的指纹图像都会呈现一定程度的形变。 ( 2 ) 在皮肤干燥或潮湿，皮肤有疾病或不干净等多种复杂情况下，可能会产生不理想 的后果：部分的脊线区域没有和采集器的平面相接触，而部分的谷线区域却和采集器的 平面相接触。结果往往会产生低对比度和模糊的图像，导致伪细节点产生和真细节点消 失 ( 3 ) 由于体力劳动的磨损或意外等原因造成手指的伤害，可能会留下暂时性或永久性 的伤疤，这可能会引入额外的伪细节点。 ( 4 ) 由于指纹采集器自身的原因可能会使指纹图像含有噪声，例如，上一次指纹捕捉 时留下的残留物没有及时清除。其中有一些采集器由于不完善的成像条件，可能会对指 纹图像产生不同程度的扭曲或几何形变。 ( 5 ) 由于特征提取和后处理的算法不够完善，不同的图像处理操作可能会干扰细节点 的定位和方向，使得对细节点的描述产生误差。 鉴于上述可能出现的情况，要设计一个准确有效的指纹匹配算法就必须适应下列可 能出现的一些不利因素： ( 1 ) 手指可能会放在采集器的不同部位，导致细节点的全局移动。 ( 2 ) 手指按压的方向可能会发生变化，导致细节点的全局旋转。 ( 3 ) 手指可能会施加不同方向的压力，导致局部细节点的空间比例不同。 ( 4 ) 输入指纹和模板指纹中可能会产生虚假的细节点 ( 5 ) 输入指纹和模板指纹中可能会缺少真实的细节点。 ( 6 ) 与模板中细节点相比，输入指纹的细节点往往在其周围作不规则形变。 ( 7 ) 与模板中细节点相比，输入指纹细节点的类型可能会发生变化，如原来是分叉点， 现在变为末梢点。 当指纹专家拿到两个指纹进行匹配的时候，按照通常的思路，会首先找到指纹的中 心参考点，接着按照纹线的走向旋转指纹，然后拿对应位置的特征点与其周围的特征点 进行比较，看它们之问的相对位置关系是否相同或相似，当相互匹配的特征点个数达到 一定数量，就认为这两个指纹来自相同手指。而当这个过程中某个环节的比对结果相距 6 ，1 盯大摩嘎士掌位崔屯 指纹讽别捌嚼习f 兜 甚远时，就会停止接下来的操作，认为两个指纹不匹配。 但对于计算机自动指纹识别系统，还不能完全按人类专家那样来实现指纹识别。目 前常用的方法1 2 9 f 1 3 2 是基于f b i 提出的细节点坐标模型来傲匹配，它利用末梢点和分叉 点这两种细节点来识别指纹。当将这些细节点应用到点模式中，一个自动指纹识别问题 就转化为点模式匹配问题，而点模式匹配问题则是模式识别中一个有名的难题。它的原 理是采用相似变换的方法把两个细节点集中相对应的点匹配起来。这些相似变化包括平 移、旋转和伸缩变换等线性变换，它可以允许少量伪细节点的存在、真实细节点的缺少 以及少量的特征点的定位偏差，对图像的平移和旋转不敏感。关于点模式匹配，现在虽 然已提出了一些算法 2 9 h 3 2 ，例如，最近邻法、最小生成树法、松弛算法，d e l a u n a y 三 角形构造法和聚类算法等，但这些点模式匹配算法用在指纹识别上都存在两个共同的不 足之处，一方面，匹配速度较慢，另一方厩，对图像的质量要求较高，由于低质量的图 像会带来大量的伪细节点，所以匹配效果不佳。解决的方法往往局限在寻找快速算法和 最优化方法上。 文献【3 3 】- 【3 6 】采用了基于结构的方法进行指纹匹配。这种方法共同的特点就是利用 指纹图像的拓扑结构，例如，利用细节点构造三角形、星形和线段等几何结构。这种基 于结构的算法往往是对指纹专家的识别行为进行模仿，通过细节点问的结合，将点匹配 变成结构匹配，从一定程度上改变了点匹配算法中对指纹图像质量过高的要求，这也是 最近在该邻域研究中值得关注的发展方向之一。 如果将指纹看成一种纹理，些用于纹理检测的方法【3 7 】【3 8 】，例如傅立叶梅林变换， 小波变换等也用于指纹识别，但这些算法在中心点定位不准确时，可能会导致识别率偏 低。 目前也提出了一些基于人工神经网络的指纹匹配方法p 9 4 0 1 。这种识别方法容错性 高，但是必须要有大量样本的事先训练才能发挥作用，而且由于神经网络固有的反复调 练特性，速度难以提高，计算量也偏大，因此不适合用于对时间要求较高的实时在线指 纹识别系统。 1 3 课题研究内容及论文结构安排 本文针对目前指纹识另u 所存在的问题，综合利用数字图像处理、模式识别、计算智 能等方面的知识，系统地研究了指纹图像预处理算法、指纹特征提取算法以及指纹细节 点匹配算法。具体工作如下： ( 1 ) 研究了指纹图像增强问题，给出了一种改进的基于c r a b o r 滤波的指纹增强算法。 局部指纹纹线相互平行、方向固定，近似平面正弦波，在其傅立叶频谱图中纹线信 号和噪声信号所对应的频谱成分之间具有很好的可分性，采用带通滤波器能实现很好的 增强效果。g a b o r 滤波器是一种带通滤波器，具有很好的方向和频率选择特性，因此本 文选用g - a b o r 滤波器进行指纹增强。给出了一种改进的基于g a b o r 滤波的指纹增强算法。 7 指瑚n ，l 别囊坤鲁研究 首先，对指纹纹线方向提取算法进行了改进，有效地提高了低质量指纹图像下纹线方向 计算结果的可靠性。其次，改进了纹线频率的提取方法，针对纹线较宽的指纹和含有较 多汗孔的指纹，能够有效地避免了g a b o r 滤波后在脊线中留下伪纹线和小孔的问题。实 验结果表明，针对纹线较宽的指纹和含有较多汗孔的指纹图像，采用本文的改进算法效 果良好，具有显著的增强效果。 ( 2 ) 研究了指纹图像细化问题，给出了一种改进的索引表细化算法。 细化是图像预处理技术的核心，细化处理的结果关系到提取的图像特征是否有效， 从而影响系统的识别率。近年来，人们提出了许多二值图像细化算法，如快速细化算法、 改进的o p t a 算法、经典细化算法、索引表细化算法等，有的虽可以保证完全细化，但 迭代次数较多；有的虽迭代次数少，但不能完全细化。索引表细化算法具有细化速度快 的优点，被广泛应用于各种二值图像的细化，但索引表细化算法在用于细化指纹二值图 像时，会存在纹线分叉点处细化不彻底的问题，本文对该算法进行了改进，该法利用模 板比较对分叉点细化结果进行修正，从而解决了现有索引表细化算法在处理指纹图像后 存在的纹线分叉点处细化不彻底的问题，有效去除了伪特征点，细化后的指纹骨架在纹 线中心线，并且光滑无毛刺。 ( 3 ) 对指纹细节特征提取和指纹匹配算法迸行了研究。采用交叉数算法对指纹进行特 征提取，采用基于编辑距离原理的指纹细节特征匹配方法对指纹库进行了实验，实验结 果表明该方法能够有效的进行指纹特征提取和指纹匹配。 本文的结构安排如下： 第一章：介绍了指纹识别的研究背景、国内外研究进展和现状，分析了现有技术的 优缺点，阐明了本文工作的意义和主要内容的安排。 第二章：先介绍了自动指纹识别系统的基本流程，然后介绍了指纹图像的增强及改 进算法，最后介绍了指纹图像的二值化。 第三章：介绍了指纹二值图的细化及改进算法。 第四章：主要研究指纹特征提取及指纹匹配过程，介绍了交叉数特征提取算法和基 于编辑距离的指纹匹配算法。 第五章：实验结果分析。 第六章：本文工作总结及未来工作展望。 g ，百大掣咽仕掌位能- 文 第二章指纹图像的增强及改进算法 2 1 自动指纹识别系统的基本流程 一般来说，自动指纹识别系统, a f t s ( a u t o m a t i cf i n g e r p r i n ti d e n t i f i c a t i o ns y s t e m ，简 写为a f i s ) 的框架如下图2 1j 标 5 q 。 图2 - 1a f i s 结构框图 f i g 2 1s y s t e mc 0 i 硒g u r a t i o nd i a g r a mo f a f i s 1 指纹图像采集 将一个人的指纹采集下来输入计算机进行处理是自动指纹识别的首要步骤。指纹图 像的采集可以通过捺印方式来获得，也可以通过光学取像，传感器取像，超声波扫描等 设备取像方法获取。 2 指纹图像的预处理 预处理在整个自动指纹识别系统过程中是关键的第一步，通常，由于在指纹图像采 集时不可避免的带有输入干扰，我们需要去除这些噪声才能正确地进行特征提取、分类、 匹配等操作。 对于不同的特征提取方法有着不同的预处理要求。直接从原始指纹图像上提取特征 时，预处理的过程只是简单的对指纹进行增强；从细化图像中提取特征时，预处理的过 程一般包括图像分割、滤波增强、二值化、细化等步骤，最后锝到一幅指纹的脊是单像 素的二值图像。 3 指纹图像细节特征提取 指纹图像在经过了预处理诸步骤后，形成了一幅指纹点线图，这时就可以进行特 征提取。最常用的细节特征是f b i 提出的细节点坐标模型，它利用脊末梢与分叉点( 图 2 - 2 ) 这两种特征来鉴定指纹。 9 指绒帆捌算爿a f 兜 。0 。 图2 - 2 眷末梢与分又点 f i g 2 - 2e n d i n ga a db i f u r c a t i o n 4 指纹特征匹配 当进行指纹特征匹配时，输入指纹通过细节特征提取产生的特征和指纹库中所存 储指纹的特征进行比对，并给出结果( 正确或错误或拒绝识别) 。它是自动指纹识别系统 的核心 2 2 指纹图像增强算法概述 指纹识别的原始输入数据是数字化指纹图像，而指纹识别所依据的通常是指纹纹线 的结构信息。例如指纹匹配一般基于纹线的局部结构特征，如纹线端点、分叉点等细节 点。能否从原始指纹图像中可靠地提取出这些特征，对指纹识别系统的精度以及指纹匹 配等算法的设计难度具有非常关键的影响。 如果指纹图像中的指纹纹线非常清晰，即脊线和谷线对比度很大、脊线之间明显分 离，则很容易用图像二值化方法从指纹图像中分离出脊线区域和谷线区域，进而从脊线 上提取出指纹局部特征或全局特征。然而在实际中，受各种因素的影响，采集到的指纹 图像不能保证都很清晰，图像中可能出现纹线粘连、纹线断裂或对比度不均匀等情形。 在这种情况下很难从图像中正确地分离出指纹纹线，导致指纹特征的可靠提取变得非常 困难。 造成指纹图像质量差的主要原因是： ( 1 ) 手指表面与采集设备表面的非均匀接触。对于光电指纹采集设备，如果指纹的脊 线与采集设备表面充分接触，而谷线与采集设备完全不接触，那么将获得清晰的指纹纹 线结构。但是在现实使用中这种理想条件很难满足。手指表面的油脂、汗液、污渍，手 指皮肤的破皮，上一个人在采集设备表面残留的痕迹等使指纹脊线无法充分接触到采集 设备表面此外，手指按压力度不同导致接触程度不同，如果按压力度很大，指纹脊线 受挤压变形互相靠近，使图像中的脊线出现粘连。对于油墨转印法采集指纹，当手指上 油墨太多、太少或涂抹不均匀时将造成图像质量较差。 ( 2 ) 采集设备的原因。设备工作环境不好( 温度和湿度不当) 、设备参数设置不当以及 设备电路噪声等会造成图像对比度较差和图像噪声 ( 3 ) 指纹本身的原因。统计结果表明，大约有4 的人其指纹天生就不好。另外，老 人的手指上通常存在很多褶皱，皮肤病患者的手指上有很多翘皮，体力劳动者的手指上 存在老茧且经常会产生划痕。 l o 指纹识别算话研究 指纹纹线模糊对指纹局部特征提取的影响尤为严重当指纹图像质量较差时，作为 指纹匹配关键环节的细节点特征提取过程可能会产生以下错误： ( 1 ) 产生大量虚假细节点。即将不是细节点的地方判定为细节点，如将纹线断裂处判 定为两个纹线端点，将纹线粘连的地方判定为纹线分叉点，但是事实上这些并不是真实 细节点 ( 2 ) 遗漏真实细节点。即忽略了存在细节点的地方，没有从中提取出细节点。造成遗 漏真实细节点的主要原因是指纹图像的对比度较差，从而隐藏了其中的细节点结构。 ( 3 ) 细节点位置和方向存在误差。虽然判断出在某处存在细节点，但是给出的细节点 位置和方向不很精确。 ( 4 ) 细节点类型错误。即将纹线端点判定为纹线分叉点，将纹线分叉点判定为纹线端 点，造成这一问题的主要原因也是纹线断裂和纹线粘连。 基于错误的细节点显然很难达到较高的指纹匹配精度。为了保证可靠地提取出指纹 特征，为指纹识别提供更加可靠的依据，一方面需要研究对指纹图像质量具有鲁棒性的 指纹特征提取方法，另一方面应该从提高指纹图像的质量入手。 要获得质量较好的指纹图像，首先应该提高指纹采集设备的性能，遗憾的是在目前 的技术条件下还没有哪种指纹采集技术能在各种条件下都获得质量很好的指纹图像。其 次是依靠用户在采集指纹时的配合，例如使用适当的力度、保证手指的清洁及具有适宜 的干湿度，然而在实际应用中很难保证所有的用户都做到这一点。最后是对指纹图像进 行增强处理，即恢复指纹图像中模糊的区域，提高其中指纹纹线的清晰度。 增强后的指纹图像中应该具有清晰的指纹纹线，即要求指纹纹线之间明显分离、纹 线边缘平滑、纹线上不存在嗓音，且增强后的指纹纹线应尽可能反映指纹的本来面貌， 如恢复因疤痕造成的纹线断裂，此外，增强处理不应该改变纹线结构而引入新的误差， 否则将导致产生虚假的指纹特征，违背了指纹增强的初衷。 数字图像处理中一些通用的图像增强方法【1 3 l 如均值滤波、低通滤波、边缘增强等对 指纹图像的增强效果不理想，这是因为这些方法主要针对图像中的随机噪声，而模糊指 纹图像中的指纹纹线缺陷属于结构性噪声。 很多指纹增强算法对细化指纹图像进行增强f 1 4 】l 嘲。这类方法的基本做法是在对原始 灰度指纹图像用低通滤波、直方图变换等通用图像增强方法进行处理后，依次进行二值 化和细化处理，得到细化指纹纹线，然后通过对细化纹线拓扑结构的分析，结合指纹纹 线的方向、纹线之问的距离等特性，修正细化纹线的结构。这种方式的根本缺陷是二值 化和细化处理不仅会损失很多有用的图像信息，而且也会带来很多新的误差，从而在此 基础上所恢复的指纹纹线结构可能不能反映指纹的原始面貌。 还有一些算法是在原始灰度指纹图像上进行指纹增强【1 6 】【1 7 1 硼1 1 9 】1 2 0 。指纹图像由脊 线和谷线交替构成，理想情况下，指纹图像局部区域中的指纹纹线形成一个具有固定频 率和方向的平面正弦波。基于这一特性，人们提出了采用具有方向和频率选择特性的带 通滤波器进行指纹增强处理的思想。经适当调节的带通滤波器能滤掉图像中的噪声信 g - 冒r 大掣嘎士掌脚时e 文 指纹讽曼蚂| 法研究， 号，而保留两个频谱峰所对应的指纹纹线信号。与基于细化纹线增强方法相比，这类方 法具有较好的效果。下面对采用这种思想的几种方法进行简要介绍。 s h e r l o c k 等u 6 】的方法利用b u t t e r w o r t h 带通滤波器和一种角度选择滤波器的组合来 构造滤波器，滤波器的主要参数有中心频率、中心方向、频率通带大小和方向通带大小 滤波处理在频域进行。该方法首先选择1 6 个均匀分布的中心方向，用以它们所确定的 1 6 个滤波器分别对原始图像进行滤波，得到若干幅滤波后指纹图像。由于这些滤波器的 频率通带设置较大，从而不必构造不同中心频率的滤波器。然后采用方向灰度投影法估 计每个像素点处的纹线方向，并根据方向图求出奇异点位置。对每个像素点，选择若干 滤波方向与该像素点方向接近的滤波后图像，以这些图像中对应像素点的加权平均值作 为该像素点最终增强结果。所选滤波后图像的数目与该像素点与奇异点的距离有关，与 奇异点越近，其方向性越差，需选用较多滤波后图像，反之，距奇异点越远，其方向性 越好，故只需选用较少的滤波后图像进行组合，这样做的实质是根据像素点处方向性强 弱调整滤波器的方向通带大小 k a m e i 等1 17 】方法的滤波处理也是在频域进行。滤波器形式上为两个高斯带通滤波器 的乘积，它们分别对方向和频率进行选择。该方法首先用若干不同中心频率和中心方向 的滤波器对原始图像进行滤波，得到若干滤波后图像。然后从这些滤波后图像确定每个 像素点增强后的值，与s h e r l o c k 等根据像素点方向进行滤波后图像选择的方法不同，该 方法搜索一种使增强后图像的方向连续性最好的增强像素点选取组合方法，增强图像中 像素点的方向为它所来自的滤波后图像所对应的滤波器的方向。方向连续性通过准则函 数度量，利用贪婪算法搜索使准则函数最小化的组合方式。 h o n g 等睁l 】的方法采用g a b o r 滤波器在空间域进行滤波，g a b o r 滤波器具有良好的方 向和频率选择特性。该方法首先求出局部区域中纹线的主导方向，每个像素点处的方向 取为其所在局部区域的方向，然后用投影分析法求局部区域的纹线频率，最后用中心频 率和中心方向与像素点的方向和频率相同的g a b o r 滤波器对每个像素点进行滤波处理。 下面对这一思想进行简要介绍： g a b o r 滤波器 4 4 - 4 7 是一种带通滤波器，它具有良好的方向和频率选择特性，其在空 间域的表达式为