（电路与系统专业论文）指纹识别算法的研究及基于FPGA的硬件实现[电路与系统专业优秀论文].pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担 论文作者签名：奎羞望 日 期： 勿哎上z 尹 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅：本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：奎董重导师签名：之丝要丝日期：丝垄羔丝 山车大学硕士学位论文 摘要 随着图像处理和模式识别技术的进步，基于生物特征的识别技术成为蓬勃 发展的高技术之一，根据i b g ( i n t e r n a t i o n a lb i o m e t r i cg r o u p ) 组织对生物特 征市场的统计和预测，该领域的收入的年增长率3 0 - 5 0 ，到2 0 0 8 年，全球总收 入将达到4 6 3 9 亿美元而基于指纹特征的识别技术由于其独特的可靠性，稳定 性，方便快捷的特点，恰好符合了市场的需求目前指纹识别技术是生物识别 领域中应用最广泛的识别技术，也是研究与应用的一个热点 s o p c 片上可编程系统和嵌入式系统是当前电子设计领域中最热门的概念 n i o s i i 是a 1 t e r a 公司开发的一种采用流水线技术、单指令流的r i s c 嵌入式处理 器软核，可以将它嵌入f p g a 内部，与用户自定义逻辑结合构成一个基于f p g a 的 片上系统与嵌入式硬核相比较，嵌入式软核具有更大的灵活性而f p g a 的高 速性，恰恰满足了指纹识别系统对速度的要求 本文对指纹识别技术中各个环节的算法进行了较为深入的研究，结合n i o s h 嵌入式处理器的特点。对算法进行了合理的选择与优化，形成了一套完整的指 纹识别算法，并提出了一种基于f p g a 的指纹识别系统硬件设计方案 论文的内容主要包括以下几个方面： 1 、对指纹图像预处理、后处理和匹配算法进行了改进，提高了算法的性能： 设计了一种适用于快速匹配的指纹特征数据结构；提出了一套基于特征点匹配 的指纹识别算法实验结果表明该算法速度快、误识率较低、可靠性较高，可 以满足实用的要求 2 、本着增加系统集成度、减小系统体积、提高便携性、降低功耗和成本， 同时提升系统的性能的原则，使用a l t e r a 公司提供的外围设备i p 核配合n i o s h 处理器软核搭建了一个单片嵌入式系统，然后以内嵌n i o s l i 软核的f p g a 和 f p s 2 0 0 指纹采集器为核心芯片，外配片外r a m 和f l a s h 存储器以及小键盘和 l c d 显示屏等器件，设计了一个便携式指纹识别系统，提出了一套基于f p g a 的硬件设计方案 3 、利用n i o s h 开发板对硬件设计方案进行了初步的验证，实现了指纹采集 芯片f p s 2 0 0 与f p g a 的接口，并进行了算法的移植 实验结果表明本文所提出的系统设计方案是可行的基于f p g a 的自动指 山东大学士擘位论文 纹识别系统在速度、功耗体积、扩展性方面有着独特的优势，具有广阔的发 展空间最后提出了对这一设计继续改进的思路和下一步研究的内容 关键词：指纹识别、图像处理、方向图、特征匹配、n i o s l t l j 乐大擘顿士竽位论文 a b s t r a c t w i t ht h e d e v e l o p m e n to fi m a g ep r o c e s s i n ga n dp a t t e r nr e c o g n i t i o n t e c h n o l o g y , i d e n t i f i c a t i o nt e c h n i q u e sb a s e do nb i o m e t r i cc h a r a c t e r i s t i c sb e c o m e o n eo ft h em o s tr a p i d l ye x p a n d i n gh i g ht e c h n o l o g y a c c o r d i n gt ot h es t a t i s t i ca n d p r e d i c t i o no fb i o m e t r i cm a r k e tm a d eb yi b g ( i n t e r n a t i o n a lb i o m e t r i cg r o u p ) ， g r o w t hr a t eo ft h er e v e n u e si nt h i sf i e l di sa b o u t3 0 t o5 0 p e ry e a r t o2 0 0 8 g l o b a lb i o m e t r i cr e v e n u e sw i l lu p t o4 6 9 3b i l l i o nd o l l a r s b e c a u s eo ft h e p a r t i c u l a rs e c u r i t y ，s t a b i l i t ya n df a c i l e n e s s ，i d e n t i f i c a t i o nt e c h n i q u eb a s e do n f i n g e r p r i n tc h a r a c t e r i s t i c sj n s ta d a p tt h er e q u e s to fm a r k e t n o w ，f i n g e r p r i n t i d e n t i f i c a t i o nt e c h n o l o g yi st h em o s tw i d e l yu s e di d e n t i f i c a t i o nt e c h n i q u ei nt h e b i o m e t r i ci d e n t i f i c a t i o nf i e l d a n da l s oi sah o t s p o tf o rr e s e a r c ha n d a p p l i c a t i o n s o p c ( s y s t e mo nap r o g r a m m a b l ec h i p ) a n de m b e d d e ds y s t e mi st h e m o s tp o p u l a rc o n c e p t i o ni nt h ee l e c t r o n i cd e s i g nf i e l d n i o s h 缸_ r i s cc p us o f t c o r cd e s i g n e d b ya l t e r ap r o v i d e dw i t hp i p e l i n i n gt e c h n o l o g ya n ds i n g l e i n s t r u c t i o nf l o w i te a rb ee m b e d d e di nf p g a , i n t e g r a t e dw i t hu s e r - d e f i n e dl o g i c ， t ob u i l das y s t e mo nc h i pb a s e do rf p g a c o m p a r e dw i t he m b e d d e dh a r dc o r e , s o f tg o r ei sm o r ef l e x i b l e , a n dt h eh i g h - s p e e dc h a r a c t e r i s t i co ff p g ad e v i c e e x a c t l ym e e t st h et i m er e q u e s to ff 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 t h i sp a p e rm a k e sa ni n - d e p t hs t u d yt oe a c hs t e p sa l g o r i t h mo ff i n g e r p r i n t i d e n t i f i c a t i o nt e c h n o l o g y , s e l e c t sf e a s i b l ea l g o r i t h m st of i tt h ef e a t u r e so fn i o s l l e m b e d d e dc p u ，a n do p t i m i z e st h ea l g o r i t h m , f i n a l l y , f o r m sa ni n t e g r a t e d f i n g e r p r i n ti d e n t i f i c a t i o na l g o r i t h m ，a n dp r e s e n t sah a r d w a r ed e s i g np l a na b o u t f m 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 mb a s e do nf p g a c o n t e n to ft h ep a p e r m a i n l yi n c l u d e 1 i m p r o v et h ep r e t r e a t m e n t 、a f t e r t r e a t m e n ta n dm a t c h i n ga l g o r i t h m ， d e s i g nan e w d a t as t r u c t l l r oo ff i n g e r p r i n tc h a r a c t e r i s t i c sf o rf a s tm a t c h i n g ，a n d p r e s e n ta nf i n g e r p r i n ti d e n t i f i c a t i o na l g o r i t h mb a s e do nm i n u t i a e s e x p e r i m e n t a l r e s u l ts h o w st h a tt h ea l g o r i t h mi sh i g hs p e e d ，l o wf a l s ea c c e p t e dr a t ea n d h i g h r e l i a b l e i tw i l ls u f f i c ef o rt h er e q u e s to fp r a c t i c a l i t y 5 山东丈擘硕士擘位论文 2 b yu s i n gn i e s i lc p us o f t c o r ea n dp e r i p h e r a le q u i p m e n ti pc o r e s p r o v i d e db ya l t e r ac o r p o r a t i o n 。b u i l das i n g i e - c h i pe m b e d d e ds y s t e m ，a n d p r e s e n tah a r d w a r ed e s i g np l a nb a s e do nf p g a 3 u s i n gn i o s hd e v e l o p m e n tk i t , m a k eap r e l i m i n a r yv e r i f i c a t i o no ft h e h a r d w a r ed e s i g np l a n ，i m p l e m e n tt h ei n t e r f a c eb e t w e e nt h ef i n g e r p r i n tc o l l e c t i o n c h i pf p s 2 0 0a n df p g a a n dm i g r a t et h ea l g o r i t h m i ct on i o s l i e x p e r i m e n t a t i o n sp r o v e dt h a tt h es y s t e md e s i g np l a np r e s e n t e db yt h i s p a p e r i sp r a c t i c a b l e 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 mb a s e do nf p g a h a sp a r t i c u l a ra d v a n t a g e so fs p e e d , p o w e la r e aa n de x p a n s i b i l i t y , a n dh a s w i d e l yd e v e l o p m e n ts p a c e k e y w o r d s ：f i n g e r p r i n ti d e n t i f i c a t i o n ：i m a g ep r o c e s s i n g ：d i r e c t i o ni m a g e ； c h a r a c t e r i s t i cm a t c h i n g ：n i o s l l 6 1 1 引言 第一章绪论 近年来。随着电子商务、网络通信和数字化社会的深入发展，随着越来越多 的电子设备进入人们日常生活以及互联网的兴起，计算机、a ：r m 、门禁控制及各 种智能卡等对个人身份识别技术要求越来越高。传统的“用户d + 密码”的认 证方式面临着密码遗忘、黑客攻击和被别人窃取等问题；而信息系统领域以外， 一些传统的需要身份验证的场合也存在类似的安全性问题，如利用伪造证件进入 考场，持伪造护照出入国境等 随着图像处理和模式识别技术的进步，基于生物特征的识别技术成为蓬勃发 展的高技术之一，而基于指纹特征的识别技术由于其独特的可靠性，稳定性，方 便快捷的特点，恰好符合市场的需求，成为目前研究与应用的一个热点。指纹识 别是模式识别领域中使用最早的，也是最为成熟的生物鉴定技术，它是集传感器 技术、生物技术、电子技术、数字图像处理、模式识别于一体的高技术 在国外，已经有很多指纹自动识别系统投入实际应用，但目前指纹自动识别技术 还不是十分的完善，我国在指纹图像采集、算法研究等多方面的技术还比较落后， 因此对指纹识别算法和指纹识别系统的研究有重要的理论价值和实际意义 随着微电子技术的发展，可编程逻辑器件规模越来越大，越来越快，功能越 来越强目前已经有若干种f p g a 器件支持嵌入式处理器软核，为基于f p g a 的硬件 开发提供了更多的选择。n i o s i - i 是a l t e r a 公司开发的一种采用流水线技术、单指 令流的r i s c 嵌入式处理器软核。可以将它嵌入f p g a 内部，与用户自定义逻辑结合 构成一个基于f p g a 的片上系统与嵌入式硬核相比较，嵌入式软核具有更大的灵 活性而f p g a 的高速性、恰恰满足了指纹识别系统对速度的要求 本文正是基于以上思路，首先进行了指纹图像预处理与识别算法的研究与比 较，在对算法进行了部分改进后，得到了一种速度快、识别率高且适合于移植到 n i o s i i 嵌入式c p u 的算法，然后给出了基于f p g a 的指纹识别系统设计与优化 方案 山东大学焉士擘位论文 1 2 生物识别技术简介 通过计算机，利用人体固有的生理特征或行为特征来进行个人身份的鉴定， 就是所谓的生物特征识别技术( b i o m e t r i c s ) 因为这些特征是每个人所独有 的，其他人很难复制或伪造，因此，利用生物特征来进行身份认证比传统的口令、 证件等认证方式安全可靠的多 近年来，随着计算机、模式识别等技术的发展，生物识别技术发展迅猛。与 传统的身份认证方法相比较，基于生物特征的身份鉴别技术具有以下优点：不易 遗忘或丢失；防伪性好、不易伪造或被盗：随身携带，使用方便。因此，基于生 物特征的身份鉴别技术发展十分迅速根据i b g ( i n t e r n a t i o n a lb i o m e t r i cg r o u p ) 组织对生物特征市场的统计和预测，如图1 1 所示。该领域的收入的年增长率 3 0 5 0 9 6 ，到2 0 0 8 年。全球总收入将达到4 6 3 9 亿美元 r o w 州啊眈囊_ 哪硼撕l 哪 - _ - _ _ -_ _ _ - _ - - _ _ 。- 。i _ 。_ - - 图生物识别技术市场预测( 2 0 0 4 b g 提供) 生理特征与生俱来，多为先天性的；行为特征则是习惯使然，多为后天性的。 生理和行为特征统称为生物特征，常用的生物特征包括面像、虹膜、指纹、掌纹、 声音、笔迹、步态、颅骨等用于身份鉴别的生物特征应该具有以下几个特点： l 、普遍性，即所有人都应该具有的特征： 2 、唯一性，即任何两个人不会具有相同的特征： 3 、稳定性，即这些特征不会因为时间或采集地点的变化而发生改变： 4 、可采性，即这些特征易于获取、量化并用计算机处理。 在实用生物识别应用系统中往往还要考虑更多方面的因素，包括： l 、性能，包括准确率，识别速度等方面： 3 山东大学顼士学位论文 2 、可接受性，即使用者对该生物特征统计特性的接受程度： 3 、防伪性，是否容易被攻击如伪造，模仿等： 4 、费用代价，即系统的成本是否在用户可接受的范围之内 到目前为止，还没有一种单独的生物特征满足以上所有要求，每一种生物识别技 术都有各自的优势和不足表1 1 给出了几种生物特征的参数比较 生物特征普遍性唯一性稳定性可采性准确性 接受度防伪性 成本 脸相高低 由 高低高低 由 指纹 出 高高 由 高中高 由 手型 由由 由 高 由 由 审 由 虹膜高高高 由 高低高高 视网膜高高 中 低高低高高 d 高高高低高低高高 声音中低低中低高低低 笔迹低低低高低高低 出 步态 由 低低高低高 由由 表1 1 生物识别技术性能比较 从上表可以看出，指纹识别技术作为生物识别技术的一种，是一种比较理想 可行的身份验证技术相对于其他识别技术，指纹识别技术具有下面的特殊优势： l 、稳定性高人的指纹从出生时到死亡后指纹纹线类型、结构、统计特征 的总体分布始终没有明显变化尽管随着年龄的增长，指纹在大小、纹线粗细等 方面可能有某些改变，局部纹线上也可能出现新的特征，但是从总体上看指纹是 稳定的 2 、具有唯一性每个人的每个指纹都是唯一的现代科学界的结论是：按 人d 6 0 亿记，3 0 0 年才可能出现两枚同样的指纹，概率几乎为0 3 、采集方便，实用性强。目前已经有标准的测试指纹库如f v c 2 0 0 4 等，方便 了指纹算法的研究与指纹识别系统的开发；有成熟的指纹图像采集芯片如f p s 2 0 0 等，硬件实现容易；与虹膜、d n a 等技术比较，用户接受度高，成本低 正是基于以上优点，指纹识别技术已经在国内外各个领域得到了广泛的应 用，已经成为生物识别领域中研究最深入，技术最成熟，应用最广泛的身份鉴定 9 山东大掌礤士学位论文 i i i _ _ _ _ 一 技术图1 2 展示了指纹识别技术在生物识别领域所占的市场份额 图1 2 生物识别技术的市场分配 1 指纹识别技术的发展及应用 人们使用指纹进行个人身份鉴定已经有很长的历史据史料记载，我国早在 周代就开始使用指纹作为个人身份凭证：公元6 5 0 年，唐代作家贾公秀在其作品中 就着重提到了指纹是确认个人身份的方法我国将指纹应用于民间契约及断案有 悠久的历史。但是由于缺乏专门性研究，未能将指纹识别技术上升为一门科学。现 代指纹识别技术起源于1 6 世纪后期，苏格兰医生h e n r y f a u l d 于1 8 8 0 年l o 月2 8 日首 次在英国( n a t u 陀) 上发表论文，指出指纹人各不同，恒久不变，并利用现场指纹 来鉴定罪犯，从此揭开了现代指纹识别的序幕。 随着电子计算机的出现，采集技术的发展以及对指纹识别的研究，人们逐渐 将人工的指纹识别向指纹自动识别( a u t o m a t e d f i n g e r p r i n t i d 髓t i f i c a l i s y s t e m ， a f i s ) 转变美国最早于1 9 6 3 年首先开展有关软件的研制，于1 9 7 5 年成功推出第 一个商业化系统p r i n t r a k 2 5 0 日本在1 9 7 5 年开始进行研究，并于1 9 8 2 年将n e c - a f i s 投入使用我国也在8 0 年代初对指纹识别展开研究” 指纹识别系统通常分为两种：嵌入式系统和基于p c 的桌面应用系统嵌入式 系统是一个相对独立的完整系统，它不需要连接其他设备和计算机就能够完成特 定的功能，其功能比较单一，如指纹锬，指纹考勤终端等而连接基于p c 的桌面 应用系统则具有灵活的系统结构，并可以多个系统共享指纹识别设备，可以建立 大型的数据库应用，但是由于需要连接计算机才能实现指纹识别功能，这限制了 山东大学颈士学位论文 这种系统在很多方面的应用 随着指纹识别产品的开发和生产，指纹识别技术应用非常广泛，遍及诸多领 域，目前的主要应用有： l 、金融证券业，可以应用到 n l 指纹终端机、指纹保险箱，指纹储蓄卡、大 额取款客户身份确认、公司提现确认、交易终端客户身份确认、远程交易身份确 认等。 2 、i t 业，应用范围有个人计算机系统密码、信息安全防范、网络安全防范、 网上银行及点子商务的安全交易等。 3 、刑侦领域，自动指纹识别系统可以帮助确认罪犯身份、联网搜捕 4 、在安全防卫业，有指纹门禁系统、指纹证件等 5 、在医疗业，有献血输血管理、个人医疗档案管理等。 6 、在社会福利方面，可以用在公费医疗确认、保险受益人确认、各种社会 福利受益人身份确认等方面 7 、另外，指纹考勤、俱乐部会员确认、海关及民航快速通关认证等也可以 用到指纹识别技术。 指纹识别技术作为一种较为成熟的生物识别技术，已经广泛应用到社会的许 多方面，随着计算机技术的发展，其应用范围将越来越广泛，因此，有必要对其 进行深入研究，开发出更加高效、实用、安全的新型指纹自动识别系统 1 4 基于f p g a 的嵌入式系统简介 嵌入式系统就是内嵌到对象体系中的微型专用计算机它具有比通用计算机 更简洁、更个性化的功能，可运行操作系统，又兼有单片机体积小、功耗低等优 点，是目前最热门的概念和应用最广泛的技术之一 2 0 世纪9 0 年代末，可编程逻辑器件的复杂度已经能够在单个可编程逻辑器 件内实现整个系统，即在一个芯片中实现用户定义的系统，它通常包括片内存储 器和微处理器。目前，国内外已经有许多应用系统设计成功的将5 l 单片机、a r m 和p p c 等处理器内核嵌入各种可编程逻辑器件中最著名的嵌入式可配置处理 器软核有a l t c r a 公司的n i o s 和x i l i n x 公司的m i c r ob l a z e 。 基于f p g a 的可配置的软核嵌入式处理器具有传统嵌入式处理器所不具有 山素丈擘硕士擘位论文 的优势现今已有的数百种嵌入式处理器，每种都具备一组不同的外设、存储器、 接口和性能特性，用户很难做出一个合理的选择：要么为了匹配实际应用所需要 的外设和接口要求等而选择在某些性能上多余的处理器，要么为了保持成本的需 求而达不到原先预计的理想方案随着嵌入式软核处理器的推出，用户可以轻松 的在f p g a 内部创建一教拥有。完美”的外设、存储器接口、性能特性和成本的 处理器 基于f p g a 的嵌入式系统还有以下优点：l 、可在f p g a 内添加多个处理器 来提升系统的性能；2 、用户可自定义处理器指令来处理复杂的运算；3 。可向 f p g a 内部添加专用硬件加速器，作为嵌入式处理器的协处理器并发的处理大块 的数据；4 、可以通过定制处理器、减小电路板成本等方法来降低系统的成本；5 、 系统开发周期更短，且产品性能更高、软硬件升级方便具有更强的竞争力 基于f p g a 的嵌入式系统开发是一个软硬件协同设计的过程，通常遵循以下 步骤进行开发： 1 、分析系统需求，包括功能需求和性能约束等： 2 、根据分析结果，选择片外外设或片内口核( i n t e l l i g e n c e p r o p e r t y c o r e ) a 除此之外。还要对选择的p 核和外设进行初步性能估计，以保证能满足系统需 求： 3 、设定口和系统参数； 4 、确定系统互联逻辑，分配f p g a 引脚等； 5 、结合嵌入式处理器的软件开发包进行软件开发 1 5 本文的主要内容 本文以自动指纹识别技术为背景，结合国内外当前研究状况，详细研究了指 纹识别系统从预处理到匹配各个阶段的主流算法，通过对这些算法分析和比较， 对其中的部分算法进行了改进，选取各个环节上性能较好的算法设计出一套完整 的，且适合于f p g a 实现的自动指纹识别算法，设计了一种适合于快速识别的指 纹特征数据结构，并通过c 语言程序验证证明该算法是可靠有效的。 在算法验证完成后使用a l t e r a 公司的n i o s i i 嵌入式处理器，基于f p g a 器 件搭建了自动指纹识别系统的硬件平台，并提出了算法和硬件优化方案 山东大学硪士掌位论文 第二章指纹识别技术简介 一个典型的指纹自动识别系统主要由指纹采集、预处理、特征提取、特征匹 配、特征数据库等几个部分组成，如图l 所示 指纹 指纹 图1 指纹识别系统图 本章将对指纹识别系统的各方面做一个总体的介绍。 2 1 指纹图像的采集 指纹取像技术是指纹识别系统中的关键技术之一，所采集的指纹图像质量将 直接影响到识别的精度和系统的处理速度。在目前的指纹识别系统中，主要由指 纹传感器负责采集指纹图像，并将采集到的指纹图像转换成数字信号常见的指 纹传感器分下面3 类： l 、光学传感器光学传感器依据的原理是光的全反射。采集时，用一束光 线照到压有指纹的玻璃表面，由c c d ( c h a r g e - c o u p l e dd e v i c e ，电荷耦合器件) 感应反射光线，从而得到指纹图像它是最早开发的指纹输入装置这种传感器 技术比较成熟，成本较低，性能稳定，但是成像质量比较差。 2 ，电容式传感器。使用这种传感器采集指纹时，先将手指放在传感器表面， 传感器感受接触点并改变电容器的电压从而获取图像固体传感器与光学扫描相 比具有体积小、集成度高、成像质量好，数字化等特点目前它的抗静电能力也 有很大的提高，它将是未来最受欢迎的指纹传感器。 3 、超声波传感器这种传感器的原理和光学传感器类似，只是用超声波来 代替了光波。超声波扫描技术是指纹取像技术中非常好的一类，积累在皮肤上的 脏物和油脂对超声波获得的图像影响不大，因此成像质量非常高，缺点是价格较 高，耐用性也有待检验 、 三种传感器的技术参数比较如表2 1 ： 山东大擘一士擘位论文 超声波传感 比较项目光学传感嚣电容式传黪嚣 嚣 体积大小 由 耐用性非常耐用容易磨损一般 千手指差，而汗多和稍干手指好，但汗多和 成像能力较好 胀的手指成像模糊稍胀的手指不能成像 - 耗电较多较少 较多 成本低低很高 2 2 指纹的特征 表2 1 指纹传感嚣三种主要技术的比较 通过直接比对指纹图像的方法是不可取的，因为指纹图像本身数据量大，直 接比对不但消耗大量的时间和系统资源，而且目前也没有一种有效的算法。另外， 指纹图像属于个人隐私，如果自动指纹识别系统将指纹图像存入数据库那么指纹 图像就有可能被窃取，进而伪造，系统将无安全性可言因此，目前的指纹识别 算法最终都归结为在指纹图像上找到并比对指纹的特征 指纹特征通常分为两种：。总体特征和局部特征 一、总体特征是指那些用人眼就可以直接观察到的特征包括： l 、纹型 蕊豢瓣 环形弓形螺旋型 图2 1 常见纹型图案 图2 1 是三种常见的指纹图案环型、弓型、螺旋型。其他的指纹图案都基于这 三种基本图案 2 、模式区 1 4 模式区是指指纹上包括了总体特征的区域。即从模式区就 能够分辨出指纹是属于那一种类型的。有的指纹识别算法只使 用模式区的数据 山东大掌焉士擘位论文 3 ，核心点 4 、三角点 5 、纹数 核心点位于指纹纹路的渐进中心，它在读取指纹和比对 指纹时作为参考点许多算法是基于核心点的，即只能处理 和识别具有核心点的指纹 三角点位于从核心点开始的第一个分叉点或者断点、或 者两条纹路会聚处、孤立点、折转处，或者指向这些奇异点 三角点提供了指纹纹路的计数跟踪的开始之处 纹数是指模式区内指纹纹路的数量在计算指纹的纹数 时，一般先在连接核心点和三角点，这条连线与指纹纹路相 交的数量即可认为是指纹的纹数 二、局部特征是指指纹上节点的特征，这些具有某种特征的节点称为特征点。两 枚指纹经常会具有相同的总体特征，但它们的局部特征特征点，却不可能完 全相同。 特征点通常以四种特征描述：特征点的类型，如终点、分叉点、孤立点等。 方向，曲率和位置目前最常用的细节特征是美国联邦调查局提出的细节点坐标 模型，它利用端点和分叉点这两种关键点来鉴定指纹，图1 。2 是他们的示例。 端点分又点 图2 1 两种特征点示例 总体特征常用来指导指纹的分类，这使得在大规模数据库中搜寻指纹更为方 便快捷，而具体的指纹匹配则依赖于指纹的局部特征。通常认两枚指纹只要有1 2 个以上特征点重合，就可以认为来自同一个手指 2 3 指纹识别算法 根据特征提取算法和特征结构的不同，可以将指纹识别算法分为很多种，如 基于结构特征的指纹算法，基于脊线采样的指纹算法等图像处理和识别是自动 1 5 山豪大学一士掌位论! 一i il i e 指纹识别系统的核心技术，对其的研究已经有很长的历史了但是总体的思路变 化不大。可以把识别算法大致分为下述3 个步骤： l 、图像预处理原始指纹图像需要进行滤波除噪、脊线增强、动态二值化、 方向信息计算、初分类、背景分割、纹线间隔估计等处理图像预处理的效果好 坏直接影响系统性能个别应用还需要指纹图像的压缩编码 2 、指纹特征提取包括纹线细化、特征点( 交叉点、断点、中心点、三角 点等) 检测与分类、伪特征点消除、特征点特性参数计算、特征参数压缩编码、 全局特征( “斗”，“箕”、“旋向”等) 检测等步骤特征提取算法应能适应噪声、 畸变、位移、旋转、缺损、变形等常见的实际情况 3 ，指纹特征比对即比较现场提取的某一个指纹特征点集合和原先建立的 数据库中的某一个指纹特征点集合的相似程度。通常用代价函数( 或匹配能量) 来表示相似程度，取合适的门限，给出最后该两组指纹特征是否来自同枚指头 的判断 本文所采用的算法是一种改进的点模式匹配算法，也包括上述三个阶段在 预处理过程中，通过对原始图像进行滤波、增强、二值化和细化，得到指纹脊线 的骨架线，然后对骨架线进行修复，去除毛刺、孤立点、小孔、小环，连接断裂 的脊线等：再用特征提取算法从修复的骨架线中提取出端点和分叉点的节点特 征，并生成特征数据模板：最后使用一种改进的基于三角形定位中心点的特征匹 配算法对两个特征数据模板进行比较。给出匹配结果 2 4 指纹识别系统的工作模式 指纹识别系统根据其应用目的的不同，可以分为两类，即验证和辨识。验证 就是通过把现场采集到的指纹与一个已经登记的模板进行。一对一的比对”，来 确认身份的过程作为验证的前提条件，他或她的指纹必须在模板数据库中已经 注册，以一定的压缩格式存储，并与其姓名或其标识联系起来随后在比对现场， 先验证其标识，然后，利用数据库中的模板与现场采集的特征比对来证明其标识 是合法的验证其实回答了这样一个问题：“他是他自称的这个人吗? ”辨识则 是把现场采集到的指纹与数据库中的模板逐一对比。从中找出与现场特征相匹配 的模板这也叫“一对多匹配”辨识其实回答了这样一个问题：。他是谁? ” 1 6 山东大学硬士学位论文 验证和辨识在比对算法和系统设计上各有特点例如：验证系统对比算法的速度 要求不如辨识系统高，但更强调易用性；另外，在辨识系统中，一般要使用分类 技术来加快查询的速度。 2 5 指纹识别算法的评价指标 由于采集到的指纹图像含有大量噪声并可能发生畸变，即使通过预处理和特 征提取过程也只能尽量减少而不能完全消除，并且在处理过程中还可能引入新的 噪声，所以在进行对比时不可避免会产生误差从而影响到最终匹配结果。评价 指纹识别算法性能一般有两个重要的技术参数：误识率f a r ( f a l s e a c c e p t r a m ) 和拒识率f r r ( f a l s e r e j c c t r a t e ) 。误识率即非法用户能通过指纹识别系统的概 率：拒识率即真正用户在建立档案后无法通过的概率。指纹算法的这两个指标越 低越好，但是f a r 和f r r 是成反比的，一个参数值的减少必然会引起令一个参数值 的增加图2 2 给出了反映f a r 与f r r 关系的r 0 c ( r e c e i v eo p e r a t i n gc u r v e ) 曲 线，曲线上的点表示在某一给定阈值下得到的拒识率和误识率 图2 2 拒判率和误判率关系曲线 在实际应用中。要根据用途的不同，调整系统参数使其满足于不同的应用目 的。例如，如果用于高度机密的访问控制，则可以适当调高拒识率，把误识率降 到最小；而对于公安部门，则降低拒识率，在更大的范围内搜寻嫌疑人另外， 通在指纹登记时采集多个手指或者每个手指采集多枚指纹，可以大幅提高指纹识 别的准确性 1 7 山东大学硕士学位论文 第三章基于方向图的预处理算法 在指纹识别过程中，由于受各种因素的影响，采集到的指纹图像是一幅含噪 声较多的灰度图像，不对其进行一定的图像增强很难进行特征的提取预处理的 目的就是去除图像中的噪音，把它变成一幅清晰的点线图，以便于提取正确的指 纹特征信息预处理是指纹识别算法的第一步，它的好坏直接影响到指纹识别的 效果指纹预处理一般由规格化、方向图计算、滤波、图像分割、二值化、去噪 和细化等环节组成 本章重点研究了这些关键环节的算法并对部分环节做出 了一定的改进，实验证明，经过预处理后，有效去除了原始图像的噪音，得到了 一幅清晰的、单象素宽的指纹骨架图本文所用的指纹图像是由v e r i d i c o m 公司 生产的f p s 2 0 0 指纹采集芯片得到的2 5 6 3 0 0 象素2 5 6 级灰度图。 3 1 指纹图像的规格化处理 规格化的目的是把采集到的指纹图像的对比度和灰度调整到一个固定的级 别上，为后续处理提供一个较为统一的图像规格。一般按照公式3 1 进行规格化： fm o + yv a r o 1 ( x 陆, y ) - m 地y ) m g 0 j ) 2 气公式3 1 【m d - i yv a r o 1 ( x 附, y ) - m 2 - 其他 其中i ( x ，y ) 是点( x ，y ) 的灰度值，m 、v a t 是原图像的灰度均值和方差，m 。、 v a r o 是期望的灰度均值和方差通过对对比度和灰度不同的指纹原始指纹图像进 行规格化处理，在对后续处理中的滤波模板、二值化阈值等参数时就可以针对期 望的灰度均值和方差选择固定的数值。图3 1 是规格化前后图像的对比，a 图是 原始图像，b 图是规格化后的图像，在这里m o 取1 2 0 、v a r d 阪1 6 0 0 i s 霪 ( 且) 原始图像( b ) 规格化后图像 圈3 i 指纹图像的规格化( m = 1 2 0 、v a r o = 1 6 0 0 1 山东大学硕士学位论文 3 2 方向图的计算 指纹图像是由局部平行的脊线和谷线构成的一种方向模式，方向信息是指纹 图像的重要信息之一指纹方向图表征了指纹的这种内在属性，它是指纹图像的 一个重要识别特征，也是对指纹进行进一步处理的基础。 指纹方向图又可分为点方向图和块方向图点方向图表示原始指纹图像中每 一象素点处的局部纹理走向，而块方向图表示原始指纹图像中每条纹线的大致走 向方向图对于指纹预处理过程中前景背景的分离、指纹图像的增强、奇异点的 检铡及指纹的分类有着重要作用。 一、点方向图的求取 常用的求点方向图的算法有梯度算子法和基于邻域灰度统计特性法。对于前 一种算法，如果使用简单的s o b e l 算子来计算梯度时，求取的方向图效果不好， 如果使用m a r t h i l d r e t h 算子计算，求得的方向图效果较好但是计算过于复杂 而第二种算法不但简单、快速而且对噪声具有较好的鲁棒性因此，本文采用了 后一种算法。 如图3 2 所示，将指纹纹线得方向在0 。1 8 0 0 之间划分为1 1 个基本方向。理 论上，n 值越大越好，但实验表明，n 取8 就可以得到满意的效果，n 取更大的 值不但对结果改善不大，相反还会消耗太多计算时间。本文中的算法n 取8 。 、i ! 、 枝墨4，2 x 、 x墨 l多zr 孓 _ ， 一l 4 r 争- 0 铀些 - 防幡 - 廿 - - 0 t 。， 呵 彳。 名3 i 葛 。z ， 、 卜 i zb 簟一x ! i 图3 2 方向计算的9 9 掩模 9 i | i 术大擘囊士学位艳文 为计算输入图像中每个象索的方向以要计算方向的象素为中心放置如图3 2 所示的9 9 掩模在掩模中每个办向上的象素分别以相应的数字0 ，7 杯出 要求点( 工y ) 的方向d ( x ，y ) 先根据公式3 2 计算& ( 延d 方向的灰度变化) ： 耻乏臻m ( 几) | 公式3 2 脚d = o 1 n 篮aj z 其r f ( x y ) 足点( 工，) 的厌度值t ( 毛儿) 是方向d 卜的第k 点n 是所取的方向 数，n 是每个力向所取的邻点数。这啭n 取4 ( 州3 2q 嘞i 有数字的点) ，n 取8 即8 个方向。 点( x j ，) | 0 ，j r 向是& 取值最小的，j 向d ，即厌度变化最小的厅向每点的，j 向求出以后，点疗向圈也就彤j 扳了。这是邻域灰度法求点方向图的摹奉思想。但 是用这种方法求出的方向图效果小是很好，误差较人在进行了多次尝试后最终 采用了如下的改进算法： l 、求菜一方向的扶j 叟差时，不是用该点的灰j 皇值i f u 是取该方向卜4 个点 的平均位f ( t ) ，) 来代f ( x y ) ，这相当于在求办向l 冬l i ；i f 先进i j 了+ 次均值 滤波擞f 1 ：。 ， 2 、取( x y ) 点的方向时不仅考虑该点的方向是咒取值最小的方向t 同时 要考虑剑该点所在纹线的法线方向d 应该是咒1 1 ) 【位最大的方向。 ( a ) 原始蚓像( b ) 减法求山向( c ) 除法求山向 酗3 3 点方向幽的求取 最终的点方向图求取公式为d ( x ，j ，) = , w a x ( s , d - 4 1 。一) 这职比较了采r t ：j 减法和除法的求取效果。证明筹别不大，如i 冬i3 3 所示。为加快处理速度。在f p g a 内部，粟玎 n i o s 嵌入式处理器的自定义指令，将求方向图的算法用纯硬件实现 山东丈擘焉士擘位论文 一i _ 时，使用减法所占用的f p g a 资源会少的多，而且即便使用n i o s 软件编程。采 用减法所占用的时钟周期也要少的多 二，块方向图的求取 采集时噪声的影响以及纹线本身的磨损、横纹，导致点方向图并不能完全真 实的反映每个象素点所在纹线的方向由于指纹纹线方向具有渐变性的特点，在 一个局部邻域内纹线的方向可以认为是一致的，因此块方向图比点方向图更精确 的反映了纹线的走向 一般求取块方向图的方法是将点方向图分成w x w 的子块，对每个子块求方 向直方图，直方图的峰值为该予块的方向但是实际上，可能某子块内，纹线较 大范围的断裂或者纹线的对比度不高，或者刚好是纹线的拐角处，这时的最大方 向不能作为该子块的方向本文对这种方法进行了改进：把点方向图分成大小为 w x w 的子块，对每一子块求方向直方图，如果峰值p l 大于某一阚值t l ，则认 为该子块的方向为p l 所在方向否则以该子块为中心取与其相邻的8 个子块方 向直方图，如果此直方图的峰值p 2 大于另一阈值t 2 ，则认为该子块的方向为 p 2 所在的方向，否则标记该子块为无方向区域。 ( a ) 原始图像 ( b ) w = 8 ，t i = 3 0 t 2 = 1 0 0( c ) w = 1 6 ，t i 。1 2 0 ，t 2 =