（信号与信息处理专业论文）自动指纹识别算法研究与实现.pdf

摘要 摘要 由于指纹的唯一性、可靠性和稳定性，指纹已成为身份识别和鉴定的一个重 要标志，并被公认为“物证之首”。尽管已有多种自动指纹识别技术的成型产品， 但因为指纹图像的噪声、皮肤弹性的非线性等因素，理想的自动指纹识别系统依 然是一个很困难的研究任务。因此，寻找有效快捷的对指纹图像处理的算法，对 基于计算机和网络环境下的指纹特征技术进行研究，仍然是解决指纹识别技术难 题的有效途径。 本文对基于细节特征点的指纹图像预处理及后处理、特征提取和匹配的部分 算法进行了研究。 在预处理方面，通过对0 v 1 7 2 0c m o s 采集得到的指纹图像的分析，结合图 像直方图信息，实现了一种指纹图像的简单分割方法；在方向图和脊线频率的基 础上，实现了基于二阶导数的指纹图像二值化算法；实现了一种1 6 邻域的细化 算法，构成了一个完整的指纹图像预处理过程。 对于细化后的二值图像，我们在后处理中对伪特征进行了剔除，减少了特征 提取和匹配的复杂度。 在指纹图像的特征提取和指纹匹配方面，本文以向量表示每个指纹特征点的 信息，以向量组构成整个指纹的信息；为了提高指纹旋转后的识别率，本文还对 指纹的特征提取和匹配算法做了改进。 本文在p c 机上用c + + b u i l d e r 实现了整个自动指纹识别系统的算法，并且， 该系统的所有算法都通过了硬件调试。试验结果显示，本文采用或改进的指纹处 理算法很好的完成了各自的功能，达到了设计的要求；整机联试显示，该系统达 到了规定的指标要求。 关键词：自动指纹识别系统，预处理，特征提取，匹配。 a b s t r a c t a b s t r a c t f i n g e r p r i n tr e p r e s e n t st h em o s ts e c u r ew a yt oi d e n t i f yi n d i v i d u a l sb e c a u s ei t p r o v i d e san o v e la p p r o a c ht or e c o g n i z et h ei d e n t i t y , o rv e r i f yt h ec l a i m e di d e n t i t y t h r o u g hau n i q u e ，h i g h l yr e l i a b l ea n dr o b u s tp h y s i c a lc h a r a c t e r i s t i co rp e r s o n a lt r a i t n o w a d a y s ，m a n yp r o d u c t so ff i n g e r p r i n th a v eb e e no f f e r e d ，h o w e v e r , b e c a u s eo f t h e d i s t u r b a n c eo fi m a g en o i s ea n dn o n l i n e a ro ft h es k i ne l a s t i c i t y , t oa c h i e v ea ni d e a l a f i s ( a u t o m a t i cf i n g e r p r i n t i d e n t i f i c a t i o n s y s t e m ) i s s t i l lad i f f i c u l tr e s e a r c h p r o b l e m s oi ti sa ne f f i c i e n ts o l u t i o nt ot h ep r o b l e m t h a tt of i n da ne f f i c i e n ta n df a s t a l g o r i t h mp r o c e s s i n gf i n g e r p r i n t si m a g e s ，a n dt os t u d yt h et e c h n o l o g yo ff i n g e r p r i n t c h a r a c t e r i s t i co nc o m p n t e ra n dn e t w o r k p a r t sa l g o r i t h m so ft h ep r e p r o c e s s i n g ，p o s t - p r o e e s s i n g ，m i n u t i a ee x t r a c t i o na n d m a t c h i n go f a f i s b a s e do nm i n u t i a ei sd i s c u s s e di nt h i sp a p e r i nt h ea s p e c to fp r e p r o c e s s i n g ，a ne a s ys e g m e n t a t i o nm e t h o di s i m p l e m e n t e d t h r o u g h t h ea n a l y s i so f f i n g e r p r i n ti m a g e sf r o mo v l 7 2 0c m o sa n dt h eh i s t o g r a mo f t h ei m a g e s w ea l s oi m p r o v eo nt h eb i n a r i z a t i o nm e t h o do f f i n g e r p r i n ti m a g e sb a s e d o nt h e2 ”d e r i v a t i v eb yt h eo r i e n t a t i o na n dr i d g ef r e q u e n c yo f t h ei m a g e sa n dt h e na n e w t h i n n i n ga l g o r i t h mi si m p l e m e n t e d o n1 6 - p i x e l s - n e i g h b o r sz o n e w h i c hc o m p o s e t h ew h o l e p r e p r o c e s s i n ga l g o r i t h m t h ef a l s em i n u t i a ea r ee l i m i n a t e df o rt h et h i m _ i e di m a g ei np o s t p r o c e s s i n g ， w h i c hr e d u c et h er e s p o n s e - t i m er e q u i r e m e n ti nm i n u t i a ee x t r a c t i o na n dm a t c h i n g i nt h ea l g o r i t h mo fm i n u t i a ee x t r a c t i o n ，av e c t o ri s f o rt h ei n f o r m a t i o no fa m i n u t i a ，a n dt h em i n u t i a eo f af i n g e r p r i n ti m a g e a r ec o m p o s e do f v e c t o r s t oi m p r o v e t h em a t c h i n gr a t eo ft h er o t a t ei m a g e s ，w ei m p r o v eo nt h ea l g o r i t h mo fm i n u t i a e e x t r a c t i o na n df i n g e r p r i n tm a t c h i n g c + + b u i l d e ri m p l e m e n t sa l la l g o r i t h m so fa f i so np c e x p e r i m e n t sr e s u l t ss h o wt h a t a l l a l g o r i t h m sp e r f o r m w e l l t h ew h o l es y s t e m i st e s t e do nt h eh a r d w a r eo fd s f , t o o ，w h i c h d e m o n s t r a t e st h a to u rs y s t e mm e e t s t h eg i v e nr e q u i r e m e n ta n dw o r k sw e l l ， k e y w o r d s ：a u t o m a t i cf i n g e r p r i n t i d e n t i f i c a t i o ns y s t e m ，p r e p r o c e s s i n g ，m i n u t i a e e x t r a c t i o n ，f i n g e r p r i n tm a t c h i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行豹研究工作及取得的研究成果。 撼我所知，除了文中特别加以标注和致谢能地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得电予科技大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所傲的任何煲献均已在论文中作了明确的说明并表示谢 意。 签名：商堡缝日期：对年岁月, z e t 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 日期；勿吐年霸 第一章绪论 第一章绪论 随着科学技术的不断发展，信息化时代的到来，越来越多的高科技电子产品 逐渐进入了人们的日常生活( 如电脑、自动提款机、电话、门禁控制、各种身份 识别的智能卡等) ，为人们的日常生活带来了极大的方便，身份识别也随之成为 人们日常生活中经常遇到的一个基本的问题。生活中几乎每时每刻都需要鉴别别 人的身份，证明自己的身份，而传统身份识别方法正越来越收到局限。 传统的身份识别方法主要基于身份标识物品和身份标识知识。身份标识物品 如钥匙、证件、自动提款机的银行卡等；身份标识知识包括用户名、密码等。在 一些安全性要求严格的系统中，往往将这两者结合起来，如自动提款机要求用户 同时提供银行卡和密码。但标识物品容易丢失或被伪造，标识知识容易被遗忘或 记错，更为严重的是传统身份识别系统往往无法区分标识物品真正的拥有者和取 得标识物品的冒充者。一旦他人获得标识物品，就可以拥有相同的权力。因此， 没有很好的身份识别与授权系统就不能很好的开展诸如电子商务电子政务等信 息化操作。据国外有关资料统计，在公司内部，存在很多非授权使用计算机系统 的工作人员，并且因此造成重大的损失；与此同时，假信用卡所造成的损失一年 在4 0 亿到6 0 亿美元之间。人们需要在与机器之间进行交易时安全方便、简单快 捷。因此，迫切需要有一种准确、方便、安全的识别技术来代替现有的身份识别 方法。 由于人体的身体特征具有不可复制的特点，人们便把目光转向了生物识别技 术i l 】，希望可以籍此技术来应付现行系统安全所面临的挑战。要把人体的特征用 于身份识别，这些特征必须具有唯一性和稳定性。研究和经验表明，入的指纹、 掌纹、面孔、发音、虹膜、骨架等都具有唯一性和稳定性的特征，即每个人的这 些特征都与别人不同、且终生不变，因此可以据此识别出人的身份。基于这些特 征，人们发展了指纹识别、面部识别、发音识别等多种生物识别技术，目前许多 技术都已经成熟并得以应用。其中指纹识别技术更是生物识别技术的热点。 指纹人人都有，人人不同，它具有唯一性、再生性的特点。现代科学界的结 论是：人类人口按6 0 亿计，则需要3 0 0 年才可能出现重复的指纹，概率几乎为 零：其次，一个人在母腹中7 个月就定型，随着年龄的变化，人的相貌体格都在 变化，雨指纹却保持不变：另外，只要不伤及真皮组织，指纹即使被磨掉，也很 快会长出来。基于以上特征性，指纹在越来越多的领域，如社会安全、办公安全、 资讯安全、金融安全、家庭安全、个人安全等方面得到广泛的应用，被认为是身 第一章绪论 份辨认的特征之首。 1 1 生物识别与指纹识别简介 a 生物识别技术( b i o m e t ri ci d e n t i f i c a t i o nt e o h n o l o g y ) 所谓生物识别技术就是：通过计算机与光、声、生物传感器和生物统计学原 理等高科技手段密切结合，利用人体固有的生理特性( 如指纹、脸像、虹膜等) 和行为特征( 如笔迹、声音、步态等) 来进行个人身份的鉴定。常见的生物识别 技术主要有9 种：指纹、脸形、虹膜、视网膜、手写体、声音、掌纹、手形和脸 部热谱图等“j 。 生物识别技术的核心在于如何获取这些生物特征，并将之转换为数字信息， 存储于计算机中，利用可靠的匹配算法来完成验证与识别个人身份的过程。生物 识别以生物技术为基础，以信息技术为手段，将两大热门技术交汇融合为一体。 从理论上说。人的任何生理或行为特性，只要满足以下条件，都可以用作人 的身份识别：普遍性( 即该特性是每个人都具有的特性) 、唯一性( 即任何 两个人的特性都是不同的) 、持久性( 即该特性不会随着时间的推移而改变) 、 量化性( 即该特性能够被定量的衡量) 。 研究表明，人的指纹、掌纹、面孔、发音、虹膜、视网膜、骨架等都具有唯 一性、稳定性和量化性的特征。基于这些特征，人们发展了指纹识别、面部识别、 语音识别等多种识别技术。 生物识别技术可广泛用于政治、军队、银行、社会福利保障、电子商务、安 全防务。例如，一位储户走进了银行，他既没有带银行卡，也没有回忆密码就径 直提款，当他在提款机上提款时，一台摄像机对该用户的眼睛扫描，然后迅速而 准确地完成了用户身份鉴定，办理完业务，这是美国德克萨斯州联合银行的一个 营业部中发生的一个真实的镜头。而该营业部所使用的正是现代生物识别技术中 的“虹膜识别系统”。美国9 1 l 事件后，反恐怖活动已经成为各国政府的共识， 加强机场的安全防务十分重要。美国维萨格公司的脸像识别技术在美国的两家机 场大显神通，它能在拥挤的人群中挑出某一张面孔，判断他是不是通缉犯。在指 纹识别的应用方面，如出国登记的指纹信息登记，更是被广泛应用。 对生物识别技术来说，被广泛应用意味着它能在影响亿万人的闩常生活的各 个地方使用。通过取代个人识别码和口令，生物识别技术可以阻止非授权的”访 问”，可以防止盗用a t m 、蜂窝电话、智能卡、桌面p c 、工作站及其计算机网络： 第一章绪论 在通过电话、网络进行的金融交易时进行身份认证；在建筑物或工作场所生物识 别技术可以取代钥匙、证件、图章等。生物识别技术的飞速发展及其广泛应用将 开创个人身份鉴别的新时代! b 自动指纹识别技术及其历史、发展现状和应用 指纹是人手指( 脚趾) 皮肤上特有的花纹，它是皮肤上隆起的纹线所构成。 这些隆起的纹线的起点、终点、分叉、结合等被称为指纹的细节特征。这种细节 特征有着无数种排列，每个人的指纹甚至每一个指纹的每一条纹线都是独立的， 并且一生都不会改变。 用指纹进行个人身份鉴定和识剐，主要是要对鉴定的指纹和事先己掌握的指 纹或任意的两个指纹进行研究比较，比对有无相同的细节特征，从而达到个人身 份的识别鉴定目的。 指纹识别技术有着悠久的历史。据考古学家证实：公元前7 0 0 0 年到6 0 0 0 年以前，指纹作为身份鉴别的工具已经在古叙利亚和中国开始应用。在那个时代， 一些粘士陶器上留有陶艺匠人的指纹，中国的一些文件上印有起草者的大拇指指 纹。在j e r c h o 的古城市的房屋留有砖匠的指纹等。由此可见，指纹的一些特征 在当时已经被人们认识和接受。 1 9 世纪初。科学研究发现了至今仍然承认的指纹的两个重要特征，一是两 个不同手指的指纹纹脊的式样不同，另外一个是指纹纹脊的式样终生不变。( 即 指纹的唯一性和不变性) 这个研究成果使得指纹在犯罪事件的鉴别中得以正式应 用。早期的指纹识别依靠人工对比方式进行由于指纹结构的复杂性及对指纹识别 要求的严格性，导致人工识别指纹难度大、速度慢和识别准确性受专家经验制约， 远不能适应实际工作的需要。 2 0 世纪6 0 年代，由于计算机可以有效地处理图形人们开始着手研究利用 计算机来处理指纹。从那时起，自动指纹识别系统( a f i s ：a u t o m a t e df i n g e r p r i n t i d e n t i f i c a t i o ns y s t e m ) 在法律实旌方面的研究和应用在世界许多国家展开。 与人工处理不同，自动指纹识别技术并不直接存储指纹的图像( 考虑到隐私 和存储空间的限制) ，而是记录从图像中提取到的特征，指纹识剐算法最终归结 为在图像上找到并比对指纹的特征。因此，基于计算机的自动指纹识别系统主要 涉及四个功能：读取图像、特征处理、保存数据和比对1 3 j 。通过指纹读取设备取 得图像，并对原是图像进行初步处理，使之更清晰；接下来，指纹识别算法对图 像进一步处理，建立指纹的数字表示一一特征数据。这是种根据指纹类型、纹 线的断点及交叉点等结构特征得到数据的单方向不可逆的转换，可以从指纹转换 第一章绪论 成特征数据但不能从特征数据转换成指纹，而两枚不同的指纹不会产生相同的特 征数据。这些数据通常称为模板，保存为数据库中的一条记录。最后，计算机通 过指纹识别算法，把两个指纹的模板进行比较，计算它们的相似程度，最终得到 是否匹配的结果。 到了2 0 世纪8 0 年代，个人电脑、光学扫描这两项技术的革新，使得它们作 为指纹取像的工具成为现实，从而使指纹识别可以在其他领域中得以应用。现在， 随着取像设备的引入及其飞速发展，生物指纹识别技术的逐渐成熟，可靠的比对 算法的发现都为指纹识别技术提供了更广阔的舞台。比如：指纹考勤系统代替了 i c 卡、磁卡等传统的考勤方法，从而从根本上杜绝了代打考勤的现象。 进入上个世纪9 0 年代后，各发达国家纷纷加快了对自动指纹识别鉴定技术 的开发应用，注重向系统的低成本、小型化和系列化发展并已开始进入市场，国 外使用自动指纹识别技术的系列化产品目前已有指纹锁、指纹开关、指纹保险柜 等。随着自动指纹化识别鉴定技术的推广应用，在一些发达国家已将该技术应用 到银行金库、代保管库、博物馆、高级宾馆、高级公寓等处的出入口管理中，同 时，也开始向家庭保安领域辐射，成为一种实用的现代化的家庭出入口控制系统。 掘统计，到2 0 世纪末，全世界生物识别市场约为1 1 2 亿美元，其中指纹识 别约为1 o o 亿美元【3 】，这标志着指纹识别是当前最成熟稳定，并且应用最广泛 的生物识别技术。 自动指纹识别鉴定技术虽然在我国起步较晚，但随着计算机在我国的普及应 用，同时经过广大科研技术人员的努力攻关，自动指纹识别鉴定技术在我国也取 得了较快的发展。指纹识别技术在我国已经得到较广泛应用，目前已开始在银行 储蓄、贵重物品保客、高级宾馆等行业推广使用，取得了较好的应用效果。随着 网络化的更加普及，指纹识别的应用将更加广泛。 1 2 指纹识别技术的特点及可靠性 i 指纹识别技术的特点 相对于其它特征的身份鉴别技术，指纹以下7 个方面的特性使其成为身份识 别技术的首选( j 、3 1 ： 1 ) 普遍性：即所有正常人都具有的生物特征； 2 ) 唯一性：即世界上两个指纹完全相同的概率小于l o ； 3 ) 永久性：即终生不变性； 第一章绪论 4 ) 可采集性：即可以通过一定的设备和手段采集到； 5 ) 可行性：即在对资源、环境、操作等条件要求不苛刻的条件下可以达到 合理的准确率、速度和鲁棒性； 6 ) 可接受性：即人们愿意接受这一方式； 7 ) 防伪性能好：与账号+ 密码、i c 卡等传统的身份识别手段相比，自动指 纹识别技术具有不会丢失、不会遗忘、唯一性、不变性、防伪性能好以 及使用方便等突出优点。采用这种技术，可以将人的身份和其指纹严格 对应起来。 另外，指纹识别中使用的模板并非最初的指纹图像，而是由图像提取的关键 特征，使所需存储的信息量最小，而且在实现异地确认时，可以大大减少网络传 输负担，支持网络功能。 可以看出，指纹识别技术相对于其它识别方法有许多独到之处，具有很高的 实用性和可行性。因此，指纹识别成为最流行、最方便、最可靠的身份认证方式， 已经在社会生活的诸多方面得到广泛应用。 i i 自动指纹识别技术的性能 计算机处理指纹图像时，只是涉及了指纹有限的信息，而且比对算法不是精 确的匹配，因此其结果不能保证1 0 0 准确。指纹识别系统的重要衡量标志时识 别率，它主要由两部分组成：拒识率( f r r ，f a l s er e j e c tr a t e ) 和误识率( f a r ， f a l s ea c c e p tr a t e ) ，f r r 和f a r 是成反比的，可以用0 1 0 的数或百分比来 表示。下图1 - 2 1 的r o c ( r e c e i v e ro p e r a t i n gc u r v e ) 曲线给出了f a r 和e r r 之间的关系。 图卜2 一lr o c 曲线 尽管指纹识别系统存在可靠性问题，但权威机构认为，在一般的应用中l 5 第一章绪论 的误识率就可以接受。由于f r r 和f a r 是一对相互矛盾的指标，这就使得在实际 应用系统的设计中，要权衡易用性和安全性，一方面要考虑整体性能，使r o c 曲线整体下降；另一方面要兼顾易用性和安全性，在r o c 上寻找合适的平衡点。 在我国，北大高科等对指纹识别技术的研究开发已达到可与国际先进技术抗 衡。中科院的汉王科技公司在一对多指纹识别算法上取得重大进展，达到的性能 指标中拒识率小于0 0 1 ，误识率小于0 0 0 0 1 ，居国际先进水平。 1 3 自动指纹识别系统的构成 输 入 指 纹 图 像 求 增 强 细 提 分 日 方 日 指 日 值 日 融 取 割 向 纹 嘲 特 征 图 化 化 信 息 图 像 l 预处理 特征提取 匹配 图卜3 1 自动指纹识别系统的构成算法流程图 自动指纹识别技术主要包含四个部分：指纹图像输入、预处理、提取特征信 息、存入信息或与库中的信息对比( 匹配) 。其中预处理部分又包括：指纹的分 割、求指纹的方向图、增强、二值化、细化。自动指纹识别系统所涉及的算法处 理流程如图卜3 - 1 。下面对图1 - 3 1 的各个部分做简单介绍： ( 1 ) 图像输入 最早的指纹采集方法是用手指蘸上墨水或印油在纸上按压，然后用扫描仪摄 取，由于其严重的不可靠，该方法早已经被淘汰。随着光学仪器、传感器及数字 技术的发展，各种快速、精确、方便、小巧的采集设备得到了应用。目前，主要 是使用光学扫描仪和固态阵列传感器进行采集。前者用激光照在手指上，然后用 c c d 阵列摄取其反射光，由于反射光随指纹的脊和谷的深度不同而不同，因此可 以得到指纹图像。后者是用大量敏感元件组成的固态阵列芯片，他们采用电容传 感、热敏传感或其它传感技术，通过感受按压指纹的压力、热度等特征来摄取指 纹。近年来，又出现了其它一些新型的指纹采集设备，如超声波指纹采集器，它 是基于指纹的脊和谷的深度对超声波的不同反射原理而工作的。这些设备中，光 6 第一章绪论 学扫描仪因其技术比较成熟。性价比比较高而得到广泛应用。 本系统使用的是o v l ? 2 0c m o s 指纹头。0 v 1 7 2 0c m o s 有两种采集模式，分别 采集3 2 0 x 2 4 0 和6 4 0 x 4 8 0 ( 宽高) 象素的两种灰度图像。本文采用的6 4 0 。4 8 0 模 式，该模式下图像的分辨率为5 0 0 d p i ，经过指纹头得到的是灰度值为0 2 5 5 的 灰度图像。 ( 2 ) 预处理 经指纹扫描仪采集的原始指纹图像不可避免的存在对比度不一致、含有大量 噪声等缺点，为了降低后续特征提取算法的复杂度、提高特征提取的效率，预处 理过程必不可少。 实际的指纹识别系统往往由于应用环境、系统规模、实现思路以及具体算法 的不同，而在系统整体框架上有所出入，因此在预处理的过程中有所区别。考虑 到两种不同的特征提取方法，预处理也有所不同：一类直接从原始指纹图像中提 取统计性特征，该方法对预处理要求比较少，只要将图像增强一下就可以；另一 类从预处理得到的指纹骨架图像中提取细节点特征，该方法要求预处理部分做大 量的工作，一般包括图像分割、增强、二值化、细化及后处理等步骤，最后得到 一幅纹线宽度为单象素的二值图像。在当前的应用系统中，后一类的方法要比前 一类应用得多一些，因为后一类方法把工作的难点分散到两步操作中，简化了特 征提取算法，且处理结果容易控制。 ( 3 ) 特征提取 特征提取负责把指纹图像的纹线走向、纹线端点、交叉点等能够充分表示该 指纹唯一性的特征用数值的形式表达出来。为了比对的准确性，要求特征提取算 法尽可能的提取有效特性，同时滤除由于各种原因造成的虚假特征。 从不同的角度进行观察，指纹图像中存在两类特征：全局特征和局部特征。 全局特征是能够反映指纹整体形状的特征，通常用于指纹的分类，因此提取全局 特征的过程往往归于指纹分类步骤。局部特征指能够反映指纹细节点的特征，通 常用于指纹的对比。狭义的特征提取指局部特征的提取。两枚指纹经常会具有相 同的全局特征，但他们的局部特征点，却不可能完全相同。 指纹的主要局部特征信息有：端点( e n d i n g ) 、分叉点( b i f u r c a t i o n ) 、分 歧点( r i d g ed i v e r g e n c e ) 、孤立点( d o to ri s l a n d ) 、环点( e n c l o s u r e ) 及短 纹( s h o r tr i d g e ) 等。在美国联邦调查局( f b i ) 提出的细节点坐标模型中，只 利用了端点和分叉点两种特征点1 3 1 ，如下圈所示。另外两种重要的特征点是奇异 点：中心点( c o r e ) 和三角点( d e l t a ) 。中心点一般位于纹线的渐进中心，三角 7 第一章绪论 点一般位于从中心点开始的第一个分支点或末梢点、或者两条纹路会聚处。并不 是所有的指纹都拥有这两个特征，因此常被用作指纹的子匹配。本系统在特征提 取和匹配算法中只用了端点和分叉点两种特征点，如图1 - 3 - 2 。 图卜3 2 主要提取的指纹特征信息 ( 4 ) 指纹匹配 自动指纹识别系统的工作模式可以分为两类：验证模式( 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 ) 。验证模式又称一对一比对( o n e t o o n e ) ，比对原 理为：指纹预先登记到样本数据库并设定一个标识码。比对时，录入指纹并输入 标识码，系统根据标识码从数据库中提取指纹样本与录入指纹进行比对；辨别模 式又称一对多比对( 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 ) 。一对几个匹配主要应用于只有“几个”用户的系统 中，e b 如一个家庭的成员要进入他们的房子。“几个”所包含的数目一般为5 2 0 人。一对几个匹配一般使用与一对匹配相同的方法。 由于原始指纹图像受噪声或者本身的原因，指纹细化之后的图像不可避免的 存在一些毛刺、空洞等伪特征点，因此，需要去掉这些伪特征点，这种处理步骤 我们称之为后处理。对细化后的指纹图像进行后处理，可以减少后期特征提取和 匹配算法的复杂度，提高系统的性能。本系统对细化后的图像做了后处理。 1 4 本文主要研究内容及结构安排 本文经过阅读大量指纹识别方面的文献资料，在他人设计- 丌发的基础上，实 现了一个完整的自动指纹识别系统，它包括指纹图像的预处理、后处理、特征提 取和匹配三个部分。本文的所有算法都在w i n d o w s 平台上用c + + b u i d e r 6 0 实 第一章绪论 现，并通过了硬件测试。在指纹的分割、二值化、细化及后处理、特征提取和匹 配方面，本文进行了深入研究，对若干算法进行了改进。 本文的具体工作主要包括以下内容： ( 1 ) 结合该系统输入指纹的特征。在分析指纹图像直方图的基础上，实现 了一种指纹图像简单有效的分割算法；在二维图像二阶导数的基础 上，改进了基于方向图和脊线频率二值化算法，并实现了对二值化图 像的1 6 邻域的细化，构成了一个完整的指纹图像预处理过程。实验 证明，这套算法能够很好地完成各自的工作，并快速、商效地实现了 指纹图像的预处理。 ( 2 ) 在后处理中，本文根据8 邻域的局部结构信息查找特征点，并对特征 点所在纹线进行跟踪记录；在跟踪的同时根据灰度图像的信息消除了 桥、毛刺和空洞等伪特征点，并针对图像的特点，连接了断纹，为后 期的特征提取工作扫溃了障碍。 ( 3 ) 在提取特征信息中，每一个特征点的信息构造一个向量，所有特征点 的信息组成一个向量表，构成整个指纹的信息；本文还对传统的特征 信息记录进行了改进，以利于匹配算法的准确性，提高了指纹旋转后 的匹配率。 ( 4 ) 匹配算法中，本文对传统的匹配算法进行了部分改进。传统的匹配算 法中，由于提取特征点信息的影响，匹配算法不能识别旋转的指纹图 像( 特别是4 5 。旋转) ；本文算法中，由于提取指纹特征信息算法做了 改进，因此匹配算法能很好的适应指纹旋转的情况，大大提高了匹配 算法的鲁棒性和速度。试验结果达到了预期的要求。 9 第二章指纹图像的预处理 第二章指纹图像的预处理 自动指纹识别系统最终目的是指纹匹配，对方向场的估计和细节点的抽取是 对指纹分类和指纹对比的性能有决定性影响的因素之一，而方向场的估计和细节 点提取的准确性和可靠性都严重依赖于输入指纹图像的质量。在指纹图像采集过 程中，由于表面皮肤特性、采集条件以及成像传感器特征差异等各种原因的影响， 采集到的指纹图像是一幅多种不同程度噪声干扰的灰度图像，指纹脊线可能被断 开、桥接或者模糊等，这种噪化的指纹脊线结构严重影响着指纹识别系统的性能。 因此，有必要对指纹图像进行预处理，以除去噪声，增强图像的可识别性。另外， 本系统时在指纹的骨架图像上进行特征提取工作，要求事先把原始指纹图像变换 为纹线宽度为单像素宽的二值化图像。所以，二值化和细化过程也是必需的预处 理工作。 预处理的目的就是利用信号处理的技术去除图像中的各种噪声干扰，把它转 化成一幅清晰的指纹图像或二值的指纹图像，恢复指纹的脊线结构，以便可靠的 提取正确的指纹特征。预处理是自动指纹识别系统中的第一步，它的好坏直接影 响着指纹识别的效果。 指纹图像的预处理的一般工作过程如下图： 输 图 像 分 割 求 方 向 图 图 像 增 强 值 化 细 化 倒2 0 0 预处理框幽 预处理是自动指纹识别系统的重要组成部分，它的结果将直接影响特征提取 和匹配的准确性，关系到整个系统的识别率。长期以来，许多研究人员在预处理 方面做了大量工作，并取得了可喜的成果。l i nh o n g 等提出的预处理方法分为 三个步骤【5 1 ，首先求指纹方向图，然后由方向图求频率图，最后由频率图得到的 g a b o r 滤波器对原始图像进行滤波。g a b o r 滤波器的计算量比较大，而且求频率 图的时候容易产生偏差，可能导致滤波效果不理想。l a w r e n c e0 g o r m a n 等提 出了种比较复杂的滤波器f 6 j ，根据图像的脊和谷的频率以及其变化规律来淀除 指纹图像中的噪声。b m m e h t r e 提出了一种上下文滤波器i _ ”，它是一系列上下文 1 0 第二章指纹图像的预处理 相关的滤波嚣组，使用时根据某一块的方向从滤波器组中相应的滤波器来对这一 块进行滤波。 从图2 - 0 0 就可以看出：预处理主要包括图像分割、求方向图、增强( 滤波) 、 二值化、细化等1 8 1 。针对不同的系统，可以选择不同的预处理步骤进行组合，使 其达到最优的效果。 通过比较多种预处理算法，并结合该系统输入指纹的特征，本文选择并实现 了一种指纹图像简单有效的分割算法、基于方向图和纹线宽度的动态阀值二值化 算法和一种1 6 邻域的细化算法，从而构成了一个完整的指纹图像该处理过程。 算法中，考虑到本系统特定的指纹采集仪的特性，简单分割算法设置了两个 阀值：均值阀值和方差阀值，通过计算块灰度的均值和方差，并与设定的阀值进 行比较，来识别和割除指纹图像的背景区：改进的指纹块方向图算法通过求太块 的方向，来平滑隔块求得的小块的块方向图，使小块的方向图更连续、更准确； 基于指纹频率场的二阶导数二值化算法根据指纹图像的方向和纹线宽度特性，准 确的完成了二值化操作；指纹图像二值化后，纹线仍具有一定的宽度，而指纹识 别只对纹线的走向感兴趣，不关心它的粗细，1 6 邻域细化算法直接完成了二值 化图像的细化工作。实验证明，这套算法能够很好地完成各自的工作，并快速、 高效地实现了指纹图像的预处理，为后续工作顺利进行提供了保障。 本文所建立的自动指纹识别系统中，实验需要的指纹图像主要来自0 v 1 7 2 0 c m o s 指纹头扫描仪，为了验证系统的可靠性和健壮性，也使用了f v c 2 0 0 0 系列 的部分指纹。本系统算法直接对0 v 1 7 2 0c m o s 得到的数据进行处理。 2 1 指纹图像的分割 根据指纹图像被噪声干扰的程度以及能否被正确恢复，可把图像细分为4 类区域1 9 1 ：( 1 ) 白背景区，指不舍纹线的边界区，该区域往往由于扫描仅镜片污 垢而呈现深浅不等的灰度，或者指纹覆盖不到的区域；( 2 ) 前景区，指纹纹线清 晰连续，几乎没有噪声干扰的区域；( 3 ) 背景区，指噪声严重干扰，纹线无法辨 认，很难恢复的区域；( 4 ) 模糊区，指纹纹线断续不清晰，有噪声干扰，但不太 严重，可以恢复的区域。根据系统要求的不同，也可以把图像分为3 类区域f 1 0 】： ( 1 ) 背景区，指不含纹线，或者纹线区域很模糊，几乎可以看作噪声且不能恢 复的区域；( 2 ) 前景区，指纹纹线清晰连续，几乎没有噪声干扰的区域；( 3 ) 模 糊区，指纹纹线不清晰，但通过一定的算法处理，能恢复出指纹原型的区域。 本系统采用的就是后面一种分类方法。在下面的叙述中，我们将( 1 ) 称为指 第二章指纹图像的预处理 纹的无效区，( 2 ) 和( 3 ) 称为指纹的有效区域。 指纹分割的目的就是割除背景区，保留前景区，并尽可能的找出模糊区。分 割处理把图像中有效指纹区和无效区域分开，使后续处理集中于有效区域，不仅 能提高特征提取的准确度，还可以大大减少指纹预处理的时间。 指纹图像的分割方法基本上都使基于图像的方向特性和灰度特性。x w a n g 等人提出了基于方向图的分割方法 1 0 , n 】。该方法依赖于方向图的可靠性，对图像 对比度的高低不敏感。但是对于纹线不连续、单一灰度等方向难以正确估计的区 域，往往不能取得满意的效果。纹线对比度、纹线频率等特性也常用于分割p j ， 这些特征有各自的优点，但也存在缺点。例如，对比度小而方向性强的区域使容 易恢复的区域，但采用对比度分割就往往会被割除。文献 9 把多种特性综台起 来使用，提出了割除白背景区、寻找模糊区、割除背景区的三级分割方法。该方 法提高了运算速度，降低了误割率，但是算法比较复杂，且也存在误割及漏割的 现象。 本文应用的是一种简单的分割方法，该方法不需要考虑指纹的方向及脊线频 率等因素，且该方法在求取指纹的方向图和频率场之前进行分割，能提前找出有 效区域，减小后期方向图和频率场的计算量。 分析0 v 1 7 2 0c m o s 指纹头扫描仪所得到的图像( 如图2 1 一1 ) ，我们可以发现： 图像边缘边框部分像素值比较小，指纹中心区域亮度高，且指纹区域纹线的灰度 值比边缘框的灰度值稍大；指纹于边框之间有明显的背景区域。因此，我们只要 得到图像的直方图，并利用均值和方差两个参数，就可以达到很好的分割效果。 记指纹图像( f ，) 处的灰度值为g r a y ( i ，j ) ，将图像分为大小为 村( m = 7 ) 的块，记块( 聊， ) 的分割标记为r ( m ，) 。这里彤的大小以包含 一脊一谷( 即一周期为宜) 。r ( m ，一) = 1 表示块如，n ) 为有效区域，r ( m ，月) = 0 表 示m ，n ) 为无效区域。 本文所用的具体算法步骤如下： ( 1 ) 求取指纹图像g r a y 的直方图，并找出最大峰值只。和次大的峰值匕。( 如 果在一定的范围内有次大值) ； ( 2 ) 将图像分成时m ( m = 7 ) 的块，计算第沏，订) 块b l o c k 内的像素的均值 神简易方觏孑= 志鬈和础( f ，护孔若鬲在。 附近，或者孑小于设定阀值，则认为块( m ， ) 为背景区域，记r ( m ，n ) = 0 墨三! 塑塾望篓塑塑塾翌 否则记r ( m ，聍) = 1 。 ( 3 ) 由于某些干扰的存在，需要对所得的太( m ，订) 进行平滑，消除r ( m ，刀) 中的 空洞，最后得到的分割示意图如图2 - 1 1 。 ( 4 ) 根据r ( m ，栉) ，寻找后续处理的主要区域，见图2 - i 一1 。后面的处理部分主 要是对主要区域的图像进行处理。 图2 - i - i 指纹图像的分割示意圈( 黑色区域表示背景) 对0 v 1 7 2 0c m o s 采集的指纹图像( 6 4 0 x 4 8 0 ，5 0 0 d p i ) ，大拇指的平均分割 时间为2 6 8 m s ，食指的平均分割时间为2 6 7 m s 。实验环境：硬件平台埘da t h l o n ( t m ) x p1 8 0 0 - t - 处理器，2 5 6 m 内存；软件平台c + + b u i i d e r 6 0 。而文献 9 采用的分级分割方法，平均时间在1 0 0 m s 以上。 对于标准指纹库f v c 2 0 0 0 内的指纹图像f 1 2 】，我们做了同样的试验，结果表 明：该分割算法能有效的将无效区域从图像中分割出去。 2 2 指纹图像的方向图 2 2 1 方向图 指纹纹线排列具有一定的规律性。一般来说，除奇异区外指纹纹线排列是近 第二章指纹图像的预处理 似平行的，且方向变化平缓，可以把指纹图像局部区域作为具有方向的纹理结构， 求取这些互不重叠的局部区域的方向值，按各区域位置组成一个场结构，就是指 纹的方向场。指纹图像的方向场表现了指纹的一种固有的特性，在指纹分析中起 了重要作用。 指纹图像的处理经常要用到空域方向图，方向图计算的精确性对于后继处理 步骤有很大的影响。指纹图像是一种具有一定纹路走向的多边缘有向图，纹理性 和方向性是它区别于其它图像的显著特点。在预处理中，亦可以利用这一特点， 并依次而更好的进行后期的处理，为后继的增强、二值化、细化及特征提取步骤 做准备。我们把指纹图像看作有确定纹理的流状模型，通过计算方向场作为它的 方向图。方向图实际上描述了指纹图像中每一像素点所在脊或谷在该点的切线方 向。 方向图分为两种：一种是点方向图，即把指纹图像中每一点的方向都表示出 来；另一种是块方向图，即把指纹图像均匀分割成块，仅表示出每一块中脊线的 大致方向。在实际处理中，经常使用的是块方向图，因为它比点方向图具有更强 的抗噪性，更值得关注的是，在实际的系统中，求块方向图可以减少计算量，且 有利于模块化处理。 计算方向图的基本原理是：在灰度图像中计算每一点( 或每一块) 在各个方 向上的某个统计量( 如灰度差、梯度等) 。根据这些统计量在各个方向上的差异， 确定该点( 块) 的方向。 计算方向圈一般有三种方式：梯度法1 1 3 1 、切缝法、抽样法【6 】、投影法i j 7 1 。 基于梯度求取方向图的方法是最简单的，但是因为它只考虑水平和垂直两个方向 上的梯度分量，就不能其余方向上的精确性，因而其结果在原图像中方向变化鞍 快的区域并不能精确反映出方向变化：切缝法的方法考虑到八个方向上的分量， 相比较应该是更精确一些，但如果指纹图像遭受的污染比较严重，则很容易将噪 声造成的伪方向当成指纹脊或谷的方向反映出来；抽样法和投影法的方法都是基 于求不同方向梯度投影的思想，但是抽样法只用到了三个投影方向，之后用到了 圆平均的思想；而投影法直接比较8 个( 或1 6 个) 方向的梯度投影，取具有最 大值的方向为该点主要方向。投影法对于图像细节方向的损失比较严重。 本系统采用的是第二种求方向图的方法：切缝法。以8 个方向代表纹线的近 似方向： p = i x 2 2 5 6 ( i = 0 l ，1 一，7 ) ( 2 1 ) 切缝法最初用于图像的局部阀值二值化，后经过对阀值的变换，也可用于求 第二章指纹圈像的预处理 取局部指纹脊线的方向。其基本原理如上图所示，在指纹图像的局部较小的区域 内，沿指纹脊线( 或谷线) 方向，图像的像素值变化最小，而垂直于脊线( 或谷 线) 方向，其像素值变化最大。因此，在规定的8 个方向上，计算出每个方向上 像素值的变化，变化最小的方向就是该点指纹脊线( 或谷线) 的方向。下图2 - 2 - i 显示了切缝法求方向图的8 个方向像素示意图。 2 ，3 l4 i 5 1 q ， 2 i毛4 i毛6 l7 】 】，7 i o ，o f ? 0 7 i o 7 ， 6 0 5 0 4 3 2 口i l 屯 5 ，4 j毛 图2 - 2 -