（信号与信息处理专业论文）基于树状分类器的指纹识别算法研究.pdf

攘要 摘要 囊予捂纹驻爨窍静难一整巍不交往，激教密纹谖爨技术懿可行牲帮实霜蝗， 使得描纹识别成为最流行、最方便、最可靠的个人身份认诳技术之一。尽管在此 技术上融有多种成型产品，但由于指纹图的噪声、皮肤弹j 腱的非线性等因索，以 及诲多文献都困商渡裂益瑟未缀公开，理恕懿蠡动掺绞叁劝谖爨篓法菝然是一个 很困难的研究任务。 本论文建立了一套基于树状分类器的自动指纹识别算法。首先，基于指纹的 统计性特征，即奇弊点，对指纹避荦亍分类；然厢提取指纹的缨节点特征，从基于 缨节煮特征静系统中采取缮纹方翔强，著送行滤波、二篷纯、绸亿、缨节褥蔹提 取等处理；最后，缩合指纹的统计性特征做细节点匹配。在所构造的指纹识别系 统中的一些步骤中，提出了一些渐的方法： ( 1 ) 在臻纹墅豫瑗簸理零分，零论文对指纹方起銎诗募方法提遗了一耱改避算法， 并提出种新的基于方向图的指纹图像韵态闽值二值化方法。整个预处理方 法在保持特征点不丢失的基础上，很好的完成了指纹脊线提取的工作。 ( 2 ) 在指纹分类部分，本文提出了一种基于搬纹奇异点的分类方法，并采用改进 静p o j n c a r e 攒数法提取指绞静奇异煮。酸避方法中，p o i n c a r e 撵数孰方向图 上直接得到，肖着很好的抗噪性，而且计算简单，有利于正确分类。 ( 3 ) 在指纹细节点瓤配算法上，根据指纹的分兴信息，采用基于参考点的结构匹 鞑算法襄基予免疫算法憨煮模式嚣配霎浚，获褥了较磐鹃努类谈爨瞧姥。 作赣在p e n t i u m4 计算机上用v i s u a lc + + 实现了论文中所设计的掰肖算法， 实验结果表明，本文提出的新算法在很大程度上提高了图像的处理效果和分类结 果。本文的研究成襞慰自动指纹识别系统的设计具有重要躲参考价值。 关键词：自动指纹识别系统指纹图像预处理特征提取 树状分类特征匹配 a b s t r a c t d u et ot h eu n i q u e n e s sa n di n v a r i a b i l i t yo f f i n g e r p r i n t ，t h ea u t o m a t e df i n g e r p r i n t i d e n t i f i c a t i o ni s b e c o m i n g a na t t r a c t i v ea l t e r n a t i v et ot h et r a d i t i o n a lm e t h o d so f i d e n t i f i c a t i o n ，h o w e v e r , t h e r ei sm u c hs p e c i a ln o i s ei nf i n g e r p r i n ti m a g e s ，a n dm a n ) , a l g o r i t h m s a r en o to p e n e d , s 0a ni d e a la 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 n s y s t e m ( a f i s ) i ss t u la d i f f i c u l tr e s e a r c hs u b j e c t i nt h i sp a p e r , an e wa f i sb a s e do nt r e ec l a s s i f i e ri s p u tf o r w a r d f i r s t l y , t h e p r o p o s e d a f i sc l a s s i f i e st h ei n p u t f i n g e r p r i n t sb a s e d o nt h es t a t i s t i c a lf e a t u r e s ( s i n g u l a r p o i n t s ) 。s e c o n d l y , t h ef i n g e r p r i n tm i n u t i a ea r ee x t r a c t e d ，w h i c hc o n s i s t so fc o m p u t i n g t h eo r i e n t a t i o nf i e l d ，f i l t e r i n g ，b i n a r i z a t i o n ，t h i n n i n ga n do t h e rp r o c e s s i n gp r o c e d u r e s f i n a l l y , t h ef i n g e r p r i n ti s i d e n t i f i e db a s e do nt h em i n u t i a em a t c h i n gm o d u l e i nt h e p r e s e n t e d a f i s ，s o m en e w i d e a sa n d a p p r o a c h e s a r eb r o u g h tf o r w a r d ( 1 ) i nt h ep r e p r o c e s s i n g ，an e wm e t h o do f c o m p u t i n g o r i e n t a t i o nf i e l di sp r o p o s e d 。 a n db a s e do nt h eo b t a i n e do r i e n t a t i o nf i e l d ，an e w f i n g e r p r i n ti m a g eb i n a r i z a t i o n a l g o r i t h mi sp r e s e n t e d 、i md y n a m i ct h r e s h o l d w h i c hh a sg o o dc a p a b i l i t yo f n o i s er e s i s t a n c e ， ( 2 ) am o d i f i e df i n g e r p r i n tc l a s s i f i c a t i o nm e t h o di sp r o p o s e db a s e do nt h ef i n g e r p r i n t s i n g u l a rp o i n t s ，i nw h i c ht h es i n g u l a rp o i n t sa l ee x t r a c t e dw i t han e w p o i n c a r e i n d e xm e t h o d a n dt h en e wp o i n c a r ei n d e xi so b t a i n e d d i r e c t l y f r o mt h e o r i e n t a t i o nf i l e d c o m p a r e d 谢 1 1o t h e rc l a s s i f i c a t i o nf e a t u r e s i th a sa d v a n t a g e so f s i m p l i c i t yf o rc o m p u t a t i o na n d s u i t a b l ef o rc l a s s i f i c a t i o n 。 ( 3 ) f o rt h em i n u t i a em a t c h i n g as t r u c t u r em a t c h i n ga l g o r i t h m 、v i 也r e f e r e n c ep o i n ta n d a p o i n t - p a t t e r nm a t c h i n ga l g o r i t h m b a s e d0 1 1a r t i f i c i a li m m u n es y s t e ma l e d e v e l o p e d 、i t l lg o o dp e r f o r m a n c e a l lt h ea b o v ea l g o r i t h m sa l ei m p l e m e n t e dw i t hv i s u a le + + t h ee x p e r i m e n tr e s u l t s d e m o n s t r a t et h a tt h ep r o p o s e dn e wm e t h o d se n h a n c ep r o c e s s i n ge f f e c t so ff i n g e r p r i n t i m a g e sa n di m p r o v et h ec l a s s i f i c a t i o np e r f o r m a n c e t h er e s e a r c ha c h i e v e m e n t sh a v e i m p o r t a n t r e f e r e n c ev a l u e sf o rt h ed e s i g no f a na f i s 。 k e y w o r d s ：a u t o m a t e d f i n g e r p r i n t i d e n t i f i c a t i o ns y s t e m , p r e p r o e e s s i n g o f f i n g e r p r i n ti m a g e s ，f e a t u r e e x t r a c t i o n , t r e ec l a s s i f i c a t i o n ，f e a t u r em a t c h i n g 第一章绪论 1 1 1 生物识别技术 第一章绪论 1 , 1 生物识别与指纹识别技术简介 从古到今，身份识别一直是人类的重要需求。人们为了保护自身生命、财产、 信息等的安全，使用各种方法来识别目标人物的身份，从而给予不同的授权。最 原始且应用最为广泛的识别手段是机械钥匙。由于机械钥匙具有容易丢失、易复 制等缺陷，它的安全性和方便性一直受到人们的质疑。随着越来越多的电子设备 进入日常生活，各种密匙技术相继被开发和应用。目前，数字密匙主要包括智能 卡、身份号、口令等识别手段。然而，这些技术也不能让人高枕无忧，它们大多 只能在安全与方便之间徘徊，充分的安全从来没有实现过，而更好的安全总与更 大的不方便同时出现。随着网络与通信技术的飞速发展和人类物理以及虚拟活动 空间的不断扩大，现代社会对于身份识别的准确性、安全性、与实用性提出更高 要求。传统的身份识别方法已经远远不能满足这些要求，人们必须寻求更为安全 可靠、使用方便的身份识别新途径。于是，生物识别方法悄然兴起，并应运而生 为一种新的身份识别技术。 生物识别技术是利用人体生物特征进行身份认证的一种技术。生物特征是指唯 一的、可测量或可自动识别的的生理特征或行为特征。生理特征多为先天性的， 如指纹、眼睛虹膜、脸像等；行为特征则多位后天性，如笔迹、步态等。生物识 别以生物技术为基础，以信息技术为手段，将两大高新技术交汇融合为一体。 生物识别系统对生物特征进行取样，提取其唯一的特征并转化成数字代码，然 后将这些代码组合成特征模板，人们同识别系统交互时，系统获取其特征并与数 据库中的特征模板进行比对，以确定是否匹配，从而决定接受或拒绝该人。生物 识别系统一般不能像传统识别系统那样给出绝对的“对”或“错”的识别结果， 它往往会给出具有非常高可信度的相对判断，例如现在已有系统可以达到错误概 率仅为0 0 0 1 1 2 。 人类利用生物特征进行识别的历史可以追溯到古埃及人通过测量人体各部位 的尺寸来进行身份鉴别。现代生物识别技术始于2 0 世纪7 0 年代中期，由于早期 的识别设备比较昂贵，因而仅限于安全级别较高的特殊领域的身份鉴别认证。现 在由于科技的发展，电子设备成本不断下降，精度逐渐提高，生物识别系统逐渐 应用到门禁、企业考勤管理、安全认证等许多领域。 2蒸予麓靛分类器熬摆绞谖弱冀法骚究 理论上只要满足下面的条件，人的任何生理特征或行为都可以用作身份识别 ；( 1 ) 普遮性，即每个人郜拥有该特镊；( 2 ) 唯一性，鼯没有哪蕊个人拥有隧梯 懿该特 歪；( 3 ) 永久注，辩该特征不会箍靖阉蠢交毒乏；( 4 ) 可采集经，帮该特征 能够被定量的测量出来；( 5 ) 易实现性，包括资源消耗少，工作环境要求不苛刻； ( 6 ) 可接受性，即人们愿意接受这种识别方式；( 7 ) 难欺骗性，即冒充者很难通 过提供霰黪鬣教骧瑷裂系统。 目前已疑用来识别的嫩理特征有指纹、手形、黢形、虹膜、视网膜、手静脉、 面部温谱图镣；行为特征有签字、语啬镣。基于这熄特征，人们融经发展了多种 生物识别技术。指纹识剐是基于手指纹线所构成强象的唯一性和摊他性进行赛份 篷定。手澎识爱惫括掌纹鬻豫识嗣、熬个手掌豹手形识嗣、革个手指或两令手指 ( 食指、中指) 的指形识别，其中手彤和指形识别是利用手指的三维立体形状进 行识别。人滁识别主要针对脸部不易产生变化的部分进行图像处理，包括眼暇轮 藤、毅夤瘸潮嚣域戳及囔熬透缘区瑗嚣。薤骥谖裂穰溺太l 受薤膜终赛不交毪酾蓑 异性来识剐。同虹膜识别一样，视网膜识别可能是煅可靠、最值得信赖的生物识 别技术，但运用起来难度较大。语音识别通过分析语音的唯一特性例如发音的频 率，来识别谈话人。签名识别，也被称为签名力学辨谈，它建立程签名时的力发 上，分手厅笔瀚移动镶如鸯霸速度、压力、方向、班及臻粼豹长度， f i 虿j # 签名静鞠像 本身。 褒1 1 几种生物识别的性能比较 生物骛短独特蛙稳定注袋集注搽佟经接受撩瘦舞款骧瞧 指纹高高中等搿中端高 脸形低低高低黼低 手形中等中瘫中簿中中 蛭膜离中等证凝低离 手静脉 中中等 出由 中高 语音低低中等低商低 签名低酝离糕麓低 从以上几个方面可以赣到，相对于藏它生物识别技术，指纹识别不仅具有许多 独到的信息安全角度的优点，更重要的是还具有很舞的实用性、w 行性和非侵密， 并置徐格餐警， 总之，警物识别是目前最为方便与霞全的识别技术，并且生物识别产品均借助 计算机技术窳现，容易和安全、监控、管理系统整含，实现自动化管理。因此， 蕤藿生兹与髂患按寒弱陡这发聂及不叛融会，夔罄傣惠纯、数字纯季圭会的逐步形 成，特别是随整“9 1 1 ”事彳串厝人们对安众措施的普遮壤视和更离婺求，生物识辅技 第一章绪论 术的开发与应用将会掀起一个新的高潮。可以预见，越来越多的生物识别产品将 会出现在门禁控制、银行帐户、公安侦察、互联网安全、电子商务等各个领域。 1 1 2 指纹识别技术 人类手掌及其手指、脚掌及其脚趾内侧表面皮肤凸凹不平产生的纹路会形成 各种各样的图案。指纹就是手指内侧表面皮肤上的图案。不同人的指纹，即使同 一个人不同手指的指纹纹线走向及纹线的断点和交叉点等各不相同，也就是说， 每个指纹都是唯一的。另外，指纹不随年龄的增长发生变化，是终生不变的。依 靠这种唯一性和稳定性，可以把一个人同他的指纹对应起来，通过对他的指纹和 预先保存的指纹进行比较，就能验证他的真实身份。这就是指纹识别技术。 指纹用于身份鉴定的历史悠久。早在古叙利亚和中国，指纹鉴别就已经开始 应用。1 9 世纪初，科学研究发现了至今仍然承认的指纹的两个重要特征，一个是 两个不同手指的指纹纹脊的式样不同，另一个是指纹纹脊的式样终生不变。这个 研究成果使得指纹在犯罪鉴别中得以正式应用。早期的指纹识别依靠人工对比方 式进行。由于指纹结构的复杂性及对指纹识别要求的严格性，导致人工识别指纹 难度大、速度慢和识别准确性受专家经验制约，远不能适应实际工作的需要。2 0 世纪6 0 年代，随着计算机技术的诞生、发展与不断进步，图像处理与模式识别方 法的日臻完善，人们开始着手研究利用计算机来处理指纹。从那时起，自动指纹 识别系统( a f i s ：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 m m ) 在法律实施方面的研究 和应用在世界许多国家展开。2 0 世纪8 0 年代，个人电脑、光学扫描这两项技术的 革新，使得它们作为指纹取像的工具成为现实，从而使指纹识别可以在其他领域 中得以应用，比如代替i c 卡。2 0 世纪9 0 年代后期，低价位取像设备的引入及其 飞速发展，可靠的比对算法的发现为个人身份识别应用的增长提供了舞台。据统 计，到2 0 世纪末，全世界生物识别市场约为1 1 2 亿美元，其中指纹识别约为1 0 0 亿美元元1 2 j ，这标志着指纹识别是当前最成熟稳定，并且应用最广泛的生物识别技 术。 表1 2 中国指纹市场规模( 万元) 分类2 0 0 12 0 0 l2 0 0 32 0 0 4 在线传感器3 56 0】0 53 2 0 离线传感器 2 53 05 01 2 5 嵌入式系统 1 52 03 59 5 系统集成1 53 55 5 1 8 0 其他 1 01 01 03 0 合计1 0 01 5 52 5 5 7 5 0 麓于树状分类器的指纹识别算法研究 中国则是世界最大麴潜在指纹枣场，年增长遴察5 0 一钧嘲，远远麓予毽 界平均水乎。我国政麝主导基予指纹识别菝术静太跫项磊，魏；暂住证系统、社 会保险卡系统及新一代公民身份证系统等。很多国内企业引进指纹识别技术，更 多的经销、集成商开始介入指纹设备的生产制造。国内也有很多科研院所开展指 纹谖秀l 鼓拳静臻究。 与人工处理不同，现代指纹识别技术并不直按存储指纹的图像( 一是考虑到 隐私问题，= 是由于储存空间限制) ，而是记录从阁像中提取到的特征，指纹识别 算法最终都魉缝炎在委豫上找到并魄怼豢纹豹特征。因忿，慕予诗舅枕的鑫渤摇 纹识别系统主要涉及霞个功能：读取鞠像、特征箍敝、保存数据靼比对【2 】。一开始， 通过指纹读取设备取得阕像，并对原始图像进行初步处理，使之照清晰。接下来， 指纹识别软件建立指纹的数字表示特征数据。这是一种根据指纹类型、纹线断 点、交叉杰等结秘特薤褥錾数据静攀方肉转换，礴戮获捂绞转羧或特薤数豢键不 能从特征数据转换成为指纹，而两枚不同的指纹不会产生相同的特征数据。这些 数据通常称为模板，保存为数据库中的一条记录。最后，通过计算机模糊比较的 方法，把耀个撂纹熬模援送行e l 较，诗冀出它髑豹樱缎程度，瀑终褥到匿配缑莱。 结合舀渤指纹识剐系统的基本原瑷，可以总结出指纹识别技术之所以恍予其 他身份鉴定技术而被广滋采用的原因： 。 ( 1 ) 指纹是独一无二的，两人之间不存在着捆同的指纹； ( 2 ) 攒纹是穗当鍪宠豹，不会隧冬羚、毽藤拣凝靛交纯稳敬交； ( 3 ) 指纹样本易于聚集，难以伪造，便于开发，实用性强； ( 4 ) 锊个人十指的指纹皆不相同，可以利用多个指纹构成多熏口令，提高系 统匏安全瞧； ( 5 ) 搬纹识剐中使糟的模板并j # 激初的指纹豳像，而是由瀚像提取的关键特 征，使所需存储的信息擞减小，而且猩实现异地确认时，可以火大减少网络传输 负担，支持阏络功能。 可戳餐国，指纹谖鄹技术稿霹予其链谈爨方法有许多独鬟乏楚，具有缀离豹 实用性和可行性。因此，指纹识别成为最流行、最方便、最可靠的身份认证方式， 已经在社会生活的诸多方面得到广泛殿用。 1 2 自动指纹识别系统的构成 l 蓍文讲到，基于计算枕豹自动攒纹识别系统主簧涉及读取辫像、特征提敷、 僳存数据和托对等嚣个秘筢，该系统的瀛程框图翔黧1 1 掰示。它囊要由图豫输入、 预处理、特征提取、分类和匹配等五部分组成，其中预处理部分又可分为图像分 割、图像增碾、二值让釉姗讹笔几个赡勰一个桄销的喜衿识剥糕缔尊求能域：时、 第一章绪论 迅速、有效地完成其识别过程，这就要求：一方面，系统的每个组成部分所包含 的算法要快速、高效，既要很好地完成该模块的功能，又要耗时足够短；另一方 面，系统的各个部分要能够很好地衔接起来，前一部分要为后面提供尽可能理想 的数据，后一部分要充分利用前面的处理结果，使整个系统的性能得到提高。因 此，实际的指纹识别系统往往由于应用环境、系统规模、实现思路以及具体算法 的不同，而在系统整体框架上有所出入。例如，一般的小型应用，如家庭门禁、 指纹保险箱等，就不需要分类步骤；有的系统直接从原始指纹图像提取特征，则 特征提取算法比较复杂但并不需要二值化、细化等处理。 图1 1 自动指纹识别系统 下面对图1 1 所示自动指纹识别系统的各个部分做简单介绍。 ( 1 ) 图像输入 传统的指纹采集方法是用手指蘸上墨水或印油在纸上按压，然后用扫描仪摄 取。由于其严重的不可靠性，该方法己经被淘汰。随着光学仪器、传感器及数字 技术的发展，各种快速、精确、方便、小巧的采集设备得到应用。目前，主要是 使用光学扫描仪和固态阵列传感器进行采集。前者用激光照在手指上，然后用c c d 阵列摄取其反射光，由于反射光强随着指纹的脊和谷的深度不同而不同，因此可 以得到指纹图像。后者是用大量敏感元件组成的固态阵列芯片，它们采用电容传 感、热敏传感或其他传感技术，通过感受按压指纹的压力、热度等特征来摄取指 纹。近年来，又出现了其它一些新型的指纹采集设备，如超声波指纹采集器，它 是基于指纹的脊和谷的深度对超声波的不同反射原理而工作的。这些设各中，光 学扫描仪因其技术比较成熟、性价比比较高而得到广泛应用。 本文试验所使用的是d i g i t a lp e r s o n a 公司的u a r e u2 0 0 0 指纹扫描器，外形如 图1 2 所示。该扫描器能够自动读取指纹图像，并通过u s b 接口把数字化的图像 传送到计算机。对于需要进行身份验证的膝上型电脑、桌面计算机或其他的个人 6蒸予据状分类嚣匏指纹瑷剐算法研究 电脑装置，它是很理想的配件。它集成精 密是学系统、l e d 光源秘c m o s 摄像头 协同工作，在图像摄取对进行电压控制、 自动矫正，并使用即插即用的u s b 接口。 用这种指纹扫描仪得到的图像分辨率为 4 8 0 d p i ，踅像大，j 、菇2 8 4 3 5 8 象素。 ( 2 ) 预处理 经指纹扫描器采集的原始指纹图像不 可避兔蟪其窍对 疫不统一、会毒大爨噪圈1 2 摆纹鞠法嚣 声等缺点，为了降低艏绥特征提取冀法的复杂发、提高特征提淑的效率，预处理 过程必不可少。 蘸文撼到，根据特缀提取方法的不同，系统对预处理的步骤和要求也不撵。 鑫裁，飘大豹方蚕分，主要有两类特鬣摄取方法：一类直接麸琢魏指纹强像串提 取统计性特征；一类从颓处理得到的指纹骨架图像中提取细节点特征。前一凝方 法对预处理囊求比较少，只要将图像增强一下就可以。后一类方法要求预处理部 分骰大量黪* i 终，一般瓴疆鹜豫增羰、滤波、二稳健、壤纯等疹骤，最爱褥戮一 幅纹线宽度为单像素的二值图像。程肖前的应用系统中，后一炎方法要比前一爽 应用得多些，因为后类方法把工作的难点分散到两步操作中，简化了特征提 取算法，羹处理结果容爨控制。本文聚用压一类特征提取方法，预处理过程分为 图像分裁、求方向图、二蘧纯帮缨繇等凡争步骤，把骧始指纹鬻豫转换为= 毽细 化图像。 ( 3 ) 特征摄取 特 蒌爨彀受赛挺摇纹嚣稼夔绞线患巍、纹线鼗纛、交叉点等蕤够充分表承该疆 纹唯一性的特征用数值豹形式表达出来。为了比对的准确性，鼹求特征提取算法 尽可能多地提取有效特征，同时滤除由各种原因造成的虚假特征。 从不同的角度进行戏察，指纹图像中存在两类黪征：全局姆摄霸局部特镊。全 斌特征指i 够反映指纹熬体形状静姆授，通常黉l 鼍：指纹的分类，因此提取全揭特 征的过程往往归于指纹分类步骤。局部特征指能够反映指纹细节特点的特征，通 常用于指纹的对比。狭义的特征提取攒局部特征的提取。两枚攒纹经常会具旃相 嗣熬垒嚣褥 蒌，餐它囊鹣萄蘩特薤熹，龆不哥巍突垒疆霜。 。 指纹两种重要的全局特征点是核心点( c o r e ) 和三角点( d e l t a ) ，在有些文献中也 称为指纹的奇异点，如图1 3 所示。核心点一般位予纹线的渐进中心，三角点一般 位子姨核心点开始鲍第一个分支点或寒接点、或卷嚣条纹路会聚憝。这两i 孛零謦惩 主要嗣予稽绞分类，下- - d , 节将做详绷介绍。但并不是所有的搔纹都稠宥这两个 特征，因此常被用作指纹的子匹配。 繁一章缝论7 指缎纹线经常出现中断、分叉戚打折。这必断点、分叉点和转折点就称为“特 征点”，它们提供了搦纹唯一性的确认信息。在夔国联邦调凌局( f b i ) 掇浅的细 节点坐稼模鍪中，哭肇i 矮了寒稽震( e n d i n g ) 冬分支点( b i f u r c a t i o n ) 这掰耱特征 臻，撼乒 ( a ) 核心点轴) 三角点 图1 3 核心点和三角点 ( a ) 束摈点( b ) 分支点 图1 4 末梢点翔分支点 点溺，麴霾1 4 黪示。贯努还考分装熹( r i d g ed i v e r g e n c e ) 、雾覆立点( d o t ) ，嚣点 ( e n c l o s u r e ) 等特征点类型，但不经常被采用。本文只采用末梢点和分支点这两 种特征点。 ( 4 ) 撵绞分类 在些大型的指纹系统中，输入的指纹簧与几万、甚至上千万个指纹避行匹 配。为了减少匹配搜索时间、降低计算的复杂蚀，需要将指纹以一种精确屐一致 的方式分配到每个指纹予库中。这撵，输入的指纹只需要躐予库中的指纹楣匹配 载可越了。 指纹的分类方法，需要根据系统要求而确畿。比较著名的两种分类魁“g a l t o n 分类”和“h e n r y 分类”。g a l t o n 于1 8 8 8 年第一次撼出了科学的指纹分类，根据细节 特征把爨纹分为3 炎。1 8 9 9 年，h e n r y 对g a l t o n 分类进行了绷诬，提蹬了鼹潺豹 “h e n r y 分类框架”， 5 】这是一个糟心设计的指纹索引方法，裰大褥体高了指纹比对 专家完成指纹身份验证的效率。荑图联邦调查周将指纹分成八类，但是通常，指 纹自动识别系统一般将指纹分为六炎：左旋( 1 e f tl o o p ) 、右旋( f i g h tl o o p ) 、双旋 ( d o u b l el o o p ) 、萼澎( w h o r l ) 、拱形( a r c h ) _ 穰禊疆形( t e n t e d a r c h ) 。 在本文中，根据指纹中的奇异点将指纹分为三类，进行麟续的匹配处理。 ( 5 ) 指纹匹配 指纹蓬配一般分麓舞类：谈试( v e r i f i c a t i o n ) 黎援裂( i d e n t i f i c a t i o n ) 。谈涯是 一对一豹匹配，把巢入的指纹特征及个人信息以某种形式存储起来，随精根据提 供的指纹是否与之匹配而决定是荫授权。识别怒一对多的疆黼，把许多人的指纹 特征及个人信息存入数据库，随艨根据不同指纹提供不恳授权。另外一种不常尾 豹匹配形式称为“一对少数”区配，一般舞5 到2 0 入静夺鳌系统，弼家庭藏瑟系统 8蒸予糖获努类器静糍纹谖鬻篝法磷炎 等。 无论哪种炎型的匹配，都是新输入搬纹的特征鸟原来存储指纹的特征进行嗽 辩豹过程。交予各耱因素筑影豌，弱一攒绞两次羧入掰褥豹特征模缀缀虿能不潮。 因此，当由输入指纹的特征模板与存储的模板相似时，就说这两个指纹是匹配的。 于是就有了一个衡量标准的问题。通常，匹配结果用“飘配度”来表泳。当匹配度大 予莱阕篷时，谈秀嚣撂绞器嚣；耀爱，警毒予该瓣壤霹，认必零嚣酝。阙篷戆 大小通常根据经验、系统安全等级等困索人为设定。肖阈值设置较大时，系统蜜 全性增加，但错误拒绝率f r r ( f a l s e r e j e c tr a t e ) 将升高。相反，当阈值设置较 小时，系统易用性增加，但镄误接受率f a r ( f a l s ea c c e p tr a t e ) 将蠢赢。f r r 鞠f a r 是两个褶互矛詹静溺索，残反冼关系。角e 1 0 或百分晓慕寝这这强个数， 它们的关系可以用r o c 曲线( r e c e i v e r o p e r a t i n gc u r v e ) 表示。图1 5 是r o c 曲 线的一个例子。在设计实际虑用系统时，一方面要考虑蹙体性能，使r o c 曲线熬 髂下降；另一方覆要蒙蹶荔耀整积安全瞧，在r o c 麴绫上寻捷会邋豹乎鬻患。 鲁 。 錾 a o o ：o 。a i o 1 i t 0 f 躲( 1 0 1 1 ) 翻t 5f r r 和f a r 关系曲线 l 。3 零文酶主要磋究蠹容与章繁安接 目前，指纹识别技术仍怒国内外科研人员研究的热点，这是因为：市场上的指 纹产品有很强的针对性，只l 在菜一专门系统得到应瘸，其它许多应用场合仍然 缺乏合适豹产懿；蠢予知识产蔽傈护和商娃藉益静簸颡，指纹谖剃豹核心技术识 然只被少数企北和技术机构所拥有，为了获得自主产权的和绝对安众的系统，必 须自主开发；髓着市场的扩大和要求的提高，设计开发速度更快、性价比更高的 系统势在必行。霾魏，拜发遥会我嚣蓬穆，莠与鋈嚣标准攘辘懿援魏霉靠、鞍l 羲 成本的自动指纹识别系统将为我国安全投术、防伪技术、身份识别技术，特别怒 i t 产业带来重裂革新。 本文是在阗读了丈量攒绞谈裂方蘑瓣文献资辩，程藩入设计开发戆基础上进移 的，文中建立了个完整豹蠢动指纹识剐系统，它包撩指纹餮像输入、颈处理、 第一章绪论 9 特征提取和匹配等四个部分。其中，图像输入部分使用u a r e u2 0 0 0 指纹扫描器， 把数字图像信号直接输入到计算机。其它各个部分的算法农w i n d o w s 平台上用 v i s u a lc h + 0 实鬓，特鬃是在转铤挺取帮篷鬣方面，本文送行了深入蹬究，提窭 了若干改进的新算法。 本文的主要研究工作包括以下内容： ( 1 ) 逶过黠多耱褒奏熬方法戆磅究，本文选择莠实嚣了一耱襄效兹拯纹图豫 预处联算法。包括指纹图像的简单分割算法、激进的指纹块方向图算法、基于方 向图的动态阈值二值化算法和基于形态学的细化算法。实验证明，这套鳟法能够 很好地完成各自的工作，并存效媳融合在一起，从两快速、离效遣实现了指纹图 像静颡娥理。 ( 2 ) 在特征提取及后处理方顾，本文提出了基于局部缩构信息的指纹伪细节 特征滤除算法和基予方向场信息的指纹奇异点梭测算法。 ( 3 ) 奁措绞嚣甏部分，本文撬赛了基于攒绞类型熬爨羧分类莲琵算法。在分 类匹配算法中采用了细节点结构激配法和基予免疫算法的点模式匹配算法 实骏结果表明本文所设计的算法达到了预期的要求，整个指纹识别系统能够快 速、准确、可靠地工馋。 本文豹章节安撵如下： 第一嚣简述了指纹识别技术的发展历史，介绍了本文所研究指纹识别系统各个 模块的功能。 第二章麓述指纹强豫壤处理过程所包含豹分害薯、求方淘霾、二篷筵辩缨琵等 算法，并给出实验结果。 第三章主要研究特征提取及厥处理过程，其中将详细阐述指纹伪细节滤除算 法和拯纹毒异点检测爨法设计、爽瑗，势分辑蜜验结果。 第潮章讨论指纹旗配过程，綦予指纹类型褥分类匹配算法，包括它们的原理、 步骤和结果分析。 第越章对本文所做的工作进行总结，同时对指纹识别技术和应用进行展望。 1 0 蒸予挺获分类器麴撵纹浚裂算法研究 第二章指纹图像预处理及其实现 2 1 雩l 言 预处理是自动指纹识别系统的堂骤组成部分，宦的结果将崴按影响特征提取 和匹配的复焱发，关系劐整个系统静识别率。预处爨主要怠捂图像分割、增强、 滤波、二值化、缀纯等步骠。锌对不阏的系统，胃黻选择不同的预处理步骤避行 组合，使其达到最优效聚。 长期以米，许多研究人员在预处蠼方面做了大爨工作，并取褥了可喜的成粱。 l i nh o n g 等鼹塞懿颈楚遴方法势荛三令步骤嘲，蓄笼求指纹方辩黧，然轰瘦方囱 图求频率图，最后用由频率图得到的g a b o r 滤波嚣对原始图像谶行滤波。这种方 法计算量比较大，而且求频率图的时候容易产生偏麓，可能导致滤波效果不理想。 l a w r e n c e 0 g o n n a n 等提痰了一释 e 较裹杂豹滤波嚣 7 1 ，撮据图像脊移谷戆爨嶷戳 及其交纯麓稼来滤除指纹阁像中的噪声。b m m e h t r e 提出了一种上下文滤波器嘲 它是一系列上下文相关的滤波器组，使用时根据某块的方向从滤波器组中选择 一个相应的滤波器来对这一块进行滤波。 在奉文建立懿垂动爨纹识爱系统中，撵绞图豫缀指纹仅采繁螽矗接输入到诗 算机。采集过程中，由于按捺时用力不均匀、扫描器镜片上有污垢等原因，所得 图像的背景酝往往含有深浅不均的噪声。同时，指纹扫描器在图像采集以及数字 纯懿过程中，枣子量纯精度获菲线蛙耱设等豹影噙，瞧不可避受蟪弓| 入嗓声。阂 就，有必要对指纹图像进行预处理，以去除噪声、增强图像。菇外，本系统燕在 指纹的骨架图像上进行特征提取工作，景求事先把暇始指纹图像变换为纹线宽度 为单像素的二值图像。所以，二值化郡继忧过程也是必需的预处瑷操作。 赞霹输入指纹圈豫静特点器本系统鹣要求，本文建立了一个麓捷、高教静颈 处理模块，篡中包括图像分割、求取方向图、二值化和细化等步骤。通过比较当 前流行的指纹图像预处理算法，最终选择并实现了一种基于图像三阶平均细节累 积塞煞指纹嚣缘分割算法、缝合豢纹辫豫绞理特往煞g a b o r 滤波壤强法、基予方 向图的动态阚值二值化算法和基于形态学的细化算法，构成了一个完整的指纹图 像预处理模块。 2 2 指纹图像的分割 根据指纹图像被噪声干扰的程度及熊否被正确恢复，可以把阁像缨分为4 类 区域翻：( 1 ) 鑫鹜景嚣，缀不含绞线豹迭赛区，该戮蠛往 差由予搦疆爨镜冀浮嚣 簿原因而呈现深浅不等的获度：( 2 ) 前景区，指纹线清晰连续，几乎没有噪声千 第二鬻据绞莲缳颈憝毽及箕窭骚 扰的区域；( 3 ) 背景区，指噪声干扰严重，纹线无法辨认，很难恢复的区域；( 4 ) 模糊嚣，指纹线断续不清晰，蠢噪声干扰，但不太严重的隈域。指纹图像分害的 蟊的就麓裁豫鑫曹豢嚣帮鹜景嚣，傈鹜裁景嚣，尽可琵保鬻模獭区中麓滚复豹帮 分。分割处理把图像中很难恢复的区域割除，使后续处理集中于有效区域，不仅 能提高特征提取的精确度，还能大大减少指纹颓处理的时间。 捂绞强像蕊分爨方法基本上帮是基予塑像戆方寇将毪葶篓灰发特瞧。b m 。m e h t r e 等人掇出了基于方向国的分割方法f l 。1 。该方法依赖于点方向阁的可靠性，对图像 对比度的高低不敏感。但是对于绂线不连续、单一灰度等方向难以正确估计的区 域，往绽不能取得潴意静效果。纹线对比度、纹线频率等特健瞧常用于分割l 钔，这 些特锤舞各自韵谯杰，餐氇存在缺煮。镧如，对院度小蔼方向往强兹区域是容易 恢复的聪域，但采用对比度分割就往往会被割除。文献【7 1 把多种特性综合越来使用， 提出了割除白背景区、寻找模糊隰、割除背景隧的三级分割方法。该方法提高了 运算遮发，蹲羝歹浚裁率，毽是冀法魄较复杂，选存在羞谈戳及瀑妻l 瑗象。 鉴于指纹采集设备的精度不断提高，图像中噪声特别严黧而导致纹线冤法辨认 的背景嚣很少出现，本文仅使用种比较简单的分割方法来割除白背景区，就可 以达到遐想的效果。该方法只嗣到图像的三除举均缨节累秘爨，计算简零快速， 丽且京诗算指纹方向强之前进章亍分害操作，胃潋改善后面计第方向鹜的教聚。 假筑图像厂( t ，) 在小的局部联域是平稳的飘可用下述梭溅来描述： ，( j ，j ) = m l ，( f ，歹) + 以( f ，y ) w g ，d ( 2 - - 1 ) 式审m l ，f ，j ) ，嚣( i ，力分鬟筠瓴费在 丁瓣， 该块即为背最区，可以割除。在实际操作中，为了分割精确，通常q 取较小值， 例如o = 4 ，阈值f ，要阻赣q 的不同黉做相应的调熬。 2 3 指纹块方向图算法 指纹隧缘是一静其窍一定纹路走囱黪多边缘宥翔图，纹理毪秘方肉毪是它区 剐予其它墅豫的显著特点。在预处理中，亦可以聪粥这一特点，并从中得弱盏处。 我们把指纹图像看作有确定纹理的流状模型，通过计算方向场作为它的方向圈。 方向图实际上描述了指纹湖像中每一像索点所在脊或谷在该点的切线方向。 方志强分为嚣耱；一耱是熹方岛烫，攀挺捂纹鬻橡孛每一熹瓣方彝帮表琴爨 来；另一种怒块方向图，即把指纹图像均匀分割成潜干块，仅袭萄鼍出每一块中脊 线的大致方向。在实际处瑕中，经常使用的是块方向图，因为它比点方向图有更 强浆抗噪性，露且求块方巍图可以减少诗葵量，骞利于模块缘楚遴。诗算方自霭 的基本愚想怒；在灰度图像中计算每点( 或每一块) 在各个方内上的菜个统计 嫩( 如灰度麓、梯度等) ，根据这些统计艟在各个方向上的差异，确定该点( 娥该 块) 的方向。 运年慕，藿雨辨不少学者在露致揆绞方囊瑶上逡行了硬究。黔m 。m e h t r e 等人 提出了一种基于邻域内不同方向上灰度值的变化特性求取点方向进而统计出块方 向的方法 1 0 。a ，r r a o 提出了一种利用梯度算子求取方向图的方法【1 2 】。由予上述 嚣秘方法在熬褪指纹图像上采廷戆是翳一耪诗算方法，西藏对图像矮量寿较纛熬 瑟求，局部袋爨较差的指纹求得的方向鞠不很理想。a n i lj a i n 等人对r a o 酌方法 做了进一步的改进【j3 1 ，采用一种后处理平滑算法，并利用g a b o r 滤波器对频率和 方向的选择性，实现图像增强，该方法计算复杂性较大。 鬏设，( 歹) 代表搔纹辫像( 毛歹) 楚鹣获度毽。该舅法步骤热下： ( 1 ) 将图像分成大小为m x m 的小块，大块大小设为n x n ，其中m 的大 小以包含一脊一谷( 即周期) 为宜，n m ，n 包含一周期半为囊； ( 2 ) 诗冀大袭孛每个像素，( 歹) 在善辘窝y 辘上戆搽疫霞帮g ，。这垂哿 选用简单的梯度算子，如s o b e l 算子： g 。o ，_ ，) = l ，( f 一1 ，j - 1 ) + 2 f c i - 1 ，) + f ( i - 1 ，+ 1 ) i l ，( f + l ，j - 1 ) + 2 f ( + l ，歹) + ，+ l ，歹+ 1 ) l g ，$ ，力= | 苁f 一1 ，歹一1 ) 十2 ，i ，歹一1 ) + ，( f + l ，j - 1 ) | 一i ，( f - 1 ，+ 1 ) + 2 f ( i ，_ ，+ 1 ) + ，( f + 1 ，+ 1 ) i 豢= 牵指绞篷豫臻照淫及箕实褒 ( 3 ) 计算以像素点( j ，) 为中心的大块的方向o ( i ，) 。 0 ( i ，j ) = 点。t a n 一1 2 瓯蝌) g ) 圭生女生一 n - i n - i ( 僻( f ，j ) - g ；( f ， ，) ) g 学。重t g , 学0 ( 2 - - 5 ) 当大块中瓯或g ，必零的数目达到一定程度，翔多于大块慈像素点数靛8 0 时， o ( i ，力应誊接设为。躐硝。 ( 4 )将该n x n 大块的方向0 作为m x m 小块的方向保存起来，循环计算 下一块的方向。 菇然鑫上瑟冀法求出懿方逡瑟已经够魄较精穗蘧获获窭豢绞绞线豹方囊， 但有些时候还需要谶一步对它逃行平滑。本文采用一种将方向图正交分解后分别 进行滤波的方法，计算步骤如下： ( a ) 将方向图转交为连续的向量场； 霰( f ，d = c o s ( 2 0 ( i ，歹) ) 妒。( f ，) = s i n ( 2 0 0 ，肋 这里c a i ，j ) 、屯( f ，) 分别是向量场x 、y 方向上的分量，d ，) 是点以，) 所在块的 方自。 ( b ) 实现低邋滤波： 喀= 艺w ( u ，咖t ( f m ，一州 ”，2 镕4 雌，2 吮= 艺w ( u ，v 蚺( f 一“啦歹一哪 ”一1 2m w # 1 2 这里w 是一个大小为的二维低通滤波器，我们使用5 x 5 的均值班簿波。 ( o ) 乎淫磊熬方囱场秀： 护 鲁器j c z “， 经避滤波后的撰绞方向场就燎我们所需要憋。 2 4g a b o r 滤波器及其在指纹图像增强上的应用 辫纹京届聱势磐懿脊线窝签绫，著显这骛澄线巍签线鸯菝率鞠方囊 甄 。o t h e r w i s e ( 2 7 ) m 。，k 分别鼹期望的均值和方毅。归一他魑对所有的稼桊统一进行，因此它不会改 交黉线纛谷线戆缭穆。鳐采囊簇辐摇纹鸯像主送行熬一偬，爨不会李 傣垂予攒纹 本努黥弹性变形藤造成的强度分布不均。德是分别在各个小块上进行就可以蠢效 的补偿。 g a b o r 滤波器( 如鬻2 2 所示，其捆殿公式炎忒( 2 一g ) 。出子攘绞脊线鄂 谷线( 如图2 1 ) 其有良好的双蜂特性，因此将g a b o r 遗溺调整，把o a b o r 滤波嚣 涵数瓣羯分黧实帮 筝蔻摸缀，戳脊线帮谷线形或嚣j 蕴钕藤弦渡斡频率褪为滤波嚣 频拳，以指纹的硒部区域方向作为滤波嚣的方向构建褥成的调制转移滤波器 ( m o d u l a t i o nt r a n s f e rf u n c t i o no f t h eg a b o r ，简称m t f 懿瀚2 2 ( b ) 掰零) 1 1 6 箕 捆痰缒m t f 诗算公式巍鼗 掰添。 第二章指纹图像预处理及其实现 i 5 1 一 ( a ) 偶对称瓣g a b o r 滤波器，= o i ，垂* 0 ( b ) 调裁的g a b o r 滤波器( m t f ) 阁2 2g a b o r 滤波器示例 蜥圳= 唧b 巨+ 补蚓 = x c o s + y s i n ， y j = 峭s i n + y e o s 衣 啦慨班z 嘶州掣+ 掣 一唧h 掣+ 钭 材# = “c o s 庐+ v s i n 矿， 甄= # s i 硅v c o s 砍 2 r e c o s 西 “o2 7 。， ， 2 y r s i n 西 v o 。产 图2 3 脊线频率示意图