（计算机软件与理论专业论文）自动指纹识别系统的研究.pdf

摘要 指纹具有唯一性和终身不变性，因此用来作为鉴别个人身份的依据。自动指 纹识别系统是用计算机来自动进行指纹识别，具有方便、高效、可靠等优点。在 金融安全、数据加密、电子商务等各个领域都得到了广泛的应用，并将在我们的 生活中发挥越来越重要的作用。 本文在收集和分析近年来国内外有关自动指纹识别技术研究成果的基础上， 对自动指纹识别系统的关键技术进行了研究。主要工作有以下几个方面： ( 1 ) 指纹图像预处理。其目的是去除原始图像中的各种噪声，增加图像的 清晰度，恢复指纹固有的脊线结构，将图像变成只有单象素宽的点线图，以便于 下一步的细节特征提取。具体包括指纹图像归化、方向图计算、频率图计算、 增强、前背景分割、二值化及后处理、细化等几个部分。 ( 2 ) 指纹的特征提取。其目的是从经过预处理得到的细化图中，提取所有真 实的端节点和分支点。文中采用求取8 一邻域交叉数算法，提取指纹中所有的端节 点和分支点，然后利用脊线跟踪算法去除其中的伪特征点。 ( 3 ) 基于脊线校准的特征点匹配。其目的是根据提取到的指纹中的端节点 和分支点，来判断两枚指纹是否来自同一手指。本文提出了一种改进的指纹匹配 算法，利用如果两个特征点相同，则它们与各自相距最近的2 个特征点组成的三 角形必然相似的性质，对初次选定的基准点进行了筛选，去除了一部分错误的基 准点。将如果两个特征点相同，则它们到各自基准点的纹线数相同的性质，作为 判断两个特征点是否相同的条件之一。实验表明，在相同的条件下，改进后算法 的正确识别率比原算法提高近3 个百分点。 该套算法在国际指纹识别竞赛( f v c2 0 0 0 ) 提供的标准指纹库上测试，识别 准确率为9 1 0 3 ，拒识率为7 9 1 ，误识率为1 0 6 ，平均每两枚指纹的比对时间 约为0 0 1 9 s 。 关键词：方向场预处理特征提取脊线跟踪匹配 a b s t r a c t d u et ot h e i ru n i q u e n e s sa n dp e r s i s t e n c e ，f i n g e r p m l t sa r eu s e da sm a i nb a s i so f p e r s o n a li d e n t i t y 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 , at e c h n o l o g yo ff i n g e r p r i n t i d e n t i f i c a t i o nu s i n gc o m p u t e r ，i so fc o n v e n i e n c e ，h i g he f f i c i e n c y ，s e c u r i t ya n dr e l i a b i l i t y - i t h a sb e e na p p f i e di nm a wf i e l d ss u c ha sf i n a n c i a ls e c u r i t y ，d a t ae n c t y p f i o n ，e l e c t m n i c a l b u s i n e s sa n dw i l lp l a yam o r ea n dm o t e i m p o r t a n tr o l ei no u r l i f e b a s e do nl a t e s te x t e n s i v ed i s c o m s e sa n dt e c h n o l o g y j o u z n a l si nt h i sf i e l d ，t h e d i s s e r t a t i o n i s 仕y i “g t om a k es t u d i e so na l g o r i t h m so fa f i s m a i n l yw o r k sa r ea s f o l l o w i n g ： ( 1 ) f i n g e r p r i n tp r e p r o c e s i t sp u r p o s ei sr e m o v i n gn o i s eo ff i n g e r p r i n ti m a g e a n d i m p r o v i n gd e f i n i t i o no ff i n g e r p r i n ti m a g e , g e tt h e s t r u c t u r eo ff i n g e r p r i n tr i d g e , c h a n g e f i n g e r p r i n ti m a g et o ao n ep e l sw i d t hi m a g e w h i c hw i l l b eb e n e f i c i a lt ot h ef o l l o w f e a t u r ee x t r a c t i o n p r e p r o c ei n c l u d e si m a g en o r m a l i z i n g ，o r i e n t a t i o ne s t i m a t i o n , f r e q u e n c e e s t i m a t i o n ，姆e x t r a c t i o n 丘d g er e m o v e dn o i s e ，t h i n n i n g ( 2 ) f i n g e r p r i n tf e a t u r ee x t r a c t i o n i t sp u r p o s ei s g e ta l lt x u ee n c t i n ga n d b i f u r c a t i o n t h et w ok i n do fm i n u t i a ec a r lb ee x t r a c t e db yu s i n g8 - n e i g h b o r h o o dc r o s s c a l c u l a t i o n a 1 9 0 甜m a f e a t u r ee x t r a c t i o n p o s t p r o c e s s i n ga l g o r i t h mw o u l d d e l e t ea l lf a l s e m i n d t i a e ( 3 ) f i n g e r p r i n ti m a g em a t c h i n g i t sp u r p o s ei sj u a g ew h e t h e r t h et w of i n g e r p r i n ta t e c a p t u r e df r o mt h e s a l n ef i n g e rb a s e d0 1 1t h e i rm i n u d a e w ea d v a n c e da na l i o , o r i t h m s c r e e nt h ep r i m a r yr e f e r e n c ep o i n t sa n dr e m o v et h o s ew r o n gp o i n t sa c c o r d i n gt ot h e p r o p e r t yt h a tt w oi d e n t i c a lm i n u t i a e sw i l ln e c e s s a r i l yc r e a tas i n m 觚d _ g o nw i t ht w op o i n t s n e a r e s tt oe a c hr e s p e c t i v e l y t w oi d e n t i c a lm i n u t i a el e a dt oi d e n t i c a lt i a g en u m b e r t o t h e i rr e s p e c t i v er e f e r e n c ep o i n t , w h i c hi sc o n s i d e r e da so n eo ft h ec o n d i t i o n st od e t e r m i n e w h e t h e ro rn o tt h et w or e f e r e n c ep o i n t sa r ei d e n t i c a l t h ee x p e r i e m e n t ss h o w e dt h a tt h e c a ne f f e c t i v e l ya v o i dt h ee l t o rf r o mt h er o t a t i o na n dn o n l i n e a r i 姆 o ft h ef i n g e r p r i n t t h ea l g o d 血ni st e s t e di nf v c 2 0 0 0d b l ，t h et l x l ea c c e p tr a t ei s9 1 0 3 t h ef a l s e r e j e c tr a t ei s7 9 1 t h ef a l s ea c c e p tr a t ei s1 0 6 ，t h et i m eo fc o m p a r k n gt w of i n g e r p r i n ti s 0 0 1 9 s k e yw o r d s ：o r i e n t a t i o n & 1 d ，p r e p r o c e s s i n g ；m i n u t i ae x t r a c t i o n ；r e m o v i n gf a l s em i n u t i a ； m a t c h i n g i i 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻 读学位期间论文工作的知识产权单位属于西北大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被 查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。同时，本人保证，毕业后结合学位论文研究课题再撰写的文 章一律注明作者单位为西北大学。 保密论文待解密后适用本声明。 学位论文作者签名：盎群鸳 指导教师签名： f 塑啦垒 册j 年6 月i 日年月日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名：瓜群将 3 耐年6 月8 日 第一章绪论 1 1 国内外发展现状 近年来，随着光电技术和计算机技术的迅猛发展，使得指纹图像的采集和处 理变得更为可行，为自动指纹识别技术的发展奠定了坚实的基础。自动指纹识别 技术主要由两部分组成：采集技术和识别技术。 在采集技术方面，较早出现的光电式活体指纹采集设备，现在仍为大多数自 动指纹识别系统所使用。后来出现的电容和电感式的采集设备，在某些条件下可 提高指纹采集的质量，但在耐磨性和稳定性等方面还存在一些问题。对干、湿、 脏的指头或磨损严重的指纹均能可靠、正确地进行采集和尽量减少采集时的变形 是指纹采集技术需要解决的主要问题。 在识别技术方面，很多国家都有公司或专门机构在从事研究。研究的重点主 要集中在如何提高识别的准确率和速度上“1 。美国的i d e n f i c a t o r 公司、s e c u g e n 公 司、法国的s e g a m 公司都有成型产品面市，i d e n t i c a t o r 公司的i ds a f e 生物识别技 术已经得到了较为广泛的应用，被用于全世界上百万台个人计算机，有5 0 0 0 多 万人登记使用i ds a f e 系统n 1 。国内的中科院自动化所、北京大学、清华大学等 高校和科研机构在这方面也取得了很大的进展，北京大学石青云院士领导研制的 用于公安刑侦的自动指纹识别系统在实际应用中取得了很大的成功。北京中控公 司、南京凹凸公司等许多公司都有各种产品面市，已经开始在管理、门禁、金融、 公安和网络安全等领域得到应用。 尽管当前的指纹识别产品已经多种多样，并成功地应用到许多领域，但是指 纹识别技术仍是国内外科研人员研究的热点。这是因为一方面，出于知识产权保 护和商业利益的原因，指纹识别的核心技术只被少数企业和技术机构所拥有；另 一方面，人们日益增长的需求对指纹识别系统的性能提出了更高的要求。所以， 自动指纹识别系统的研究既有很强的理论意义，也有很高的实用价值。 1 2 1 基本概念 1 2 指纹识别的原理 指纹是手指末端正面皮肤上凹凸不平产生的纹路，这些纹路就是通常所说的 脊和谷。尽管指纹只是人体皮肤的- - + 部分，但是，它蕴涵大量的信息。这些近 乎平行的曲线，形成了指纹的模式，成为指纹的全局纹路结构；同样，指纹还有 许多局部特征，称为细节点( m i n u t i a ) 。正是这些全局特征和局部特征形成了指 纹的独特性，使它成为身份认证的可靠工具。 ( 1 ) 指纹的全局特征 全局特征指那些人眼可以_ 直接观察到的特征，包括基本纹路图案、模式区、 核心点( 中心点) 、三角点、式样线和纹线数等幻1 。基本纹路图案有拱形、尖拱 形、右旋、左旋、旋涡。如图1 1 所示。 拱形尖拱形右旋左旋旋涡 图1 1 基本纹路图案 模式区是指纹上包括了总体特征的区域，即从模式区就能够分辨出指纹是属 于哪一种类型的。有的指纹识别算法只使用模式区的数据。核心点( 中心点) 位 于指纹纹路的渐进中心，它在读取指纹和比对指纹时作为参考点。三角点位于从 核心点开始的第一个分叉点或者断点、或者两条纹路会聚处、孤立点、折转处， 或者指向这些奇异点。三角点提供了指纹纹路计数跟踪的开始之处。纹线数指模 式区内指纹纹路的数量。在计算指纹的纹数时，一般先连接核心点和三角点，这 条连线与指纹纹路相交的数量即可认为是指纹的纹线数。如图1 2 “1 所示。 模式区中心点三角点纹数 图1 2 指纹图案细分图 2 利用指纹的全局特征，可以对指纹进行分类，这样做的意义在于，预先把大 型的数据库分成了几个组，可以减少数据库搜索时间：匹配时，首先进行模式匹 配( 称作“粗匹配”) ，有助于提高识别率。 ( 2 ) 指纹的局部特征 局部特征是指指纹上节点的特征，这些具有某种特征的节点称为特征点。两 枚指纹经常会有相同的总体特征，但它们的局部特征特征点，却不可能完全 相同。 指纹纹路并不是连续和平滑笔直的，而是经常出现中断、分叉或打折。这些 断点、分叉点和转折点就称为“特征点”( 也就是细节点，m i n u d a ) 。就是这些 特征点提供了指纹唯一性的确认信息，人们正是利用这些局部特点进行指纹的精 确匹配。 这些指纹特征点可用以下四种特性来描述： 分类( c l a s s i f i c a t i o n ) 特征点有以下几种不同类别b 1 ，其中最典型的 是终结点( 末梢点) 和分叉点，而其他的细节点可以用它们的组合来表示。例如 环可以看成两个分叉点，便可以看成一个终结点和一个分叉点等。 疗 一 终结点( e n d i n g ) ：一条纹路在此终结。 口 分支点( b k f i u c a t i o n ) ：条纹路在此分开成为两条或更多的纹路。 c 一 1 分歧点( e a d g ed i v e r g e n c e ) ：两条平行的纹路在此分开。 口 孤立点( d o t ) 条特别短的纹路，以至于成为一点。 _ ，- 环点( e 。1 。s u r e ) ：一条纹路分开成为两条之后，立即有合并成为一条， 这样形成的一个小环称为环点。 p - 短纹( s h 。= r i d g e ) ：两端较短但不至于成为一点的纹路。 方向( o r i e n t a t i o n ) 节点可以朝着一定的方向。 3 所在脊线( r i d g e ) 节点所在脊线通过脊线上的采样点来描述。 位置( p o s i t i o n ) 节点的位置通过( x ，v ) 坐标来描述，可以是绝对的，也可以是相对于三岛点 或特征点的。 1 2 2 基本原理 两枚指纹经常会具有相同的总体特征，但它们的局部特征特征点，却不可 能完全相同，因此，指纹识别技术通常使用指纹的全局特征来进行分类，再用局 部特征来进行识别用户身份。 通常，首先从获取的指纹图像上找到特征点( m i n u t i a e ) ，然后根据特征点的 特性建立用户指纹的数字表示指纹特征数据( 一种单向的转换，可以从指纹 图像转换成特征数据但不能从特征数据转换成为指纹图像) 。由于两枚不同的指 纹不会产生相同的特征数据，所以通过对所采集到的指纹的特征数据和存放在数 据库中的指纹特征数据进行模式匹配，计算出它们的相似程度，最终得到两个指 纹的匹配结果，根据匹配结果来鉴别用户身份。 图1 3 自动指纹识别系统的原理框图 总之，自动指纹识别系统首先通过取像设备读取指纹图像，然后用计算机识 别软件提取指纹的特征数据，最后通过匹配识别算法得到识别结果。其基本原理 框图如图1 3 3 所示。 4 1 3 自动指纹识别系统的构成 自动指纹识别系统主要由图像输入、预处理、特征提取、分类和匹配等五部 分组成，其中预处理部分又可分为图像分割、图像增强、二值化和细化等几个步 骤。系统的流程框图如图1 4 所示。一个优秀的指纹识别系统要求能实时、迅速、 有效地完成其识别过程，这就要求：一方面，系统的每个组成部分所包含的算法 要快速、高效，既要很好地完成该模块的功能，又要耗时足够短：另一方面，系 统的各个部分要能够很好地衔接起来，前一部分要为后面提供尽可能理想的数据， 后一部分要充分利用前面的处理结果，使整个系统的性能得到提高。因此，实际 的指纹识别系统往往由于应用环境、系统规模、实现思路以及具体算法的不同， 而在系统整体框架上有所出入。例如，一般的小型应用，如家庭门禁、指纹保险 箱等，就不需要分类步骤；有的系统直接从原始指纹图像提取特征，则特征提取 算法比较复杂而不需要二值化、细化等处理。 图1 4 自动指纹识别系统 下面对图1 4 所示自动指纹识别系统的各个部分做简单介绍，s “。 ( 1 ) 图像输入 传统的指纹采集方法是用手指蘸上墨水或印油在纸上按压，然后用扫描仪摄 取。由于其严重的不可靠性，该方法己经被淘汰。随着光学仪器、传感器及数字 技术的发展，各种快速、精确、方便、小巧的采集设备得到应用。目前，主要是 使用光学扫描仪和固态阵列传感器进行采集。前者用激光照在手指上，然后用c c d 阵列摄取其反射光，由于反射光强度随着指纹脊和谷的深度不同而不同，因此可 以得到指纹图像。后者是用大量敏感元件组成的固态阵列芯片，它们采用电容传 5 感、热敏传感或其他传感技术，通过感受按压指纹的压力、热度等特征来摄取指 纹。近年来，又出现了其它一些新型的指纹采集设备，如超声波指纹采集器，它 是基于指纹的脊和谷的深度对超声波的不同反射原理而工作的。这些设备中，光 学扫描仪因其技术比较成熟、性价比比较高而得到广泛应用。 ( 2 ) 预处理 经指纹扫描器采集的原始指纹图像不可避免地具有对比度不统一、含有大量 噪声等缺点，为了降低后续特征提取算法的复杂度、提高特征提取的效率，预处 理过程必不可少。 根据特征提取方法的不同，系统对预处理的步骤和要求也不一样。目前，从 大的方面分，主要有两类特征提取方法：一类直接从原始指纹图像中提取统计性 特征；一类从预处理得到的指纹骨架图像中提取细节点特征。前一类方法对预处 理要求比较少，只要将图像增强一下就可以。后一类方法要求预处理部分做大量 的工作，一般包括图像增强、滤波、二值化、细化等步骤，最后得到一幅纹线宽 度为单像素的二值图像。在当前的应用系统中，后一类方法要比前一类应用得多 一些，因为后一类方法把工作的难点分散到两步操作中，简化了特征提取算法， 且处理结果容易控制。本文采用后一类特征提取方法，预处理过程分为图像增强、 图像分割、二值化及后处理和细化等几个步骤，把原始指纹图像转换为二值细化 图像。 ( 3 ) 特征提取 特征提取负责把指纹图像的纹线走向、纹线断点、交叉点等能够充分表示该 指纹唯一性的特征用数值的形式表达出来。为了比对的准确性，要求特征提取算 法尽可能多地提取有效特征，同时滤除由各种原因造成的虚假特征。从不同的角 度进行观察，指纹图像中存在两类特征：全局特征和局部特征。全局特征指能够 反映指纹整体形状的特征，通常用于指纹的分类，因此提取全局特征的过程往往 归于指纹分类步骤。局部特征指能够反映指纹细节特点的特征，通常用于指纹的 对比。狭义的特征提取指局部特征的提取。两枚指纹经常会具有相同的全局特征， 但它们的局部特征点，却不可能完全相同。 指纹纹线经常出现中断、分叉或打折。这些断点、分支点和转折点就称为“特 征点”，它们提供了指纹唯一性的确认信息。在美国联邦调查局( f b i ) 提出的特 6 征点坐标模型中，只利用了末梢点( e n d i n g ) 与分支点( b i f u r c a t i o n ) 这两种特征 点“1 。另外两种重要的特征点是核心点( c o r e ) 和三角点( d e l t a ) 。核心点一般 位于纹线的渐进中心，三角点一般位于从核心点开始的第一个分支点或末梢点、 或者两条纹路会聚处。并不是所有的指纹都拥有这两个特征，因此常被用作指纹 的子匹配。另外还有分歧点( r j d 辨d i v e r g e n c e ) 、孤立点( d o t ) ，环点( e n c l o s u r e ) 等特征点类型，但不经常被采用。 ( 4 ) 指纹分类 在一些大型的指纹系统中，输入的指纹要与几万、甚至上千万个指纹进行匹 配。为了减少搜索时间、降低计算的复杂性，需要将指纹以一种精确且一致的方 式分配到每个指纹子库中。这样，输入的指纹只需要跟子库中的指纹相匹配就可 以了。本文建立的自动指纹识别系统没有分类操作，因此不作详细讨论。 ( 5 ) 指纹匹配 指纹匹配一般分为两类：认证( 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 ) 。认证是 一对一的匹配，即将待识别指纹与任一指纹进行比对，判断它们是否来自同一个 手指。识别是一对多的匹配，把许多人的指纹特征及个人信息存入数据库，将待 匹配指纹与库中每一个指纹进行比对，找出所有来自同一个手指的指纹。 无论哪种类型的匹配，都是新输入指纹的特征与原来存储指纹的特征进行比 对的过程。由于各种因素的影响，同一指纹两次输入所得的特征模板很可能不同。 因此，当由输入指纹的特征模板与存储的模板相似时，就说这两个指纹是匹配的。 于是就有了一个衡量标准的问题。英国学者e r h e t t y 认为，只要比对1 3 个特征 点重合，就可以确认为是同一个指纹”1 。通常，用两枚指纹的重合点数目是否大 于某个阈值，来判断它们是否为同一个指纹。实际中，该阚值随图像的大小及匹 配算法而不同，比如在算法1 8 中，该阈值设为6 。当闽值设置较大时，系统安 全性增加，但错误拒绝率f r r ( f a l s er e j e c tr a t e ) 将升高。相反，当闽值设置较 小时，系统易用性增加，但错误接受率f a r ( f a l s ea c c e p tr a t e ) 将升高。f r r 和 f a r 是两个相互矛盾的因素，成反比关系。用o 1 0 或百分比来表达这两个数， 它们的关系可以用r o c 曲线( r e c e i v e ro p e r a d n gc u r v e ) 表示。图1 3 是r o c 曲 线的一个例子。在设计实际应用系统时，一方面要考虑整体性能，使r o c 曲线整 体下降：另一方面要兼顾易用性和安全性，在r o c 曲线上寻找合适的平衡点。 7 名 三 盏 q 田iq q l 口1 l l 口 m t l e c l ) 图1 3f r r 和f a r 关系曲线 1 4 研究的目标和内容 本文的研究目标是： 设计一个自动指纹识别系统。系统功能为对于任意一枚指纹，判断在指纹库 中是否存在与其同源的指纹，识别率和识别速度要满足实时系统的要求。 为了完成该目标，在收集和分析近年来国内外有关自动指纹识别技术研究成 果的基础上，主要研究内容为： ( 1 ) 指纹图像预处理。包括归一化、求方向图、求频率图、增强、分割、二 值化及后处理、细化等算法。 ( 2 ) 特征点提取及伪特征点删除。 ( 3 ) 基于校准的指纹匹配。 对于指纹采集和指纹分类不做研究。 8 第二章预处理 2 1 引言 在采集指纹过程中，由于按捺时用力不均匀、扫描器镜片上有污垢等原因， 所得图像的背景区往往含有深浅不均的噪声。同时，指纹扫描器在图像采集以及 数字化的过程中，由于量化精度及非线性形变等的影响，也不可避免地引入噪声。 因此，有必要对指纹图像进行预处理，以去除噪声、增强图像的可识别性。它的 结果将直接影响特征提取和匹配的复杂度，关系到整个系统的识别率。 预处理的目的是使原始灰度图像，经过一系列处理，变为单象素宽的点线图， 这幅点线图尽可能的保持原始图像中的细节特征。目前预处理过程主要包括图像 分割、增强、滤波、二值化、细化等步骤。针对不同的系统，可以选择不同的预 处理步骤进行组合，使其达到最优效果。 通过比较当前广泛使用的预处理算法，本文最终选择并实现了一套较复杂但 效果好的预处理算法，包括指纹图像增强算法、简单分割算法、动态阙值二值化 算法和一种8 邻域最简的细化算法。实验结果表明，这四种算法能够很好地完成 各自的功能，为后续工作顺利进行提供了保障。 2 2 图像增强 指纹图像增强的目的是去除图像中噪声，改善图像的质量，尽可能恢复图像 固有的纹线结构和细节特征。 由于指纹脊和谷的分布，具有明显的方向性，因此常规的图像增强算法不适 合指纹图像。目前，所有的指纹增强算法，都把指纹图像的方向作为重要的参数。 l m h o n g 等提出了基于g a b o r 函数的增强算法幻1 ，首先求指纹方向图，然后由方 向图求频率图，最后用由频率图得到的g a b o r 滤波器对原始图像进行滤波。这种 方法滤波效果好，但计算量比较大。l a w r e n c e g o r m a n 等提出了一种比较复杂的滤 波器“”，根据图像脊和谷的宽度以及其变化规律来滤除指纹图像中的噪声。b m m e h t r e 提出了一种上下文滤波器“”，它是一系列上下文相关的滤波器组，使用时 根据某一块的方向从滤波器组中选择一个相应的滤波器来对这一块进行滤波，该 方法相对简单，计算量小，但对于较低质量指纹图像，效果不是很好。 9 文中采用的是g a b o r 滤波器对原始指纹图像进行增强b 1 。 下面的讨论针对灰度指纹图像。对一幅给定的指纹图像，将感兴趣的区域分 为以下三类( 图2 1 ) ： ( 1 ) 良好区域：该区域的纹线结构比较清晰，特征提取算法可以直接准确的 提取出特征信息； ( 2 ) 可恢复区域：该区域的纹线结构被一小部分皱痕、污点等噪声破坏，但 相邻区域可以提供恢复其真正纹线结构的充足信息； ( 3 ) 不可恢复区域：该区域的纹线结构已经被彻底破坏，以致于脊线与谷线 结构无法辩认，相邻区域也不能提供恢复该区域真正纹线结构的充足信息。 将良好区域和可恢复区域统称为有效区域，而不可恢复区域则称为无效区域。 显然，在无效区域中，纹线结构已经遭到彻底破坏，要正确恢复其纹线结构是不 可能的。因此，该指纹增加算法的目标是尽量提高指纹图像在有效区域的纹线结 构的清晰度，同时屏蔽掉无效区域。以减少区域对特征提取算法的影响。 良好区域可恢复区域不可恢复区域 图2 - 1 2 2 1 几点说明 ( 1 ) 输入的原始灰度指纹图像，定义为：+ 矩阵，( f ，j ) 表示第所i 、第 ，列象素的灰度值。假定所输入的指纹图像是2 5 6 阶灰度图像，则该指纹图像，灰 度平均值m ( i ) 和方差v a r ( i ) 分别定义如下： m ( ，) = 丽1 埘，) ( 2 1 ) j = 0j = o 1 0 v a r ( ，) = 嘉善n - i 丢n - 1 ( 砸舶一m ( f ，脚2 ( 2 2 ) ( 2 ) 方向场图0 定义为：矿+ 矿矩阵，o ( i ，j ) 表示第i 行，第，列块的方向。 实验中，块的大小取为：1 7 x 1 7 ，因而有w = n 1 7 。在一块之内求取一个唯一的 局部纹线方向，它代表了该块内所有象素点的大致走向，用来表征该块内象素点 的方面信息。 ( 3 ) 频率图f 定义为：+ 矩阵，其划分方法与方向场图一样，其中f ( i ，j ) 代表第i 行、第列块的局部纹线频率。局部纹线频率定义为脊线和谷线在一个局 部领域内沿着垂直于该局部纹线方向的频率。如果在一个局部领域内，脊线和谷 线的结构并不能形成一个规则的正波形状的曲线，该区域的频率定义为它的邻域 频率的平均值。 4 ) 区域模板图r 定义为：w w 矩阵，与方向场图和频率图的划分一样，区 域模板图也被划分为大小相等的块，其中r ( i ，) 代表第i 行，第j 列块的种类，其 中0 代表无效区域( 不可恢复区域；) 1 代表有效区域( 良好区域和可恢复区域) 。 2 2 2 归一化 与直接从原始图像提取方向信息不同，首先对原始指纹图像进行归一化，再 在归2 化后的图像算出方向场图0 、频率图，以及区域模板图r ，最后对归一化 后的指纹图像用一组调节局部纹线方向和纹线频率的g a b o z 滤波器，以获得一个 增强的指纹图像。 ，( f ，) 表示象素点( f j ) 处的灰度值，m 和v a r 分别表示平均值和方差，假定 g ( i ，j ) 表示归一化后象素( f ) 处的灰度值，则归一化后的灰度指纹图像可以表示 为： g ( i ，) = 里v a r o x ( i ( i , j ) - m ) 2 砸 。吲 m 。一v a r 。x ( i ( i , j ) - m ) 2 一，( f ，) t d ，则块( f ，) 为指纹图像区域， f l a g ( i ，j ) = 1 ；否则，为背景图像块，f l a g ( i ，j ) = 0 。 ( 6 ) 进行基于块水平的平滑，消除孤立前景块。若一块被标记为前景块，且 其四周相邻的块中前景块数目不超过2 ，则将该块区域置为背景块，即 f l a g ( i ，) = 0 。 实验证明，只要闽值t d ，选择的合适，该方法能稳定、可靠地从背景区域中 分离出指纹图像。实验中t d 为所有分块方差值平均值的1 3 。 2 4 二值化及后处理 2 4 1 二值化 二值化的目的是把灰度指纹图像变成0 - - - 1 取值的二值图。这样做的好处是： 对图像作进一步处理时，图像的几何性质只与0 和1 的位置有关，不再涉及到像 素的灰度值，使处理变得简单，而且数据的压缩量很大。例如，一幅3 0 0 x 3 0 0 x g b i t 2 0 )力o 孵4 一 力 m 嘶 g “c l = 力o 足蹦 的灰度图像，二值化以后的数据量只有3 0 0 x3 0 0 1 b i t ，这给存储和处理都带来了 很大的方便，同时也提高了系统的经济实用性。 图像二值化“明“4 1 的具体办法是：通过设定阈值，把灰度图像变换成仅用两个 值来分别表示的图像目标和图像背景的二值图，其中目标取值为1 ，背景取值为0 。 在实际的位图( b i t m a p ) 中，0 对应于r g b 值均为白色( 2 5 5 ，2 5 5 ，2 5 5 ) ，1 对应于r g b 值均为黑色( o ，0 ，o ) 。 二值化图像的方法很多，闽值的选择是二值化图像的关键。本文采用了动态 阈值二值化方法。算法的核心思想是：对每块图像，选取的闽值应尽量使该块图 像内的大于该闽值的象素点数和小于该阈值的象素点数相等，而这一思想和指纹 图像脊线、谷线间隔均匀出现的特征正好可以吻合。具体算法如下“2 “1 ： ( 1 ) 将指纹图像划分为不重叠的大小为w w 的块，实验中w = 1 7 ； ( 2 ) 对每一块进行如下处理： a ：求平均灰度值t ； b ：n h = 灰度值大于等于t 的象素点个数： n t = 灰度值小于t 的象素点个数； c ：如果i 一f i a口= ( 矿矿1 0 ) ，则t 为阈值。 如果m m ，t = t + 1 ； n h n ”t = t 一1 ； ( 3 ) 平滑处理。这种以区域间二值化为基础的二值化算法应用于指纹图像 时，也有一定问题，主要是区域间的闽值可能变化幅度较大，这就会造成部分指 纹图像的丢失。因此使用了平滑算法对子区间的阈值进行平滑处理。 具体做法：先将所得块阈值分配到一个二维阈值数组中，每一个像素对应一 个阈值，然后按从左到右从上到下的顺序，使用3 x 3 算术平均模板对整个阙值数 组进行一次滤波，再将所得的闽值与指纹灰度值相比较来进行二值化。灰度值大 于t ，则置0 ，小于等于t ，则置1 。 实验表明，这种以区域灰度幅度为函数的平滑自适应阈值法，完全适合用于 对指纹图像进行二值化处理。 2 1 2 4 2 二值化后处理 由于灰度去噪声的不完全性及二值化时有可能引入的噪音，所以对二值化后 的指纹图像还需进行一次去噪声操作，目的是去除或减弱图像中的噪音，增强图 像中有意义的部分。 在指纹图像处理中，由于指纹图像二值化后，在指纹的纹线上仍然存在着或 多或少、大大小小的孔洞，并且纹线边缘并不光滑，即有不少的缺口和突出物。 如果直接对其进行细化，则这些缺口、突出物就会使细化的纹线变得参差不平， 并出现些短小的分叉，即毛刺；同时，处于纹线上的孔洞，在保持连通性的细 化处理过程中将被扩大，形成一些圆圈和网状线。这不仅使指纹细化图变得杂乱， 而且在特征提取时，将得到许多的伪特征点，从而影响以后的识别，因此，在细 化之前对二值图进行了修补。 指纹的端点和分支点是二类重要的特征，但由于按捺时用力不均或指纹采集 仪的缺陷或按压时油墨不匀，就会产生一些假的端点或分支点，比如当手指上有 一个没沾上油墨的凹沟时，可能会产生图2 2 ( c ) 的假端点，当某条纹线中有一 个小洞时，细化后则可能产生图2 2 ( d ) 的假分支点。 my ( b ) 真分夏点 & 弓 ( d ) 但分叉点 图2 8 两种典型特征的伪特征点 在提取特征之前，应该尽量去除二值图中的噪声。二值化后的去噪处理有多 种办法，有的使用带方向的快速付氏变换来进行去噪“7 1 ，也有使用方向加权中值 滤波的办法来进行去噪“”。有关的算法很多，但都只能消除部分或某一类的噪声， 具体应采用哪些算法无统一标准，由于已经用g a b o r 对指纹进行处理，因此文中 采用几个快速去噪声算法“”。 ( 1 ) 对于填补纹线中的小洞，选用了如图2 9 所示模板：其中值为1 的点 表示纹线上的点，0 值为背景，没有注明数值，表示该点的值不确定。在二值图中 遍历搜索所有满足以上模板的点，将其置1 。 图2 9 需要修饰的空洞模板 ( 2 ) 对二值图中模糊区域进行清晰化，对图像中坐标为( x ，y ) 的像素点作 以下处理：若坐标为( x 一1 , y - 1 ) ，( x ，y 一1 ) ， x + l ，y 一1 ) ，( x l ，y + 1 ) ，( x ，y + 1 ) ，( x + 1 ，y + 1 ) 的点的值都是1 ，或者坐标为( x - i ，y - 1 ) ，( x l y ) ，( x 一1 ，y + 1 ) ，( x + l y - 1 ) ，( x + 1 ，y ) ， ( x + b + 1 ) 的点都是1 ，则将( x ，y ) 点置为1 ；否则若( x y ) 的8 个邻接点中均为 0 ，则( ( x ，v ) 的值置为0 ( 3 ) 去除毛刺：扫描整个图像，搜索满足如图2 1 0 所示的模板的条件的像素 点，然后按照少数服从多数的原则，将满足模板的点的值反相( 即将为0 的置1 ， 而为1 的置0 。 图2 1 0 需要修饰的毛刺模板 2 3 前背景分割及二值化处理结果如图2 1 1 所示 图2 1 1 前背景分割、二值化及后处理结果 2 5 细化 指纹图像的纹线具有一定宽度，这对于特征提取来说是冗余信息，而且会增 加特征提取的难度，因为特征提取只对纹线的走向感兴趣，而不关心它的粗细。 为了进一步压缩数据，简化特征提取操作，需要对指纹图像进行细化处理。 指纹图像的细化是指删除纹线的边缘像素，使之只有一个像素宽度。一种好 的细化方法应满足下列条件呦1 ：( 1 ) 收敛性：迭代必须收敛的；( 2 ) 连接性： 不破坏纹线的连接关系；( 3 ) 拓扑性：不引起纹线的逐步吞食；( 4 ) 保持性： 保护指纹的细节特征；( 5 ) 细化性：骨架纹线的宽度为1 个像素；( 6 ) 中轴性： 骨架尽可能接近条纹中心线；( 7 ) 快速性：算法简单、速度快。 目前图像细化算法的种类很多，代表性的算法有h i l d t c h 法、e i s i d e u t s c h 法 等。但这些经典的细化算法用于指纹纹线细化处理时，往往会引起较明显的纹线 吞食现象或骨架位置发生偏移等问题，并不能达到满意的效果。o p t a 算法是一 种典型的模板匹配细化算法匕”。一种新的指纹图像细化算法对o p t a 算法的消除 模板和保留模板进行改造b ，不仅改善了细化效果，提高了处理速度，而且易于 进行并行操作。 本文采用一种8 邻域最简的细化算法b 1 。所谓8 邻域最简是指在满足上述 基本条件的同时，使每一个保留下来的像素点的8 邻域组合最为简单。图2 1 2 所 示为细化的两个实例。在通常的细化算法中，图( a ) 中的a 点和图( c ) 中的b 2 4 点将会被保留下来，而在该细化算法中，它们将会被删除掉，效果分别如图( b ) 和图( d ) 所示。显然，所保留下来的像素的8 邻域组合更简单了，同时保证了细 化的其它要求。这样处理的好处将在下一章所介绍的8 邻域编码纹线跟踪算法中 体现出来，它简化了8 邻域组合，使跟踪算法更加简单、快捷。 蛋岛昏圈日圈 ( a )( b )( c ) ( d ， 图2 1 2 细化实例 该细化算法根据二值图像中每一点的八个相邻点的情况来判断该点是否能删 除。具体讲，是否删除的判据如下：( 1 ) 内部点不能删除；( 2 ) 孤立点不能删 除；( 3 ) 直线端点不能删除；( 4 ) 如果点p 是边界点，去掉p 后，如果连通分 量不增加，则p 可以删除。图2 5 给出了几种8 邻域组合情况，我们来判断它们的 中心点是否应该删除。其中( a ) 不能删，因为它是个内部点，我们要求的是骨架， 如果连内部点也删了，骨架也会被掏空的；( b ) 不能删，和( a ) 是同样的道理： ( c ) 可以删，这样的点不是骨架：( d ) 不能删，因为删掉后，原来相连的部分 断开了：( e ) 可以删，这样的点不是骨架：( f ) 不能删，因为它是直线的端点， 如果这样的点删了，那么最后整个直线也被删了；( 2 ) 不能删，因为孤立点的骨 架就是它自身。 田围圈圈酗田 a )( b )( )( d )( o )r f )( g ) 图2 1 3 细化判据实例 该细化算法的步骤如下： ( 1 ) 按顺序对8 邻域组合进行编码，则2 5 6 种组合将与数值0 到2 5 5 一一对 应； ( 2 ) 根据上述判据制作一张消除表，实际上是一个容量为2 5 6 的数组，下标 分别与8 邻域组合的编码一一对应，元素值设为0 表示该组合的中心点应该保留， 设为1 则表示应该删除： ( 3 ) 从上到下，从左到右，对二值图像进行扫描，对每一个黑点做如下处理： 先判断该黑点的左右邻居，如果都是黑点，则该点不做处理：否则计算8 邻域编 码作为索引，查消除表看是否删除：如果该黑点被删除了，那么跳过它的右邻居， 处理下一个点； ( 4 ) 从左到右，从上到下，对二值图像进行第二次扫描，对每一个黑点做类 似处理：先判断该黑点的上下邻居，如果都是黑点，则该点不做处理；否则计算 8 邻域编码作为索引，查消除表看是否删除：如果该黑点被删除了，那么跳过它的 下邻居，处理下一个点： ( 5 ) 如果本次循环有黑点被删除，则跳到( 3 ) ，否则，终止循环，细化结 束。 图2 1 4 图像细化后结果 2 6 第三章特征点提取 3 1 引言 指纹特征提取的目的是要获得真正的细节特征，同时去除由噪声或污染等因 素所造成的伪细节特征。 特征点的提取一般是从细化后的指纹点线图来提取，这样做可以得到指纹的 细节特征的位置、类型和方向。也曾有人提出过在灰度图像上利用纹线跟踪直接 获取特征点，比如文献b ”，但是后者的提取速度和效果明显不如前者。 在大型自动指纹识别系统f a f i s ) 中，为了加快指纹数据库的检索速度往往要根 据指纹的总体特征把样本分为若干个种类( 4 - 8 类) ，输入的指纹先根据总体特征判 断其类别，再在所属指纹类型中利用细节特征进行比对，找出样本库中与之相对 应的指纹。而在指纹验证系统中，由于样本数量小，一般不大于1 0 0 个，所以可 以直接从指纹图像中抽取细节特征，然后利用指纹匹配算法对指纹进行验证。 指纹的特征是指纹识别的技术基础，由于本论文没有研究指纹的分类技术， 所以仅限于研究通过指纹的细化图来提取细节特征的算法。 3 2 特征点的提取 指纹的细节特征是在预处理中得到的细化图上提取的，而所有的指纹细节特 征中，