指纹识别匹配算法研究论文

1、国内图书分类号：tn47国际图书分类号：621.3.049.77工学硕士学位论文指纹识别匹配算法研究硕 士 研 究 生： 闫志锋导师： 王明江副教授申请学位级别： 工学硕士学 科 、 专 业： 微电子学与固体电子学所 在 单 位： 深圳研究生院答 辩 日 期： 2008 年 12 月授予学位单位： 哈尔滨工业大学classified index：tn47u.d.c.: 621.3.049.77dissertation for the masters degree in engineeringresearch on matching algorithmin fingerprint identif

2、icationsystemcandidate：supervisor：academic degree applied for：specialty：affiliation:date of defence：degree-conferring-institution：yan zhifengassociate prof. wang mingjiangmaster of engineeringmicroelectronics and solid-stateelectronicsshenzhen graduate schooldec, 2008harbin institute of technology哈尔

3、滨工业大学工学硕士学位论文摘要随着科技的进步，生物识别技术日益受到人们的关注。指纹识别是最重要的生物识别技术之一，不仅已在司法领域取得巨大成功，而且开始广泛涉足民用领域，在现代社会中发挥着重要作用。指纹识别系统涉及图像处理、模式识别、计算机、传感器等多项技术。在过去的几十年间，指纹识别技术取得了飞速的发展。匹配算法在指纹识别系统中占据重要地位。匹配算法的好坏，直接关系到匹配结果的准确度。目前，关于匹配算法的研究很多，并且已经提出了一些成功的算法，诸如基于特征点的匹配、基于图像的匹配等。在这些算法中，图像的质量必须满足一定的条件。也就是说图像质量不能太差，能够提供足够的特征信息用于匹配。以基于特

4、征点的匹配算法为例，该算法要求指纹图像中的特征点数目必须达到一定的数目，否则无法进行匹配。然而，在实际应用中，有时我们又不得不处理质量较差的图像。例如，在刑侦领域，指纹是一项重要的证据，但采集到的指纹往往是模糊不清、存在形变或者只是很小的一部分图像。同时，外伤也会引起指纹的局部改变。要处理这些特殊情况下的图像，就对匹配算法提出了新的挑战。基于此类问题，本文提出的两种新的匹配算法。本文首先简要介绍指纹识别系统，然后重点研究了匹配算法。论文除了分析目前常用的几种匹配算法外，仔细阐述了自己提出的两套匹配算法：点线结合的指纹匹配算法和基于四特征点拓扑结构的指纹匹配算法。点线结合的指纹匹配算法将特征点与

5、其所在脊线紧密关联，以脊线为匹配的基本单元。基于四特征点拓扑结构的匹配算法以四个特征点构成的拓扑结构为基本匹配单元，充分考虑了特征点间的相互关系。实验证明，新的匹配算法均具有很好的抗噪能力。关键词指纹识别；匹配算法；特征信息i哈尔滨工业大学工学硕士学位论文abstractwith the development of the technology, biometric identification has attractedmore and more attention. and fingerprint identification is one of the most importantpa

6、rts of it. it has not only made a great progress in judicature field, but also hasbegun to play an important role in pepoles daily life. fingerprint identificationsystem involves a lot of technologies, including picture processing, patternrecognition, computer, transducer, and so on. in the past ten

7、s years, fingerprintidentification has made a good progress.matching algorithm is a very important part in fingerprint identification system.the performance of it has a direct effect on the accuracy of the identification result.at present, massive research on matching algorithm has been done and som

8、e successalgorithms have been reported, such as feature-point-based matching algorithm,image-based matching algorithm and so on. in these algorithms, the quality of thefingerprint image must fulfill some conditions. that means the quality should be nottoo poor, and the feature information should be

9、enough for matching. take feature-point-based matching algorithm as an example, the feature-points number shouldexceed certain value; or the matching operation will be denied. however, sometimeswe have to deal with some poor fingerprint image. for example, in criminalinvestigation, the fingerprint i

