（模式识别与智能系统专业论文）基于大规模指纹库的指纹识别算法研究.pdf

中文摘要 生物识别技术，根据生理特征或行为特征对个人身份进行鉴别，比传统的身 份认证技术更加安全可靠，同时使用方式也更富于人性化。指纹识别是生物识别 中应用最早，准确率最高，使用最为方便的技术，越来越广泛地被人们所使用。 本文的目的是设计一套指纹识别算法，该算法主要针对指纹识别系统中指纹 库规模较大的情况，可以使自动指纹识别系统在满足一定可靠性的前提下，具有 很高的实时性和易用性。因此该识别算法应该具有较低的复杂度，较快的运算速 度，从而满足实时性的要求。 本文探讨了现有指纹识别算法的不足，针对指纹库规模较大时，指纹识别相 当耗时的特点对预处理算法、分类算法和匹配算法作了相应的改进，并在m a t l a b 下对部分算法进行实现，通过实验证明了算法的实用性。 在自动指纹识别算法方面，本文作了以下几个方面工作： 1 、改进了传统伪特征点滤除算法中阈值的选取方法，采用自动阈值选取， 阈值因人而异，为滤除算法提供了可靠的标准。 2 、对指纹分类做了全面的讨论，指出了基于奇异点的指纹分类方法的不足， 提出了将奇异点信息和指纹纹线总体几何形状综合运用的指纹分类方 法。 3 、将指纹的匹配分成粗细两个等级依次进行。在第一级匹配中，利用r o i 的思想，通过统计r o i 中端点和分叉点的个数对指纹进行粗匹配，大大 节省了匹配算法的运算时间。在第二级匹配中，利用基于可变限界盒的 指纹匹配方法，在一定程度上解决了指纹非线性形变的问题。 4 、在参考点定位方面，充分利用了脊线信息并且通过计算两个参数和的最 小值来确定参考点，参考点定位快速准确。 本文的研究成果将为进一步开发具有商业价值的自动指纹识别系统提供必 要的理论基础和技术手段。 关键词：大规模指纹库指纹预处理指纹分类参考点定位可变限界盒 a b s t r a c t b i o l o g yi d e n t i f yt e c h n i q u eb a s e so nt h ep h y s i o l o g i c a lo rb e h a v i o rc h a r a c t e r i s t i c s ， i ti d e n t i f i e si dm o r es a l t ya n ds h o w sm o r ec o n v e n i e n c ei ns t u d ya n du s e f i n g e r p r i n t r e c o g n i t i o nt e c h n o l o g yi st h ep i o n e e rt e c h n i q u ei nb i o l o g yi d e n t i f yf i e l d ，i th a st h e m o s tv e r a c i t ya n d c o n v e n i e n c y , s ot h a ti ti su s e di nm o r ea n dm o r ed o m a i n s t h ea i mo ft h i sp a p e ri st od e s i g naf i n g e r p r i n tr e c o g n i t i o na r i t h m e t i cw h i c hi s b a s e do nt h el a r g e - s c a l ef i n g e r p r i n td a t a b a s e a f t e rs a t i s f i n gt h er e q u i r e m e n to f r e l i a b i l i t y , t h es m a l lf i n g e r p r i n tr e c o g n i t i o ns y s t e mm u s tr e a l i z et h ef a s tr e c o g n i t i o n a n dh a v em o r ec o n v i n e c et oh u m a n 。t h ea r i t h m e t i cm u s th a v el o w c o m p l i c a t i o n ，h i g h o p e r a t i o nr a t e ，s oi tc a nb ec o n t e n tw i t hr e a lt i m ed e m a n d s t h es h o r t c o m i n go ft h ee x i s t i n gf i n g e r p r i n tr e c o g n i t i o na r i t h m e t i ch a sb e e n d i s c u s s e d b a s e do nt h ec h a r a c t e r i s t i co fl a r g e s c a l ef i n g e r p r i n td a t a b a s ei nm a t c h i n g t i m e ，s o m ei m p r o v e m e n t st ot h ee x i s t i n gp r e v i o u sp r o c e s sa r i t h m e t i c ，p i c k - u pm i n u t i a a r i t h m e t i c ，f i n g e r p r i n tm a t c h i n ga r i t h m e t i ch a v eb e e nm a k e d t h e nt h ea r i t h m e t i ch a s b e e nc a r r i e do u ti nm a t l a b t h r o u g he x p e r i m e n t ，i t sr e l i a b i l i t ya n de f f i c i e n c yh a sb e e n v a l i d a t e d s o m ea s p e c t so fw o r ka b o u ta u t o m a t i cf i n g e r p r i n tr e c o g n i t i o na r i t h m e t i ch a v e b e e n d o n e ： 1 t h ee x i t i n ge l i m i n a t i o na l g o r i t h n ao ff a l s ef e a t u r e si nt h ec h o o s i n go f t h r e s h o l d h a sb e e ni m p r o v e d t h ed i f f e r e n tt h r e s h o l dh a sb e e nc h o o s e db a s i n go nd i f f e r e n t p e r s o n a u t o m a t i ct h r e s h o l dh a s b e e nu s e db e f o r et h ee l i m i n a t i o nf a l s ef e a t u r e s 。i th a s p r o v i d e dar e l i a b l ec r i t e r i o nf o rt h ee l i m i n a t i o na l g o r i t h mo ff a l s ef e a t u r e s 2 t h em e t h o do ff i n g e r p r i n tc l a s s i f i c a t i o nh a sb e e na n a l y z e d 。t h es h o r t a g eo f t h ep r e v i o u sc l a s s i f i c a t i o nm e t h o dw h i c hb a s e so ns i n g u l a rp o i n t sh a sb e e np o i n t e d o u t an e wc l a s s i f i e dm o t h e dw h i c hi n t e g r a t e st h es i n g u l a rp o i n t sa n dt h er i d g e so ft h e f i n g e r p r i n th a sb e e nc r e a t e dt oc l a s s i f yt h ef m g e r p r i n t 3 t h ef i n g e r p r i n th a sb e e nm a t c h e db yt w os t e p s t oa b t a i nh i 曲o p e r a t i o nm t e ， i nt h ef i r s ts t e p ，ar o ii nt h ef i n g e r p r i n th a sb e e nm a r k e da n dt h e nt h en u m b e ro f e n d i n ga n db i f u r c a t i o ni nr o ih a sb e e nc a l c u l a t e ds e p a r a t e l yt oa c h i e v ec u r s o r y m a t c h i nt h es e c o n ds t e p ，t h ec h a n g e a b l es i z e db o u n d a r yb o xw h i c hh a v em o r er o b u s t o nn o n l i n e a rt r a n s f i g u r eh a sb e e nu s e dt or e a l i z et h ea c c u r a t em a t c h 。 4 t h ei n f o r m a t i o no ft h ef i n g e r p r i n tr i d g e sh a sb e e nm a d eg o o du s et ol o c a t et h e r e f e r e n c ep o i n t b yc a l c u l a t i n gt h em i n i m u ms u mo ft h et w op a r a m e t e r s ，r e f e r e n c e p o i n th a sb e e nl a c a t e df a s ta n da c c u r a t e l y a d v a n c e dt h e o r ya n dt e c h n o l o g yf o rt h ea p p l i c a t i o no fa u t o m a t i cf i n g e r p r i n t r e c o g n i t i o ni nc o m m e r c i a lf i e l dh a sb e e np r o v i d e di nt h i sp a p e r k e y w o r d s ：l a r g e s c a l ef i n g e r p r i n td a t a b a s e ，p r e v i o u sp r o c e s s ，f i n g e r p r i n t c l a s s i f i c a t i o n ，r e f e r e n c ep o i n tl o c a t i o n ，c h a n g e a b l es i z e db o u n d a r yb o x 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他入已经发表 或撰写过的研究成果，也不包含为获德苤盗蠢堂或其他教育机构的学位或证 书而使用过的材料。与我。同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 签字日期：砷呵 年月倍日 学位论文版权使用授权书 本学位论文作者完全了解墨注盘望有关保留、使用学位论文的规定。 特授权蕉鲞基茎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：常蕊 导炒签名：吾以b 签字曰期：汐呵年，月f g 匿 签字圜期：魂7 年月，箩尽 第一章绪论 1 1 生物特征识别技术概述 第一章绪论 传统的身份鉴别方法通常转化为鉴别一些表示个人身份的事物，包括钥匙、 证件、用户名、密码等。这些传统的身份鉴别方法存在明显的缺点：个人拥有的 物品容易丢失或被伪造，个人的密码容易遗忘或记错。更为严重的是这些系统无 法区分真正的拥有者和取得身份标识物的冒充者，一旦他人获得了这些身份标识 事物，就可以拥有相同的权力。所以，传统的以密码为特征的身份识别技术也越 来越难以满足高安全性的要求。 生物识别技术【1 4 】指通过计算机利用人体固有的生理特征或者行为特征来进 行身份鉴定的过程。生理特征与生俱来，多为先天性的，行为特征则是习惯使然， 多为后天形成，生理和行为特征统称为生物特征。由于生物特征识别技术根据生 理特征或行为特征对个人身份进行鉴别，它与生俱来就比传统的身份鉴别技术更 加安全可靠。它的高安全性主要来源于： 1 每个人的生理特征或行为特征都是独一无二的； 2 生物特征难以被窃取、复制和伪造； 3 进行生物特征识别时，待鉴别的个人必须位于物理现场，而且生物特征 便于管理，不会遗失也无需记忆。 由于生物特征本身与传统的密码等身份鉴别相比，具有很大的优点，因此得 到了广泛而深入的研究和应用。出于反恐、刑侦、信息安全、金融安全等多方面 的需要，生物识别技术的研究和应用得到了世界各国前所未有的重视。 典型的生物特征识别系统可以以图l l 的形式来表示，逻辑上包括两个模 块：注册模块和识别模块。在注册模块中首先登记用户的姓名，通过生物特征识 别传感器得到用户的生物特征信息，然后从获取的数据中提取出用户的特征模 式，创建用户模板，存储在数据库中。在识别模块中，同注册过程一样获取用户 的生物特征信息，提取特征模式，然后与事先注册在数据库中的模板相匹配，检 验用户的身份。 第一章绪论 圈l i 生物特征识别系统的基本结构 y e 洲。 目前较常用来进行身份鉴别的生物特征有：面像、指纹、虹膜、声纹、手形、 签名等。基于这些特征，人们已经开发了面部识别、指纹识别、虹膜识别、语音 识别、手形识别、签名识别等多种生物识别技术。每种生物特征识别技术都有其 自身的优缺点，对于常用生物特镬技术的识别可靠度、可否一对一比对、可否一 对n 比对、采集设备的价格和采集设备的体积五个方面的比较如表l l 所示。 表1 - l 常用生物特征识别技术比 类型识别可靠度可否i ：l 比对可否l ：n 比对采集设备价格采集设备体积 指纹很好是是较低很小 人脸一般 是 否 低 较小 虹膜 很好 是是高较大 视网膜很好是是高较大 签名一般是否低较小 声音 一般 是否极低很小 在实际中，需要根据需求领域的不同，成本的离低，实用性的大小等诸多方 面综合考虑，选取适合的识别技术。 生物特征识别技术为这个信息社会日益加剧的安全需求提供了一个很好的 解决方案。随着生物特征识别技术的不断改进，生物特征传感器价格的不断下降 戳及人们接受程度的不断提高，生物特征识别技术必定会作戈一种基本的身份识 2 第一章绪论 别手段而得到广泛的应用。 1 2 本文的研究背景和意义 1 2 1 研究背景 本课题来源于对考勤系统的改进预研项目。 目前使用的考勤系统主要为脱机打卡的方式，根据卡的类型，又可以分为纸 片式和磁卡式两种。纸片式考勤的数据不易数字化，无法与企业的工资系统等财 务软件配合使用；而磁卡需要员工携带，易于遗失。而且，两种方式都难以杜绝 代人考勤等舞弊现象。因此，传统的考勤方式已逐渐不再满足现代企业管理的要 求。有一部分考勤系统已经使用了指纹识别算法，但这些考勤系统还难以达到速 度和精度的一个好的平衡点，因此设计一个既准确又快速的指纹识别算法应用于 考勤系统中是非常必要的。 1 2 2 识别技术的选择 随着世界各国对生物识别技术重视程度的日益加深，生物识别技术也得到了 前所未有的发展，指纹、人脸、虹膜、声纹、d n a 、手形等识别技术得到广泛 的开发和应用，为基于生物特征识别技术的考勤系统的进一步研究提供了一个良 好的开发环境和理论基础。 虽然生物特征识别技术有许多种识别方法，但综合以下因素考虑，选用指纹 识别技术应用于考勤系统中： 1 指纹识别作为识别技术已经有很长的历史【5 1 。作为发展时间最长、应用 范围最广也最成熟的生物识别技术，指纹识别系统得到了越来越多的人的认同。 2 自动指纹识别具有许多独到的信息安全优点： ( 1 ) 每个人的指纹是独一无二的，并且它们的复杂度足以提供用于鉴别的 足够特征； ( 2 ) 每个人的指纹是相当固定的，较难发生变化； ( 3 ) 读取指纹时，用户必需将手指与指纹采集头相互接触，与指纹采集头 直接接触是读取人体生物特征最可靠的方法。 3 自动指纹识别更重要的是还具有很高的实用性、可行性： ( 1 ) 扫描采集指纹的速度很快，使用非常方便； ( 2 ) 指纹采集头可以更j d , 型化，并且价格会更加的低廉； 第一章绪论 ( 3 ) 指纹识别中使用的模板不是最初的原始指纹图，而是由指纹图中提取 的关键特征，这样系统对模板库的存储量较小。 当然，指纹识别技术也有其自身的缺点： 1 某些人或某些群体的指纹因为指纹特征很少，故而很难成像； 2 每一次输入指纹时用户都会在指纹采集头上留下的指纹印痕，而这些指 纹痕迹有可能会被复制。 尽管如此，随着识别技术的发展，指纹识别仍将是最方便、可靠、非侵害和 价格便宜的生物识别技术解决方案，对于广大市场的应用有着很大的潜力。 1 2 3 本文研究的意义 指纹技术的成熟使指纹考勤系统成为可能。指纹考勤技术的最大优势就在于 其不可替代性，从根本上杜绝了代打卡现象的发生，保证了企业考勤管理的公证 性、严肃性、纪律性。员工也不必随时携带磁卡，只使用自己的指纹就可以完成 考勤的注册和登录工作，实现了真正意义上的考勤系统的现代化转变。这种转变 并不需要从硬件上给企业带来操作上的门槛。用户所需要的是在传统的考勤系统 上外接一个采集器，然后安装指纹识别算法的软件，用手指按一下指纹采集器即 可实现。 为了实现对考勤系统的改进，本文的目标是提出一个快速准确的指纹识别算 法。该算法不仅可以用于现代化考勤系统的改进，还可以用于以指纹为“身份代 码”的其他具有大规模指纹库的指纹识别系统中。 1 3 本文研究的主要内容 本文的最终目标是建立一个基于大规模指纹库的指纹识别算法，实现以指纹 为“身份代码 的功能。系统的目的是实现实时准确的比对，因此在保证识别率 要求的前提下，主要强调识别算法应具有较快的运算速度和较低的复杂度。 针对这一目标，本文研究了现有的指纹识别算法，并且根据实际需要，对现 有算法做出了改进。具体地说，本文研究主要包括以下几个方面的内容： 1 详细讨论了指纹的预处理技术： ( 1 ) 选用“最小平方估计 的方法求取指纹的块方向图，并通过低通滤波 得到了一个平滑的方向图，为以后的识别工作打下了良好的基础； ( 2 ) 采用傅立叶变换对原始指纹图像进行增强，并使用了分离滤波器和平 均滤波器进一步修补指纹纹线。算法不仅满足了系统实时性要求，也达到了很好 4 第一章绪论 的增强效果； ( 3 ) 采用改进了的局部自适应阈值法，充分利用了指纹的方向信息，二值 化后的线条平滑，对断裂的指纹有一定的连接作用； ( 4 ) 采用了改进的o p t a ( o n e p a s st h i n n i n ga l g o r i t h m ) 细化方法，获得了 较好的细化结果。 2 对于指纹库规模比较大的指纹识别系统( 如指纹考勤系统) ，如果单纯的 采用l ：1 循环匹配的方法，将大大影响匹配的速度。在传统的指纹识别系统中加 入了分类的模块。本文讨论了基于奇异点的指纹分类方法和基于指纹纹线总体几 何形状的指纹分类方法的优缺点，在此基础上提出了基于奇异点和指纹纹线总体 几何形状的综合指纹分类方法。 3 本文重点研究了指纹匹配阶段的算法： ( 1 ) 直接从细化的二值图像中利用8 邻域判定法进行特征提取； ( 2 ) 在对伪特征点进行滤除时，改进了阈值选取的方法，使阈值更加符合 实际情况，有效地完成了特征点提取后的处理工作； ( 3 ) 改进了参考点定位算法，不仅充分利用了脊线信息而且减少了参考点 定位的处理时间； ( 4 ) 提出了二级指纹识别算法：在第一级中利用基于r o i ( r e g i o no f i n t e r e s t ) 的思想对指纹进行初匹配，大大节省了匹配的运算时间；第二级匹配在基于图像 校准的点模式匹配法中采用了可变大小的界限盒，改进了固定大小的界限盒的不 足。 第二章自动指纹识别系统 第二章自动指纹识别系统 2 1 自动指纹识别系统原理 自动指纹识别系统睁i o 】( a u t o m a t e df 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 ) 己经被广泛应用。除了传统公安领域的应用，自动指纹识别系统还可以 应用于计算机操作系统的用户识别、智能i c 卡的双重确认、雇员的身份鉴定以及 家用电子门锁等许多方面。 不同应用领域的自动指纹识别系统，需要满足不同的性能要求。用于罪犯身 份鉴定的指纹识别系统，对可靠性要求较高。而一般的指纹识别系统对可靠性要 求并不是很高，其设计要求具有很高的实时性和易用性，因此识别算法应该具有 较低的复杂度，较快的运算速度，从而满足实时性的要求。所以在选择识别算法 之前应该充分考虑到识别系统在可靠性、实时性、有效性等方面不同性能的要求。 本文的指纹识别算法主要是针对诸如指纹考勤系统等指纹库规模较大的指 纹识别系统的，这类自动指纹识别系统对可靠性要求较低。由于指纹库规模较大， 识别速度是最关心的问题，因此系统主要强调的是实时性和易用性。考虑到以上 需要，本文采用的自动指纹识别系统框图如图2 1 所示。 图2 1a f i s 的系统流程图 一个较为完善的自动指纹识别系统的核心部分主要由指纹图像采集、图像预 处理、特征提取、分类和匹配等部分组成。为了使系统能够实时、快速地完成识 别任务，要求构成该系统的各个模块能够彼此良好地衔接起来，所以每个部分涉 及的算法必须高效、省时，既要完成自己的任务，又要为后面提供可靠、方便的 数据，使整个系统的性能提高。 6 第二章自动指纹识别系统 2 1 1 指纹图像输入 a f i s 系统中获取指纹图像【1 1 】一般采用两种方式：光学扫描采集方式和固体 传感器采集方式。 光学扫描采集指纹图像依据的是光的全反射原理( f t 取) 。当手指放在棱镜 上时，手指的脊和棱镜相接触而手指的谷和棱镜不相接触，激光以一定的角度照 射棱镜产生全反射，由c c d ( 电荷耦合装置) 阵列接收反射光线，并获取指纹图 像。固体传感器采集图像时，利用手指放在传感器表面，传感器感受接触点所改 变的电容器电压来获取指纹图像的。固体传感器与光学扫描相比具有体积小、集 成度高、数字化等优点，但其采集范围较小，而光学扫描在采集范围上受限较少。 本文所采用的是杭州中正生物认证技术有限公司生产的指纹仪，采集方式属 于固体传感器采集。 2 1 2 指纹图像的预处理 经指纹扫描器采集的原始图像不可避免地含有大量的噪声和对比度不统一 等缺陷，为了减少后续特征提取算法的复杂度，指纹图像的预处理 1 2 - 1 4 j 是必不可 少的部分。将采集到的指纹灰度图像通过方向图计算、图像滤波、二值化、细化 等操作转化为单个像素宽的脊线线条二值图像。然后，基于此细化二值图像对指 纹的中心参考点以及细节特征点等特征进行定位提取，特征信息提取的方法不 同，所采用的预处理方法也会不同。 指纹图像预处理是自动指纹识别系统的基础，是进行指纹特征提取和指纹识 别的必要前提。 2 1 3 指纹图像的特征提取 经过预处理后的指纹图像通过相应的处理算法来提取指纹的特征【1 5 1 。 指纹共有两类几何特征：总体特征和局部特征。 1 总体特征 总体特征是指那些用人眼直接就可以观察到的特征，包括：基本纹路图 案、模式区、核心点( c o r e ) 、三角点( d e l t a ) 以及纹数等。 ( 1 ) 基本纹路图案：指纹的图案都是基于三种基本图案，如图2 2 所示。 基本纹路图案为指纹提供了分类的依据。 第二章自动指纹识别系统 震圈凰 ( a ) 环型( b ) 涡型( c ) 拱型 图2 2 指纹的三种基奉图案 ( 2 ) 模式区：指纹图像r 包括了总体特征的区域，它是指由典型线围绕而 成的指纹区域，典型线是指指纹中形成圆形或环绕趋势的最外层纹线， 即从模式区就能够分辨出该指纹是属于哪一种类型的； ( 3 ) 核心点：位于指纹纹路的渐进中心； ( 4 ) 三角点：可能是从核心点开始的第一个分叉点，或者是断点、孤立点、 纹路的折转处或者是两条纹路的会聚处； ( 5 ) 纹数：指模式区内指纹纹路的数量。即指纹的纹数为连接核心点和三 角点的连线与指纹纹线相交的数量。 指纹的模式区、核心点，三角点、纹数如图2 3 所示。 e# o ! 角点 纹数 图2 3 指纹的模式区、核心点、三角点、纹数图例 2 局部特征 局部特征即指纹上的细节特征。两枚指纹经常会具有某些相同的总体特 征但它们的局部特征却不可能完全相同。正是这些细节特征点提供了指纹 唯一性的确认信息。 指纹上的细节特征点有四种不同的特性：特征点的类型、特征点的方向、 特征点处纹线的曲率和特征点的位置。方向是指特征点灰度连续的方向。曲 第二章自动指纹识别系统 率描述特征点处纹路方向改变的速度。位置表示特征点的位置，通过( x ，y ) 坐 标来描述，可以是绝对的，也可以是相对于参考点或特征点的。 细节特征点的类型大致可以分为以下六种，如图2 4 所示： ( 1 ) 端点( e n d i n g ) ：一条纹路在此终结。 ( 2 ) 分支点( b i f u r c a t i o n ) ：一条纹路在此分成为两条或更多条纹路。 ( 3 ) 分歧点( r i d g ed i v e r g e n c e ) 两条平行的纹路在此分开。 ( 4 ) 孤立点( d o to ri s l a n d ) ：一条特别短的纹路，以至于成为一点。 ( 5 ) 环点( e n c l o s u r e ) ：一条纹路分开成为两条之后，立即又合并成为一条 而形成的一个小环。 ( 6 ) 短纹( s h o r t r i d e ) ：一段较短但不至于成为一点的纹路。 ab - 卜一 - 一- - 弋 y 图2 4 指纹特征的六种类型 要区分任意两枚指纹仅仅依靠全局特征是不够的，还需通过局部( 细节) 特 征的位置、数目、类型和方向才能唯一确定。 特征点的真伪将直接影响匹配的效果，因此特征提取后还要进行后处理 ( p o s t - p r o c e s s i n g ) ，后处理的目的是为了消除虚假特征点，即伪特征。 指纹的特征很多，没有必要一一提取。在本文中，根据选定系统的实际需要 来提取核心点、三角点、分叉点和端点等特征，其提取方法将在第四章和第五章 分别叙述。 2 1 4 指纹图像的分类 在指纹数据库中，指纹分类提供了一个重要的索引机制。一个准确而一致的 分类能够极大地减少大数据库内指纹匹配的时间。对于大型指纹库来说，分类环 节是必不可少的。在1 8 9 9 年，e d w a r dh e n r y 和他的两个助手建立了指纹分类的 “h e n r y 系统”【1 6 】。h e n r y 系统将指纹分类成三个主要的类型：( i ) 环型、( 2 ) 涡 型、( 3 ) 拱型。每一种类型可进一步划分为超过二十种类型的指纹。联邦调查局 ( f b i ) 沿用t h e n r y 分类系统，但只使用了八种不同类型的指纹进行识别：放射 ( 挠骨) 环型( r a d i a ll o o p ) 、尺骨环型( u l n a rl o o p ) 、双环型( d o u b l el o o p ) 、中 心口袋环型( c e n t r a lp o c k e tl o o p ) 、平拱型( p l a i na r c h ) 、尖拱型( t e n t e da r c h ) 、 第二章自动指纹识别系统 普通涡型( p l a i nw h o r l ) 和意外类型( a c c i d e n t a l ) 。由于这些指纹类型具有小的 类阆可分性，设诗一个具有嘉准确性的夕类分类器是菲常困难的。因瑟，大多数 自动化系统将指纹类型的数目减少到h e n r y 分类系统所定义类型的一个子集。例 如，学术研究机构典型地关注于包括旋涡型、双环型、左环型、右环型、拱型和 尖拱型等六种类型的分类方案的研究，而商业系统典型地提供了放射( 挠骨) 环 型、尺骨环型、双环型、涡型、意外类型和拱型等分类f l 。7 1 。 本文中将指纹分为六糖类型，以便和其缝算法毙较，讨论算法瓣性能。本文 将在第四章对分类算法详述。 2 1 5 指纹图像的匹配 指纹匹配作为指纹识别的核心技术之一，是自动指纹识别系统设计中的热点 和难点。它在指纹特征提取之后，是自动指纹识别的最后一步，也是非常关键的 一步。匹配结果的正确与否将最终决定整个系统的性能好坏。 前面的各阶段，包括指纹图像预处理、特征提取和后处理，都是为获得好的 匹配结果做准备的。经过以上处理，得到一系列包含原有指纹图像信息的指纹特 征点。指纹涯配要解决的闯题就是将当前输入的测试指纹图像特征点与事先存在 数据库中的模板指纹图像特征点进行比对，判断两幅指纹图像是否来自同一个手 指。 指纹图像的匹配问题将在第五章中详述。 2 2 系统可靠性的衡量标准 在指纹匹配算法中，对予每种类型的决定都有正确( t r u e ) 和错误( f a l s e ) 两种可能的结果，相应会有四种输出结果：( 1 ) 一个身份正确的人被接受，( 2 ) 一今身份正确的人被拒绝，( 3 ) 一个身份错误的入被燕绝，( 4 ) 一个身份错误盼 人被接受。其中( i ) 和( 3 ) 是正确的决定，( 2 ) 和( 4 ) 是错误的决定。 识别率是指纹识别系统特定的衡量指标f 嘲，它一般有两部分构成：错误拒绝 率和错误接受率。如果来自不同手指的两个指纹被判断匹配，则为错误接受( f a l s e a c c e p t a n c e ) ，发生错误接受的次数与所有不同手指的匹配次数的比值被定义为 错误接受率f a r ( f a l s ea c c e p t a n c er a t e ) 。如果来自同一手指的指纹被判断不匹 配，则为错误拒绝( f a l s er e j e c t i o n ) ，发生错误拒绝的次数与所有相同手指的匹 配次数酶泷僮被定义为错误拒绝率f r r ( f a l s er e j e c t i o nr a t e ) 。以f a r 为横坐标， f r r 为纵坐标，将不同识别率下所对应的f a r 和f r r 绘制成曲线，称为r o c 1 0 第二章自动指纹识别系统 ( r e c e i v e ro p e r a t i n gc u r v e ) o 图2 5 的r o c 曲线给出f a r 和f r r 之间的关系，曲线上的点表示在某个给定 的匹配阈值下得到的错误拒绝率和错误接受率。 在设计应用系统时，要考虑整体性能，使r o c 曲线尽量整体下降。同时要考 虑到在实际中f r r 和f a r 是成反比的。在确定匹配阈值时，应根据具体应用情况进 行考虑：在刑事应用中，需要把可能的嫌疑人都找出来，这时应尽量减小错误拒 绝率，所以错误接受率非常高；而对于高度保密应用来说，错误接受造成的损失 非常大，因此要求错误接受率很低。 f r r ( ) 褥话 翁湎 图2 - - 5r o c 曲线图 1 。，：j # a r ( i o g ) 霎 第三章指纹图像的预处理 第三章指纹图像的预处理 指纹图像由于按压时用力不均匀和手指表面干湿度不同等因素的影响，一般 都存在一定程度的指纹纹线间的粘连、模糊以及纹线断裂等现象。同时，从三维 人体指纹n - 维数字指纹图像的转换过程中，由于量化精度及扫描仪的非线性特 性等影响，都会不可避免地引入噪声。这些粘连、模糊、断裂以及噪声的存在将 严重影响指纹特征提取和识别匹配的准确性。因此在进行特征提取和匹配之前， 进行指纹图像的预处理，以增强图像的可识别性是非常必要的。 指纹特征是指由指纹脊线形成的某种构型，如端点、分叉点等构型。为了提 取这些特征，需要将指纹图像处理为二值细化图f l9 1 ，这一过程即为指纹图像的预 处理过程。预处理是指纹自动识别过程中的第一步，它的好坏直接影响着指纹自 动识别系统的性f l 彦t 2 0 1 。指纹预处理的各个环节之间具有很强的相关性，本文对指 纹预处理的全过程进行了系统的研究，将预处理过程分为以下四个基本步骤：方 向场的计算、图像增强、二值化和细化。整个图像预处理流程如图3 一l 所示。 鼍。最。 7 ，二 ：? j 0 堑j 一尊! ! 夔 尊轻，t 一一i “：4 细 赉： 一化 j 弘 向j 图； 。二， 场 像 值 j 细j 值7 j 纹 的+增1 化v ： “化； 一图+ 图二：计强1 i 于像， ：像“ 算， ：r 。 ：， ，5 ：二：一一0 争：，i r 葛， 图3 1 指纹图像预处理流程图 预处理通常是基于指纹方向图来进行的，方向图的每一个元素代表了指纹图 像中某个给定像素点( 像素区域) 的纹理方向。由于许多图像处理方法中都用到 了指纹图像的方向图，而且方向图可以从原始灰度图像中得到，因此在预处理的 第一步就计算指纹图像的方向图，方便后续的操作。图像增强包括两个部分忙u j ， 首先是对原始图像进行增强，减弱噪声，增强脊和谷的对比度。然后再对整幅图 像滤波，消除指纹脊线间的断裂和粘连。图像二值化是提取经增强处理的指纹图 像的脊线，用“1 ”表示脊线上的点，“0 ”表示背景和谷线，从而把原始灰度图 像转化为二值图像。图像细化是进一步把二值指纹脊线细化为单像素宽度的骨架 1 2 第三章指纹图像的预处理 线，这是为了方便以后的特征提取。 3 1 指纹方向图的计算 指纹图像是一种具有一定纹路走向的多边有向图，纹理性和方向性是它区别 于其他图像的显著特征。方向图抽象了指纹脊线与谷线交错平行分布的特点，描 述了指纹图像中每一像素点所在脊线或谷线的切线方向，反映了指纹图像纹理结 构的本质，具有重要的意义。作为一种可以直接从原始灰度图像中得到的有用信 息，它的计算一直是指纹识别技术中必不可少的一步。 方向图分为两种：一种是点方向图，即把指纹图像中每一点的方向都表示出 来；另一种是块方向图，即把指纹图像均匀分割成若干块，仅表示出每一块中脊 线的大致方向。在实际处理中，经常使用的是块方向图，因为它比点方向图有更 强的抗噪性，而且求块方向图可以减少计算量，有利于模块化处理。 对于计算块方向图，一般是基于指纹各像素点的梯度进行计算获得比较精确 的方向。k a s s 和w i t k i n 提出了一种向量平方的方法，在“平方梯度向量法”中， 可以通过将梯度向量进行平方来消除方向向量互相抵消的现象。但是，此种方法 对原始图像中的每一点都求得一个方向角，没有充分地利用该点处的邻域信息， 使得此种方法抗噪声性能不好，求得的结果方向图比较凌乱。 本文使用的是“最小平方估计 的方法【2 i - 2 3 ，该方法对“平方梯度向量法 进行了改进。此种方法抗噪声性能较好。下面将对此种方法作较为详细的说明。 1 原始图像为厂，它在水平和垂直方向的梯度向量分别为：a 。，a ，。根据计 算的需要，梯度算子可以是简单的s o b e l 算子或复杂的m a r r - h i l d r e t h 算子。 2 此梯度向量组合成复平面中的方向向量，并且平方，得： 1 ，= p ，+ j a ，尸= a ，。一a ，。+ 歹2a ，a ， ( 3 1 ) 则，向量v 水平和垂直方向的分量分别为： v ，= a ，2 一a y 2 ( 3 2 ) v y = 2 ax 8y 如果采取将的比值简单的求反正切，那么就是“平方梯度向量法 的方 ，v i 法。但是，要使用该点附近邻域的信息来达到方向图平滑的效果，所以： 3 将原始图像厂分成w w ( 根据经验，w = 1 6 是一个比较合理的选择) 的 一系列不重叠的块，利用下式计算每一块( 中心点为( f ，) ) 的水平和垂直分量： 第三章指纹图像的预处理 圪o ，j ) = 2 a ，0 ，v p 多0 ，y ) ww ”7 1 ”7 一i o o ，) = 芝芝p ：0 ，v ) 一a ；0 ，v ) ) ( 3 3 ) 。”1 ”7 1 4 则每一块的方向定义为： 比小妒( 瑚) 4 ， 采用此种计算方法，所得的方向图效果好，而且计算量小。 为了得到更准确的方向，对方向图进行平滑，具体计算方法如下所示： 1 假设原始方向图为0 ，首先将矢量域转换成数量域，即对以和矽，做低通 滤波： 主= s i n ( 黢2 琵岩 5 ) 丸=d u ， 一 2 将所得的z ，y 分量通过一个低通滤波器后得： 11 苁( f ，歹) = 形0 ，v 溉( f + 材w , j + v w ) “一半一一半 半半 力( f j ) = 形0 ，v 域( f + z 鹏+ w ) 。：半v 孚 其中0 ， ，) 为幸坳大小的低通滤波器，一般取形0 ，1 ，) 为5 5 。 经低通滤波后的方向场0 为： 啪，= 妒 矧) 7 ) 3 、最后在每块内以块方向作为该块内所有像素点的方向。 使用了该方法后，指纹的块方向图变得相当准确平滑。 3 2 指纹图像的增强 由于指纹采集设备的不完善性，对于干、湿、脏、老化、磨损的指纹，往往 难以采集到清晰的图像，为了弥补指纹图像的质量缺陷，保证指纹后处理算法对 指纹图像具有足够的鲁棒性，图像增强步骤是十分必要的。 指纹图像增强算法，除了具有良好的增强效果之外，还应当在算法速度、鲁 棒性和稳定性方面也具有较好的特性，但是这几个性能指标通常是相互制约的。 1 4 第三章指纹图像的预处理 例如：a j w i l l i s 等人提出的低质量指纹增强算法，将图像分成3 2 x 3 2 的小块，然 后再作傅立叶滤波从而使指纹图像得到增强，这种算法的不足是没有利用全局信 息，从而导致增强效果没有达到最佳。l i nh o n g 等人将g a b o r 瘟波器用于指纹图像 增强，这种算法可以获得较好的增强效果，但缺点是速度太慢，不适于在线实时 处理。 考虑以上算法的优缺点，同时考虑到系统实时性的要求，本文采用傅立叶变 换来实现指纹的增强，然后再使用两种方向滤波器来进一步修补指纹纹线【2 4 1 ，详 细的过程如下： 1 将指纹图像分成w w 的图像块，把块中的每个像素都变换成复数形式表 示：a 4 - i b ，实部彳表示像素的灰度，虚部召为0 。 2 应用傅立叶变换公式，得到变换后的矩阵x = i y ： 戤+ ，= 薹w - - i 荟w - - io 。+ i b m ) e x p l 等( 阿+ n k ) l ( 3 8 ) 肘= oh = 曲l w j 3 对其作带通滤波，把低频与高频的噪声去掉。频率太低或者太高的都可 以被当做噪声，将这些频率对应的幅度置为0 。 k 协 毛。i f 黼( r a d i u 捃l p b a ，可以取d = 7 ，c = 5 ， b = 3 ，a = l ； 分离滤波器中，权值之间的关系为d + 2 c + 2 b + 2 a = 0 ，可以取d = 1 0 ， c = - 2 ，b = - 2 ，a = - 1 。 由公式( 3 。1 2 ) 求褥的像素点灰度值，0 ，歹) 可能夺子o ，也哥能大子2 5 5 ，所 以要通过公式( 3 1 3 ) 进行处理。 f 0f 。( i ，j f ) 0 f ”g ，歹) = ，o ，j f ) 其他 ( 3 。1 3 ) 1 2 5 5 f 0 ，歹) 2 5 5 3 3 指纹图像的二值化 指纹图像的二值化是指将增强后的灰度图变成0 1 取值的二值图像，以像素 值0 来量化脊线区域，以像素值2 5 5 量化谷线区域。在指纹识别时，只关心图像的 几何性质，两对它每个像素点豹具体获度值不感兴趣，图像的足何性质只与0 秘1 的位置有关。因此，二值化处理在保持了指纹的几何性质前提下，使后续的处理 变得简单，而且数据的压缩量很大。 二值化的传统方法就是阑值法，又可分为固定阈值法和局部自适应阂值法 江熨。 1 6 第二章指纹图像的预处理 固定阔值法就是采用固定的闽值对指纹图像进行= 值化但是不同的指纹图 像其灰度差异很大，即使是同一幅指纹图像其各部分的