分类号：TP391 单位代码：10422 密 级： 学号：200312283 硕 士 学 位 论 文 论文题目：非理想条件下指纹识别的研究 作 者 姓 名 赵博 专 业 计算机软件与理论 指导教师姓名 专业技术职务 尹义龙 副教授 2006年4月5日
分类号： 单位代码： 密 级： 学号： 硕 士 学 位 论 文 论文题目： 作 者 姓 名 专 业 指导教师姓名 专业技术职务 年 月 日
原 创 性 声 明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名： 日 期： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。 (保密论文在解密后应遵守此规定) 论文作者签名： 导师签名： 日 期：
山东大学硕士学位论文 目 录 摘 要..................................................................................................I ABSTRACT.....................................................................................III 第一章 绪论.......................................................................................1 1. 1指纹识别技术简介....................................................................................................2 课题的选择.....................................................................................................................6 论文的组织和创新之处.................................................................................................6 第二章 在线指纹模板增强...............................................................7 在线模板增强思想简介.................................................................................................7 算法思想.........................................................................................................................9 算法描述.......................................................................................................................11 ．模板增强算法............................................................................................................13 ．实验结果....................................................................................................................14 ．本章小结....................................................................................................................15 第三章 混和指纹匹配算法研究.....................................................17 指纹匹配算法综述.......................................................................................................17 基于细节点的指纹匹配算法.......................................................................................21 全局特征匹配算法.......................................................................................................22 分类器融合...................................................................................................................25 实验结果.......................................................................................................................25 本章小结.......................................................................................................................27 第四章 基于模型的指纹方向信息计算.........................................28 指纹图像的方向信息计算...........................................................................................28 算法改进.......................................................................................................................31 实验及其结果...............................................................................................................32 本章小结.......................................................................................................................33 第五章 总结和探讨.........................................................................34 参考文献...........................................................................................35 攻读学位期间发表的学术论文和参加的工作...............................40 i
山东大学硕士学位论文 摘 要 指纹识别是因为其悠久的历史以及较高的识别精确度，成为了目前最成熟的生物特征识别技术之一，并被广泛的应用到各个领域当中。然而直到目前为止，非理想条件下指纹识别中仍存在一个指纹识别中的技术难点。本文针对非理想条件下指纹识别问题，特征提取以及匹配两个方面进行研究：在匹配阶段，从两个方面进行研究，在识别过程中引入学习机器思想，利用指纹匹配获得的信息进行模板增强对模板信息进行处理；引入新的特征信息用于指纹匹配，增加指纹识别过程中可用的有效信息量。在特征提取阶段，方向信息提取为研究点，通过对指纹方向信息的可靠计算，提高在非理想条件下指纹识别的效果。 本文的主要工作主要包含三个部分指纹识别中的模板增强算法、混合指纹匹配以及方向信息计算： 指纹识别中的模板增强算法：在自动指纹识别系统当中，因为系统中指纹模板包含的信息不全以及信息的不准确可能会导致系统产生错误的拒绝或是错误的匹配。因而如何改进模板的质量，也就是模板增强，对于一个自动指纹识别系统来说，至关重要。我们提出了一个新的指纹模板增强算法。根据机器学习中基于案例学习以及概率论上的一些理论，通过删除模板中的伪细节点、增加模板中丢失真细节以及调整模板中细节点参数等手段对模板进行增强。为了检验我们算法的效果，我们建立了特殊的指纹图像库。在我们自建的指纹库以及公开数据库fvc2000上面的实验表明，应用我们的指纹增强算法，指纹模板的质量逐渐提高，系统的性能逐渐提高。 混合指纹匹配：可用于匹配的特征信息不足是指纹识别，特别是基于细节点进行指纹匹配中存在的主要问题。在本文中，我们研究同源指纹与非同源指纹在全局方向信息上面存在差异，设计了一种基于全局方向信息的指纹识别算法，并将基于全局方向信息匹配的识别算法与基于细节点匹配的指纹识别算法在分类器级别上，利用SUM规则进行融合。在bac2005指纹竞赛上面的竞赛结果显示，我们设计的混合指纹匹配算法，在识别的精度上能够获得较满意的识别效果。 方向信息计算：指纹图像中的方向信息是指纹识别中重要的特征信息之一， I
山东大学硕士学位论文 并被应用于指纹分类、指纹细节特征提取以及指纹匹配中。在本文中，我们针对基于模型的方向信息计算的模型进行了局部改进，加入了奇异点位置参数的自适应步骤，针对公开数据库上图像的实验表明进行了，通过对于参数的改进，可以提高方向信息的计算精度。 关键词 指纹，指纹识别，模板增强，方向场，指纹匹配 II
山东大学硕士学位论文 ABSTRACT Automatic fingerprint identification technique has become a research focus in the area of science in last decades. Much work has been done on fingerprint identification, but some technical difficulties still baffle the development of fingerprint identification, especially non-ideal fingerprint identification. Fingerprint matching and feature extraction are two main steps in fingerprint identification, in the process of fingerprint matching, under the theory of machiner learning, using the information got during the matching process, we improve the information about the template, and plus the type of information used in fingerprint matching to add the information which can be used in fingerprint identification. While in the feature extraction process, we improved the quantity of fingerprint orientation to reduce the noise exist in the information after feature extraction. Our work is focus on the template improvement, combined fingerprint matcher and orientation calculation. For fingerprint template improvement, based on the case-based method of machine learning and probability theory, we improve the template by deleting pseudo minutia, recovering losing genuine minutia and updating the information of minutia such as location and direction. Special fingerprint image database is built for this work. Experimental results on the new database and fvc2000 indicate that our method is effective and the quality of fingerprint template is improved evidently. Accordingly, performance of fingerprint matching is also improved stably along with the increase of using time. For combining matcher: the limitation of information used in fingerprint matching is the one of the most important problems during fingerprint matching. In this paper, a new kind of fingerprint matching based on the global orientation information is studied. And a combined fingerprint matcher based on the global orientations and minutia is also introduced. The result reported in the bac2005 indicates the valid of proposed matching III
山东大学硕士学位论文 algorithm. For calculating the orientation: orientation is one of the most important information in fingerprint identification. And wildly used in fingerprint classification, feature extraction and fingerprint matching. In this paper, an improvement about the model-based orientation calculation is designed; changing the location of singular point, the result on the public fingerprint database shows the improvement about the precision. Keywords fingerprint, Fingerprint Identification, template improvement, minutiae matching, hybrid fingerprint matching IV
山东大学硕士学位论文 第一章 绪论 生物特征识别（biometrics）技术是指通过计算机，对人体所具有的某些生理[1]特征或者行为特征来进行识别的一项模式识别技术。生理特征与生俱来，大多数为先天性的，比如指纹，人脸、虹膜、DNA等，具有较大的稳定性和可靠性。行为特征由习惯产生，多为后天形成，例如笔迹、步态等，因而相对来讲，稳定性和可靠性要差一些。通常，生理特征和行为特征统称为生物特征。 身份鉴定是生物特征识别一个最为广泛的应用。传统的身份鉴别方法是通过对那些用来标识个人身份的实物或者其它的标识信息来进行身份特征识别的，它包括：（1）标识身份的物品，例如钥匙、身份证件、ATM卡等；（2）其它的标识信息，例如用户名和密码。在一些安全性要求比较高的系统中，为了提高识别的可靠性，通常将以上的两种方式结合起来，例如在ATM机取款时，要求用户同时提供ATM卡和对应密码。虽然传统的身份识别方法应用在很多领域，并且能够取得令人满意的识别效果，例如识别精度高和伪造的难度大，然而他们却仍然存在明显的缺点：用于进行身份识别的物品容易丢失，用于标识个人身份的密码容易遗忘或者记错。更为严重的是传统的身份识别系统无法区分真正的拥有者和取得身份标识物的冒充者，一旦他人获得了这些用于身份标识的物品或者信息，就很难进行身份的识别。 与传统的身份识别手段相比，基于生物特征的身份识别技术，因为利用了人体所具有的某些生理特征或者行为特征，具有如下优点： （1） 不易被人们所遗忘或者丢失； （2） 防伪性能好，不易伪造或者被盗； （3） “携带方便”，随时随地可用。 目前常见的生物特征识别手段主要有DNA识别、耳型识别、人脸识别、脸部热量、指纹识别、步态识别、手形识别、手部血管识别、虹膜识别、视网膜识别、[3-9]手写体识别和声音识别等。 1
山东大学硕士学位论文 1. 1指纹识别技术简介 生物特征识别的历史可以追溯到古代埃及人通过测量人的尺寸来进行身份鉴别。公元前7000年到6000年以前，在古叙利亚和中国，指纹作为身份鉴别已经开始应用。19世纪初，科学研究发现了指纹的两个重要特征，一是两个不同手指的指纹纹脊的式样不同，另外一个是指纹纹脊的式样终生不改变。这个研究成果使得指纹在犯罪鉴别中得以正式应用，1896年阿根廷首次应用，然后是1901年的苏格兰，20世纪初其他国家也相继应用到犯罪鉴别中。20世纪60年代，由于计算机可以有效地处理图形，人们开始着手研究利用计算机来处理指纹。从那时起，自动指纹识别系统AFIS在法律实施方面的研究和应用在世界许多国家展开，FBI在60年代末期开始使用一种自动识别指纹的设备，到在70年代末期，已经有一定数量的设备开始在美国大范围使用。20世纪80年代，个人电脑、光学扫描这两项技术的革新，使得它们作为指纹取像的工具成为现实，从而使指纹识别可以在其他领域中得以应用。 目前常用的指纹识别系统通常分为以下三个模块：（1）指纹的采集；（2）指纹的特征提取；（3）指纹匹配。指纹的采集就是通过相关设备将指纹纹线分布录入并进行数字化处理；指纹特征提取是在采集到的指纹图像上，提取感兴趣的指纹的特征信息；指纹匹配是利用提取到的特征信息判断两枚指纹是否同源。指纹识别技术是最可靠的生物识别技术之一，已经有很多自动指纹识别产品应用于法 律部门、公共安全领域和民用领域，但是自动指纹识别技术仍然面临巨大的挑战。指纹识别系统的一般结构及工作模式 指纹识别系统本质上是一个模式识别系统，它根据使用者的生理或者行为特征对使用者进行辨识，从而判断其是否具有合法身份。从逻辑上讲，自动指纹识别系统由两个主要模块组成：注册模块和识别模块。注册模块主要负责将生物特征信息保存到系统样本数据库。在登记过程中，生物特征样本首先经相应的采集设备录入，然后经特征提取算法提取特征信息，这种特征信息被称为样本。根据需要，样本信息被保存在数据库或磁卡、智能卡中。识别模块负责判断待识的特 2
山东大学硕士学位论文 征信息和当前样本特征信息是否匹配。在该模块中，相应设备录入待识生物特征，并进行数字化，经特征提取算法提取待识生物特征中的有用信息，由模式匹配算子将这一信息与预先存储的样本信息进行比对，最后得出是否匹配的判断。 自动指纹识别的研究内容 从技术的角度看，自动指纹识别主要可以被分为指纹采集、指纹特征提取和指纹匹配三个方面的内容。 指纹采集 按照采集方式的不同，指纹主要可以分为三类：捺印指纹、活体指纹和模糊指纹。 捺印指纹指的是将沾了印墨的手指按压在某种东西（通常是纸）上留下的指纹的痕迹，再经相应设备转化为数字化的信息，就得到捺印指纹图像。捺印指纹采集到的有效面积比较大，但因采集方式所限，采集速度较慢，指纹缺陷较多，并且难以严格控制采集的质量。 根据录入原理的不同，活体指纹录入仪可分为光反射式、热感式、电容式和超声反射式等几种。根据采集时指头是否与指纹录入仪接触，又可分为接触式和非接触式。经活体指纹采集设备得到的是数字化的指纹图像，相比较而言，活体指纹的质量是最好的。 模糊指纹一般是指在犯罪现场采集到的指纹。将罪犯无意中遗留在犯罪现场的指纹痕迹经过显影、拍照和扫描等技术处理而得到的指纹图像。 指纹特征信息提取 指纹的特征信息主要分为两大类：指纹的全局特征和指纹的细节特征。全局特征主要是指指纹图像中的奇异点、指纹图像的全局方向信息等宏观特征。指纹的细节特征与指纹的全局特征相比，种类繁多，有150多种，但是其中很多特征是极其罕见的，而在大多数自动指纹识别技术中，一般只使用两种细节点特征：纹线端点（ridge ending）和分叉点（ridge bifurcation）。纹线端点指的是纹线突然结束的位置，而纹线分叉点则是纹线突然一分为二的位置。大量统计结果和实际 3
山东大学硕士学位论文 应用证明，这两类特征点在指纹中出现的机会最多，也最稳定，而且比较容易获取。更重要的是，使用这两类特征点足以描述指纹的唯一性。通过算法检测指纹中这两类特征点的数量以及每个特征点的类型、位置和所在区域的纹线方向是特征提取算法的任务。特征点的类型和定义如图所示。 指纹匹配 虽然指纹图像中的细节点信息是最有效的用于指纹匹配的指纹特征，然而研究者逐渐发现，紧紧依靠指纹的细节点信息，不能取得更加理想的识别效果，因而，许多研究者在细节点匹配的基础之上，加入了局部信息，例如局部纹线方向、局部图像灰度方差和全局信息，例如指纹图像的奇异点、指纹图像的全局方向等信息。这些信息的加入，虽然占用了更多的存储空间，消耗了更多的运算时间，然而却大大提高了指纹识别的识别精度。 这充分表明，在进行指纹识别过程中，指纹的细节点无法给我们提供足够多的信息用于指纹的识别，因而有必要引入其他的特征，通过增加特征的数量来增加我们获得的特征信息的总量。特别是在非理想条件下（非理想条件的定义及相关解释见），我们获得的指纹信息不足，并且得到的指纹信息中包含较大噪音，就更需要加入新的特征用于匹配，因而基于细节点的多种特征融合匹配将是指纹[1，2]识别算法研究的趋势。 自动指纹识别的应用 经过30多年的发展，生物识别技术的产品在主流社会中开始了比较大规模的应用，在很多国家，政府采用法律规定的方式来保证生物识别技术的应用。如在美国：911以后，三个相关法案（爱国者法案、边境签证法案、航空安全法案）都要求必须采用生物识别技术作为法律实施保证。总体上来讲，应用已经进入了以政府及应用为主的阶段。 指纹识别技术的应用非常广泛。典型的脱机应用有指纹锁，指纹保险柜、指纹考勤系统等。银行保管箱，自动取款机、网上交易等基于计算机的自动指纹识别系统都属于指纹识别技术的联机应用。 4
山东大学硕士学位论文 以指纹为代表的生物特征识别技术有望在将来的公共领域和民用领域扮演更[23]重要的角色。 指纹识别中面临的问题 指纹识别的可靠性度量 利用生物特征作为人身份鉴别的手段，尤其是作为证据用于法庭，往往需要满足以下五个条件： （1） 用于识别的某种生物特征技术，经过了统计假设测试； （2） 此项技术的错误率能够被估计； （3） 此项技术已有操作的标准； （4） 此项技术已经被同行业者评论及出版物； （5） 此项技术被广泛认可。 以上这五个条件，又被称为Daubert条件，它是美国高级法院，在审理Daubert与Merrell Dow 医药品公司的案件中提出的，并逐渐作为判断一项生物识别技术，能否被用于法庭进行生物身份鉴定的标准。非常不幸的是，只到目前为止，没有任何一项生物识别技术被证明可以满足以上五个条件。手写体识别则因为被证实无法全部满足Daubert条件，因而被认为无法用来进行身份鉴定。现在绝大多数手写体识别是作为一种计算机辅助输入技术来应用的。目前，关于指纹、人脸、[37-40]声音以及虹膜的唯一性研究是指纹识别研究中的一个热点。 非理想条件下的指纹匹配 指纹识别是一种高精度的生物特征识别技术，它的识别效果很容易受到其他因素的影响。因而，我们将那些影响指纹匹配系统做出正确判断的外界条件（非程序或者算法本身原因），称为非理想条件。 一般说来，影响指纹识别的非理想条件主要包含以下几种情况： a. 重要的特征区（of interest），没有被传感获取； b. 指纹图象中包含背景噪音； c. 整体指纹太淡，不清晰； 5
山东大学硕士学位论文 d. 局部指纹纹线严重粘联； e. 脊线结构中大的断裂。 除此之外，在指纹识别过程中可能出现两幅指纹的相对性形变较大和两幅指纹重叠区域过小等问题。 针对非理想条件下的指纹匹配是目前指纹匹配研究的重点。在非理想情况下的指纹识别，在特征提取方面主要面临的问题：用于识别的特征信息的丢失以及在特征信息中存在较大杂音；在指纹识别阶段体现在：用于识别的有效的特征信息不足（有效信息是指用于匹配的低噪音的指纹信息）。 课题的选择 基于以上分析，本文针对非理想条件下指纹识别问题，特征提取以及匹配两个方面进行研究：在匹配阶段，从两个方面进行研究，在识别过程中引入学习机器思想，利用指纹匹配获得的信息进行模板增强对模板信息进行处理；引入新的特征信息用于指纹匹配，增加指纹识别过程中可用的有效信息量。在特征提取阶段，将方向信息计算作为研究点，通过基于模型方向信息计算的改进，提高了方向信息的提取精度。本文主要针对上述三个关键技术----指纹模板增强、指纹匹配和方向信息估计进行了深入细致的分析和研究。 论文的组织和创新之处 本论文共分五章，其中第一章为绪论，主要针对自动指纹识别的有关概念进行介绍，确立课题的研究内容。 第二章到第四章为正文部分。第二章提出了基于细节点分布概率的模板增强方法，第三章研究并实现了一种混合匹配算法，第四章对现有基于模型方向信息估计方法的改进。 根据指纹细节点分布的特征以及EM算法设计了一种新的模板增强算法以及一种细节点与全局方向信息在分类器级别上的融合的混合匹配算法。是本文的主要创新所在。实验结果证明了该方法的有效性。此外，对基于模型的方向信息估计进行了局部改进，取得了较好效果，在技术实现上略有新意。 6
山东大学硕士学位论文 第二章 在线指纹模板增强 影响指纹识别的因素主要有三点：因为重叠面积不足造成的信息量不足、因为噪音、算法本身造成的指纹区内的特征信息的丢失、伪特征信息的误提取以及因为形变等噪声信息造成的信息不准确。在自动指纹识别过程中，指纹识别算法是在系统中存储的模板指纹和输入的输入指纹之间进行识别的，模板指纹质量对指纹识别性能有很大影响。 为了提高模板的质量，同行学者们提出了多模板、模板融合以及模板增强三种方法。多模板因为需要占用较大的存储空间、消耗较多的运算时间可不适合于应用于较大型的指纹数据库；模板融合因为很难对噪声干扰的信息进行有效地纠正，也不适用；模板增强，采用机器学习的观点，根据输入指纹的信息对模板进行改进，实验证明，效果良好。 因为目前绝大多数的指纹识别算法是基于指纹的细节点信息的，在系统模板中存储的信息主要细节点信息，因此，模板增强主要是针对模板中的细节点信息进行处理。模板增强研究的主要问题是学习规则的设定。Jaing等人，利用最小均方误差，减少模板指纹与实际输入指纹之间的差距的方法，对模板信息进行调整，实验证明可以提高识别系统的性能。 本章深入研究了指纹匹配过程中细节点的分布特点，充分考虑细节点之间的联系，提出了一种新的学习规则。实验证明，基于新的学习规则上面的模板增强算法效果更好。 在线模板增强思想简介 指纹识别的实质是指纹中特征信息的比对，而模板可以被认为是特征信息的载体。在非理想条件下，指纹识别的效果不好，很多情况下是因为采集模板过程中获得只是局部信息，并且在获得的信息中包含有噪音。因为采集器的限制，在每一次指纹采集过程中，我们获得的信息只能是局部的；因为其它因素(例如天气、指纹按压的方式等)的影响，我们在每一次指纹采集过程中获得的信息总是包含着 7
山东大学硕士学位论文 或多或少的噪音信息（形变也算作一种噪音）。因而，通过一次采集，就获得完整的、不含噪音的指纹信息，是很困难的。为此，需要多次采集指纹，获得完整信息。根据多次得到信息利用方式的不同可以分为三类，分别是：多模板、模板融合以及模板增强。 多模板，就是针对某一枚指纹，采集多幅图像当作系统中这个指纹的模板，利用多存储图像的办法来增加存储的信息量。在进行识别的时候，对于每一枚输入的指纹信息，需要与系统存储的同一幅指纹的多个模板相互比较，并按照某种规则，决定两枚指纹间的相似程度。多模板的思想实现简单，在实际中应用广泛。 多模板面临的问题，主要是因为大量模板的存在，导致系统需要占用大量的存储空间以及耗费大量的运算时间，特别是当指纹数据库较大以及要求精度高的[28]时候，这种现象尤为突出。为此，U. Uludag等人，针对多模板的方法，提出了模板选择的思想，即：利用聚类的思想，对大量模板分类，去掉质量较差的模板，保存质量相对较好的模板，这种方法在一定程度上减少了系统在存储空间和运算时间上消耗。 模板融合，就是将多模板方法中的多个模板融合为一个大的模板，去除各个模板中的重复信息，保留不同的信息。这样做，一方面因为融入了多次采集的指纹信息，从而避免了单一指纹图像因为信息量不足造成的误匹配（错误的拒识以及错误的误识的总称），另一方面减少了系统因为要存储大量模板所造成的系统消耗。模板融合又要分为两类，一类是针对指纹图像，一类是针对特征信息的。 针对指纹图像的方法，主要是将两幅指纹图像进行融合，然后在合成后的指[24,29]纹图像中提取信息，然后保存为模板；针对特征的方法，则是首先将两幅图[25-26]像中的特征信息提取，然后将两图像中的特征信息融合，并保存为模板。 模板融合的方法存在的问题主要是进行融合的图像的选择问题。影响指纹匹配的有两个因素：指纹图像中包含的信息量以及信息中噪音。模板融合通过将大量的模板融合，可以使得模板中信息量足够大，然而，指纹图像信息中的噪音（例如形变）一般具有较强偶然性，少量图像中的噪音无法代表其真实的分布，因而也就很难提供较好的模板用于匹配。 模板融合与多模板方法存在的问题主要是系统中存储模板固定不变。虽然， 8
山东大学硕士学位论文 指纹被证实是终生不变的，然而，由于各种现象的影响，例如天气变化引起的干湿指纹、人手指的剥皮以及人们按压指纹的方式等等，使得指纹会出现变化，因此，为了使得模板中的指纹模板能够代表指纹的特征，就需要对模板进行变化，[27]即是模板增强。Jiang等人，利用最小均方误差，减少模板指纹与实际输入指纹之间的差距的方法，对模板信息进行调整，实验证明可以提高识别系统的性能。 算法思想 基于细节点的指纹匹配算法，主要存在的问题是：真是细节点的丢失、虚假细节点的误提取，以及细节点参数（位置和角度）的不准确。因而，模板增强的任务就包含了两方面的内容，一是细节点的去伪存真；二是细节点参数的调整。 细节点的去伪存真 要对模板中的细节点进行调整，首先需要判断一个细节点的真伪。一般情况下，不考虑算法的造成的影响，真实的细节点往往比虚假的细节点出现的频率更高。因此，利用某一细节点出现的频率，也许就能够判断细节点的真伪。 为了验证我们的假设，我们建立了一个特殊的细节点点集，在这个细节点点集中包含了采自同一指头的120幅指纹的细节点点集。这个细节点点集的概率密度函数就代表了这幅指纹的细节点出现的频率。 在图(a)中，我们发现细节点出现的频率各不相同，（深色的位置代表出现细节点的机率高，深蓝色的位置代表几率最低）因此利用细节点出现的频率，完全可以将真伪细节点区分，从而将模板中的伪细节点除去。 为了将模板中丢失的真细节点补充进模板，可以将输入指纹中的信息添加到模板中。根据合理的规则，重复的对模板信息的加入真细节点，去处伪细节点的操作，就可以达到增强模板的目的。 细节点参数的调整 目前最常用的细节点参数主要是细节点的位置和细节点的角度。因为指纹图 9
山东大学硕士学位论文 像在采集过程中存在非线性形变，而我们在匹配过程中采用的线性映射并不能消除形变，因而同一个细节点在两个不同的细节点点集中的参数往往会略有不同。为了应对这种不同，大多数的匹配算法应用边界盒来应对参数间的差异[10]。因而，在指纹中细节点数量不变的情况下，系统的性能往往由细节点的参数与边界盒的大小影响。影响指纹识别系统性能有两方面的因素：同源指纹的匹配性能与非同源指纹匹配的性能。目前大多数系统往往只通过调整边界盒大小来获得更好的性能，但是只改变边界盒的大小不能够很好的提高系统的性能。这是因为应用较大的边界盒虽然能够使得更多同源指纹匹配，但是许多非同源指纹也会因此而匹配；应用较小的边界盒虽然会使得更多非同源指纹不匹配，但是许多同源指纹却也会因此而不匹配。 对于指纹中的一个细节点来说，最理想的情况是，在同源指纹中以相对高的概率的可能性被匹配，然而在非同源指纹中以相对低的概率匹配。为了对模板中细节点参数进行调整，我们首先对模板中细节点参数的分布进行非参数估计，见图(b)。由图(b)可知，在同源指纹中的细节点的位置信息符合高斯分布。因为非同源指纹的可能情况太多，因而无法对齐细节点参数分布进行估计，因而我们的调整细节点参数的目的是通过改变同源指纹的匹配性能来提高整个系统的性能。所以，模板中的细节点参数应该选择高斯分布的均值点。所以，我们的任务变成了如何确定混合高斯分布的参数估计问题。采用Expectation-Maximization(EM)算法可以轻易地进行高斯混合模型的参数估计。 h=<μ,μ>μμ1212EM算法：假设需要估计2个均值，，其中和模板增强算法为任意的初始值。重复以下的两个步骤来估计h，直到该过程收敛到一个稳定的h值。 zE[z]h=<μ,μ>ijij12步骤1：计算每个隐藏变量的期望值，假定当前假设成立。 z′′′h=<μ,μ>ij12步骤2：计算一个新的极大似然假设，假定每个隐藏变量所取E[z]h=<μ,μ>ij12的值为第1步中所取得的期望值，然后将假定替′′′h=<μ,μ>12换为新的假设，然后循环。 1 0
山东大学硕士学位论文 p(x=x|μ=μ)iiE[z]=ij2p(x=x|μ=μ)∑inn=112−(x−μ)ii22σe=12−(x−μ)in222σe∑n=1其中： mE[z]x∑ijii=1 μ =jmE[z]∑iji=1 EM算法的收敛性,但EM算法只能保证收敛到局部极值[43]。 算法描述 我们的模板增强算法包含三个部分：预处理、调整模板细节点以及调整模板细节点参数。 预处理 在指纹的模板增强之前，我们首先需要确定细节点的对应情况。如前所述，为了应对非线性形变，许多系统中采用了边界盒来应对细节点之间的差异。然而，应用这些细节点，却可能会使不同的细节点相互匹配，为了减少因为由此而带来的错误，我们在学习之前，首先对细节点匹配进行分类。 不失一般性，我们假设细节点β处于模板指纹中，而细节点γ处于输入指纹中，因此，四种类型是： 1. 只存在唯一的细节点β（γ）与细节点γ（β）匹配； 2. 有多于一个的细节点与β（γ）匹配； 3. 细节点γ与细节点β的位置相匹配，但是角度不匹配； 4. 不存在细节点 与β（γ）位置相匹配。 针对这四种不同的匹配类型，选择不同的学习方式。 11
山东大学硕士学位论文 (a) (b) (c) Probability density function of (a) minutiae sets,(b) location of a minutia and (c) direction of a minutia 图(a) 指纹的细节点,(b) 细节点位置以及(c) 细节点方向的概率密度函数 调整模板细节点 为了更加合理的判断的真伪，我们计算细节点出现的概率，需要考虑如下几 1 2
山东大学硕士学位论文 个方面的因素：细节点匹配的次数、细节点出现在指纹区域内的次数以及输入指纹的数目。由此可以得到细节点出现的相对频率（即细节点匹配次数与细节点出现在区域内的次数的比值）与绝对频率（即细节点匹配的次数与输入指纹的数目的比值），通过运用双阈值，更好的判断细节点的真伪。在计算指纹区域的时候，我们应用指纹细节点形成的凸包来代替指纹的区域。 为了能够丰富模板信息，需要向模板中添加新的细节点。Jiang等人[9]进行模板增强，主要是针对指纹区域内的信息，因而不能很好的解决因为采集面积不足造成的不匹配问题。为了能够使指纹的区域扩大，加入的细节点不应只包含模板区域内的细节点还应该适当的加入模板区域外的细节点。 通过对细节点的添加和删除，能够增加模板中真细节点，去处伪细节点，还能够扩大指纹的区域。 调整模板细节点参数 常用的细节点参数包括细节点的位置（x坐标和y坐标）和细节点的角度。因为目前无法确定细节点位置与细节点角度之间的关系，因而在我们利用EM算法对三维细节点信息进行调整时，假设它们之间相互独立。 对于上述的EM算法，在进行参数估计时要求更新的参数与输入的值在数量上是完全相同的，而且对应关系明确。然而在指纹识别中，因为很多原因的影响，即使是一个真实的细节点，他也并不是每次都会出现。因而，我们进行的参数更新，对于每次指纹匹配后的学习，只是对所有匹配的细节点点对。 ．模板增强算法 我们的模板增强算法描述如下： 1．用户首先进行指纹登记，并在系统中存入提取的细节点点集； 2．系统等待直到用户输入指纹，系统从指纹图像中提取细节点，并与系统中的模板逐一比对； 3．如果匹配的最高得分高于某一阈值，则继续，否则回到步骤2； 4．进行模板增强： 13
山东大学硕士学位论文 a. 预处理，找到所有的匹配点点对以及匹配关系 b. 更新模板中所有细节点的出现频率 c. 对于模板中的满足匹配关系1的所有细节点，按照EM算法依次更新细节点参数 d. 对于输入中的满足匹配关系4的所有细节点，将它们加入到模板中去 e. 根据阈值，去掉模板中所有细节点可信度过低的细节点，并更新系统模板，回到步骤2。 上述的模板增强算法，通过去除伪细节点，加入丢失的真细节点以及调整参数这三个方面改进模板，提高了系统的性能。 ．实验结果 为了能够衡量我们算法的性能，需要有一个数据库包含大量的指纹ID，并且每一个指纹ID对应有很多指纹。目前的许多公开指纹库，例如：FVC2000、FVC2002等等，对应每一个指纹ID只还有很少的指纹图像，无法有效的进行模板学习。Jiang等人建了一个用于模板增强的数据库，然而可惜的是我们无法获得其指纹数据。因而，我们只好自己建立数据库，并在起上进行对比试验。同时，为了提高我们数据的可靠性，我们选择fvc2000的数据库，进行少量样本的学习。 为了能够有效的模拟实际应用的情况，我们选择了16个指纹ID，应用采集器ZYZ202-B，采集图像大小320*320。对于每个指纹ID每天采集一次，直到采够300枚指纹图像为止。在实验中，每一枚指纹输入后要与所有的指纹进行比较，因而在实验中，同源比对的次数为299*16=4784，非同源比对次数299*15*16=71760。 为了体现我们的算法的有效性，我们将我们的算法、Jiang等人的算法、原始的算法在结果上作了比较。因为在进行指纹匹配和细节点提取等方面采用了不同的方法，而且指纹库的不同，因而我们无法直接与Jiang的算法进行比较，因此，我们模拟Jiang算法，并在我们的数据库上进行测试。图. 是在我们自建库上运行得到三条ROC曲线图。实验结果表明，我们的算法不但能够同源匹配得分，而且还能够降低非同源的匹配得分，因而我们的增强算法是有效的。 FVC是目前主要的公开数据库之一。为了加强我们试验的可信性，我们选择 1 4
山东大学硕士学位论文 (a) (b) Fig. . (a) False match rate and false non-match rate versus threshold and (b) ROC curve 图. (a) 错误的匹配率与错误拒绝率与验证阈值之间的关系 (b) 为ROC曲线 FVC2000作为我们试验的数据库。FVC2000有四个子库：DB1_a，DB2_a，DB3_a和DB4_a。每一个数据库包含100个指纹ID，每个指纹ID对应8幅指纹图像。在实验中，主要计算同源指纹匹配得分以及非同源指纹匹配得分。其中在计算同源得分时是将每个指纹ID对应的8幅指纹图像，两两比较，从而获得2800个同源匹配得分；在计算非同源匹配得分时，只是将每个指纹ID对应的第一幅指纹两两比较，从而获得4950个非同源得分。Jiang等人设计了一种实验方法，首先，对于任意一个指纹图像，利用任意的6幅同源指纹进行增强，然后再与第7幅同源指纹进行匹配，得到同源匹配得分，共获得2800个同源匹配得分。然后，对于同源指纹中的第1幅指纹图像，利用第2到第7幅指纹图像进行模板增强，共获得100个增强后的模板，将这些模板两两比较，获得4950个非同源得分。 利用Jiang等人[8]的这个方法，我们进行了实验，结果见图。实验结果表明，在FVC2000的四个数据库上，我们的实验结果优势明显，我们的实验算法行之有效。 ．本章小结 本文提出了一种新的指纹模板增强算法，针对指纹模板中存在的真细节点丢失、伪细节点误提取以及细节点参数由于受形变影响产生的差异等问题进行了相应的处理。首先根据细节点出现频率，利用双阈值判断细节点真伪；然后利用对 15
山东大学硕士学位论文 细节点偏差分布的估计，利用EM算法进行参数估计。实验证明，我们提出的指纹模板增强算法，能够提高识别算法的精度，与我们模拟Jiang等人[8]的算法形成的结果相比，我们的算法结果更好。 (a) (b) (c) (d) ROC curves on fvc2000 (a) DB1_a, (b) DB2_a, (c) DB3_a, (d) DB4_a 图. 在fvc2000指纹库上的ROC曲线图，(a) 为DB1_a, (b)为 DB2_a, (c)为 DB3_a, (d)为 DB4_a 1 6
