（信号与信息处理专业论文）指纹识别系统中的匹配算法研究与实现.pdf

摘要 摘要 随着社会信息化建设的迅猛发展，信息安全保障的实际需求日益增 强。在网络安全、金融、电子商务等诸多应用领域都有着身份认证的强 烈需要。与此相关的生物特征识别技术日益受到人们的重视。这种技术 根据人体自身的特征，如人脸、指纹、视网膜、声音等来识别个人的身 份。其中，指纹识别技术更以其独有的优越性成为生物特征识别技术的 研究热点之一。 本文的研究内容正是指纹识别系统中的一个关键技术：指纹匹配。 指纹匹配是用当前输入指纹的特征与事先保存起来的模板特征进行比 对，从而判断这两个指纹图像是否来自同一个手指。匹配结果的正确与 否是自动指纹识别系统是否成功的最后一道关口。主要完成的工作如下： 编程实现了基于矢量三角法的指纹匹配算法。它利用两个临近细 节点的信息作为辅助，来定位指纹参照点，从而实现指纹的匹配。 实验结果表明，算法不依赖指纹的中心点，具有旋转不变性等优 点，但是对图像质量要求较高； 编程实现了基于脊线校正和矢量三角法的二次选取参照点的细 节匹配算法。它更多地引入了指纹的脊线信息，同时，又利用矢 量三角法来对脊线校正阶段初次选取的参照点进行验证，以确定 参照点的可靠性。通过实验验证了这种算法的有效性。 在c c s 软件集成环境下，对指纹识别算法进行了硬件仿真。 关键词：指纹识别，匹配算法，脊线，细节点，c c s ( c o d e c o m p o s e rs t u d i o ) a b s t r a c t a b s t r a c t w i t ht h ea d v e n to fi n f o r m a t i o ns o c i e t y ，t h ed e m a n do nt h es e c u r i t yo f i n f o r m a t i o ni si n c r e a s i n gi nt h ec i v i l i a nf i e l d ss u c ha sw e b - a c c e s s ，f i n a n c e ， s a f e g u a r da n de l e c t r o n i cb u s i n e s s b i o m e t r i c s ，w h i c hr e f e r st oi d e n t i l y i n g a ni n d i v i d u a lb a s e do nh i so rh e r p h y s i o l o g i c a lo rb e h a v i o r a lc h a r a c t e r i s t i c s ， h a st h ec a p a b i l i t yt or e l i a b l yd i s t i n g u i s hb e t w e e na na u t h o r i z e dp e r s o na n d a ni m p o s t e r a m o n ga l lb i o m e t r i c s ( e g ，f a c e ，f i n g e r p r i n t ，i r i s ，r e t i n a ，d n a ， v o i c e ，e t c ) ，f i n g e r p r i n t - b a s e di d e n t i f i c a t i o ni s o n eo ft h em o s tm a t u r ea n d d e p e n d a b l et e c h n i q u e s t h i s p a p e r f o c u s e so no n eo ft h em o s t i m p o r t a n tt e c h n i q u e s i n a u t o m a t i c f i n g e r p r i n t i d e n t i f i c a t i o n s y s t e m ：f i n g e r p r i n tm a t c h i n g t h e t e m p l a t eo ft h ei n p u tf i n g e r p r i n ta n dt h et e m p l a t eo ff i n g e r p r i n t sf r o mt h e d a t a b a s ea r ec o m p a r e dt od e c i d ew h e t h e rb o t ho ft h et w o f i n g e r p r i n t sb e l o n g t ot h es a m ef i n g e r t h ea c c u r a t er a t eo f m a t c h i n gr e s u l t si st h el a s tc r i t e r i o n o ft h es u c c e s so fa 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 s t h e f i n g e r p r i n t m a t c h i n ga l g o r i t h mb a s e d o nt h ev e c t o rt r i a n g l eh a s b e e nr e a l i z e db y p r o g r a m m i n g t h i sm e t h o d u t i l i z e si n f o r m a t i o no f t w on e a r e s tm i n u t i a et od e t e r m i n et h e r e f e r e n c e p o i n t s i n f i n g e r p r i n ti m a g ea n dt of u l f i l lf i n g e r p r i n tm a t c h i n g e x p e r i m e n t a l r e s u l t sd e m o n s t r a t et h a tt h em e t h o dd o e s n tr e l yo nt h ec o r ep o i n t s ， a n df u r t h e r m o r e ，i ti si n v a r i a n tt or o t a t i o n b u t ，i td e m a n d sg o o d q u a l i t yo fi m a g e s t h e f i n g e r p r i n t m a t c h i n ga l g o r i t h mb a s e do nt h ea l i g n e dr i d g e sa n d t h ev e c t o rt r i a n g l e i n c o r p o r a t e sm u c hr i d g ei n f o r m a t i o ni n t ot h e m a t c h i n gp r o c e s s a tt h es a m et i m e ，i tu s e st h ev e c t o rt r i a n g l et o v e r i f yt h el o c a t i o no fr e f e r e n c ep o i n tt oc o n f i r mt h er e l i a b i l i t yo f r e f e r e n c e p o i n t t h ee x p e r i m e n t a l r e s u l t sc a n p r o v e t h a tt h e f i n g e r p r i n t - m a t c h i n ga l g o r i t h mu s e di nt h i sp a p e ri se f f e c t i v e a b s t r a c t t h eh a r d w a r e s i m u l a t i o no ft h ef i n g e r p r i n ti d e n t i f i c a t i o na l g o r i t h m i s a c c o m p l i s h e d i nt h e i n t e g r a t e ds o f t w a r e d e v e l o p i n g t o o lc c s ( c o d ec o m p o s e rs t u d i o ) ： k e yw o r d s ：f i n g e r p r i n ti d e n t i f i c a t i o n ，f i n g e r p r i n tm a t c h i n ga l g o r i t h m r i d g e l i n e ，m i n u t i a ，c c s ( c o d ec o m p o s e rs t u d i o ) i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电 子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 签名：塑垦堡日期：脚j 月加日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学 位论文的规定，有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大 学可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后应遵守此规定) 签名：胄秘壤 导师签名： 日期：汐妒年月d 2 de l 第一章绪论 第一章绪论 进入二十世纪九十年代，随着计算机技术，特别是图像处理技术、 模式识别技术的迅速发展，以及大量快速有效、价格相对低廉的数字信 号处理芯片的出现，指纹识别技术的应用越来越广泛，它不仅用于公安、 司法等部门作为罪犯查证的一种手段，而且还广泛应用于银行、保密、 信用等需要验证个人身份的场所以及需要严格控制出入的地方。指纹识 别系统日益明显地显示出快速和准确的特点。现在，计算机已经能在几 十到几百毫秒内对指纹进行核对。当今社会对技术发展的要求是先进、 成本低廉、易用，为顺应这个趋势，指纹识别技术作为身份识别工具， 日益受到人们的欢迎。 1 1 课题提出的背景和意义 越来越多的电子设备和保密机构对更安全更方便的身份认证和访问 控制的需求变得越来越紧迫，传统的机械钥匙、“口令+ 密码”以及智 能卡等的保护措施存在着丢失、遗忘、复制及被盗用的隐患，在这种情 况下，生物识别技术为上述方法的不足提供了一个很好的解决方案。一 个人的生物特征是“随身携带”的，不用担心会丢失，您可以不必携带 大串的钥匙，也不用费心去记或更换密码；生物特征又具有唯一不可复 制性，有学者推论：以全球6 0 亿人口计算，3 0 0 年内都不会有两个相同 的指纹出现。指纹被称为“物证之曹”，安全可靠。进入信息时代，生 物特征识别在西方又次崛起。以电子商务、电子银行的安全认证为例， 目前在电子商务中他人假冒当事入的身份能有效确认，例如通过生物特 征识别确认，就可有效防止此类事件的发生。另外，网络、数据库和关 键文件等的安全控制，机密计算机的登陆认证，银行a t m 、p o s 终端等 的安全认证，蜂窝电话，p d a 的使用认证等等，都离不开可靠安全的生 物特征识别。可见，在即将到来的信息社会，生物特征识别不但有可观 的经济效益，还有不可估量的国家信息安全效益。 第一章绪论 1 2 指纹识别与生物识别 生物识别( b i o m e t r i c ) 是自动识别( i d e n t i f i c a t i o n ) 或确认 ( v e r i f i c a t i o n ) 人的生理特征( 如指纹、手掌的几何形、掌纹、虹膜、 视网膜、面孔、面部热像图、手腕脉络、皮肤毛孑l 、身体的气味、脉管 图样等【1 】) 和行为特征( 如声音、签名、步态、姿势等) 来进行身份验 证的一种技术【“。生物识别技术的核心在于如何获取这些生物特征，并 将之转换为数字信息，存储于计算机中，利用可靠的匹配算法来完成验 证与识别个人身份的过程。生物识别以生物技术为基础，以信息技术为 手段，将两大热门技术交汇融合为一体。生物识别技术目前主要包括指 纹、手掌、视网膜、虹膜、面孔、脉络、声音、步态等的认证。其中的 指纹识别技术更是生物识别技术的热点。 指纹识别是生物识别技术中最早应用，技术最为成熟，价格最低廉 的分支。与其他的生物识别技术相比，指纹识别不仅具有许多独到的信 息安全角度的优点，而且更为重要的是还具有很高的实用性和可行性。 随着图像处理模式识别和计算机科学等学科的发展，自动指纹识别系统 ( a u t o m a t i ef 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 ) 的研 制取得了很大的进展，并且已经有实用产品问世。 自动指纹识别系统的性能在很大程度上依赖于指纹识别算法的有效 性和可靠性。不同应用领域的自动指纹识别系统，需要满足不同的性能 要求。用于罪犯身份鉴定的指纹识别系统，其最终的设计要求是可靠性 要高，而一般的小型指纹门禁系统，其设计要求具有很高的实时性和易 用性，因此识别算法应该具有相对较低的复杂度，较快的运算速度，从 而满足实时性的要求。我们有必要研究不同的指纹识别算法，使得应用 系统在可靠性、实时性、有效性等方面满足不同的性能要求。 1 3 指纹识别技术的历史和发展现状 早在公元前6 0 0 0 年，在古叙利亚和中国，指纹作为身份鉴别已经开 始应用。考古发现，在这个时代，一些粘土陶器上留有陶艺匠人的指纹， 中国的一些文件上印有起草者的大拇指指纹，在j e r e h o 的古城市的房屋 留有砖匠一对大拇指指纹的印记等。 2 第一章绪论 1 9 世纪初，科学家研究发现了至今仍然承认的指纹的两个重要特 征，一是两个不同手指的指纹纹脊的式样( r i d g ep a t t e r n ) 不同，另外一 个是指纹纹脊的式样终生不改变。这个研究成果使得指纹在犯罪鉴别中 得以正式应用。主要代表性的事件有：1 8 9 6 年阿根廷首次应用，然后是 1 9 0 1 年的苏格兰，2 0 世纪初其他国家也相继应用到犯罪鉴别中。2 0 世 纪6 0 年代，由于计算机可以有效的处理图形，人们开始着手研究利用计 算机来处理指纹。从那时起，自动指纹识别系统a f i s ( a u t o m a t i c f 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 ) 在法律实施方面的研究和应用在 世界许多国家展开。 2 0 世纪8 0 年代，个人电脑、光学扫描这两项技术的革新，使得它 们作为指纹取像的工具成为现实，从而使指纹识别可以在其他领域中得 以应用，比如代替i c 卡。现在( 9 0 年代后期) ，低价位取像设备的引入 及其飞速发展，可靠的比对算法的发现为个人身份识别应用的增长提供 了舞台。 进入2 l 世纪以来，生物认证技术被广泛接受。目前，指纹识别技术 正越来越广泛地应用在机场、银行和网上交易等需要验明身份的地方。 随着新的身份识别技术的发展，指纹识别将成为未来身份认定的重要方 式。由于活体指纹识别技术的成功发展，使指纹识别系统可不需由特定 人士操作，成为一般人可使用的工具，使指纹识别进入个人使用的阶段， 如移动电话，p c 等电子产品。 1 4 指纹识别技术的特点及应用 从理论上说，人的任何生理或行为特性，只要满足以下条件，都可 以用作人的身份识别： 普遍性：即该特性是每个人都具有的特性。 唯一性：即任何两个人的特性都是不同的。 持久性：即该特性不会随着时间的推移而改变。 量化性：即该特性能够被定量的衡量。 研究和经验表明，人的指纹、掌纹、面孔、发音、虹膜、视网膜、 第一章绪论 骨架等都具有唯一性和稳定性的特征。基于这些特征，人们发展了指纹 识别、面部识别、语音识别等多种生物识别技术。 尽管每一种技术都在一定程度上满足前述的要求，并且已经被用于 实际系统或可能成为一种有效的生物测定技术。但并不是都被认可为无 可争议的身份验证依据。 在实际应用中，还有一些其他重要的要求得考虑在内。他们包括： 性能指标：指能达到的验证精度，为达到这一准确度所需的 资源以及影响该准确度的各项因素。 易接受性：指人们在多大程度上愿意采用该生物测定系统。 反欺诈性：指该系统是否易于为欺诈技术攻破。 例如，尽管对自动面孔识别进行了广泛的研究，而且些面孔识别 系统已经面世。但迄今仍无证据表明凭借面孔能够可靠的识别身份。在 实际环境中，仅凭面孔无法达到可以令人接受的验证精度。到目前为止， 指纹验证技术是唯一被法律认可的，能够自动检验的，已经成熟了的生 物测定技术。尽管签字也是被法律认可的生物测定技术，但由于它的精 度，易被伪造及变化性等因素，而远远落后于指纹排名第二。 1 4 1 指纹识别技术的特点 事实证明，相对于其它的生物识别技术( 如视网膜识别和语音识别 等) ，指纹识别技术是一种更为理想的安全身份认证技术【3 5 】。原因如下： 由于指纹识别更具有实用性与可行性，所以更成为生物识别技术的热点， 应用指纹识别技术具有特点如下： 1 ) 指纹的唯一性：指纹是人体独一无二的特征，两人之间不存 在相同的手指指纹，并且它们的复杂性足以提供用于鉴别的 足够特征； 2 )指纹的稳定性，即终身不便性。指纹的形态和细节特征，在 人的一生中保持不变，可一直被当作人的身份鉴定的可靠手 段； 3 ) 指纹的高可靠性。如果我们想提高可靠性，只需登记更多的 4 第一章绪论 指纹，鉴别更多的手指，一个人的十指指纹皆不相同，这样， 可以方便地利用多个指纹构成多重口令，提高系统的安全性。 同时，并不增加系统的设计负担。 4 )指纹的易获取性。指纹样本便于获取，易于开发身份识别系 统。目前已有标准的指纹样本库。而对虹膜、视网膜等则难 以采样，也无标准的样本库供系统软件开发。 5 )指纹采集的高速、低成本性。指纹扫描的速度很快，使得非 常方便。指纹采集头可以更加小型化，并且价格更加低廉。 从以上几个方面可以看到，相对于其它生物技术，指纹识别不仅具 有许多独到的信息安全角度的优点，更最要的是还具有很高的实用性和 可行性。 1 4 2 指纹技术识别的应用 指纹识别技术可以通过多种方法应用到许多方面。如指纹可以作为 密钥进行个人身份的认证，取代传统的数字密码认证，更具备安全性。 又如，在当今的网络时代，指纹识别技术可以通过电子邮件或其它传输 方法在计算机网络上进行传输和验证，从而极大地提高了网上信息的安 全性。使网上银行、网上贸易、电子商务等一系列的网络商业行为得到 安全保障。 随着多种指纹识别产品的开发，指纹识别技术已经开始应用到民用 市场，并发展迅猛。该项技术适用于几乎所有需要进行安全性防范的场 合，在金融证券、1 t 、安防、公安、医疗、福利等行业的许多应用系统 中具有广阔的发展前景。这方面目前主要用于领域有： 夺金融业：电子货币交易，a t m 安全，核对现金，信用卡安全 等。 夺i t 业：个人计算机系统及蜂窝电话密码、信息安全防范、 网络安全防范、网上银行及电子商务的安全交易。 夺安防业：指纹门禁系统、个人证件。 夺医疗：献血输血管理、个人医疗档案管理。 5 第一章绪论 冷社会福利：公费医疗确认、保险受益人确认、各种社会福利 受益人身份确认。 夺其他：指纹考勤、俱乐部会员确认、选举身份认证、海关及 民航快速通关认证等。 指纹识别技术在我国已经开展得很广泛，众多的公司和机构都参与 了研发和应用工作。其中，中科院自动化研究所人工智能实验室取得了 最为突出的成果，获得了很多有自主知识产权的技术，他们是国内唯一 一家参与f v c 2 0 0 2 的机构；另外，北京大学，清华大学，四川大学都在 指纹识别上取得了一定的进展。 1 5 本课题所做的主要工作 本文对指纹识别技术的一个核心步骤一一指纹匹配，进行了一定的 研究。针对点模式匹配，选用了一种基于矢量三角法的指纹缅节匹配算 法【“，实验结果表明算法虽然具有旋转不变性、不依赖中心点等一些优 点，但是它对一些质量差、偏移大的图像不能像期望的那样找到参照点， 进行两幅指纹图像的匹配，因而它的拒识率较高。为了减小算法的拒识 率，提高识别率，本文将脊线校正引入其中，采用基于脊线校正和矢量 三角法相结合的二次选取参照点的指纹细节匹配算法，这种算法明显改 善了基于矢量三角法的细节匹配算法有时找不到参照点的情况，取得了 较为满意的结果。最后，本文在t m s 3 2 0 c 6 7 1 i 上对指纹识别算法( 主要 针对特征提取) 进行了仿真。 1 6 本文的结构 全文共由五章组成，每章的主要的内容如下： 第二章自动指纹识别系统 主要介绍指纹识别的基本原理，识别系统的各部分组成，以及系统 性能的评估方法。包括指纹识别的系统组成、基本原理、性能评估方法； 第三章指纹匹配算法 概述了文献中提到的一些匹配算法，详细描述了我们进行实验的和 采用的两种匹配算法以及算法实现，并给出了在指纹识别算法竞赛 6 第一章绪论 ( f v c 2 0 0 0 ) 的数据库上的实验结果； 第四章t m s 3 2 0 c 6 0 0 0 的指纹识别算法仿真 本章详细介绍了t i 公司的t 1 ：l $ 3 2 0 c 6 0 0 0 的c c s 软件开发环境，重点 阐述了利用c c s 2 0 集成开发软件对指纹细节提取算法的模拟仿真，并获 得一些实验参数。 第五章结论和展望。 总结全文，并对系统今后的进一步扩展提出了修改建议。 7 第二章 自动指纹识别系统 第二章自动指纹识别系统 2 1 介绍 早在1 8 8 0 年，英国人亨利就提出了用指纹识别系统识别罪犯。但那 时无论是指纹分析还是指纹存储和对比，都是依靠人工的方式，利用放 大镜对指纹进行分类、编码，要对比一个指纹，需要对库中的指纹一个 一个的对比，花费的人力和时间很多。到2 0 世纪7 0 年代，由于计算机 的广泛应用和模式识别理论的发展，人们已开始研究使用计算机进行指 纹的自动识别，并开发出了一些半自动化系统，即指纹分析采用带有投 影屏幕的指纹分析仪或光笔对指纹进行分类，而存储和对比采用计算机 自动工作。近十年来指纹自动识别系统才得到大量的关注，世界各国都 在争先研究和开发自动指纹识别系统。根据资料显示已有各种指纹识别 系统研制成功。但直到近年来科技事业的高速发展，才使自动识别系统 进入实用阶段。活体指纹的自动识别基于多方面的成就：激光技术和 c c d ( c h a n g ec o u p l ed e v i c e ，电荷耦合器件) 技术使活体指纹的采集完 成于瞬间；算法的发展为活体指纹图像的特征提取和匹配提供了坚实的 基础：计算机速度的提高，使活体指对比的时间大大缩短。 本章首先讲述指纹识别技术的基本原理，并详细论述指纹识别系统 的各部分组成，讨论指纹识别系统的应用情况，以及系统性能的评估方 法，最后是本章小结。 2 2 指纹识别的基本原理 2 2 1 基本概念 在讨论指纹识别技术的基本原理以前，首先明确几个与指纹相关的 概念。 指纹是手指末端正面皮肤上凹凸不平产生的纹路，这些纹路就是通 常所说的脊和谷 3 1 。尽管指纹只是人体皮肤的一小部分，但是，它蕴涵 大量的信息。这些近乎平行的曲线，形成了指纹的模式，成为指纹的全 局纹路结构；同样，指纹还有许多局部特征，称为细节点( m i n u t i a ) 。 8 第二章自动指纹识别系统 正是这些全局和局部特征形成了指纹的独特性，使它成为身份认证的可 靠工具。另外，为了识别需要，在纹线上还定义了中心点和三角点( 通 称奇异点) ，如图2 1 所示，图像取自f v c 2 0 0 0 a 图2 - 1 指纹的中心点、三角点和细节点 图中三角形“”标出的是中心点，四方形“口”标出的是三角 点，圆形“o ”标出的是部分细节点。 2 1 1 1 指纹的全局特征 全局特征指那些用人眼直接就可以观察到的特征，包括基本纹路图 案、模式区、核心点( 中心点) 、三角点、式样线和纹数等。基本纹路图 案有涡形、拱形、弓形、左旋箕形、右旋箕形。如图2 - 2 所示。 模式区是指指纹上包括了总体特征的区域，即从模式区就能够分辨 出指纹是属于那一种类型的。有的指纹识别算法只使用模式区的数据。 核心点( 中心点) 位于指纹纹路的渐进中心，它在读取指纹和比对指纹 时作为参考点( 见图2 1 ) 。三角点位于从核心点开始的第一个分叉点或 者断点、或者两条纹路会聚处、孤立点、折转处，或者指向这些奇异点。 三角点提供了指纹纹路计数跟踪的开始之处。纹线数指模式区内指纹纹 路的数量。在计算指纹的纹数时，一般先连接核心点和三角点，这条连 线与指纹纹路相交的数量即可认为是指纹的纹数。 9 第二章自动指纹识别系统 ( d ) 右旋箕形 图2 - 2 指纹的基本纹路图案 ( e ) 涡形 利用指纹的全局特征，可以对指纹进行分类，这样做的意义在于， 预先把大型的数据库分成了几个组，可以减少数据库搜索时间；匹配时， 首先进行模式匹配( 称作“粗匹配”) ，有助于提高识别率。 2 1 1 2 局部特征 局部特征是指指纹上的节点的特征，这些具有某种特征的节点称为 特征点。两枚指纹经常会具有相同的总体特征，但它们的局部特征一一 特征点，却不可能完全相同。 指纹纹路并不是连续的、平滑笔直的，而是经常出现中断、分叉或 打折。这些断点、分叉点和转折点就称为“特征点”( 也就是细节点， m i n u t i a ) 。就是这些特征点提供了指纹唯一性的确认信息，人们正是利 1 0 第二章 自动指纹识别系统 用这些局部特点进行指纹的精确匹配。 这些指纹特征点可用以下四种特性来描述 1 分类( c l a s s i f i c a t i o n ) 一一特征点有以下几种不同类别 7 1 ， 其中最典型的是终结点( 末梢点) 和分叉点 8 - 9 1 ，而其他的细节点可 以用它们的组合来表示。例如环可以看成两个分叉点，鞭可以看成 一个终结点和一个分叉点等。 终结点( e n d i n g ) 条纹路在此终结。 分叉点( b i f u r c a t i o n ) 条纹路在此分开成为两条 或更多的纹路。 分歧点( r i d g ed i v e r g e n c e ) 一一两条平行的纹路在此 分开。 孤立点( d o to r i s l a n d ) 条特别短的纹路，以至 于成为一点。 环点( e n c l o s u r e ) 条纹路分开成为两条之后， 立即有合并成为一条，这样形成的一个小环称为环点。 短纹( s h o r tr i d g e ) 端较短但不至于成为一点 的纹路。 第二章自动指纹识别系统 2 位置( p o s i t i o n ) 一一特征点的位置通过( x ，y ) 坐标来描 述，可以是绝对的，也可以是相对于三角点或核心点的。 3 方向( o r i e n t a t i o n ) 一一该特征点所在的局部脊线的方向。 4 脊线( r i d g e ) 一一特征点对应的脊线( d ，q ) 。 特征点对应的脊线用在该脊线上的采样点来表示。采样点用该点与 对应特征点的距离d 和连接该点与对应特征点的直线和对应特征点方向 的夹角d 来表示。 2 2 2 基本原理 两枚指纹经常会具有相同的总体特征，但它们的局部特征一一特征 点，却不可能完全相同，因此，指纹识别技术通常使用指纹的全局特征 如纹形、三角点等来进行分类，再用局部特征如位置和方向等来进行识 别用户身份。通常，首先从获取的指纹图像上找到“特征点”( m i n u t i a ) ， 然后根据特征点的特性建立用户活体指纹的数字表示一一指纹特征数据 ( 一种单向的转换，可以从指纹图像转换成特征数据但不能从特征数据 转换成为指纹图像) 。由于两枚不同的指纹不会产生相同的特征数据，所 以通过对所采集到的指纹图像的特征数据和存放在数据库中的指纹特征 数据进行模式匹配，计算出它们的相似程度，最终得到两个指纹的匹配 结果，根据匹配结果来鉴别用户身份。 l 一一塑堡塑坌 1 卜臣至i 磊藁，塑堡警 亘至三三荆细节点数据 。1 。一 i i i 模板细节点 图2 - 3 自动指纹识别系统的原理框图 1 2 第二章自动指纹识别系统 总之，自动指纹识别系统首先通过取像设备读取指纹图像，然后用 计算机识别软件提取指纹的特征数据，最后通过匹配识别算法得到识别 结果。其基本原理框图见图2 3 。 2 3 自动指纹识别系统的组成 指纹识别系统主要由四个部分构成：采集，表征( 模板) ，特征提取， 匹配。 2 3 1 指纹采集 指纹识别的第一步就是采集指纹图像。采集指纹图像的装置一般分 为两类：光学成像设备和固体状态感应器。光学成像设各的原理是利用 一组设计好的光学系统将由光源照射的指纹反射到一组c c d 阵列上， 由c c d 捕获指纹的图像；固体状态感应器是近几年开发出来的采集设 备，他们都是带有压力、温度或其它传感表面的传感器，传感表面由 1 0 0 0 0 0 个以上的传导单元构成一个传感阵列，当手指押在传感器上时， 由于各个传导单元受力不同，产生不同的电压或电流等电信号，从而可 以记录指纹的脊和谷。 光学采集设备的优点是采集面积大、技术成熟，缺点是体积较大， 设备成本较高；固体状态感应器的优点是成本相对低廉、结构紧凑，缺 点则是采集面积小，精度难以保证。尽管如此，随着近年来技术的日益 完善，这两类采集设备优点已经开始逐渐融合，缺点也在逐渐消失。 目前主要有两种采集指纹图像方式：涂抹法( 离线) 和扫描法( 在 线) 。涂抹法就是由一名指纹专家将涂抹上印泥的手指在纸上印出指纹图 像，再用扫描仪扫描成图像文件。扫描法就是直接对手指扫描获得图像 文件，不需要通过纸张的中间过渡。通过涂抹法获取指纹很繁琐，而且 对于指纹自动识别来说也是不可行的。 最流行的指纹扫描技术是利用光的漫反射原理。将手指放在玻璃板 的一面，指纹的脊与板相接触，而谷则没有接触。板的另一面放置l e d 光源和c c d 。激光以一定的倾角照在玻璃板上，而相机放在能接收到激 光反射光的位置上。射在玻璃板上与脊相接触的位置的光很少发散，而 射在谷所在的位置上的光则完全内反射，于是在c c d 上形成对应的指 1 3 第二章自动指纹识别系统 纹图像。除此以外，还有其它的成像方法，如基于超声波内反射的方法， 基于温差( 脊和谷之间) 热感应的方法，基于容差感应的方法，非接触 式三维图像扫描法等。这些方法的主要目的是降低扫描系统的尺寸或价 格，或者提高图像的质量和分辨率而设计的。 2 3 2 指纹表征( 模板) 表征问题构成了指纹识别的本质，并对系统其它方面的设计有深远 的影响。 基于整个图像的灰度轮廓的表征方式在光学匹配的识别系统中被普 遍使用。然而这一方法的应用由于亮度变化，图像质量变化，疤痕等诸 多因素的存在而有很大局限性。一些设计者希望通过限制表征区域的范 围，以一块较小但一致性好的区域来表征指纹。但这样做会带来一定风 险，因为用来识别的模板量也随之减少了。但从另一方面看，由于基于 整个图像的表征法事先未对指纹作任何假定，因而对多种类型的指纹图 像有很强的鲁棒性。 基于整个脊结构的表征是不会随着亮度的变化而发生变化的。但这 一方法要比后面将要提及的基于特征点的表征方法对图像质量更为敏 感。这是因为特征点更容易辨认的缘故。 基于特征点的表征法是从一幅二值化的指纹图像中提取特征点。这 一方法还有另外一个好处一一隐私性，即无法仅凭借特征点的信息来重 构指纹图像。该方法基于这样一个假定：每个指纹的唯一性可由特征点 及其在空间的分布来确定。因此，自动指纹识别系统大都采用特征点匹 配，面非基于象素或脊线的匹配。典型的自动指纹识别系统采用两种最 显著的结构来表征：脊末端点和脊分叉点【9 l 。如图2 - 4 所示。 这两种结构是背景一前景对偶的。而且由于压力的变化，一种结构 会转化为另一种结构。因此，很多算法对这两种结构不加区分同等对待， 统称为特征点( m i n u t i a ) 。特征点表征法最简单的形式，是由他们相对 与图像中的一个固定中心的空闻坐标组成的一个表来构成。然而在多数 情况下，这些特征点还要附加上更进一步的信息，如特征点子集，特征 点对，等等。另外，每个特征点还可以附上脊线在该点的方向作为附加 1 4 第二章自动指纹识别系统 信息，或者每对特征点之间穿过的脊线的数目。特征点表征法还可以结 合一些指纹的全局信息，如方向、旋的位置、指纹类别等。 圈2 - 4 脊末端点和分叉点 2 3 3 指纹特征提取 特征提取就是从输入的图像中提取所需的特征。 它负责把指纹图像的纹线走向、纹线断点、交叉点等能够充分表示 该指纹唯一性的特征用数值的形式表达出来。为了比对的准确性，要求 特征提取算法尽可能多地提取有效特征，同时滤除由各种原因造成的虚 假特征。 指纹识别的过程实际上就是指纹特征比对的过程，因此指纹特征提 取的好坏决定着整个识别系统的成败。特征提取又包括提取什么样的特 征、用什么方法提取特征、提取到的特征是不是能够代表该指纹特点的 1 5 第二章自动指纹识别系统 真特征等三个问题。 如果脊线可以从指纹图像中准确确定的话，特征提取则是一件轻而 易举的事。然而在实际中，很难获得精确的指纹脊线图。目前的特征提 取算法都与输入图像的质量密切相关。由于一些因素，如职业，采集设 备等，指纹图像并不总是清晰的脊结构。因此，可靠的特征提取算法应 当不以精确的脊结构为基础，并且性能随着图像质量的下降而平稳下滑。 前面已经提到，指纹图像中存在两种类型的特征：全局特征和局部 特征。全局特征通常用于指纹的分类，局部特征通常用于指纹的比对。 目前大部分指纹识别系统使用的局部特征都是美国联邦调查局( f b i ) 提出的细节点匹配模型，它利用末梢点与分支点这两种特征来鉴定指纹。 本文也采用提取末梢点和分支点的细节点匹配模型。 2 3 4 指纹匹配 给定两个模板，匹配算法可以确定这两个模板是否来自同一手指。 匹配之前要先定义一个表征两个模板相似程度的量度。匹配是根据事先 定义的阀值来确定匹配结果的。 在应用特征点表征法的情况下，指纹识别被归结为点模式匹配问题。 在理想情况下，如果：1 ) 参考模板和输入模扳的对应关系已知。2 ) 不 存在平移，旋转，变形等。3 ) 指纹图像中的每个特征点都可被准确找到。 那么，指纹识别只需对两个模板中匹配的特征点计数即可。然而判断从 一个手指两次提取出的指纹，特别是在相隔很长一段时间之后，是否出 自同一手指，实际上是件极其困难的事。难度主要在于两个原因：首先， 如果两个模板( 参考和输入) 的确是匹配的，但这两组模板的参考特征 点的对应关系却是未知的。其次，成像系统会产生一些特殊情况，其中 有些对指纹成像是特有的： 【1 】不一致接触：由于传感过程造成指纹图像扭曲。手指与玻 璃板相接触，在压力的作用下，手指的三维曲面被映射到 玻璃板上的二维平面。通常这一映射是无法控制的，因此 造成映射的指纹图像具有不一致性。 2 】不均匀接触：如果指纹的脊能够与玻璃板完全接触的话， 1 6 第二章自动指纹识别系统 内： 脊结构可以被完整的捕捉到。然而由于皮肤的干燥程度， 皮肤病，汗液，灰尘，周围空气湿度等因素的影响，使得 接触并非是理想的，部分脊线可能没有与玻璃板接触到， 而部分谷区域反到可能与玻璃板接触上。这将产生低对比 度的图像，从而造成伪特征点或特征点遗失。 3 】无法再现的接触：由于手工劳作，事故等原因对手指造成 损伤，从而导致手指的脊结构发生永久性改变。这也会产 生出多余的伪特征点。 【4 】特征提取引入误差：由于特征提取算法并非理想，会引入 量度误差。而各种图像处理运算也可能造成特征点的位置 和方向与对应灰度图像上的位置方向发生偏离。 【5 】传感作用：传感过程本身会对图像引入噪声。指纹成像系 统对图像典型的扭曲通常是由于成像条件不理想造成的。 鉴于上述因素，在设计匹配算法时，必须将下面的前提情况考虑在 a ) 手指可能置于玻璃板的不同位置，导致输入模板和参考模 板间的位置偏移。 b ) 手指可能置于玻璃板的不同角度，导致输入模板和参考模 板间的旋转偏移。 c ) 手指可能施加在玻璃板上不同的向下压力，导致输入模板 和参考模板的空间尺度偏差。 d ) 手指可能施加在玻璃板上不同的切向压力，导致输入模板 和参考模板对应的特征点发生切向变换。 e ) 输入模板和参考模板中都可能存在伪特征点。 f ) 输入模板和参考模板都可能发生真特征点缺失。 g ) 特征点的位置可能与他们的“真实”位置发生波动，且波 动对每个特征点是不同的，但这种波动很小，在几个象素 之内。 1 7 第二章 自动指纹识别系统 h 、对应特征点间的波动相当大，不过是空间线性的。 i 1 对应特征点间的波动相当大，但是空间非线性的。 根据上面的某种或某几种前提条件设计的匹配算法，产生的结果可 能有很大的差异。在一种极端情况下，“欧氏空间”匹配算法只允许输入 模板和参考模板间有严格意义上的变换。在另一种极端情况，“拓扑结构” 匹配算法允许有最松散的变换，甚至包括顺序反转。对上述假定的不同 选择通常意味着某种性能的牺牲。只有对精度要求不高的场合才能不考 虑一些约束性的前提。 一些匹配算法以相似性交换为假定前提( 即上面的前提a ，b ，c ) ，因 而对伪特征点和特征点遗失具有一定的容忍性。“弹性”匹配算法容许特 征点在他们的位置上有小的波动，但对较大的波动无能为力。将两个脊 结构对正时，经常会出现这样的情况，在某一区域有最佳的对正位置时， 其他区域的特征点却又有较大的偏差，而且这种偏差是非线性的，无法 由一对特征点的偏差估算出其他特征点的偏差。因此一个好的匹配算法 应当不仅在全局相似性变换的情况下，而且在有切向变换( 前提d ) ，线 性和非线性形变( 前提h ，i ) 的情况下，都有很好的表现。 2 4 指纹识别技术的应用系统 2 4 1 指纹识别技术的应用系统的分类 随着指纹识别算法的发展，计算机安全、网络安全等诸多方向都开 始使用指纹识别技术。目前，利用指纹识别技术的应用系统可以分为两 大类：指纹识别系统( i d e n t i f i c a t i o n ) 和指纹认证系统( v e r i f i c a t i o n ) 。 认证系统是指通过和预先存储在系统中的指纹模板比较来确认个人 身份，也即一对一比较。识别系统是指通过搜索整个指纹模板数据库来 确认个人身份，也即通过一对多比较来实现个人身份确认。作为认证的 前提条件，他或她的指纹必须在指纹库中已经注册，指纹以一定的压缩 格式存贮，并与其姓名或其标识( i d ，p i n ) 联系起来，随后在比对现 场，先验证其标识，然后，利用系统的指纹与现场采集的指纹比对来证 明其标识是否合法的。验证其实是回答了这样一个问题：“他是他自称的 这个人吗? ”即“一对一匹配( o n e - t o - o n em a t c h i n g ) ”。识别则是把现场 1 8 第二章自动指纹识别系统 采集到的指纹同指纹数据库中指纹逐一对比，从中找出与现场指纹相匹 配的指纹。这也叫“一对多匹配( o n e t o m a n y m a t c h i n g ) ”。识别其实是 回答了这样一个问题：“他是谁? ”。例如，罪犯的判别，即将一个不明 身份的人的指纹与指纹库中有犯罪记录的人指纹进行比对，来确定此人 是否曾经有过犯罪记录。 2 4 2 典型的指纹身份验证系统 近年来，指纹产品开始逐渐应用于社会生活中，基本上利用认证方 式来确定个人身份。 这一系统主要用于用户身份验证。例如在多用户环境中可以代替口 令进行登录验证。该系统的结构如图2 5 所示： 图2 - 5 指纹身份验证系统 系统主要由四部分组成：1 用户界面。2 系统数据库。3 注册模 块。4 验证模块用户通过用户界面输入身份标识和指纹。系统数据库 中保有一组记录，每个记录对应一个授权用户。每个记录的组成如下： 1 9 第二章自动指纹识别系统 1 用户名。2 用户指纹的特征点模板。3 其他相关信息。 注册模块将用户的指纹注册到系统数据库中。当指纹图像和用户名 输入到注册模块时，首先用特征点提取算法提取出指纹的特征点，然后 用质量检测算法确保系统数据库中保有的都是质量较高的指纹。这样的 指纹包含有大量的真特征点。这一点至关重要。因为用只有少量真特征 点的指纹模板来验证是没有意义的。如果一个指纹图像的质量较差，则 需利用图像增强算法来提高脊谷的清晰度，再对增强后的图像提取特征 点。 验证模块对试图进入系统的用户进行验证。在用户将身份标识和指 纹输入之后，对输入的指纹提取特征点，然后和系统数据库中与标识对 应的指纹模块进行匹配运算，得出验证结果。 2 5 系统性能评估 指纹识别系统因为它的方便和可靠性得到广泛应用，那么它的准确 率到底有多少? 可靠性如何? 这是人们关心的问题，于是它的系统性能 估计和测试方法问题就被提出来了。 2 5 1 指纹系统的多种测试 性能评估包括三种类型和层次，分别是技术、现场和操作评估【1 们。 其中，技术评估的目的是算法的比较，它需要一个统一的指纹库，取自 通用指纹录入设备。其中的指纹质量最好可以根据需要进行调整，以便 适应不同程度的需要。而且它们不能事先被应试者得到，以示公正。验 证是在“离线”状况下进行的，并可重复，因为数据库是固定的。现场 评估的目的是针对一个特定应用检测系统的整体性能。检测时把整个系 统放在一个模拟真实应用的环境中，取指纹并进行识别，它