（计算机软件与理论专业论文）指纹图像分割与参考点提取算法研究.pdf

山东大学硕士学位论文 摘要 近年来，自动指纹识剐系统 三绐成为，物特征泌刹研究的一个热点，包括指 纹采集、指纹增强、指纹分类、特征提取和指纹匹配等内容，已有不少国内外学 者对指纹识别技术作了大量研究。但到日阿为止，指纹泌别仍存在着一些技术上 的难点，主要体现在如下两个方面：一是在 理想条件下指纹图像与背景区域的 有效分割问题；二是在有弹性形变和特征点丢失变形和旋转的情况下如何可靠、 稳定的进行指纹匹配的问题。 本文针对以上的两个问题进行了深入研究，主要研究内容包括； 针对现有指纹图像分割方法存在的不足之处，提出采用小波包分解对指纹图 像进行分割的思想，并使用该思想实现了基于小波分析的指纹图像分割方法。首 先将待识别的指纹图像使用小波包分解成多个子图，每个子图包含了原指纹图像 中某一段频率的图像信息；然后选择一个合适的予图。并在垓予图上提取出有效 区域的轮廓；最后根据该轮廓并结合原图像完成指纹图像的分割。出于噪音总是 存在于某一个频率范围中，通过选择合适的子图就可以最大可能的将噪音过滤掉， 从而完成有效区域的提取。大量典型低质量指纹数掘库上的实验结果证明了该算 法的有效性。 提出了一种基于d e l a u n a y 三角化匹配的参考点提取方法。现有的指纹匹配方 法大多是利用指纹图像中纹线端点和纹线分叉点这两种点作为判断指纹唯一性的 特征点柬识别指纹，这实际上是一个点模式匹配的问题。在点模式匹配中，往往 需要在匹配静通过进行平移和旋转等操作将两个点模式对准，这也就需要在两个 点模式中找出一对或者一对以上的参考点以计算平移和旋转参数。d e l a u n a y 三角 网具有空外接圆性质和最大的最小角度性质，这使得在指纹特征点模式的匹配中 最大可能的避免导致不稳定和误荸的瘦小三角形出现。对于在有细微弹性形变和 少量特征点丢失、变形和旋转的情况下也能找到可靠的参考点对。 对基于p o i n c a r ei n d e x 的奄异点捡测方法进行了改进。奇异点足指指纹图像 中疗向，玺化比较人的地方中f l 勺某+ 个点，分为c o r e 点稿id e i t a 点。奇异点最初足 破脚水对指纹列像进行分炎，i , , j i b e 它也川以j f ，怂特垛的参与点。已7 ，的璧j ： 山东大学硕士学位论文 p o i n c a r e1 n d e x 的疗法对图像中的每个象褒点酃进i j ：检测，消幸的时f j i 艮大且育 很高的洪硷测率。本文方法根掘c o r e 点年u1 ) e i t a 点的不同的形成特点，首先俭测 到指纹图像中n r 能包含奇异点的区域；然后在这几个区域内使用堆于p o i n c a r e i n d e x 的方法进行奇异点舱测。改进后的茆法能更快速、准确的榆澳f 出指纹图像巾 的奇异点，且有很好的鲁棒性。 全文内容共分五章。第一章绪论，上要介绍了指纹识别技术的概况及其存在 的技术难点：做为丌展研究工作的碡础第二章研究并实现了基于小波包分解的 指纹分割方法；第三章介绍改进的基于p o i n l n d e x 的奇异点定位方法：第四章介 绍了基于d e l a u n a y 三角网的结构匹配和基于局部特征的匹配；第缸章为总结和探 讨。 关键词指纹，指纹识别，图像分割，奇异点，参考点 山东大学硕士学位论文 a b s t r a c t i nr e c e n ty e a r s ，a u t o m a t i c f 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 ，w h i c hc o n s i s t so f f i n g e r p r i n ti m a g ee n h a n c e m e n t ，f i n g e r p r i n tc l a s s i f i c a t i o n ，f e a t u r ee x t r a c t i o n a n d f i n g e r p r i n tm a t c h i n g , h a sd r a w nas u b s t a n t i a la t t e n t i o ni nt h el i t e r a t u r e u n t i ln o w ， a u t o m a t i cf 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 mi ss t i l ln o ts a t i s 助n gf o rt h ef o l l o w i n gt w o p r o b l e m s ：( i ) t os e g m e n tt h ev a l i df i n g e r p r i n t a r e af r o mb a c k g r o u n du n d e rs o m e n o n p e r f e c ts i t u a t i o n ；( i i ) t om a t c ht w of i n g e r p r i n ti m a g e si nt h a t ( a ) f e a t u r e sm a yh a v e u n d e r g o n ee l a s t i cd e f o r m a t i o nd u et os k i ne l a s t i c i t ya n d ( b ) f e a t u r e sm a yb es e a l e d ， t r a n s l a t e d a n d o rr o t a t e d i nt h i sp a p e r , w ed e e p l ya n a l y z ea n di n v e s t i g a t et h ea b o v et w ok e yp r o b l e m so f a u t o m a t i cf 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 t h em a i nc o n t e n t sa r ea sf o l l o w s ： f o rf i n g e r p r i n ts e g m e n t a t i o n ，a i m i n ga tt h ed e f i c i e n c yo fe x i s t i n gm e t h o d ，w ef i r s t b r i n gf o r w a r dan e wt h o u g h to ff i n g e r p r i n ts e g m e n t a t i o nb a s e do nw a v e l e tp a c k e t d e c o m p o s i t i o na n dc a r r yi to u t t h ef i n g e r p r i n ti m a g ei sd e c o m p o s e di n t os u b - i m a g e s u s i n gw a v e l e tp a c k e td e c o m p o s i t i o na ts o m es p e c i f i e dl e v e lf i r s t l y e a c hs u b i m a g e c o n s i s t so fp i x e l si nas p e c i f i e dr a n g eo ff r e q u e n c yo ft h eo r i g i n a lf i n g e r p r i n ti m a g e ； t h e na na p p r o p r i a t es u b - i m a g ei ss e l e c t e da n dr e c o n s t r u c t e da n dt h ee d g e so ft h ev a l i d f i n g e r p r i n ti m a g ea r ed e t e c t e di n t h i ss u b - i m a g e ；f i n a l l yt h ef i n g e r p r i n ti m a g ei s s e g m e n t e da c c o r d i n gt ot h ee d g e sw ed e t e c t e d t h ee x p e r i m e n t so l ls o me x t r e m e l yl o w q u a l i t yf i n g e r p r i n ti m a g e sc o n f i r mm t h ee f f e c t w e n e s so f o u ra p p r o a c h d e l a u a n yb a s e dr e f e r e n c ep o i n t se x t r a c t i o nm e t h o di sp r e s e n t e d m i n u t i ab a s e d m a t c h i n gi st h em o s tw e l l k n o w na n dw i d e l yu s e dm e t h o df o rf i n g e r p r i n tm a t c h i n ga s o n eo fg r a p h - b a s e dm a t c h i n gm e t h o d s t w ok i n d so fm i n u t i a ea l ea d o p t e di nm a t c h i n g ： r i d g ee n d i n ga n dr i d g eb i f u r c a t i o n t h u s ，f i n g e r p r i n tm a t c h i n gc a nb er e g a r d e da s a p o i n t p a t t e r nm a t c h i n gp r o b l e m s o m ep a i r so f r e f e r e n c ep o i n t sa r ef i r s tl o c a t e d t oa l i g n t h et e m p l a t ei m a g ea n dt h eq u e r yi m a g eb e f o r em a t c h i n g r e f e r e n c ep o i n t sc o u l db e o b t a i n e du s i n gd e l a u n a yt r i a n g u l a t i o nn e tb a s e do nt r i a n g u l a t i o nm a t c h i n g 山东大学硕士学位论文 t r i a n g u l a t i o n sg e n e r a t e df r o md e l a n u a yt r i a n g u l a t i o na r en o tt h i na n ds t a b l ea n d r e l i a b l ec o r r e s p o n d i n gc o u l db el o c a t e de v e ni nt h es i t u a t i o n st h a tf i n g e r p r i n ti m a g e u n d e r g o e se l a s t i cd e f o r m a t i o na n dt h eo v e r l a pa r e ai sl i m i t e de x i s t s p o i n c a r ei n d e xb a s e ds i n g u l a r i t i e sd e t e c t i o nm e t h o di si m p r o v e di nt h i sp a p e r s i n g u l a r i t i e s ，n a m e l yc o r ea n dd e l t a , a r em o s tu s e df o rf i n g e r p r i n tc l a s s i f i c a t i o n i nf a c t ， s i n g u l a r i t ym a yb ca l s or e g a r d e da sar e f e r e n c ep o i n t m o s ts i n g u l a r i t i e sd e t e c t i o n m e t h o d sb a s e do np o i n c a r ei n d e xb e g i na tt h ep i x e il e v e l ，t h u st i m ew a s t i n ga n da h i g h e re r r o rr a t e a c c o r d i n gt ot h ed i f f e r e n tc h a r a c t e r i s t i co ft h ec o r ea n dt h ed e l t a , b l o c k st h a ts i n g u l a r i t i e sb e l o n gt oa r ed e t e c t e df i r s t ；t h e ns i n g u l a r i t i e sc o u l db ed e t e c t e d w i t hp o i n c a r ei n d e xw i t h i nt h o s eb l o c k s t h ei m p r o v e dm e t h o dc o u l df i n dd e l t aa n d c o r ep o i n t sm o r er e l i a b l ya n du s i n gl e s st i m e t h et h e s i si so r g a n i z e da sf o l l o w s ：c h a p t e r1i si n t r o d u c t i o n w h i c hi n t r o d u c e st h e g e n e r a li n s t i t u t i o n sa n dd i f f i c u l t i 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 n b e i n gt h eb a s eo ft h e s t u d y i n g , c h a p t e r2p r e s e n t saf i n g e r p r i n ts e g m e n t a t i o nb a s e do nw a v e l e tp a c k e t d e c o m p o s i t i o n c h a p t e r3i n t r o d u c e sa l li m p r o v e dm e t h o dt ol o c a t et h es i n g u l a r i t y o n e m e t h o do fr e f e r e n c ep o i n te x t r a c t i o ni sr e p o r t e di nc h a p t e r4 ，c h a p t e r5i sc o n c l u s i o n a n dd i s c u s s i o n k e y w o r d sf i n g e r p r i n t , f i n g e r p r i n ti d e n t i f i c a t i o n ，f i n g e r p r i n ts e g m e n t a t i o n ， s i n g u l a r i t y , r e f e r e n c ep o i n t i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：日期：丛! ! ：， 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作糍：础i 燃：秽日期：世盟j 山东大学硕士学位论文 1 1 指纹识别技术简介 第1 章绪论 自动指纹识别系统有如下4 个主要模块组成：( 1 ) 指纹采集；( 2 ) 指纹预处 理：( 3 ) 特征提取；( 4 ) 指纹匹配。指纹采集就是将指纹纹线分铈经相关设备录 入、数字化；指纹预处理是对采集到的指纹图像进行一定的处理，如指纹图像分 f i g 1 1b m m e t r i cm a r k e ts h a r eb yt e c h n o l o g yi n2 0 0 2 图1 12 0 0 2 年各种生物识别技术产鼎的市场，i 有率 割、增强、二值化、细化等：指纹特征提取是在经过预处理后的图像的基础上， 提取指纹的关键特征；指纹匹配是判断两枚指纹足否来自同一个人的同一个指头。 指纹识别技术是最可靠的生物识别技术之，也被官方作为身份识别的依据，这 已经有很长的历史了。自动指纹识别技术的研究丌始于1 9 世纪7 0 年代，迄今已 取得了巨大的发展。现在，已经有很多自动指纹识别产品应用于法律部门、公共 安全领域和民用领域。但自动指纹i ： 别技术仍然【f i i 巨大的挑战。 山东大学硕士学位论文 1 1 f 指纹识别系统的一般结构 指纹i 别系统本质上是一个模式识别系统，它根掘使用者的尘理或者行为特 征对使用者进行辨识，从而判断其是否具有合法身份。般指纹识别系统的结构i | 如图1 2 所示。 从逻辑上讲，这种系统有两个主要模块组成：登记模块和辨i 模块。登记模 块主要负责将生物特征信息登记到生物特征识别系统样本数据库，在登记模块中， 个体的生物特征样本首先经相应的设备录入、数字化，进而经特征提取算法提取 特征信息，这种特征信息被称为样本。根据需要，样本信息被保存在数据库或磁 卡、智能卡中辨识模块负贵解决待识特征信息和样本特征信息是否匹配的问题。 在该模块中，相应设备录入待识生物特征，并进行数字化，经特征提取算法提取 f i g 1 2b l o c kd i a g r a m so f c o m m o ns t r u c t u r o f b i o m c t r i cs y s t e m 图1 2 一般生物识别系统结构示意| ! i 待识生物特征中的有用信息，出模式匹配算子将这一信息与预先存储的样本信息 进行比对，做出是否匹配的判断。 指纹识别系统的工作模式可以分为两类：验证( 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 ) 模式。验证模式通过把现场采集到的生物特征与该人已经赣记了 的存在数掘库中的生物特征进 j - 时的比对( o n c q o o n em a t c h i n g ) ，束确 人身份 的过程。改种模式常常被用j 秘板谚 别，h 的是为了防j 上：多个人使脚【| 可一个身份2 l 。 山东大学硕士学位论文 在辨识模式中，系统把现场采集到的生物特征同样本数据库中的生物特征逐一对 比，找出与现场生物特征相匹配的特征信息。因此，该模式使用一对多比对来建 立被考察者的身份( 如果未注册，则匹配失败) ，不需要他或她声称身份。辨识是 拒绝识别( 这个人是否是被否认的) 应用的一个重要的组成部分。拒绝识别的目 的是防止一个人具有多个身份【引。辨识模式主要应用于公共安全领域。比如，可以 通过将一个不明身份的人的指纹与指纹库中有犯罪记录的人的指纹进行比对，来 确定此人是否曾经有过犯罪记录。 1 1 2 自动指纹识别研究内容 自动指纹识别技术主要包括指纹采集、指纹预处理、特征提取和指纹匹配等 内容。 1 指纹采集 从采集方式来看，指纹基本可以分为三类：捺印指纹，活体指纹和模糊指纹。 捺印指纹指的是将沾了印墨的手指按压在某种东西( 通常是纸) 上留下的指 纹的痕迹，再经相应设备转化为数字化的信息，就得到捺印指纹图像。捺印指纹 采集到的有效面积比较大，但因采集方式所限，采集速度较慢，指纹缺陷较多， 目前难以严格控制采集的质量。 根据录入原理的不同，活体指纹录入仪可分为光反射式、电感式、电容式和 超声反射式等几种。根据采集时指头是否与指纹录入仪接触，又可分为接触式和 非接触式。经活体指纹采集设备得到的是数字化的指纹图像，相比较而言，活体 指纹的质量是最好的。 山东大学硕士学位论文 f i g 1 3 a v a r i e t y o f f i n g e r p r i n ts e n s o r s w i t h d i f f e r e n ts p e c i f i c a t i o n s 图1 3 几款不同原理的指纹采集器 模糊指纹一般是指在犯罪现场采集到的指纹。将罪犯无意中遗留在犯罪现场 的指纹痕迹经过显影、拍照和扫描等技术处理而得到的指纹图像。 2 指纹预处理 指纹预处理是指纹特征提取前的一个非常重要的环节，主要用于突出指纹图 像中的纹理、方向信息，消除或者减弱噪声等无用信息。指纹图像预处理包括指 纹图像分割、图像增强、二值化、细化等。 准确、可靠的将指纹图像从背景区域中分割出来，对于缩短图像处理时间， 提高特征提取的准确率都具有重要意义，非理想采集条件下的指纹图像分割显得 越发重要。指纹图像分割是自动指纹识别中一个非常困难同时也是一个值得深入 研究的问题。 图像增强是根据指纹图像纹理的方向性和纹线距离对可恢复的纹线进行恢复 和增强，对于不可恢复的区域进行屏蔽。二值化即将图像中灰度大于某阈值的像 素的狄度置为l ，小于等于该阈值的像素的灰度置为0 ，即将图像变为二值图像 指纹细化就是提取指纹图像的骨架。图1 4 显示了一副指纹图像的几个预处理过 程。 4 山东大学硕士学位论文 ( a ) ( c ) 筋墨，。 黪拣i | | 穆墨娆 f i g 1 4 a n e x a m p l e o f f i n g e r p r i n t p r e t r e a t m e n t ：( a ) s e g m e n t a t i o n , ( b ) e 】1 1 1 l c e l l 砖n l ( c ) t h r o n i n ga n d ( d ) b l n a r i z i n g 图1 4 指纹图像预处理示例：( a ) 分割，( b ) 增强，( c ) 细化，( d ) 二值化 3 指纹细节特征定义和提取 在自动指纹识别技术中，一般使用两种细节点特征；纹线端点( 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 5 所示。 瓣誊 山东大学硕士学位论文 4 指纹匹配 ( a ) f i g 1 5m i n u t i a et y p e ( a ) e d g ee n d i n g ( b ) e d g eb i f u r c a t i o n 图1 5 特征点类璎示意图( a ) 端点( b ) 分义点 指纹匹配是自动指纹识别系统( a f i s ) 的核心研究内容之一，它在指纹特征 提取之后，是自动指纹识别的最后一步，也是非常关键的一步。指纹匹配是靠比 较两枚指纹的局部纹线特征和相互关系来决定指纹的唯一性的。由于采集设备的 不完善性、采集条件的随机性以及预处理技术的局限，使得真正特征点的缺失、 伪特征点的存在和特征点定位偏差的情况普遍存在。所以，指纹匹配必然还是一 种模糊匹配，且需要具备一定的弹性。 1 1 3 自动指纹识别的应用 经过3 0 多年的发展，以指纹识别技术为代表的生物识别技术的产品在社会中 开始了比较大规模的应用。很多国家的政府采用法律规定的方式来保证生物识别 技术的应用。如美国在9 1 1 以后，三个相关法案( 爱国者法案、边境签证法案， 航空安全法案) 都要求必须采用生物识别技术作为法律实施保证。 指纹识别技术的应用非常广泛。典型的脱机应用有指纹锁，指纹保险柜，指 纹考勤系统等；银行保管箱，自动取款机、网上交易等基于计算机的自动指纹识 别系统都属于指纹识别技术的联机应用。 以指纹识别技术为代表的生物特征识别技术有望在将柬的公共领域和民用领 域扮演更重要的角色。 6 山东大学硕士学位论文 1 1 4 自动指纹识别技术存在的问题 经过学术界和产业界近几十年的努力，指纹识别技术已经有了突飞猛进的发 展。指纹采集的技术越来越先进，识别的精度也越来越商，新算法，新系统层出 不穷。尽管如此，仍然有许多地方不尽如人意，主要体现在如下几个方面： 指纹采集技术有待突破。对于干、湿、脏、老化和磨损严重的指头，现有的 采集器往往难以采集到清晰的指纹图像，这样就直接影响到后继算法的可靠性和 识别的准确性。另外，目前大多数指纹采集器采集的是指纹的二维图像，这样就 不可避免的造成一定程度的形变。所以，如何提高现有的指纹采集技术，使其能 够较好的处理指纹的清晰度和变形问题，将是今后自动指纹识别研究的一个重大 课题。 非理想采集条件下具有鲁棒性的特征提取技术有待发展。广义的指纹特征提 取包括指纹图像的预处理和特征提耿。非理想采集条件下指纹特征的可靠提取与 识别，是当前自动指纹识别领域的一个研究重点，特别是其中的指纹图像分割技 术。图像分割是指纹识别的第一步，分割性能的好坏将直接影响最终识别的准确 性和效率。故准确、可靠地将指纹图像从背景区域中分割出来，对于缩短图像预 处理时问、提高指纹特征提取的准确率都具有非常重要的意义 指纹匹配技术有待发展。由于一些客观因素的存在，如采集的指纹图像质量 较差、存在弹性形变、重叠面积较小等，使得指纹匹配技术存在很大的难度2 引 在以上因素存在的情况下，如何准确、可靠的进行指纹匹配仍是当f i 所要解决的 技术难点。 1 2 本文的创新之处 本文针对指纹识别中的两个关键技术，即指纹图像分割和指纹匹配中基准点 对的确定进行了深入细致的分析和研究。 针对目前指纹图像分割中存在的分割精度低，分割效果差等问题提 h 采用 小波分析对指纹图像进行分割的思想，并使用垓思想实现了基于小波包分解的指 纹图像分割方法。 山东大学硕士学位论文 - 一i - - - _ _ - _ _ _ - _ _ - _ _ _ _ _ _ _ - _ _ _ _ _ - - _ _ - _ _ _ _ _ _ _ _ _ _ _ 一 针对点模式匹配算法中参考点定位不准确的问题，提出了两种参考点定位的 方法：基于d e l a u n a y 三角网的方法和基于局部特征匹配的方法。这两种方法均能 快速、准确的对参考点进行定位。对基于p o i n l n d e x 的奇异点定位方法进行了改进， 改进后的算法能够比原算法更快速、准确的定位奇异点。 1 3 本文的组织 本论文共分五章。第一章绪论，主要介绍了指纹识别技术的概况及其存在的 技术难点；做为丌展研究工作的基础，第二章研究并实现了基于小波包分解的指 纹分割方法；第三章介绍改进的基于p o i n i n d e x 的奇异点定位方法；第四章介绍 了基于d e l a u n a y 三角网的结构匹配和基于局部特征的匹配；第五章为总结和探讨。 山东大学硕士学位论文 第2 章基于小波分析的指纹分割方法 2 。1 指纹图像分割方法综述 2 1 1 图像分割的有关概念 图像分割是指把图像分成各具特性的区域并提取出感兴趣目杯的技术和过 程。该技术在不同的领域中有时也用其他的名称，如目杯轮廓( o b j e c td e l i n e a t i o n l 技术，阈值化( t h r e s h o l d ) 技术，图像区分或求差( i m a g ed i s c r i m i n a t i o n ) 技术，目标检 测( t a r g e td e t e c t i o n ) 技术，目标识别( t a r g e tr e c o g n i t i o n ) 技术等。 借助集合概念可对图像分割给出如下形式化的定义孤。令集合r 代表整个图像 区域，对r 的分割可看作将只分成n 个满足以下五个条件的非空子集( 子区域) 凰r 2 ，m ： ( 1 ) y r = 胄； ( 2 ) 对所有的f 栅，i # - j ，有置ir ，= a ； ( 3 ) 对f = l ，2 ，a ，有p ( 置) = t r u e ( 4 ) 对i j ，有烈置y 足，) = f a l s e ： ( 5 ) x c i = l ，2 ，a ，置足连通的域。 其中p ( r ) 是对所有在集合r 中元素的逻辑谓词，o 代表空集。条件( 1 ) 指 出在对一幅图像的分割结果中全部子区域的总和( 并集) 应能包括图像中所有像 素；条件( 2 ) 指出在分割结果中各个子区域足互不重叠的：条件( 3 ) 指出在分 割结果中每个子区域都有独特的特性；条件( 4 ) 指出在分割结果中，不同的子区 域具有不同的特性，没有公共元素；条件( 5 ) 要求分割结果中同一个子区域内的 像素应当是连通管，即同一个区域内的任两个像索在陔予区域内互相连通。 9 山东大学硕士学位论文 2 1 2 指纹图像分割方法 人们在图像分割方面作了很多研究工作，目丽可查的有上千种可用的图像分 割方法4 ，1 ”7 】。但是迄今为止没有一个通用的分割理论，绝大多数算法部是针对 某一个具体的问题。本文基于像素的不连续性和相似性的性质区域内部的像 素一般具有某种相似性，区域之间的边界上一般具有某种不连续性将分割算 法分为三类：基于边界的分割算法、基于区域的分割算法和基于特殊技术的图像 分割方法。 1 基于边界的图像分割方法 该方法根据区域边界处像素特征值不连续的特征提取图像中感兴趣的区域。 根据算法的执行过程可以将该类方法分为两类：并行边界技术和串行边界技术。 并行边界分割技术是采用并行方法通过对目标边界的检测束实现图像分割， 其方法原理与人的视觉过程相似，在确定一组点是否组成一段边界时不需考虑其 他点是否为边界点。首先采用微分算子或者建立边界模型来检测目标边缘点，然 后利用哈夫交换组成目标边界。常用方法有两种：微分算子边缘检测和边缘拟合。 而串行分割技术通过顺序搜索边缘点来实现。常用方法有边界跟踪，曲线拟合， 状态空问搜索和动态规划。毋立芳等“1 将基于边界的分割方法应用于人脸脸分割， 该类方法在指纹图像分割中的应用较少。 2 基于区域的图像分割方法 基于区域的分割算法有如下几种：阈值化算法，特征空间聚类，区域生长算 法和分裂合并算法。 阈值化算法的分割原理比较简单，以基于灰度的阈值分割方法为例“j 。首先 确定一个处于图像灰度取值范围之中的灰度阂值，然后将图像中各个像素的灰度 值与该闽值相比较，并根据比较结果将对应的像素分为两类。但基于图像灰度特 性的方法不太直接适用于较强纹理方向的指纹图像。阂值化分割方法常常结合其 它的分割思想一起使用。 区域增长分割算法的基本思想是将具有相似性质的像素集合起来构成区域。 0 山东大学硕士学位论文 首先对每个需要分割的区域找一个种子像素作为生长的起点，然后将种子像素周 围邻域中与种子像素有相同或相似性质的像素( 根掘某种事先确定的生长或相似 准则柬判定) 合并到种子像素所在的区域中。将这些新像素当作新的种子像素继 续进行上面的过程，直到再没有满足条件的像素被包括进来。 目i j i 指纹图像分割的主流算法多采用基于区域的分割技术。从分割的精度方 面考虑可将现有的区域分割方法主要归结为以下两大类： 一类是基于块水平的方法。m e h t r e 等人陋埔1 根据分块图像的梯度分白和灰度 方差将它们分成指纹区和背景区两类。x c h e n 等人【档1 使用线性分类器实现了对指 纹图像块的分类，从而实现图像分割。唐良瑞等人将d s 证据理论用于指纹图 像分割，提出了基于将旷s 证据理论的指纹图像分割方法，利用块图像的方向和 对比度信息实现了指纹图像分割。王森等人【1 9 1 将对比度和主能比作为两个特征进 行指纹图像的分割。q r e n t 2 0 1 等人提出了基于特征统计和基于前景轮廓线搜索的 两种指纹图像分割方法。耿茵茵等人1 2 1 提出了指纹图像的分级分割算法，利用纹 线方向特性和灰度特性个改进判据。 另一类是基于像素水平的方法。b a z e n 等“”通过对象素点特征定义与分析， 使用c m v 三个指标的线性分割器将所有象素点分成指纹和背景两类。何余良等 提出了一种基于马尔科夫随机场的指纹图像分割方法，实现了清楚图像背景区域 的目的。蒋景英等m 3 将遗传算法和方向图信息相结合，实现了指纹图像的分割。 3 基于特殊技术的图像分割方法 基于数学形态学的分割方法可以简化图像数据，保持它们基本的形状特性， 并除去不相干的结构。该类方法主要有边缘形态检测和水线区域分割。 常用的边缘检测算予通过计算图像中局部小区域的差分来工作，算子对噪声 都比较敏感并且常常会在检测边缘的同时加强噪声。而形态边缘俭测器主要用到 形态梯度的概念，虽对噪声较敏感，但不会加强或放大噪声。根据要得到的边界 的宽度，形状，可以定义需要的形态梯度进行边缘检测。 水线( w a t e r s h e d ) 区域分割法的基本过稃是连续腐蚀二值图像。第一轮被腐 蚀掉的元素记为l ，第二轮被腐蚀掉的元素已为2 ，以此类推，最后剩f 的元素记 山东大学硕士学位论文 为n 。这样元素的最大值就形成了山峰，而最小值形成山谷，即水线。这样将各个 山峰周围的水线连起来就可得到对目标的分割。 分水岭区域分割算法常常用于医学图像处理，在文章i9 1 中，作者将分水岭算法 用于医学图像分割。主动轮廓线模型被广泛的应用于计算机视觉和图像处理，尤 其用于提取物体的边界基于主动轮廓线模型的图像分割方法 1 0 - 1 4 j ，本质上讲也是 基于边界的分割方法，只是对于具体的应用，结合图像的特征，定义了不同的边 界搜索的策略。 另外还有些分割方法，如基于信息论的分割技术，基于神经网络的分割技术、 基于模糊集合和逻辑的分割技术、基于小波分析和变换的分割技术、基于遗传算 法的分割技术f 2 6 】和基于d - s 证据理论的分割方法1 1 8 1 等。 f i g 2 tf i n g e r p r i n ti m a g e s1 i t l ll o wf r e q u e n c yn o i s e s ：( a ) l o w f r e q u e n c yn o i s e sw i t har e l a t i v e l yc l e a rf o r e g r o u n d ；( b ) l o w f r e q u e n c yn o i s e sw i t i if u z z ye d g e s 图2 1 带有低频噪声的指纹图像：( a ) 边界相对清晰的指纹图 像，( b ) 边界模糊的指纹i 茎i 像 山东大学硕士学位论文 2 2 算法思想 指纹图像中脊线和谷线有规律的交叉出现组成了指纹的有效区域。在同一个 人的指纹图像中脊线和谷线之f b 】的距离一般比较固定，可以认为是一个常数，因 而指纹的有效区域实际上是一种低频信号。当图像中的噪声不是很明显，或者存 在高频噪声时，大多数算法都能给出比较好的效果。但当指纹图像中的噪声主要 是低频噪声时( 如图2 2 所示) ，常规的算法就不能很好的工作。采用小波包分解 能够很好的解决以上的问题。 一 2 2 1 小波包分解 多级小波变换和小波包变换都能将一幅图像在频率上进行分解。对于一个2 d 的指纹图像而言，经过多级小波变换后，一个j 1 级的低频信号将会分成四个部分： j 级的低频信号，水平方向的高频信号，垂商方向的高频信号以及对角线方向的高 广3 厂 ” 广肥 陀 f i g 2 2d e c o m p o s i t i o nn o f m u l t i - r e s o l u t i o nw a v e l e tt r a n s f o r m 图2 2 多分辨率小波分解示意图 频信号。每次都只能是对上一级的低频信号进行分解。多级小波变换有时被称作 是多分辨率小波变换，图2 2 显示了一个一维信号的多级小波变换的情况。 小波包分解是经典小波分解的一个简单推广。相对于对分辨率小波分解，小 波包分解能提供更丰富的信号分析信息。在小波包分解中，不仅低频信号可以进 行分解，高频的细节信号同时也可以进行分解。这样一幅2 d 指纹图像经小波包分 解后将产生一个分解树，其中的每一个子节点都包含了原指纹图像中一段频率中 山东大学硕士学位论文 的象素信息。图2 3 显示了一个二维信号的小波包变换的情况。 2 2 2 算法思想 厂一4 厂“厂“ f i g 2 3d e c o m p o s i u o nt r e eo f w a v e l e tp a c k e tt r a n s f o r m 圈2 3 小波包分解示意i 璺l 从以上的分析可以看出，使用小波包分解，一幅2 d 指纹图像可以分解成若干 幅子图，每个子图都包含了原指纹图像中某一段频率的象素信息。指纹图像分成 大小为矿w 的块，分别计算块内的平均灰度和平均方差。例如，对于一个三级小 波包分解，会产生出8 个子图，假定厂，f 【o ，1 】是原指纹图像信号的频率，那么这 8 个子图所包括的频率从低到高分别是【o o 1 2 习，e o 1 2 s o 2 5 1 ，a a ，【o 7 5 , 0 s 7 5 ，1 0 8 7 s 1 】。 因而可以期望，在某一个子图里，噪声会比较明显；而在其他的子图里，噪声则 几乎没有任何影响，这样我们就能把指纹图像的有效区域和噪声分离出来，达到 分割的目的。虽然在某些个子图里面，指纹图像的信息也会被过滤掉，但是指纹 图像的轮廓信息还是可以检测得到，从而根掘这个轮廓信息完成指纹图像的分割。 2 3 算法步骤 在对原指纹图像信息进行小波包分解后，一个合适的子图将会被挑选出来， 以用束在进行指纹的边界检查，这驻的边界检查只是找到指纹的轮廓信息。有了 有效的轮廓信息，就可以根据该信息并结合原指纹图像将噪声从原指纹图像中分 离出去。下面将分别介绍该算法的3 个主要步骤。 1 哪 观 厂鹏1 姗 雠 厂鹏 粥 眦 厂舭一l 眦 厂舭 山东大学硕士学位论文 2 3 1 子图选择 对于一个n 级的小波包分解，将会产生出2 ”个子图。我们应该选择出这样一 个r 图：在这个子图中，噪声被最大限度的过滤，而指纹的纹线信息或者轮廓尽 町能的清晰。 假定l ，i = 1 ，2 是两个门槛值，g 是指纹图像的灰度平均值， n 。，o - ，z 。 - 2 是厌度直方图中找到的最高点的数目，c 是类别标签，我们可以 根据下面的公式( 1 ) 将指纹图像大体分成3 类： 1 1 i f t 2 g 。( r ，”n 。2 2 c = 2 i fg 。t z a n d ( 以。2 1 口r n ，2 0 )( 2 1 ) 【3 i t g 。t ia n d ( 行。2 10 7 胛。2 0 ) 第一类是那种质量较好，且带有低频噪声的指纹图像；第二类和第三类均代表带 有低频噪声的指纹图像：第二类会有一个比较明显的边界，而第三类的边界则较 ( a f f ，( g ) 山东大学硕士学位论文 (i)0j( k ( i ) “1 ) ( n )( o ( p ) f i g 2 4s i x t e e ns u b - i m a g e sg e n e r a t e df r o mt h ed e c o m p o s i t i o no f w a v e l e tp a c k e t a tl e v e l 李。( a ) ，( b ) ( o ) ( p ) a l es u b - i m a g ef r o ml o wf r e q u e n c yt oh i g h f r e q u e n c y , r e s p e c t i v e l y 图2 4 一幅指纹图像在4 级小波包分解后产生的1 6 个子图：( a ) ，( b ) 一 ( o ) ( p ) 的频率从低剑高 模糊。对于一个给定的分解级数，根据计算出来的c 值，再结合表2 1 ，我们就可 t a b l e 2 1c o r r e s p o