（计算机应用技术专业论文）指纹压缩与识别及在电子门票系统中的应用研究.pdf

摘要 信息社会的今天，电脑应用系统已经渗透到各行各业。而国内绝大多数旅游 景点在门票管理上仍采用人工售票、人工验票等人工管理模式，已远远不能适应 现代旅游景点管理的需要。解决传统人工票务管理中的缺陷，建立一个全方位、 多层次、立体化及高效率的景区信息管理系统已经成为旅游景点的一项基础技术 建设。 针对现今假票、偷票、漏票这个使管理者既敏感而又甚为头痛的难题。如何 利用生物识别技术来杜绝这些现象成为当前一个需要解决的问题。指纹识别技术 是一种比较成熟的生物技术。其先天性、唯一性和不变性等特点，使其在门票系 统中准确鉴定身份成为可能。可大量的指纹原始图像存储在计算机中将使指纹库 十分庞大。本文在分析了指纹识别和图像压缩技术的基础上，开展了如下工作； 针对指纹图像存储难的问题提出了一种改进的r o i 编码技术； 利用s p i h t 与改进r o i 编码技术相结合，以指纹特征值作为r o i ，使其 精确保留关键点信息的同时可以提高图像的压缩比； 结合指纹压缩与识别设计了一种指纹电子门票系统。 系统将指纹与i c 卡结合，做成人卡合一，可以大大的提高门票的安全性，一 人一卡，可以非常有效地解决假票、偷票、漏票、补票等问题。 关键词：指纹识别；指纹图像压缩；感兴趣编码；电子门票系统 a b s t r a c t i nt h ei n f o 肌a t i o na g e ，t h ec o m p u t e rs y s t e m sh a v eb e e n 印p l i e di n t ov a r i o u s i n d u s t r i e s i no u rc o u n t r y ，t h em a n a g e m e n tm o d e lo fg o t - u ps a l e sf o rt i c k e t s 卸dg o t - u p c h e c ko ft i c k e t ss e e m sn o tt ob ea b l em e e tt h ed e m 锄do ft h em o d e mm a n a g e m e n to f t o u r i s m 柚ym o r e h o wt ob r e a kt h el i m i t a t i o no ft h et r a d i t i o n a lm a n a g e m e mo ft i c k e t h 锄d l i n g跏d t os e tar o u n d ， i n t e g r a t e da n de m c i e n tm a n a g e m e n tm o d e l w i t h i n f o m a t i o n s y s t e mh 嬲b e c o m eaf u n d a m e n t a l i s s u ei nt h et e c h n o l o g i c a lp r o j e c t f a l s et i c k e t s ，t i c k e tt h e f t 锄dm i s s i n ga f ev e r yt r o u b l es o m ep r o b l e m sn o w a d a y s s oh o wt om a k eu s eo fb i o i o g i c a li d e m i f y i n gt e c h n o l o g yt op r e v e n tt h e s ep h e n o m e n a h a sb e c o m ea nu r g e mt a s k t h et e c h n o l o g yo ff i n g e r p r i n ti d e n t i 丘c a t i o ni sak i n do f m a t u r eb i o l o g i c a lt e c h n o l o g y n si l l n a t e n e s s ，u n i q u eq u a l i t i e s 舳di n v a r i a b i l i t ym a k e t h ei d e n t i 6 c a t i o ni d e m i t i e si nt h et i c k e ts y s t e m sp o s s i b l e a st 0t h ef i l n c t i o no fb u y i n g t i c k e t sa f t e rt h en o m a l t i m e ，h o wt ou s et h et e c h n o l o g yo fp i c t u r ec o m p r c s s i n gt os t o r e m o r ei n f o r i i l a t i o ni ss t i l la nu r g c mo n e ，f o rt h ed e p o s i to fo r i g i n a lp i c t u r eo ft h e f i n g e 叩r i n tm a k et h es t o r e f o o mv e r ) ，b i g t h i sp a p 盯d i s c u s s e st h et e c l l i l o l o g yo f f i n g e r p r i n ti d e n t i f i c a t i o n ，p i c t u r ec o m p r c s s i o n锄dm r t h e m o r ec a r r i e so u t t h e f o l l o w i n g 锄a l y s i s ： b r i n gf o r w a r dak i n d o fm e n d e dr o lc o d i n gt e c h n o l o g ya i m i n g a tt h e p r o b l e mo fs t o r i n gf i n g e r p r i n tp i c t u r e ； c o m b i n et h es p i h tw i t ht h em e n d e dr o ic o d i n gt e c h n o l o g yt oi n c r e a s et h e r a t eo ft h ep i c t u f ec o m p r e s s i n ga n dt ok e e pt h ek e yi n f o h n a t i o np r e c i s e l yb y u s i n gr o i a sf j n g e r p r i n tc h a r a c t e r ； d e s i g nak i n do fe t i c k e ts y s t e m c o r d i n gt ot h ec o m b i n a t i o nc o m p r e s s i o n a n df 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 l l i i o i o 黟 t h es y s t e mw h i c hc o m b i n e sb o t ht h ef i n g e 叩r i m 眦dt h ei c c a r dt om a k et h e p e r s o ni d e n t i f i a b l em a ys t r o n g l ye i l l l a n c et h es e c i i r i t yo f t i c k e ta d m i n i s t r a t i o n h o l d i i l g ac a r df o re a c hp e r s o nc a ne f f e c t i v e l ys o l v es o m ep r o b l e m sr e l a t e dw i t hf a k et i c k e t s ， s t o l e nt i c k e t ，t i c k e te v a s i o n ，a n dt i c k e tm a k e u pa n ds oo n k e yw o r d s ：f i g e r p r i n ti d e n t i n c a t i o n ；f i n g e r p r i n ti m a g ec o m p m s 3 i o n ；r e g i o no f i n t e 他s t ；s p i h t ；e l e c t r o n i ct i e i 【e ts y s t e m h 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：刍名玉日期：砷年f 月，妒日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：童弓知匆 导师签名：7 危扫 1 1 引言 第一章绪论 随着计算机、网络技术、信息处理技术的发展，多媒体技术在社会生活中的 应用越来越广泛。多媒体一般涉及的数据有文字、语音、静止图像、动画、视频 等。由于这类数据的数据量一般都比较大，因此，如何处理、组织这些数据，提 高处理和存储效率，去除冗余信息是信息技术要解决的一个重要问题。 1 1 1 图像压缩概述 压缩机制通常可以分为两种：有损压缩( 1 0 s s yc o m p r e s s i o n ) 和无损压缩 ( 1 0 s s l e s s c o m p r e s s i 咖) 。在无损压缩中，关心的是精确重建没有信息丢失的数据， 无损压缩通常被用于文本文件的压缩中。对于有损压缩，允许压缩后产生质量上 的误差。有损压缩机制的优点是可以得到比无损压缩高得多的压缩比，但是它只 能用于可以用近似的数据代替原始数据，而这种相近数据又是容易被压缩的情况。 举例来说，一幅和原图像在视觉上没有区别的图像可以看作是原图像的近似。 任何压缩机制的根本思想都是除去数据中存在的相关性。就图像而言，所谓 相关性，就是能够根据给出的一部分图像数据来判断和推断出与其相关的( 例如 相邻) 其它数据。 实际中存在着很多种数据相关性，这里给出常见的几种。 ( 1 ) 空间相关性。可以根据图像中某一点的像素值推断出其相邻点的像素值。 ( 2 ) 频率相关性。一个信号的傅立叶变换通常是光滑的，这意味着可以根据 某一部分的频率来推断其相邻部分的频率。 ( 3 ) 时间相关性。在数字视频中，在时间上相邻两帧图像的大部分像素的值 变化很小。 无损压缩方法可分为两大类：基于统计概率和基于字典的方法。基于统计概 率的方法基本思想是根据信息论中的变长编码定理和信息嫡有关知识，用较短代 码代表出现概率大的符号，用较长代码代表出现概率小的符号，从而实现数据压 缩：基于字典的方法基本思想是将长度不同的符号串编码成一个一个的新单词， 这些单词形成一个编码表，将输入字符串映射成编码表中的码字，当单词的码字 短于它所代表的短语，就达到了数据压缩的目的。 有损压缩的典型过程是变换编码。基本思想是用一个和原来不同的数学基来 表示数据，在这种新的表示下，数据的相关性能够显露出来或被拆开。在这种新 的基下，大部分的系数都接近零，可以忽略，于是可以将余下的信息存储在一个 较小的数据包中。压缩是通过数据变换，把阀值以下的系数置零，对非零的数据 进行编码来实现的。 常见的无损压缩方法有行程( r u n l e n g t h ) 编码、算术编码、霍夫曼( h u f f r n a l l ) 编码、l z w ( l e m 口e iz i vw e l c h ) 编码：有损压缩方法则有预测编码、正交变换 编码、金字塔编码等等。无损和有损的界限并不是绝对的，主要还是看重构图像 和原始图像是否完全一致。 1 1 2 本课题研究目的和意义 本课题的研究目的是实现指纹图像的感兴趣区域编码，即在一幅指纹图像中 选取指纹特征值作为感兴趣区域，结合s p i h t 方法对指纹图像进行压缩，使其应 用于电子门票系统。 指纹具有唯一性、稳定性、可再生性的特点。按照现代科学乔的结论，人类 人口按6 0 亿计，则需3 0 0 年才可能出现重复的指纹，概率几乎为零；其次，一个 人在母腹7 个月时指纹就已定型，随着年龄的变化，人的相貌体格都在变化，而 指纹却保持不变；另外，只要不伤及真皮组织，指纹即使被磨掉，也会很快长出 来。基于以上特点，指纹在越来越多的领域，如社会安全、办公安全、资讯安全、 金融安全、家庭安全、个人安全等方面得到广泛的应用。 由于指纹图像的信息量大且有很大冗余。在大型的指纹图像数据库中，为节 省空间，对图像进行压缩以有效的对其进行存储、传输已十分必要。以一个4 0 万 人的指纹库为例，若以( 5 1 2 5 1 2 ) 8 b i t 的灰度图像来存储一个手指的指纹， 每人十指，则共需要1 0 0 0 g b 的存储量。如此庞大的数据量，若不经压缩，数字 图像传输所需要的高传输率和数字图像存储所需要的巨大容量将很难保证。美国 联邦调查局自1 9 2 4 年就开始收集指纹，在过去的7 0 年里，他们己经收集了多达 几百万张的指纹图片，同时指纹数据正在以每天3 0 0 0 0 5 0 0 0 0 枚的速度继续增长。 为了解决如此庞大的指纹数据量的存储，节省存储空间必须对指纹图像进行压缩。 由此可知对指纹图像进行压缩是很必要的，本文研究工作有两个方面的意义。 第一，从具体的应用角度看，本文研究成果可以直接应用于电子门票通道检票子 系统和特殊门票的补票。第二，从图像压缩和编码的角度看，本文提出了一种新 的基于s p i h t 算法及指纹图像特征的改进的r o i 编码，此编码通过一种改进的 r o i 技术，使其有别于j p e g 2 0 0 0 的标准的r o i 技术，与j p e g 2 0 0 0 中仅支持矩形 和椭圆形r o i 编码的g e n e r a is c a l i n gb a s e d 方法相比，p b b b s h i f t 方法能够在不编 码r o i 形状信息的情况下，对任意形状的r o i 进行编码压缩。此外这种新方法和 m a x s h i f t 方法一样，在不同的小波子带可以有不同的r o i 定义。但比m a x s h i r 方 法优越的是，p b b b s h i f t 方法通过调整偏移参数能够灵活控制r o i 和b g 的相对质 量。这种灵活性使得解码率固定时，在保证足够的r o i 图像质量的前提下，尽可 能提高了b g 的图像质量。 2 1 2 指纹图像压缩的发展与现状 指纹压缩编码算法的难点在于，提高压缩比的同时要最大化地保留指纹的特 征点。这是因为指纹图像的特征点中包含有待识别指纹图像与指纹库中的指纹图 像进行匹配时所必需的、最重要的特征信息，如果压缩算法改变或遗失了这些信 息，自动指纹识别系统将无法进行正确的指纹匹配过程。 近年来，小波图像压缩编码方法取得了较大突破，主要表现在充分利用小波 塔式分解后图像数据统计属性，改进小波图像数据的组织和表示策略。基于小 波变换的图像编码方法很多，基本上可分为基于点量化和基于块量化两类。 基于块量化图像编码方法主要是应用分形压缩的方法来提高单纯分形的效 率、压缩比和图像的效果。其思路是先将变换后的图像根据不同的频率方向、不 同的尺度分成很多小块，然后对每一小块进行矢量量化编码。 基于点量化图像编码算法包括嵌入零树小波编码( e m b e d d e d z e r o t f e ew a v e l e t ， e z w ) i l ，分层树集划分( s e tp a n i t i o n i n gi nh i e r a f c h i c a l t r e e ，s p i h t ) 1 1 ，形态 学表示( m o r p h o l o g i c a lr c p s e n t a t i o no fw a v e l e t d a t a ，m r 、d ) 和连通成分重要 联系分析( s i g n i f i c 姐c e l i l i l 【e dc o i l n e c t e d c o m p o n e n ta n a l y s i s ，s l c c a ) 1 5 1 ，前两 种基于零树结构，后两种基于数学形态学。二 j m s h a p i 于1 9 9 3 年提出嵌入零树小波编码具有突破性的历史意义，目前 被认为是国际上最先进的图像压缩编码方法之一。e z w 有效地利用了不同尺度的 小波系数所具有的自相似性，通过称为零树的高约束零区域的联合，有效地识别 任意形状的零值区域( 跨子带集合) ：同时通过逐渐逼近地定义系数值来定义零域 以外的范围，每棵零树能有效地被它的根符号所表示。零树编码不仅速度快、效 果好，而且在不损失编码效率前提下能产生嵌入式码流，支持多码率解码；此外 在编解码中也无需训练码本和预先存储码书，实现比较简单。e z w 方法侧重于对 小波系数沿方向子带的纵深衰减规律的利用，其成功之处在于注意到了零值小波 系数具有方向零树结构，使得大量的树结构零系数只用一个零树根来表示，但仍 存在许多不能被包含入高结构化零树的零系数，这些零系数需要高代价表示。 e z w 利用子带间相似性对小波变换域大量零系数和小幅值系数进行了有效地 组织和表示，取得了优于j p e g 的效果，但也有一定的缺陷，存在着改进的可能性。 在e z w 中，若根结点为重要系数而其后代均为非重要系数时还要分别考察其子 结点，并分别进行编码。s a i d 等人提出的s p i h t 很好地解决了这个问题，在相同 码率下，峰值信噪比有了大幅度提高。s p i h t 改进了e z w ，它划分跨子带树结构 为三个部分：树根、根的子结点和根结点的无子结点后代。最后一部分占整个小 波系数的绝大部分( 约占总数的3 4 ) 。当一个系数为重要值时，e z w 分别编码表 示所有的4 个子系数，甚至所有子系数非重要且无后代。相反，s p i h t 把所有非 重要且无后代系数作为一个集，并用一个单独的符号来表示。这个策略作用在小 波变换图像上，峰值信噪比可提高o 3 o 6 d b ，表明s p i h t 比e z w 更有效地利 用了子带间的依赖性。s p i h t 具有比e z w 更高效的重要性映射编码，它定义了 三种序列：l i p 一非重要象素点序列；l i s 一非重要集序列；l s p 一重要象素点序列。 树被定义为d 和l 两种类型。d 型的树需要检查所有的后代的重要性，而l 型 的树则检查除去直接后代的所有后代。 1 9 9 9 年s e r g i ods e e t t o 等提出有别于零树思想体系的m r w d 算法，该算 法通过量化策略的简单改变，生成高效的嵌入式或固定码率的码流。它的一个重 要特征就是形态集的形状被小波系数隐含编码，因此能有效地防止直接形状描述 所需要的大量比特位，并在执行过程中除去了一些噪声，重建图像视觉效果更好。 与e z w 相比，m r w d 有效地利用了信号能量在小波域内分布集中的特点。即重 要系数予带内聚集。如果一个小波系数被判别为重要系数，则称在其“邻域”内 具有很高概率的系数为重要系数。其编码算法主要特点是对小波域各子带进行光 栅扫描，并利用形态进行聚类连通操作。通过这个过程，小波系统被划分成4 个 具有不同统计特性的模型，最后根据不同统计模型进行自适应算术熵编码。m d w d 通过利用结构元素来控制簇的形状和大小的形态学膨胀操作，从子带内的重要系 数直接建立起非规则形状的簇结构，避免了e z w 中“孤立零”的高代价表示，得 到了优于e z w 的效果，但仍需要表示每个簇内部及边界的非重要系数。这种基于 形态学图像编码算法侧重于对重要小波系数在子带内的横向聚类特性的利用。 s l c c a 算法提出了新的数据编码策略，即增强型m r 、d ，它不仅利用了子带 重要系数的聚集，同时利用了子带间系数的父子信赖关系。s l c c a 算法关键在于 小波分解、子带内重要系数连通部分分析、子带间重要性联系记载和重要系数值 的位平面自适应编码等方面。s l c c a 通过利用子带内重要系数聚集生成连通部分 ( 簇) 。由于小簇对图像效果不会产生明显影响，并且这些簇的非重要重要系数比 例较高，因此忽略小簇可避免高编码代价，提高率失真，产生更好的效果。与其 它图像压缩算法一样，s l c c a 最后一步涉及到熵编码。s l c c a 选择自适应算术 编码，但与其它算法不同，它的上下文被用来决定概率模型，对变换图像的每个 位平面分别进行编码。子带内最大值决定子带每个重要系数幅值转变为二进制所 占的比特位。 1 9 9 2 年联合图像专家组( j o i n tp h o t o g r 印h i ce x p e r t sg r o u p ，j p e g ) 推出了基 于离散余弦变换( d c t ) 的j p e g 静止图像压缩标准( i s o1 0 9 2 8 ) 嘲。该压缩标准 一经推出就因为其优越的压缩性能而得到了各方面的认可，成为迄今为止应用最 为广泛的图像标准之一。但随着多媒体技术和网络通讯技术的迅猛发展，人们对 图像的压缩性能、处理灵活性、功能性等各方面也有了进一步要求。现有的j p e g 图像压缩标准已经不能完全满足用户的需求。人们迫切需要一种压缩效果更加优 4 越，支持更多图像格式，并能够提供更多新特性的静止图像压缩格式。于是联合 图像专家组2 0 0 0 年1 2 月推出了j p e g 2 0 0 0 静止图像压缩标准，而在此标准中包括 感兴趣区域编码r 0 l ( r e g i o no f i n t e r c s t ) 川。 基于感兴趣区域的图像编码技术是近来出现的一种新兴的方法。随着多媒体 技术的不断发展，网络用户的飞速增加，对高效率的图像编码技术要求越来越高。 在数字图像处理过程中一般要产生很多的包含图像数据的大量文件，它经常需要 在不同的用户及系统之间互相交换，这就需要有一种有效的方法来存储及传递这 些大量文件。而且在很多情况下，传输的图像中只有一小块区域对用户是有用的。 对这些有用的区域，采用低压缩比，而此区域之外的区域，则采用高压缩比，在 保证不丢失重要信息的同时，又能有效压缩数据量，这就是基于感兴趣区域的编 码方案所采取的策略。它是静止图像压缩的新国际标准j p e g 2 0 0 0 的及其重要的优 点。随着标准制定的深入，感兴趣区域的编码理论及方法的研究将会越来越显示 出它的重要型和优越性。在r o i 编码技术中，图像被分割成若干个感兴趣区域和 一个背景区域，要对不同的区域采用特定的编码策略。现有的编码策略分为两类： 一类是对不同的区域采用不同的编码算法：另一类是对不同的区域采用完全相同 的编码方法，但会根据区域的重要程度不同，决定编码的比特率分配，与其它图 像处理技术一样，r o i 编码技术既能够被应用于静止图像压缩，也能够被应用于 序列图像压缩，由于对静止图像的处理方法相对简单，现在对r o i 编码方法的研 究成果大多集中于此。 1 3 本文的主要研究内容 本文主要研究基于指纹压缩与识别在电子门票系统中的应用。分析了静止图 像r o i 编码中的一些关键技术，主要包括r o i 位平面偏移方法、r o i 系数标定方 法和基于r o i 的s p i h t 编码算法，其中对r o i 位平面偏移方法进行了重点阐述。 在分析已有方法优缺点的基础上，提出了一种新的指纹图像压缩算法一基于 s p i h t 算法及指纹图像特征的改进的r o l 编码，使其在具备更高的压缩比的同时， 拥有更好的恢复图像效果并能有效保留指纹图像的关键点信息实现指纹的压缩编 码。 结合指纹压缩与识别设计了指纹电子门票系统，主要包括系统总体设计与实 现、验票中心子系统设计与实现。全文共由五章组成，每章的主要内容如下： 第一章绪论。主要介绍了图像压缩技术和研究目的及意义，随后讲述了指纹 图像压缩的发展及研究现状。 第二章相关技术分析。主要介绍了指纹识别技术的工作原理，分析了s p i h t 算法原理和r o i 编码技术。 第三章基于r o i 的s p i h t 编码。最后结合指纹特征值提出了新的指纹图像 压缩算法一基于s p i h t 算法及指纹图像特征的改进的r o i 编码。 第四章指纹电子门票系统设计与实现。提供了一种开发指纹电子门票系统的 总体设计方案和基于指纹压缩与识别的验票中心子系统的设计，最后给出了系统 总体框架和验票中心子系统的实现，具体介绍了其中指纹补卡这个功能界面，说 明了指纹压缩在模块中的重要性，接着给出了验票中心子系统的实现，详细说明 了游客过闸时的首次过闸和以后的过闸情形下的验票。 最后对全文进行总结和提出进一步需要解决的问题。 6 第二章相关技术分析 指纹识别技术主要涉及读取指纹图像、提取特征、保存数据和指纹比对等。 指纹识别整个过程具体可以细分成下面几个步骤：原始图像输入、预处理、指纹 特征提取、指纹识别和识别结果输出。如图2 1 所示。 图2 1 指纹识别流程图 2 1 指纹图像的获取 取像设备直接关系到指纹图像的质量和识别系统设计中的方法选择，大致分 为：光学、硅晶体传感器以及超声波取像等。 光学取像依据的是光的全反射原理( f t i r ) 。光线照到压有指纹的玻璃表面， 反射光线由c c d 获得，反射光强度取决于压在玻璃表面指纹的脊和谷的深度和皮 肤与玻璃间的油脂。光线射到谷后反射到c c d ，而射到脊后则不反射到c c d 。 晶体传感器技术最重要的弱点在于， 感器有时会取不到图像，甚至会被损坏， 而影响了使用寿命。 它容易受到静电的影响，这使得晶体传 另外，它们并不像玻璃一样耐磨损，从 超声波扫描被认为是指纹取像技术中非常好的一类。很像光学扫描的激光， 超声波扫描指纹的表面。紧接着，接收设备获得其反射信号，由于指纹表面脊和 谷的声阻抗不同从而造成接受到的超声波的能量不同，测量它的范围、脊的深度， 最后得到指纹的灰度图像。不像光学扫描，积累在皮肤上的脏物和油脂对超声波 获得的图像影响不大，所以这样的图像是实际脊地形( 凹凸) 的真实反映。 2 2 指纹图像预处理 经指纹扫描器采集的原始指纹图像不可避免地具有对比度不统一、含有大量 噪声等缺点，为了降低后续特征提取算法的复杂度，提高特征提取的效率，预处 理过程必不可少【。t ，m 。 根据特征提取方法的不同，系统对预处理的步骤和要求也不一样。目前，从 大的方面分，主要有两类特征提取方法：一类是直接从原始指纹图像中提取统计 性特征1 ；另一类是从预处理得到的指纹骨架图像中提取细节点特征【1 2 l 。前一类方 法对预处理要求比较少，只要将图像增强一下就可以。后一类方法要求预处理部 分做大量的工作，一般包括求分割、方向图】、图像增强l 、平滑、二值化1 1 5 】、细 7 化等步骤l ，最后得到一幅纹线宽度为单像素的二值图像。在当前的应用系统中， 后一类方法要比前一类应用得多一些，因为后一类方法把工作的难点分散到两步 操作中，简化了特征提取算法，且处理结果容易控制。 图像预处理步骤如图2 2 所示。 图2 2 指纹图像预处理过程 2 3 特征值提取及匹配 经过前面部分对指纹图像的预处理，指纹图像己经基本满足了特征值提取和 匹配的要求。指纹特征值的提取和匹配是指纹识别的一个关键技术，指纹匹配的 结果就是指纹识别的最终结果。 2 3 1 特征值提取 1 特征值的分类 用于分类和识别的指纹特征分为两类：总体特征和局部特征。 总体特征指那些用肉眼直接就可以观察到的特征，如图2 3 所示。包括纹形、 核心点、三角点等。其中纹形有右旋箕( r i g h t l o o p ) 、左旋箕( 1 e f t l o o p ) 、拱( a r c h ) 、 双旋箕( t w i ni o o p ) 和涡( w h o r l ) 。在美国联邦调查局( f b i ) 提出的细节点坐标 模型中，利用的是脊端点( 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 7 】，它们 被统称为细节点。细节点常用的以下特性描述：类型( 脊端点还是脊分叉点) 、位 置、方向等，如图2 4 所示。 右旋箕左旋箕拱 涡双旋箕 图2 3 指纹总体特征 8 叉点 图2 4 指纹图像特征示意图 局部特征指指纹图像中的细节特征。指纹纹路并不是连续的、平滑的，而是 经常出现中断、分叉或打折，这些端点、分叉点和转折点就成为细节特征，就是 这些细节点提供了指纹唯一性的确认信息。 局部特征是指纹上节点的特征，指纹上的节点有以下几种主要特性： ( 1 ) 特征点类型如图2 5 所示。 _ 一= = o 一一 l 图2 5 指纹特征点类型 终结点( e n d i n g ) 一纹路的末端。 分叉点( b i f h r c a t i o n ) 一条纹路在此分开为两条或更多的纹路。 分歧点( r i d g ed i v e r g e e ) - 两条平行的纹路在此分开。 孤立点( d o to ri s l 觚d ) 一条特别短的纹路，以至于成为一点。 环点( e n c l o s u r e ) 一一条纹路分开成为两条之后，立即合并成为 一条，这样形成的一个小环称为环点。 短纹( o r i e m a t i o n ) 一一一端较短但不至于成为一点的纹路。 ( 2 ) 方向( o r i e n t a t i o n ) 一节点可以朝着一定的方向。 ( 3 ) 曲率( c l 肼a t l l r c ) 一描述纹路方向改变的速度。 ( 4 ) 位置( p o s i t i o n ) 一节点的位置通过( 薯y ) 坐标来描述，可以是绝 对的，也可以是相对于三角点或特征点的。 2 特征值的提取 指纹图像的特征提取是按区进行的，即先将图像划分为若干个区，每个区确 定若干个特征，然后就可以对每个区直接进行特征提取。区的数量视定位的精确 度及处理的效果而定，一方面，区的数量不宜过多，否则一旦定位误差较大，就 会引起各区参数混乱，造成误判；当然，也不宜过少，它可造成整个系统的识别 率下降。例如，假定划分为8 个区，每个区平均有1 2 个特征，则可分出1 2 8 个单 一确定的指纹。若划分3 2 个区，尽管每区的平均特征个数减少，如4 个特征，但 仍能分出4 3 2 个单一确定的指纹。区域确定后( 如划分为3 2 个区) ，每区的端点 9 和分叉点的特征数之和约为三个，据此，在理论上可分出3 3 2 个单一确定的指 纹，若再加上每区的累加方向数，就足以满足一般指纹识别的要求。把各区的特 征量按序构成“指纹字”，用以表示给定指纹，并以此作为对指纹库进行检索的基 本单位。 2 3 2 特征值匹配 基于细节的匹配算法是最著名、使用最广泛的指纹匹配算法，其严格的类推 方法与法院专家比较指纹的方法非常相似，这也使得通过这种方法得出的身份验 证在几乎所有国家的法律条文中得到承认，下面描述了这种算法的思路。 1 细节特征的校准，用 p = ( ( 茚，茆，钟) 2 ( ，诺) 7 ) ( z 1 ) 表示模板中的m 个细节点，用 q = ( ( 坪，卯，砰) 7 ( x ，y 2 ，爵) 7 ) ( z 2 ) 表示输入图像中的n 个细节点。 对应模板点集中的每一点日( 1 f m ) 和输入点集中的每一点9 ( 1 ，) ， 定义r o t a t e 【i 】d 】为将p f ，9 当作参照点对时，从输入图像到模板图像的旋转角度。 如果是匹配点，那么两条脊线必然相似到一定程度，是o 到3 6 0 之间的值，否则， 如果不是对应点时，不能做参照点，则是一个无效值。 如果p ，q ，是相同类型的点，也就是说它们都是脊线末梢或者都是脊线分支， 则它们之间的相似性用差异来度量，差异越小越相似，公式如下： 1工 掘棚= l 尺( 4 ) 一，( z ) 1 ( 2 3 ) r 厶一i i 。 厶卢0 1上 口，础= l 尺( q ) 一，( 口f ) i ( 2 4 ) 口，喀伦2 7 乙l 代【q ) 一，t 口f 川 ( 2 4 ) 上一i = 0 其中三是脊线中的点个数，r ( 西) 和，( 西) 分别表示从脊线r 到，上的点f 到对应细节点的距离，r ( 研) 和，( 口f ) 分别表示连接脊线r 与，上的点f 与对应 细节点的直线同对应细节点的方向的夹角。如图2 6 所示。 如果两条脊线之间的差异a n g e l 和d i s t a n c e 同时小于阀值，则认为两条脊线是 相似的，对应的央角为两细节点的方向之差。 r o t a t e i 】【j 】= d i l t e m p d i l i n ( d i r t e m p 和d i r - i n 分别表示b ，9 的方向) 否则 认为两个点不是对应的细节点，将r o t a t e 【i 】啪设为一个无效值。 l o 暴 扣 x 轴 图2 6 输入脊线与模板脊线的校准 2 细节特征点集的成串 把得到的一对匹配细节点作为各自所在的点集中的坐标原点，并将各自点集 中其余点相对于坐标原点转化成为极坐标形式，如下： 汁 ( 2 5 ) 公式( 2 5 ) 中，( 一，咒，包) 1 表示待转换的细节属性，( ，y 7 ，矿) 1 是参照点的 坐标属性。，f 表示转换成极坐标后所对应的极径，白是极角，而口，表示在极坐标中 所对应的局部纹线方向。 对于输入和模板点集中的每一个点，得到其对应的r o t a t e 【- 】d 】的值，如果不是 一个无效值，就把它们作为参考点，并把两个集合中的所有点都相对于它们转化 为极坐标；否则另选一对，判断是否是参考点。 将所得到的极坐标形式的特征点集合按照其极角递增的方向重新排列，得到 一对匹配串；并对这对串进行匹配，得到一个匹配分数；对所有有效的参考点对 进行同样操作，得到的最高匹配分数作为本次匹配的最终匹配分数。为了解决指 纹采集时间上的不一致问题，引入了界限盒( b o u n d i n gb o x ) i l - 】。 界限盒是包围模板细节点的一个虚拟的“平行四边形”，四个边表示如图2 7 所示，柚g l e - h i g h 表示角度的上界，锄g l e _ l o w 表示角度的下界；r a d i u s _ h i g l l 表示 而矧 一一厂li扩 厅叫 极径的上界，r a d i u sl o w 表示极径的下界。对模板指纹特征点集中的每一个特征点， 选取它周围的一个矩形区域作为它的限界盒，只要变换后的待识别指纹的特征点 落在这个区域之内，且方向基本一致、类型相同，就可以认为这两个特征点对是 一对匹配的特征点。最后，统计所有相匹配的特征点数目，若匹配的特征点数大 于设定的阙值，则认为待测指纹和模板指纹来自同一手指。否则，认为来自不同 手指。 2 4s p i h t 编码 图2 7 界限盒 对给定的原始图像尸的像素为m 。可以用任何的小波滤波器组7 将像素变换 为小波系数。价构成变换图像c ，假设变化系数c ，已经存放在存储器中。对系数 进行排序，排序信息包含在数组聊中，这样数组元素埘( 七) 包含了系数c ，的坐标 ( u ) ，且对于所有的七，有1 ( i ) i ic ，( 川) i 。如表2 1 中列出了1 6 个系数，都是 1 6 位数，最高有效位是符号位，而其余1 5 位( 白上而下，编号从1 4 到o ) 是幅 值。编码器采用循环方式，每次迭代都进行一次排序和一次细化。由此可理解 s p i h t 解码器的主要步骤： 第一步给定一幅待压缩图像，用任何适当的小波滤波器对其做小波变换，将 其分解成变换系数勺，并用固定的位数表示系数，另珂= l l o g ：m 觚( c 叫) j 。 第二步排序。传送满足条件2 ”i 钆“2 ”的系数c ，。，的个数，然后再传送 这些系数的，对坐标和，个符号。 第三步细化。传送满足lo “l 2 ”1 的系数的第玎个最高有效位，这些系数通过 前面的排序已被选中( 但不包括刚刚进行的一次排序) 。 第四步迭代。n 减l ；转到第二步执行。 在实际中，图像可能有l k l k 或者更多的像素，系数个数可能超过l o o 万， 故对所7 f 系数进行排序会很慢。s p i h t 没有对系数进行排序，而是利用了这样一 个事实：排序时，一次比较两个元素，每次比较都会得到一个简单的是或否。s p i h t 实际所用的算法就是基于这样一个认识：实际上不需要对所有系数排序。每次迭 1 2 代中，排序的主要任务是选择那些满足2 ”l 。“l 2 ”1 的系数。这个任务可以分成 两部分：对于一个给定值栉，如果系数。“满足i 。口l 2 ”，则我们说它显著；否则， 认为它不显著。排序要决定哪些显著系数满足。“ 5 2 ) ，其中5 ，= 5 即= 3 ， 它们的和等于r o i 所有系数的最人位平而数与j p f g 2 0 0 0 中m a x s h i f t 和 s c a l e _ b a s e d 次移动r o l 系数的全部位平面不旧，逐个4 平面提升法将r 0 1 系数 和b g 系数分别划分成两部分， 5 ，和比用控制每部分位甲而的提升。 假定最t 而的位平面为1 ，接下来的是位平面2 ，依玖类推，i | l | j 编码他平面的 过程如卜 所述。 对于任意属fr o i 系数的位半哂6 ： 如果6 j ，不提升； 如果j ， 即，则提升到位平而+ ? 十6 。 图2 1 l 运个位提升法示意图 在解码端，对于任意非零系数，首先通过检查位平面的最重要位( m o s t s i g n m c a n tb i t p l a n e ，m s b ) 来判断它属于背景区域系数还是r o i 系数。和r o i 相关的位平面系数满足公式( 2 ，8 ) 。 曰加_ r ：川6 s o r6 邓j + 2 b 拓1 ，2 ，印】 ( 2 8 ) 如果小波系数的m s b 位平面6 省月。f ，那么它必然属于r o i 系数，反之则属 于背景区域系数。按此位平面被还原到原始的位置，过程和编码端的提升过程相 反。当s j = 0 时，此方法就便成了m “s h i r 方法。 逐个位平面提升法具有最大平移法的优点。若设定趵= o ，s j = m a x ( m b ) ，其中 m a 】【( m b ) 是r o i 系数所在位平面的晟大值，则逐个位平面提升法就等同于最大平移 法，也就是说，最大平移法也是逐个位平面提升法的一个特例。而相对于最大平 移法，逐个位平面提升法又具有灵活选取平移因子的优点，可以调整r o i 系数干u 背景区域系数的相对重要性。例如，用户可以选择一个s ，值使r o i 达到足够好的 图像质量，之后就可以开始编码，传输一些重要的背景区域系数，使其优先于不重 要的r o i 系数。但是和最大平移法一样，当图像有多个r o i 区域时，逐个位平面 提升法也只能赋予所有r o i 同样的平移因子，无法调整它们编码，传输的优先权。 在实现复杂度上，逐个位平面提升法和最大平移法一样，不需要对r o i 的形状信 息进行编码和传输，但它需要把编码懈码位提升到特定的位平面上，所以比最大 平移法复杂一砦。它们的缺点是：与j p e g 2 0 0 0 中的r o i 编码定义不兼容，并且 无法按不同优先级对多个r o i 进行编码。 ( 4 ) 摄重要平移法( m o s ts i g n i 疗c a l l t b i t p l a n es h j f l m e t h o d ，m s b s h i n ) 是由 美国俄克拉马州州立大学的l i j i el i u 等人提出的m l 。它的理论基础是，在低编码 比特率时，图像的r o i 要求保持比背景区域更好的质量，而在高编码比特率时， r o i 和背景区域在质量要求上的差别就不是很大了。因此可以选择r o i 系数所在 位平面的一部分作为最重要位平面，来调整r o l 和背景区域的相对重要性。也就 是说我们只需要提升r o i 系数的部分位平面，而不是像最人平移法那样，提升 所有r o i 系数的位平面。 m s b 章；羹0 0i 图2 1 2 最重要平移法 如图2 1 2 所示，所有r o i 系数的位平面被分成了两部分：上面的最重要伉平 面( m s b ) 和剩下的位平面。在编码端，r 0 1 系数的晟重要值平面并不被提升， 而是降低剩下的不重要的位平面到背景区域系数所在的位平面。设把r o i 系数的 5 ( 图中s = 4 ) 个不重要位平面和背景区域系数一起下移，则r o i 系数剩下的肌咖 个最重要位平面将高于所有的背景区域系数位平面和不重要r o i 系数位平面。 n 。满足 一j 帆一s j - ； ( 29 ) ”“一1oj 慨； m s b s h i n 方法的优点是可以在不传输任何形状信息的前提下，实现对任意形 状的r o i 编码，而且能够控制r o i