（计算机应用技术专业论文）指纹匹配及纹线距离估计算法研究.pdf

山东大学硕士学位论文 摘要 指纹识别技术是一种利用人的指纹进行计算机自动识别的综合技术，属于生 物特征识别领域。应用指纹进行身份鉴别已有悠久的历史，很多国内外学者对指 纹识别技术作了深入细致的分析和研究，并提出不少卓有成效的算法，取得了丰 硕的成果。然而，指纹识别仍然存在一些未得到完全解决的技术难点。指纹识别 应用领域的不断扩大和应用要求的不断增加对于指纹匹配算法的可靠性和鲁棒性 提出了迫切的要求。此外，由于指纹图像质量的影响，纹线频率估计也是一个难 点。因此，本文针对指纹匹配和纹线频率估计进行了深入研究。 基于d t 网格的指纹匹配算法是一种基于点模式的指纹匹配算法。它引入d t 网格使得指纹模式中的所有细节点构成一个稳定的网状结构，然后利用局部结构 中相邻细节点之间的距离，连线方向以及相邻连线的夹角等信息进行匹配。经过 仔细分析发现，此算法对细节点方向的使用和相邻细节点连线起始点的定义存在 严重不足。当对应细节点方向分居在3 6 0 。两侧时，称之为细节点方向跨越3 6 0 。当对应细节点连线的起始点刚好相反时，称之为边方向跨越9 0 。针对算法 中的以上两个问题，本文提出了相应的改进措旌。此外，本文还提出了细节点方 向和线方向变化趋势一致性的概念。实验结果表明，识别性能有了一定程度的提 高。 纹线频率是指纹的一个本质属性，也是目前主流指纹增强方法一一基于加博 滤波器的指纹增强算法一一的一个重要参数。指纹增强能够在突出关键特征信息 的同时减弱噪声影响，在指纹识别中起着非常重要的作用。但是，绞线频率的本 质决定了它非常容易收到噪声的影响，因此，纹线频率的精确估计比较困难的。 为实现这一目标，本文尝试在频率域估计纹线距离，提出了两种基于频谱分析的纹 线距离估计算法，并在增强、提取细节点方面将性能做了对比。实验结果表明， 纹线距离估计的精度有所提高。但是，在质量较低指纹图像的识别过程中，识别 性能的提高仍然有赖于增强算法本身的提高。 关键词：指纹；指纹匹配；d t 网格；纹线距离 山东大学硕士学位论文 a b s t r a c t f i n g e r p r i n tr e c o g n i t i o nt e c h n o l o g y ，b e l o n g i n gt ob i o m e t r i cf e a t u r e s r e c o g n i t i o n ，i sa ni n t e g r a t e dt e c h n o l o g yt h a tu s ec o m p u t e rt or e c o g n i z e p e r s o n a lf i n g e r p r i n t f i n g e r p r i n t sa r eu s e df o rp e r s o n a li d e n t i f i c a t i o n l o n gb e f o r e ，m a n yr e s e a r c h e r sh a v ed o n em u c hw o r ko nf i n g e r p r i n ti d e n t i f i c a t i o n a n dp u tf o r w a r ds o m ee f f e c t i v ea l g o r i t h m s b u t ，t h e r ea l es o m ei n c o m p l e t er e s o l v e d p r o b l e m si nf i n g e r p r i n ti d e n f i f i c a f t o n w i t ht h ea p p l i e da l e ae x t e n d i n ga n dt h e r e q u i r e m e n t si n c r e a s i n g ，t h er e l i a b l ea n dr o b u s tf i n g e r p r i n tm a t c h i n ga l g o n t h m sa l e n e e d e d i na d d i t i o n ，b e c a u s eo ft h ei m p a c to ff i n g e r p r i n ti m a g eq u a l i t y , t h ef i n g e r p r i n t f r e q u e n c ye s t i m a t i n gi sad i f f i c u l t yt h e r e f o r e ，w er e s e a r c hf i n g e r p r i n tm a t c h i n ga n d f i n g e r p r i n tf r e q u e n c ye s t i m a t i n gd e 印l y t h ef i n g e r p r i n tm a t c ha l g o r i t h mb a s e do nd ti sak i n do fm i n u t i a e b a s e d a l g o r i t h m o nt h ep r i n c i p l eo f d e l a u n a y , t r i a n g u l a t i o nu s e sa s e to f m i n u t i a et of o r ma d tn e t i nat r i a n g l e ，l e n g t ho fe d g e sa n di n c l i n a t i o nb e t w e e ne d g e sa r ea l s ou s e di n m a t c h i n gp r o c e s s a 髓ra n a l y s i s w ef i n dt h a tt h e r ea r et w os e r i o u ss h o r t a g e si n m i n u t i a eo r i e n t a t i o na n d e d g e o r i e n t a t i o nw h e n3 6 0d e g r e ei sb e t w e e nt h e c o r r e s p o n d i n gm i n u t i a eo r i e n t a t i o n ，w en a m ei tm i n u t i a eo r i e n t a t i o ns p a n n i n g3 6 0 d e g r e e w h e nt h es t a r t i n gp o i n ta n de n d i n gp o i n to f t h ec o r r e s p o n d i n ge d g ea l er e v e r s e ， w en a n l ei te d g eo r i e n t a t i o ns p a n n i n g9 0d e g r e e a i m i n ga tt h et w op r o b l e m s ，w e p r o v i d ee f f e e f t v ei m p r o v e m e n tm e t h o d b e s i d e s ，w ei n t r o d u c et h ec o n c e p to ft h et r e n d c o n s i s t e n c yo fm i n u t i a eo r i e n t a t i o na n de d g eo r i e n t a t i o nc h a n g e e x p e r i m e n tr e s u l t s s h o wt h a tt h ei d e n t i f i c a t i o np e r f o r m a n c eh a sa ne x t e n ti m p r o v e m e n t f i n g e r p r i n tf r e q u e n c yi sa ne s s e n t i a la t t r i b u t eo ff i n g e r p r i n t ，a l s o i sa ni m p o r t a n tp a r a m e t e ro ft h ef i n g e r p r i n te n h a n c e m e n ta l g o r i t h mb a s e d o ng a b o rf i l t e rw h i c hi sn o wap o p u l a rf i n g e r p r i n te n h a n c e m e n tm e t h o d f i n g e r p r i n t e n h a n c e m e n th a sa n i m p o r t a n t f u n c t i o ni n f i n g e r p r i n t i d e n t i f i c a t i o n ，w h i c hc a ne m p h a s i z et h ek e yf e a t u r ei n f o r m a t i o na n di m p a i r i i 山东大学硕士学位论文 t h ei m p a c to fn o i s e s b u tt h ee s s e n c eo ff i n g e r p r i n tf r e q u e n c yd e t e r m i n e s t h a ti ti si n c i d e n tt ob ei m p a c t e db yn o i s e s ，t h e r e f o r e ，i ti sd i f f i c u l t t oe s t i m a t ef i n g e r p r i n tf r e q u e n c ya c c u r a t e l y t oa c h i e v et h i sg o a l ，w ea t t e m p t t oe s l i m a t er i d g ed i s t a n c ei nf r e q u e n c yd o m a i n ，p r o v i d et w or i d g ed i s t a n c ee s t i m a t i n g a l g o r i t h m sw h i c ha r eb o t hb a s e do i ls p e c t r u ma n a l y s i s ：锄dt h e ng i v et h ec o m p a r i s o n b e t w e e nt w oa l g o r i t h m si nt e r m so fe n h a n c e m e n ta n de x t r a c t i n gm i n u t i a ee x p e r i m e n t r e s u l t ss h o wt h a tt h er i d g ed i s t a n c ei sm o l ep r e c i s e h o w e v e r , i nt h ei d e n t i f i c a t i o n p r o c e s so fp o o rq u a l i t yf i n g e r p r i n t , t h ei d e n t i f i c a t i o np e r f o r m a n c er e l i e so nf i a e i m p r o v e m e n to f e n h a n c e m e n ta l g o r i t h m s k e y w o r d s ：f in g e r p r i n t ；f i n g e r p r i n tm a t c h i n g ：d tn e t ；r i d g ed is t a n c e f l l 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：暨圈捶日期：逻z ：址! 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：衄导师签名：桦日期：互驾出 山东大学硕士学位论文 1 1 指纹识别简介 1 1 1 发展历史 第1 章绪论 要说指纹，最终还是要追溯到古老的中国。据相关资料显示，我国古代最早 的指纹应用可追溯至秦朝。至唐朝，以“按指为书”为代表的指纹捺印已经在文 书、契约等民用场合被广泛采用。自宋朝起，指纹则开始被用做刑事诉讼的物证。 在欧洲，1 7 8 8 年，梅耶( j m a y e r ) 首次提出没有两个人的指纹会完全相同：1 8 8 9 年，亨利( e r h e n r y ) 在总结前人研究成果的基础上，提出了指纹细节特征识 别理论，奠定了现代指纹学的基础【1 】。 指纹识别技术从被发现时起，就被广泛地应用于契约等民用领域。由于人体 指纹具有终身稳定性和唯一性，很快就被用于刑事侦查，并被尊为“物证之首”。 但早期的指纹识别采用的方法是人工比对，效率低、速度慢，不能满足现代社会 的需要。2 0 世纪6 0 年代末，在美国开始有人提出用计算机图像处理和模式识别 方法进行指纹分析以代替人工比对，这就是自动指纹识别系统( 简称a f i s ) 。 因为成本及对运行环境的特殊要求，开始时其应用主要限于刑侦也叫警用领 域。随着计算机图像处理和模式识别理论以及大规模集成电路技术的不断发展与 成熟，指纹自动识别系统的体积不断缩小，其价格也不断降低，因而被应用到民 用领域。 由于人体指纹具有不变性和唯一性，所以指纹识别技术成为应用最广泛的识 别技术。指纹相比于其他几种生物特征，如视网膜、虹膜、掌形、人脸、语音、 签名等，还具有一些优势嘲：( 1 ) 使用指纹作为身份识别的手段已有很长的历史， 为人们所广泛接受。( 2 ) 便于获取指纹样本，易于开发识别系统，实用性强。目 前已有标准的指纹样本库，方便了识别系统的软件开发，另外，识别系统中完成 指纹采样功能的硬件部分也比较容易事项。( 3 ) 一个人的十指指纹都不相同，因 此可以方便地利用多个指纹构成多重口令，提高系统的安全性。同时，并不增加 山东大学硕士学位论文 系统设计的负担。( 4 ) 指纹识别中使用的模板并非最初的指纹图像，而是由指纹 图像中提取的关键特征，因此存储量较小。另外，对输入的指纹图像提取关键特 征后，可以大大减少网络传输的负担，便于实现异地确认，支持计算机的网络功 能。 从以上的分析可以看到，自动指纹识别技术相对其他技术不仅具有许多独到 的信息安全角度的优点，更重要的是还具有很高的实用性和可行性。指纹相对人 的其它生物特征具有个体差异大、实现识别所需的软硬件资源较小等优势。随着 模式识别、图像处理以及信息传感等技术的不断发展，自动指纹识别技术将展现 出更加广阔的应用前景。 1 1 2 指纹识别系统 指纹识别技术是生物测量学技术中较为成熟、应用较多的一种，它是一种利 用人的指纹进行计算机自动识别的综合技术。其基本原理【3 l 是通过指纹采集仪得 到指纹图像，然后用适当的算法进行指纹图像预处理，并提取指纹的特征数据， 最后通过匹配算法获得识别结果。 指纹识别系统就是用计算机软件实现以上流程能够进行自动对比的模式识别 系统，主要包含以下四个模块( 图1 - 1 ) ：( 1 ) 指纹采集：( 2 ) 指纹预处理：( 3 ) 特征提取；( 4 ) 指纹匹配。 _ h h ，h ，- - - - - _ - _ - _ - _ _ - _ - _ - 1 一 ：l 缮绞幽豫壤缝篱纠： ： ： l 图1 - 1 指纹识别流程 l 指纹采集 指纹采集就是通过相关采集设备得到数字化的指纹图像。从采集方式来看 山东大学硕士学位论文 指纹基本可以分为三类：捺印指纹、活体指纹和模糊指纹。 捺印指纹指的是将沾了印墨的手指按压在某种东西( 通常是纸) 上留下的指 纹的痕迹，再经相应设备转化为数字化的信息，就得到捺印指纹图像。活体指纹 就是指经活体指纹采集设备得到的是数字化的指纹图像。根据采集原理的不同， 活体指纹采集仪可分为光学式、半导体式和超声波式等几种【2 】。模糊指纹一般是 指在犯罪现场采集到的指纹，即将罪犯无意中遗留在犯罪现场的指纹痕迹经过显 影、拍照和扫描等技术处理而得到的指纹图像。 捺印指纹采集到的有效面积比较大，但因采集方式所限，采集速度较慢，指 纹缺陷较多，目前难以严格控制采集的质量。模糊指纹更多的是用现有技术还原 罪犯无意间留下的指纹痕迹。相比较而言，活体指纹的质量是最好的。 2 指纹预处理 指纹预处理是指纹特征提取前的不可缺少的一个重要环节，主要用于突出指 纹图像中的纹理、方向信息，消除或者减弱噪声等无用信息。指纹图像预处理包 括指纹图像分割、图像增强、二值化、细化等。 指纹图像分割位于预处理的最前端，就是将指纹图像从背景区域中分割出来， 对于缩短图像处理时间、提高特征提取的准确率都具有重要意义。图像增强是根 据指纹图像纹理的方向性和纹线距离对可恢复的纹线进行恢复和增强，对于不可 恢复的区域进行屏蔽。二值化即将图像中灰度大于某阈值的像素的灰度置为1 ， 小于等于该阈值的像素的灰度置为0 ，即将图像变为二值图像。细化就是提取指 纹图像的脊线骨架。 3 特征提取 指纹特征提取是在预处理指纹图像的基础上，提取指纹的关键特征。指纹的 细节特征( m i n u t i a e ) 有1 5 0 种之多。但这些特征出现的概率并不相同，其中很 多特征是极其罕见的。在自动指纹识别技术中，一般只使用两种细节点特征：纹 线端点( 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 所示。 通过算法检测指纹中这两类细节点的数量以及每个细节点的类型、位置和所在区 域的纹线方向是特征提取算法的任务。 山东大学硕士学位论文 4 指纹匹配是判断两枚指纹是否来自同一个人的同个指头。 1 1 3 工作模式及性能评价 图卜2 细节点类型示意图 1 工作模式 指纹识别系统本质上是一个模式识别系统，目的是为了防止多个人使用同一 个身份 4 】。它根据使用者的生理或者行为特征对使用者进行辨识，从而判断其是 否具有合法身份。指纹识别系统的工作模式可以分为两类【4 】：验证( 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 ) ，来确认身份的过程。作为验证的前提条件，他或 她的指纹必须在指纹库中已经注册。指纹以一定的压缩格式存贮，并与其姓名或 其标识( 1 1 3 ，p i n ) 联系起来。随后在比对现场，先验证其标识，然后，利用系 统的指纹与现场采集的指纹比对来证明其标识是合法的。验证其实是回答了这样 一个问题：“他是他自称的这个人吗? ”这是应用系统中使用得较多的方法。 辨识则是把现场采集到的指纹同指纹数据厍中的指纹逐一对比，从中找出与 现场指纹相匹配的指纹。这也叫“一对多匹配( o n e 4 0 - m a n ym a t c h i n g ) ”。验证 其实是回答了这样一个问题：“他是谁? ”辨识主要应用于犯罪指纹匹配的传统领 域中。例如，将一个不明身份的人的指纹与指纹库中有犯罪记录的人指纹进行比 对，来确定此人是否曾经有过犯罪记录。 2 性能评价 为了反映当今模式识别应用的技术水平和发展状况，国际上举行了三届指纹 识别竞赛5 6 ”。f v c 各届竞赛均使用四个标准指纹库做测试，并建立了统一的性 能评价标准，通过各种指标衡量指纹识别系统的性能，女e i e e r 、f m r ，f n m r ，f 4 山东大学硕士学位论文 m r l 0 0 、f m r l 0 0 0 ，z e r o n 心瓜和z e r o f m r 。其中，e r r 是等错误率，即拒识率 和误识率相等时的拒识率或误识率。f m r 是误识率，f n m r 是拒识率。f m r l 0 0 表示当f m r = i 1 0 0 时的f n m r ，f m r l 0 0 0 表示当f m r = i 1 0 0 0 时的f n m r ，z e r o n 删喂表示当f n m r = o 时的f m r ，z e r o f m p 壤示当f m r = 0 时的f n m r 。近年来， f v c 的各项标准在指纹识别算法性能的研究中已经被广泛采用。 1 2 研究现状 1 2 1 指纹匹配 与人工处理不同，现在的自动指纹识别系统并不直接存储指纹的图像，而是 通过对两幅给定的图像提取特征信息进行匹配，判断这两枚指纹是否是同源的， 即是否来自同一个指头。由此看来，指纹识别算法最终都归结为在指纹图像上找 到并比对指纹的特征。 目前，用于指纹验证的特征可以分为两类：总体特征和局部特征。总体特征 是指那些用肉眼直接就可以观察到的特征，包括：纹形、模式区、核心点( c o r e ) 、 三角点( d e l t a ) 。纹形是指纹线的整体形状，主要有环形( 1 0 0 p ) 、弓形( a r c h ) 、 螺旋型( w h o r l ) 三种基本类型。模式区是指指纹上包括了总体特征的区域，即从 模式区就能够分辨出指纹是属于那一种类型的。纹形和模式区常用作指纹分类 f 8 】。核心点位于指纹纹路的渐进中心，是曲率最大的细节点。三角点位于从核心 点开始的第一个分叉点或者断点、或者两条纹路会聚处、孤立点、折转处。核心 点和三角点统称奇异点。 局部特征是相对于总体特征而言的细节特征，可以分为两类：单一细节特征 和混合细节特征。单一细节特征是指客观存在的，可以通过特征提取算法直接提 取的细节特征一一细节点( 端点、分叉点、分歧点、孤立点、环点、短纹) 和纹 线。目前最常用的细节点有两种：纹线端点( 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 f v ) t o l 。 根据指纹匹配的模式可以分为验证模式和辨识模式 1 1 - 1 3 ：根据操作过程不同 可分为自动匹配c s ，1 4 】和入机交互匹配：根据匹配适应性可以分为弹性匹配n 们和 刚性匹配【”。不同的分类不胜枚举，然而这些分类方法都难以囊括所有的指纹匹 配算法，同时一些算法又可以综合多种分类的特性。 按照指纹匹配使用特征的不同可以分为以下五种，基于点模式的匹配【”- z 4 ， 基于纹线的匹配1 2 2 7 1 ，基于图的匹配 2 8 - 2 9 1 ，基于纹理的匹配【3 0 - 3 2 以及多种细节特 征混合的匹配方法 3 3 - 3 4 】。 基于点模式的匹配是目前指纹匹配算法中的主流方法。首先，利用局部特征 匹配获得模板指纹和待识别指纹之间的旋转平移参数；其次，将两幅指纹进行姿 势调整：最后，全局匹配求取匹配得分。该类方法的关键在于局部匹配中使用的 局部特征，其目的是为了获取精确的旋转平移参数。众多学者为此做了大量的工 作。 尹义龙川提出了一种基于纹线拟合的指纹匹配方法，即利用纹线拟合技术来 寻找基准点对的指纹匹配算法。该算法基于指纹纹线的相似程度寻找一对基准特 征点，然后根据基准点对的坐标计算两幅指纹图像( 模板图像、待识图像) 的相 对平移和旋转参数，并将待识别图像相对于模板图像进行图像姿势纠正，最后使 用坐标匹配的方法统计两幅图像能够匹配的特征点数目，实现两枚指纹的匹配。 x j f e n gt o n g 1 0 1 等人提出了一种基于i 临近特征向量( a f v ) 的细节匹配算法。 该方法利用纹线方向和纹线数目信息生成成了一个新的局部结构一一临近特征向 量。首先，从给定细节点a 引出两条相互垂直的直线，确定四个与细节点同等距离 的临近点t l ，t 2 ，t 3 ，t 4 ，b ，0 2 ，岛，0 4 分别表示四个临近点的方向。o l ，0 2 ，0 3 ，0 4 表示细节点a 的方向占与四个临近点方向最，包，岛，0 4 之间的夹角，n 1 ，n 2 ，n 3 ，n 4 ， n 5 ，n 6 则表示a t l ，a t 2 ，a t 3 ，a t 4 ，t l t 3 ，t 2 t 4 跨越的纹线数目。那么，临近特征向量 就是由o l ，0 2 ，0 3 ，0 4 ，n l ，n 2 ，n 3 ，n 4 ，n 5 ，n 6 组成的一维向量。其次，算法使用两对 细节点进行姿势调整。最后，由坐标匹配细节点对的相似程度计算得到匹配得分。 w e i w e iz h a n g l 等人的基于c o r e 点的结构匹配算法，受奇异点提取准确性的 山东大学硕士学位论文 影响。卢朝阳1 3 6 】等人的基于d t ( d e l a u n a yt r i a n g u l a t i o n ) 网格的细节点匹配算 法，利用d t 网格搜索匹配线对从而加快搜索速度及匹配速度。j i nq i f 3 刀等人定义 了一个由细节点周围若干采样点组成的新特征向量，并且结合方向场信息进彳亍匹 配。 指纹图像在本质上是脊线和谷线以固定的频率交替出现的一种纹理模式。正 是基于这个纹理特性，a k j a i n i ”1 等人提出了基于滤波器组的指纹匹配算法。 首先，以c o r e 点为中心将指纹图像划分成若干个扇形区域。其次，使用g a b o r 滤波 器对指纹图像分成8 个方向( 0 。，2 2 5 4 ，4 5 4 ，6 7 5 。，9 0 。，1 1 2 6 。，1 3 5 。，1 5 7 5 。) 进行滤波，得到每个方向的g a b o r 滤波图像。然后，在计算每个 滤波图像的纹理特征值一一平均绝对方差h a d ，并且将所有区域的纹理特征值a a d 以某个固定的顺序组成指纹特征码f i n g e r c o d e 。最后，计算模板指纹和待识别指 纹特征码之间的欧式距离，实现指纹匹配。 指纹匹配是自动指纹识别系统( a f i s ) 的核心研究内容之一，它在指纹特征 提取之后，是自动指纹识别的最后一步，也是非常关键的一步。指纹匹配靠比较 两枚指纹的细节点、纹线或者其他局部结构特征来决定指纹的唯一性。然而，由 于采集设备的不完善性、采集条件的随机性以及预处理技术的局限性，使得真正 特征点的缺失、伪特征点的存在和特征点定位偏差的情况普遍存在。所以，指纹 匹配必然还是一种模糊匹配，且需要具备一定的弹性。 1 2 2 纹线距离估计 纹线距离指的是两条相邻指纹纹线之间的距离，可以被看作从一条脊线中心 到与之相邻的另一条脊线中心的距离或者是一条脊线和与之相邻的谷线宽度的 和。在一幅指纹图像中，指纹纹线距离应该是一致的。但是，在指纹采集过程中， 由于手指用力方向的不同造成的不同区域出现纹线距离不同、甚至差别很大的情 况以及由其他因素造成的对比度小、纹线间断和纹线粘连等噪声的存在会对纹线 距离的估计形成一定的干扰。 指纹图像增强在自动指纹识别系统中起着消弱噪音影响同时突出关键特征信 息的重要作用。在指纹图像增强中，纹线距离是一个重要参数。因此，纹线距离 7 山东大学硕士学位论文 的估计也是非常重要的环节。在自动指纹识别领域，很多文献使用了纹线距离并 强调了它的重要性。但是，深入研究纹线距离估计的文献却不多。已有文献提供 的方法主要可以归结为三类：基于块水平的纹线距离估计方法、基于区域水平的 纹线距离估计方法和基于整幅图像估计纹线距离的方法。 l h o n g p 卅等人提出了一种估计纹线频率的方向窗方法。在图像对比度好和 方向窗内纹线方向比较一致的情况下，该方法可以可靠地估计纹线频率。但当噪 声干扰严重或者方向窗内纹线方向不完全一致时，该方法的性能会受到严重影响。 z m 。k o v a c s - v a j n a 4 0 1 等人提出了纹线距离估计的两种方法：几何法和谱分析 法，两种方法都是针对分块图像估计纹线距离的，也属于窗口方法的范畴。几何 法的一个优点是它不需要纹线方向的计算结果作为先导。但由于该方法中有很多 门槛值需要精确选定，这些门槛值又会因图像质量的差异和其他因素的影响而变 化，这就使得这种方法比较复杂，实现的难度也比较大。谱分析法则是将图像分 块，利用离散傅立叶变换将每块图像由空间域表达转换为频域表达，然后根据谐 波系数分布估计该块图像的纹线距离。 尹义龙提出了基于区域水平的纹线距离估计方法p 1 】。该方法依据指纹图像方 向场将指纹图像分成若干个区域，每个区域中指纹纹线方向大致相近。在若干被 划分的区域中统计出现频率最高的纹线距离，作为该区域的纹线距离。而整幅图 像的平均纹线距离由这些区域的纹线距离计算平均值得到。 0 g o r m a na n dn i c k e r s o n 4 1 l 在指纹滤波器设计中将纹线距离作为滤波器的一 个关键参数来使用，该方法使用的是纹线距离的统计均值，假定纹线距离在整幅 指纹图像上是一个常量并将指纹划分为三个的类别。l i na n dd u b e s 4 2 1 试图实现纹 线数目的自动统计并假定纹线距离在整幅指纹图像上是一个常量。他们发现，实 际上纹线距离在一幅指纹图像不同区域有时候会有所变化，这种变化会干扰纹线 数目的统计结果的正确性。h u n 9 1 4 3 通过计算脊线和谷线宽度的和实现在整幅指纹 图像上估计纹线的平均距离。陈旭】将整幅图像转换到频域能量谱图像，计算能 量直方图，通过检测峰值计算出对应的纹线距离作为整幅图像的平均纹线距离。 山东大学硕士学位论文 1 3 课题的选择 本文针对指纹匹配以及指纹识别系统中的一个重要参数纹线距离的估计 进行了深入细致的分析和研究。 本文仔细分析了尹义龙等人提出的基于d t 网格的指纹匹配算法 4 5 1 ，发现其中 存在的两个问题：细节点方向跨越3 6 0 。问题和边跨越9 0 。问题，并针对这些问 题对算法提出相应的改进措施。此外，本文提出的细节点方向和边方向变化一致 性的概念，应用于算法当中能够更加精确地寻找相似边。尤其在非同源指纹匹配 时，抑止虚假相似边的大量产生也就抑止了误识的发生，有效的提高了匹配算法 的性能。 指纹增强在指纹图像的识别过程中是最为重要的一环，增强的效果对整个系 统的性能产生至关重要的影响。纹线距离是指纹的一个固有属性，也是基于加博 滤波器的指纹增强算法中的一个重要参数。纹线距离估计的精确程度直接影响基 于加博滤波器的指纹增强效果。但是，受指纹图像质量的影响，现有算法对纹线 距离的估计往往不够准确。本文尝试实现了两种基于频谱分析的纹线距离估计算 法，并进行了性能比较。 1 4 论文的组织和创新之处 本论文共分四章，其中第一章为绪论，主要介绍了自动指纹识别技术的发展 历史、研究内容、性能评价体系及研究现状。第二章和第三章为正文部分。第二 章引入了基于弧网格的指纹匹配算法，第三章主要讨论了两种基于频谱分析的纹 线距离估计算法，第四章是本文总结。 针对目前指纹匹配方法中参考点确定精度不高的情况，在基于d t 网格的指纹 匹配算法中，通过解决细节点方向和细节点连线方向的定义问题，并提出细节点 方向和细节点连线方向变化趋势一致性的概念，进一步准确确定参考点对，有一 定的可取之处。此外，基于频谱分析，提出了基于多峰值检测和朴素的加权平均 思想来估计纹线频率，有一定的创新性。 山东大学硕士学位论文 第2 章基于d t 网格的指纹匹配方法 随着传统身份识别的不可靠性与日俱增，基于生物特征的身份识别因其不可 伪造性受到越来越多的关注。自动指纹识别系统( a f i s ) 就是生物特征识别的一 种，包括指纹采集、预处理、特征提取和指纹匹配。指纹匹配处于自动指纹识别 系统中的最后一个环节，也是非常关键的一步，因此成为一个研究的重点。 目前，基于细节点( 纹线端点和纹线分叉点) 的点模式匹配是指纹匹配的主 流方式。在这种算法体系下，指纹被表示成离散的细节点集合，指纹匹配依赖于 细节点的匹配。 多年来，国内外众多学者致力于指纹匹配的研究，并在点模式匹配方面提出 了一些方法。罗希平等人的一种细节匹配算法1 ，引入脊线信息，提高了匹配算 法的有效性。尹义龙等人提出了一种基于d t 网格的指纹匹配算法h ”，它利用d t 网 格中的相似三角形计算指纹姿势纠正的参数从而进行匹配，是一种比较有效的指 纹匹配算法。但是，其实现细节上并不完善，本章在统计分析的基础上对存在的 问题进行了改进。 2 1 基于d t 网格的指纹匹配算法思想 在基于特征点的匹配算法中，两个待匹配的指纹特征模式可以看成两个平面 域上的离散点集。计算几何的三角化方法是分析研究区域离散数据的有力工具， 在这个原理下生成的d t 网格具有唯一性和良好的局部性。这两个性质决定了其在 处理点模式指纹匹配时的优势明： ( 1 ) “三角化”方法对离散点集的划分结果，具有唯一性。即对于相同的两 个点模式，使用同样的三角划分准则，划分的结果是相同的。这是“三角化”方 法的固有属性。 ( 2 ) “三角化”方法对指纹特征点模式的划分结果，具有良好的局部性。三 角划分采用“最小角最大”( m a x - m i n ) 准则，对指纹特征点组成的平面点集进行 三角划分，使划分得到的三角网格具有良好的局部性。在指纹特征点模式中，这 山东大学硕士学位论文 种划分规则可以使少数真正特征点的缺失、个别伪特征点的出现和特征点的定位 偏差等因素对划分结果的影响尽量局限在一个小的局部区域内，从而使待匹配的 两个特征模式( 如果他们来自同一手指) 的大部分区域的划分结果是基本相同的。 只要待匹配的两个特征模式中真正特征点的缺失、伪特征的存在现象不是特 别严重、并且两个特征模式客观上具有足够的重叠区域，就能得出正确的匹配结 果。由此可以看出，基于d t 网格的指纹匹配算法是一个比较有效的指纹匹配方法。 由参考文献 4 5 可知，基于d t 网格的指纹匹配算法的基本思想如下： 第一步，采用基于均匀网格的三角网生长法【4 8 1 划分离散细节点集生成d t 网 格。 第二步，基于d r r 网的局部匹配与参考点对求取。该算法主要有如下3 个步骤 组成： ( 1 ) 在输入图像和模板图像的d t 网格里找相似边。从两个三角网中各选一条任 意边l l ，k ，边长分别为l 。，l 。边l 。的两个端点r u ，r 。其特征点方向为d 1 1 ，观，边 k 的两个端点r 2 ：，r 毖，判断这两条边是否满足下面的条件： l 厶一乞l 五 ( 2 - 1 ) i iq 。一口2i _ i 砬。一d 2 ：i l 疋 ( 2 - 2 ) 其中，t ，t 2 是经验值。如果以上两个条件都满足，则表示l l ，k 是一对相似 边，转( 2 ) ；不满足则继续找相似边，直到找到一对相似边或者搜索完毕，没有 相似边，则算法结束。 ( 2 ) 在d t 网格中，边的结构包括4 个标志位s 、t 和l 、r ，其中s 、t 对应边的两 个端点，l 、r 对应边的左右是否有三角形。令s 对应x 坐标较小的端点，t 对应下x 坐标较大的端点。根据一条边的方向及左右标志，可以找到这条边的左( 右) 邻 三角形。假设有左邻点p 1 ，p 2 ，则有两个左( 右) 邻三角形t r i l ，t r i 2 ，转( 3 ) ： ( 3 ) 比较三角形( 图2 - 1 ) ，判断两个三角形是否满足以下条件： i 。一乞。i 五，i ，l ：一乞i 己 ( 2 3 ) 旧。广0 2 li 7 4 ，i 已2 一如l p s s t x ) e s j s = s t ： e s j t = s s ： 1 ) 山东大学硕士学位论文 e i s e ( i f ( a b s ( p t t s x p i t t x ) a b s ( p t t s y p t t t y ) p s s t y ) e s j s = s t ； e s j t = s s ： ) ) ) 上述算法中，两条边中的任意条边恰好是垂直方向时，本文认为两条边位 于同侧。其中，t 。是边与垂直方向之间夹角的阈值。 当两条边位于垂直方向的同一侧时，无需考虑这个问题。而当两条边分居垂 直方向的两侧，与垂直方向夹角大于给定阈值时，本文认为在旋转角度不是很大 的情况下，也没有必要考虑。只有当两条边分居垂直方向的两侧，同时与垂直方 向夹角小于给定阀值的情况下，才有必要考虑以y 坐标调整边的起点和终点。 边的起点和终点确定之后，下面所要做的工作就是判断其是否相似。为了尽 可能的保留真正的相似边，去除虚假的相似边，本算法在考虑跨越3 6 0 。问题的 同时，还引入了细节点和边方向变化致性的概念。所谓细节点和边方向变化一 致性是指给定一对边，在指纹图像有旋转的情况下，对应细节点方向的变化趋势 应该完全与边的方向变化趋势一致，都是逆时针或顺时针方向，即指纹图像的旋 转方向。 在实际应用过程中，由于方向估计误差，变化趋势往往不会完全一致。因此， 本文采用细节点总体变化趋势和边方向变化趋势进行比较。细节点总体变化趋势 是由两个细节点共同决定的，可以代表指纹的旋转方向。边方向变化趋势也在一 定程度反应了指纹旋转的方向。因此，用这两个变化趋势足以区分相似边的真伪， 山东大学硕士学位论文 从而剔除一些伪相似边。 在算法执行过程中，只有当对应细节点的方向分居0 。( 3 6 0 4 ) 方向两侧并 且与之夹角小于给定阈值时才考虑变换细节点方向，变换后的细节点方向同样用 于方向一致性的判断。具体算法如下： t s = e t i s ：t t = e t i t ：s s = e s j s ：s t = e s j t ： d l = a b s ( p t t s a - p s s s a ) ： d 2 = a b s ( p t t t a - p s s t a ) ： i f ( d l l s o ) ( i f ( ( a b s ( p t t s a - 3 6 0 ) t 6 | la b s ( p t t s a - o ) t 6 ) a b s ( p s s s a - 3 6 0 ) t 6i | a b s ( p s s s a _ o ) t 6 ) ( d l = a b s ( d l 一3 6 0 ) ； i f ( a b s ( p t t s a o ) t 4 ) p t t s a + = 3 6 0 ： i f ( a b s ( p s s s a - o ) 1 8 0 ) ( i f ( ( a b s ( p t t t a - 3 6 0 ) t 4 | ia b s ( p t t t 瑚) t 4 ) a b s ( p s s t a - 3 6 0 ) t 4 | la b s ( p s s t a - o ) t 4 ) f d 2 = a b s ( d 2 - 3 6 0 ) ： i f ( a b s ( p t t t 铲o ) o ) ) i f ( 1 e n g t h ( e 。j ) 一l e n g t h ( e t i ) t 5 a b s ( a b s ( p t t s a - p s s s a ) 一a b s ( p t t t a p s s t a ) ) t 6 ) a d d e d g e ( e “，e 。，e p a i r ) ： ) 算法执行过后，e p a i r 将记录所有的相似边，然后寻找相似三角形，确定参考 点。使用相似三角形的三对参考点计算平均旋转平移参数，将输入指纹和模板指 山东大学硕士学位论文 纹