（电路与系统专业论文）指纹识别算法的研究及基于dsp的实现.pdf

中文摘要 摘要：指纹识别技术以生物特征为基础，以信息处理技术为手段，将生物技术和 信息技术有机结合在一起，在所有包含身份认证的领域均有着广阔的应用前景。 尽管指纹识别的理论研究与应用开发取得了重大进展，但指纹识别算法的准确性 和识别速度仍有待提高，构建准确可靠、安全实用的自动指纹识别系统己成为研 究热点。 本文对指纹识别算法和硬件平台实现两方面展开了较为深入的分析与研究， 提出了指纹识别算法的优化方法，并在此基础上设计合理的d s p ( d i g i t a ls i n g l e p r o c e s s i n g ) 硬件解决方案。本文的主要目的是将指纹识别技术应用于身份认证领 域，促进指纹识别技术在实际应用中的发展。论文的主要研究工作如下： 1 研究分析了国内外自动指纹识别技术应用及发展现状。重点研究了指纹识 别算法的指纹图像预处理、指纹特征提取和指纹图像匹配三个阶段，比较分析了 现有算法的优缺点。 2 分析及优化了指纹识别算法中的重要环节。在指纹图像特征提取阶段，为 迸一步简化图像，提出将经典细化后的图像与8 连通模板比较的方法，实现了图 像的进一步简化，减少了跟踪过程的难度。在细节点匹配阶段，通过对指纹图像 进行分类，对基于三角形全等的指纹细节点匹配的算法进行了优化，减少了匹配 过程的计算量。 3 设计了一个基于d s p 的便携式指纹识别系统硬件平台。指纹识别系统硬件 平台设计包括：以d s p 芯片t m s 3 2 0 v c 5 4 1 6 和指纹传感芯片m b f 2 0 0 为核心，外 配片外s r a m 和f l a s h 存储器以及l c d 显示屏等的自动指纹识别系统，对各模 块进行合理的组合与设计。 通过对指纹识别系统的研究，提出了指纹图像预处理及匹配算法的优化，仿 真实验结果表明，本文提出的优化算法是可行的。设计了一种具有通用性的基于 d s p 应用的指纹识别系统，作为该指纹识别算法的应用平台，可有效促进指纹识 别技术的应用和普及。 关键词：指纹特征；预处理；细节点提取；特征匹配；d s p 分类号：t p 3 0 1 6 ：t p 3 9 1 4 a bs t r a c t a b s t r a c t ：f i n g e r p r i n ti d e n t i f i c a t i o nt e c h n o l o g yb a s e do nb i o l o g i c a lc h a r a c t e r i s t i c s ， w i t hi n f o r m a t i o np r o c e s s i n gt e c h n o l o g y a sam e a n s ，c o m b i n e sb i o t e c h n o l o g ya n d i n f o m a t i o n i th a sw i d ea p p l i c a t i o np r o s p e c t i na l lf i e l d sw h i c hc o n t a i ni d e n t i t y a u t h e n t i c a t i o n a l t h o u g ht h e o r e t i c a lr e s e a r c ha n da p p l i c a t i o nd e v e l o p m e n t o fi th a v eg o t as i g n i f i c a n tp r o g r e s s ，a c c u r a c yo ft h ea l g o r i t h ma n dp r o c e s s i n gs p e e d s t i l ln e e dt ob e i m p r o v e d c o n s t r u c t i o n o fa c c u r a t ea n dr e l i a b l e ，s a f ea n dp r a c t i c a la u t o m a t l cf i n g e r p n n t i d e n t i f i c a t i o ns y s t e m ( a f i s ) h a sb e c o m ea r e s e a r c hh o t s p o t i n t h i sp a p e r , f i n g e r p r i n ti d e n t i f i c a t i o na n dh a r d w a r ed e s i g n a r ea n a l y z e da n d d i s c u s s e di nd e t a i l ，p u t t i n gf o r w o r dt h eo p t i m i z e da l g o r i t h ma n d h a r d w a r ed e s i g nb a s e d o nd s p t h em a i np u r p o s eo ft h i ss t u d yi s t ou s et h ef i n g e r p r i n t i d e n t i f i c a t i o n t e c h n 0 1 0 9 yf o ri d e n t i t ya u t h e n t i c a t i o n ，o p t i m i z ef i n g e r p r i n ti d e n t i f i c a t i o na l g o r i t h m ，a n d p u tf - o 州砌ad s p s c h e m e t h i sp a p e ri sm a d eu po ft h ef o l l o w i n gp a r t s ： 1 t h ed o m e s t i ca n do v e r s e a sa c t u a l i t yo ff i n g e r p r i n ti d e n t i f i c a t i o nt e c h n o l o g ya r e i c s e a r c h e da n da n a l y z e d f i n g e r p r i n ti m a g ep r e t r e a t m e n t ，m i n u t i a e e x t r a c t i o na n d f i n g e r p r i n tm a t c h i n gi sr e s e r a r c h e d w i t he m p h a s i s 2 t h em a i np h a s e so ff i n g e r p r i n ti d e n t i f i c a t i o na l g o r i t h ma r ei m p r o v e d a n d o p t i m i z e d 1 1 1t h ep r o c e s s o fm i n u t i a ee x t r a c t i o n ，c l a s s i c a lt h i n n i n gt m a g e s a n d 8 - c o n n e c t e dt e m p l a t e sa r ec o m p l a r e dt o r e d u c et h ed i f f i c u l t yo ft r a c k i n g i n t h e p r o c e s s i n go fi m a g em a t c h i n g ，t h ei m g e i sa s s o r t e db e f o r et h et r i a n g l e - b a s e df i n g e r p r i n t m i n u t i a em a t c h i n ga l g o r i t h m ，r e d u c i n gt h e c a l c u l a t i o ng r e a t l y 3 t h eh a r d w a r ed e s i g no ff i n g e r p r i n ti d e n t i f i c a t i o ni n t r o d u c t i o n i su s m gd i g i t a l s i g n a lp r o c e s s i n gt m s 3 2 0 v c 5 4 16a n df i n g e r p r i n ts e n s o rm b f 2 0 0a si t sm a i nc h l p s ， w i t ht h ec o o p e r a t i o no fs r a mm e m o r y , f l a s hm e m o r y , l c da n d s oo n t h i sr e s e a r c hp r o j e c th a sd o n ea no p t i m i z e dr e s e a r c ho 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 l g o r i t h ma n dp r o v i d e dad s p a p p l i c a t i o n b a s e df i n g e r p r i n tp r o c e s sm o d u l eo f g e n e r a i t y p ea sa na p p l i c a t i o np l a t f o r mf o rf i n g e r p r i n ti d e n t i f i c a t i o na l g o r i t h m s i m u l a t i o nh a s p r o v e dt h a to p t i m i z e da l g o r i t h mp r e s e n t e db yt h i sp a p e r i sp r a c t i c a b l e t h i sr e s e a r c h p r o j e c t i o nc a np r o m o t e t h ea p p l i c a t i o na n dp o p u l a r i z a t i o no ft h i st e c h n o l o g y k e y w o r d s ：f i n g e r p r i n tc h a r a c t e r i s t i c ；p r e t r e a t m e n t ；m i n u t i a e e x t r a c t i o n ；m i n u t l a e m a t c h i n g ；d i g i t a ls i n g l ep r o c e s s i n g c 1 a s s n o ：t p 3 0 1 6 ：t p 3 9 1 4 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：麟岬 签字日期：扣牌孑月1 2 - 日 导师签名： 签字日期：歹伪分年6 月，z 伺 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名： 签字日期：年月同 致谢 本论文的工作是在我的导师侯建军教授的悉心指导下完成的，侯建军教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两年来 侯建军老师对我的关心和指导。 感谢曾经给我讲授课程的陈后金教授、刘颖教授、戴胜华副教授、杜普选副 教授，他们对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷心的 感谢。 在实验室工作及撰写论文期间，李赵红师姐、牛永琴师姐等对我论文中的软、 硬件设计及研究工作给予了热情帮助，在此向她们表达我的感激之情。 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业。 1 。1 生物识别技术概述 1 引言 生物识别技术就是通过计算机与光学、声学、生物传感器和生物统计学原理 等高科技手段密切结合，利用人体固有的生理特性，如指纹、脸像、红膜等，和 行为特征，如笔迹、声音、步态等来进行个人身份的签定。电子生物识别可以通 过计算机与光学、声学、生物传感器和生物统计学原理等高科技手段密切结合， 实时采集生物体的特征并实时做出判断，彻底改变了以往靠人眼辨识的状态。电 子生物识别技术已经成为身份识别领域的后起之秀川。 传统的身份鉴定方法包括身份识别物品，如钥匙、证件、a t m 卡等，和身份 标识知识，如用户名和密码，但由于主要借助体外物，一旦证明身份的标识物品 和标识知识被盗或遗忘，其身份就容易被他人冒充或取代。我们的需要在于机器 之间交互和交易是安全方便的。也即，我们需要简单快速的使用机器而不用担心 不安全的问题。原有的智能卡、身份号和口令的系统却只能在安全与方便之间徘 徊，充分的安全从来没有实现过，而对于更好的安全却与不方便同时出现。为了 实现较高的安全性，我们必须使用更复杂和更不方便的口令。生物特征识别技术 具不易遗忘、防伪性能好、不易伪造或被盗、随身“携带”和随时随地可用等优 点。比传统的身份鉴定方法更具安全、保密和方便性。将有效的解决上述传统安 全措施所不能克服的困难。 生物识别技术可广泛用于政府、军队、银行社会福利保障、电子商务、安 全防务。因此基于生物识别技术的身份验证发展极其迅速。i b g ( i n t e r n a t i o n a l b i o m e t r i cg r o u p ) 国际生物识别集团，是生物识别行业领先的咨询和技术服务公司。 i b g 发布了2 0 0 7 2 0 1 2 年度全球生物识别市场报告，如图1 1 所示，2 0 0 7 年超过 3 0 亿美元，2 0 0 8 年达到3 8 亿美元，到2 0 1 2 年将超过7 4 亿美元，比2 0 0 7 年翻一 倍以上。 基于生物特征的身份鉴别技术的研究伴随着这一应用的发展越来越深入，逐 渐自成系统。能够用来鉴别身份的生物特征应该具有以下特剧2 】： 广泛性：每个人都应该具有这种特征； 唯一性：每个人拥有的特征应该各不相同； 稳定性：所选择的特征应该不随时间变化而发生变化； 可采集性：所选择的特征应该便于测量。 实际的应用还给基于生物特征的身份鉴别系统提出了更多的要求，如：性能 要求，所选择的生物统计特征能够达到多高的识别率；对于资源的要求，识别的 效率如何；可接受性，使用者在多大程度上愿意接受；安全性能，系统是否能够 防止被攻击；是否具有相关的、可信的研究背景作为技术支持；提取的特征容量、 特征模板是否占用较小的存储空间；价格是否为用户所接受：是否具有较高的注 册和识别速度；是否具有非侵犯性。迄今为止，还没有哪一个单项的生物特征能 达到完美无缺的要求【3 】。每种生物识别技术都有各自的优缺点。表1 1 给出了几种 生物特征的参数比较。 8 0 0 0 7 0 0 0 6 0 0 0 5 0 0 0 4 0 0 0 3 0 0 0 2 0 0 0 1 0 0 0 0 a n n u a lb i o m e t r i ci n d u s t r yr e n e n u e s ，2 0 0 7 2 0 1 2 2 y 2 z 2 w 其他方向的滤波器采用如下公式计算。 n 2 n 2 + 隹竺 n 2 n 2 ( 3 1 1 ) ( 3 1 2 ) i ，j = 0 n - 1( 3 1 3 ) 其中，q 为旋转角度，( i ，j ) 为水平滤波器的行列坐标，( i ，j ) 为旋转后的滤波 器的行列坐标，n 为滤波器的阶数。由于在新滤波器中( i ：j i ) 的系数与水平方向的 滤波器( i ，j ) 位置的系数相等，即：( i ，j - ) = f ( i ，j ) 。 一般情况下，利用( 3 1 1 ) 计算的对应于( i t ，j ) 的值( i ，j ) ，不为整数，所以也就 在水平滤波器中无法找到对应的系数值，在这种情况下，我们只有通过( i ，j ) 周边 点，利用线性插值的方法求得( i ，j ) 的系数值，即f ( i ，j ) ，也就是f i i ，j ) 。 如图3 3 所示，在( i ，j ) 不为整数情况下，设a ( i o ，j o ) 、b ( i l ，j o ) 、c ( i o ，j 1 ) 、 d ( i t ，j 1 ) 为( i ，j ) 附近的整数点。 利用a 和b 的插值，可以得到e 的系数。 f ( i ，j 。) 2f ( i o ，j 。) + ( f ( i ，j o ) 一f ( i o ，j 。) ) x ( i - i o ) ( i i i o )( 3 1 4 ) 利用c 和d 的插值，可以得到f 的系数。 w z y x y z w w z y x y z w w z y x y z w w z y x y z w w z y x y z w w z y x y z w w z y x y z w f 【i ，j i ) = f 【i 。，j 1 ) + ( f 【i 。，j 。) - f 【i 。，j 。) ) ( i i o ) ( i 。- i 。)( 3 1 5 ) 利用e 和f 的插值，可以得到( i ，j ) 的系数。 f i i ，j ) = f ( i ，j 。) + ( f 【i ，j 。) f ( i ，j 。) ) ( j j 。) 0 一j 。)( 3 1 6 ) 利用公式( 3 - 1 1 ) 、( 3 - 1 2 ) 和( 3 - 1 3 ) 可求得( i t j i ) 。这样，就求出8 个方向的方向 滤波器。 y 。 f ( 0j i ) c ( i o ，j oo p o d ( i , ， ，i i - - a ( i o ，j o ) obob ( i i ， e i ( i ，j o )。 图3 3 插值示意图 f i g u r e 3 - 3i n t e r p o l a t i o ns k e t c hm a p 这样，我们就可以跟据每个像素的方向，采用相应的方向滤波器对指纹图像 进行操作。在公式( 3 一1 7 ) 中p o 代表平滑操作前的指纹灰度图像，p i 代表平滑后的 指纹图像。 n n 吣y ) = 窆圭p 。( x + i ，y + j ) f ( i + i n ，j + 掣) ( 3 - 1 7 ) 1 “i 2 i 3 1 3指纹图像二值化 二值化是图像预处理中非常重要的一步，所谓二值化就是通过设定阈值，将 图像转换为仅用两个狄度值表示的二值图像。对指纹图像进行二值化处理不但对 图像信息进行了压缩，保留了纹线的主要信息，解决了存储空间问题，更重要的 是进一步修复了断裂的纹线，去除了粘连现象，图像得到了进一步的增强。一般 采用阈值法对图像进行二值化，阈值法又分为固定阈值和浮动阈值，很明显，由 于不同图像的狄度差异变化很大，甚至同一幅图像中各部分的明暗也大不相同， 所以固定阈值的方法并不可取。浮动阈值的方法，是根据图像中每一块的明暗度 来调整阈值，块内大于阈值的像素被置为1 ，小于阈值的像素被指为0 。在实际的 位图( b i t m a p ) 中，o 对应于r g b 值均为白色( 2 5 5 ，2 5 5 ，2 5 5 ) ，1 对应于r g b 值 均为黑色( o ，0 ，0 ) 。 本文采用了一种浮动阈值二值化算法，在二值化的同时，结合方向信息将背 景从指纹图像中分离出来，在二值化后，又进行了次滤波去噪，通过实验，这 种算法取得了良好的效果，为细化和指纹特征的提取打下了良好的基础。算法的 核心思想是：对每块图像，选取的阈值应尽量使该块图像内的大于该阈值的像素 点数和小于该闽值的像素点数相等，而这一思想和指纹图像脊线、谷线间隔均匀 出现的特征正好可以吻合。具体算法如下： 1 将指纹图像划分为不重叠的大小为w x w 的块，w 的取值与图像的分辨率 有关，富士通公司f p s 2 0 0 指纹传感器的分辨率为5 0 0 d p i ( 点每英寸) ，w = 1 6 就能 得到最佳的效果。 2 对每一块进行如下处理： ( 1 ) 求平均灰度值m ； ( 2 ) n 。= 灰度值大于等于m 的像素点个数，n 。= 狄度值小于m 的像素点个 数； ( 3 ) 如果 n h - n 。l r i ，r l = ( w xw x l 0 ) ，则r l 为阂值，如果n h n 。，r i = 1 1 + 1 ； 如果n h n t ，r l = r l - l ； 3 平滑处理。这种以区域问二值化为基础的二值化算法应用于指纹图像时， 也有一定问题，主要是区域问的阈值可能变化幅度较大，这就会造成部分指纹图 像的丢失。因此使用了平滑算法对子区问的阈值进行平滑处理。具体做法：先将 所得块阈值分配到一个二维阈值数组中，每一个像素对应一个阈值，然后按从左 到右从上到下的顺序，使用3 3 算术平均模板对整个阈值数组进行一次滤波，再 将所得的闽值与指纹灰度值相比较来进行二值化。灰度值大于1 1 ，则置0 ，小于等 于t 1 ，则置l 。实验表明，这种以区域灰度幅度为函数的平滑自适应阈值法，完全 适合用于对指纹图像进行二值化处理。图3 4 是指纹图像二值化前后对比效果图。 ( a ) 二值化前指纹图像( b ) 二值化聒指纹幽像 图3 _ 4 二值化前后图像对比 f i g u r e 3 - 4c o m p a r ei m a g e sa f t e rb i n a r y z a t i o n 2 3 3 1 4指纹图像细化 指纹图像二值化后，其纹线仍具有一定宽度，而指纹识别只对纹线的走向感 兴趣，不关心它的粗细。为了以后特征提取方便，需要对其进行细化处理。细化 就是将二值图像变化为单像素宽度的骨架图像。细化可去掉大量的冗余信息，同 时又能保留指纹的拓扑联结关系，以便于后面的特征提取。图像细化算法的种类 很多。代表性的有h i l d t c h 、d e u t s c h 等方法，细化的方法不同，细化的结构就有差 异。指纹自动识别系统中的纹线细化应满足下列条件：收敛性，迭代必须是收敛 的；连接性，不破坏纹线的连接性；拓扑性，不引起纹线的逐步吞食；保持性， 保护指纹的细节特征；细化性，骨架纹线的宽度为1 个像素；中轴性，骨架尽可 能接近条纹中心线；快速性，算法简单、速度快。 经典细化算法将骨架像素定义为与图3 5 模式( 包括这些模式的9 0 度、1 8 0 度、 2 7 0 度) 相一致的那些像素。图中用a 或b 标记的每个像素群中，至少有一个像 素必须为非零。一个像素集p 的骨架是按下述步骤求出的集。首先确定骨架像素 和p 的轮廓像素，然后移去不是骨架的轮廓像素，并且重复这个过程，直至剩下 仅出骨架像素所组成的集为止。理论上依次考察途中每个像素，若满足条件，则 标记为骨架像素，否则为非骨架像素，如果一个像素在一次迭代期间被标记为骨 架像素，那么以后就不能删除它。 a a a opo bbb aaa ap0 a01 图3 - 5 骨架像素模式 f i g u r e 3 - 5f r a m e w o r kp i x e lm o d e 在细化处理过程中，根据指纹图像本身特有性质，在原有的经典细化算法的 模板上加上指纹分叉点和端点的信息，即对点( x ，y ) ，判断其4 邻域点是否满足下 列方程，若成立，保留相应邻点，否则予以删除。则其条件表达式为： k 。= p 3 + p 5 ( 1 一a o + p 1 ) ( 1 p 6 + p 7 ) ( 1 - p 5 + p 2 + p l + p 7 + p 8 ) ( 3 一p 5 p 3 一p 7 + p 6 + p 8 ) = 0 ( 3 1 8 ) k r = p 5 + p 3 ( 1 一p 2 + p o ) ( 1 - p 8 + p 7 ) 0 一b + p o + p i + p 7 + p 6 ) ( 3 - p 3 一e - p 7 + p o + p 6 ) 20 ( 3 - 1 9 ) k u = p i + p 7 ( 1 一p o + p 3 ) ( 1 p 2 + p s ) ( 1 一p 7 + p 3 + p 5 + p 6 + p s ) ( 3 一p 5 - p l - p 7 + p 2 + p 8 ) 20 ( 3 2 0 ) k d = p 7 + p l ( 1 一p 6 + p 3 ) ( 1 - p 8 + p 5 ) ( 1 - p l + p 2 + p o + p 3 + p 5 ) ( 3 p5 - p i - p 3 + p 2 + p o ) 20 ( 3 - 2 1 ) k l 、k r 、k u 、k d 分别对应左右上下邻点，其中：p o = f ( x - 1 ，y - 1 ) ，p i = f i x 1 ， y ) ，p 2 = f ( x l ，y + 1 ) ，p 3 = f ( x ，y - 1 ) ，p 4 = f ( x ，y ) ，p 5 2 f ( x ，y + 1 ) ，p 6 = f ( x + l ，y - 1 ) ，p 7 = f ( x + l ， y )，p s = f ( x + l ，y + 1 ) 。细化结果如图3 - 6 。 图3 - 6 细化结果 f i g u r e 3 6t h i n n i n gr e s u l t 3 2 指纹特征提取算法的改进 指纹特征提取是保证自动指纹识别系统匹配性能的重要前提。目前流行的自 动指纹识别系统大多采用基于细节点的方式。这种方法是模拟人工指纹匹配，在 指纹图像上确定细节特征的位置，然后通过比较特征之问的相互关系来确定指纹 是否匹配。细节特征是指指纹脊线的突变，一般常见的主要有如图2 4 所示的几类。 这几类细节在指纹图像中的分布及比例并不相同。如统计实验表明，端点和分叉 点是指纹中最常见的细节特征，它们出现的几率分别为6 8 2 和2 3 8 t 2 3 】。因此在 大部分自动指纹识别系统中都只把端点和分叉点作为细节特征，匹配一般采用图 形匹配或点模式匹配的方法。 尽管基于细节的指纹匹配在一定程度上满足了指纹匹配的要求，并且由于比 对的是细节特征，所以并不需要存储整幅的指纹图像，大大降低了存储的容量， 加之由灰度指纹图到细节特征表述是一个不可逆的过程，这样也起到了保护个人 隐私的作用。 指纹细节点可分别从指纹细化图像、灰度图像和二值图像上提取。d m a r i o 提出基于指纹灰度图像的特征提取算法。该算法先设定起始追踪位置后，在此位 置作纹线的截面，并寻找截面上的灰度最大值，然后以此为起点，再向切线方向 自订进一定步长进行纹线跟踪，直到满足中止条件为止。算法的主要步骤有【2 3 】： ( 1 ) 选取纹线的灰度最大值点作为起始追踪点； ( 2 ) 寻找截面上灰度值晟大的像素点； ( 3 ) 计算灰度值最大的像素点位置处脊线的切线方向； ( 4 ) 根据设定步长追踪纹线； ( 5 ) 判断脊线追踪是否满足终止条件： a 超出前景区域； b 纹线截面不存在符合条件的灰度最大值像素； c 当前追踪点己经追踪过； d 纹线过分弯曲。 ( 6 ) 判断纹线追踪终止条件类型，并以此判断提取结果：若纹线截面不存在 符合条件的灰度最大值像素，则遇到纹线终止点；若当前追踪点已追踪过，则遇 到了纹线分叉点；若纹线过分弯曲，则追踪到了奇异区的纹线端点。 由于无需二值化和细化处理，使得该算法执行速度快，且不会因为二值化而 丢失信息。但算法每次追踪都需要合理选取追踪起始点，所以计算复杂度比较大。 z x s h i 提出在指纹二值图像中提取细节点，算法主要分四个步骤( 2 3 】： ( 1 ) 在增强后的指纹灰度图像上利用局部自适应阈值法得n - ：值图像； ( 2 ) 利用链码进行块方向估计； ( 3 ) 采用方向滤波器对二值图中的脊线进行滤波； ( 4 ) 利用链码在二值图像上进行特征提取，采用从上到下，从右到左的顺序 检测像素从1 到0 的变化以追踪脊线边缘，如果追踪过程生成的检测向量的变化 角度大于阈值，即认为找到了细节点：向量方向左转为终止点，右转为分又点。 该方法的缺陷在于得到的二值图像产生伪细节点过多，算法鲁棒性差，算法 易造成终止点和分叉点的类型交换，丢失真实细节点的现象比较严重，且没有提 供较好的细节点后处理算法。 3 2 1细节点类型 本文将采取从指纹细化图像上提取细节点信息的传统方法。从指纹细化图像 上确定细节点的类型和位置通常都是采用3 3 模板考察每个像素及其8 邻域的取 值。采用的模板如图3 - 7 ( a ) 所示，图中将其8 邻域按一定顺序从高位到低位进行了 排列如图3 7 ( b ) 。设纹线像素取值为l ，背景像素为0 ，则图3 - 8 ( a ) ，3 - 8 ( b ) 表示了 典型的终止点和分叉点的邻域取值组合。 设p 为当前考察的像素，显然p 为细节点的必要条件是p 取值为l 。定义邻域 点数为当前考察像素p 的8 邻域取值为1 的像素的个数，用s 。表示。定义交叉数 为绕p 在其8 邻域内旋转一周，邻域像素取值变化的次数的一半，用c 。表示【2 5 1 。 设r ( k ) 为8 邻域中排列顺序为k 的像素p k 的取值，且令r ( 9 ) = r ( 1 ) ，可得： 8 s ，= r ( k ) ( 3 2 2 ) c ，= 去i r ( k + 1 ) r ( k ) l ( 3 2 3 ) lk = l 由s ，、c ，的取值可以判定中心像素点的类型。若在像素p 处满足s ，= 1 、c ，2 l ， 则该像素为终止点；若满足s ，= 3 、c ，= 3 ，则该像素p 为分叉点；若满足s ，2 2 、c p 2 或3 ，则该像素p 为纹线连续点。像素p 在图像中的行、列坐标即为细节点的所在 位置( x ，y ) 。 ( a ) 【b ) 图3 7 细：1 ，点提取模板 f i g u r e 3 7m i n u t i a ee x t r a c t i o nt e m p l a t e 这种算法具有计算量小、速度快的优点，而且对没有完全细化的图像也可以 提取出细节特征信息。如图3 8 所示，a 为完全细化的端点c ，= 1 ，b 为完全细化的 分叉点c 。= 3 ，c 为完全细化的连续点，c ，= 2 ，而d 图和e 图分别表示未完全细化 的分叉点和连续点，其中d 图的c 。= 3 ，e 图的c 。= 2 。可见该算法对未完全细化的 指纹图像具有较好的鲁棒性。 田禺田 ( a ) 留爵 3 2 2细节点方向 ( e ) 图3 - 8 细节点的提取 f i g u r e 3 8m i n u t i a ee x t r a c t i o n 2 7 为了使后续处理更加方便，对图像进一步细化。预处理后的指纹图像上仍然 存在着4 连通细化的点，如图3 - 9 ( a ) 所示为一指纹细化后的局部区域示意图，我们 理想的细化结果应是只有8 连通细化如图3 - 9 ( b ) ，这说明上述细化过程是不彻底的。 对这样的细化图进行跟踪时某些点会有多个邻近点，从而为跟踪过程增加了难度。 如果能进一步将多余的点删掉，将有助于后续步骤的顺利进行。本文结合文献【2 】 对此算法再进行改进，对已经细化过的指纹图像进行处理。 ( a ) ( b ) 图3 - 9 后细化结果 f i g u r e 3 9b e h i n dt h i n n i n gr e s u l t 如图3 1 0 所示，细化后处理的8 连通细化模板定义如下：a ，b ，c ，d 为细化 线中的点的8 连通细化模板，e ，f 为分叉点的8 连通细化模板。 x 1x 11x xx x x xx xll x1x ( b ) x x x 111 xxx x x x 11x x1x ( c ) xlx x1x xlx ( d )( e )( d 图3 1 08 连通细化模板 f i g u r e 3 - 108 - c o n n e c t e dt e m p l a t e 8 连通细化的方法为，如果p 点是终止点( 仁1 ) ，不作处理；如果p 点是连续 点( t = 2 ) ，p 点的8 邻域与a ，b ，c ，d 模板比较，如果与其中一个相符合，则把p 点置0 ；如果p 点是分叉点( 仁3 ) ，p 点与e ，f 模板比较，如果与其中的一个相符 合，则把p 点置o 。经过此步处理后，细化图像有了较大的改进，为后续处理减少 了难度。 细节点方向描述了细节点所在纹线延伸的方向，是细节点的重要信息之一。 在己知细节点位置的情况下，求细节点方向需要再确定纹线上另一点的位置，该 位置通常采用纹线追踪的方法来获取。本文采用8 邻域编码追踪算法在细化图像 中提取细节点的方向【1 6 1 【2 6 1 。 基于查表法原理的8 邻域编码追踪算法首先需要建立以下表格： ( 1 ) 邻域编码与类型表 采用图3 - 9 ( a ) 中的3 3 模板像素p 的8 邻域排列顺序进行邻域编码： 8 n ，= 2 。r ( k ) ( 3 - 2 4 ) k = l 由排列组合理论可知，n 。有2 8 种组合方式，故有2 5 6 种取值可能。对于终止 点，其8 邻域有且仅有一个像素为l ，邻域有8 种组合方式，故n 。中有8 种取值 表示该中心像素p 为终止点，如表3 1 所示：对于分叉点，其邻域有三个像素为l 且互不相连，共有1 6 种组合方式，但如果细化完全，n 。中仅有1 2 种取值可以用 来表示该中心像素p 为分叉点；另外，n 。中还有4 0 种取值表示中心像素为连续 点。 表3 1 终j ：点的8 邻域组合与编码表 t a b l e 3 - le n d s 8 - n e i g h b o r h o o dc o m b i n a t i o na n dc o d i n g l -f 耵_ l1 jj 图例 i _i - ji - i_ _ _ _ _ _ _ il _ li _ _ ji _ i ii_ li _ ll l - 8 邻域 编码 l2481 63 26 41 2 8 基于以上邻域编码规则建立的3x3 模板中心像素类型表是一个容量为2 5 6 l 的一维表，它表示了中心像素邻域编码与该像素类型的对应关系。类型表的行坐 标表示邻域编码值，表中元素有四种取值方式：1 ，2 ，3 和0 ，分别表示了该像素 为终止点、连续点、分叉点以及无效点。 ( 2 ) 方向与坐标增量表 在纹线追踪过程中，从当自订像素p 追踪到下一像素p k ，前进的方向有8 种可 能，定义d p = k 作为p 到p k 的方向编码。方向与坐标增量表记录了这8 个方向编 码所对应的行、列坐标的增量。所以该表容量为8 3 ，其中第一列记录了8 个方 向的编码，第- y u 和第三列分别记录行、列坐标的增量。 ( 3 ) 终止点方向表 终止点方向表的容量为8 2 ，用于表示终止点的8 种邻域编码与下1 个追踪 2 9 方向的对应关系。 ( 4 ) 分叉点方向表 分叉点方向表的容量为1 2x4 ， 个追踪方向的对应关系。 ( 5 ) 连续点方向表 连续点方向表的容量为4 0 4 ， 个或3 个追踪方向的对应关系。 用于表示分叉点的1 2 种邻域编码与各选的3 用于表示连续点的4 0 种邻域编码与备选的2 建立了以上表格以后，8 邻域编码追踪算法流程如图3 1 1 所示。 军 f 茹化图荔丽矗编鬲 【一l 一一一 图3 - ii 邻域编码追踪算法【1 6 】 f i g u r e 3 11n e i g h b o r h o o dc o d et r a c i n ga l g o r i t h m 其中，追踪初始化过程中设定的追踪步长为局部纹线间距d ，在指纹图像为 5 0 0 d p i 的采集分辨率下，纹线间距一般为1 0 个像素左右。方向补码d 。与方向编 码d 。的关系为【2 7 】： 雕= 黔0 身 p 2 5 ， 追踪过程中若遇到连续点，则从连续点方向表中选择与补码不同的方向编码 作为新的方向d 。，然后将己追踪步长加1 。求取细节点方向时，以细节点所在位 置为追踪起始位置，从细节点对应方向表中查找备选的方向作为起始追踪方向， 3 0 设定起始追踪步长k = d ，依据以上8 邻域编码追踪算法步骤对纹线进行追踪。当 遇到终止点、分叉点或追踪步长达到l o 时，追踪结束。追踪算法返回结果为追踪 过程中经过的像素坐标( x ，y ) 及追踪结束的类型。设终止点( x o ，y o ) 处纹线追踪结 束返回结果中最后一个像素的坐标为( x ，y ) ，称之为追踪结束点，则该终止点方 向e 为： 0 ：a r c t a i l ! 型 ( 3 2 6 ) y o 。y 分叉点有三个备选的追踪方向，以分叉点所在位置为追踪起始位置，依次追 踪与分叉点相连的三条纹线，可分别得到三条纹线的方向，计算这三条纹线两两 之问的央角大小，根据央角最小的两条纹线方向上的两个追踪结束点的中点位置， 计算出分叉点的最终方向。如图3 1 2 所示。 一， ( b ) 终i ：点方向( a ) 分叉点方向 图3 1 2 纹线方向及细肖点方向 f i g u r e 3 - 12d i r e c t i o no fr i d g el i n e sa n dm i n u t i a e 3 2 3伪细节点的消除 基本的伪细节点的类型有短线、断裂、毛刺、小环、小桥等，如图3 1 3 所示。 为保证提取结果的可靠性，需要对提取的指纹细节点进行后处理。合理的细节点 后处理算法应满足： 1 对所有的细节点进行处理，且每一步仅考虑一种虚假细节点类型； 2 处理的前一步不应破坏后续处理的信息； 3 每个处理步骤尽量不引入新的虚假特征，否则应在后续处理中予以剔除。 本文提出将指纹二值图像和细化图像相结合，分析不同类型虚假细节点的形 成原因，根据它们各自的特点，运用多种后处理规则予以剔除。细节特征提墩后 处理过程为填充岛屿、连环、三角，去除边缘，连接断纹，删除毛刺，删除小桥， 去除叉形，删除短线。具体说明如下【2 3 】： _ _ _ - ( a ) 短线 l - _ - _ _ _ _ ( d ) 组合形态 _ _ _ _ ) 断裂 - _ _ _一 -_ _ _ _ _ 1 _ _ l _ 1- l_ _ ( c ) 毛刺 - _ _ _ _ _ _ _ ( e ) 断裂( f ) 义肜 ( 曲小环( h ) 三角 图3 1 3 伪细h 点类型5 j f i g u r e 3 13f a l s em i n u t i a et y p e s 1 复杂结构的清除 如果指纹采集设备分辨率高，则获取的指纹图像中指纹纹线会存在大量清晰 可见的汗孔，如果指纹图像在增强过程中未能将这些汗孔形成的纹线空洞进行平 滑，那么在二值化和细化后，纹线骨架上就会形成较多的独立岛屿、连环岛屿等 复杂结构；同时，在指纹纹线分叉点附近，如果纹线出现了粘连或由于增强和二 值化过程造成了两条纹线之白j 的连接，经过细化以后就形成了三角结构。实际上， 这些复杂结构都是由多个虚假的分叉点构成的，如果仅仅从细化图中根据规则予 以删除，不仅处理过程复杂，还会造成真实分叉点的丢失。本文在二值图像上采 用了开、闭及填充等操作，避免了这些复杂结构的出现，实验证明，处理效果良 好。 2 前景边缘错误细节点的去除 指纹图像前景边缘属于指纹纹线终止的区域，会形成大量的错误终止点，采 用后处理规则通常是无法去除的。考虑到指纹图像分割算法已经得到了明确的前 景区域模板，本文对该模板进行了二值图像的腐蚀操作，根掘腐蚀结果，可以准 确地定位指纹前景的有效区域，位于该区域以外的错误细节点全部被去除。 3 小桥的删除 指纹纹线之间的粘连或纹线间距太小都会造成小桥结构，该结构是由两个分 叉点构成的。设两个分叉点b l ( x l ，y l ，0 1 ) 、b 2 ( x 2 ，y 2 ，0 2 ) 纹线追踪得到的追踪结 束点位置分别为( x l a ，y l a ，0 1 a ) 、( x i b ，y b ，0 l b ) 、( x l c ，y j 。，0 1 。) 以及( x 2 a ，y 2 a ，0 2 a ) 、 【x 2 b ，y 2 b ，e 2 b ) 、( x 2 。，y 2 。，0 2 。) 。则b i 、b 2 为小桥结构的判定规则为： ( x i c y l 。) 2 ( x 2 ，y 2 ) a n d ( x 2 。，y 2 。) = ( x l ，y 1 ) ( 3 2 7 ) 荨 0 1 a - 0 。i 等a n d 等 0 2 a - 0 ：。i 5 4 7 r ( 3 - 2 s ) 三 0 1 。- 0 。i 3 4 1 ra n d 三 0 2 c 0 ：。l 莩( 3 - 2 9 ) 以上三个判定规则分别用来确定b i ，b 2 之间是否有一条纹线相连、另外两条 纹线是否两两方向一致，且相