10、s one important proof. but the image captured isalways fuzzy, distortion or partial. also, sometimes the trauma will result in the localchanging in the fingerprint. how to deal with these kinds of fingerprint give newchanllenge to matching algorithm. the new matching algorithms in this thesis are to

11、committed to these situations.in this thesis, the fingerprint system will be introduced in brief firstly; then is thedetailed presentation of the matching algorithm. except for the analyzing of somepopular matching algorithms, two new matching algorithms of our own will beintroduced in detail, respe

12、ctively. one is matching algorithm using character pointsand lines, the other is matching algorithm basing on four character pointtopology structure. the former one considers the character points and lines together,and takes the lines as the basic matching unit. the latter bases on a special topolog

13、yii哈尔滨工业大学工学硕士学位论文structure, which will make good use of the space information of the minutiaes, andalso, topology structure revising will be done for each matching, respectively.experiments on a set of fingerprints captured with a scanner showed that the newalgorithms had a good effect.keywordsfing

14、erprint identification, matching algorithm, feature informationiii哈尔滨工业大学工学硕士学位论文目录摘要 .iabstract . ii第 1 章 绪论 . 31.1 课题背景 . 31.2 国内外研究现状及课题意义 . 51.3 论文内容及结构 . 7第 2 章 指纹识别系统综述 . 82.1 图像采集 . 82.2 预处理 . 92.3 后处理 . 172.4 特征提取 . 182.5 特征匹配 . 192.6 本章小结 . 19第 3 章 指纹识别算法研究 . 203.1 指纹脊线跟踪 . 203.1.1 8-邻域编码 .

15、 203.1.2 窗口法 . 213.2 伪特征信息处理 . 223.2.1 短线、断线处理 . 233.2.2 小孔去除 . 233.2.3 小桥去除 . 243.2.4 毛刺去除 . 243.2.5 伪特征点去除 . 253.3 奇异点提取 . 253.4 匹配算法概述 . 263.5 常用指纹匹配算法介绍 . 283.5.1 基于点模式的匹配算法 . 283.5.2 基于纹理模式的匹配算法 . 303.5.3 基于图的匹配算法 . 311哈尔滨工业大学工学硕士学位论文3.6 本章小结 . 31第 4 章 指纹识别匹配算法改进 . 324.1 点线结合的指纹匹配算法 . 324.1.1 算

16、法背景 . 324.1.2 算法特点 . 334.1.3 算法概述 . 354.1.4 相似度计算 . 374.1.5 脊线定位 . 374.1.6 脊线匹配 . 384.1.7 算法小结 . 394.2 基于四特征点拓扑结构的指纹匹配算法 . 394.2.1 算法目的 . 394.2.2 算法特点 . 404.2.3 算法概述 . 404.2.4 拓扑结构构建 . 414.2.5 拓扑结构匹配 . 424.2.6 算法小结 . 434.3 本章小结 . 43第 5 章 实验结果及分析 . 445.1 实验条件及环境 . 445.2 测试指标 . 445.2.1 指纹图像库 . 445.2.2

17、 测试方案 . 455.2.3 测试结果 . 455.3 本章小结 . 48结论 . 49参考文献 . 50攻读硕士学位期间发表的学术论文 . 55哈尔滨工业大学硕士学位论文原创性声明 . 56哈尔滨工业大学硕士学位论文使用授权书 . 56致谢 . 572哈尔滨工业大学工学硕士学位论文第1章绪论1.1课题背景随着科技的进步，人类社会已进入快速发展的信息时代，人与人之间的信息交流变得更加方便和快捷。然而，科技在提高人们工作效率，推动社会发展的同时，也带来了一系列有关安全的问题。例如，在信息高度发达的今天，任何非法窃取、冒用或篡改信息的行为都有可能给社会或个人带来重大损失。而实行个人身份鉴别是保障

