（通信与信息系统专业论文）指纹识别算法研究与实现.pdf

摘要 摘要 自动指纹识别作为具有良好发展前景的生物识别技术之一得到了广泛的关 注和研究，许多应用级产品已经投入使用，但远未到问题完全解决的时候，设 计一种能够有效提取特征信息并使匹配的鲁棒性较高的算法是相当困难的，尤 其是在指纹图像质量比较差的情况下更是如此。 本文着重研究了自动指纹识别的几种主要技术，如指纹图像增强、细化、匹 配、指纹分类等，并提出了解决方案。在方向图的求取上提出了一种采用各向 同性s o b e l 算子作为边沿检测算子，并利用指纹局部方向的连续性对图像抽样， 对样本处理来计算方向图的方法；在方向滤波增强部分，利用指纹图像灰度在 一定范围内平滑变化的特点，提出了一种基于空域抽样和插值的方向滤波增强 算法；在对增强图像的细化方面，提出了一种基于方向场的指纹图像四方向扫 描细化方法；在点模式匹配问题上，针对x u d o n gj i a n g 匹配算法不足之处，提 出了一种改进的基于全局及局部结构特征和多级判别准则的综合匹配算法；在 自动指纹分类上，分析了几种不同类型的分类算法的基本原理和主要缺点，在 此基础了提出一种基于纹线方向变化最大熵指纹奇异点的提取算法，阐述了基 于奇异点的分类算法。在这些算法的基础上用v c 实现了一套既可用于图像处理 实验，又可检验指纹识别算法性能的单机实验版自动指纹识别系统，为将来的 联机指纹识别系统和嵌入式识别系统的开发打下了良好的基础。 关键词：指纹识别、抽样和插值、方向场、特征提取、最大熵 a b s t r a c t a b s t r a c t a so n eo ft h eb i o m e t r i c sw i t he x c i t i n gf u t u r e ，t h ea 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 ) r e c e i v e da t t e n t i o na n d r e s e a r c h i n gw i d e l ya n dh e a v i l ym a n y a p p l i c a n tp r o d u c t sh a v eb e e ni nu s e h o w e v e r , i ti s f a rf r o mt h et i m ew h e ne v e r y t r o u b l ew o l l l db er e s o l v e d i ti s v e r yd i f f i c u l t t o d e s i g n 8 i 1 a l g o r i t h m w i t hh i g h m a t c h i n gp r e c i s i o n ，e s p e c i a l l yt ol o wq u a l i t yf i n g e r p r i n t m u c h r e s e a r c h i n ga c h i e v e m e n t0 1 - 1t h ea f i sh a sb e e np r e s e n t e di nt h i sp a p e r f o re x a m p l e ，ao r i e n t a t i o ng r a p ha l g o r i t h mb a s e do l l i s o t r o p ys o b e lo p e r a t o r , a o r i e n t a t i o n f i l t e r i n g e n h a n c e m e n t a l g o r i t h m b a s eo n s p a c es a m p l i n g a n d i n t e r p o s i n g ，at h i n n i n ga l g o r i t h mb a s e do n f o u ro r i e n t a t i o ns c a n n i n g ，ai m p r o v e d m u l t ij u d g i n gc o n d i t i o n sm a t c h i n g a l g o r i t h mb a s e d o ng l o b a la n dl o c a ls t r u c t u r e f e a t u r ea n das i n g u l a rp o i n t sd e t e c t i o na l g o r i t h mb a s e do nm a x i me n t r o p yo f o r i e n t a t i o nv a r i a t i o n b a s e do na l lo fa b o v e a l le x p e r i m e n t a lv e r s i o na f i sb a s e do n v ca n do r a c l ef l a th a sb e e nd e v e l o p e d a l lo f t h e s ew o r k s p r o v i d eg o o df o u n d a = t i o nf o r d e v e l o p i n g o n l i n ea f i sa n de m b e d d e da f i si nt h ef u t u r e k e y w o r d s ：f i n g e r p r i n tr e c o g n i t i o n ；s a m p l ea n di n t e r p o s e ；o r i e n t a t i o nf i e l d ；f e a t u r e e x t r a c t i o n ；m a x i me n t r o p y u 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：日期：夕彬犀夕月岁目 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后 签名： 应遵守此规定) n 翩签辎 日期：w 5 年；月岁白 电子科技大学硕士学位论文：指纹识别算法研究与实现 1 1 生物识别技术概况 第一章绪论 生物识别技术是指通过计算机利用人类自身生理或行为特征进行身份认 定的一种技术。近十多年来，作为模式识别和机器视觉的一个重要研究领域， 生物识别技术获得了前所未有的发展，现在已经有许多种类的生物识别技术 出现。其中有一部分还处在研究阶段，比如体味分析( t h eo d o ra n a l y s i s ) ， 另外还有相当一部分已经发展得较为成熟而进入了商用领域。现在看，至少 有十多种不同的生物特征可以作为有商用价值的识别技术基础，比如指纹 ( f i n g e r p r i n t ) 、指形( f i n g e rg e o m e t r y ) 、手形( h a n dg e o m e t r y ) 、掌纹 ( p a l mp r i n t ) 、虹膜( i r i sp a t t e r n ) 、视网膜( r e t i f l ap a t t e r n ) 、面部识 别( f a c i a lr e c o g n i t i o f f ) 、声音比对( v o i c ec o m p a r i s o n ) 、签名( s i g n a t u r e d y n a m i a s ) 、d n a 等。 1 2 为什么选择指纹 指纹识别可能是最早被使用的生物识别技术。考古证实，公元前7 0 0 0 年 到6 0 0 0 年以前，古叙利亚和中国，指纹作为身份鉴别己经开始应用。而自动 指纹识别兴起于上世纪六十年代的，是当前最为成熟的生物测定技术之一。 相对于其他生物特征鉴别技术例如语音识别及虹膜识别等，指纹识别具有许 多独到的优点，如易于采集、技术成熟可靠等，更重要的是它具有很高的实 用性和可行性，使其在越来越多的领域如社会安全、网络安全、办公安全、 资讯安全、金融安全、个人安全及防伪等方面得到广泛的应用，被认为是一 种理想的身份认证技术，有着十分广泛的应用前景，是将来生物特征识别技 术的主流。世界有实力的国家纷纷进军指纹识别技术及市场的开发。目前， 利用计算机进行指纹识别的技术在国外已较成熟，并且已经开始大规模推广。 许多大公司有专门的机构从事该项技术的研究和应用产品的开发，包括( i b m 、 i n t e l 、m i c r o s o f t 、d i g i t a l p e r s o n a 、韩国现代、朝鲜培富士、台湾v e r i d i c o m 公司，其中i d e n t i x 公司在生物识别技术领域独树一帜，韩国现代、朝鲜培 电子科技大学硕士学位论文：指纹识别算法研究与实现 富士在识别算法上也都达到世界先进水平。国际上著名的大型指纹识别系统 有：美国联邦调查局的a f i s 系统、英国迪米里印迹公司的f i s 系统、日本n e c 公司的指纹鉴定系统、北美英弗公司的指纹鉴别系统等；成功的指纹识别产 品有：c o m p a q 、d i g i t a l p c r s o n a 、n e c 等公司生产的指纹识别器，美国 s g s t h o m s o n 制造的t o u c h c h i p 指纹识别芯片等。近年来，特别是从1 9 9 8 年来， 我国在指纹识别技术方面得到较大发展，可以说是日新月异。从研究角度来 说，国内外的差距并不明显，有些方面还处于领先地位。但是国内对于a f i s 主要侧重于研究角度，很长一段时间没有在实际应用中实践，所以这些技术 和实际的市场需求间还有不少差距。而实际从事指纹应用的公司鲜有自己的 技术，绝大多数都是使用国外的指纹识别算法。国内从事指纹产品开发的知 名公司有西安青松公司、北京中控、北京汉王、厦门宝利铬、厦门一指通、 北京培富士、北京海鑫、同飞资讯、深圳数码、深圳乾诚科技等。不管是引 进技术还是自己开发的指纹识别产品，由于其成本太高，一款普通的指纹门 锁都要4 0 0 0 元左右，市场接受能力有限，市场推广难度大，所以需要开发出 具有完全知识产权的指纹识别算法及其应用产品，满足一般小型的嵌入式及 大容量比对的需要，在此基础上研制基于d s p 及大规模可编程器件的独立识 别模块，利用此核心模块开发出系列指纹门禁、卡证应用系统等，这些都具 有很好的市场前景。 自动指纹识别是一种复杂的模式识别问题，设计一种能够有效提取特征 信息并使匹配的鲁棒性较高的算法是相当困难的，尤其是在指纹图像质量比 较差的情况下更是如此。尽管目前指纹识别技术空前发展，但远远没到问题 完全解决的时候，指纹识别仍然是富有挑战性的、重要的模式识别问题。 1 3 作者的主要工作及论文的主要内容 指纹识别是一种较为成熟的生物识别技术，我国在指纹识别算法上的研 究已经处于世界一流水平，就在前不久举行的世界指纹识别技术大赛 ( f v c 2 0 0 4 ) 上，中科院自动化所提交的指纹识别算法的多项技术指标拿到了 金牌! 这是所有国人的骄傲，同时也说明，对于我们这样一个团体，耗费大 量的精力和物力去研究一整套全新的算法，意义不大，客观条件也不允许。 电子科技大学硕士学位论文：指纹识别算法研究与实现 因此，我把研究重点放在对现有算法的优化、改进和自动指纹识别软件的设 计实现上。 在识别算法的研究上主要从方向滤波增强、增强图像细化、点模式匹配问 题、自动指纹分类等方面提出了自己的观点和解决方案；在识别软件的设计 上，对在v c 和o r a c l e 平台下如何实现a f i s 进行了一系列的研究与探讨。 1 4 本文的章节安排 论文的主要内容及其安排如下： 论文第一章主要介绍和总结了指纹识别技术的发展现状和发展趋势，简 要说明了本文涉及的研究范围和目标。 第二章则主要介绍自动指纹识别算法研究，详细讨论本文的识别算法的 细节，并与相关著名算法进行比较，指出改进之处，分析所做改进的原因。 第三章则重点介绍基于本文算法的单机版自动指纹识别软件的设计和开 发，包括简要的需求分析、软件的设计和开发、识别结果及分析等 第四章进行全文总结、指出下一步的工作。 电子科技大学硕士学位论文：指纹识别算法研究与实现 第二章自动指纹识别算法研究 本章详细讨论本文自动指纹识别算法的细节，并与相关著名算法进行比 较，指出改进之处、分析所做改进的原因、给出相应的实验结果。 2 1 自动指纹识别系统的发展现状和趋势 一套完整的指纹识别系统通常包括以下几部分：指纹图像的采集、图像处 理、数据存储、模式匹配等。相应的a f i s 的研究主要集中在指纹采集技术、指 纹图像预处理、指纹分类和模式匹配等方面。在系统的设计上主要考虑系统的 可靠性、快捷性、灵活性、安全性、可接受性、兼容性、实时性等因素。 2 1 1 指纹图像的采集技术简介 现在使用的指纹采集设备几乎都是活体指纹采集器，活体采集仪感应指纹 的温度和湿度、电容差等信息，这就保证了系统的安全性和指纹图像的不可替 代性，因为复制的指纹图是无法在活体指纹采集器识别的。 指纹取像方式有以下几类：光学、硅晶体传感器、超声波扫描等。光学取 像设备在2 0 世纪7 0 年代就开始被使用，其依靠光的全反射原理。光线照到压 有指纹的玻璃表面，由c c d 摄像头获取反射光线，反射光的强度依赖于手指与 玻璃采集表面的面积。但这种传感器结构复杂，价格较高，体积庞大，因此造 成整个识别系统价格非常昂贵，所以过去指纹识别系统仅仅在公安、银行等特 殊部门内应用。随着光电技术的发展，光学传感器的价格和体积也在不断下降， a f i s 也顺利进入普通的民用领域。9 0 年代中期开始出现半导体的指纹传感器。 最初这类传感器采集的图像质量和光学传感器有比较大的差距，但是随着半导 体技术的进步，它采集的图像质量也越来越高，现在这两种传感器采集的图像 质量差距已经相当小了。半导体传感器具有价格低、体积小的优点，特别适合 集成在普通的消费电子产品中，有取代光学传感器的趋势。除此之外，还有超 声波扫描取像，由于采用比光学扫描的激光波长更短的超声波，这种采集装置 对积累在皮肤上的异物和油脂等不敏感，抗干扰能力强，成像质量高。表2 1 “1 是这几类采集方式效果的比较： 4 电子科技大学硕士学位论文：指纹识别算法研究与实现 表2 1 几种主要指纹采集装置的性能对比 噪集方式院学全反射技术 陋晶体电容传感技术渖声波扫描 l 体积中小大 耐用性非常耐用容易损坏一般 干手指差，汗多的手指干手指好，汗多的手指不能 戚像能力非常好 成像比较模糊成像，抗静电能力差 盼辨率 4 5 0d p i 3 0 0 d p i 5 0 0 d p i 嚷电l 较少一般 较多 减本慨i 低 陋高 2 1 2 指纹图像的特点 如图2 1 所示，指纹图像包含很多细节信息( m i n u t i a e ) ，有c o r e ( 中心) 、 b i f u r c a t i o n ( 分叉) 、r i d g ee n d i n g ( 端点) 、i s l a n d ( 岛) 、d e l t a ( 三角) 、 p o r e ( 池) 、c r o s s o v e r ( 交叉) 等。但由于采集条件的不同，比如：采集方式、 空气湿度、采集时的人为因素( 如手指的污染、伤痕、干燥、潮湿、与接触表 面的压力) 等都会引起指纹图像的附加噪声，如图像的旋转、斑点、空洞，纹 线的断裂、扭曲、粘连等。因此，如何从包含大量噪声的指纹图像中找出有用 的细节信息，就是细节类指纹识别算法的要解决的关键问题。另外，指纹的拓 扑特性及某些先验知识也为指纹识别提供了多种有效的途径。 图2 1 指纹的细节特征 电子科技大学硕士学位论文：指纹识别算法研究与实现 21 3 自动指纹识别的主要算法 指纹识别算法是a f i s 系统的核心技术，这方面的研究虽然早在1 9 世纪初 就开始了，但深入研究是从2 0 世纪6 0 年代后随着计算机技术的引入才逐步开 展起来的。早期的研究主要针对脱机的指纹图像，而且都是在高性能计算机上 完成的，研究的广度和深度相对不足。随着技术的发展，8 0 年代到9 0 年代初开 始针对光学传感器，进行联机的活体指纹识别算法的研究，由于这个时期a f i s 只在特殊的行业部门使用，所以往往可以使用了价格比较昂贵的d s p 等硬件附 加设备来解决指纹识别的实时性问题，但推广难度大。9 0 年代末到现在，半导 体指纹传感器的出现使得指纹识别的应用领域迅速扩大，在个人电脑上、个人 数字助理、掌上电脑、手机等很多领域都开始使用a f i s 技术，所以指纹算法的 研究重点从光学传感器转移到了半导体传感器，对算法的性能也提出了更高的 要求( 因为半导体成像质量通常没有光学成像好) 。 指纹识别算法大致可归纳为四种基本类型： 1 ) 基于图像处理的图像识别算法。：此类算法大多以指纹细节特征理论为基 础。其基本流程是通过大量的预处理手段得到增强的指纹图像，然后进行特征 提取得到指纹的细节信息，再用细节特征进行比对来实现识别。但有一个比较 大的缺点是对细节特征较少的指纹识别效果差，如残缺的指纹等，这限制了此 类算法在刑事侦探方面的应用，而在民用上应用较多。 2 ) 基于规则推理的人工智能方法“叫：可以描述为基于多种知识约束下的滤波 增强、特征提取和特征匹配。比如指纹相关先验知识、数字信号处理相关知识、 图像处理相关知识等。 3 ) 基于几何拓扑的图形识别算法：这种算法是将指纹化作函数定义域，通过证 明这有限的特定的函数定义域中每个点是否都一一对应，从而判断两枚指纹是 否具有相同的拓扑性质来完成识别。 4 ) 上述各类方法的综合运用算法。 现在国内外指纹识别大都采用基于细节特征点的指纹识别技术，即采用基 于图像处理的指纹识别算法，其中比较有代表性的有两种。一种是h o n gl i n 。3 为代表的基于方向滤波增强，并在指纹细化图上提取特征点的算法，另一种是 以d a r i om a i o ”3 为代表的直接从指纹灰度图上提取特征点的算法。两类算法的 6 电子科技大学硕士学位论文：指纹识别算法研究与实现 性能比较如表2 2 所示 表2 2h o n gl i n 和d a r i om a i o 两类算法的性能比较 算法名称 b 。n gl i n 类b a r i 。m a i 。类 采用的核心技术 | 方向滤波增强拇线跟踪 特征信息提取效果 陋好陋差 特征信息提取速度慢限快 抗干扰性强睦 【算法复杂度大| 很小 d a r i om a i o 算法由于脊线跟踪容易受到纹线断裂、扭曲、粘连及空洞等的 影响，特征信息提取效果较差，但算法简单、速度快，比较适宜用在采集的图 像质量较高、匹配精度要求不高，要求速度较快的小型嵌入式识别系统上。而 h o n gl i n 类算法通过方向滤波可以得到质量较高的增强图像，在此基础上提取 的特征信息可信性较高，成为当前指纹识别算法研究的重要方向之一。所以， 本文算法以h o n gl i n 类增强算法为基础，从多方面对其进行改进，力求得到增 强效果更好，特征信息提取速度更快、匹配精度更高的识别算法。 本文中所有的指纹图像来源于f v c 2 0 0 2 指纹识别大赛指纹库。以下详细介 绍本文算法的细节。 2 2 本文的识别算法 整个算法流程如图2 2 。其中t 是指纹图像质量分割阀值，用来剔除质量太 差的、无法用作可靠识别的图像。 图2 2 识别算法的流程图 7 电子科技大学硕士学位论文：指纹识别算法研究与实现 2 2 1 指纹图像的方向滤波增强 在方向滤波增强过程中，如何保证不破坏实际存在的指纹脊线结构，而又能 有效地减少由于采集原因引起的纹线误连、纹线误断和孤立点，同时尽量减少 运算时间等是问题的关键。下面将详细讨论本文方向滤波增强的各个步骤。 2 2 1 1 计算掩码 所谓求掩码就是求指纹图像的前景区。h o n g 等”1 的算法是在求得指纹的方向 图后再求掩码，对背景区的点运算明显浪费了大量的时间，因为我们只关心指 纹区的信息；而且该算法要求局部方差、脊线频率、脊线灰度偏差等信息，计 算量大。基于此，本文将求指纹掩码这一步放到算法的最前面来做，且只需要 局部方差信息即可。 将指纹图像分割成1 6 i 6 的小块，分别计算子块的方差v a r ( i ) ，再将子块 按方差大小排序后可得到如图2 3 的关系( 图中指明了近似的最佳分割点) 。实 验发现，把方差拟合线做平滑处理后，拟合线斜率变化率o ( v a r ( i + 1 ) 一v a r ( i ) ) 最 大处的点的值接近最佳分割方差值。 图2 3 方差分割点示意图 基于此可以很方便地通过子块方差求出指纹掩码。但对那些前景区也有明显 的方差变化的指纹图像，仅靠子块方差求出的掩码往往有空洞和孤立块。这些 空洞和孤立块的存在可能使最后提取的有效特征点数量减少和伪特征点数量增 加，从而造成有效特征点的丢失，使识别性能下降。采用基于数学形态学 ( m a t h e m a t i c a lm o r p h o l o g y ) 的方法可以有效地消去这些空洞和孤立块。若掩 码中将前景点设为l ，背景点设为0 ，其原理可以简单描述为以下两条： 电子科技大学硕士学位论文：指纹识别算法研究与实现 1 ) 膨胀( e x p a n d i n g ) ：平移图像之并集。即对应块至少有块为前景就确定为 前景。 2 ) 腐蚀( e r o d i n g ) ：平移图像之交集。即对应块都为前景才确定为前景。 利用一定的膨胀和腐蚀运算可以有效地消除掩码空洞，实验求得的掩码如图 2 4 所示。 2 2 1 2 指纹图像质量评估 图2 4 指纹掩码 a f i s 的性能往往对指纹图像的质量比较敏感。如前所述，指纹在采集过程 中，由于受到多种因素的干扰( 手指的干湿状态、污染，采集器背景噪声、残 留指纹等) ，有可能得到质量很差甚至无效的指纹。受到污染的指纹会导致提取 的伪特征信息增加而使没有获得授权的人通过系统；不完整的指纹又只能得到 部分特征信息而错误地拒绝获得授权的人。这些都会导致识别性能大幅下降。 因此，有必要获得指纹的质量和有效性信息，即指纹质量的可靠性评价指标。 许多研究者使用多种不同的评价指标。如b o l l e “”等采用指纹有方向区域和 无方向区域的面积比。s h e n “o 等对子块作g a b o r 滤波，若子块经滤波后能得到 清晰的脊和谷，则认为指纹图像的质量较高。由于对原始图像直接进行方向运 算和滤波处理，一方面，大量的点运算( 对每个像素进行处理) 使时间消耗大， 另方面，仅靠方向及派生信息不足以全面可靠地反映指纹图像的质量的高低。 鉴于指纹灰度图像在纹线清晰的区域有明显的层次性，即局部方差较大，本文 主要依靠局部方差和质量较高的块的数量来判断质量好坏。 定义指纹图像质量评价指标f q a i ( f i n g e rq u a l i t ya c c e s s i n gi n d e x ) 。计 电子科技大学硕士学位论文：指纹识别算法研究与实现 算指纹区子块的平均方差m e a n o f v a r 、子块方差大于等于平均方差的块的数量 s u m o f h i g h 、子块方差小于平均方差的块的数量s u m o f l o w ，再由式( 2 1 ) 可求 得f q a i 值： f q a ，= 黑罴 ( 2 1 ) 当f q a i m o t h e r w i s e ( 2 2 ) 其中、删r 分别为期望均值和期望方差，m 、v a r 为指纹区的实际均 值和实际方差。实验发现，对吖取一定的偏差后增强效果有显著提高( 如图2 5 所示) ，即可对m 乘上一个偏差系数1 1 ，t 1 通常取0 6 0 8 。 l23 图2 5 偏差系数”对增强性能的影响比较图 电子科技大学硕士学位论文：指纹识别算法研究与实现 图中1 为原始图，2 的t 1 取1 ，3 的t 1 取0 7 。 2 2 1 4 计算方向图 几乎所有识别算法都要用到指纹方向信息，也产生和发展了多种计算方向图 的方法。b m m e h t r e “”等提出的领域方向模板法，据式( 2 3 ) 求出每个像素的 点方向，再将图像分成w * w 大小的小块，由式( 2 4 ) 对每一块计算方向模板的 各标准方向的统计直方图，直方图的峰值方向即定为该块的方向。a r r a o “3 1 提 出了基于梯度算予的最小均方根法；h o n gl i n 等。1 又对a 。r r a o 的算法做了改 进，采用了后处理平滑算法，依据指纹方向有渐进性的特点，选择适当的低通 滤波器对求得的方向图作平滑滤波。 = 邓，) 一f a i 。，厶) o p ( i ，) = d 且巧= 施n ( v o 一1 i = o 式中f o ，j ) 为点( i ，j ) 处的灰度值 l 为领域大小，n 为方向模板的方向数。 ( 2 3 ) ( 2 4 ) 厶( 0 ，l ) 为d 方a i 第m 点的灰度值， 领域方向模板法对噪声的敏感性随分块大小的增大而增大，且对纹线断裂处 的方向估计误差大，当l 超过1 6 后中心和三角区的指纹方向获取效果较差；r a o 类“”算法的主要缺点之一是采用m a r r h i l d r e t h 算子后尽管有较好的抗噪能力， 但计算复杂度较大；h o n g 等“1 采用后处理算法加以改进后，方向图有一定改进， 但单一采用低通滤波可能对指纹方向正常变化的指纹中心和三角区产生副作 用。可见方向图的估计精度对整个识别算法性能影响很大，如何准确地估计纹 线方向是首先要突破的问题。因此，本文在降低算法复杂度和平滑技巧的运用 上对h o n g 等的算法做了进一步的改进。 由于指纹的纹理的连续性，在一个有限的区域可认为指纹图像的局部方向是 一致的，并且是趋于连续变化的，因此我们不必对每一点的进行计算就可以得 到某个局部区域的方向值。本文的做法是对前景区( 指纹区) 隔一抽样，再对 样本进行处理，由于样本点只有原来的1 4 ，在理论上隔一抽样可以节约接近 3 4 的时间。 电子科技大学硕士学位论文：指纹识别算法研究与实现 检测水平边沿的( i l 享| 1 ；另一个是检测垂直边沿的 三 i 。s o b e ， 检测水平边沿的f j 了0 孑i - 1 云；车 。 f 1 o 1 l l 0 1 j ( f ，) = 2 a ，( 甜，v 弦，( “，v ) ( 2 5 0 ( f ，) = ( a ：( “，v ) 一a ；( “，力) ( 2 6 ) 式中屹( f ，) 、( f ，) 为点( i ，j ) 处沿x 和y 方向的梯度估计，a ，( ，v ) 、a ，( “，v ) p ( n ) ：委t a l l 一( ，+ w ，2 值j w j 十w t 2 一( f ，) 1 2 ( 2 7 ) m 罴 一 ” 电子科技大学硕士学位论文：指纹识别算法研究与实现 由于纹线中的毛刺、背景中的噪声点等的干扰，在已得到的方向图中会存在 一定的噪声，为了防止出现误判断，需要对方向图p ( m ，h ) 进行平滑处理。由于 方向具有循环性质，因此方向图的平滑需要采用不同于一般图像平滑的方法。方 向图平滑的基本思想是：指纹纹线的走向是趋于连续变化的，邻近点上的方向不 应该有突然的大角度转折。 f 1 21 本文的平滑采用两步：第一步用高斯平滑模版i2 4 2i 对块方向作领域平 1 1 2 l j 滑处理，再将块方向量化为8 个方向，如图2 6 所示；第二步对量化后的方向图 平滑，即若与某块的相邻的上下或左右两块的方向相同，则将对应的相邻块的方 向作为该块的方向。 矗 6 s 4 o 过乙二 彳。0 2 l 图2 6 指纹方向量化示意图 实验表明，指纹图像分块的尺寸及平滑算法的优劣对方向图的性能影响很 大，图2 7 显示在p e n t i u m1 7 g h zp c 和m a t a l b 平台上，不同分割尺寸下l i n h o n g 算法与本文算法求得的方向图( 方框内的差别更为明显) 。 2 7 1 2 7 22 7 3 电子科技大学硕士学位论文：指纹识别算法研究与实现 z 7 4z 7 5z 7 6 图2 7 指纹方向图 图2 7 1 、2 7 2 、2 7 3 分别为w = 1 6 、w = 1 2 、w = 9 时l i n h o n g 算法求得的方 向图，图2 7 4 、2 7 5 、2 7 6 分别为w = 1 6 、w = 1 2 、w = 9 本文算法求得的方向 图。可以看出，分割尺寸过大无法准确地得到指纹奇异点附近的方向信息，如 图中小方框所示，分割尺寸过d , n 算法对纹线断裂比较敏感，基于此，本文采 用的分割尺寸为w = 1 2 ；由于本文算法分阶段采用了三种不同的平滑算法，特别 是对各向同性s o b e l 算子处理后的的图像采取了初步平滑，求得的方向信息要 比l i n h o n g 算法准确。方向图的平均耗费时间l i n h o n g 算法为0 9 3 8 s ，本文算 法为0 3 2 3 s 。 2 2 1 5 方向滤波增强 g a b o r 函数是唯一能够达到时频测不准关系下界的函数，g a b o r 滤波器能够 在时频最佳的意义下确定纹理的边缘，采用g a b o r 滤波器不但能够去掉噪声， 而且能把指纹的脊和谷的结构不失真的保留下来。因此在得到方向图后，可以 根据每个像素点的方向值利用g a b o r 滤波器对指纹图像进行滤波，以消除噪音、 增强纹线、提高脊和谷之间的反差，即所谓方向滤波增强。 方向滤波器可由式( 2 8 ) ( 2 9 ) ( 2 1 0 ) 求得： 坼艄力= e ) 【p ( 一三( 等) + ( 警2 删 ( 2 8 ) b = x c o s 0 + y s i n 口 ( 2 9 ) 1 4 电子科技火学硕士学位论文：指纹识别算法研究与实现 y 目= 一x s i n 0 + y c o s 0 ( 2 1 0 ) 其中0 为滤波器的方向，厂为指纹纹线频率( 沿纹线垂直方向的单位距离内 包含的脊线数目) 。6x 和6y 分别是沿着x 和y 轴的高斯包迹的空间常量。 方向滤波器是一系列与像素点方向有关的滤波器，使用时根据某一块区域的 方向特征，从一系列滤波器中选择一个相应的滤波器来对这一块进行滤波。比 如，本文算法将方向量化为8 个方向，相应就需要8 个方向滤波器。实际应用 中，可先设计对应某个方向的方向滤波器，而对应其它方向的方向滤波器可由 该滤波器旋转得到。方向滤波器的设计通常要遵守以下原则： 1 ) 滤波器波形特性尽量与指纹脊线和谷线形成的波形特性接近，以保证较好的 对比度增强效果。 2 ) 滤波器模板的尺寸要合适。模板过小，难以达到良好的去噪、增强效果：模 板过大则可能在纹线曲率较大处破坏原有的纹线结构，而且滤波时间是随模版 尺寸的增大成平方几何级数增长，过大的模版在实际应用上没有什么价值。一 般取模板边长为1 1 5 个纹线周期，本文取9 个像素宽度： 3 ) 为滤掉谷线上的斑点、增强脊线过淡的区域，模板应关于其朝向轴及朝向垂 直方向轴均为对称，且模板边长为奇数； 4 ) 为提高脊、谷之间的灰度反差，达到边缘锐化的效果，模板应满足：在垂直于 朝向方向上，中央部分系数为正，两边系数为负，即模版应过零点： 5 ) 考虑到滤波结果应与原图的平均灰度无关，因此滤波模板中所有系数的代数 和应为零。 滤波器进行纹理分割时，需要事先确定纹线频率f ，l i n gh o n g 等利用沿纹 线垂直方向的正弦模型来求，( 一般为1 3 1 2 5 ) ，计算过程相当复杂，且实 验表明，即使准确地求出指纹纹线频率，对增强质量的影响也不大，因此可将厂 设置为一固定值，本文取，= 7 。由于时频域中的定位精度是一对矛盾的指标， 表现为增强对噪音的鲁棒性和减少假纹线结构之间的矛盾，参数a ，、a ，选取过 大会使得纹理分割在空域中的精度降低，过4 , n 会降低纹理分割的可靠性，因 此一般取经验值，本文两者都取0 4 。 综上，可以求得任意方向的方向滤波模版。本文将指纹的方向量化为8 个方 向，相应求出8 方向图的滤波模版即可。图2 8 为方向滤波器模版的网格示意 图。 电子科技大学硕士学位论文：指纹识别算法研究与实现 图2 8 滤波模版网格图 众所周知，方向滤波是h o n gl i n 类增强算法最为耗时的一部分，大约占到 整个增强算法的8 3 5 3 ，这大大限制了该类算法在实时高速自动指纹识别系统 中的应用。那么，在保证一定滤波增强性能的情况下，如何提高方向滤波的速 度就成了问题的关键。 对指纹图像的处理通常都可以归结为对位图的处理，而位图处理的特点是一 系列的点运算，要提高算法的速度，除了编程、硬件和软件方面的因素，很自 然的方法是减少需要运算的点的个数。在方向滤波时，一方面可以考虑缩小滤 波模版的尺寸，但不可能无限制地缩小，这在前面已经讨论过；另一方面考虑 减少需要作方向滤波增强的点数，本文通过如下处理后，需要作方向滤波的点 数可减少到指纹区像素的l 4 l 8 ，从而大大提高算法的执行效率： 1 ) 根据奈奎斯特抽样定理，理论上一个周期内只要采样一次以上就可完全恢复 原信号。对指纹这种离散图像来说，作隔一抽样后，采用合适的插值方法，同 样可以恢复原图像( 保留原图像的纹理结构特性) 。 2 ) 对隔一抽样后的样本，很明确是指纹脊线上的点( 三领域方差小于某一阀值 且平均灰度值小于某一阀值) 不作增强处理，直接取最小灰度值；很明确是谷 线上的点( 三领域方差小于某一阀值且平均灰度值大于某一阀值) 也不作增强 处理，直接取最大灰度值。 完成对样本的方向滤波增强后，需作插值以恢复原图像脊线信息。本文插值 算法描述如下( 前景取1 ，背景取o ) ： 6 电子科技大学硕士学位论文：指纹识别算法研究与实现 1 ) 若某点为。且三领域中某对相对的点为1 ( 如上下、左右等) ，进入第二步， 否则，判断下一点是否满足此条件。 2 ) 在三领域中将与该点及与其方向平行的线上的点附值为1 。 图2 9 比较了指纹原图、抽样滤波图和插值图。从该图可清晰看到本文增强 算法的特点和过程。 2 2 2 二值化 抽样砖陂图 图2 9 滤波模版网格图 指纹识别只对前景波峰和背景感兴趣，为了便于后续处理，如图像细化、提 取特征点等，需要对方向滤波后的指纹图像进行二值化处理。需要注意的是无 论质量好的还是质量差的图像，阈值的选取不当会导致二值化后产生信息丢失， 对于质量好的图像可能会发生特征点退化并出现一些伪特征，给识别带来很大 的困难，而对于质量差的图像则可能会产生大面积的纹线丢失，导致无法识别。 所以，二值化的结果直接影响着图像识别的效果，而分割阀值的选取是二值化 质量的关键。 本文采用最小错误分割法进行二值化。这种方法的基本思想是找到一个门限 阀值，使按这个阀值划分目标和背景的错误分割概率为最小。为计算方便，假 设指纹图像中感兴趣的目标的像素点( 脊线部分) 灰度成正态分布，密度为只( z ) ， 均值和方差分别为“和盯? ，背景点( 谷线部分) 的灰度也成成正态分布，密度 为只( x ) ，均值和方差分别为鸬和盯；。设目标的像素点数占总点数的q ，背景点 占( 卜q ) ，则混合概率密度为( 式2 1 1 ) ： 电子科技大学硕士学位论文：指纹识别算法研究与实现 p ( x ) = ! a 暇( z ) + ( 1 一q ) b ( x ) ( 2 1 1 ) 当选定门限为t 时，目标点错化为背景点的概率为( 式2 1 2 ) ： 巨( 7 _ ) 2f ( x ) d x ( 2 1 2 ) 把背景点错化为目标点的概率为( 式2 1 3 ) ： e 2 ( r ) = f 。b o ) d x ( 2 1 3 ) 则总的错误概率为( 式2 1 4 ) ： e ( 丁) = q e , ( r ) + ( 1 一q ) e 2 ( r ) ( 2 1 4 ) 令警圳惰蝴( 耻( 1 - 9 ) w ) ，由此矧： i n 堡垒一掣+ 掣：0 ( 1 一q ) 9 i2 昕2 0 - ； 当盯? = 盯；= 仃2 时，可求得( 式2 1 5 ) ： r ：些! 坐2 + ! ：l n 垒一( 2 1 5 ) 2 2 一11 一q 若先验概率为已知，本文取q = 1 2 ，则有r = 半，由此，只要求得前景 和背景的数学期望，即可得到最小错误概率意义下的最佳分割阀值。但要直接 求数学期望“、l ：比较困难，本文采用一种逐渐逼近的方法，其伪码描述如下： t = ( p m a x + p m i n ) 2 ：初始化t 为指纹灰度最大值和最小值的均值 l e n = s ( 1 ) s ( 2 ) ：总像素数目 t e m p = t + l ： t e m p 3 = s u m ( s u m ( i n p u t m a t r i x ) ) ：总的灰度值 w h i l ea b s ( t e m p t ) o 0 0 1 允许误差 t = t e m p ： t e m p l = s u m ( s u m ( ( i n p u t m a t r i x t 木o n e s ( s ) ) * i n p u t m a t r i x ) ) ： t e m p 2 = s u m ( s u m ( i n p u t m a t r i x t 木o n e s ( s ) ) ) ： z o = t e m p l t e m p 2 ：目标区的灰度均值 z b = ( t e m p 3 一t e m p l ) ( 1 e n t e m p 2 ) ：背景区的灰度均值 电子科技大学硕士学位论文：指纹识别算法研究与实现 t e m p = ( z o + z b ) 2 ： e n d 其中i n p u t m a t r i x 是前景区的灰度矩阵。通过上述方法可以得到比较理想的 全局分割阀值。因为经过方向滤波增强后，前景区和背景区的对比度非常明显， 采用全局分割阀值足可得到较满意的二值化图像，如图2 1 0 ： 2 2 3 细化 图2 1 0 二值化指纹图像与原始图的比较 指纹图像二值化后，仍然具有一定的宽度。但是指纹识别只对纹线的走向 感兴趣，不关心它的粗细，为了压缩数据和有利于提取特征，需要对指纹图 像进行细化。细化是删除指纹图像边缘的像素，使纹线只具有一个像素的宽 度，这种从指纹图像中提取“骨架”的方法称为细化。 图像细化算法的种类非常多，已有的具有代表性细化算法有基于数学形态 学为基础的算法“”“”、模拟人眼找纹线中点的所谓扫描算法“”、r o s e n f e l d “” 的并行细化法等。基于数学形态学的细化算法、r o s e n f e l d 的并行细化法等 的主要优点是纹线的拓扑结构和细节特征保持很好，但由于采用迭代运算和 大量的判决条件，比如，即使是只有一个像素没有细化，也会重复一次迭代， 做许多无谓的判别，这样算法的速度往往难以令入满意；同时，由于扫描先 后的影响，往往引起较明显的纹线吞食现象，纹线的中轴性也较差。扫描细 化算法的主要优点是一次扫描即可找到纹线的中点，细化速度快，纹线的中 轴性好；缺点是对叉点的细节保持性不强。 一般来说，考虑采用或开发某种细化算法至少应考虑以下几个因素： 电子科技大学硕士学位论文：指纹识别算法研究与实现 不破坏纹线的连续性 不引起纹线的吞噬现象 能够有效地保护纹线的细节特征 细化后的骨架宽度应仅有一个像素 细化后的骨架应尽可能靠近纹线的中心线 迭代可以迅速收敛 算法简单、速度快 针对上述要求，本文提出了一种基于方向场的指纹图像细化方法算法的基 本思路是利用扫描算法将脊线的垂直方向进行扫描，取中间的两个像素，这样 可以快速地将纹线宽度降低，节省细化时间，同时又尽可能地保持纹线的细节 特征；再用形态学细化算法一次迭代完成细化，最后对叉点处的细节进行修补。 具体步骤如图2 1 1 所示( 放大处显示对叉点修补前后的细节差异) ： 方向场形态学细化 纹线修补 图2 1 1 本文细化算法的流程图 这种细化算法既能保持纹线的拓扑结构和细节特征，又能获得如扫描算法 的光滑纹线，并且细化时间也比形态学细化算法减少一半以上。值得注意的是 向滤波是指纹图像增强的重要手段，因此，方向场信息通常是a f i s 中不可缺 少的，采用基于方向场的方法进行细化，不会额外地增加整个a f i s 的时间。 电子科技大学硕士学位论文：指纹识别算法研究与实现 2 2 4 特征提取 如前所述，指纹图像包含很多细节信息( m i n u t i a e ) ，有c o r e 、b i f u r c a t i o n 、 r i d g ee n d i n g 、i s l a n d 、d e l t a 、p o r e 、c r o s s o v e r 等。但要将这些细节信息完 全区别并提取出来，在提取算法的设计和实现上都相当困难，而且提取精度也 无法保证，目前常用的细节特征是美国联邦调查局( f b i ) 提出的细节点坐标模 型，它利用端点和叉点这两种关