（计算机软件与理论专业论文）基于基准点的结构化指纹细节特征匹配算法.pdf

内容摘要郑州大学硕士学位论文 内容摘要 生物特征识别是一种利用个体生理特征来对个体进行身份鉴定的技术，指纹 由于其唯一性和终生不变性特征而成为理想的个体身份鉴定依据。近年来，随着 计算机与信息技术的发展，指纹识别作为生物特征识别领域中一门成熟的应用技 术逐渐被广泛用于个体身份验证和鉴定。因此，对指纹识别的研究不仅具有重要 的学术价值，而且具有广阔的应用前景。 本文分别介绍了自动指纹识别系统中的图像增强技术和特征提取方法，并对 指纹匹配过程进行了综述和重点讨论。现有的指纹匹配算法多种多样，其中基于 细节点模式的匹配方法历史最为悠久，其性能上也占有相对优势本文详细介绍 了一类最具代表性的细节点模式匹配算法基于细节特征串距离的匹配算法。 由于该类算法在提取基准点时需要对所有细节点对进行试探计算，因此导致了相 对较大的计算代价。针对该类算法的这种不足，又由于结构化的方法可以实现较 高的匹配精度，本文提出只在指纹的局部区域提取基准点，并在提取基准点时引 入结构化的方法。基于上述考虑，本文提出基于基准点的结构化细节特征匹配算 法。首先提取指纹图像的奇异点( 中心点和三角点) ，然后在指纹图像的中心区域 选择若干细节特征点，并为这些细节特征点分别构造局部结构，最后根据这些局 部结构的匹配结果实现基准点的精确定位。另外为了对部分非真匹配的情况做出 快速处理，本文引入了一个新的细节点描述属性。在实际匹配时，本文算法首先 对这一新引入属性进行比较，然后在此基础上利用界限盒的方法实现指纹的最终 匹配。 为了测试提出算法的匹配性能，本文在f v c 2 0 0 0 提供的四个公开指纹库上根 据其测试标准进行了实验，并将实验结果与基于串距离的匹配算法进行比较，实 验结果显示提出算法的平均注册时间和平均匹配时间均低于基于串距离的匹配 算法，匹配精度总体上优于原算法。 关键字：指纹匹配，细节特征，奇异点，局部结构 郑州大学硕士学位论文 a b s t r a c t b i o m e t r i c si d e n t i f i c a t i o ni sak i n do fi n d i v i d u a li d e n t i f i c a t i o nt e c h n o l o g yu s i n gt h e i n d i v i d u a lp h y s i o l o g i c a lc h a r a c t e r i s t i c s f i n g e r p r i n t sa r et h ei d e a lb a s i sf o ri n d i v i d u a l i d e n t i f i c a t i o no w n i n gt ot h e i ru n i q u e n e s sa n di m m u t a b i l i t y w i t ht h ed e v e l o p m e n to f c o m p u t e ra n di n f o r m a t i o nt e c h n o l o g y i nr e c e n ty e a r s , a sam a t u r ea p p l i c a t i o n t e c h n i q u ei nt h ef i e l do fb i o m e t r i c si d e n t i f i c a t i o n , f i n g e r p r i n ti d e n t i f i c a t i o nh a sb e e n w i d e l yu s e di ni n d i v i d u a li d e n t i t yv e r i f i c a t i o na n da u t h e n t i c a t i o n t h e r e f o r e ，r e s e a r c h o nf i n g e r p r i n ti d e n t i f i c a t i o nh a sn o to n l yt h ei m p o r t a n ta c a d e m i cv a l u e ，b u ta l s oh a sa b r o a da p p l i c a t i o np r o s p e c t t h ew o r kr e p o r t e di nt h i st h e s i si n c l u d e st h et e c h n o l o g i e so ff i n g e r p r i n ti m a g e s e n h a n c e m e n ta n df e a t u r ee x t r a c t i o n , a n dt h ee m p h a s i so ft h et h e s i sf o c u s e so nt h es t e p o ff i n g e r p r i n tm a t c h i n g t h e r ee x i s tm a n yf 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 sa tp r e s e n t t h em i n u t i a e - b a s e dm a t c h i n ga l g o r i t h m sh a v et h el o n g e s th i s t o r y , a n dt h e r e f o r et h e p e r f o r m a n c eo ft h e ma l s oh a ss o m ec o m p a r a t i v ea d v a n t a g e ak i n do ft h em o s t r e p r e s e n t a t i v em i n u t i a ep a t t e r nm a t c h i n ga l g o r i t h m - t h em i n u t i a ef e a t u r es t r i n g d i s t a n c em a t c h i n ga l g o f i t h mi si n t r o d u c e di nt h i st h e s i s i nt h i sk i n do fa l g o r i t h m s ，i t i sn e c e s s a r yt ot e s ta l lt h ep o s s i b l em i n u t i a ep a i r si no r d e rt oe x t r a c tt h er e f e r e n c e p o i n t s ，w h i c hl e a d sab i gc o m p u t a t i o n a lc o s t c o n s i d e r i n gt h es h o r t c o m i n ga n dt h e h i g hm a t c h i n gp r e c i s i o no fs t r u c t u r e dm e t h o d s ，w ec a l le x t r a c tt h er e f e r e n c ep o i m o n l yi nt h el o c a lr e g i o no ff i n g e r p r i n ti m a g e s ，a n dt h es t r u c t u r e dm e t h o d sc a na l s ob e i n t r o d u c e di n t ot h es t a g eo f e x t r a c t i n gr e f e r e n c ep o i m b a s e do nt h e a b o v e c o n s i d e r a t i o n , t h er e f e r e n c ep o i n t - b a s e ds t n j c t u r e df i n g e r p r i n tm i n u t i a ef e a t u r e m a t c h i n ga l g o r i t h mi sp r o p o s e di nt h i st h e s i s s i n g u l a rp o i n t s ( c o r ea n dd e l t a ) a r e e x t r a c t e df i r s t l yi nt h ea l g o r i t h m , a n dt h e nw eb u i l dal o c a ls t r u c t u r ef o re a c hm i n u t i a c h o s e na r o u n dt h ef i n g e r p r i n tc o r e a tl a s t , t h er e f e r e n c ep o i n tc a nb ee x t r a c t e d p r e c i s e l yb ym a t c h i n gt h e s el o c a ls t r u c t u r e s i na d d i t i o n , an o v e ld e s c r i p t i v ea t t r i b u t e o fm i n u t i a ei sa l s oi n t r o d u c e di n t ot h em a t c h i n gs t e p i nt h em a t c h i n gs t a g e ，t h e 郑州大学硕士学位论文 m i n u t i a ep a i r st h a ta t en o tm a t c h e do b v i o u s l yc a nb er e c o g n i z e dr a p i d l yt h r o u g h c o m p a r i n gt h en e w a t t r i b u t eo ft h e m , a n dt h e nt h ef i n a ld e c i s i o ni sm a d eb a s e do l lt h e m e t h o do f b o u n d a r yb o x i no r d e rt ot e s tt h ep e r f o r m a n c eo ft h ep r o p o s e da l g o r i t h m ，e x p e r i m e n t sa r cd o n eo n t h ef o u rd a t a b a s e so ff v c 2 0 0 0u n d e rt h es t a n d a r do ft h e m c o m p a r i s o n so ft h e r e s u l t so ft h ep r o p o s e da l g o r i t h ma n dam i n u t i a ef e a t u r es t r i n gd i s t a n c em a t c h i n g a l g o r i t h ma r ca l s og i v e ni nt h et h e s i s e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a tt h e a v e r a g em a t c h t i m e sa n dt h ea v e r a g ee n r o l lt i m e so fo i l l a l g o r i t h mo nd b i d b 4a r e l e s st h a nt h eo t h e ro n e ，a n dt h em a t c h i n gp r e c i s i o ni sa l s ob a s i c a l l yb e t t e rt h a nt h e o t h e ro n e k e y w o r d s ：f i n g e r p r i n tm a t c h i n g ；m i n u t i a ef e a t u r e ；s i n g u l a rp o i n t ；l o c a ls t r u c t u r e 第一章绪论郑州大学硕士学位论文 第一章绪论 身份识别与验证是每个人都不可回避的问题，传统的身份识别与验证方法一 般是基于标识物品( 如身份证等) 或标识符号( 如帐户密码等) 来进行的。由于 标识物品和标识符号容易丢失或被人窃取，因此近些年来生物特征识别技术得到 了广泛的研究和发展。生物特征识别技术是一门利用个体生理特征来完成身份签 定的技术，与传统的身份识别验证方法相比，生物特征识别技术是典型的“只认 人不认物”的身份鉴定方法，它解决了传统身份识别方法中因标识物品丢失或标 识符号被窃取而带来的一系列问题；同时它还具有识别依据随身携带的特点，避 免了随身携带各种证件或牢记各种口令符号的烦恼。 指纹识别是生物特征识别技术领域中研究最为深入、应用最为广泛且发展最 为成熟的技术之一。长期以来，指纹识别技术主要应用于刑事侦察和司法领域， 因此不被大多数人了解。近年来计算机信息技术和指纹采集传感技术的飞速发 展，为指纹识别技术开拓了更为广阔的应用领域，各种更为广泛的应用也逐渐成 为可能。 1 1 指纹识别的历史 人们应用指纹识别进行身份签定有着悠久的历史。历史资料表明，早在公元 前人类就已经开始了对指纹的应用，当时我国的一些文书合约上就印有手指的指 印；在出土西安据今六千多年的陶器上已经发现了指纹的痕迹；到了宋代，指纹 则被直接用作刑事诉讼的证据。现代指纹技术开始于十六世纪。1 8 8 0 年，苏格 兰人福尔茨( h e n r yf a u l d ) 在( n a t u r e ) ) 上发表论文论证了指纹的唯一性和永久 不变性【1 l 【2 】，从此为指纹识别作为一种有效的个体身份签定方法提供了理论基础。 1 8 9 2 年，英国的f r a n c i sg a l t o n 在( f i n g e r p r i n t 一书中首次详细介绍了用于指 纹分类的细节特征，并确立了一整套指纹识别方法。1 8 8 9 年，亨利( e r h e n r y ) 提出基于细节特征( m i n u t i a b a s e d ) 的指纹识别理论，从而奠定了现代指纹学的 基础，时至今日，基于细节特征的指纹识别方法仍被广泛采用。 指纹识别在以往都是采用人工的识别方法，这种基于人工的识别过程需要经 第一章绪论郑州大学硕士学位论文 过专业人士或经验丰富的指纹专家凭借经验来完成。由于人眼的视觉误差以及受 各种主观因素的影响，这种人工签定结果的精确性很难得到保证；此外，人工鉴 定的方法不仅效率低下，而且指纹的搜索规模也十分有限，远不能满足现代社会 对个体身份签定的大规模需求。到了2 0 世纪中期，随着科学技术尤其是信息技 术的不断发展，计算机技术开始应用到指纹识别领域，为自动指纹识别技术提供 了可能的实现方法和解决途径。到了2 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 ) 研制成功并投入使 用，从此自动指纹识别技术开始应用到实际中来。 近年来，尤其是进入二十一世纪之后，随着各种计算机系统和指纹采集设备 价格的降低，以及计算机图像处理和模式识别理论的不断发展完善成熟，自动指 纹识别技术也逐渐开始应用于民用场合。 1 2 指纹识别的优势 生物特征识别是一门应用人的生理特征来实现个体身份签定的科学，由于其 识别依据来源于个体自身，与传统基于标识物或标识符号( 身份证、帐号、密码、 门禁卡等) 实现身份鉴定的方法相比，识别依据不会丢失或被窃取，因此截止目 前，生物特征识别一种最为方便和安全的个体身份鉴定方法。 理论上来说，个体的任何生理特征( 人脸、虹膜、掌形以及d n a 等) 或行 为特征( 笔迹、语音和步态等) 都可以作为身份鉴定的依据。在众多的生物特征 识别方法中，指纹识别是目前研究最为深入、应用最为广泛、发展最为成熟的技 术。与其他生物特征识别方法相比，基于指纹的生物特征识别具有不可取代的优 势。基于唯一性和稳定性两方面的考虑，基于人脸、声音、签名以及掌形的生物 特征识别方法分别存在以下问题： 人脸和语音很容易受到外界环境因素和个体自身健康状况的影响。在唯一性 方面，孪生兄弟姐妹的面部和声音均具有很大的相似性，很难区分；人脸在人一 生中的不同时期也会有一些变化( 胖瘦、伤痕、胡须等) 。人的声音会受到个体 健康状况、语速、语气等的影响，且容易被伪造，这些因素都会对个体识别的准 确度带来影响。基于签名的个体识别方法同样面临着和语音识别一样容易被伪造 的问题，且个体签名的稳定性也不是很明显，随着书写熟练程度的增加会有所不 2 苎二皇篁丝 塑丛奎兰堡主兰竺丝苎 同，此外个体自身的健康状况也会影响到签名的稳定性。基于掌形的识别方法主 要面临着相似性难以分辨的难题，并且与指纹、虹膜相比，人的手掌上包含的数 据信息明显相对较少 与上面几种识别方法不同，基于视网膜、虹膜以及d n a 的生物特征识别方 法都能够取得很好的识别效果，然而它们却面临着个体配合程度和识别成本的难 题。基于视网膜和虹膜的识别技术是目前较为理想的识别技术，且很难进行伪操 作；然而在利用这两种技术对个体进行识别时，需要个体较好的配合，而且它们 的识别成本较高，因此大规模大范围的应用受到了限制。人类细胞的细胞核中 d n a 记载着每个人特有的遗传基因，随着现代科学技术的发展，可以对人类个 体的d n a 进行精确的分析检测。由于个体d n a 的唯一性和不变性，因此基于 个体d n a 可以实现对个体身份的精确鉴定。目前为止，d n a 是最精确的生物特 征识别方法。与基于视网膜和虹膜的识别方法一样，基于d n a 的生物特征识别 方法同样面临着个体的配合程度和识别成本的问题。 相比之下，虽然手指指纹只是人体皮肤的- - , j , 部分，却包含着大量的特征信 息。指纹识别主要是根据人体指纹表面凸凹不平的的指纹纹路、纹线细节特征等 信息实现身份签定的对于不同的手指，其指纹图像的中心点、三角点、端点、 分叉点、断点等特征信息的分布各不相同，也就是说，对于一枚固定的手指其指 纹图像是唯一的。在稳定性方面，一个人在出生时其手指指纹就基本定型，随着 年龄的增长不会改变；人的手指即使被划破，只要不损害到真皮组织，伤愈之后 仍会恢复原状。除了唯一性和稳定性方面的优势外，每个人均拥有各不相同的十 个手指，因此在个体一个或几个手指伤残的情况下，我们仍可有其他选择；我们 也可以应用个体的多个手指组成多重的鉴定方案，以提高识别的可靠性。除了指 纹的自身特点之外，指纹识别方法在个体配合度和识别成本方面还具有许多优 势。指纹采集对于个体没有身体伤害，采集速度快，采集设备使用简单方便，容 易被个体所接受；指纹采集设备体积较小，价格低廉，这些因素在一定程度上也 推动了指纹识别技术的快速发展。 1 3 指纹识别的研究内容 1 8 8 9 年，亨利( e r h e n r y ) 在总结前人研究成果的基础上，提 3 第一章绪论郑州大学硕士学位论文 出了基于指纹细节特征( m i n u t i a b a s e d ) 的识别理论，完善确立一整套 人工指纹识别的方法，从而奠定了现代指纹学的基础。直到1 0 0 多年后 的今天，指纹识别的过程已经由人工操作发展到计算机自动识别，基于 指纹细节特征的识别方法仍被广泛采用。鉴于指纹识别在身份鉴定方面 的优势以及现代社会对个体身份鉴定的需求，自动指纹识别系统在近些 年得到了日益广泛的研究。图1 1 列出了自动指纹识别系统的一般工作 过程。 1 ：指纹图像2 ：增强后的图像3 ：特征点4 ：输入特征点5 ：特征点模板6 ：匹配结果 图1 1 自动指纹识别系统工作流程 该系统由两部分组成，包括两大功能。一是建立指纹特征模板数据库( 图 1 1 中虚线以上部分所示) ，这一过程称为指纹采集；二是随机识别某一指纹( 图 1 1 中虚线以下部分所示) ，这一过程称为指纹匹配。在采集指纹时，采集到的指 纹图像经过增强后，提取出其中的特征点并存入数据库；在指纹匹配时，对要匹 配的指纹图像进行增强处理，并根据提取的特征点在指纹特征模板数据库中进行 匹配检索，最后把匹配结果返回给用户。 在实际的指纹识别过程中，由于各种因素的影响，输入的指纹图像会不同程 度的受到噪声干扰，一般在进行特征提取之前需要对采集到的指纹图像做增强处 理。指纹增强的目的就是要去除指纹图像中的叉连以及断点现象，把指纹图像变 成一幅清晰的点线图，以便精确提取指纹特征。指纹图像增强是指纹识别的第一 步，它的好坏直接影响着特征提取以及指纹识别的效果。特征提取是指纹识别系 统中关键的一步，特征提取的精度如何则直接影响到指纹识别系统的性能。 随着自动指纹识别系统的应用范围日益广泛，指纹数据库的规模也日趋海 量。在大规模的应用中，为了实现对海量指纹数据库的快速检索，以减少数据库 4 第一章绪论郑州大学硕士学位论文 的搜索空间，进而减少匹配时间，指纹分类的问题在近些年也得到了研究人员的 广泛关注。 指纹图像增强、特征提取以及指纹分类，都是为了实现精确高效的指纹匹配 做准备的。指纹匹配是指通过对两幅指纹图像的特征信息集合问的相似性进行比 较，最终得出两幅指纹图像是否是来自同一手指的结论的过程。显然，指纹匹配 过程得出的结论正是自动指纹识别系统最终的输出结果，正因为此，指纹匹配一 直是自动指纹识别系统中的研究热点。 综上所述，目前对自动指纹识别系统的研究主要包括图像增强、特 征提取、指纹分类和指纹匹配等几个方面 1 4 本文的内容和组织结构 本文将介绍指纹识别技术在图像增强和特征提取等几个方面的最新进展情 况；重点介绍一类基于点模式的指纹匹配方法并分析其优缺点。该类算法在指纹 匹配时采用一种弹性界限盒，从而使算法能够适应指纹图像的非线性形变。在对 这类点模式匹配算法分析的基础上，本文提出基于基准点的结构化细节特征匹配 算法。该算法将基于指纹图像的局部细节点结构实现基准点的精确定位，并在指 纹匹配的过程中引入和应用细节点到基准点之间的纹线切割数目这一属性，通过 对细节点该属性的比较可以快速检索出明显不匹配的细节点对，进而提高指纹的 匹配效率。 本文的组织结构如下： 第一章是本文的绪论部分，分别介绍指纹识别技术的发展历史、指纹识别技 术的优势，以及指纹识别技术在现阶段的主要研究内容。 第二章我们将详细介绍指纹图像增强技术，重点介绍指纹方向场的估计、指 纹图像的平滑滤波操作以及指纹图像的二值化和细化操作。 在本文的第三章，我们将分别介绍指纹图像的表示方法、指纹特征提取，并 对现有的指纹匹配算法进行介绍。 第四章将介绍一类基于点模式的指纹匹配方法( 基于指纹细节特征串距离的 匹配算法) ，并分析该类算法的不足之处，在此基础上我们将提出基于基准点的 结构化指纹细节特征匹配算法。 5 第一章绪论郑州大学硕士学位论文 第五章是本文的实验部分，我们将就第四章提出的基于基准点的结构化指纹 细节特征匹配算法在f v c 2 0 0 0 的四个公开数据库进行实验，并将实验结果与基 于细节特征串距离的指纹匹配算法在相同数据库上的实验结果进行比较分析。 最后总结全文。 6 第二章指纹图像增强技术郑州大学硕士学位论文 第二章指纹图像增强技术 在指纹识别的过程中，由于受各种因素的干扰，采集到的指纹图像中会存在 大量的噪声，指纹图像增强就是要去除图像中的噪声，在保持指纹纹理结构不变 的前提下把指纹图像加工成一幅清晰的点线图，以便于正确提取细节特征。指纹 图像增强是指纹识别的第一步，图像增强的质量如何直接影响着系统的识别效 果。指纹图像增强包括指纹图像归一化、方向场的估计、指纹图像平滑滤波，指 纹图像的二值化以及细化等几个主要步骤。 2 1 指纹图像归一化 指纹图像归一化是指在对指纹图像进行增强之前，为使输入的指纹图像具有 相同的均值和方差而对指纹图像进行的预处理操作。下面简单介绍指纹图像的归 一化方法【3 】。 设w 和h 分别表示指纹图像的宽和高，g ( i ，j ) 表示原始灰度指纹图像在点( i ，j ) 处的灰度值，m 和v a r 分别表示原始图像的灰度均值和方差，m 。和、，a 表示 灰度均值和方差的期望值( 即归一化后的灰度均值和方差) 。则m 和v a r 分别 计算如下： m - 击墓篝州 v a r 一而1 盏w - i wx 以f = 6 ( i ，) 一m ) 2 归一化后的指纹图像在点( i ，j ) 处灰度值计算如下； g ( i ，) - 肼。+ v a ro ( g ( i , j ) - m ) 2 ：删卜m 肘。一v a ro ( g ( i , ) - m ) 2 ：幽p 经过以上计算即完成了指纹图像的归一化操作。归一化操作的目的是为了降 低不同指纹图像之间的灰度差异，为后面的处理过程做准备，它并不改变指纹图 像的纹理结构和细节特征信息。 7 川 第二章指纹图像增强技术郑州大学硕士学位论文 2 2 指纹方向场的估计 指纹方向场是一种用指纹像素点的脊线方向表示指纹纹线的方法，它可以粗 略地表示指纹的纹线结构及基本形状。由于指纹纹线走势变化缓慢，因此方向场 也不太可能发生走向突变的情况，基于指纹方向场的这一特点，我们也可以对低 质量指纹图像的方向场进行平滑处理，从而对于低质量的指纹图像仍可以获取效 果相对较好的方向场。方向场的质量如何是衡量指纹图像好坏的重要尺度之一。 现有的方向场估计方法有很多 4 1 ，其中比较常用的方法有八方向掩膜法和最小均 值平方估计算法。下面分别介绍。 2 2 1 八方向掩膜法 八方向掩膜法首先为指纹脊线设置若干个既定方向。对于指纹图像中的任意 像素点，其方向值的确定都是在以该像素为中心的n x n 临域窗口中进行的，实 践中n 值取为9 。对于像素点p ( i ，i ) ，其9 x 9 的临域窗口如图2 1 所示。八方向 掩膜计算方向场的具体过程如下 p 7 4p 6 4p p “p ，毒 p p 7 ，蹈p 5 3现3 p 2 4 p s 3p 2 3 p l l p 1 2 p ijp 1 3p 1 4 p 2 2p 配 p 2 1现2p 4 2如2 p 6 2p 7 2p s l p 3 ll如lp lp n 首先计算像素点p gi ) 沿各个方向的灰度变化： s 。暑4i 纵) 一m 。i d1 1 ，2 ，3 ，8 ，以，加专善九( 。j t ) 其中，缸仇吐j 表示像素点p d k 的灰度值，p 血是d 方向上的第k 个点。令d 8 第二章指纹图像增强技术郑州大学硕士学位论文 表示与d 垂直的方向，即d = ( d + 4 ) m o d8 ，则点p i ) 的方向应该取为s d 取值最 小同时s d ，取值最大的方向，即不仅考虑纹线切线方向灰度变化最小，同时要保 证其垂直方向灰度变化最大对于上述d = 1 8 ，求出所有的( s d s d ) ，并进一步 求出最小值s = m i n ( s d s d , ) ，p ( i ，j ) 的方向即为s 取最小值时所对应的方向。 通过上述步骤即求出了指纹图像的方向场。这样求出的方向场还存在一定的 噪音，需要对其进行平滑。若某一点的方向与它周围八临域的方向都不相同，则 将该点视为噪音点，把周围八临域中出现频率最高的方向设为该点的方向。通过 这种改进，就得到了平滑后的方向场。 2 2 2 最小均值平方估计( al e a s tm e a ns q u a r ee s t i m a t i o n ) 下面介绍应用最小均值平方估计计算指纹方向场的方法 s l 。主要步骤如下： ( 1 ) 把输入的指纹图像分割成w x w 大小的块( 实践中w 一般取1 6 ) 。 ( 2 ) 对于每个像素a ，d ，分别计算梯度其反倡刀和西仨6 1 ： d y ( i ，) - 1 “- 1 - 1 “- 一1 j ( “+ 1 ，v + 1 ) go + 球，歹4 - v ) y ( “+ 1 ，v + 1 ) o ( i + “，+ v ) 上式中最和昌分别为s o b e l 算子，g 似圳表示图像中像素点伍圳的灰度值。 ( 3 ) 根据下面的公式，对以像素隔d 为中心的每一块的方向进行估算【7 l ： 吲“) - 。置，：，- j 芝- w 2 1 2 引m ( v ) 州) - 。置，：，：；。；( 川地v ) ) 叩卜4 ( 揣) “， 【詈 i f ( l d 0 ) 其中口似纠是以像素信刀为中心的块的局部脊线方向的最小平方估计。数学 意义上它表示垂直于w x w 块的傅立叶频率的主方向。 ( 4 ) 由于噪声的影响，上面计算的脊线方向p “力可能不完全正确。由于指纹 脊线的走向不会发生突变，因此可用一个低通滤波器平滑脊线方向。首先将方向 9 s 1 s l 。， 第二章指纹图像增强技术 郑州大学硕士学位论文 场转化到一个连续向量场中，定义向量场的z 分量和) ，分量分别为九和以，计 算如下： f 九( f ，) - c o s ( 2 0 ( f ，) ) l 妒y ( f ，) - s i n ( 2 0 ( f ，) ) 用低通滤波器对氏和以分别进行滤波，得到m ，和垂y ： o ，( f ，j ) i 其中，是一个二维低通滤波器，讹砂是滤波器各点的权值，一是滤波器 窗口的宽度，默认大小为5 。 ( 5 ) 计算滤波后像素点( d 的方向场： ，咖( 黜) 这样就得到了指纹图像的方向场。把指纹的点方向场分割为1 6 1 6 大小的 块，把每一块中点方向出现频率最高的方向定为该块的方向，这样就可以计算出 指纹图像的块方向图。 2 3 指纹灰度图像的平滑滤波 由于受噪声和指纹压力等因素的影响，采集到的指纹图像中会存在各种指纹 纹理被破坏的情况，其中出现频率最多的是断点和叉连现象。断点就是一条完整 的指纹纹线上出现的缺口现象，叉连是由于两条l | 笛近的指纹纹线由于噪声因素的 干扰而连接在一起了，其他噪声一般都是由这两种情况组合而成。由于这些因素 会导致伪特征点的生成，因此在指纹图像的增强阶段必须给予清除。常用的指纹 图像增强算法包括基于g a b o r 滤波的方法【5 】、基于傅里叶滤波变换的指纹图像增 强算法嗍、k n o w l e d g e b a s e d 的指纹图像增强算法1 9 】、方向场滤波器滤波方法【1 0 l 以及多尺度的指纹图像滤波方法1 1 1 1 等。下面具体介绍方向场滤波器的滤波方法。 1 0 吼 m 一 一 埘 埘 一 一 o a 九 以 ” ” ，2厂2 小互警m 互小 第二章指纹图像增强技术郑州大学硕士学位论文 2 3 1 方向场滤波器的设计 对一般数字图像进行处理时只需一个滤波器，而指纹图像的方向场滤波器是 由一组不同方向的多个滤波器模板组成的。滤波时，根据指纹图像某一小块的方 向特征，从该组滤波器模板中选择一个对应方向的滤波模板来进行处理。下面详 细介绍水平方向滤波器的设计方法。 一个基本的滤波器模板应具备两种功能：连接指纹纹线中的断点和去除图像 中的叉连现象。滤波模板的大小一般为n x l l ，其中n 由指纹纹线间的平均距离确 定，实验中一般取为7 ( 指纹纹线间的平均距离一般为7 个像素) 。水平方向滤 波器的模板系数如图2 2 所示。 - - d 1 3 - - 2 d 3 - d - d d - - 2 d 3 - - d 1 3 c 32 c 3 ccc 2 c 1 3 c f 3 b 1 32 b 3 bbb 2 , 1 3b 1 3 a 32 a 1 34a42 a 1 3a 1 3 b 32 b 3 bbb 2 2 , 3 b 1 3 c | 3k | 3 ccc 2 c 1 3 c 1 3 - d 3 - - 2 d 3一d - d - - d - 2 d 3 - - d 1 3 图2 2 水平方向的滤波模板系数 上面滤波模板各系数之间大小关系为a b c 0 ，d o 且a + 2 b + 2 e = 2 d 。 由图2 2 中可以看出，模板系数由中间向四周快速减少，这样做的目的是为了保 证曲率较大的纹线结构不被破坏，为后面特征提取打下良好基础。 滤波时，图像中任一像素点的灰度值都由其7 x 7 邻域窗口中包含自身在内的 4 9 个像素点的灰度值共同决定。若图像中出现断点，即该点的灰度值远小于周 围像素点，那么经过滤波后其灰度值就和周围点的灰度值非常接近；对于图像中 的叉连点，由于其连接了两条相邻的指纹纹线，因此该点同行上临近点的灰度值 较小，而上下行的灰度值都非常大，经过滤波处理后叉连点的灰度值会大大降低， 因此滤波器起到了连接断点和去除叉连的作用。 经过上面的过程可得到水平方向的滤波器模板系数，其他方向的滤波器可通 过对水平方向的滤波器模板旋转一定的角度分别得到。这样就完成了所有方向滤 波器模板的设计。 1 1 第二章指纹图像增强技术郑州大学硕士学位论文 2 3 2 滤波 在用方向场滤波器进行滤波时，根据指纹方向图中某一块的块方向或每一个 像素的点方向，选择对应的滤波器分别进行处理。例如对于像素点伍y ) ，根据 其方向值选择对应的滤波器模板进行处理，计算如下： 33 ，( 圳) - ，他+ 州+ 一) w ( m ，n ) 其中，f 伍+ m ，y + n ) 表示( x ，y ) 点的邻域窗口中个像素点的灰度值，w ( m ，n ) 为对应滤波器的模板系数，f ( x ，y ) 为经过滤波后( x ，y ) 点的灰度值。 指纹图像经过滤波之后，其中的断点和叉连现象消除了，指纹图像得到增强。 ； ! f 用方向场滤波器进行指纹滤波，由于考虑了指纹图像中的纹理方向，因此取得 了较好的滤波效果。 2 4 指纹图像的二值化 二值化的目的是把灰度图像转为0 1 取值的二值图像。对一幅指纹图像进行 二值化，必须首先选取阈值，把高于阙值的像素点灰度值转换为1 ，否则转换为0 。 我们这里采用局部阈值自适应算法【1 2 1 实现指纹图像的二值化。该算法充分利用 指纹图像脊线和谷线宽度大致相同的特点，e p - 值后黑白像素的个数也应大致相 等。该算法首先把指纹图分成n n ( n 由纹线的平均宽度决定) 的小块，然后在所有 小块内计算灰度均值： ，。击莓；似，y ) 其中，f ( x ，y ) 为某一小块内任一像素点( x ，y ) 的灰度值。在该小块内若f ( x ，y ) 大 于该小块内的灰度均值，则令自( x ，y ) = 1 ；否则令f 伍，y ) = o 。这样即完成了指纹图像 的二值化过程。 2 5 指纹图像的细化 细化就是使指纹图像的纹线变为宽度为单个像素的点线圈。指纹图像细化算 法有很多，如骨架算法、逐层推进算法、线跟踪算法等。细化可以去除指纹图像 第二章指纹图像增强技术 郑州大学硕士学位论文 中的大量冗余信息，同时尽可能地保留指纹纹线的拓扑结构，为以后的特征提取 打下良好基础。下面介绍逐层推进的细化算法【1 0 j 。该算法把一次迭代分做两次 扫描，由周围向中间逐层推进，最终保留指纹纹线靠近中轴的那条点线。 p 4 p 3p 2 p 5p p 1 p 6hp 8 图2 33 3 窗口及其中的目标像素 令n 蠢为3 3 窗口内目标像素的个数，n - 一荟只其中，p i 定义如图2 3 所示，其取值为0 或1 。n c 为p 8 邻域中的连接成分数，即序列p l p 2 p 3 p 4 p 5 p 6 p 7 p 8 p 1 中0 至1 的变化次数。 逐层推进细化过程重复执行如下两次扫描： 1 从左到右，从上到下顺序扫描图像，对同时满足条件( 条件在下面定义) 的像素( 当前像素和其3 x 3 邻域) ，如p 1 p 3 p 7 = 0 且p l p 5 p 7 = 0 ，则在该中心像素 上作标记； 2 从左到右，从上到下顺序扫描图像，对同时满足条件的像素，如p l p 3 p 5 = 0 且p 3 p s p t = 0 ，则在该中心像素上作标记。 需要满足的条件如下： 2 剞b e 6 ； ，排除p 为端点和内部像素点的情况 若已标记p i 视为1 时，有n c = 1 ； 保证删除当前像素不改变原图的连通性 p 的灰度值是1 ； 保证p 为前景像素 当p 3 或p 5 已标记时，若视p 3 和p 5 为0 ，仍有n c = 1 ； ，保证宽度为两个像素的纹线只删除其中的一个像素，以免纹线断裂 扫描完整幅指纹图像后，删除作了标记的像素，重复上述两步骤，直到得到 单像素宽度的指纹线条为止。 经过上述细化可以得到单像素宽度且八连通的指纹图像。由于细化过程会引 第二章指纹图像增强技术郑州大学硕士学位论文 入一些噪音，细化指纹纹线上会存在一些小的分叉，可通过以下方法删除小的分 叉：沿纹线前进方向，在其垂直方向上若存在长度较短的灰度为1 的像素，则将 其删除。这样就得到了清晰的指纹点线图。 1 4 第三章特征提取和指纹匹配郑州大学硕士学位论文 第三章特征提取和指纹匹配 前一章介绍了指纹图像增强技术，将一幅含噪音较多的原始指纹灰度图像最 终处理成一幅清晰的二值化点线图。本章我们将在指纹点线图上提取细节特征， 并根据提取的指纹细节特征来记录指纹图像。指纹匹配过程大多是基于指纹细节 特征完成的，本章最后，我们将对现有的指纹匹配算法进行介绍。 3 1 指纹特征的表示 由某一特定指纹图像提取的各类特征点描述的集合，称为指纹的特征模板。 指纹的特征提取过程是不可逆的，指纹特征模板是一组与原始指纹图像密切关联 的特征点集合。然而，指纹图像中都存在什么样的指纹特征呢? 我们用哪些特征 来表示和记录指纹的特征模板呢? 图3 1 指纹图像及其细节特征 图3 1 显示了一幅典型的指纹图像及其细节特征，包括纹线的端点、分支点、 环形区、桥点、岛点、交叉点、中心点以及三角点等各种指纹细节特征，其中中 心点和三角点还称为指纹图像的奇异点。在众多的指纹细节特征中，纹线端点和 分支点是两种最基本的特征，而其他的细节特征都可以看作是由纹线端点和分支 第三章特征提取和指纹匹配郑州大学硕士学位论文 点这两种基本特征组合而成的，因此在实际的指纹特征提取时，我们通常取指纹 纹线的端点和分支点作为指纹的细节特征。 一枚指纹图像中通常包含有近百个细节特征点，在指纹识别技术中，一个特 定的特征点可用多种参数来描述： 特征点类型表示特征点的不同种类，如纹线端点、纹线分支点等。 特征点坐枥o - 通过坐标系中的坐标值来表示，其值可以是绝对的，也可以 是相对于奇异点或其他特征点的相对值。 特征点方向表示特征点所处的纹线在特征点位置的纹路走向。 特征点曲率表示特征点所处的纹线在特征点位置的曲率大小。 除了上述描述属性外，特征点的邻域纹线密度以及特征点之间的纹线数量等 属性也可以用来描述指纹特征。在实际的指纹识别中，我们经常用特征点的类型、 特征点的坐标、特征点的方向以及特征点所处的纹线信息等属性一起描述和记录 指纹细节特征。 3 2 指纹特征提取 特征提取是指纹识别中关键的一步，特征提取的精度如何将会影响到指纹识 别的效果。人们在这方面进行了很多研究，众多研究人员提出了很多指纹图像的 细节提取算法【1 3 1 7 】。一般的特征提取算法首先对原始指纹图像进行滤波、增强、 二值化和细化，然后在细化指纹图像上提取纹线的端点和分支点。由于细化过程 存在畸变以及受噪音干扰，获取的端点和分支点并非都是真实细节点，因此需要 去除伪细节点。此外，也有人提出从二值图像上提取细节点的方法【堋，以及从 原始灰度图像上直接提取细节点的方法【1 9 1 嗍。除了纹线端点和分支点这些传统 细节点外，指纹纹线的弯曲程度也是描述指纹的重要信息，因此近年来，也有人 提出采用指纹纹线的弯曲信息作为指纹特征来对指纹图像进行描述【2 1 1 。我们这 里采用最常用的基于细化图像的方法邻域判定方法来提取指纹细节特征，并 用提取的细节特征构成指纹特征模扳。下面简单介绍。 在细化指纹图像中，用3 x 3 模板( 见图2 3 ) 来进行特征提取。首先分析纹线 端点和分支点的八邻域像素特征。如图3 2 所示，纹线端点周围八个像素只有一 个值为1 ，其余全为o ；分支点周围八个像素有三个像素值为1 ，其余为0 。根据这 1 6 第三章特征提取和指纹匹配郑州大学硕士学位论文 些特征可以检测特征点的存在，并正确判定特征点类型。方法如下： 同 尉0 p0 衄 皿 f f 用 吐0 刮1 0 8 ) p 为纹线端点b ) p 为纹线分支点 图3 2 特征点的八邻域像素特征 在细化的指纹图像上，对每一个点分别计算其交叉数c n ( 像素点周围八邻 域像素顺序从0 至1 或从1 至o 变化的次数的一半) ，其计算公式如下： c 妄磊陪只+ - l 其中p 8 + 1 = p 1 。计算出交叉数c k 之后，我们可以根据其值来检测细节点并判 定其类型。当c n = 1 时，细节特征点p 为指纹纹线端点，当c h = 3 时，说明点p 为纹线的分支点。 提取出特征点之后，再对提取的细节特征进行去伪操作，保留真实特征点。 去伪操作根据以下几条规则进行： 1 连接断线。根据纹线的连续性，当在同一指纹纹线上具有同一方向的两 个端点间的距离小于某一阈值时，则认为是伪特征点，将这两个端点相连接。 2 删除毛刺结构。若一个纹线分支上的端点到对应分支点的距离小于一给 定阈值，则认为是伪特征点，给予删除。 3 删除桥点、梯形等各种错误连接结构。 4 删除前景图像边界的特征点。由于图像边界的细节特征点往往是受边