18、信息安全的重要途径，所以如何快速准确地辨别出个人身份，以确保信息安全和维护社会秩序，已成为现代社会亟待解决的一个重要课题。古往今来，为了保证生命、财产和信息安全，人类尝试过各种各样的方法来检验目标人物的真正身份1。传统的方法是验证该人是否持有有效的证件或信物，远至古人的印章、兵符、钥匙，近至高科技时代的智能卡、电子密码，尽管识别方法不断进步，但这些“以物认人”的方法存在着明显的缺陷：易丢失、遗忘、被复制或盗用。在目前需要大量身份鉴别的社会中，传统的身份鉴别方式己经越来越不能满足社会发展的需要。于是，生物识别作为一种新的稳定可靠的身份识别技术悄然兴起。所谓生物识别 24，就是利用人体的生理特征或

19、行为动作来认证人的身份。因为这些特征对于每个人来说是独一无二的，其它人无法复制取代或者假冒，用它们来识别人的身份，其效果显然要优于传统的身份识别方法。但是，并不是所有人体特征或动作都能用于身份识别，一项生物特征5，只有满足以下条件，才可能作为验证个体身份的依据：(1) 普遍性。所谓普遍性，是指它应该是人人具有的特征信息，而那些个体的个别的特征显然不能作为身份判别的依据。(2) 唯一性。唯一性指这些特征信息是独一无二的，不同人的特征信息是完全不同的，具有明显的可区分性。(3) 稳定性。稳定性是指这些特征信息或特征行为应在一个相当长的时间内保持不变，如随着个体年龄的变化，这些特征信息应相对保持稳定

20、。(4) 可采集性。可采集性也是很重要的一点。因为只有能采集，才能进行处理、存储、辨认识别等一系列相关操作。3哈尔滨工业大学工学硕士学位论文此外，除了满足以上几点外，这些特征信息还应该容易实现，资源消耗少，对环境及硬件设备要求低，易于为人们所接受，具有很好的防伪性。目前常用的生物识别技术主要分为两大类，生理特征和行为特征。生理特征主要包括：指纹、掌形、虹膜、视网膜、人脸、面部热像等；行为特征主要有：签名、语音、步态、击键等。以上各类特征都在不同程度上满足普遍性、唯一性、稳定性和可采集性等基本特性的要求。因此，基于这些特征，已经开发了多种生物识别技术，其中应用较广的主要包括：指纹识别、掌形识别6

21、、虹膜识别7、视网膜识别、人脸识别8、面部热像识别、签名识别、语音识别等。在以上各类生物识别技术中，就应用程度而言，指纹识别占据了绝对的优势，国内外市场上的主要生物识别产品基本上都是基于指纹识别技术的。视网膜识别具有高度的准确性和防伪性，但在采集方面要求较高，因此并未普及应用，目前主要用于需要高度安全防范的场合。其它几种被看好的技术是虹膜识别、人脸识别和语音识别。虹膜识别具有相当于视网膜识别的高准确性和高防伪性，对采集设备的要求则相对低于视网膜识别。人脸识别和语音识别比较容易为人们所接受，具有较大的应用潜力。表 1-1 是集中常用生物识别技术效果的比较。表 1-1 常用生物特征比较table

22、1-1 comparison of biometric character生物特征指纹掌纹虹膜视网膜人脸语音签名普遍性mediummediumhighhighhighmediumlow唯一性highmediumhighhighlowlowlow稳定性highmediumhighmediummediumlowlow可采集性mediumhighmediumlowhighmediumhigh性能highmediumhighhighlowlowlow接受程度mediummediumlowlowhighhighhigh防伪性highmediumhighhighlowlowlow指纹识别技术是利用指纹进行

