（计算机软件与理论专业论文）基于微特征的指纹识别算法研究.pdf

摘要 指纹具有唯一性、可靠性和稳定性的特征，在身份鉴别认证领域得到了广泛的 应用，其商业应用也越来越成熟。从指纹图像中提取高质量的指纹模板，并且实现 高识别率和鲁棒性的基于微特征的指纹匹配算法，是实现基于指纹的生物特征的挑 战应答认证的前提。同时，为了实现基于生物特征的挑战应答认证，需要摆脱目 前商品化的指纹认证系统，这些系统多数包含了厂家拥有知识产权的特殊技术。因 此，基于微特征的自动指纹识别技术依然是一个具有重要研究意义的课题。 在对国内外公开的指纹识别算法研究的基础上，本文重点研究了如何提取有效 的指纹模板和基于微特征的指纹匹配算法。本文的特色主要包括以下两个方面： 1 、提取有效的指纹模板。首先，为消除指纹图像中噪音的影响，利用预处理技 术进行指纹的图像增强，包括实验研究规格化、分割、方向场估计、频率场估计、 滤波增强、二值化等算法，并且提出基于h a r r i s 角点的分割算法的一种改进形式， 该算法不仅能够有效消除指纹背景区域带来的伪特征点，也可减少指纹图像预处理 的计算量。其次，通过对增强后的指纹图像进行细化，提取指纹微特征，并且设计 了基于微特征的脊线跟踪算法，能够消除因毛刺、桥、洞等伪特征结构产生的伪特 征点，从而提高指纹模板的质量。 2 、基于微特征的指纹匹配算法。本文提出一种改进的基于微特征的指纹匹配算 法，该算法不依赖于指纹的中心点和脊线结构等全局特征，并且采用相似矢量三角 形来解决点模式匹配算法中的关键问题：参考点定位。改进的基于微特征的指纹匹 配算法，不仅使得指纹模板的空间大小满足基于生物特征的挑战应答认证的要求， 而且算法对指纹的平移、旋转和形变情况具有较高的识别率和鲁棒性。 本文在p c 上使用m i c r o s o t tv i s u a lc h6 0 软件对所有算法进行了实验研究，编 程实现了一个自动指纹识别系统的原型，统计结果表明，系统达到了预期的目的， 满足课题研究的要求。 关键词：自动指纹识别系统；特征提取；点模式匹配 a b s t r a c t w i t ht h ec h a r a c t e r i s t i c so fu n i q u e n e s s ，r e l i a b i l i t ya n ds t a b i l i t y , f i n g e r p r i n ti sw i d e l y u s e di ni d e n t i f i c a t i o na n dv e r i f i c a t i o nf i e l d s ，a n di sb e c o m i n gam o r ea n dm o r em a t u r e b u s i n e s st e c h n i q u en o w a d a y s e x t r a c t i n gh i 曲q u a l i t yf i n g e r p r i n tt e m p l a t ea n ds t u d y i n g 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 sb a s e do ni i l i n 埘aw i 也1 1 i g ha c c u r a c ya n dr o b u s t n e s s ，a r e p r e c o n d i t i o n st oi m p l e m e n tc h a l l e n g e r e s p o n s ev e r i f i c a t i o n b a s e do nb i o m e t r i c s m e a n w h i l e ，i no r d e rt oi m p l e m e n tc h a l l e n g e r e s p o n s ev e r i f i c a t i o nb a s e do nb i o m e t r i c s ， w en e e dt og e tr i do fc o m m e r c i a lf i n g e r p r i n tv e r i f i c a t i o ns y s t e mw i t l lp r o t e c t e dp a t e n t s t h a tb e l o n gt oc o m m e r c i a lc o m p a n i e s t h e r e f o r e ，f i n g e r p r i n tr e c o g n i t i o ni ss t i l laf a r r e a c h i n gr e s e a r c hf i e l d b a s e do nm o u n t so fs t u d i e so nt h ef i n g e r p r i n th o m ea n da b r o a d , t h ep a p e rd o e s d e e p l yr e s e a r c h e so i lh o wt oe x t r a c th i 曲q u a l i t yf i n g e r p r i n tt e m p l a t ea n df 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 m sb a s e do nm i n u t i a t h ep a p e rc o n s i s t so fs e v e r a lc h a r a c t e r i s t i c sa s f o l l o w s ： 1 h i g j aq u a l i t yf e a t u r ee x t r a c t i o n f i r s t l y , t h ep r e p r o c e s s i n gt e c h n o l o g yi su s e df o r t h ef i n g e r p r i n ti m a g ee n h a n c e m e n t , i n c l u d i n gn o r m a l i z a t i o n , s e g m e n t a t i o n ，o r i e n t a t i o n f i e l de s t i m a t i o n ，f r e q u e n c ye s t i m a t i o n , f i l t e re n h a n c e m e n tb a s e d0 1 1g a b o r , b i n a r i z a t i o n a l g o r i t h m sa n ds o o n e s p e c i a l l y , t h ep a p e rp r o p o s e da ni m p r o v e ds e g m e n t a t i o n a l g o r i t h mb a s e do nh a r r i sc o m e r , w h i c hn o to n l ye f f e c t i v e l ye l i m i n a t e sf a l s em i n u t i a e f r o mt h ef i n g e r p r i n tb a c k g r o u n dr e g i o n , b u ta l s or e d u c e st h ec a l c u l a t i o no ff i n g e r p r i n t i m a g ep r e - p r o c e s s i n g s e c o n d l y , w i t ht h i n n i n g ，f e a t u r ee x t r a c t i o na n dr e d u c i n gf a l s e m i n u t i a ef r o mf a l s ef e a t u r e sb a s e do nr i d g et r a c k i n ga l g o r i t h m ，h i g hq u a l i t yf i n g e r p r i n t t e m p l a t ew i l lb eo b t a i n e d 2 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 mb a s e do nm i n u t i a t h r o u g hl o t so fr e s e a r c h e so 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 s ，t h i sp a p e rp r o p o s e da ni m p r o v e df i n g e r p r i n tm a t c h i n g a l g o r i t h mb a s e do ns i m i l a rv e c t o rt r i a n g l e ，w h i c hi si n d e p e n d e n to ft h e 西o b a lf e a t u r e so f f i n g e r p r i n t ，s u c ha st h ec o r ep o i n t sa n dr i d g es t r u c t u r e f u r t h e r m o r e ，t h ea l g o r i t h mi s c o n d u c t e dt os o l v et h ek e yp r o b l e mo ff i n g e r p r i n tm a t c h i n gb a s e do nm i n u t i a ：r e f e r e n c e p o i n to r i e n t a t i o n a n dt h ei m p r o v e df i n g e r p r i n tm a t c h i n ga l g o r i t h mb a s e do nm i n u t i a , n o t o n l ym a k e st h ef i n g e r p r i n tt e m p l a t es i z em e e tt h er e q u i r e m e n t so fc h a l l e n g e r e s p o n s e v e r i f i c a t i o nb a s e do nb i o m e t r i c s ，b u ta l s oo b t a i n sr e l a t i v e l yh i g ha c c u r a c ya n dr o b u s t n e s s t ot h ef i n g e r p r i n tt r a n s l a t i o n ，r o t a t i o na n dd e f o r m a t i o n i nt h i sp a p e r , a l la l g o r i t h m sa r et e s t e do nt h ep l a t f o r mo fm i c r o s o f tv i s u a lc 抖6 0 ， w i t ht h ep r o d u c t i o no fa na f i sp r o t o t y p e f i n a l l ys t a t i s t i ce x p e r i m e n t a lr e s u l t ss h o wt h a t t h ea f i sp r o t o t y p eh a sa c h i e v e do u rp r e d i c t e dg o a l sa n dm e e tt h er e s e a r c h s r e q u i r e m e n t s k e yw o r d s ：a f i s ；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 tm a t c h i n gb a s e do nm i n u t i a 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成果。 本人在论文写作中参考其他个人或集体已经发表的研究成果，均在文中 以适当方式明确标明，并符合法律规范和厦门大学研究生学术活动规 范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的资 助，在() 实验室完成。( 请在以上括号内填写课题或 课题组负责人或实验室名称，未有此项声明内容的，可以不作特别声 明。) 声明人( 签名) ：弓镌口风a 士s 汐c 7 年易月6 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大学 有权保留并向国家主管部门或其指定机构送交论文的纸质版和电子版， 有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书 馆被查阅，有权将学位论文的内容编入有关数据库进行检索，有权将学 位论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。 本学位论文属于 1 、保密( ) ，在年解密后适用本授权书。 2 、不保密( ) ( 请在以上相应括号内打“”) 作者签名 导师签名 日期：护7 年6 月乡日 吼呷年钼7 日 第一章绪论 1 1 引言 第一章绪论 随着计算机在现代信息社会的深入， 的问题。尤其是用户身份认证鉴别机制， 全性和可靠性要求越来越高。 安全性成为现代计算机系统必须首先考虑 作为安全体系的第一道关口，人们对其安 在目前的安全体系中，用户的身份鉴别主要来自以下三个方面： 1 你知道什么( w h a ty o uk n o w ) 。这种方法也称为基于知识( k n o w l e d g e - b a s e d ) 的鉴别技术。待鉴别者通过私有的知识和信息来证明自己的身份，如密码、 个人识别码( p 玳) 、口令等； 2 你拥有什么( w h a ty o uh a v e ) 。即基于令牌( t o k e n - b a s e d ) 的鉴别技术。待 鉴别者使用自己的私有物品如护照、身份证、驾驶证、钥匙等来证明个人身 份； 3 你是谁( w h oy o ua r e ) 。即生物特征识别( b i o m e t r i c s ) 技术。它基于人体 固有的生理特征( 如语音、指纹、掌纹、面部特征、虹膜等) 或行为特征( 如 步态、击键特征等) ，集成了验证( 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 ) 等 技术，对个人身份进行鉴定。 现行的许多计算机系统中，大部分是以”用户i d + 密码”的方式来进行用户的身 份认证和访问控制。但是，这种方案隐含着一些问题，例如，密码或者容易被忘记， 或者容易被别人窃取，统计报告显示因密码丢失或者盗窃造成的损失非常巨大。正 基于此，其他借助外部辅助设备进行的身份认证方式( t o k e n - b a s e d ) ，正在逐渐得 到推广，比如基于数字证书和u s b k e y 等方式。但是这些方式同样存在一些问题， 比如存在容易丢失、令牌管理难和更新复杂等问题。 生物个体的生物特征具有不可复制性的特点，将它们应用于身份鉴别中具有独 特的优势。用作身份鉴别的生物特征，首先需要满足以下几个方面的要求【l 】： 1 通用性：每个人都要有此特征； 2 唯一性：任意两个人的特征各不相同； 基于微特征的指纹识别算法研究 3 稳定性：该生物特征在较长的时间里不会改变，随时可以提取； 4 可采集性：该特征必须能够比较容易收集。 同时，为了满足身份鉴别的安全性要求，生物特征还必须考虑如下三方面的因 素【2 】： 1 可操作性：识别的准确性、速度和抗干扰性； 2 接受性：人们愿意接受这一生物特征识别的程度； 3 欺骗性：采取一定的欺骗技术导致这一技术产生误判的难易程度。 近年来，基于生物识别的技术逐渐成熟，应用也越来越广泛。人们研究和应用 作为身份鉴别的生物特征主要包括：虹膜识别、人脸识别、视网膜识别、掌纹识别、 语音识别、签名识别、行为识别等。下面是几种生物识别技术的比较( 2 】。 表1 1 基于生物特征的身份鉴别技术 类型通用性唯一性可接受性不变性可采集性可欺骗性 指纹较好鬲较好好好 难 虹膜好高较好好 较好 难 人脸好较低好较好较好易 掌纹一般一般一般较好好中等 语音一般较低好一般较好中等 签名 较低较低好难高易 d n a 一般好较好好较低难 由表1 1 可知，相对于其他的生物特征，指纹识别是一种更为理想的身份鉴别 技术。主要鉴于以下这几个方面的原因： 1 每个人的指纹都是独一无二的，两人之间不存在相同的手指指纹，而且同一 个人的不同手指的指纹各不相同，这样子很方便利用多个指纹来提高系统的 安全性； 2 每个人的指纹是相当稳定的，在人出生9 个月后，指纹就很难发生变化，而 且不会随着年龄的增长或身体健康程度的变化而变化。其他的生物特征，比 2 第一章绪论 如声音，容易变化； 3 指纹样本容易采集，指纹采集器的硬件生产制造已经变得比较容易，而且， 已经存在一些标准指纹库，这些使得研究和开发指纹识别系统变得很容易。 虹膜、d n a 等生物特征在目前的情况下，却没有这些特点； 4 指纹识别系统中使用指纹模板来进行身份验证和识别，指纹模板存储容量较 小，能够满足实时、在线的应用要求。 1 2 指纹识别技术的发展历史和研究现状 指纹识别作为生物识别技术有着悠久的历史。追溯到公元前7 0 0 0 年到6 0 0 0 年 以前，古叙利亚和中国就开始应用指纹作为身份鉴别，当时还主要应用在民间契约。 现代的指纹身份识别技术始于十六世纪的末期。1 6 8 4 年，英国的植物形态学者 n g r e w 发表了关于分析指纹的谷线、脊线、汗腺孔结构的系统研究成果，被认为是 关于指纹的第一篇研究报告。从此，对指纹的大量研究成果开始出现。1 7 8 8 年， m a y e r 首次对指纹的构造原理和脊线分布做出详细的描述。1 8 0 9 年，t b e w i c k 开始 用指纹代替印章，迈出了指纹识别历史上重要的一步。p u r k i n j e 首次提出指纹的分 类策略。h f a u l d 于1 8 8 0 年在英国g n a t u r e ) ) 杂志上发表论文，指出指纹具有唯一 性和不变性，并利用现场指纹来识别罪犯，这使得指纹在犯罪鉴别中得以正式运用。 十九世纪末，e g a l t o n 对指纹进行了更为深入的研究，在指纹分类中引入了细节特 征。1 8 9 9 年e h e n r y 建立了著名的h e n r y 指纹分类系统，该系统在1 9 0 1 年被英国 政府正式采用，政府在指纹用于身份识别的应用中起了重要的推动作用。 到了二十世纪早期，人们对指纹的构成开始有更深的认识，司法部门将指纹鉴 别正式规定为合法的身份识别方法。此后很多国家开始建立大型的罪犯指纹库。2 0 世纪7 0 年代，随着计算机的广泛应用和模式识别理论的发展，各个国家开始对自动 指纹识别系统( 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 ) 进行研究和应用。 美国的联邦调查局( f b i ) 和巴黎警方首先开发了自动指纹识别系统。在司法领域 取得的成功，促进了自动指纹识别系统在民用方向的发展。到了2 0 世纪8 0 年代， 随着个人电脑、光学扫描这两项技术的革新，指纹取像的工具发生质的飞跃，生物 3 基于微特征的指纹识别算法研究 指纹识别技术逐渐成熟，可靠的指纹匹配算法的出现大大促进了指纹识别技术的发 展。 近年来，自动指纹识别技术的应用，更加注重向系统的低成本、小型化和系列 化发展，系列化产品目前已有指纹锁、指纹开关、指纹保险柜等。在一些发达国家， 指纹识别技术已经被应用到银行金库、代保管库、博物馆、高级宾馆、高级公寓等 处的出入口管理中，同时在家庭保安、门禁系统等领域也有广泛地应用。 我国在自动指纹识别领域起步较晚，和国外还有一定的差距，近年来清华大学、 北京大学、中科院自动化所等科研机构对自动指纹识别系统进行了大量研究，提出 了很多种重要的研究成果。目前，指纹识别技术的应用正在逐渐展开，被广泛应用 于身份证、驾驶执照、医疗保障系统、自动提款机( a t m ) 、信用卡、计算机系统安 全、出入境检查等领域，极具经济效益与社会效益。 1 3 本文的研究背景和意义 本文研究课题的源项目是国家自然科学基金项目( 6 0 3 7 3 0 7 7 ) 。该基金项目研究 基于身份( i d e n t i t y - b a s e d ) 的数字签名技术，并且研究把基于生物身份的挑战应答 认证逆向转化为生物特征认证的可行性。 1 9 8 4 年s h a m i r 首次提出了基于身份的加密、签名、认证的设想【3 1 ，其中身份可 以是用户的姓名、身份证号码、电子邮件地址等。基于身份的密码系统中的用户公 钥就是用户的身份，或者是可以通过一个公开的算法根据用户的身份可以容易地计 算出来，而私钥则是由可信中心统一生成。基于身份的密码系统不存在传统p k i 认 证体系中c a 颁发证书所带来的存储和管理开销问题。 目前，基于身份数字签名算法中，比较常见的是s h a m i r 的算法【4 】。生物身份的 挑战应答认证，采用s h a m i r 算法，过程如下： 记挑战码为r ，应答码可表示为( x ，y ) ，它们按如下公式计算： x = k 。( m o d 拧) ， y = 一1 k ，”( r o o d 刀) ， 4 第一章绪论 其中，h ( r ，x ) 是哈希函数，帆e ) 是用户的r s a 公钥，即1 1 是两个大素数的乘积， e 是一个大整数，k 是一个随机数，p 是用户私钥，矿1 表示对求逆，满足 b = 夕( m o d 丹) ， b 是用户的生物身份，即其生物特征模版。应答码的验证可采用如下方程： y 。：6 1 x h ( 厂，x ) ( r o o d 拧) 。 从以上方程中解出b 。计算公式为 b = y 一，x ( ，工) ( m o d 疗) 。 采用s h a m i r 算法的缺点是应答码算法需要高阶乘方运算，固化成本较高。由国 家自然科学基金项目( 6 0 3 7 3 0 7 7 ) 及其后续研究提供的p k r 数字签名算法无需乘方 运算，速度可比s h a m i r 算法高出数百倍。我们不是利用给定的公钥去检验数字签名， 而是反过来先利用数字签名恢复公钥，再对其真实性进行检验，因此不仅需要保证 上述数字签名算法本身的安全性，还要证明算法在基于生物身份的挑战应答认证协 议以及特定生物特征认证技术构成的上下文中证明其用法的安全性。具体地说，该 基金项目需要完成的工作之一是证明当且仅当a s ( b ) 时，用户提供的令牌是有效 的，且用户必是该令牌的合法拥有者，其中a s ( 6 ) 代表所有能够与b 实现容差匹 配的生物特征构成的集合。 指纹具有唯一性，且指纹识别是目前应用比较成熟的生物识别技术，能够满足 基于身份的数字签名技术中对生物特征的要求。 目前国内外比较著名的自动指纹识别系统包括b i o k e y 、v e r i f i n g e r 、f i n g e r p a s s 等，很多厂商采用自己的算法、模板和硬件【5 】，厂商以中间件的方式提供给系统集 成商，内部封装了算法代码，最后提供给二次开发商的模板几百b y t e 以上，如u a r e u 4 0 0 0 b 提供的模板大小为3 1 0 或者1 1 5 2b y t e t 6 1 。 另一方面，在目前的基于身份的数字签名技术中，数字签名算法采用的身份信 息长度通常为1 0 2 4 或者2 0 4 8 位b i t ，过大的身份信息数据长度会大大降低数字签名 算法的效率。 从指纹图像中提取高质量的指纹模板，并且实现高准确性和鲁棒性的基于微特 征的指纹匹配算法，基于生物特征的挑战应答认证才有实现的可能性。同时，为了 5 基于微特征的指纹识别算法研究 实现基于生物特征的挑战j 立答认证，需要摆脱目前商品化的指纹认证系统，这些系 统多数包含了厂家拥有知识产权的特殊技术。因此，研究基于微特征的指纹自动识 别技术依然是一个具有重要研究意义的课题。 1 4 本文的主要工作和结构安排 本课题的研究目标是在指纹图像中提取有效的指纹特征模板，并且利用基于微 特征的指纹模板，设计准确、高效的指纹匹配算法，使之能够解决基于点模式匹配 算法中的关键问题：参考点定位，并且对指纹的平移、旋转和形变的情况具有较高 的识别率和鲁棒性。 本文共分七章，文章的结构安排如下： 第一章，绪论。简述身份鉴别的现状以及指纹识别技术的发展历史和研究状况， 指出了在目前指纹识别技术如此成熟的情况下本课题的研究背景和意义。 第二章，指纹识别的基本原理。主要描述指纹图像的几种特征模型，并对自动 指纹识别系统的构成和评价标准进行阐述。 第三章，指纹图像预处理方法研究。为提取有效的指纹模板，需要对指纹图像 进行预处理。本章对指纹预处理阶段的几个关键步骤：规格化、分割、方向场估计、 频率场估计、g a b o r 滤波增强、二值化等算法进行研究，并且提出基于h a r r i s 角点 的分割算法的一种改进形式，该算法不仅能够有效消除指纹背景区域带来的伪特征 点，还可减少指纹图像预处理的计算量。 第四章，指纹特征提取方法研究。本章研究指纹细化的原理，侧重分析基于 h i t - m i s s 转换的细化算法和特征提取算法。在此基础上，我们设计基于微特征的脊 线跟踪算法，该算法的特点是能够记录微特征点所在的纹线和发现可能的伪特征结 构，有效消除因噪音和细化算法等带来的伪特征点，从而提高指纹模板的质量。 第五章，基于微特征的指纹匹配算法。本章是本文的重点。在对国内外公开的 指纹匹配算法研究分析的基础上，侧重分析了基于微特征的点模式匹配算法以及点 模式匹配算法中的参考点定位。最后本文提出一种改进的基于微特征的指纹匹配算 6 第一章绪论 法，算法采用相似矢量三角形来解决点模式匹配算法中的关键问题：参考点定位。 该算法对指纹的平移、旋转和形变的情况具有鲁棒性。 第六章，自动指纹识别系统实验结果。本章详细介绍本文设计的自动指纹识别 系统的原型，并且在两种指纹库上，通过实验来显示指纹的特征提取和指纹匹配的 各个算法的性能。 第七章，工作总结和展望。 7 第二章指纹识别的基本原理 2 1 引言 第二章指纹识别的基本原理 指纹是指手指末端正面皮肤上形成的凹凸不平的纹路，即谷和脊的部分。指纹 的唯一性即是根据这些纹线的方向和分布特征来表示的。不同手指的指纹纹线的数 目、方向和相对位置是不相同的，弗且指纹具有稳定性，指纹的纹线特征并不随人 的年龄变化而改变。如图2 1 所示，深色部分为脊线，浅色部分为谷线。 图2 1 指纹的谷和脊 指纹识别的过程，就是对指纹的表面特征进行识别和比对的过程。因此，本章 将首先简要介绍指纹的几种特征类型，然后对自动指纹识别系统的构成和评价标准 进行阐述，以作为自动指纹识别算法研究的理论基础。 2 2 指纹图像的特征 人的指纹表面中包含大量的信息，这些信息被称为指纹特征。要进行指纹识别， 首先要提取指纹的特征( 指纹模板) 。指纹特征中，能够用来进行指纹识别的特征包 括两类：全局特征( g l o b a lf e a t u r e ) 和局部细节特征f 7 】，即微特征( m i n u t i a ) 。 9 基于微特征的指纹识别算法研究 2 2 - 1 全局特征 全局特征是指纹中的脊线和谷线所形成的全局特定模式，是那些用人眼直接就 可以观察到的特征，包括基本纹路图案、模式区、核心点、三角点等，它们提供了 对指纹纹路的全局的描述。 根据指纹的纹路图案类型的不同，我们可以将指纹分成3 类【7 】：弓型、箕型和 斗型，如图2 2 的( 1 ) ( 3 ) 所示。 ( 1 ) 弓型( 2 ) 箕型( 3 ) 斗型 图2 2 基于全局特征的指纹分类 如图2 2 所示，弓型指纹是指那些纹线从一边流入，中间像桥拱一样隆起，然 后从另一边流出的指纹。箕型指纹的一条或多条纹线从手指的一边流入，中间弯曲 折回，然后再从同一边流出。箕型纹线的对侧有一个三角形纹线区的上下纹线包围 着的中心花纹。箕型纹还可以分为左箕型和右箕型。斗型指纹的中心花纹为螺旋形 或成环形，它由内向外扩展与上下纹线汇合形成，即三种不同方向纹理的交汇点。 指纹的核心点( c o r e ) 和三角点( d e l t a ) ，被称为指纹的奇异点。根据指纹中奇 异点的个数、类型以及相对位置可以确定指纹的类型。如图2 3 所示。其中，核心 点位于指纹纹路的渐进中心，它是指纹中心部位脊线上曲率最大的点，可用于读取 或匹配指纹时的参考点。三角点位于从核心点开始的第一个分叉点或者断点、或者 两条纹路会聚处、孤立点、折转处，或者指向这些奇异点。三角点提供了指纹纹路 的计数和跟踪的起始位置。 1 0 第二章指纹识别的基本原理 图2 3a ：三角点，o ：核心点 弓形指纹没有中心点，即没有指纹纹线的渐进中心，中心花纹与上下包围线没 有明显界限，也没有三角形形状的纹线区。箕型指纹由一条以上完整的箕型纹线组 成中心点。斗型指纹至少包含两个核心点。 2 2 2 局部细节特征 指纹的全局特征，主要用于指纹的分类算法，指纹匹配时能够缩小搜索范围， 减少检索量。但是，指纹的全局特征并不能够用来指纹的精确匹配。目前的大部分 自动指纹识别系统都是基于指纹的局部细节特征。 指纹的局部细节特征，即微特征( m i n u t i a ) ，包括指纹纹线的终结点、分叉点和 转折点等。两枚指纹可能会有相同的全局特征，但不可能具有完全相同的局部细节 特征。不同指纹的局部细节特征的相对位置、方向、类型，能够表征指纹的唯一性。 目前，可以用于识别的局部细节特征有1 5 0 多种【引，其中常用的四种基本的指 纹特征为【9 】：末梢点( e n d i n g ) 、分叉点( b i f u r c a t i o n ) 、孤立点( d o t ) 和洞( h o l e ) ，其他经 常用到的细节特征还包括短脊( s h o r tr i d g e ) 、交叉点( c r o s s i n g ) 、脊线断裂( r i d g e b r e a k i n g ) 和桥( b r i d g e ) 等，主要特征如下： 1 末梢点：一条纹线的终结点； 2 分叉点：一条纹线在此分开成两条或更多条的纹线； 3 孤立点：一条特别短的纹线，以至可以看成一点； 4 洞：即存在两条或者两条以上的连接两个分叉点的纹线； 基于微特征的指纹识别算法研究 5 桥点：两条临近的平行纹线连接的交汇点； 6 短脊：一条较短但不至于成为一点的纹线； 因为指纹采集时的压力以及图像质量等方面的限制，指纹的绝大多数局部细节 点在实际中并不多见，它们在指纹中出现的概率如表2 1 所示【9 】。 表2 1 不同微特征的出现概率 特征 概率( ) 特征 概率( ) 末梢点 6 0 6分叉点2 2 6 孤立点4 3小孔0 7 短脊线 6 1 交叉点 3 2 桥2 5 从表2 1 可以看出，脊末梢点和分叉点出现的概率最高，它们占据了指纹局部 细节特征的8 0 以上。由于脊末梢点和分叉点相比其他局部细节特征，对噪声不敏 感，目前自动指纹识别系统中主要使用这两种指纹微特征。美国f b i 就是采取他们 来进行指纹匹配。 指纹的局部细节特征不仅仅采用类型来描述，通常还采用其他参数，如位置、 方向、曲率等。其中，方向用来描述特征点所在位置的纹线的走向；位置描述特征 点在直角坐标系中的水平坐标和垂直坐标，可以是基于图像坐标系的原点，也可以 是相对于指纹全局特征的核心点和三角点等；曲率能够描述特征点位置上纹线方向 的改变的速度。本文使用的指纹模板，根据指纹匹配算法的需要，将采用四元组( 水 平坐标、垂直坐标、方向、类型) 来描述指纹的局部细节特征。 2 3 自动指纹识别系统的构成 自动指纹识别系统是一种典型的模式识别系统，它利用图像处理和模式识别理 论来对指纹图像进行自动识别。一个典型的自动指纹识别系统通常包括：指纹图像 采集、指纹预处理、指纹特征提取、指纹分类、指纹匹配，如图2 4 所示： 1 2 第二章指纹识别的基本原理 2 3 1 指纹图像采集 图2 4 自动指纹识别系统构成 目前指纹采集方法主要有三种：光学传感器设备采集，晶体传感器采集和超声 波设备采集。 光学采集设备的使用起始于2 0 世纪7 0 年代，因此有悠久的历史。这种设备依 据图像依据的是光的全反射原理( f t i r ) 。光线照到压有指纹的玻璃表面，反射光线 由c c d 获得，反射光的数量依赖于压在玻璃表面指纹的脊和谷的深度和皮肤与玻 璃间的油脂。光线经玻璃射到谷后反射到c c d ，而射到脊后则不反射到c c d 。 晶体传感器，是最近才出现的技术，它通过多种技术来绘制指纹图像。电容传 感器通过电子度量来捕捉指纹，它的外面是绝缘的表面，当用户的手指放在上面时， 皮肤组成了电容阵列的另一面。电容器的电容值由于脊( 近的) 和谷( 远的) 之间的距离 不同而变化。压力感应传感器表面是具有弹性的压感介质材料，它们依照指纹的外 形( 凹凸) 转化为相应的电子信号。温度感应传感器通过感应压在设备上的脊和远离 设备的谷温度的不同来得到指纹图像。 超声波扫描被认为指纹采集设备效果中最好的一种。采集原理类似与光学扫描 器。超声波首先扫描指纹的表面，接收设备获取了其反射信号，测量它的范围，得 基于微特征的指纹识别算法研究 到脊的深度。相对于光学扫描，皮肤上的污渍和油脂等噪音对超声波获得的图像的 质量影响较小，获得的图像能够真实反映指纹的脊和谷。 以上三种指纹图像采集方法各有各的优缺点，设计人员应该根据具体情况，综 合考虑成本，设备要求的体积等各个因素考虑，选取最适合设计要求的指纹图像采 集设备。 2 3 2 指纹预处理 通过指纹采集器采集的指纹图像，由于受手指本身的因素( 如油渍、疤痕等) ， 以及采集条件( 潮湿、干燥、接触面环境等) 的影响，采集到的指纹图像会不同程度 地受到各种噪声的干扰，直接进行指纹特征提取和指纹匹配，会有很大的偏差。指 纹预处理阶段，就是要对图像的有效区域进行增强，减弱噪声，增加脊和谷的对比 度，并产生可容易进行特征提取的图像。这个阶段通常包括规格化、分割、滤波增 强、二值化等过程。指纹的预处理是提取有效指纹特征模板前的重要步骤。 2 3 3 指纹特征提取 指纹纹线的走向和分布，可以通过细节点特征的坐标、类型、方向等信息来表 示。要提取指纹细节点特征，必须先对预处理后的指纹图像进行细化操作，生成宽 度为1 的骨线图。然后，从这细化后的指纹图像中提取特征点的坐标位置、类型以 及方向等信息。这些特征点的信息，通常称为指纹模板( t e m p l a t e ) 。但是，由于噪音 等因素的影响，细化后的指纹图像中会存在不同程度的伪特征点，因此在提取指纹 模板前，需要对细化的指纹图像进行后处理，以消除伪特征点和保存真正的特征点。 2 3 4 指纹分类 指纹分类是根据指纹的整体结构特征将指纹分别归属到几个不同的预先设定的 类别中去【7 1 。在自动指纹识别系统中，为完成一次自动识别，待识别的输入指纹需 要与样本数据库中的大量指纹模板逐一进行比对。当样本数据库的容量非常大时， 识别过程可能耗费大量时间。把样本数据库中的指纹分为几个类，将属于不同类别 1 4 第二章指纹识别的基本原理 的指纹分别保存在不同的子数据库，输入指纹只需与属于同一类别的子数据库中的 样本指纹进行比对，因此能够有效减少匹配时的信息检索量。由于本文主要研究基 于细节点的指纹匹配算法，所以不具体对指纹的分类进行研究。 2 3 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 ) 。验证( 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 ) ：即一对多比对，使用者仅仅提供一个指纹并从数据库中寻找 一个匹配指纹数据，也即通过指纹特征来确定个人身份，解决的是这指纹是谁的指 纹的问题。基于微特征的指纹匹配算法是本文重点要研究和解决的问题。 2 4 自动指纹识别系统的评价标准 实际上，大部分指纹识别只利用到指纹的一些有限的信息，而且匹配算法并不 是精确匹配，因此，指纹识别系统也不能保证1 0 0 准确。 评价自动指纹识别系统的指标包括准确度、性能( 包括注册时间、验证时间) 、 拓展性、模板大小等。其中衡量准确度的重要标志是识别率，主要是以下两个方面： 错误接受率( 彤汰) ：表示将不同的指纹判断为相同指纹的概率，它衡量系统的 安全性，误识率越小则系统的安全性越高。 错误拒绝率( h 汰) ：表示将相同指纹判断为不同指纹的概率，衡量系统的易用 性能，若拒真率大，则合法用户经常会被拒绝。 1 5 基于微特征的指纹识别算法研究 事实上，f r r 和f a r 是成反比的，现实中都是根据不同的用途来调整这两个值。 如图2 5 所示，r o c ( r e c c i v c ro p e r a t i n gc u r v e ) 曲线给出f a r 和f r r 之间的关系： 错 误 拒 绝 率 勇 2 5 本章小结 错误接受率f a r 图2 5 温和f r r 的r o c 曲线 在本章，我们详细描述了指纹的几种特征类型，并对自动指纹识别系统的构成： 指纹图像采集、指纹预处理、指纹特征提取、指纹分类、指纹匹配等部分进行了简 要的介绍，最后阐述了自动指纹识别系统的评价标准。 1 6 第三章指纹图像预处理方法研究 3 1 引言 目前大多数自动指纹识别系统是基于指纹的局部细节特征( 微特征) 匹配的【”】。 因此，要进行指纹识别，必须先从采集的指纹图像中获得有效的特征点信息( 指纹 模板) 。 有效的指纹特征信息的提取，很大程度地依赖于指纹图像的质量。一幅理想的 指纹图像，脊线和谷线清晰，对比度高且噪音少，此时比较容易检测出指纹的脊线 并且能够精确定位特征点的位置，从而能够准确地提取指纹特征点，进行指纹的匹 配。但是，在采集指纹围像时由于手指按力不均匀，手指皮肤表面过干、太湿、 伤疤、脱皮等，以及采集设备表面的环境等设备本身的限制，都可能不同程度地存 在指纹纹线粘连、模糊或断裂等现象，如图31 所示： 图3 1 指纹图像的某个噪声区域 带有各种各样噪音的低质量的指纹图像，将会在指纹特征提取阶段至少带来三 方面的问题： 1 产生大量的伪特征点，导致最后的指纹模板的空间变大； 2 无法提取出真实的特征点，容易丢失真正的特征点； 玉提取出的特征点定位错误( 如位置和方向等) ，即提取出的特征点信息与真实 情况存在偏差。 基于微特征的指纹识别算法研究 如果提取的特征点信息不准确，指纹自动识别系统的准确性将面临挑战。本章 和第四章，将围绕如何提取有效的指纹模板展开研究工作。其中，第三章主要研究 指纹预处理技术来进行图像增强，以降低各种各样的噪音带来的影响，第四章将进 行指纹特征的提取，并通过一些后处理技术消除大量的伪特征点，从而提高指纹模 板的质量。 3 2 指纹预处理的步骤 指纹图像预处理，目的是使原始指纹图像经过预处理后，能够增强纹线的清晰 度，增加脊线和谷线的对比度，降低噪音的影响，和减少指纹的伪特征，最大程度 上去除指纹图中的叉连、断点以及模糊不清的地方。 传统的数字图像处理中常用的滤波方法，比如均值滤波、中值滤波、直方图均 衡化、十字形中值滤波等，如果只是简单地被用来对指纹进行图像预处理，将发现 效果并不理想。其中一个主要原因，就是忽略了指纹的独特性：纹路具有方向性。 正如前面章节阐述的，指纹的唯一性是基于纹线的走向和分布特征。因此对指纹图 像预处理，必须结合指纹纹线的方向来进行。 人们对预处理的算法进行了大量的研究，设计了许多高效的滤波器来进行图像 的增强。其中，l a w r e n c e0 g o r m a n 提出一种方向自适应滤波方法【1 2 】。该算法将滤 波器和局部的指纹纹路方向重合以实现指纹图像滤波。其中，纹路方向需要预先估 计，纹路的宽度则根据具体的指纹图像而设定的一个阈值范围。但是，指纹的纹路 宽度在大部分情况下差别很大，甚至在同一幅图像中，指纹的纹路宽度也会有很大 不同。如果纹路宽度超过了预先设置的范围，算法就会失效。b gs h e r l o c k 提出了 一种基于方向f o u r i e r 滤波器的方法【1 3 】。该算法首先根据不同的纹路方向和纹路宽 度设计一种分离滤波器组，然后分别利用不同的滤波器对图像滤波并得到一组滤波 图像，最后利用局部纹路方向将不同的滤波图像进行重组来重建滤波图像。在这种 算法中，当取非常大的滤波器组，算法就能取得很好的效果，但同时算法的性能会 急剧下降。k a m c it 则提出了另外一种基于f o u r i e r 变换的指纹图像增强方法【1 4 1 ， 他们利用两个分离的滤波器组分别处理纹路和局部方向，同时定义一个能量函数来 1 8 第三章指纹图像预处理方法研究 选择图像特征，比如频率和方向，然后通过选择图像特征最小化能量函数，增强的 函数由滤波图像重构产生。但是由于滤波器组的数量非常大