（信息与通信工程专业论文）指纹特征点提取及比对.pdf

电子科技大学硕士学位论文 中文摘要 自动指纹识别系统有着广泛的应用背景。指纹识别是使用在个人自动识 别上很热门的生物特征科技。指纹识别在刑事侦查中的应用是广为人知的， 现在其正被广泛应用于安全系统。这主要是由于随着科学技术的进步，越来 越多的电予设备不断进入人们的日常生活。例如电脑、自动提款机、电话、 门禁控制、各种身份识别的智能卡等。这些产品对安全、方便的个人身份认 证要求越来越高。假如没有很好的身份识别与授权系统就不能很好的开展电 子商务、电子政务，也无法真正做到个人通信和三网合一。而生物技术的唯 一性使其广泛用于安全系统，指纹识别相对予其它生物识别技术，有易于采 集，处理方便，实时性高等优点，更易于在人们的目常生活中推广使用。 结合上述背景，本文研究并总结了指纹识别基本原理和关键技术，介绍 了目前使用的指纹识别的算法。通过对算法及其实现的可行性的对比，尤其 是钊对在手机中的指纹识别，对其算法进行适当的优化和简化，用纹形比较 的方法，设计了一种以d s p 为核心的指纹识别终端。本文详细介绍了该终端 的设计与开发过程，包括其硬件组成、软件实现的预处理、二值化、细化、 中心点搜索、特征点提取、去伪、建模、比对等各个模块。测试结果表明， 该指纹识别终端达到了识别指纹的基本要求。在该终端的开发中，笔者负责 系统的软件设计、p c 机上的软终端的实现以及整机的调试与测试等。 本文第一部分( 第一章到第二章) 探讨了指纹识别的基本原理及关键技 术等；第二部分( 第三章到第五章) 介绍我们的指纹识别终端的开发过程， 包括该系统的分析、设计、实现和测试等。 关键词：指纹识别中心点分叉点端点特征点 电子科技大学硕士学位论文 a b s t r a c t i tw a sa b r o a d a p p l i e d i n m a n y f i e l dt h a ta 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 。f o r e x a m p l e ，s p y i n g o n c r i m i n a t i o n ，c o m p u t e r ，c a s h d i s p o n s e r ，t e l e p h o n ea n da l lk i n d so fc a p a b l ec a r do f i d e n t i f i c a t i o n 。o n ea n d o n l yo fb i o l o g i ct e c h n o l o g ym a k e si t b ew i d l yu s e di ns e c u r es y s t e m s 。t h e i d e n t i f i c a t i o no f f i n g e r p r i n tc o m p a r e w i t ho t h e rb i o l o g i ci d e n t i ct e c h n o l o g i e s ，i t h a sm a n y a d v a n t a g e s ，f o ri n s t a n c e ，t e n dg a t h e r ，c o n v e n i e n c ed i s p o s e ，r e a l t i m e i ti sp r o n et ob eu s e di nd a i l yl i f e 。 i nt h i st h i s e s ，w e i n v e r t i g a t e a n ds u m u pk e y s t o n e a n dt h e k e y o f t e c h n o l o g yi nf i n g e r p r i n ti d e n t i f i c a t i o n 。w ei n t r o d u c es o m ea r i t h m e t i c st h a ta r e m a k i n gu s eo ff i n g e r p r i n ti d e n t i f i c a t i o na tt h ep r e s e n tt i m e 。ic o m p a r ef e a s i b i l i t y o f t h e s ea r i t h m e t i c sa n di t sa c h i e v e ，m o r e o v e r ，im a d ea r i t h m e t i co p t i m i z ea n d p r e d i g e s t 。ip a r t i c u l a r l yi n t r o d u c et h ep r o c e s so f t h ef i n g e r p r i n ti d e n t i f i c a t i o n s d e s i g n a n d e x p l o i t a t i o n 。i n c l u d i n g h a r d w a r ef o r m 、s o f t w a r er e l a t i o n 、 p r e t r e a t m e n t 、m i n u t e 、c e n t e rh u n t 、c h a r a c t e rp i c k - u p 、m o d e l i n g k e yw o r d s ：f i n g e r p r i n l i d e n t i f i c a t i o n c e n t e rb i f u r c a t i o n e n d p o i n t m i n u t e i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致 洌的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得电子科技大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 签名：日期：肋年年岁月g 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位 论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以 将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：受廷 导师签 日期： 电子科技大学硕士学位论文 1 1 指纹识别研究的意义 第一章引言 随着科学技术的进步，越来越多的电子设备不断进入人们的日常生活。 例如电脑、自动提款机、电话、门禁控制、各种身份识别的智能卡等。这些 产品对安全、方便的个人身份认证要求越来越高。假如没有很好的身份识别 与授权系统就不能很好的开展电子商务、电子政务，也无法真正做到个人通 信和三网合一。 尽管人们现在越来越多的依赖像智能卡、身份证、密码等保护措施来进 行人的身份认证，但是各种各样的损失仍时有发生。现行的许多计算机系统 和个人通信系统大都采用密码识别的方法来进行用户的身份认证和访问控 制。但实际上，这些方法隐含着一些问题。例如，密码容易被忘记，也容易 被人窃取和破解。据有关资料统计，对5 3 3 名i t 经理的调查表明，在公司内 部，非授权使用计算机系统的工作人员从2 0 0 1 年的4 2 增长到2 0 0 2 年的4 9 ， 并且因此造成的损失超过1 亿美元；假信用卡所造成的损失年在4 0 亿到 6 0 亿美元之间。人们需要在与机器之间交互交易时安全方便，也即需要简单 快捷的使用机器而不用担心安全隐患。因此，迫切需要有一种准确、方便、 安全的识别技术来替代现有的身份识别。 这种新的识别技术所识别的对象必须具有长期不变性和唯一性。人体的 生物特征均具有不可复制的唯一性，所以用它们来识别人的身份是最安全、 最可靠、最方便的方法。人的生物特征分为身体特征和行为特点两类。身体 特征包括：指纹、掌型、眼睛( 视网膜和虹膜) 、人体气味、脸型、皮肤毛孔、 手腕手的血管纹理和d n a 等；行为特点包括：签名、语音、行走的步态、 击打键盘的力度等。根据生物识别技术采用的生物特征的不同，广泛应用的 生物特征识别技术可以被分成三类：高级生物识别技术( h i g h b i o m e t r i c s ) ， 如：视网膜、虹膜和指纹；次级生物识别技术( l e s s e rb i o m e t r i c s ) ，如：掌 型识别、脸型识别、语音识别、签名识别，第三类是“深奥的”生物识别技 电子科技大学硕士学位论文 术( e s o t e r i cb i o m e t r i c s ) ，如：血管纹理识别、人体气味识别等。在这些众多 的特征识别中，指纹识别是最为成熟、应用最广泛的生物识别技术。 1 ，2 指纹识别的发展现状 目前，基于通用p c 机进行指纹识别的技术已经很成熟，并且已经开始 大规模推广。许多大公司有专门的机构从事该项技术的研究、开发、应用， 包括i b m 、i n t e l 、m i c l o s o f t 、d i g i t a l p e r s o n a 、i d e n t i x 、m o t o r o l a 、韩国现代、 朝鲜培富士、法国t h o m s o n c s f 、台湾a e t e x 公司、v e r i d i c o m 、b a c 等。 在技术上，基于w i n d o w s 操作系统的指纹识别软件和通过u s b 接口与p c 机相连的指纹采集器已经非常普遍。 另一方面，基于嵌入式系统特别是d s p 系统的指纹识别技术，无论是在 硬件设计还是算法软件方面都才刚刚起步，在p c 机上性能优秀的算法并不 一定就能简单的移植到d s p 系统中。然而，随着移动通信蓬勃发展和便携式 设备的推陈出新，指纹识别技术在今后将被更多的应用于嵌入式设备。因此， 基于d s p 平台实现指纹识别对于拓展d s p 的应用领域，让指纹识别从依赖 于p c 机向脱机使用以及提高系统灵活性、实时性、性价比都具有重大意义。 我们通过研究发现，t id s p 由于具有以下多个方面的特性，特别适合作 为嵌入式指纹识别系统的主处理器： 一一拥有c 3 0 0 0 、c 5 0 0 0 、c 6 0 0 0 、o m a p 等多个系列，能满足不同的指 纹识别场合的需要。由于指纹识别系统应用领域非常广泛，在不同的领域， 甚至是同一领域中的不同设备中，都需要采用不同系列的d s p 。比如：用于 个人通信的手机、p d a 等，采用c 5 0 0 0c o r e 或者o m a p 就是最佳选择； 在大型的指纹管理中心或网络核心设备中，当然首选c 6 0 0 0d s p ；在一般性 的应用领域，用c 3 0 0 0 或c 5 0 0 0d s p 是最好的性价比方案。 一一高效的指令集。t id s p 的指令集对算术运算、逻辑操作、控制操作 都有强大的支持，而且还专门针对数字信号处理提供了丰富的实用指令，这 对于既需要大量的数字信号处理又需要众多逻辑判断的指纹识别软件的开发 提供了很大的便利。 电予科技大学硕上学位论文 一一丰富的片上外设便于连接多种类型的指纹系统外设。嵌入式的指纹 识别系统除了d s p 以外，还需要外接指纹传感器、l c d 显示屏、键盘、指 示灯、扩展r a m 等多个外设，t id s p 可以方便的和这些外设无缝连接，这 剥简化系统设计，方便系统调试，缩短开发周期提供了很大的便利。 一一完善的软件开发环境。嵌入式的指纹识别系统功能的实现与完善很 火程度上依赖与其软件的开发。t ic c s 在开发d s p 软件方面的强大功能和 其全方位的技术支持有利于软件的调试。 1 3 本文研究的具体内容和课题来源 本文研究的内容来源于t i 杯竞赛的横向项目。该项目要求设计并实现一 个独立的手机中的指纹识别系统，包括指纹采集、预处理、细化、二值化、 特征点提取、比对以及显示终端等。笔者负责该指纹识别系统的特征点提取 及比列的设计与实现，通过在p c 机上的软终端的实现阱及硬件的调试与测 试等。通过对硬件的实际测试表明，本次设计达到了课题的预期要求。 本文由两大部分组成，第一部分( 第一章到第二章) 探讨了指纹识别的 基本原理及关键技术等：第二部分( 第三章到第五章) 介绍指纹识别终端的 软、硬件的开发过程，及算法的实现，包括该系统的分析、设计、实现和测 试等。 电子科技大学硕士学位论文 第二章指纹识别的介绍 2 1 指纹识别简介( i n t r o d u c t i o n ) 自动指纹识别系统( 即a u t o m a t e df i n g e r p o i n ti d e n t i f i c a l i o ns y s t e m ，简 称a f l s ) 有着广泛的应用背景。指纹识别是使用在个人自动识别上很热门的 生物特征科技。除了传统的在法律案件中的应用外，目前它也被在具有高安 全性的系统上，如作为嵌入式系统用于银行a t m 卡和信用卡使用的确认， 以及用于员工上下班监督、海关身份鉴定、家用门禁系统等许多方面。其主 要根据是根据生物统计学的研究，认为不同的人具有相同指纹的概率低到几 乎是不可能的。同时，指纹不会因年龄的增加而有所改变。因此在个人识别 上，指纹一直有其重要的地位。 目前指纹识别方法分为两大类：一是以手指毛细孔的位置，二是以手指 表皮上的凸纹和凹纹所形成的纹路为识别的基准。利用毛细孔来做识别，最 主要的困难是必须以雷射光来扫描毛细孔的位置，设备不易取得，然而毛细 孔的位置是永远固定不变的，而且毛细孔的位置不容易受外力而破坏，判断 成功率较高。凸凹纹线所形成的纹络，可经由油墨的按压在纸上，或经由扫 描器扫描进电脑后取得影像档案，藉此来做判断，所以取得非常容易，可是 此种方法取得的指纹，因为经过多次失真，使比对的错误率提高。 指纹纹络的系统匹配工作主要基于两个指纹的两个特征：纹形和特征点。 根据指纹纹线对中心点的总体流向，指纹可以分为五大类型：拱类、左 环类、右环类、尖拱类、漩涡类。指纹分类的主要目的是方便大容量的指纹 库的管理，加速指纹的搜索匹配。尽管许多研究者对指纹分类问题已作了大 量的工作，但到目前为止指纹分类的误识率仍居高不下，至今如何减少纹形 分类的误识率在指纹识别系统的研究中仍是一个难点。 正是因为指纹分类的这些问题，使得指纹匹配一般从指纹的细节特征入 手，用以判断两个指纹是否属于同一个人。所以指纹鉴定算法最终都归结为 电子科技大学硕士学位论文 在指纹图像上找到并比对指纹的特征点，所以特征点的提取是指纹鉴定算法 中的核心。f b i ( f e d e r a lb u r e a uo f i n v e s t i g a t i o n ) 提出的指纹的细节特征有下 列几种：端点、叉点、毛刺、短线和小环等。目前最常见的用于匹配的细 ：订特征是端点( 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 ) ，如图2 1 】所示。 这两种特征占了指纹特征点的8 0 以上。 图2 1 1 两种细节特征点 可以认为：隆起线上的端点和叉点在所有细节特征中占有主要地位。所以， 我们可以认为端点和叉点这两种特征点是表征指纹特征的有效特征，而且只 需要这两种特征点，就足够获得指纹图像的主要信息。 在用传统的抽取特征点的方法时，空洞、毛刺和短线等一些伪特征都被 抽取为特征点，而这些并不是指纹的有效特征点，我们应在进入最后的匹配 之前将这些伪特征点除去。 指纹系统的工作流程 指纹识别系统的工作流程是手指经活体指纹录入仪输入计算机内，形成 灰度指纹图像，然后进入图像处理过程，通过提取方向图、图像分割、图像 增强、细化，再经过抽取特征、伪特征去除后，进入比对过程，与库存指纹 匹配后，给出最后结果。其工作流程图如图2 i 2 ，其中算法处理并保存模板 和模板比对在第四章详细说明。 y = 0 ，z 0 和u + 2 x + 2 y 一2 z = 0 。 每行的系数由中间向两端很快地衰减，这是为了避免破坏大曲率的纹线构 型。滤波时，指纹图中每一点的灰度值由其周围的4 8 个点的灰度值及相应的 模板系数共同决定( 即灰度值与相应的模板系数相乘并把结果相加，然后赋给 中心象素点，作为其灰度值) 。滤波器应有连接断点和去除叉连的作用。根据 本文所设计滤波器的特点，如果指纹中出现断点，即这一点的灰度值比周围点 小得多，经过滤波器的处理后就接近周围点的灰度值了：如果指纹中出现叉连 点把相邻的两条脊线连接起来，则其上下两行的灰度值较大，而其同一行上邻 点的灰度值较小，经过滤波后叉连点的灰度值会明显降低。所咀此滤波器起到 了连接断点和去除叉连的作用。 得到水平方向的滤波器后，其它方向( 2 8 ) 的滤波器可由水平方向的滤 波器按下式旋转相应的角度得到。旋转后滤波器的坐标为i7 ，j ，水平方向 滤波器的坐标为i ，j 。 竺燃出 其中0 = ( d 一1 ) 8 为滤波器旋转的角度，d 为方向代码( 2 8 ) 。 电子科技大学硕士学位论文 图4 2 3 在新方向的滤波器上，( i7 ，j7 ) 位置的系数等于水平滤波器上( i ，j ) 位置的系数。( i ，j ) 经常不是整数值，此时该点上的系数需要用其周围点的 系数进行内插得到。设水平模板上( i ，j ) 周围四个点( f ，j ，) 、( j 。) 、 ( f 。，) 、( i 。，j 。) 构成一个l x1 的正方形，四个坐标对应的系数分别 为：g b ，j2 1 ，g ，i t ，j 。1 ，g o t t h ，j ! ，g h t 。，j 。) ，此处t f i ( i 。j i j j 。，我们用垂直于该l 1 的正方形的线段来表示，如图4 2 3 。 先对( ，- ，。) 与( 屯，l ) 进行线性插值，得： g ( j ，。) = g o ( i h ，。) + ( i 一) g o ( f 。，。) 一g 。( 扎j 。) ( 2 j 对另外两点线性插值，得： g ( i ，) = g o ( ，j f ) + ( i i l ) g 。( f 。，j f ) 一g 。( i ，j 川 ( 3 ) 最后对( i ，j 。，) 与( i ，f ，) 线性插值，得： g 。( 1 ，j ) = g ( i ，五) + ( i 一 ) g ( j ，五) 一g ( j ，鼻) ( q ) 将( 2 ) ，( 3 ) 代入( 4 ) ，可得内插表达式为： g 。( 1 ，j ) = ( j 。一j ) ( i 。一i ) g o ( f ，j j ) 十( i i t ) ( ，。一j ) g 。( f 。山) + ( j 一 ) ( t ，一i ) g 。( t ，。) + ( j 一 ) ( i 一) g 。( i 。，j 。) ( 5 ) 由此可得其余七个方向的滤波器模板的系数，这样八个滤波器模板都得 至f 了。 电子科技大学硕士学位论文 下 滤波 滤波时，根据每一个象素的方向值，选用相应的滤波器模板进行滤波如 33 f ( x ，y ) = 厂( x + i ，y + j ) g 。( i ，) 其中，g o ( f ，) 为相应的滤波器模版的系数。 4 3 二值化及细化 4 3 1 二值化 经过预处理后所得的指纹图像是一个灰度图像，需要将其进一步二值化。 二值化指纹图像是将灰度图像变成0 ，l 两个灰度级的图象，前景点( 指纹脊 线) 取作l ，背景点取作0 ，以把指纹脊线提取出来，便于后续处理。二值化 指纹图像是数字指纹图像处理与分析的主要对象，对指纹图像二值化的好处 在于使得图像的几何性质只与0 和1 的位置有关，不再涉及像素的灰度值， 使处理变得简单，而且能够压缩数据量。对于我们的指纹传感器采集到的图 像而言，二值化以后的数据量只有原始数据量的1 8 。图像二值化过程中的 闽值选择是关键。 一般的图像处理中的二值化算法主要是计算整幅图像的灰度平均值，然 后将该值作为门限，高于该门限的像素点就置0 ，反之置1 。我们通过研究发 现，这种方法虽然简单，但是对噪声较大，图像质量不好的指纹会产生较大 的二值化噪声。由于本系统是集成在手机中的，因此，我们综合了性能和算 法复杂性两方面的因素，选用动态阈值法作为二值化算法。 其思路是：将图像分为n * n f l 方块，对任方计算平均灰度值，将方块中 每个象素点的灰度值与平均灰度值进行比较，若大于平均灰度值，则将该象 素点灰度值置为零，反之置2 5 5 。分块的大小会对二值化效果产生一定的影响， 具体的大小选定将视程序调试情况丽定。 电子科技大学硕士学位论文 根据指纹图中脊线与谷线宽度大致相等的特点，即二值化后黑白象素的 个数应大致相同，采用局域自适应二值化算法。把指纹图分成w w ( w 为。一个 纹线周期) 的子块，在每一个子块内计算灰度均值： a v ：_ _ f ( i ，) w w 一 “i ，j ) 为子块内( i ，j ) 的灰度值。选用v e r i d i c o m 公司a g f p s 2 0 0 t 旨纹传感 器，根据指纹采集器的实际情况我们可以取w 为1 6 。由于采集到指纹的灰度值 是：如果是纹线，则灰度值相对较小，不是纹线则灰度值相对较大。所以， 在该块内若某一点的灰度值“i ，j ) a v ，则取“i ，j ) = 1 ；否则取f ( i ，j ) 2 0 。 对每一块都进行这样的处理，可以得到二值化的图像。对每一块都进行这样 的处理可得到图4 3 2 的二值化图像。 图4 3 1 原始图像图4 3 2 二值化后未去噪的图像图4 3 3 z 值化后去噪的图像 4 3 2 二值化后去噪 由于灰度去噪的不完全及二值化过程可能引入噪音，所以对二值化后的 指纹图像还需要进行一次二值滤波去噪，目的是去除或减弱图像中的噪音， 增强图像中有意义的部分。这一过程可以填补二值化后纹线上的孔洞或者删 除模式上的“毛刺”和孤立的值为1 的象素，即包括填充和删除两个算法。 1 ) 填充 填充算法把同时满足以下条件的象素p 值取为1 ： a ) p 为o 象素； b ) p 的四邻域中有三个或三个以上的邻点为1 象素。 电子科技大学硕士学位论文 图4 34 填充过程实例 2 ) 删除 删除算法把同时满足以下条件的象素p 值取为0 ： a ) p 为1 象素； b ) ( p 1 + p 2 + p 3 ) ( p 5 + p 6 十p 7 ) 十( p 3 + p 4 + p 5 ) ( p 7 十p 8 + p 1 ) 2 0 c ) p 不是端点。 图4 3 5 删除过程实例 fp 4p 3p 2 ip 5pp l fp 6p 7p 8 图4 3 6 模板 其c o p l p 8 ( 值为0 或1 ) 定义如图4 3 6 所示。去噪后可得到如图4 3 3 所示 的图像。根据图4 3 1 图4 3 3 可以看出：经过去噪后，原二值图中的大部分 孔洞和“毛刺”被有效地清除了。增加去噪后的二值化指纹图像更接近原始 的指纹图像。 。 4 3 3 细化及细化后的去噪处理 细化是图像分析、信息压缩、特征提取和模式识别常用的基本技术，它 使图像的每条纹线都变为单象素宽的“点线”，且细化后的纹线近似处于原 图的“中轴”。在指纹的自动识别过程中，指纹图像二值化后纹线仍然具有 定的宽度，而指纹识别只对纹线的走向感兴趣，提高识别的准确性，需要 对二值指纹图进行细化。这样可以大大减少冗余的信息，突出指纹纹线的主 要特征，从而便于后面的特征提取。 电子利技大学硕士学位论文 现在有许多细化算法，一种好的细化算法应满足下来条件：迭代必须收 敛；不破坏纹线的连接性：不引起纹线的逐步吞食；保护指纹的细节特征； 骨架纹线的宽度为1 个象素；骨架尽可能接近纹线中心线；算法简单、速度