23、身份识别的生物识别技术，指纹是人的手指表皮上呈现的纹线9。指纹具有稳定性、唯一性和普遍性等重要特征。首先，它是与生俱来的，且在人的一生中基本保持不变，这是它的稳定性。其次，两个不同的人具有相同指纹的概率是极小的，包括双胞胎，指纹都不会完全相同，甚至同一个人同一只手的不同手指的指纹也是不同的。从概率学上讲，两个人具有相同指纹的概率约为几十亿分之一。指纹的唯一性和不变性两个特点为指纹作为身份鉴别提供了客观的依据。指纹几乎每个人都有，这是它的普遍性，同时指纹采集也容易为人们所接受，易于采集处理。指纹的这些特征，使4哈尔滨工业大学工学硕士学位论文指纹识别技术成为一种易于实现推广且具有广阔应用前景的一项

24、身份识别技术。实际上用指纹作为身份鉴别的手段已经有几千年的历史了。现代指纹人身标识技术要追溯到十六世纪晚期，当时一位英国的植物形态学者对指纹做出了系统的研究并发表了一篇论文，文中详细分析了指纹的犁沟、脊线、汗腺孔的结构，这篇文章被认为是有关指纹技术的第一篇科学文献。后来相继出现了关于指纹分类策略等的一系列著作，逐渐奠定了指纹识别技术的理论基础。十九世纪末，随着对指纹进行了更为深入的研究，提出了利用细节特征点进行单个指纹分类的方法，提高了指纹验证效率，为指纹用于人身标识起了重要的推动作用。发展至二十世纪早期，结合解剖学观点，人们对指纹的构成已经有了很好的了解，指纹鉴别被司法部门正式规定为合法的人

25、身辨识方法，指纹鉴别己经成为司法调查的一道标准程序，指纹鉴别机构在世界范围内开始建立。上世纪 60 年代，随着计算机的出现，人们开始了对自动指纹鉴别技术的研究。其中以美国联邦调查局开发的自动指纹鉴别系统最为成功，极大地提高了法律相关部门的效率，同时也很好地推动了自动指纹鉴别系统向民用领域的转化。20 世纪末期以来，指纹识别逐渐走向民用10，通过使用指纹验证来取代各个计算机应用程序的密码就是最为典型的实例。可以想象如果计算机上的所有系统和应用程序都可以使用指纹验证的话，人们使用计算机就会非常方便和安全，用户不再讨厌必要的安全性检查，而开发商的售后服务工作也会减轻许多。目前许多国家都将指纹识别技术

26、作为重大基础战略技术加以研究，911 事件发生后，这一技术更是受到美国、日本以及欧洲各国的高度重视。在此前后，国际上还纷纷成立了各种官方和非官方的生物识别组织，其中著名的有ibg、ibia、bc 和 bioapi 等。我国也于 2003 年 9 月 14 日在中国科学院自动化研究所设立了生物特征认证与评测中心，以期进一步推动生物识别技术的发展。1.2国内外研究现状及课题意义从 20 世纪初期起，指纹识别开始在西方被正式接纳为合法的身份鉴别方法并成为标准的法律依据，世界各国纷纷设立指纹识别机构并建立罪犯指纹数5哈尔滨工业大学工学硕士学位论文据库。美国联邦调查局(fbi)于十九世纪二十年代设立指纹

