（计算机应用技术专业论文）基于频谱能量和判别熵的指纹分类算法.pdf

山东大学硕士学位论文 摘要 自动指纹识别系统是生物特征识别研究的一个热点，而指纹分类又是指纹识 别系统的核心技术之一。在大型的指纹数据库中，待识别指纹与样本数据库中的 大量指纹逐一进行比对，是极其耗费时间的。为了减少搜索时间和计算复杂性， 把样本数据库中的指纹分为几类，将属于不同类别的指纹分别保存在不同的数据 库中，待识别指纹只需与属于同类的子数据库中的样本逐一比对。从某种意义上 讲，指纹分类实际上就是一次粗糙的指纹匹配过程，它为自动指纹识别系统提供 了一个索引机制。尽管国内外学者已经进行了大量的研究，但目前的指纹分类算 法对于低质量的指纹图像的分类效果还不够理想。因此，本文提出了基于频谱能 量和判别熵的指纹分类算法，此算法对低质量指纹图像具有一定的鲁棒性。 本文提出的指纹分类算法是以指纹方向图作为特征来进行分类的，首先计算 指纹方向图，然后提取特征并对特征进行降维，最后把特征送入分类器进行分类。 主要研究内容包括以下几个方面： 一、 基于频谱能量的方向图的构建。指纹方向图的获取是指纹分类中的一 个重要的步骤，但对于低质量指纹图像，现有方法获取准确的方向图仍存在 一定的局限性，因此本文提出了基于频谱能量的指纹方向图构建方法。首先 对指纹进行傅立叶变换，然后根据指纹频谱图中的能量分布特点计算指纹的 方向，从而得到指纹的方向图。由于指纹频谱能量图中指纹信息的分布特点， 使得这种方法不仅能够获得较为准确的方向图，而且对噪声有一定的鲁棒性。 实验结果表明了此方法的有效性。 二、基于判别熵最小化的特征提取。特征维数过多不但影响指纹分类的性 能，也会影响指纹分类的速度。因此本文提出了基于判别熵最小化的特征提 取方法，用于对特征向量进行降维，此方法的原理是判别熵越小，两类指纹 的概率分布差别越大，降维后的新特征就越有利于进行分类，实验结果表明 了此方法的可行性。 三、s v m 分类器的设计与实现。s v m 是一种针对两类的分类方法，它通 过寻找类别间的最优分类面进行分类，具有严密的数学解释。本文选用了 山东大学硕士学位论文 s v m 分类器来对指纹进行分类，首先将指纹划分为五种类别，对每两个类别 设计一个分类器，共l o 个分类器，然后使用训练集对各个分类器进行训练， 最后将待测样本送入训练好的分类器进行分类。实验结果表明了此方法的有 效性。 关键词：指纹；指纹分类；指纹方向图；判别熵最小化；s 分类器 i i 山东大学硕士学位论文 a b s t r a c t a u t o m 撕o nf i n g e 巾r i n tr e c 0 印i t i o ns y s t e mi sh o t s p o to fb i o m c sr e c o 舯i t i o n ，粕d f i n g e 叩r i n tc l a s s i f i c 撕o ni s0 n eo fk e yt e c l l l l o l o 影i nf i n g e 巾r i n tr e c 0 印i 石o n h 1l a 唱e 6 n g e 印r i n td a t a b a s e ，i ti st i m ec o n s u i i l i n g 也a tt h ei n p u tf i n g e 印打n tc o m p a r e d 、v i t l lm e r e f e r e n c ef i n g e r p r i n t si nd a t a b a s e i no r d e rt 0r e d u c es e a f c h i n gt i m ea n dc o m p l e ) ( i 够o f c a l c u l a t i o n ，r e f e r e n c ef i n g e 巾r i m s 访d a t a b 豁ea r ec l 嬲s i f i e di n t os e v e r a lc l 笛s e s ，缸da r e p u ti n t ot h ec o l l r e s p o n d i n gd a 协b a s e t h ei n p u tf i n g e 印r i n ti s0 1 1 l yc o m p 2 u r e d 谢mm e r e f e r e n c ef i l l g e r p r i n 住i i l l ec 0 丌e s p o n d i n gd a t a b 笛e h 1as e n s e ，删l y 铀g e 甲r i n t c l a l s s i f i c a t i o ni sr o u 曲p r o c e s so ff i n g e 叩r i n tr e c 0 印i t i o na n di tp r 0 、，i d e s 肌i n d e x m e c h 枷s mo ff i n g e 叩r i mr e c 0 印i 石o ns y s t e m t h r o u 曲n a t i v e 锄df o r e i 印s c h o l a r sh a v e m a d eal a 唱en 啪b e ro fr e s e a r c h e s ，c u r r e n tf i n g e 印r i n tc l 笛s i f i c 撕0 na l g o r i m mc 锄t s a t i s 母t h ea p p l i c 撕o no fl o wq u a l i t ) rf i n g e 叩r i n ti m a g e s s oe a c hs t 印o f6 n g e 叩r 血 c l a s s i f i c a t i o ni sr e s e a r c h e di nm i sp a p e r f i n g e 甲r i mc l a s s i f i c a l i o ni i lm i sp 印e ri sb a u s e do nf i n g e 叩r i n td i r e c t i o n a l 伊a p h f i r s t l y ，f i n g e 叩r i n td i r e c t i o n a j 伊印hi sc o m p u t e d t h e nf i n g e 叩r i mf e a t u r ei se ) 【t r a c t e d a n dd i m e n s i o no ff i n g e r p r i n tf e a n l r ei sr e d u c ed a tl a s t ，t l en e wf e a t u r ei ss e n ti n t o c l a s s i f i e r t h er e s e a r c hc 0 n t e n t sa r ea sf - 0 1 l o 、s ： 一、e ) ( t r a c t i o no ff i n g e r p n tm r e c t i o n a l 掣a p hi so n ei m p o r t 锄ts t e po ff i n g e 叩r i n t c l a s s i f i c a t i o n ，b u tf o rl o wq u a l i 够f i n g e r p r i n ti m a g e s ，i ti sc l i 伍c u l t ) rf o rc u l l r t m 讪o d st oe 妯r a c ta c c u r a t e 击r e c t i o n 址黟印h s oan e wm e m o db 笛e do nf r e q u 明c y s p e c t n l l l le n e 嗡ri sp r o p o s e d f i r s t l y ，t 啪s f o 咖t l l ef i n g e 叩血ti m a g e sf r o ms p 撕a l d o m 豳t 0f r e q u e n 呵d o m a j n ，血e n l ed i r e c t i o n a li m a g e sa r ec o n s t r u c t e da c c o r d j n g t 0f r e q u e n c ys p e 栅e n e r i g y b e c a u s eo ft h e 出s t r i b 而o nc h a r a u c t e r i s t i c so f f r e q u e n c ys p e c t n 肌朗e 唱y ，吐l i sm e 廿1 0 dn o to n l ye x t r a u c ta c c m ed i r e 曲o n a l 伊印h ， b u ta l s oh 嬲s o m et o l e r a l l c et 0n o i s e b 叩e r i m e n t a lr e s l l l t ss i l o wm ev a l i d i 够 h i g hm m e n s i o n a l f e a t u r en o t o n l y a 丑e c 侄 p e r f 0 肌锄c e o f f i n g e 印r i n t c l a s s i f i c a t i o n ， b u ta l s oa f f e c t s s p e e d o ff i n g e 印血tc l a s s i f i c 撕o n b e c a u s e m m e n s i o no fm ef i n g e 叩r i n tf l e a h j r ei st o oh i g h ，t h em e 山o db 罄e d0 nj - d i v e 唱e i l c e i i i 山东大学硕士学位论文 e n 仃0 p yi sp r o p o s ed j m v e 唱e n c ee n t r o p yi ss m 扣l e r 柚dp r o b a b i l i 钞d i s t 曲l n j o n 、i t l lt 、) v 0c l a s s e si sb i g g er - i ti sb e n e f i c i a lf o rf i n g e 叩r i n tt 0c l a s s i 够t h en e w m e d l o di sc o m p a r e d 谢1u s u a im e t l l o d so fd e s c e n m n gd i m e n s i o n ，a n de x p e r i m 锄t r e s u l t sh a v ep r o v e dt t l i sm e m o di sf b a s i b l e 三、s c l a s s i f i e ri su s e d 证“sp a p e r s 讧i sak i n do fm e m o d 、) v i t l lr i 9 0 r o u s m 础e m 撕c a l 唧l a n a t i o n 锄di ti sb yo p d m a lh y p e rp l a n et 0c l a s s i 矽f i n g e 甲r i n t h m i sp a p e r ，f i n g e 叩r i n ti sc l 舔s i f i e di n t 0f i v ec l 鹊s e sa j l df o re a c ht 、) v oc l 镐s 懿，0 n e s v mi sc o n s t m c t e d f i r s t l y ，s 1 mc l a s s i f i e r sa r e 仃a i n e db y 仃洳i n gs e t ，a n dt h e n m ei n p u t6 n g e 巾r i n ti ss e n di n t 0s v mc l a s s i f i e r s t h ee x p e r i m e n t sp r 0 v em e e 衔c i e n c yo ft h ea p p r o a c h k e y o r d s ：f i n g e r p r i n t ；f i n g e r p r i n tc l a s s i 6 c a t i o n ；f i n g e r p r i n td i r e c t i o n a l g r a p h ；m i n i m i z a t i o no fj - d i v e r g e n c ee n t m p y ；s v mc l 嬲s i f i e r 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：重盘整日期：垫q 呈：生! s 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：互查堑导师签 山东大学硕士学位论文 第1 章绪论 生物识别技术作为2 0 世纪末期才开始蓬勃发展的高新技术，必将在社会生活 中占据越来越重要的位置，从根本上改变人类的生活方式，网络信息化时代的一 大特征就是身份的数字化和隐形化，如何准确鉴定一个人的身份，保护信息安全 是当今信息化时代必须解决的一个关键社会问题。 生物特征识别( b i o m e t r i c s ) 技术是指通过计算机利用人体所固有的生理特 征或者行为特征来进行个人身份鉴定的技术【l 】。生理特征包括指纹，脸相、虹膜、 d n a 等，行为特征则包括笔迹、步态。我们将生理特征和行为特征统称为生物特征。 关于人的身份验证问题，传统的身份鉴别方法是把该问题转化为鉴别一些标 识个人身份的事物，这包括：( 1 ) 身份标识物品，比如钥匙、证件、a t m 卡等； ( 2 ) 身份标识知识，比如用户名和密码。与传统的身份鉴别手段相比，基于生物 特征识别的身份鉴定技术具有如下优点：不易遗忘或者丢失；防伪性能好，不以 伪造或者被盗；“随身携带”，随时随地可用等，因而得到了更广泛的应用。常 见的生物特征识别手段主要有手写体识别、耳型识别、人脸识别、脸部热量、指 纹识别、步态识别、手形识别、手部血管识别、虹膜识别、视网膜识别、手写体 识别和声音识别等二引。 近几年来，生物特征识别的市场份额也在不断扩大。据研究显示【9 】，整个生物 特征识别的市场总额已从2 0 0 0 年的$ 8 9 m 上升到了2 0 0 6 年的$ 7 3 5 m ，预计2 0 0 7 年 这一数字将达到惊人的$ 1 0 7 4 m ，平均年增长率达到了1 6 0 ，如图卜1 所示。 各种生物识别技术各有优势和不足之处。表1 1 列出了常用的7 种生物特征 识别技术的几个技术指标。从表卜1 可以看出，无论从唯一性和永久性来看，还 是从准确性和防伪性来看，指纹识别技术相对于其他生物识别技术来讲都具有很 大的优势。事实上，除了以上的几点外，指纹作为一种生物特征，还具有其他的 优势【l0 】：( 1 ) 使用指纹作为身份识别的手段已有很长的历史，为人们所广泛接受。 据考古发现，公元前7 0 0 0 一6 0 0 0 年，古代的亚述人和中国人就意识到了指纹的特 点，并使用指纹作为身份的象征，1 9 世纪中叶开始了对指纹在科学意义上的研究。 很早以前一些政府就开始使用指纹进行罪犯鉴别，如阿根廷在1 8 9 6 年，苏格兰在 1 9 0 1 年，其他一些国家在2 0 世纪初期也纷纷引入指纹技术鉴定罪犯。2 0 世纪6 0 山东大学硕士学位论文 图卜12 0 0 0 一2 0 0 7 生物特征识别市场总收入 生钫特捱瞢谄性嚯缝j j ( 久性可采集性准确性 可接受性防伪馕 人脸hlmelh h 指纹mhhmh m 手形 mmmhmm m 虹覆hhhmhll 搅阿改 hhmlhl l 手写体 lllh1 h h 声奔mllmlhh 表卜1 几种常见的生物识别技术性能比较。h ，m ，l 分别代表h i g h ，m e d i 岫，l o w 年代起用计算机自动识别指纹，自动指纹识别系统( a f i s ) 逐渐在全球开始了广 泛的应用。( 2 ) 指纹识别准确率较高，使用方便，有很好的应用前景。( 3 ) 采 集设备简单，防伪性能好。 1 1 自动指纹识别技术简介 基于指纹的身份识别系统是典型的模式识别系统。它包含两个主要的模块： 离线训练模块和在线识别模块( 鉴定或识别) 。离线训练模块指采集指纹数据， 提取代表这些数据的特征，将特征和相关的身份信息存入数据库：在线鉴别模块 2 山东大学硕士学位论文 采集待识别样本的生物统计数据，提取特征，然后在数据库中根据提取的特征进 行检索，找到最佳匹配( 鉴定模式) 或者根据用户所宣称的身份，从数据库中调出 相应的特征，决定它们是否匹配。 1 1 1 指纹采集 指纹识别的第一步就是进行指纹采集【1 1 1 3 】，本节介绍一下指纹采集的相关内 容。 从采集方式来看，所采到的指纹基本可以分为三类：捺印指纹、活体指纹和模 糊指纹( 见图1 _ 2 ) 。 捺印指纹指的是将沾了印墨的手指按压在某种东西( 通常是纸) 上留下指纹的 痕迹，再经相应设备转化为数字化的信息，就得到捺印指纹图像。捺印指纹采集 到的有效指纹面积比较大，但因采集方式所限，采集速度较慢，指纹缺陷较多， 且采集的质量难以严格控制。 活体指纹是指用活体指纹录入仪采集的指纹。根据录入原理的不同，活体指 纹录入仪可分为光反射式、电感式、电容式和超声反射式等几种。根据采集时指 头是否与指纹录入仪接触，又可分为接触式和非接触式。经活体指纹采集设备得 到的是数字化的指纹图像，相比较而言，活体指纹的质量是最好的。 模糊指纹一般是指在犯罪现场采集到的指纹。将罪犯无意中遗留在犯罪现场 的指纹痕迹经过显影、拍照和扫描等技术处理而得到的指纹图像。 其中活体指纹采集技术目前应用最广泛，当今所使用的主要指纹采集技术有 光学指纹采集技术、半导体指纹采集技术和超声波指纹采集技术。 ( 1 ) 光学指纹图像采集技术 光学指纹采集技术是目前应用最广泛的指纹采集技术，光学指纹采集设备原 理是光的全反射。光线照到压有指纹的玻璃表面，反射光线由c c d 去获得，反射 光的量依赖于压在玻璃表面指纹的脊和谷的深度以及皮肤与玻璃间的油脂和水 分。光线经玻璃照射到谷的地方后在玻璃与空气的界面发生全反射，光线被反射 到c c d ，而射向脊的光线不发生全反射，而是被脊与玻璃的接触面吸收或者漫反射 山东大学硕士学位论文 到别的地方，这样就在c c d 上形成了指纹的图像。 ( a ) 捺印指纹( b ) 活体指纹( c ) 模糊指纹 图卜2 指纹图像采集方式分类 光学采集设备有许多优势，它经历了长时间实际应用的考验，能承受一定程 度温度变化，稳定性很好，成本相对较低，并能提供分辨率为5 0 0 d p i 的图像。 光学采集设备也有不足之处，主要表现在图像尺寸和潜在指印两个方面。台 板必须足够大才能获得质量较好的图像。潜在指印是手指在台板上按完后留下的， 这种潜在指印降低了指纹图像的质量，严重的潜在指印会导致两个指印的重叠。 另外台板上的涂层( 膜) 和c c d 阵列随着时间的推移会有损耗，精确度会降低。 ( 2 ) 半导体指纹采集技术 半导体传感器是含有微型晶体的平面通过多种技术来绘制指纹图像。主要有 硅电容传感器、半导体压感式传感器和半导体温度感应传感器。 半导体指纹传感器采用了自动控制技术，能够自动调节指纹图像像素行以及 指纹局部范围的敏感程度，在不同的环境下结合反馈的信息便可产生高质量的图 像。半导体指纹采集设备可以获得相当精确的指纹图像，分辨率可高达6 0 0 d p i ， 并且指纹采集时不需要像光学采集设备那样，要求有较大面积的采集头。由于半 导体芯片的体积小巧，功耗很低，可以集成到许多现有设备中，这是光学采集设 备所无法比拟的。早期半导体传感器最主要的弱点在于：容易受到静电的影响， 使得传感器有时会取不到图像，甚至会被损坏，手指的汗液中的盐分或者其他的 4 山东大学硕士学位论文 污物，以及手指磨损都会使半导体传感器的取像很困难。另外，它们并不象玻璃 一样耐磨损，从而影响使用寿命。 ( 3 ) 超声波指纹图像采集技术 超声波指纹图像采集技术被认为是指纹采集技术中最好的一种，但在指纹识 别系统中还不多见，成本很高，而且还处于实验室阶段。超声波指纹取像的原理 是：当超声波扫描指纹的表面，紧接着接收设备获取的其反射信号，由于指纹的 脊和谷的声阻抗的不同，导致反射回接受器的超声波的能量不同，测量超声波能 量大小，进而获得指纹灰度图像。积累在皮肤上的脏物和油脂对超声波取像影响 不大。所以这样获取的图像是实际指纹纹路凹凸的真实反映。 总之，这几种指纹采集技术都具有它们各自的优势，也有各自的缺点。超声 波指纹图像采集技术由于其成本过高，还没有应用到指纹识别系统中。通常半导 体传感器的指纹采集区域小于1 平方英寸，光学扫描的指纹采集区域等于或大于1 平方英寸，可以根据实际需要来选择采用不同的指纹采集设备。 1 1 2 指纹匹配 指纹匹配首先对指纹进行特征点的提取，然后使用特征点来进行匹配。 1 1 2 1 细节点提取 细节点的提取首先要进行预处理，指纹图像的预处理主要包括图像分割、图 像增强、图像二值化、图像细化。 1 图像分割 图像分割就是把图像分成各具特性的区域并提取出感兴趣目标的技术和过 程，对指纹图像的分割主要是找出指纹区和非指纹区。指纹分割是指纹预处理的 第一个步骤，后续步骤都是在这个基础上进行的。对指纹图像进行分割后，后续 处理就可以只考虑我们感兴趣的指纹区，对非指纹区将不再重复计算，这样可以 为整体系统节省大量时间，提高整体系统的运行效率。如图卜3 所示，为指纹的 分割图。目前常用的分割方法主要包括：基于边界的分割算法、基于区域的分割 山东大学硕士学位论文 圈圈叠圈阐幽 0 囊量一j 参誊，j 翻 b ) 指纹增强图像 图卜4 指纹原图像及其增强图像 3 图像二值化l 二值化即将图像中灰度大于某闽值的像素的灰度置为l ，小于等于该闽值的像 山东大学硕士学位论文 素的灰度置为0 ，即将图像变为二值图像。常用的二值化方法一般是闽值分割法， 最简单的一种是根据整幅图像的灰度直方图中的峰值，确定二值化分割的闽值， 但是这种方法存在着很大的问题，因为在实际采集图像中，因为光照、手指按压 的用力不均等都会使得图像灰度不均衡，即有的地方过白，有的地方过浅，这样 无论所取的阈值伪多少，都不可避免的会将指纹纹线当作背景，造成大量信息的 丢失，这种情况在实际应用中是行不通的。最常用的局部阈值选取方法是自适应 局部闽值二值化方法，它比使用区域中值，区域均值二值化的效果都要好。指纹 图像二值化结果如图卜5 。 a ) 指纹原图( b ) 指纹二值化图像 图卜5 指纹原图像及二值化图像 4 指纹图像细化 指纹细化是使得到的二值图像在保持原有的纹路特征的前提下删除纹线的边 缘像素，直到纹线为单像素宽为止。现有的指纹细化算法主要有以下几种：快速 并行细化算法、o p t a 细化算法、串并行混合细化、中心扫描细化 1 4 一1 6 。细化结 果如网卜6 所示。在对指纹图像预处理后，对处理后的指纹图像进行特征点的提 取。 指纹的细节特征( m i n u t i a e ) 可以有1 5 0 种之多。但这些特征出现的概率并 不相等，很多特征是极其罕见的。一般在自动指纹识别技术中只使用两种细节特 征：纹线端点( n 电ee n d i n g ) 和分差点( n 电e b i n c “o n ) 。纹线端点指的是纹 山东大学硕士学位论文 ( a ) 指纹原图 图卜6 指纹原图像及细化图像 ( b ) 细化图 线突然结束的位置，而纹线分差点则是纹线突然一分为二的位置。大量统计结果 和实际应用证明，这两类特征点在指纹中出现的机会最多、最稳定，而且比较容 易获取。更重要的是，使用这两类特征点足以描述指纹的唯一性。通过算法检测 指纹中这两类特征点的数量以及每个特征点的类型、位置和所在区域的纹线方向 是特征提取算法的任务。特征点的类型和方向定义如图卜7 所示。 垂藿= = = = = = = ；兰皇 蚊钱自点 蚊线分里点 图l 7 指纹特征点的类型和方向定义：( a ) 类型，m 方向 山东大学硕士学位论文 网 逡兰鞫 ( a ) 指纹图像 图卜8 指纹图像及其细化圈 1122 指纹匹配 纛 ( b ) 细节点图像 红色代表端点、蓝色 指纹匹配要解决的问题是对两幅给定的图像提取特征信息，进行匹配，判断 这两枚指纹是否是同源的，即是否来自同一个指头。如：传统的点模式指纹匹配 一般是基于细节点( m i n 而a e ) 实现的。目前最常用的细节点有两种：纹线端点 ( r i g d ee n d i n g ) 和纹线分叉点( r i 电eb i 缸撕o n ) 。这两种细节点在指纹纹线中 出现的几率晟大，也最稳定，易于检测，且足以描述指纹的唯一性。指纹匹配靠 比较两枚指纹的细节点特征来决定指纹的唯一性。 根据指纹匹配的模式可以分为验证模式和辨识模式陋2 。】：根据操作过程不同 可分为自动匹配口1 也1 和人机交互匹配；根据匹配适应性可以分为弹性匹配2 4 l 和刚性匹配。不同的分类不胜枚举，然而这些分类方法都难以囊括所有的指纹匹 配算法，同时一些算法又可以综合多种分类的特性。 指纹匹配是自动指纹识别系统( a h s ) 的核心研究内容之一，它在指纹特征 提取之后，是自动指纹识别的最后一步，也是非常关键的一步。指纹匹配靠比较 两枚指纹的细节点、纹线或者其他局部结构特征来决定指纹的唯一性。然而，由 于采集设备的不完善性、采集条件的随机性以及预处理技术的局限，使得真正特 征点的缺失、伪特征点的存在和特征点定位偏差的情况普遍存在。所以，指纹匹 山东大学硕士学位论文 配必然还是一种模糊匹配，且需要具备一定的弹性。 113 指纹分类 图l 一9 模板指纹与待识指纹的匹配示图 指纹的分类是根据纹线的全局结构模式来进行的。人们经大量统计发现，虽 然纹线的全局结构模式因人而异，但变化的种类却是很有限的。这表明把所有指 纹分别归属于有限的几个不同类别是可能的，从而奠定了指纹分类的理论基础。 指纹分类的目的是提高1n 识别的效率。经过指纹分类后，在1 ：n 识别时输入 指纹只需同指纹库中与其类型相同的指纹进行匹配，从而大大减少了匹配次数， 提高1 ：n 识别的速度。 指纹分类的思想最早由eh i y 提出。他提出了著名的h e n r ys y s t e m 方法， 将指纹分为五种主要的结构类型：旋涡( w h o r l ) 、左旋( l e 舟l o 印) 、右旋( r i 曲t l o o p ) 、 拱形( a r c h ) 、尖拱形n t e da r c h ) 如图l - 1 0 所示。分类的依据是中心点附近的纹线 结构以及中心点、三角点的数量和相对位置。h e n i ys y s t e m 方法提出之后，在人工 指纹识别中获的成功应用。 山东大学硕士学位论文 ( a ) 漩涡( b ) 左旋( c ) 右旋 ( d ) 拱形( e ) 尖拱形 图卜1 0 指纹图像( a ) 表示旋涡形、( b ) 为左旋形、( c ) 为右旋形、( d ) 为拱形、( e ) 为尖拱形 对于自动指纹分类，主要关心以下几个方面的问题： 1 ) 指纹类型数目，也就是说将指纹划分为几种类型。 2 ) 指纹分类的一致性。相同的指纹的不同指纹图像划分为相同类型，这 是指纹分类的基本要求。 3 ) 指纹分类的准确性。分类的准确性是指自动分类应能准确的将指纹划 分为其所属的客观类型 4 ) 指纹分类的速度。指纹分类速度并不是很重要，因为指纹库中的指纹 可以在后台进行分类，在l ：n 识别时只需对待识别指纹进行一次分类操作。 指纹分类的难点在于很难对各种类型进行精确、定量的描述，且指纹结构变 化情况很多，有些类型之间出现交叉。即使是人也需要经过长时间的训练才能掌 握指纹分类的技巧，而且在分类时往往结合自身的经验。当指纹图像质量较差或 图像不完整时，很难提取出可靠、丰富的指纹特征，造成指纹分类困难。 1 2 指纹分类算法的研究现状 指纹分类是指纹识别系统的核心技术。在大型的指纹数据库中，待识别指纹 山东大学硕士学位论文 与样本数据库中的大量指纹逐一进行比对，是极其费时的。为了减少搜索时间和 计算复杂性，把样本数据库中的指纹分为几类，将属于不同类别的指纹分别保存 在不同的数据库中，待识别指纹只需与属于同类的子数据库中的样本逐一比对。 从某种意义上讲，指纹分类实际上就是一次粗糙的指纹匹配过程，它为自动指纹 识别系统提供了一个索引机制。指纹分类涉及的内容为指纹类型数目、指纹分类 的一致性、指纹分类的准确率和指纹分类的速度。 国内外学者已经对指纹分类算法进行了大量的研究。主要可分为基于奇异点 的指纹分类、基于结构的指纹分类、基于方向场的指纹分类、以及混合特征的指 纹分类。 1 2 1 基于奇异点的指纹分类 基于奇异点的指纹分类方法【2 6 1 是根据奇异点的个数及它们之间的关系来对指 纹进行分类的。如图1 1 l ，半圆表示c 0 r e 点，三角形表示d e l t a 点，此种方法把指纹 分为了下面类型：拱形、尖拱形、左旋、右旋、旋涡( 包括旋涡形和双旋形) 。 ( a ) 拱形 ( d ) 右旋 具体算法步骤如下： ( b ) 尖拱形 恭么蚕 ( c ) 左旋形 ( e ) 旋涡形( d 双旋形 引自参考文献【2 6 】 图1 1 1 指纹的简易类型 山东大学硕士学位论文 1 计算指纹图像的方向图。 2 平滑指纹方向图。 3 提取奇异点。 4 对指纹进行分类，按照如下规则 a 1 若有一对c o r e 点且一对d e l t a 点，则判为w h o r l b ) 若无奇异点，则判为拱形。 c 1 若有一对奇异点： i 若c 0 r e 点和d e l t a 点的连线是垂直的直线，则为尖拱。 若c o r e 点所在的脊线在d e l t a 点的左边为左旋。 若c o r e 点所在的脊线在d e l t a 点的右边则为右旋。 1 2 2 基于结构的指纹分类 m 【c l 垣lm s c h o n d 2 7 ，2 8 1 等人提出了基于几何结构的指纹分类算法，此算 法利用了指纹图像纹线的整体结构，把指纹分为5 种类型：双旋、旋涡、左旋、右 旋、拱形。如图1 1 3 所示，各种指纹类型的几何结构都有不同的特点，具体步骤如 下： 1 对指纹图像进行预处理。 2 对指纹图像的几何轮廓结构进行描述。 3 对几何轮廓进行后期处理( 得到图1 1 3 结构) 。 4 根据如下规则对输入指纹图像进行分类： a ) 有两个方向相反的转折，则为d o u b l ew h o r l 。 b ) 有两个相同方向的转折，则为w h o r l 。 c ) 转折的方向为顺时针为l e r1 0 0 p 。 d ) 转折的方向为逆时针为r i 曲tl o o p 。 e ) 无转折的为拱形。 山东大学硕士学位论文 ( a ) 双旋( b ) 旋涡( c ) 左旋 ( d ) 右旋( e ) 拱形 引自参考文献【2 7 】 图1 1 3 五种指纹类型的简易图 还有一种是使用句法的指纹分类现3 0 1 ，在此也可归为基于结构的指纹分类方 法，本方法把指纹分为1 2 种类型：平弓型、尖弓形、左上箕、右上箕、左下箕、 右下箕、斗型纹、正弦型双箕斗、余弦型双箕斗、s 型双箕斗、反s 型双箕斗、杂 型纹。它首先对指纹图像进行方向采样，将方向采样图进行平滑预处理，得到指 纹图像的折线表示：再把折线的各种端点及方向转折点用基元来表示，最后将指 纹图像表示为由基元组成的句子。通过描述指纹图像的句子来对指纹进行分类。 1 2 3 基于方向图的指纹分类 基于方向图3 1 ，3 2 1 的指纹分类是根据指纹图像相同类型的方向图相似，不同的 方向图之间存在着差别来进行分类的，如图卜1 4 所示，不同类型的指纹方向图的 方向趋势差别很大，算法的主要步骤为：首先对指纹图像进行预处理，然后计算 指纹方向图，提取指纹方向图中可以代表指纹类型的部分作为该幅指纹图像的特 征，最后把指纹特征向量送入分类器对指纹进行分类。 1 4 山东大学硕士学位论文 黝缀雾彩搽襄 ( a ) 左旋 ( d ) 拱形 1 2 4 混合特征指纹分类 ( b ) 右旋 图1 1 4 指纹方向图 ( c ) 旋涡 ( d ) 尖拱形 混合特征的指纹分类算法采用两种或两种以上的特征作为指纹的特征向量对 指纹进行分类，多种特征的组合可以使指纹图像的描述更加全面。 q i n z h iz h a n g 等人提出了结合奇异点和脊线结构的指纹分类算法，现有的 算法对于准确提取奇异点有一定的局限性，因此仅仅使用奇异点来进行指纹分类 是有困难的。此算法首先使用奇异点的个数以及它们之间关系来进行粗略分类， 然后在此基础上再利用指纹的几何结构来进一步对指纹进行详细分类。 j u nl i 【3 4 】等人提出了结合奇异点和方向图的指纹分类方法，此算法使用了方 向模型的系数和奇异点的信息作为特征，然后通过s 分类器进行分类。 1 3 课题选择 目前，基于奇异点的指纹分类算法是最常用的方法，对于高质量指纹，此种方 法也是最准确的。但对于低质量指纹来说，提取奇异点算法目前依然是一个难点， 伪奇异点出现和真奇异点的丢失都会直接导致分类的失败。指纹的纹线结构代表 山东大学硕士学位论文 了指纹的整体结构，但获取指纹结构的算法复杂度是相当高的，并且对于低质量 指纹此方法同样是很难获取指纹的整体结构。指纹方向图表明了指纹的纹线方向 趋势，它同样是依据指纹的整体来对指纹进行分类，但对于低质量指纹，目前的 方法也很难获取准确的指纹方向图。 因此，为了对低质量指纹图像有效的进行分类，本文提出了基于频谱能量和判 别熵的指纹分类方法。此方法首先利用指纹的频谱能量来的获得较准确的指纹方 向图，然后使用判别熵最小化对特征进行降维，最后使用s 分类器来对指纹进 行分类。 1 4 论文的组织与主要贡献 本论文分为五章，第一章为绪论，对指纹识别技术进行介绍，并对现有的指 纹分类算法进行了综述和分析。第二章介绍基于频谱能量的指纹方向图算法，第 三章介绍了基于判别熵最小化的特征提取，第四章介绍了指纹分类算法实现，最 后一章是结束语。 方向图作为指纹分类中的重要的一步，它获取是否准确直接影响到指纹分类 的准确率。现有的指纹方向图获取方法对于低质量指纹有一定的局限性，因此， 本为提出了基于频谱能量的方向图构建算法，此方法对于噪声具有一定鲁棒性， 能够较为准确的获取指纹方向图。 特征降维不仅能提高指纹分类的准确率，而且会加快指纹分类的速度。本文 方法获取的指纹特征向量维数较多，因而提出了基于判别熵最小化的降维方法， 判别熵考虑了各类的概率分布，确切的表达了各类的交叠状况，从而有效对指纹 特征进行降维。 分类器的选取是指纹分类算法的重要环节之一，本文中使用了s v m 分类器， s v m 在解决非线性模式识别问题时表现出许多特有的优势。同时本文引入了基于 质量的拒绝决策，对于一些质量过差的指纹不进行分类，从而降低了指纹分类的 错误率。 1 6 山东大学硕士学位论文 第2 章基于频谱能量的指纹方向图构建算法 2 1 指纹方向图算法研究现状 由于指纹方向图在指纹匹配和指纹分类中都需要，因此国内外学者进行了大 量的研究，目前存在的指纹方向图的获取主要有下面几种方法：基于梯度的方向 图构建盼3 引、基于模板的方向图构建3 9 1 、基于方向滤波器的方向图构副4 0 1 。 2 1 1 基于梯度的方向图构建 基于梯度的方向图获取算法是目前最普遍使用的方法。对于质量好的指纹图 像，此方法能够获得较为准确的指纹方向图，分块图像的梯度方向求取公式： 。+ ij + 了 屹( f ，_ ，) = 2 a 工( 甜，) a y ( 甜，v ) ( 2 1 ) ”1 ”广i = 妒( 器) 亿3 ) 其中，w 为块大小，a ，( ”，) 和a ，( “，v ) 是像素( u ，v ) 的梯度，臼( f ，- ，) 即是块( i ，j ) 的 方向。 2 1 2 基于模板的方向图构建 基于模板的方法是把方向归为8 个角度，此种方法计算的方向比较粗略，因 此对噪声有一定的容忍度，但获取的指纹方向不十分准确。所用模板如图2 1 所 示，具体步骤如下： ( 1 ) 八个方向对应的灰度值，_ s ，计算如下： s o = ，( f ，j 一4 ) + ，( f ，- ，一2 ) + j ( f ，歹+ 2 ) + ，( f ，歹+ 4 ) ( 2 4 ) 1 7 v甜ay甜a 砖口畸畸 = 山东大学硕士学位论文 而= ，o 一4 ，一4 ) + ，( f 一2 ，歹一2 ) + ，( f + 2 ，j f + 2 ) + ，( f + 4 ，_ ，+ 4 ) ( 2 5 ) 占：，s 。，s ，占。，s ，计算方法如上所求，其中i ( i ，j ) 为像素( i ，j ) 的灰度值。 6 543 2 75 4 3 o o l34 5 7 23456 图2 1 八方向模板 ( 2 )分别计算8 个方向中的最大值和最小值 s ，= m i n 墨 ( 2 6 ) s 2 = m a x 墨 ( 2 7 ) ( 3 ) 若中心像素处于脊线，则像素的方向为p ，若处于谷线，则像素的方向为 q ： d ：p矿( 4 c + s p + 5 。) 言：。( 2 8 ) 【g d 历p ，1 f s p 其中，c 为中间像素的灰度值。 2 1 3 基于方向滤波器的方向图构建 基于方向滤波器的方向图构建方法是针对指纹图像的频域图像来进行的，通 过使用方向滤波器( 图2 2 ) 对频域图像进行卷积来构建方向图，具体步骤如下： ( 1 ) 对图像块进行傅立叶变换。 f c ，= 篓篓撕川唧 一何等砌) 唧 一j 等n ) c 2 f ( 尼，) - ，( 肌，刀) 唧 _ 一l 等砌 唧 - 一l 等l n ( 2 9 ) 用= 0n = 0l 1 jl 1 j 其中，n 为块大小。 山东大学硕士学位论文 ( 2 ) 构建方向口对应的方向滤波器： m 十睁爿镊 1 其中 i ：筹秒，一p f ，p ，臼= 。，。，7 。， p = 1 6 。 ( 3 ) 使用每一个方向滤波器对指纹频率图进行卷积： ( 臼) = b ( f ，j ) i f o ，力i ( 4 ) 厂( 口) 最大值对应的口即为该块的方向： ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) 1 9 山东大学硕士学位论文 2 1 4 现状分析 基于梯度的方法是目前最普遍使用的方法，它通过求取像素或者块的梯度来 获取方向，如果指纹图像质量好，则此种方法求出的方向图比其它方法更为准确； 但此方法对噪声比较敏斟4 1 1 。 基于模板的方法也是较为普遍使用的一种方法，尽管此种方法对于噪声有一 定的容忍度，但它仅将指纹方向归为八个方向，因而计算不够精确。 基于方向滤波器的方法是在频域里使用方向滤波器来获取指纹的方向图，尽 管此方法对于低质量指纹有一定的容忍度，但是它通过对指纹图像的卷积来获取 指纹方向，算法复杂度比较高。 本文使用频谱能量来获取指纹方向图，首先利用傅立叶变换把图像转换到频 域，然后利用频谱图中能量分布特点来获取指纹的方向图。傅立叶变换是处理周 期性和方向性图像的一种有用的工具，它可以通过检测高频系数来去除噪声4 2 1 。 由于噪声大部分都处于频谱图中的高频区与低频区，因而此种方法对低质量图像 有一定的鲁棒性，能够较准确的获得指纹的方向图。 2 2 基于频谱能量的方向图构建 2 2 1 傅立叶变换 一幅尺寸为m n 图像f ( x ，y ) 的离散傅立叶变换h 3 1 由以下等式给出： 即，v ) 2 赤萎萎m 庐肛州州肌州 ( 2 1 3 ) 由于构建指纹方向图是在频域中进行的，因而首先对指纹图像进行傅立叶变换。 为了提高计算速度，本文使用快速傅立叶对指纹图像进行变换。如图2 3 所示， 指纹图像块( a ) 、( c ) 经过傅立叶变换后的图像为( b ) 、( d ) 。 本文使用的是n i s t 一4 指纹数据库中的指纹图像，大小为5 1 2 4 8 0 。由于指纹 图像边缘存在噪声( 一些手写字和线条) ，文中进行了简单的分割，为了便于后 面计算，分割后的指纹图像尺寸为4 8 0 4 8 0 。 山东大学硕士学位论文 ( d ) 图2 3 指纹图像块和对应的频谱图，( a ) 、( c ) 是指纹块，( b ) 、( d ) 分别是( a ) 、( c ) 所对应 的频谱图。 本文基于分块图像来构建指纹方向图。分块的方法为：指纹图像边缘的8 个像 素不进行分块，然后把中间的图像分成大小为1 6 1 6 的不重叠的块，由于块的尺 寸太小，容易受噪声的影响，因此把每一个1 6 1 6 指纹块扩展为大小为3 2 3 2 的块( 原块周围各加8 个像素) 。然后对指纹图像块进行快速傅立叶变换，最终得 到2 9 2 9 个指纹频谱图。 2 2 2 构建指纹的方向图 指纹图像的方向图是描述指纹纹线方向的图像。如图2 - 6 中的5 幅图像分别 是5 种指纹类型的方向图。 指纹图像作为周期图像，它