（信号与信息处理专业论文）指纹的匹配方法研究.pdf

摘要 指纹识别技术作为生物识别技术的一种，以其特有的唯一性和不变性，成为当前最 可靠的个人身份识别技术。指纹匹配作为指纹识别的核心技术之一，是自动指纹识别系 统设计中的热点和难点。 本文在前人工作的基础上，完成了如下工作 ( 1 ) 在指纹匹配的前期处理部分，选择并实现了一套快速、高效的指纹图像预处 理、特征提取和后处理算法，为后续的指纹匹配处理奠定了基础。 ( 2 ) 指纹匹配是本文的重点，在该部分对原有算法进行改进，提出了一种基于指 纹全局星型结构特征的分步匹配算法。针对局部特征向量构造简单、易受局部形变干扰 的问题，在第一步匹配中采用全局向量的同时，在此向量中增加了邻域特征点与中心特 征点所在纹线方向夹角等反映纹线走向等参量，提高了匹配的准确性；针对固定限界盒 门限造成误匹配率较高的问题，在第二步匹配中运用自适应门限，进一步提高了匹配的 正确率。 ( 3 ) 在指纹检索部分，提出了一种新的基于星型结构的指纹检索方法，一方面可 以有效地进行指纹检索，排除不合格的指纹，使匹配速度得到显著提高；另一方面可以 实现多维结构检索，满足不同系统的要求。 本文在实际微机指纹识别系统上实现了上述全套算法。实验结果表明，该套算法快 速、有效，结果令人满意。 关键词：自动指纹识别系统：指纹匹配；指纹检索；全局结构特征；自适应门限 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 na sab i o m e t r i ci sb e c o m i n go n eo ft h em o s tr e l i a b l ep e r s o n a a u t h e n t i c a t i o nt e c h n o l o g i e sd u et ot h eu n i q u e n e s sa n d i m m u t a b i l i t yo ff i n g e r p r i n t s a so n eo f t h e k e yt e c h n i q u e s ，f i n g e r p r i n tm a t c h i n g i ss t i l lt h ef o c u si nt h e d e s i g no fa 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 s t h em a i nw o r k s g i v e n i nt h e p a p e r a r ea sf o l l o w s ： ( 1 ) s e l e c ta n di m p l e m e n tas e t o ff i n g e r p r i n t p r e p r o c e s s i n g ，f e a t u r e e x t r a c t i o na n d p o s t - p r o c e s s i n ga l g o r i t h m s ，w h i c h i s p r o v e df a s t a n de f f e c t i v e ，a n di st h eb a s i so ft h e f i n g e r p r i n tm a t c h i n g ( 2 ) p r o p o s eat w o s t e pg l o b a ls t a r s t r u c t u r e b a s e dm a t c h i n ga l g o r i t h mf o rf i n g e r p r i n t i d e n t i f i c a t i o nb a s e do i le x i s t i n gm e t h o d s i nt h ef t r s ts t e po ft h ea l g o r i t h m t h eg l o b a ls 8 r s t r u c t u r ef e a t u r ev e c t o ri sc o n s t r u c t e d t h er i d g ed i r e c t i o na n dt h es t r u c t u r a l r e l a t i o n s h i p p a r a m e t e r sa r ea d d e di n t ot h ef e a t u r ev e c t o r a n da d a p t i v et h r e s h o l d sa r eu s e di nt h es e c o n d s t e p ，w h i c hi m p r o v e st h er o b u s t n e s so f t h em a t c h h a 唱a n dm a k e s t h er e s u l tm o r ea c c u r a t e ( 3 ) p r o p o s e an o v e l f i n g e r p r i n ti n d e x i n ga l g o r i t h m b a s e do ns t a r s t r u c t u r e t h i s a l g o r i t h m c a na c c e l e r a t et h e p r o c e s s o fm a t c h i n g g r e a t l yb yr e j e c t i n g t h em i s m a t c h e d f i n g e r p r i n t se f f i c i e n t l y i t c a l la l s or e a l i z em u l t i d i m e n s i o n a l i n d e x i n g a n dm e e tt h e r e q u i r e m e n t so f d i f f e r e n ts y s t e m s a j lt h ep r o p o s e da l g o r i t h m sh a v eb e e ni m p l e m e n t e do naf i n g e r p r i n ti m a g e p r o c e s s i n g s y s t e m t h ev a l i d i t yo ft h ea l g o r i t h m si sc o n f i r m e db yt h ee x p e r i m e n tr e s u l t sg i v e n 访t h e p a p e l k e y w o r d s ：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 l e a r i o ns y s t e m ；f i n g e r p r i n tm a t c h i n g ； f i n g e r p r i n ti n d e x i n g ；g i o b a is t r u c t u r ef e a t u r e ：a d a p t i v et h r e s h o i d 指纹的匹配方法研究 1 绪论 对于当今日益频繁的电子信息交流社会，拥有准确无误的自动身份识别显得越来越 重要。传统意义上的使用“用户d + 密码”的个人身份识别系统，在实际应用中已经 不够安全，经常会被非法盗用或滥用。随着科技的发展，依靠人的身体特征来进行身份 验证的生物识别技术很好地解决了这一问题。指纹识别技术作为生物识别技术的一种， 以其特有的稳定性、唯一性和方便性，被愈来愈广泛地应用在安全、认证等身份识别领 域。虽然指纹识剐发展迅速，但是由于其中许多核心技术没有公开，以及社会的不断发 展对系统的性能提出了更高的要求，因此从事指纹识别技术的研究具有重要的理论意义 和实用价值， 指纹匹配是指纹识别的核心技术之一。它在指纹图像预处理和特征提取之后，是自 动指纹识别系统的最后一步，也是非常关键的一步。指纹匹配结果的正确与否将最终决 定整个自动指纹识别系统的性能好坏。但是由于输入指纹和模板指纹之问，不可避免的 存在不同程度的平移、旋转、尺度伸缩和增加虚假特征等差异，指纹匹配是自动指纹识 别系统设计中的热点和难点。 本章首先对生物识别技术与指纹识别技术，以及指纹识别中的一些关键技术做简要 综述，最后给出本文的主要研究内容和结构安排。 1 1 生物识别技术和指纹识别技术 a 生物识别技术 生物识别技术【卜4 l 是利用人体的生物特征来进行身份验证的一种识别技术。由于人 的生物特征具有人体所固有的不可复制的唯一性，因此，这一生物特征密钥是无法复制、 失窃或遗忘的您既可不必携带大串的钥匙，也不用费心去记或更换密码。系统管理员 更不必因忘记密码而束手无策。理论上说人的任何生理或行为特征都能够用来确认人 的身份，只要满足以下特性：普遍性，即是所有人都拥有的特征；唯一性，即没有其他 人拥有此特征；稳定性，即此特征不随时间或空间的变化而变化：可获取性，即能对此 特征进行定量处理。 目前，常用的生物识别技术有以下五种： ( 1 ) 人脸识别技术 人脸识别技术是人们最早使用的生物识别技术之一。该技术通过比较面部的某些特 征部位的大小和关系，例如鼻子的长度和两眼之间的距离，或是对面部区域内的十几个 点进行分析，将这些点排列成一幅图案，并与数据库中存储的图像进行比较。但是这种 系统的抗干扰性较差，对双胞胎的鉴定仍然无能为力，而且发型、肤色、胡子或者胖瘦 的变化、以及是否带眼镜都会影响系统的正确识别。 指纹的匹配方法研究 ( 2 ) 虹膜识别技术 虹膜识别技术利用世界上任何两个人的虹膜都是不一样的特征来进行身份鉴别。即 使是双胞胎，虹膜也各不相同，而且人的虹膜在一岁之后便不再发生变化。识别系统利 用一台标准摄影机对用户的眼睛进行扫描，然后将扫描图像转化成数字信息与数据库中 的资料核对，以验证身份。但是目前的虹膜识别系统的价格还比较昂贵。 ( 3 ) 掌纹识别技术 掌纹识别是基于手掌几何学中的这样一个事实：几乎每个人的手的形状都是不同 的，而且手的形状在人达到一定年龄之后就不再发生显著变化。当用户把他的手放在手 形读取器上时，手的二维图像就被捕捉下来。接下来，对手指和指关节的形状和长度进 行测量。映射出手的不同特征是相当简单的，不会产生大量数据集。但是，即使有了相 当数量的记录，也不一定能够将人准确区分开来，因为手的特征是很相似的。与其他生 物识别技术相比，掌纹识别技术不能获得最高程度的匹配准确率。 ( 4 ) 语音识别技术 语音识别是对说话者声音和语言学的综合运用，是一种行为鉴定学它并不对词语 本身进行辨识，而是通过分析语音的特征，例如发音的频率等，来识别说话的人。语音 识别技术使得人们可以通过说话来控制能否出入限制性的区域。举例来说，可以通过电 话拨入银行、购物或使用语音邮件。虽然语音识别比较方便，但由于非人性化的风险、 远程控制和低准确率，它并不十分可靠。一个患上感冒的人就有可能被错误的拒识，而 无法使用该语音识别系统。 ( 5 ) 签名识别技术 签名识别和语音识别一样，也是一种行为鉴定学。人们都很熟悉在银行的账单上签 名，以此作为身份的标志。签名识别是这样一个过程：测量图像本身以及整个签名的动 作在每个字母以及字母之间不同的速度、顺序和压力。使用签名识别更容易被大众接受， 但是随着经验的增长、性情和生活方式的改变，签名也会随之而改变。为了处理签名不 可辟免的自然改变，不得不在安全方面做出妥协。 ( 6 ) 指纹识别技术 据统计，按人口6 0 亿计算。需3 0 0 年才可能出现重复的指纹，概率几乎为零：其 次，一个人在母腹7 个月时指纹就已定型：随着年龄的增长，人的相貌和性格都在变化， 但指纹却保持不变；另外，只要不伤及真皮组织，指纹即使被磨掉，也很快会长出来。 指纹识别系统就充分利用了上述指纹的唯一性、稳定性和再生性等特点，通过比较输入 指纹和预先保存的模板指纹特征，进行身份验证。 指纹识别技术的发展得益于现代电子集成制造技术和快速可靠算法的研究。尽管指 纹只是人体皮肤的- - d , 部分，7 但可用于识别的数据量相当大，对这些数据进行比对不是 简单的相等与不相等的问题，而是使用需要进行大量运算的模糊匹配算法。现代电子集 成制造技术使得人们可以制造相当小的指纹图像读取设备，同时飞速发展的个人计算机 2 指纹的匹配方法研究 运算速度提供了在微机甚至单片机上进行两个指纹比对的可能。与其他生物识别技术相 比，使用指纹识别方式的优点在于其可靠、方便，并易于被接受，你只须花微不足道的 时间去用指纹采集器获取指纹图像，就可以验证身份。而且在所有生物识别技术中，指 纹识别技术是对人体最不构成侵犯的一种技术手段。 b 指纹识别技术 人们使用指纹识别身份已经有很长一段时间了口j 。考古证实，公元前7 0 0 0 年到6 0 0 0 年以前，在古叙利亚和中国，指纹作为身份鉴别已经开始应用。考古发现，在这个时代， 一些粘陶器上留有陶艺匠人的指纹，中国的一些文件上印有起草者的大拇指指纹等。 虽然当时指纹的一些特征已经被人们认识和接受，但却不能被证明。尽管如此，指纹己 被人们使用。 现代指纹识别技术起源于1 6 世纪晚期 6 1 。在1 6 8 4 年，英国植物形态学家g r e w 发 表了一篇论文，阐述他关于指纹的脊、谷和孔状结构的系统研究驿】，这被认为是指纹研 究方面的最早一篇科学论文。从那时起，许多后来者在指纹研究方面做出了努力。1 7 8 8 年，m a y e r 对指纹的结构做出了详尽的描述，并对许多指纹特征下了定义 6 】。1 8 8 0 年， f a u l d 第一次科学的阐述了指纹的稳定性与唯一性【5 】，这些发现奠定了现代指纹识别技 术的基础。在1 9 世纪晚期，g a l t o n 引发了指纹的深入研究，他在1 8 8 8 年介绍了指纹的 细节特征【5 】。1 8 9 9 年，h e n r y 做出了又一次重要进步，他建立了著名的“h e n r y 系统” 【5 】用于指纹分类。直到2 0 世纪早期，指纹上携带的信息才被完全理解，有关指纹的生 物特性叙述如下： 指纹在手指上呈现出脊、谷相间的图案，其中脊的颜色较，谷的颜色较浅，如图 1 l 所示。不同的指纹有不同的脊、谷特性。 图1 1 指纹的脊、谷特性 f i g 1 】f i n g e r p r i n tr i d g ea n df i n g e r p r i n tv a l l e y 虽然指纹的结构类型各不相同，但却可以进行有效地分类和识别。 指纹的结构与特征是永恒不变的。 指纹的匹配方法研究 这一研究成果使得指纹识别技术在犯罪鉴别中得以正式应用，并被法律正式强制接 收成为一种有效的个人身份识别方法，并且成为一项标准的法庭程序。2 0 世纪6 0 年代， 由于计算机可以有效地处理图形，人们开始着手研究利用计算机来处理指纹。从那时起， 自动指纹识别系统a f i s 在法律方面的研究和应用在世界许多国家展开。2 0 世纪8 0 年 代，个人电脑、光学扫描这两项技术的革新，使得它们作为指纹取像的工具成为现实， 从而使指纹识别可以在其他领域中得以应用。 现在，指纹在越来越多的领域得到了广泛的应用，被认为是身份认证的物证之首。 ( 1 ) 信息安全领域：如个人计算机系统使用指纹进行验证，网上银行、电子商务的安 全交易等；( 2 ) 数据通信领域：如指纹识别技术作为生物密钥可对加密传输数据进行二 次加密，增加安全性；( 3 ) 公共安全方面：如指纹门锁、汽车门锁、个人指纹身份证等； ( 4 ) 金融安全方面：如指纹智能卡、指纹终端、指纹保险箱、指纹储蓄卡、大额取款 客户身份确认等；( 5 ) 其他方面：如指纹考勤、个人医疗档案管理、保险受益人确认、 海关及民航快速通关认证等。 随着许多指纹识别产品的开发，指纹识别技术的普及应用已经指日可待。但是，目 前指纹识别技术仍是国内外科研人员研究的热点，主要原因有：市场上的指纹产品有很 强的针对性，只能在某一专门系统得到应用：出于知识产权保护和商业利益等原因，指 纹识别的核心技术仍然只被少数企业和技术机构所拥有，为了获得自主产权的和绝对安 全的系统，必须自主开发；随着市场的扩大和要求的提高，设计开发速度更快、性价比 更高的系统势在必行。因此，开发性能可靠、成本较低的自动指纹识别系统将给我国安 全技术、防伪技术、身份识别技术，特别是i t 产业带来重要的革新。 1 。2 指纹识别的核，b 技术 自动指纹识别系统6 ，7 ，引，简称a f i s ( 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 ) 。如 图1 2 所示，自动指纹识别系统由指纹图像采集、预处理、特征提取与匹配等过程组成。 其中，指纹匹配、指纹图像预处理与特征提取都是指纹识别的核心技术。 图1 2 自动指纹识别系统 f i g 1 2a 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 4 指纹的匹配方法研究 1 2 1 指纹图像预处理与特征提取 a 指纹图像采集 将指纹采集下来输入计算机进行处理是指纹识别的首要步骤。传统的指纹采集方法 是用手指蘸上墨水或印油在纸上按压，然后用扫描仪摄取。由于其严重的不可靠性，该 方法已经被淘汰。随着光学仪器、传感器及数字技术的发展，各种快速精确、方便小巧 的采集设备得到应用目前，主要使用的指纹采集技术 9 1 有光学采集技术，电容采集技 术和超声波采集技术 光学采集技术是最古老也是应用最广的指纹采集技术。手指放在一个加膜的台板 上，一般是用硬质塑料制成的。大多数的光学采集设备是利用c c d 将由深色脊和浅色 谷构成的指纹图像转换成数字图像。电容传感器通过电子度量来捕捉指纹。电容设备能 结合大约1 0 0 ，0 0 0 个导体金属阵列的传感器，其外面是绝缘的表面，当用户的手指放在 上面时，皮肤组成了电容阵列的另一面。电容器的电容值由于金属间的距离而变化，这 里指的是脊( 近的) 和谷( 远的) 之间的距离，超声波采集技术虽然被认为是精确度最 高的指纹采集技术，但在实际运用领域中还较少。这种设备采取传送声波并通过手指、 台板和空气间的电阻来测量距离的方法来完成采集。超声波能够穿透台板和指纹上的灰 尘和残余物。在这点上，使光学采集设备无法比拟。 本文实验中所使用的是d i g i t a lp e r s o n a 公司的 u a r e u2 0 0 0 指纹扫描器，外形如图1 3 所示。该扫 描器能够自动读取指纹图像，并通过u s b 接口把数字 化的图像传送到计算机。对于需要进行身份验证的膝上 型电脑、桌面计算机或其他的个人电脑装置，它是很理 想的配件。它集成精密光学系统、l e d 光源和c m o s 摄像头协同工作，在图像摄取时进行电压控制、自动矫 图1 3 指纹扫描器 正，并使用即插即用的u s b 接口。 f i g 1 3f i n g c r p r i ms c a n t i e r b 指纹图像预处理 经指纹采集器采集到的原始指纹图像不可避免地存在对比度不均匀、含有大量噪声 等缺点，为了降低后续特征提取和匹配算法的复杂度、提高效率，预处理过程必不可少。 预处理的目的是去除图像中的各种噪声于扰，恢复指纹的脊线结构，改善输入指纹图像 的质量，以提高特征提取的准确性。预处理通常包括以下几部分：图像增强、方向图计 算、二值化和细化等，本文将在第二章详细介绍这几步处理的方法。 c 指纹图像的特征提取 特征提取是将预处理后的二值细化指纹图像中能够充分代表该指纹唯一性的特征 抽象出来。特征提取的目的是为了去除数据冗余，以便于匹配识别。 指纹图像由脊和谷组成的纹线构成，指纹特征就是指纹纹线的局部不连续点，这些 特征决定了指纹的唯一性。如图1 4 所示，指纹图像中存在两种类型的特征：全局特征 指纹的匹配方法研究 和局部特征。全局特征常用于指纹的分类，两个重要 的全局特征是核心点( c o r e ) 和三角点( d e l t a ) ，但 并不是所有的指纹都具有这两种全局特征。局部特征 又称指纹细节( m i n u t i a e ) ，常用于指纹的匹配。美国 国家标准局( n i s t ) 提出了用于指纹识别的瞪种细节 特征：纹线端点、纹线分叉点、复合特征( 三分叉或 交叉点) 和未定义。美国联邦调查局( f b d 提出的细节 点坐标模型中，只利用了纹线端点( r i d g ee n d i n g ) 与纹线分叉点( r i d g eb i f u r c a f i o n ) 这两种特征。大量 统计结果和实际应用表明，这两种特征点在指纹中出 现的几率最多，并且足以描述指纹的唯一性，而被广 泛采用。 特征点的真伪将直接影响匹配的效果，因此特征 提取后还要进行后处理( p o s t - p r o c e s s i n g ) ，后处理的目 的是为了消除虚假特征点，即伪特征。本文也将在第 二章中详细叙述特征提取以及后处理的方法。 图1 4 指纹特征 f i g 1 4f i n g e r p r i n tf e a t u r e 1 2 。2 指纹匹配 指纹匹配作为指纹识别的核心技术之一，是自动指纹识别系统设计中的热点和难 点。它在指纹特征提取之后，是自动指纹识别的最后一步，也是非常关键的一步。匹配 结果的正确与否将最终决定整个系统的性能好坏。 前面的各阶段，包括指纹图像预处理、特征提取和后处理，都是为获得好的匹配结 果做准备的。经过以上处理，得到一系列包含原有指纹图像信息的指纹特征点。指纹匹 配要解决的问题就是将当前输入的测试指纹图像特征点与事先存在数据库中的模板指 纹图像特征点进行比对，判断两幅指纹图像是否来自同一个手指。 指纹匹配一般分为两类【6 ，嘲：指纹验证( v e r i f i c a t i o n ) 和指纹辨别( i d e n f i f i c a f t o n ) 。 ( i ) 指纹验证是“一对一的指纹匹配( o n e t o - o n e m a t c h i n g ) ”，即事先把个人的指 纹特征及其姓名等个人信息以某种有效的形式在数据库中存储起来，验证时，待验证的 个人重新提供其个人指纹和姓名( 或其他个人信息，如证件号等) ，将其提供的新指纹 与其所声称的那个人的存储模板指纹进行一对一的匹配，通过一次匹配的结果( 指纹匹 配只进行一次) 来判断是否是同一个人。指纹验证其实是回答了这样一个问题：他是他 自称的这个人吗? 这是应用系统中使用较多的匹配方法。各种中小型民用系统，如门禁 控制、银行账户、指纹考勤等系统中的匹配皆属于此类匹配。 ( 2 ) 指纹辨别是在不知道待辨别个人的其他个人信息的前提下，把现场得到的指 纹图像同指纹数据库中保存的多个指纹进行逐一的对比，从中找出与现场指纹相匹配的 指纹，是“一对多的匹配( o n e - t o - m a n ym a t c h i n g ) ”。指纹辨别其实回答了这样一个问题： 他是谁? 辨识主要应用于犯罪指纹匹配的传统领域和大型民用系统中。例如，将一个不 指纹的匹配方法研究 明身份的人的指纹与指纹库中有记录的人的指纹进行比对，来确定此人是否曾经有过犯 罪记录或者是否拥有有效身份。 在实际应用中还有“一对几的 匹配( o n e - t o f e wm a t c h i n g ) ”，其主 要应用于只有几个用户的系统中 ( 如一个家庭的成员要进入他们 的房子) ，“几个”所包含的数目一 般为5 2 0 人。 无论是哪种类型的指纹匹配，( a ) 要想准确地判断两幅指纹图像是 否来自同一个手指都是一项很困 难的工作。如图1 5 所示，指纹( a ) 和指纹) 来自于同一个手指，但看 上去却很不相同；而指纹( c ) 和指纹 ( d ) 虽然来自于不同的手指，却非常 相似。 一个具有鲁棒性的指纹匹配 算法，需要同时满足以下要求；匹 配快速准确，以满足实时系统的需 ( c )( d ) 要；匹配与指纹的平移和旋转无图1 5 相同手指指纹与不同手指指纹之间的比较 关：匹配与一定的指纹变形无关。 f i g 1 5c o m p a r ew i t ht h ef i n g e r p r i n t sf r o mb o t ht i 】es a n e 但是由于一些客观因素的存在，要 f i n g e ra n d t h ed i f f e r e n t f i n g e r 想满足以上条件很困难这些因素 主要有： ( 1 ) 指纹录入的随机性使得同一手指的指纹图像之间存在不同程度的平移和旋转： ( 2 ) 指纹采集过程中三维人体指纹映射为二维指纹图像的不确定性，使得指纹图像存 在非线性局部形变，这种形交是随机的，难以用数学模型来描述； ( 3 ) 手指指尖表面皮肤的干燥度、空气湿度和灰尘，以及接触面表面被污染程度的不 同，导致指纹伪特征点的出现； ( 4 ) 指纹前期预处理和特征提取算法的不完善和累积计算误差，人为地导致伪特征的 增加、真正特征点的丢失和特征点位置的偏差。 因此，指纹匹配仍是自动指纹识别系统设计中的难点和热点。本文将在第三章中详 细叙述指纹匹配的方法及其改进，第三章的内容也是本文的重点所在。 衡量指纹匹配算法性能的重要指标是识别率。识别率是由两个值 1 0 1 共同确定：错误 接受率f a r ( f a l s e a c c e p t a n c e r a t e ) 和错误拒绝率f r r ( f a l s e r e j e c t i o n r a t e ) 。错误接 指纹的匹配方法研究 受率f a r 是所有不同的指纹被认为相同而被接受 的匹配次数占总匹配次数的比率：错误拒绝率f r r 5 0 是所有相同的指纹被认为不同而被拒绝的匹配次 4 0 数占总匹配次数的比率。通常用百分比来表达这两蔓3 0 个比率，f a r 和f r r 互成反比。当阈值设置较小重2 0 时，系统安全性增加，f a r 减小，但错误拒绝率 1 0 f r r 将升高：相反，当阈值设置较大时，系统易用0 性增加，f r r 减小，但错误接受率f a r 将升高。 图1 6 给出表示f a r 和f r r 之间关系的r o c ( r e c e i v i n go p e r a t i n gc u r v e ) 曲线。在设计实际应 用系统时，一方面要考虑整体性能，使r o c 曲线 整体下降；另一方面还要兼顾安全性和易用性，在 r o c 曲线上寻找合适的平衡点。 l t 3 本文主要研究内容与结构安排 f a r ( 1 ：l 暮l ) 图1 , 6r o c 曲线 f i g 1 6r o c c u e 本文通过大量阅读指纹匹配与识别方面的文献资料，在前人设计开发的基础上，建 立了一个完整的自动指纹识别系统，它包括指纹图像输入、预处理、特征提取和匹配等 四个部分。其中，图像输入部分使用u a r e u2 0 0 0 指纹采集器，把数字图像信号直接 输入到计算机。其它各个部分的算法均在w i n d o w s 平台上用v i s u a lc + + 得以实现，特别 是在指纹检索和匹配方面，本文进行了深入的研究，提出了行之有效的改进算法。 本文的具体工作主要包括以下内容： ( 1 ) 在指纹匹配的前期处理部分，通过比较多种预处理、特征提取和后处理算法， 选择并实现了一种基于灰度特性的指纹图像分割算法、改进的块方向图算法、基于方向 图的动态阈值二值化算法、一种经典o p t a 细化算法以及一种简单实用的特征提取和后 处理算法实验证明，这套算法能够较好地完成各自的工作，为后续指纹匹配的顺利进 行奠定了基础。 ( 2 ) 在指纹匹配部分，本文在原有算法的基础上进行改进，提出一种基于指纹全 局星型结构的分步匹配算法针对局部特征向量构造简单、易受局部形变干扰的问题， 在第一次匹配中采用全局向量的同时，并在向量中增加了邻域特征点与中心特征点所在 纹线方向夹角等反映纹线走向及特征点间相互结构关系等参量，提高了匹配的准确性； 针对固定限界盒门限造成误匹配率较高的问题，在第二次匹配中运用自适应门限，进一 步提高了匹配的正确率。实验结果表明，该方法可以实现指纹的快速准确匹配，且不受 指纹图像的平移、旋转，以及局部形变的影响。 ( 3 ) 在指纹检索部分，本文提出了一种基于近邻结构的指纹检索方法，一方面可 以有效地进行指纹检索，排除不合格的指纹，使匹配速度得到显著提高；另一方面可以 实现不同的多维结构检索，满足不同系统的要求。 指纹的匹配方法研究 本文的结构安排如下： 第二章首先介绍在指纹匹配之前进行的指纹图像预处理、特征提取和后处理的基本 原理和方法。其中包括指纹图像的增强、求方向图、二值化和细化，以及特征提取和后 处理等算法。 第三章详细讨论指纹匹配和指纹检索方法。其中将重点阐述基于指纹全局星型结构 特征的分步匹配算法和基于星型结构的指纹检索方法，包括其算法原理和具体步骤。 第四章是实验结果讨论与分析。给出本文所涉及的所有算法的实验结果，并进行了 比较和分析。 最后，第五章是对本文所做工作的总结和对指纹识别技术的展望。 指纹的匹配方法研究 2 指纹图像预处理和特征提取 2 1 引言 与其它的图像匹配一样，在指纹匹配之前，必须进行有效的指纹图像预处理和特征 提取。预处理 1 1 1 3 l 是为了改善输入图像的质量，以提高特征提取的准确性。特征提取【1 4 】 又包含提取什么样的特征、用什么方法提取特征，以及如何去除虚假特征等问题。预处 理和特征提取的好坏将直接影响到指纹匹配的效果。 指纹图像由于按压时用力不均匀和手指表面干湿度不同等因素的影响，一般都存在 一定程度的指纹纹线间的粘连、模糊以及纹线断裂等现象。同时，从三维人体指纹到二 维数字指纹图像的转换过程中，由于量化精度及扫描仪的非线性特性等影响，都会不可 避免地引入噪声。这些粘连、模糊、断裂以及噪声的存在将严重影响指纹特征提取和识 别匹配的准确性。因此在进行特征提取和匹配之前，进行指纹图像的预处理，以增强图 像的可识别性是非常必要的。 预处理是自动指纹识别系统中的第一步，也是自动指纹识别系统的重要组成部分， 它的处理效果将直接影响特征提取和匹配的复杂度，关系到整个系统的识别率。预处理 的目的就是利用信号和图像处理的方法去除图像中的各种噪声干扰，恢复指纹的纹线结 构，把它转化成一幅清晰的指纹二值细化图像，以便可靠地提取正确的指纹特征。指纹 图像的预处理主要有图像分割、增强、滤波、求方向图、= 值化、细化等方法。针对不 同的系统要求，可以选择不同的预处理方法进行组合，使其达到最佳处理效果。指纹图 像预处理的一般工作过程如图2 1 所示。通常，预处理之后得到一个已经细化了的清晰 的二值指纹图像。 图2 1预处理框图 f i g2 1t h ef l o wo f p r e p r o c c s s i n g 预处理之后是特征提取过程，所谓特征提取就是要给指纹特征点赋予一些参数和标 记，使得这些参数和标记能把每一个指纹从众多的指纹中唯一的区别出来。指纹匹配的 指纹的匹配方法研究 过程实际上就是指纹特征比对的过程，因此指纹特征提取的好坏决定指纹匹配的可靠 性。由于指纹图像采集以及预处理过程中一些其它因素的影响，提取到的特征点中会含 有一些虚假的特征点，称之为伪特征。在特征提取之后，还需要对提取的特征点进行筛 选处理，即后处理，以找到真正有用的指纹特征点用于指纹匹配。 长期以来，许多研究人员在预处理和特征提取方面做了大量工作。本章将详细介绍 指纹图像预处理与特征提取，以及后处理的各种原理和方法。 2 2 指纹图像的预处理 a 指纹图像的增强 图像增强是对指纹采集器采集进来的指纹图像进行的第一步预处理，将图像的背景 噪声去除，以降低背景噪声对后续处理的影响。图像分割是经常被使用的指纹图像增强 方法之一。在指纹图像中，我们感兴趣的区域是由指纹脊线和谷线组成的清晰的指纹区 域，称之为前景；而非指纹区域或噪声严重的区域，是我们不希望处理的区域，称之为 背景。指纹图像分割1 1 5 , 1 6 的目的就是要将指纹前景区域同背景区域分离开来，使后续处 理集中于有效区域，以避免在噪声和背景区域中提取特征。指纹图像分割不仅能大大减 少指纹预处理的时问，还能提高特征提取的有效性。 本文采用一种基于图像灰度特性的分割方法。由于该方法只用到图像的灰度特性， 计算简单快速，而且在计算指纹方向图之前进行分割操作，可以改善后面计算方向图的 效果。 一般来说，前景图像中指纹脊线和谷线的灰度差较大，因而其灰度统计特性中局部 灰度方差较大；而对于图像背景区域，正好相反。如图2 2 所示，在指纹图像( a ) 的前景 区和背景区分别取1 6 1 6 的块，设块灰度均值为m e a n ，块灰度方差为v a r i a n c e 。图 ( a ) 指纹图像 ( c ) 背景区灰度直方图 图2 , 2 前景区与背景区的比较 f i g 2 2c o m p a r i s o nb e t w e e nf o r e g r o u n dr e g i o na n db a c k g r o u n dr e g i o n 指纹的匹配方法研究 和图( c ) 分别为前景块和背景块的归一化灰度直方图。通过比较可以发现，前景区灰度主 要分布在黑( 灰度值为o ) 白( 灰度值为2 5 5 ) 两端，均值较低( m e a n l = 1 0 6 ) ，而且 由于包含脊线和谷线，方差很大( v a r i a n c e i = 1 2 5 7 6 ) ；与之相反，背景区灰度主要集中 在白色一端，均值较大( m e a n 2 = 2 2 7 ) ，方差较小( v a r i a n c e 2 = 2 1 4 9 ， v a r i a n c e 2 ( v a r i a n c e l ) 。基于这一特性，可利用图像的局部均值和方差( 即块均值和方差) 对指纹图像进行分割。算法描述如下： 假设厦f ，) 代表指纹图像( f ，) 处的灰度值，将指纹图像分成大小为m x m 的块，这里 m 的大小以包含一脊一谷( 即一周期) 为宜。通过计算以下2 种灰度特征来区分前景区 与背景区： ( 1 ) 第，坊块的均值计算方法如下： mean(m，一，=：5：，cr+ma，+nx，mllo1 = 0 ， ，一) = ，( “m m ，+ n x 肘) j m 1 ( 2 ) 第( 埘，n ) 块的方差计算方法如下： m ，j + n x m ) - m e a n ) 2 7 m ， c “m ，n ) = l ， x 2 m i 扭0j o ( 2 1 ) ( 2 2 ) ( 3 ) 设置适当的均值阈值死和方差阈值乃，当m e a n t 1 且v a r i a n c e i 2 时，该块即为 背景区，可以割除。在实际操作中，为了分割精确，通常m 取较小值，例如肘= 6 。阈值乃和乃随着m 的不同要做相应的调整。 b 指纹方向图的计算 指纹图像是一种具有一定纹路走向的多边有向图，纹理性和方向性是它区别于其它 图像的显著特征。方向图抽象了指纹脊线与谷线交错平行分布的特点，描述了指纹图像 中每一像素点所在脊线或谷线的切线方向，反映了指纹图像纹理结构的本质，具有重要 的意义。作为一种可以直接从原始灰度图像中得到的有用信息，它的计算一直是指纹识 别技术中必不可少的一步。 方向图之所以具有如此高的研究价值【1 7 1 是因为其具有以下特点： 真实性：指纹局部方向图真实地反映了指纹图像最本质的纹形特征，再现了指纹的 中心纹线、外围包络线和根基线的形状和走势。 渐变性：由于指纹纹线具有缓变性的特点，求出的方向图也不应发生走向的剧变( 中 心点除外) ，利用这一特性可以对在有噪声情况下求出的方向图进行平滑处理，从 而可以实现从低质量指纹图像中获取效果较好的方向图。 抽象性：块方向图是对纹线形状的一种抽象的描述，因此使研究指纹的几何拓扑结 指纹的匹配方法研究 构闯题得以大大简化。 在8 0 年代初，就已经开始有把方向图引入到指纹图的一些成功的尝试。这时候所 使用的方向图是从制图中直接提取，得到的结果并不十分令人满意。从1 9 8 7 年开始， m e h 订e 等人成功地得到了在灰度图上直接获取方向图的有效算法 【8 】，使指纹图像的处 理效果达到了一个新的水平，从而使基于方向图的算法成为指纹图像处理方法研究中的 一个热点。r a o 提出一种利用梯度算子求取方向图的方法1 1 9 1 j o i n 等人对r a o 的方法做 了进一步的改进，采用一种后处理平滑算法【2 0 ，并利用g a b o r 滤波器对频率和方向的选 择性，实现图像增强。指纹方向图已经被认为是解决指纹自动识别中的某些关键技术的 一个重要途径。 方向图分为两种：一种是点方向图，即把指纹图像中每一点的方向都表示出来；另 一种是块方向圈，即把指纹露像均匀分割成若干块，仅表示出每一块中脊线的大致方向。 在实际处理中，经常使用的是块方向图，因为它比点方向图有更强的抗噪性，而且求块 方向图可以减少计算量，有利于模块化处理计算方向图的基本思想是：在灰度图像中 计算每一点( 或每一块) 在各个方向上的某个统计量( 如灰度差、梯度等) ，根据这些 统计量在各个方向上的差异，确定该点( 或该块) 的方向。 常用的点方向图和块方向图的计算方法 如图2 3 所示，设如c ，y ) 是指纹图像中点p 协，力的灰度值，要计算该点的方向d 0 ，y ) ， 需要先求出该点临域沿d 方向的灰度变化，用变量& 表示。 以= i f ( x ，y ) - f a x , ，儿) | d = 1 ， ( 2 3 ) i l 点的灰度值：n 为所取的方向数；，z 为每个方向上所取 4 i 黧熟鬻蓄每晶嘉粼震滏凳爰。爿 最小时的方向。对图像中的每一点求取点方向，便形成五鲤 了指纹点方向图。批鼎 点方向图的方向取值不是0 2 厅中的任意值，而是 有限的几个数，例如：1 7 = 1 6 时，方向取值 d ( x ，y ) 0 ，厅，8 ，石，4 ，3 z r 8 ，7 石4 1 5 厅8 ，2 茚) 。当得到 指纹点方向图后，求块方向图就比较容易了。把点方向 图分成w w 大小的小块，对每一块计算方向直方图， 方向直方图中的峰值所对应的方向即该块的方向。 丁 图2 3 点方向示意图 f i g 2 3p o i n td i r e c t i o nm o d e l 一种改进的指纹块方向国算法 本文采用一种改进的指纹块方向图算法【2 1 1 。这里的改进，是指在计算方向图时采用 块重叠的方式，即在求某一小块的方向时，先以此小块为中心扩大块的范围并计算该大 指纹的匹配方法研究 块的方向，然后将此大块方向作为小块方向。由于引进了相邻块的相关性，所得的块方 向图更连续、更准确。 假设力，力代表指纹图像( f ，力处的灰度值。该算法步骤如下： ( 1 ) 将图像分成大小为m x m 的小块 脊一谷( 即一周期) 为宜，脚 大块大小设为n x n ，其中m 的大小以包含一 包含一个半周期为宜； ( 2 ) 计算大块中每个像素苁f ，力在x 轴和y 轴上的梯度g 文f ，力和g ( i ，力。这里可选用简 单的梯度算子，如s o b e l 算予： q ( 加 ，( f 一1 ，一1 ) + 2 ，( f l ，) + ，( f 一1 ，+ 1 ) 】 ( 2 - 4 ) 一【，( f + l ，一1 ) + 2 f ( i + l ，j ) + ，( f + 1 ，+ 1 ) 】 ) 2 唧一1 ，卜1 ) + 2 ，( f ，一1 ) + ，( + 1 卜1 ) ( 2 5 ) 一 ，( f 一1 ，j + 1 ) + 2 f ( i ，j + 1 ) + f ( i + 1 ，j + 1 ) 】 ( 3 ) 计算以像素点( f ，d 为中心的大块的方向e ( i ，力。 ，2 g ( i ，) q ( f ，) e ( i ，) = 去t a n “( _ 寰竿l 一) ，g ，0 且q 0 ( 2 6 2 ( g ：2 ( f ，) 一q 2 ( f ，埘 当大块中g 或g v 为零的数目达到一定程度，如多于大块总像素点数的8 0 时，e ( f ，) 应直接设为0 或万。 ( 4 ) 将n x n 大块的方向口作为m x m 小块的方向保存起来，循环计算下一块的方向。 虽然由上面算法求出的方向图己经能够比较精确地反映出指纹纹线的方向，但有些 时候还需要进一步对它进行平滑。本文采用一种将方向图正交分解后分别进行滤波的方 法，计算步骤如下： ( 5 ) 将方向图转换为连续的向量场： o ，( f ，j ) = c o s ( 2 0 ( i ，) ) 中，( f ，j ) = s i n ( 2 0 ( i ，) ) ( 2 7 ) ( 2 _ 8 ) 其中，中。中y 分别是向量场x ，y 方向上的分量，o ( i ，d 是点( f ，力所在块的方向。 ( 6 ) 实现低通滤波： 指纹的匹配方法研究 p- 如，：_ “4 ，i 中，1 ( f ，j ) = 矽( ) o ，( f _ w ，j v w ) ( 2 9 ) 一o ，2 ，2 ，f = o 帅w ，z 中，。( f ，) = 艺矽( 虬v ) o y ( f 一叭，一v w ) ( 2 - l o ) w m - w o ，2 o ，1 其中，矿是一个大小为w 。x w 。的二维低通滤波器，本文使用5 x5 的均值滤波。 ( 7 ) 平滑后的方向场为： o ，c 。，= 知毒羔， ( 2 1 1 ) c 指纹图像的二值