27、识别处，并收集了81 万张指纹卡片。与此同时，各种指纹识别相关技术包括潜在指纹获取、指纹分类和指纹匹配等都得到了极大发展11。早期的指纹识别工作只能由人工来完成，指纹专家凭借知识和经验对指纹图像进行辨认。随着指纹识别技术在刑侦领域的广泛应用，各国司法机关的指纹数据库越来越大，并且一直都在不断增长中。如此大的数据量，仅仅依靠人工是远远不能满足需要的，人们为此开始寻找其它办法。计算机的出现和发展，有力地推动了指纹识别技术的发展，从 20 世纪 60年代起，美国 fbi、英国内政部和法国巴黎警察局开始着手研究自动指纹识别系统(automatic fingerprint identification

28、system，简称 afis)，希望借助现代计算机超强的运算能力来节约人力和时间。美国于 1963 年最先开始研究工作，并于 1975 年成功推出第一个商业化系统 printrak250。日本随后在 1975 年进行研究，于 1982 年开发出 necafis 并投入使用。早期的自动指纹识别系统只能运行在大型计算机或工作站上，并通过体积较大的光学设备来采集指纹，使用不便且价格昂贵。随着技术的进步，个人计算机已经可以独立完成指纹识别任务，极大地方便了自动指纹识别系统的研究和应用。如今，体积小、功耗低的嵌入式处理器和半导体指纹图像传感器的出现更使得嵌入式指纹识别系统成为可能，从而使自动指纹识别系统

29、得以向小型化、一体化方向发展。与此同时，模式识别和图像处理方法的进步也为指纹识别的算法理论研究提供了坚实的基础，使得自动指纹识别系统能够在有限的硬件技术条件下不断得到改善。日前，国外从事指纹识别研究的公司、学校及科研机构多达二百多家。其中以 ibm、intel 、nec 及韩国现代等公司较为著名。著名的研究高校主要有加州理工学院、密歇根州立大学模式识别与图像处理实验室、意大利大学特征识别系统实验室等。研究机构有美国国家标准局视觉图像处理研究组、沃特生研究中心等。这些国外公司、研究机构在指纹的采集、图像处理、识别、比对等方面的技术己经比较成熟。各种相应的产品也已投放市场多年。其中美国fbi 提出

30、的指纹分类及处理模型使用最为广泛。国内指纹识别技术研究起步较晚，从上个世纪 80 年代初期开始研究指纹自动识别技术。我国的公安部门在 20 世纪 80 年代初与各大高校合作，共同研究自动指纹识别系统。从事指纹识别的研究机构主要有北京大学信息中心，清华大学自动化系，北京邮电大学，中科院，长春光机所等。本课题研究的指纹识别系统主要应用于汽车门禁锁，把指纹当作开锁的钥6哈尔滨工业大学工学硕士学位论文匙。随着汽车的普及，该方向是目前比较有前景的一个方向之一。该技术把锁的主人的指纹加密后存储在指纹识别芯片上，并在芯片的后端加装机械开锁系统，当录入指纹时，指纹芯片先对指纹进行一系列预处理及特征信息提取，通

31、过与事先建立的指纹数据库进行比对，就可以确认开锁者是否具有开锁的权限，从而进行下一步的操作：发出开锁指令以驱动开锁机械系统或者发出拒绝信号。以指纹作为开锁的钥匙，既方便快捷又易携带，同时可以避免因遗忘带来的麻烦。指纹识别算法的开发与研究，将给人们的生活带来巨大的便利，相信指纹识别别技术具有更广阔更美好的明天，同时它的应用也将广泛地普及于人们的日常生活中。1.3论文内容及结构本文重点对指纹识别匹配算法进行研究，并在算法研究的基础上提出新的匹配算法。全文的内容分为五章展开。第 1 章简要介绍了课题的研究背景、现状及意义，然后是本文的研究工作及各章内容安排。第 2 章概括性地介绍了指纹识别系统的基本

32、原理。第 3 章是对指纹识别算法的研究，内容包括脊线跟踪、伪特信息处理、奇异点提取及常用指纹匹配算法介绍与分析等。第 4 章是对指纹匹配算法的改进，这是本文的重点，在本章中，提出了两种新的匹配算法，并对他们的特点及关键技术进行分析。两种算法均已申请发明专利。第 5 章是在建立的指纹数据库上对算法进行测试，对实验结果进行分析和总结。最后是结论，对论文进行归纳和总结。7哈尔滨工业大学工学硕士学位论文第2章指纹识别系统综述早期的指纹识别技术仅限于人工或半自动化的查找和匹配，随着计算机技术的发展，指纹识别系统的逐渐实现了自动化，出现了自动指纹识别系统。与人工处理相比，自动的指纹识别技术并不直接存储指纹

