（通信与信息系统专业论文）基于小波变换的指纹识别算法的研究.pdf

基于小波变换的指纹识别算法的研究 专业：通信与信息系统 硕士生：周晓 指导老师：沈伟教授 摘要 指纹识别技术是人体生物识别技术的重要内容之一，己在众多领域得到程度 不同的应用。但就提高指纹识别的准确度及识别速度而言，进行指纹识别算法的 研究无论在理论上还是在应用上都具有十分重要的意义。图像增强、特征提取、 分类决策是指纹自动分类系统中最为关键的三个步骤。本文从这三方面出发，研 究并实现了基于小波变换和特征提取的指纹分类系统。在预处理阶段，采用数学 形态学的分割方法对图像进行有效的分割，将指纹图像从背景中提取出来，达到 削减数据和噪声的双重目的：并利用图像频域变换特征，应用g a b o r 滤波增强的 方法提高了图像质量。在特征提取阶段，对指纹图像作四层小波变换，对各层各 个方向的小波系数矩阵求取标准差并将其作为特征。为了体现局部细节，将指纹 图像的中心区域分成4 块分别作小波变换，这样一幅指纹图像就会得到一个长为 4 8 的特征向量。随后的指纹图像的识别即是对代表指纹图像的特征向量进行识 别。在分类识别阶段，采用两种分类器k n n 和s v m 分别进行有监督的分类识别， 实验表明这种基于小波变换的指纹识别算法具有较强的识别率。为了进一步提高 识别效率，需要在时间和空间上进行优化改进。为此对提取出的小波特征向量作 迸一步的特征选择和提取，即采用s f s 算法对4 8 维特征进行选择，去掉一些对 分类贡献不大的特征分量；采用k l 算法将4 8 维特征投影到低维空问进行降维 由此研究了一种基于m k l 变换的分类方法和一种低维空间的分类方法，实验表 明后者具有更高的识别率。将上述特征选择和特征提取这两种降维策略结合在一 起，通过实验验证先除去第一层小波分解系数，然后对余下的特征作特征提取的 k l 变换降维至1 5 维，所获得的识别效率和识别率都能达到较优水平，是行之有 效的。论文的最后对经典分类算法k l a n 的一些缺陷迸行了分析，提出了基于特征 选择的加权欧式距离计算方法，并将样本相似度和样本间加权欧式距离相结合对 k r i l l 算法加以改进。实验结果表明改进k n n 算法具有更高更稳定的识别率。 关键词：指纹识别，小波变换， s f s ，k l ，k n n 【 s t u d yo ff i n g e r p r i n tr e c o g n i t i o na l g o r i t h mb a s e do n w a v e l e tt | a n s f o r m m a j o r ：c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m n a m e ：z h o ux i a o s u p e r v i s o r ：p r o f e s s o rs h e nw e i a b s t r a c t b i o m e t r i c sr e f e r st ot h ea u t o m a t i cl d e n t i f i c a t i o no fap e r s o nb a s e do nh i s h e r p h y s i o l o g i c a lo rb e h a v i o m ic h a r a c t e r i s t i c s c o m p a r e dw i t ht r a d i t i o n a li d e n t i f i c a t i o n m e t h o d s , b i o m e t r i c sp r o v i d e sm o r ea d v a n c e da n dr e l i a b l es o l u t i o n sf o rs e c u r i t y p r o b l e m s a m o n gd i f f e r e n tt e c h n i q u e so fb i o m e t r i c s ，f i n g e r p r i n tr e c o g n i t i o nh a s g a i n e dg r e a ts u c c e s s e si nm a r k e t sb yr i g h to fi t sr e l a t i v e l yr i p e rt e c h n i q u e sa n dl o w e r p r i c e w h i l eas i g n i f i c a n tp r o g r e s sh a sb e e nm a d ei nt h er e s e a r c ha n dd e v e l o p m e n to f a 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 n , t h ea p p l i c a t i o no f t h et e c h n o l o g yd o e sn o tp r e v a i la t p r e s e n t t h er e a s o n i st h a tt h ea c c u m c ya n ds p e e do fr e c o g n i t i o ni sf a rf r o m s a t i s f a c t o r yt om a n yp r a c t i c a lc i r c u m s t a n c e s i m p r o v i n gt h ep e r f o r m a n c eo fa u t o m a t i c f i n g e r p r i n tr e c o g n i t i o ni sm e a n i n g f u l b o t hi nt h e o r ya s p e c ta n dp r o m o t i n gi t s a p p l i c a t i o n i m a g ee n h a n c e m e n t ，f e a t u r e e x t r a c t i o na n dd e c i s i o n m a k i n gf o r r e c o g n i t i o na r et h et h r e ep r i n c i p a la n dm o s tc r i t i c a ls t e p si na 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 ns y s t e m s i nt h i st h e s i s ，w ep r e s e n taf i n g e r p r i n tr e c o g n i t i o ns y s t e mb a s e d o nw a v e l e ta n ds o m ef e a t u r es e l e c t i o na l g o r i t h mu s e df o rw a v e l e tf e a t u r es e l e c t i o n i n p r e p r o c e s s i n gs t a g e ，w eu s eas e g m e n t a t i o nt e c h n i q u eo fm o r p h o l o g ym e t h o dt o d i s t i n g u i s hf i n g e r p r i n tf o r e g r o u n df r o mb a c k g r o u n d t h e n ，d i r e c t i o n a lg a b o rf i l t e ri s a p p l i e dt oi m p r o v et h ei m a g eq u a l i t y i nf e a t u r ee x t r a c t i o ns t a g e ，t h ef e a t u r e sa r e e x t r a c t e df r o mt h ew a v e l e tc o e f f i c i e n t sa f t e r4o c t a v e sw a v e l e tt r a n s f o r m t og e tt h e l o c a ld e t a i l ，w ed i v i d et h ec e n t r a ls u b i m a g ei n t o4n o n - o v e r l a p p i n gb l o c k s ，t h e nw e h a v eav e c t o rw h o s el e n g hi s4 8r e p r e s e n t i n go n ef i n g e r p r i n t t h ef o l l o w i n g r e c o g n i t i o no ff i n g e r p r i n ti sa c t u a l l yc l a s s i f i c a t i o nf o rt h ef e a m r ev e c t o r s i nt h ef i n a l s t a g e ，w ep u tt w oc l a s s i f i e rk n na n ds v m t os u p e r v i s o r yc l a s s i f i c a t i o n e x p e r i m e n t s h o wt h a tt h i sr e c o g n i t i o nm e t h o db a s e do nw a v e l e tt r a n s f o r mh a sah i i 业r e c o g n i t i o n r a t e t oi m p r o v ee f f i c i e n c yo ft i m ea n ds p a c e ，w en e e dt og i v es e c o n dt h o u g h to n i i i f e a m r ec h o i c ea n ds e l e c t i o no ft h ew a v e l e tf e a t u r e i nt h i ss t a g e ，w eu s es f s a l g o r i t h mt os e l e c tf e a t u r ef r o mt h e4 8 一d i m e n s i o n a lw a v e l e tf e a t u r e g e tr i do fs o m e u n i m p o r t a n tf e a t u r ep a r t ；i na d d i t i o n , w eu s ek la l g o r i t h mt ot r a n s f o r mt h ef b a n l r et o al o w e rd i m e n s i o n a lp r o j e c t i v es p a c e ，a n ds t u d yt w oc l a s s i f i c a t i o na l g o r i t h m sb a s e d o nm k lt r a n s f o r i l la n db a s e do nt h ei o w e rd i m e n s i o n a ls p a c e e x p e r i m e n t ss h o wt h a t t h el a t t e rh a sah i g h e rr e c o g n i t i o nr a t e t h e nw ec o m b i n et h et w os t r a t e g yf b a t u r e c h o i c ea n ds e l e c t i o nt o g e t h e rt od e c m a s ed i m e n s i o n so fw a v e l e tf b a t u r e m a n y e x p e d m e n t ss h o wt h a tp u t t i n gk l t r a n s f o r mt or e s i d u a lf e a t u r ea f t e rg e t t i n gr i do ft h e f i r s to c t a v ew a v e l e tc o e f f i c i e n ta n da tl a s tu s i n g1 5 一d i m e n t i o nf e a t u r et oc l a s s i r yc a n g a i ng o o dp e r f o r m a n c e ，b o t hi nr e c o g n i t i o nr a t ea n dt i m e f i n a l l y , w ea n a l y z et h e c l a s s i c a lc l a s s i f i e rk u n ，p r o p o s et h ew e i g h t e de u c l i d e a nd i s t a n c eb a s e do ns f sf c a t u m s e l e c t i o na l g o r i t h m ，a n di m p r o v e dt h ek n na l g o r i t h mw i t hs i m i l a r i t ya n dd i s t a n c e t o g e t h e r u s i n gt h i si m p r o v e dc l a s s i f i e r , w ec a l lg e t ah i g h e ra n ds t e a d i e rr e c o g n i t i o n k e yw 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 ，w a v e l e tt r a n s f o r m ，s f s ，k l ，k n n 第1 章绪论 1 1人体生物特征识别技术 当今社会，安全性对许多系统来说是至关重要的，比如银行系统、证券交易 系统等。在这些系统中，需要引入一定的身份验证机制来识别每个使用者，并且 进一步追踪和记录使用者的操作，来保证系统的可靠性。传统的验证用户身份的 方法多采用“用户i d + 密码口令”。但是这种保密机制存在明显的缺陷：首先， 对用户来说密码n 令的记忆是一个很大的负担：另外，这些密码n 令也容易被 黑客或恶意攻击者通过各种手段破译。 由于人体的身体特征具有不可复制的特点，人们把目光转向了人体生物识别 技术，希望将此技术应用到现行的系统安全领域。要把人体的特征用于身份识别， 这些特征必须具有唯一性和稳定性。因此人体生物特征识别技术就是通过验证个 人的生理或行为特征进行人的身份认证的技术。因为每个人的生理或行为特征都 是独一无二的，所以它比传统的身份认证方法更为可靠【l l 。 1 。1 1 人体的生物特征 人的身份认证所依据的人体生物特征基本上可以分为人的生理特征和人的 行为特征2 i t ”。人的生理特征为人体本身所固有，包括人脸、指纹、手形，耳形 热辐射与眼部特征( 视网膜、虹膜) ，腕部手部面部的静脉血管模式，d n a 、汗 毛孔、气味等。这些生理特征不随客观条件和主观意愿的改变而改变，因此可用 于人的身份识剐；入的行为特征也可以用于身份识别，如：语音识别、签名识别、 击键识别等。其中击键识别是基于人击键时的特性，如击键时的持续时间、出错 的频率、力度的大小以及不同键之间的时间差等，来达到身份识别的目的。 1 1 2 人体的生物特征识别技术 随着互联网的兴起，以及越来越多的电子设备进入人们的日常生活，计算机、 a t m 、门禁控制、各种智能卡对个人安全、方便的身份识别技术要求越来越高， 传统的身份识别方式渐渐不能满足社会的需要，人们迫切需要有准确、安全、方 i 中山大学硕士学位论文 便的识男技术。从以上的分析可以看出，生物特征识别相对于其它识别方法不仅 具有许多独到的信息安全角度的优点，更重要的是还具有很高的实用性、可行性。 因此，人体的生物特征识别技术在安全领域得到了广泛的应用。 在众多的生物特征识别技术中，指纹识别是一种最常用的，方便可靠的身份 鉴定技术。指纹的应用历史可以追溯到公元前，那时的中国人就在商业契约上按 指纹作为凭证。在当代的刑事科学中，指纹更得到了广泛的应用，可以用来确定 嫌疑犯。世界上许多国家都建立了指纹库，仅美国联邦调查局的指纹库中就存有 二亿张指纹卡f l 。 基于指纹的生物识别技术具有以下突出优点p 1 ： ( 1 ) 高稳定性。指纹具有很强的稳定性。它们的形成依赖于胚胎发育时期的环境， 从胎儿指纹的完全形成到人死后，指纹的纹线类型，结构、统计特征的总体分布 始终没有明显的变化。指纹是伴随人一生的最稳定的生物特征之一。 ( 2 ) 惟一性。科学实验和无数的事实证明，指纹具有明显独特的惟一性，并且纹 理本身非常复杂，其复杂程度足以提供用于鉴别的足够证据，包括双胞胎在内都 不可能有相同的指纹，任何两个人指纹相同的概率小于十亿分之一。 ( 3 ) 高可靠性。高稳定性和高惟一性决定了指纹识别的高可靠性。要想再增加指 纹识别的可靠性，只需要登记更多的指纹即可满足，而随便一个人都可以毫不费 力地提供l o 个手指的指纹信息。 ( 4 ) 易采集性。指纹与生俱来，随身携带，不需记忆。扫描指纹的速度非常快 采集指纹时只要将手指平放在指纹识别器上，l ，2 秒钟即可完成，免去了记忆密 码、丢失印章、遗忘密码和印章等烦恼。 ( 5 ) 伪造难破译难。由于指纹识别具有上述特点，识别指纹时必须将真正的手 指与指纹采集头接触，因此伪造、假冒、攻击、破泽指纹的难度就变得相当大。 指纹一直被人们用作“印章”使用。 可以看到，指纹识别技术为我们提供了一个方便、可靠的识别身份的途径。 它以其巨大的优势，显示出了强大的生命力。不但在学术上具有极大的研究价值， 而且有着极其广泛的应用领域。近几年，其研究成果和应用产品的数量直线上升， 逐渐取代过时的、不安全的身份认证方法。 基于小渡变换的指纹识别算法的研究 1 2 自动指纹识别系统 自动指纹识别系统( 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 ) 是随计算机技术的发展而兴起的。它利用模式识别和图像处理的理论和方 法，用计算机提取出采集得到的指纹的特征信息，然后再将这些特征存储在计算 机的硬盘上建立指纹特征库。这样，通过不是记录整幅指纹图像而是只记录那些 代表整幅指纹的特征信息可以大大的节省存储空间。识别时再通过计算机提取出 刚采集到的指纹的特征，和指纹库特征进行比较，从而达到身份鉴别的目的。这 种自动指纹识别系统比传统的手工识别具有不可比拟的高效率、容易操作的明显 优点。一个典型的a f i s 主要由指纹图像输入、指纹图像预处理、指纹图像特征提 取、指纹图像征匹配这四个部分组成”1 ，其系统框图如图1 - 1 所示。 压网 输入 i _ j 指纹图像 输入 指纹图像 预处理 指纹图像 预处理 嚣霎袭h 指纹特征 指纹图像 特征提取 指纹特征 数据库 图1 1 指纹识别系统框图 1 2 1自动指纹识别系统的结构 指纹图像 匹配结果 指纹的自动识别，方便了大容量指纹库的管理，加快了指纹搜索的速度。由 于其采用的识别方法不同，过程也不尽相同，但一股从获得指纹图到决定指纹类 型都将经过图卜t 所示的自动指纹识别的几个处理步骤：指纹采集、指纹图像预 处理、特征提取、指纹识别等。对各部分简要介绍如下： 1 ) 指纹采集”1 最早的指纹采集方法是用手指蘸上墨水或印油在纸上按压，然后用扫描仪摄 取，该方法由于不可靠早己经被淘汰。随着光学仪器、传感器及数字技术的发展， 各种快速、精确、方便、小巧的采集设备得到了应用。目前，主要使用光学扫描 仪和固态阵列传感器进行采集，前者用激光照在手指上，然后用c c d 阵列摄取其 反射光，由于反射光随指纹的脊和谷的深度不同而不同，因此可以得到指纹图像。 中山大学硕士学位论文 后者是用大量敏感元件组成的固态阵列芯片，他们采用电容传感、热敏传感或其 它传感技术，通过感受按压指纹的压力、热度等特征来摄取指纹。近年来，又出 现了其它一些新型的指纹采集设备，如超声波指纹采集器，它是基于指纹的脊和 谷的深度对超声波的不同反射原理而工作的。这些设备中，光学扫描仪因其技术 成熟度，性价比高而得到广泛的应用。 2 ) 指纹图像预处理 在指纹采集过程中，由于各种原因的影响，如指纹摄入时发生指纹畸变和扫 描仪采集不够精确等，经常使指纹模糊不清，造成脊线的粘连或断开，导致提取 的方向不能代表真正的纹线走向，产生伪特征，造成误分类和误识别。指纹预处 理部分一股包括两个步骤：图像分割与图像增强。图像分割通过剪切指纹图，在 基本不损失有用的指纹信息的基础上产生一个比原图像小的指纹图片，这样可以 减少以后各个步骤中所要处理的数据量。图像增强用以增强分割后的指纹图像， 提高图像质量。 实际的指纹识别系统往往由于应用环境、系统规模、实现思路以及具体算法 的不同，而在系统整体框架上有所差异，因此在增强的过程中有所区别。考虑到 两种不同的特征提取方法。增强也有所不同：一类直接从原始指纹图像中提取统 计性特征，该方法对增强要求比较少；另一类从预处理得到的指纹骨架图像中提 取细节点特征，该方法要求增强部分做大量的工作，包括除了一般的增强操作如 规格化、图像分割、求方向图、增强外还包括二值化、细化及后处理等步骤，最 后得到一幅纹线宽度为单像素的二值图像。在当前的应用系统中，后一类的方法 要比前一类应用得多一些。 3 ) 特征提取与选择 从不同的角度进行观察，指纹图像中存在两类特征：全局特征和局部特征。 全局特征是能够反映指纹整体形状的特征，通常用于指纹的分类，因此提取全局 特征的过程往往归于指纹分类步骤。局部特征指能够反映指纹细节点的特征，通 常用于指纹的对比。狭义的特征提取指局部特征的提取。两枚指纹经常会具有相 同的全局特征，但他们的局部特征点，却不可能完全相同。 指纹的主要局部特征信息有：端点( 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 ri s l a n d ) 、环点( e n c l o s u r e ) 及短纹( s h o r t r i d g e ) 等。在美国联邦调查局( f b ) 提出的细节点坐标模型中，只利用了端点和 基于小渡变换的指纹识剜算法的研究 分叉点两种特征点，如图i - 2 ( a ) 所示。另外两种重要的特征点是奇异点：中心点 ( c o r e ) 和三角点( ( d e l t a ) 。中心点一般位于纹线的渐进中心，三角点一般位于从 中心点开始的第一个分支点或末梢点、或者两条纹路会聚处，如图卜2 ( b ) 所示。 并不是所有的指纹都拥有这两个特征，因此常被用作指纹的子匹配。 ( a ) 端点和分又点( b ) 中心点和三角点 图1 - 2 常用特征点示意图( ( a ) 中“0 ”表示端点，“”表示分又点：( b ) 中“0 ” 表示中心点，“”表示三角点) 特征形成是指提取将用来作为分类依据的特征量，也称原始测量，原始特征 的数量可能很大，或者说样本是处于一个高维空间中，通过映射( 或变换) 的方法 可以用低维空间来表示样本。这个过程我们称之为特征提取。有些时候还可以再 选取一些最有效的特征，我们称之为特征选择。在习惯上，特征提取通常也用来 指特征形成和特征选择6 1 ”。 4 ) 指纹识别 对选择后的特征按照其相同类别的某相似性，制定分类判决准则，输出判 决结果。按照分类识别依据的不同，可以根据指纹脊线特征或细节特征进行识别。 按照分类决策的不同，特征分类方法可以分为最近邻法，神经网络法，支持向量 机等。 1 2 2 自动指纹识别的应用系统分类 利用指纹识别技术的应用系统可以分为两类，即认证( 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 ) ”。认证就是通过把一个现场采集到的指纹与一个已经登记的 指纹进行一对的比对( o n e t o - o n em a t c h i n g ) ，来确认用户身份是否与其真实 中山大学硕士学位论文 身份一致，即回答“他是他自称的那个人吗? ”的问题。作为认证的前提条件， 他或她的指纹必须在指纹库中已经注册。图卜3 是这种系统的结构框架。而指纹 识别是解决一对多的问题，就是把现场采集到的指纹和指纹库中的指纹进行逐一 的比较，从库中找到与现场指纹达到一定相似度的指纹，这也叫“一对多匹配 ( o n e t o l i i a n ym a t c h i n g ) ”。识别其实是回答了这样的一个问题：“他是谁? ” 识别主要应用于犯罪指纹匹配的传统领域中。因为目标的指纹库可能容量很大， 为了达到一定的速度，对于大多数的指纹识别系统都需要进行一个预先的指纹分 类程序。就是把指纹库按指纹中心区域纹理走向先进行分类。这样再通过对现场 采集到的指纹事先分类就可以大大的减少指纹的匹配数目，从而达到更快的识别 速度。图卜4 说明了指纹识别系统的框架。 图1 3 指纹认证系统框架图图1 4 指纹识别系统框架图 认证和识另u 在比对算法和系数设计上各具技术特点。例如认证系统一般只考 虑对完整的指纹进行比对，而识别系统要考虑残纹的比对；认证系统对比算法的 速度不如识别系统高，但更强调易用性 7 1 ：另外如前所述，在识别系统中，一股 要使用分类技术来加快查询的速度。 t 2 3 指纹识别系统的重要指标吲 由于计算处理指纹时，只是涉及了指纹的一些有限的信息，而且比对算法并 不是精确匹配，其结果也不能保证1 0 0 准确。指纹识别系统性能的重要指标是 6 基于小渡变换的指纹识异叮算法的研究 识别率( c r ) 、拒识率( f r r ) 和误识率( f a r ) 。在这里对这几个名词进行以下的说明， 用t n 表示匹配的总次数，c n 表示正确识别的次数( 包括应该识别而正确识别的次 数和不该识别而没有识别的次数) ，f n 表示误识的次数( 不应该识别而识别的次 数) ，r n 表示拒识的次数( 应该识别而没有识别的次数) 。则识别率c r = c n t n ，误 识率f a r = f n t n ，拒识率f r r = r n t n ，其中误识率和拒识率呈相反的方向变化， 即降低误识率，会增加拒识率；反过来，降低拒识率，又会增加误识率。图卜4 给出误识率和拒识率成反比的关系曲线。f r r 识系统易用的重要指标f a r 是系统 安全性的重要指标，由于f r r 和f a r 是相互矛盾的，这就使得在应用系统的设计中。 要权衡易用性和安全性。一个有效的办法是比对两个或更多的指纹，从而在不损 失系统易用性的同时，提高系统的安全性。 1 0 8 主 u6 三 置4 2 0 图1 5 误识率( f r r ) 和拒识率( f a r ) 的关系曲线8 1 1 3 指纹匹配研究现状 不管是指纹认证还是识别都涉及到指纹的匹配问题。指纹匹配是自动指纹识 别系统( a f i s ) 的核心研究内容之一，它在指纹特征提取之后，是自动指纹识别的 最后一步，也是非常关键的一步。指纹匹配要解决的问题是对从两幅给定的指纹 图像提取的特征信息进行匹配，判断这两枚指纹是否来自同一个指头。 目前指纹匹配方法大致可以分成两类。一类是基于点模式( m i n u t i a b a s e d ) 的匹配方法，一类是基于图像( i m a g e b a s e d ) 的匹配方法。很多指纹识别算法是 基于细节点匹配的因为普遍认为细节点是最独特、最可信的特征。目前最常用 的细节点有两种：纹线端点( r i d g ee n d i n g ) 和纹线分叉点( r i d g eb i f u r c a t i o n ) ， 如图1 2 ( a ) 所示。 中山大学硕士学位论文 j a i n ”o 的点模式匹配的松弛算法的思想是寻找一对匹配点，使得反映匹配程 度的相似变换最大，则将该点作为基准点对，然后根据相似变换的计算结果调整 待识图像的姿势，通过计算两幅图像落在同一界限盒的细节点数，统计最重的匹 配点对数，给出匹配结果。其中一些改进后的算法可容忍细节点在一个小界限盒 内的偏移，但是它们不能处理细节点偏离真实位置较远的形变。r a t h a ”1 等提出 一种基于点模式的匹配，用一般的h o u g h 变换来恢复两幅图像间的位置变换。 c h a n g ”等基于一般h o u g h 变换的方法将点模式转化为对h o u g h 变换参数空间中 峰值的检测。它将h o u g h 参数空间离散化，利用一个结构或特征匹配方法可以提 取出联系两个点模式间的变换参数并在h o u g h 空间中累积样本点。但如果只存在 少量可利用的细节点，在h o u g h 变换空间内积累足够的样本点以完成可靠匹配是 很困难的。而且它很难处理严重形变的情况。j a in ”等提出一种改进后的松弛 算法来降低匹配的复杂度。但是，算法需要反复执行且难以处理严重形变的情况， 这决定了其固有的复杂性。有些研究者采取能量最小化方法进行点模式匹配 ”“1 。首先基于可能相关性的初始序列定义能量方程，通过它估计一对点序列 问的相关程度；选取和使得优化算法譬如遗传算法、神经网络、模拟退火算法等 来达到一种可能的次优匹配。这些算法执行速度非常慢因而不满足实时指纹识别 系统的需求。j i a n g ”提出了指纹局部特征和全局特征相结合的匹配算法，这些 局部和全局特征实际上是由细节点构成的局部和全局区域特征，所以它们也可以 看作是点模式匹配。 基于图像的指纹匹配算法不使用细节点特征来匹配，这种方法一般没有预处 理( 去噪，二值化，细化) 而直接应用于灰度图像，从灰度图像中提取脊特征，并 用参数表征脊特征。而因为常常使用滤波器来提取脊特征，因此这种方法也叫做 基于脊的匹配方法或基于滤波器的匹配方法。它的缺点是没有考虑两图像位置、 方向、尺度上的偏差。j a i n ”引等提出一种基于g a b o r 滤波器的指纹特征表征方法 使用6 a b o r 滤波器对指纹图像进行8 个方向的滤波，把提取的各个方向上的特征码 组成指纹图像的特征。p a t i l 【2 0 l ，l i f e n gs h a 2 0 | 等提出了类似的通过提取特征码 来进行匹配的方法，不同的是他们的方法是将矩形区域分格提取特征，而j a t n 是在圆形区域中提取。j a i n b ”后来又提出了一种混合匹配的方法，将细节点匹 配和基于滤波器的匹配结合起来，这样在一定程度上克服了基于滤波器匹配没有 摹于小波变换的指纹【 ! 剐算法的研究 克服的旋转、平移误差，并且由于把得到的两个匹配分数共同构成最后的分数， 提高了识别率。但是因为引入了点匹配相应也加大了计算量。在小波在图像处理 中越来越广泛之时，很多研究者把它引入指纹识别领域。t i c o “等提出对指纹 图像进行几层小波变换后提取各个子图像的小波系数的标准差作为指纹特征码。 而后s t a c h a p b e t p i b o o n 等利用类似小波变换的方法对指纹图像进行f f t 和 o c t 来提取指纹特征码进行匹配。由于这种基于图像匹配的算法具有简易，快速， 识别效果好的优点，目前受到很多关注。 有些人提出基于图的算法”，本质上是一种拓扑的匹配器。它们容许一 般的变换、位置错误、细节点丢失及伪细节点出现。这些算法的性能严重依赖于 脊线特征及外部的指纹配准信息的可信度。在半自动指纹特征识别系统中，由于 细节点模式的配准及细节点和脊线特征的错误都可以交互式的修正，这些算法表 现出优异的性能。但是完全自动的指纹匹配系统不能一直保证正确脊线特征及外 部配准信息的可靠性。 1 4 论文的主要内容及其安排 本论文从实际应用的角度出发，着重就指纹图像的匹配算法进行了尝试性的 探索，力求在现有的算法基础上改进它们的不足，研究更具有实际应用价值的算 法。 图像增强、特征提取、分类决策是指纹自动分类系统中最为关键的三个环节。 本文从这三方面出发，对指纹识别的每个环节进行了研究，在每一个环节上使 用对指纹识别有利的方法对指纹图进行处理，研究并实现了基于小波变换和特征 提取的指纹分类系统。在预处理阶段，采用数学形态学的分割方法对图像进行有 效的分割，将指纹图像从背景中提取出来，达到削减数据和噪声的双重目的；另 外，利用图像频域变换特征，应用g a b o r 滤波增强的方法来提高图像质量。在特 征提取阶段，对指纹图像作四层小波变换，对各层各个方向的小波系数矩阵求取 标准差并将其作为特征。为了体现局部细节，将指纹图像的中心区域分成4 块分 别作小波变换，这样一幅指纹图像就会得到一个长为4 8 的特征向量。随后的指纹 图像的识别即是对代表指纹图像的特征向量进行识别。分类决策阶段，采用两种 分类器k n n 和s v m 分别进行有监督的分类识别，实验证明这种基于小波变换的指 9 中山大学硕士学位论文 纹识别算法具有较强的识别率。为了进一步提高识别效率，需要在时间和空间上 进行优化改进。因此对提取出的小波特征进行进一步的特征选择和提取。在这一 阶段，主要采用s f s 算法对4 8 维特征进行选择，去掉一些对分类贡献不大的特征 分量：另外采用k l 算法将4 8 维特征投影到低维空间进行降维，由此研究了一种 基于m k l 变换的分类方法和一种低维空间的分类方法。最后将特征选择和特征 提取这两种降维策略结合在一起，通过大量实验证明这种方法获得的识别效率和 识别率都能达到较优水平。论文的最后对经典分类算法k n n 的一些缺陷进行了分 折，提出了基于特征选择的加权欧式距离计算方法，并将样本相似度和样本闻加 权欧式距离相结合对k n n 算法加以改进。实验结果表明改进k n n 算法具有更高更稳 定的识别率。 本文后续部分分四章进行论述： 第二章给出对指纹的预处理方案。首先介绍了基于形态学的分割方法，然后 采用g a b o r 滤波器进行增强，并给出了每个步骤的实验结果。 第三章介绍了小波变换对纹理图像分析的特性，给出了利用小波变换进行指 纹特征提取的具体步骤。 第四章为本文的主体，对提取的特征采用k n n 和s v m 分类器进行分类，并通 过特征选择算法s f s 和特征提取k l 变换对小波特征进行降维，提高识别效率，得 到一个识别时间和识别率都达到较优的策略，最后利用s f s 特征选择算法对指纹 特征进行多次实验选择，得到每个特征分量的权重用于计算样本间的加权欧式距 离，然后使用样本相似度和样本间距离信息对经典分类算法k n n 进行改进并取得 更优的效果。 第五章对全文工作进行总结，分析了目前研究工作中需要迸一步完善的地 方，指出了今后的研究方向。 o 第2 章指纹图像的预处理 指纹图像的预处理过程，主要包括图像分割和图像增强。分割即是剪切指纹 图像，在基本不损失有用的指纹信息的基础上产生一个比原图像小的指纹图片， 这样可以在一定程度上减少后续处理的数据量。增强即是对由于各种原因造成的 质量不高的指纹图像进行去噪，突出或修复有用信息，提高图像质量，指纹图像 质量的高低直接关系到指纹特征提取的有效性和可信性，影响系统在匹配时的拒 认率和误认率，从而最终影响整个系统识别的结果，因此对指纹图像进行加强， 提高纹线的清晰度是非常有必要的。 本文对一种基于g a b o r 滤波的指纹图像增强方法进行讨论并加以实现。由于 局部指纹纹线脊谷交错近似平面正弦波。其傅立叶频谱具有明显的峰值，且峰 的方向和位置取决于纹线的方向和频率，因此采用具有良好方向和频率选择特性 的g a b o r 滤波器可以实现较好的增强效果。在这种指纹图像增强方法中，关键是 如何准确的计算指纹纹线方向和纹线频率。本章详细介绍了指纹图像的预处理方 法包括指纹图像的分割和增强，并给出了算法的流程及实验结果。 2 1 指纹图像分割 图像分割通常位于预处理的前端，其目的是把指纹图像中质量很差，在后续 处理中很难恢复的图像区域与有效区域区分开来。分割处理不仅能提高特征提取 的精确度，而且还能大大减少指纹处理的时间，尤其是当输入图像需要进行大量 的处理步骤时。所以图像分割应该在尽可能早的阶段进行，使后续处理能够集中 于有效区域，减少计算量。 在指纹图像中，感兴趣的只是由指纹的脊和谷组成的指纹区域，称之为前景； 而非指纹区域，即对指纹的识别无意义的区域，这些区域称之为背景，指纹图像 分割的目的就是要将指纹前景区域同背景区域分离开来，以避免在背景区域中提 取伪特征，这样能提高特征提取的准确性，同时节省处理时间，从而提高整个系 统的性能。因而指纹图像分割成为指纹图像预处理中一个必不可少的重要环节。 就目前来讲，指纹分割的方法是相当多的，常用的有方差法和方向法等。方 中山大学硕士学位论文 差法主要利用指纹前景区域中指纹脊和谷的灰度方差值较大而背景区域方差值 较小这一特性，对指纹图像进行分割。方向法则是利用指纹的前景区域具有方向 信息而背景区域没有方向信息进行分割。方差法算法简单，计算速度快，但对质 量较差的指纹分割效果不太理想。方向法很容易把奇异点区域当成背景处理掉， 且计算量很大四1 。因此本文利用一种更为简洁有效的分割算法，基于数学形态 学的方法。 2 1 1 数学形态学简介划 数学形态学是一种应用于图像处理和模式识别领域的新的方法，基本思想是 用具有一定形态的结构元素去度量和提取图像中的对应形状以达到对图像分析 和识别的目的。用于描述数学形态学的语言是集合论，因此它可以用一个统一而 强大的工具来处理图像处理中所遇到的问题。形态方法中图像信息的基本单元是 二值像素。利用数学形态学的以下几个基本概念和运算，将结构元灵活地组合分 解，应用形态变换达到分析的目的。 ( 1 ) 膨胀 已知二值图像a ，如果 ， ， 是由二值图像b = 6 i ，b 2 ，以 中像素值 为l 的点平移得到的，则a 由b 平移的并称为a 被b 膨胀，即； a o s = u 4 膨胀具有结合性、交换性。这样，在进行膨胀的步骤序列中，完成运算的顺 序就不重要了。这就允许我们将一个复杂的形状拆成几个简单的形状，然后重新 组合成为膨胀序列。 ( 2 ) 腐蚀 腐蚀是膨胀的相反过程。二值图像a 经二值图像口腐蚀后在p 点仍为1 的充 分必要条件是：b 平移到p 后，口中的l 像素也是a 中的l 像素。a 被b 腐蚀可用 下式表示： a o b = i p i b 。椰 二值图像8 常常是规则图像，是作用于图像中的一种探针，也称为结构元。 腐蚀在许多应用中起着十分重要的作用。结构元对一幅图像进行腐蚀会生成一幅 基于小渡变换的指纹识剐算| 圭的研究 包含结构元所有位置的图像。 图2 一l 到图2 2 是一个倒t 形结构元对一个简单物体进行嘭胀与腐蚀运算的示 意图。用结构元进行膨胀或腐蚀运算也可蛆描述为：结构元的原点像素经过待膨 胀的二值图像中所有l 像素点时，对应结构元所有l 像素的待膨胀二值图像像素置 为l 像素；在腐蚀运算过程中，结构元的原点像素经过待腐蚀的二值图像中所有1 像素点时，如果结构元中有一个l 像素没有对应待腐蚀二值图像的l 像素，则对应 结构元原点的待腐蚀二值图像l 像素置为o 。 蝌田 圃圈 图2 2 膨胀与腐蚀实验结果。( a ) a 被8 膨胀，其中原始像素a 的边界用粗 黑线表示。( b ) a 被口腐蚀，其中原始像素爿的边界用粗黑线表示。 数学形态中的基本运算可以组合成很复杂的运算。用同一结构元( 探针) 腐蚀 后再膨胀可去除比结构元小的所有区域像素点，而留下其余部分，这一顺序称为 “开”运算。如用一圆形的探针将所有比探针小的区域删除t 实现抑制加性空域 细节的滤波。 中山大学硕士学位论文 与上述处理顺序相反的过程是膨胀后再腐蚀，称为“闭”运算，这种顺序会 填满比探针小的孔洞和凹状区。这些运算见图2 3 和图2 4 ，其中结构元采用了相 同的t 形结构。这样的滤波器可用来抑制空域特征或区分基于尺寸的物体类型。 所用的结构元不一定是简洁的或规则的，可以是任意模式的像素点集合。这样可 以探测到具有一定分布的图像特征。 国圄 图2 - 3 “开”运算( 左：腐蚀；右：膨胀。图中的粗黑线表示原始图像边界) 避圈 图2 - 4 “闭”运算( 左：膨胀：右：腐蚀。图中的粗黑线表示原始图像边界) 2 1 2 数学形态学用于指纹图像分割 本文主要使用形态学的基本运算来滤波提取指纹的前景区域。算法步骤： 1 对边长为 ，个像素的矩形结构元对指纹灰度图像进行腐蚀( 实验中取n = 5 ) ， 并将腐蚀图像的像素值平方用以加强对比度。 2 使用直方图双峰法得到的闽值( 图像由前景和背景组成，在灰度直方图上，前 后二景都形成离峰，在双峰之间的最低谷处就是图像的闽值所在) 对加强图像进 行二值化，对二值化图像取反得到掩模。 3 对掩模图像进行开运算腐蚀运算，即对掩模图像的背景黑色区域去除小黑块， 对前景白色区域填补空洞，腐蚀边缘，最后得到最终的掩模图像t a s k 。 4 用掩膜m s k 对原图像相乘得到最终分割图像。 1 4 善于小渡变换的指纹识剐算法的研究 利用上述算法对图2 5 指纹图像进行分割所得的分割掩模如2 6 分割图像如 图2 - 7 所示： 图2 5 原图像 图2 - 7 分割图像 2 2 指纹图像增