33、的图像，而是直接存储指纹图像中的特征信息。这样既有利有保护个人隐私，也大大节省了存储空间。自动指纹识别系统的工作原理是先通过指纹读取设备获得图像，并对原始图像进行初步处理，使之更清晰；然后提取指纹的特征信息数据，这些数据通常称为模板，保存为数据库中的一条记录。最后，通过计算机模糊比较的方法，把两个指纹的模板进行比较，计算出它们的相似程度，最终得到匹配结果。指纹识别算法最终都归结为在图像上找到并比对指纹的特征信息。在指纹识别系统中，采集到的指纹图像并不能直接用于匹配。图像必须先经过一些处理步骤，才能用于匹配。这主要基于两点原因，一是采集到的图像质量、规格参差不齐，直接用于匹配难以得到稳定可靠的结

34、果；二是在 afis系统中，只有将图像转化为系统能够识别的数据格式，系统才能进行自动识别和匹配。这些处理步骤主要包括预处理、后处理、特征提取、特征匹配等，其中预处理又包含图像软化、图像规格化、方向场计算、频率提取、有效区域分割、增强、二值化、细化等过程。2.1图像采集指纹采集是指纹识别的第一步。传统的指纹采集方法是用手指蘸上墨水或印油在纸上按压，然后用扫描仪摄取。由于其严重的不可靠性，该方法己经被淘汰。目前主要的指纹采集技术有光学指纹采集技术、半导体指纹采集技术和超声波指纹采集技术。光学指纹采集技术是目前应用最广泛的指纹采集技术，其原理是光的全反射；半导体指纹采集技术最常用的是硅电容指纹图像传

35、感器，采集图像时，指纹的脊和谷对应不同的电容值，通过电子度量来捕捉指纹；指纹的脊和谷具有不同的声阻，它们反射回接收器的超声波的能量不同，一次可以通过测量超声波能量确定图像，这是超声波指纹图像采集技术的基本原理。这些设备中，光学扫描仪技术比较成熟、性价比较高，且能承受一定程度温度变化，稳定性好，因而得到广泛应用。本课题中指纹图像采用光学扫描仪采集。8哈尔滨工业大学工学硕士学位论文2.2预处理采集的图像因为外界噪声等原因，可能存在模糊不清、部分区域连接不好甚至错误连接的情形，所以在进行特征提取及匹配之前要先进行预处理，保证得到可靠的图像。预处理主要包括图像软化、图像规格化、方向场计算、频率提取、有

36、效区域分割、增强、二值化、细化等过程。图像软化 在自动指纹识别系统中，输入的指纹图像由于各种原因的影响，比如用力不均或手指不干净等原因，从而使采集到的指纹图像是一幅含噪声较多的灰度图像，因而必须先进行平滑处理。传统的去除噪声的方法是对指纹图像进行低通滤波，以此来消除高频噪声。基于 55 子块软化是一种常用的软化算法，该法是先选取一个包含中心点的 55 图像子块，然后计算含中心点的四个五边形和四个六边形以及一个 33 的矩形区域的灰度均值和方差，取方差最小的区域的灰度均值作为中心点的灰度值。经过实验测试，简单采用一个 33 的矩形区域计算均值，作为软化后的的像素值，与 55 子块法软化结果相差不大，亦能满足要求。故为了减少运算量，本课题中软化算法直接采用一个 33 的矩形进行软化处理。如图 2-1 所示。a)为四个五边形示意图，b)为四个六边形示意图，c)为本文采用的33 矩形。a) 五边形a) pentagonb) 六边形b) hexagonc) 矩形c) rectangle图 2-1 图像软化的区域fig.2-1 area of image softening图像规格化 受采集设备工作环境及