（计算机应用技术专业论文）基于局部结构和质量因子的指纹匹配算法研究与实现.pdf

山东大学硕士学位论文 摘要 指纹识别技术是一种利用人的指纹特征通过计算机进行身份自动识别的综合 技术，属于生物特征识别领域。应用指纹进行身份鉴别已有悠久的历史，很多国 内外学者对指纹识别技术作了深入细致的分析和研究，并提出不少卓有成效的算 法，取得了丰硕的成果。然而，指纹识别仍然存在一些未得到完全解决的技术难 点。随着指纹识别技术得到原来越广泛的应用以及应用要求的不断增加，指纹匹 配算法的可靠性和鲁棒性与各种应用要求的性能之间的矛盾越来越突出。重叠面 积较小和指纹质量较差就是影响自动指纹识别性能提高的其中两个关键因素。本 文主要对重叠面积小、细节特征点不够丰富的指纹识别方法进行研究与实现。同 时为了提高识别算法的准确率，将指纹细节点周围图像质量评价引入匹配算法。 对重叠面积小、细节特征点不够丰富的指纹，常用的基于点模式的指纹匹配算 法和单纯基于纹线相似度的指纹匹配算法有一定的局限性。所以，本文提出了一 种基于细节点局部结构的指纹匹配算法。首先利用细节点所在脊线的相似度寻找 基准细节点，并进行姿势调整；然后，根据细节点类型( 端点和分叉点) 分别设 计了相应的局部结构，通过计算局部相似度，进而融合计算出整幅指纹的相似度， 来判断两幅指纹是否同源。实验结果表明，该算法对解决重叠面积小的指纹匹配 问题有一定的优势。 指纹图像质量是影响指纹匹配的关键因素之一。本文将指纹图像质量评价引 入指纹匹配算法中，作为指纹匹配算法的一个重要环节。指纹质量评价分为全局 质量评价和局部质量评价。本文主要是对指纹图像指定区域进行局部质量评价。 首先是根据提取的细节特征点( 端点和分叉点) 构造局部结构，即端点局部结构 和分叉点局部结构；然后，求得每个局部结构的外接矩形，并对每个矩形区域进 行质量评价，计算每个矩形区域的指纹质量因子：最后，找到匹配细节点对，并 对细节点各自所在区域的质量因子求平均，平均值作为匹配细节点对应局部结构 在计算整体指纹相似度的权重。实验结果表明，该方法在一定程度上提高指纹识 别准确率。 关键词：指纹识别；纹线相似度；基准细节点：局部结构；质量因子 山东大学硕士学位论文 a b s t r a s t f i n g e r 】) r i n ti d e n t i f i c a t i o n ，、v ! h i c hi sa ni n t e g r a t e dt e c l u l i q u eu s i n gf i n g e 叩r i n tf 0 r a u t o m t i cr e c o 印i t i o n ，i sar e s e a u r c hf o c u si n l ea r e ao fb i o m e t r i cr e c o 印i t i o n a p p l i c a t i o no ff i n g e r p r i n ti d e n t i f i c 撕o nh a sal o n gh i s t o 巧al o to fr e s e a r c h e r sa r e w o r k i n gh a r do nf i n g e 叩r i n ti d e n t i f i c a l i o nt e c h n o l o g y 锄dp r o p o s e dan u m b e ro f e 虢c t i v ea l g o r i m n l s 谢t hf m i t f u lr e s u l t s h 0 w e v e r t h e r ea r es 伽s o m ep r o b l e m s 眦r e s o l v ed t h ee x p a n d i n ga p p l i c a t i o n so ff i n g e 叩r i n ti d e n t i f i c a t i o na n dt l l ed i v e r s i t yo f f i n g e 叩r i n ta c q u i s i t i o ni n s t r u m e n t ss e th i g h e rr e q u i r e m e n t s t om er e l i d b i l i 锣锄d r o b u s 恤e s so ff i n g e 叩 n tm a t c h i n ga l g o r i t l l m s o 也e r 、v i s e ，t l eq u a l i 够o ff i n g e 甲r i n t i m a g ei s 甜s 0ac t i c a lf a c t o rt 0a f f e c tt h ea c c u r a c yo ff i n g e 印r i n tm a t c h i n 吕t h e r e f o r e ， t h i sp a p e rf o c u s e so n 1 ei d e n t i f i c 撕o no ff i n g e 甲r i n t s 谢ms m a l ls i z e 锄dl i t t l en 啪b e r o fr n j n u t i a ep o i n t s i no r d e rt oi m p r o v e 也ea c c u r a c yo ft h ei d e n t i f i c a t i o na l g o r i l m s ，w e a l s ota ：k et h eq u a l i 够o fl o c a la r e ao ff i n g e 中r i n tw h i c ha t o u n de a c hm i n 埘a ei n t 0 a c c o 哪ti nt h em a t c h i n gp r o c e s s f o rm e s ef i n g e 叩r i n t sw h i c hh a v es m a j la c q s i t i o na r e aa n d 、v i t hl i 坩en u m b e ro f r n j n u t i 毛n o r m a lm a t c h i n ga l g o r i m m sb a s e do np o i n tm o d a lo rr i d g es i r n j l 撕t ) rh a v e l i m i t a _ t i o n s t h i sw o r kp r o p o s e san o v e lm a t c m n ga l g o r i t l l mw h i c hi sb a s e d0 nl o c a j s t m c n l r eo fi t l i n u t i a et 0d e a l 、析山廿1 0 s ec a s e s i tu s e se 毹c t i v e l yt l l ei n f o n i l a 五o no f l i “t e dr n j n l n i a 锄di t s 砌a c e n tr i 电e s f i r s t l y ，t h es i r n j l a rd e g r e eo fr i d g e si su s e dt o s e e kt h eb a s ep o i n t sw h i c ha r el i e do nt 1 1 0 s er i 姑e s 谢t i lh i 曲s i m i l a r i 饥l e na d ju s tt 1 1 e p o s t u r eo f 廿1 em a t c h i n gf i n g e 印r i n tb a s e do n 吐1 0 s ep o i n t s s e n c o n d ，c o 丌e s p o n 山n g p a r t i a ls t n j c t u r ei sd e s i 朗e da u c c o r d i n gt 0m e 妙p eo fn l i n l n i a e b y 夥n c r e t i z i n gm el o c a l s i r n j l 撕锣o fm o s ep a n i a ls t r u c t u r e s ，w ec a no b t a i nt l l es i r n j l a r i 够o ft h ew h o l ei m a g et 0 j u d g ew h e t h e rm em a t c h i n gf i n g e 甲r i n t sc o m ef 而mt 1 1 es 锄ef r m g e r t h e 唧e r i m e n t a l r e s “t si n 出c a t et 1 1 a tt h i sa l g o r i m mh 笛c e n a j na d v a n t a g e 血l em a t c h i n gw i t hs m a l l a r e a t h eq u a l i 锣o ff i n g e 叩r i n ti m a g ei so n eo ft l l ec r i t i c a lf 如t o r si nf i n g e 甲 n t m a t c h i n g t h ee v a j u a t i o no fq u a l i 够i si n 仃i ) d u c e d 签ak e ys t e pi nf i n g e 平r i n tm a t c h i n g i i 山东大学硕士学位论文 i tc a i lb ec l a s s 讯e di n t oo v e 删lq u a l i t ) re v a l u a t i o na n dl o c a lq u a j i t ) ，e v a l u 撕0 n 1 1 1 i s p 印e rm a j n l yf o c u s e so nm el o c a lq u a l i 秒e v a l u a t i o no fi n t e r e s t i n gr e 孚o n f i r s t l y ， a c c o r d i n gt 0m et y p eo fe a c hc a l l d i d a t e 嘶n u t e a ( i e 也er i d g ee n d i n ga n dt h er i d g e b i 缸c 撕o n ) ，帆ol o c a ls t r u c t u r e sa r ec o n s t m c t e d ，a sd e s i 印e di nc h 印t e r2 ：l o c a l s t n l c t l l r eo fe n d i n ga 1 1 dl o c a ls t n l c t i j r eo f b i f u r c 撕o n 1 1 1 e n ，w eg e te n c l o s i n gr e c t 狮g l e o fe a c hl o c a ls t r u c n l r e ，a n de v a l u a t et h eq u a j i 够o fe a c hr e c t a n g l er e g i o nt oo b t a i n q u a j 时i n d e x f i n a l l y ，w ec a l c 山a t et 1 1 ea v e r a g eo fq u a l i 够i n d e xo fe a c hr n j n 埘a m a t c h e d ，锄ds e tm ea v e r a g ef k t o r s 嬲w e i 曲t so fs i r n i l a r1 1 1 i n 而a sl o c a ls t m c t l 鹏i n o v e r a l le n g e 巾r i n tm a t c m n g t h ee x p e r i m e n t a lr e s u l t sd e m 伽s 仃a t e 也a 士t h i sm e n l o dh a s i m p r 0 v e dt h ea u c c u r a c y0 ff i n g e 叩r i n tm a t c h i n ga ts o m ed e g r e e i ( e yw o r d s ：n n g e r p r i n ti d e n t i 6 c a t i o n ； s i m i l a r d e g i e e o f r i d g e s ；r e f e r e n c e m i n u t i a e ；l o c a ls t 巾c t i i r eo fm i n u t i 扯： e n c l o s i n gr e c t 柚g l eo fl o c 砌s t 邝c t u 他 i i i 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：么l 班 日期： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 蝴糍：4 蜘燧名够期：中州 山东大学硕士学位论文 第1 章绪论 现代社会对于信息安全和身份认证的准确性、安全性提出了更高的要求。如 何准确鉴定一个人的身份，保护信息安全是当今信息化时代必须解决的一个重要 的社会问题。传统的保密以及身份认证方法已经越来越不能满足应用的需要，如 钥匙、证件、i c 卡和密码等，这些手段无法避免被伪造或遗失，密码也容易被窃 取或遗忘。而生物特征识别技术以其方便、可靠的特点引起了学术界和企业界的 广泛关注。 生物特征识别技术( b i o m e t r i ci d e n t i f i c a t i o nt e c h n 0 1 0 9 y ) 是指通过计算 机与各种传感器和生物统计学原理等高科技手段密切结合，利用人体固有的生理 特性和行为特征，来进行个人身份鉴定的一项模式识别技术【1 1 。人体的生理特征与 生俱来，大多数为先天性的，比如指纹，人脸、虹膜、d n a 等，具有较大的稳定性 和可靠性。行为特征由习惯产生，多为后天形成，例如笔迹、步态等，因而相对 来讲，稳定性和可靠性要差一些。通常，我们将生理特征和行为特征统称为生物 特征。 常用的生物特征包括：脸相、虹膜、指纹、掌纹、声音和笔迹阻3 】等。目前人 体特征识别技术市场上占有率最高的是指纹机，这种识别方式也是目前技术发展 中最成熟的。 1 1 指纹识别技术简介 1 1 1 发展历史 关于指纹独有的特征和应用可以追述到很久以前，人类肤纹( 指纹、掌纹、足 纹) 的观察和应用的发源地定位在中国。据相关资料显示，我国古代最早的指纹 应用可追溯至秦朝。至唐朝开始，以“按指为书”为代表的指纹捺印已经在文书、 契约等民用场合被广泛采用。自宋朝起，指纹则开始被用做刑事诉讼的物证。直 至1 7 世纪下半叶，中国人对于指纹的应用才引起西方医学界的重视。在欧洲，1 7 8 8 年，梅耶( j m a y e r ) 首次提出没有两个人的指纹会完全相同：1 8 7 4 年，英国科 学家福尔兹又发现，每个人的指纹均有差别，世上没有一模一样的指纹这个重要 山东大学硕士学位论文 特征。1 8 8 9 年，亨利( e r h e n r y ) 在总结前人研究成果的基础上，提出了指纹 细节特征识别理论，奠定了现代指纹学的基础。1 8 9 2 年，英国人高尔顿写下有关 指纹的专著，将指纹分作弓、箕、斗三大类，同时指出：摩擦脊的解剖学特征和鉴 别方式，为指纹学理论作出很大贡献。指纹真正成为人类一门应用科学引起了世界 性的普遍重视。6 0 年代末至8 0 年代初，美国科学家最早研制计算机识别指纹系统。 此后，法国、日本也分别在此领域获得进展。1 9 9 8 年，中国第一代指纹自动识别系 列产品由北京邮大和清华大学研制并通过鉴定。现代科学界得出结论：人类人口 倘按6 0 亿计算，则需3 0 0 年才可能出现重复指纹，概率几乎为犁5 1 。指纹，真正 具有权威的唯一性、稳定性以及再生性的特点。指纹已被公认为：物证之首。 指纹识别技术从被发现时起，就被广泛地应用于契约等民用领域。由于人体 指纹具有终身稳定性和唯一性，很快就被用于刑事侦查。但早期的指纹识别采用 的方法是人工比对，效率低、速度慢，不能满足现代社会的需要。2 0 世纪6 0 年代 末，在美国开始有人提出用计算机图像处理和模式识别方法进行指纹分析以代替 人工比对，这就是自动指纹识别系统( 简称a f i s ) 。因为成本及对运行环境的特殊 要求，开始时其应用主要限于刑侦也叫警用领域。随着计算机图像处理和模式识 别理论以及大规模集成电路技术的不断发展与成熟，指纹自动识别系统的体积不 断缩小，其价格也不断降低，因而被应用到民用领域。 由于人体指纹具有不变性和唯一性，所以指纹识别技术成为应用最广泛的识 别技术。指纹相比于其他几种生物特征，如视网膜、虹膜、掌形、人脸、语音、 签名等，还具有一些优势【6 】：( 1 ) 使用指纹作为身份识别的手段已有很长的历史， 为人们所广泛接受。( 2 ) 便于获取指纹样本，易于开发识别系统，实用性强。目 前已有标准的指纹样本库，方便了识别系统的软件开发，另外，识别系统中完成 指纹采样功能的硬件部分也比较容易事项。( 3 ) 一个人的十指指纹都不相同，因 此可以方便地利用多个指纹构成多重口令，提高系统的安全性。同时，并不增加 系统设计的负担。( 4 ) 指纹识别中使用的模板并非最初的指纹图像，而是由指纹 图像中提取的关键特征，因此存储量较小。另外，对输入的指纹图像提取关键特 征后，可以大大减少网络传输的负担，便于实现异地确认，支持计算机的网络功 能。 2 山东大学硕士学位论文 从以上的分析可以看到，自动指纹识别技术相对其他技术不仅具有许多独到 的信息安全角度的优点，更重要的是还具有很高的实用性和可行性。指纹相对人 的其它生物特征具有个体差异大、实现识别所需的软硬件资源较小等优势。随着 模式识别、图像处理以及信息传感等技术的不断发展，自动指纹识别技术将展现 出更加广阔的应用前景。 1 1 2 指纹识别系统 由于人体指纹具有不变性和唯一性，所以指纹识别技术成为应用最广泛的识 别技术。它是一种利用人的指纹进行计算机自动识别的综合技术。其基本原理【4 】 是通过指纹采集仪得到指纹图像，然后用适当的算法进行指纹图像预处理，并提 取指纹的特征数据，最后通过匹配算法获得识别结果。 指纹识别系统本质上是一个模式识别系统，它根据使用者的生理或者行为特 征对使用者进行辨识，从而判断其是否具有合法身份。一般指纹识别系统的结构 如图1 1 所示【7 】。 引用自参考文献【7 】 图1 1 一般生物识别系统结构示意图 从逻辑上讲，这种系统有两个主要模块组成：登记模块和辨识模块。登记模 块主要负责将生物特征信息登记到生物特征识别系统样本数据库，在登记模块中， 个体的生物特征样本首先经相应的设备录入、数字化，进而经特征提取算法提取 特征信息，这种特征信息被称为样本。根据需要，样本信息被保存在数据库或磁 3 山东大学硕士学位论文 卡、智能卡中。辨识模块负责解决待识特征信息和样本特征信息是否匹配的问题。 在该模块中，相应设备录入待识生物特征，并进行数字化，经特征提取算法提取 待识生物特征中的有用信息，由模式匹配算子将这一信息与预先存储的样本信息 进行比对，做出是否匹配的判断。 引用自参考文献【8 】 图1 2 两种工作模式的结构框图 纹识别系统的工作模式可以分为两类：验证( 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 ) 模式【引，如图1 2 所示。 验证模式通过把现场采集到的生物特征与该人已经登记了的存在数据库中的 生物特征进行一对一的比对( o n e t o o n e a t c h i n g ) ，来确认身份的过程。在该 4 山东大学硕士学位论文 类系统中，他或她借助其姓名或p i n ( p e r s o n a li d e n t i t yn 岫b e r ) 或信用卡等等 来声称身份，然后，验证模式系统先验证其标识，然后利用系统的样本生物特征 与现场采集的生物特征执行一对一比对来证明其身份是否合法。该种模式常常被 用于积极识别，目的是为了防止多个人使用同一个身份9 1 。 在辨识模式中，系统把现场采集到的生物特征同样本数据库中的生物特征逐 一对比，找出与现场生物特征相匹配的特征信息。因此，该模式使用一对多比对 来建立被考察者的身份( 如果未注册，则匹配失败) ，不需要他或她声称身份。辨 识是拒绝识别( 这个人是否是被否认的) 应用的一个重要的组成部分。拒绝识别 的目的是防止一个人具有多个身份i l o 】。辨识模式主要应用于公共安全领域。比如， 可以通过将一个不明身份的人的指纹与指纹库中有犯罪记录的人的指纹进行比 对，来确定此人是否曾经有过犯罪记录。 验证和辨识在比对算法和系统设计上各具技术特点。验证系统一般只考虑对 完整的指纹进行比对，而辨识系统则要考虑对残纹的比对；验证系统对比对算法 的速度要求不如辨识系统高，但更强调其易用性；另外在辨识系统中，一般要使 用分类技术来加快查询的速度。 验证问题也可以用下述方式表达【1 1 】：给定一个输入特征向量x n 和声称的身份 ，判断( x 口，j ) 是属于q 还是：。其中国。指声称的身份，符合实际身份( 真实者) ， 国：指声称的身份，不符合实际身份( 冒充者) 。实际上就是将x q 和身份，的模板 向量x ，做匹配，来确定( x 口，) 的类别。 c 刎 ：骗力h 公o 。， 其中，s 是衡量x q 和x ，相似性的相似度函数。f 是预定义的阈值，s ( ，x ，) 的值就是测量到的身份与声称的身份之间的一个相似度或者匹配分数。因此，每 一个声称的身份，的类别( 属于国。还是国：) ，取决于x 口，x ，f 和相似度函 数s 。 识别问题也可以看作是如下过程：给定一输入特征向量x n ，确定其身份 山东大学硕士学位论文 ，i ，尼 1 ，2 ，+ 1 。这里，。，：，是系统中已经登记的身份，当识别 结果不是前n 个中的一个时，我们将其记作，+ 。即： ，i ，矿m a x s ( x q ，x 厶) ) f 五n 2 i ，+ l 否则， 公式( 卜2 ) 其中，x 厶为身份，。对应的模板向量，f 为预定义的阈值。 从技术的角度看，自动指纹识别系统主要包括一下四个模块：( 1 ) 指纹采集； ( 2 ) 指纹预处理：( 3 ) 特征提取：( 4 ) 指纹匹配。 1 1 2 1 指纹采集 从采集方式来看，指纹基本可以分为三类：捺印指纹、活体指纹和模糊指纹。 捺印指纹指的是将沾了印墨的手指按压在某种东西( 通常是纸) 上留下的指纹的 痕迹，再经相应设备转化为数字化的信息，就得到捺印指纹图像。捺印指纹采集 到的有效面积比较大，但因采集方式所限，采集速度较慢，指纹缺陷较多，目前 难以严格控制采集的质量。 根据录入原理的不同，活体指纹采集仪可分为光学式、半导体式和超声波式 等几种【6 】。根据采集时手指皮肤是否与指纹采集仪接触，又可分为接触式和非接触 式。经活体指纹采集设备得到的是数字化的指纹图像，相比较而言，活体指纹的 质量是最好的。 模糊指纹一般是指在犯罪现场采集到的指纹，即将罪犯无意中遗留在犯罪现 场的指纹痕迹经过显影、拍照和扫描等技术处理而得到的指纹图像。 1 1 2 2 指纹预处理 指纹预处理是指纹特征提取前的不可缺少的一个重要环节，主要用于突出指 纹图像中的纹理、方向信息，消除或者减弱噪声等无用信息。指纹图像预处理包 括指纹图像分割、图像增强、二值化、细化等。 指纹图像分割位于预处理的最前端，非理想采集条件下的指纹图像分割显得 越发重要。准确、可靠的将指纹图像从背景区域中分割出来，对于缩短图像处理 6 山东大学硕士学位论文 时间、提高特征提取的准确率都具有重要意义。指纹图像分割是自动指纹识别中 一个值得深入研究的问题。 图像增强是根据指纹图像纹理的方向性和纹线距离对可恢复的纹线进行恢复 和增强，对于不可恢复的区域进行屏蔽。 二值化即将图像中灰度大于某阈值的像素的灰度置为1 ，小于等于该阂值的像 素的灰度置为o ，即将图像变为二值图像。 指纹细化就是提取指纹图像的脊线骨架。 1 1 2 3 指纹细节特征定义和提取 指纹的细节特征点( i n u t i a e ) 有1 5 0 种之多。但这些特征点出现的概率并 不相同，其中很多特征是极其罕见的。在自动指纹识别技术中，一般只使用两种 细节点特征：纹线端点( r i d g ee n d i n g ) 和分叉点( r i d g eb i f u r c a t i o n ) 【1 2 】。纹 线端点指的是纹线突然结束的点，纹线分叉点则是纹线突然一分为二的点。大量 统计结果和实际应用证明，这两类细节点在指纹中出现的机会最多，也最稳定， 而且比较容易获取。更重要的是，使用这两类细节点足以描述指纹的唯一性。通 过算法检测指纹中这两类细节点的数量以及每个细节点的类型、位置和所在区域 的纹线方向是特征提取算法的任务。细节点的类型、方向的定义如图1 3 所示。 ! ! ，! 竺! ：；囊- i 童曩 _ 物- _ _ 。j 盔 _ _ 一i 纹线端点纹线分叉点 ( a ) c b ) 引用自参考文献【1 2 1 图1 3 指纹特征点的类型和方向定义：( a ) 类型，( b ) 方向 7 山东大学硕士学位论文 1 1 2 4 指纹匹配 指纹匹配要解决的问题是对两幅给定的图像提取特征信息，进行匹配，判断 这两枚指纹是否是同源的，即是否来自同一个指头。如：传统的点模式指纹匹配 一般是基于细节点( m i n u t i a e ) 实现的。目前最常用的细节点就是纹线端点和纹 线分叉点。如图1 3 所示。这两种细节点在指纹纹线中出现的几率最大，也最稳 定，易于检测，且足以描述指纹的唯一性。但由于采集设备的不完善性、采集条 件的随机性以及预处理技术的局限，使得真正特征点的缺失、伪特征点的存在和 特征点定位偏差的情况普遍存在。所以，指纹匹配必然还是一种模糊匹配，且需 要具备一定的弹性。 1 1 3 性能评价 为了反映当今模式识别应用的技术水平和发展状况，国际上举行了三届指纹 识别竞赛1 3 - 15 1 。f v c 各届竞赛均使用四个标准指纹库做测试，并建立了统一的性 能评价标准，通过各种指标衡量指纹识别系统的性能，如e e r 、f 脓，f n 棵，f 躲1 o o 、f 脓1 0 0 0 ，z e r o f n 躲和z e r o f 职。其中，e r r 是等错率，即拒识率和误识率相 等时的拒识率或误识率。f 豫是误识率，f n 职是拒识率。f 豫1 0 0 表示当f 豫= 1 1 0 o 时的f n 豫，f 脉1 0 0 0 表示当f 躲= 1 l o o o 时的f n t ，z e r o f n 豫表示当f n 脓= o 时的f 躲，z e r o f 豫表示当f 脉= o 时的f n 脓。近年来，f v c 的各项标准在指纹识别 算法性能的研究中已经被广泛采用。 1 2 指纹匹配算法研究现状 与以前人工处理指纹识别方式不同，现在的自动指纹识别系统并不直接存储 指纹的图像，而是通过对两幅给定的图像提取特征信息进行匹配，判断这两枚指 纹是否是同源的，即是否来自同一个指头。由此看来，指纹识别算法最终都归结 为在指纹图像上找到并比对指纹的特征。 目前，用于指纹验证的特征可以分为两类：总体特征和局部特征。总体特征 是指那些用肉眼直接就可以观察到的特征，包括：纹形、模式区、核心点( c o r e ) 、 三角点( d e l t a ) 。纹形是指纹线的整体形状，主要有环形( 1 0 0 p ) 、弓形( a r c h ) 、 山东大学硕士学位论文 螺旋型( w h o r l ) 三种基本类型。模式区是指指纹上包括了总体特征的区域，即从 模式区就能够分辨出指纹是属于那一种类型的。纹形和模式区常用作指纹分类1 6 】。 核心点位于指纹纹路的渐进中心，是曲率最大的细节点。三角点位于从核心点开 始的第一个分叉点或者断点、或者两条纹路会聚处、孤立点、折转处。核心点和 三角点统称奇异点。 局部特征是相对于总体特征而言的细节特征，可以分为两类：单一细节特征 和混合细节特征。单一细节特征是指客观存在的，可以通过特征提取算法直接提 取的细节特征一一细节点( 端点、分叉点、分歧点、孤立点、环点、短纹) 和纹 线。目前最常用的细节点是纹线端点和纹线分叉点两种。混合细节特征是由单一 细节特征采用不同的方式组合而成的，常用于基于点模式的局部匹配中。例如： 临近特征特征向量( a f v ) 等1 7 1 。 根据指纹匹配的模式可以分为验证模式和辨识模式1 1 一矗”】；根据操作过程不 同可分为自动匹配【1 6 ，2 0 1 和人机交互匹配【1 2 】；根据匹配适应性可以分为弹性匹配f 2 l 】 和刚性匹配【2 2 1 。不同的分类不胜枚举，然而这些分类方法都难以囊括所有的指纹 匹配算法，同时一些算法又可以综合多种分类的特性。 按照指纹匹配使用特征的不同可以分为以下五种，基于点模式的匹配【2 3 圆】、 基于纹线的匹配【3 0 。3 2 】、基于图的匹配【3 3 3 4 1 、基于纹理的匹配1 3 5 - 3 7 1 以及多种细节特 征混合的匹配方法【3 8 瑚j 。 基于点模式匹配是目前指纹匹配算法中的主流方法。首先，利用局部特征匹 配获得模板指纹和待识别指纹之间的旋转平移参数：其次，将两幅指纹进行姿势 调整；最后，全局匹配求取匹配得分。该类方法的关键在于局部匹配中使用的局 部特征，其目的是为了获取精确的旋转平移参数。众多学者为此做了大量的工作。 尹义龙【3 6 1 提出了一种基于纹线拟合的指纹匹配方法，即利用纹线拟合技术来 寻找基准点对的指纹匹配算法。该算法基于指纹纹线的相似程度寻找一对基准特 征点，在进一步筛选更精确的基准点对后，根据基准点对的坐标计算两幅指纹图 像( 模板图像、待识图像) 的相对平移和旋转参数，并将待识别图像相对于模板 图像进行图像姿势纠正，最后使用坐标匹配的方法统计两幅图像能够匹配的特征 点数目，实现两枚指纹的匹配。 9 山东大学硕士学位论文 x i f e n gt o n g 【1 7 1 等人提出了一种基于临近特征向量( a f v ) 的细节匹配算法。 该方法利用纹线方向和纹线数目信息生成成了一个新的局部结构一一临近特征向 量。首先，从给定细节点a 引出两条相互垂直的直线，确定四个与细节点同等距 离的临近点t 1 ，t 2 ，t 3 ，t 4 ，4 3 2 1 ，oo oo 分别表示四个临近点的方向。0 1 ， 0 2 ，0 3 ，0 4 表示细节点a 的方向。与四个临近点方向4 3 2 1 ，oo oe 之间的夹角， n 1 ，n 2 ，n 3 ，n 4 ，n 5 ，n 6 则表示a t l ，a t 2 ，a t 3 ，a t 4 ，t l t 3 ，t 2 t 4 跨越的纹线数目。那么， 临近特征向量就是由0 1 ，0 2 ，0 3 ，0 4 ，n 1 ，n 2 ，n 3 ，n 4 ，n 5 ，n 6 组成的一维向量。其次， 算法使用两对细节点进行姿势调整。最后，由坐标匹配细节点对的相似程度计算 得到匹配得分。 w e i w e iz h a n g 【4 0 】等人的基于c o r e 点的结构匹配算法，受奇异点提取准确性的 影响。卢朝阳【4 1 】等人的基于d t ( d e l a u n a yt r i a n g u l a t i o n ) 网格的细节点匹配算 法，利用d t 网格搜索匹配线对从而加快搜索速度及匹配速度。j i nq i 【4 2 】等人定义 了一个由细节点周围若干采样点组成的新特征向量，并且结合方向场信息进行匹 配。 指纹图像在本质上是脊线和谷线以固定的频率交替出现的一种纹理模式。正 是基于这个纹理特性，a k j a i n 【4 3 1 等人提出了基于滤波器组的指纹匹配算法。首 先，以c o r e 点为中心将指纹图像划分成若干个扇形区域。其次，使用g a b o r 滤波 器对指纹图像分成8 个方向 ( o 。，2 2 5 。，4 5 。，6 7 5 。，9 0 。，1 1 2 5 。，1 3 5 。，1 5 7 5 。) 进行滤波，得到每个方向的g a b o r 滤波图像。然后，在计算每个 滤波图像的纹理特征值一平均绝对方差从d ，并且将所有区域的纹理特征值a a d 以某个固定的顺序组成指纹特征码f i n g e r c o d e 。最后，计算模板指纹和待识别指 纹特征码之间的欧式距离，实现指纹匹配。 指纹匹配是自动指纹识别系统( a f i s ) 的核心研究内容之一，它在指纹特征 提取之后，是自动指纹识别的最后一步，也是非常关键的一步。指纹匹配靠比较 两枚指纹的细节点、纹线或者其他局部结构特征来决定指纹的唯一性。然而，由 于采集设备的不完善性、采集条件的随机性以及预处理技术的局限性，使得真正 特征点的缺失、伪特征点的存在和特征点定位偏差的情况普遍存在。所以，指纹 匹配必然还是一种模糊匹配，且需要具备一定的弹性。 l o 山东大学硕士学位论文 1 3 课题的选择 通过对常用指纹匹配算法的研究可以看出，基于点模式匹配是目前指纹识别 的主流算法。其中常用的细节点主要是纹线端点( r i d g ee n d i n g ) 和纹线分叉点 ( r i d g eb i f u r c a t i o n ) 两种。基于点模式匹配算法要求指纹仪在扫描指纹图像时 手指和指纹仪的扫描窗口有足够的接触面积，只有这样指纹图像中才会有足够的 细节点信息和相应的细节点纹线信息供匹配算法使用。随着实际应用要求指纹仪 足够小，以便嵌入到鼠标、蜂窝电话等小型设备中，指纹仪的扫描窗口必将变小， 而且在刑侦领域，残留指纹图像也许会比较小。这种情况下，基于细节点匹配的 策略将面临挑战。 本文针对上述关于重叠面积小、细节点不足的指纹图像，提出了一种基于细 节点局部结构的指纹识别方法。根据细节点( 端点和分叉点) 所在脊线设计了两 种局部结构，通过计算局部结构的相似度，进而融合计算整体指纹的相似度。这 样就充分利用了指纹的细节点及其所在脊线和相邻脊线信息，使得特征点的可利 用信息更丰富，可靠性更高。 在利用每个细节点局部结构的相似度来计算整体指纹相似度环节，本文将指 纹细节点周围图像质量评价引入匹配算法，提出了一种结合质量因子的加权平均 算法。首先计算每个局部结构的外接矩形，并对每个矩形区域进行质量评价，计 算每个局部结构外接矩形区域的指纹质量因子：然后，将每对匹配细节点各自所 在区域的质量因子的平均值，作为该相似局部结构在计算整体指纹匹配相似的权 重。 1 4 论文的组织和主要贡献 本论文共分四章，其中第一章为绪论，主要介绍了自动指纹识别技术的发展 历史、研究内容、性能评价体系，并对现有指纹匹配算法进行综述。第二章和第 三章为正文部分。第二章介绍了一种基于细节点局部结构的指纹匹配算法。第三 章提出了基于指纹质量评价的指纹匹配算法。第四章是本文结束语。 本文主要针对重叠面积小、细节点不足的指纹图像，提出了基于细节点局部 结构的指纹识别算法。该算法的优点是能够充分利用待识别指纹的细节点及其相 邻纹线的有效信息，一定程度上能够解决细节点不足的指纹图像识别。实验结果 山东大学硕士学位论文 表明，该算法对解决小面积指纹匹配问题有一定的优势。 为了提高识别算法准确率，将指纹图像质量评价引入指纹匹配算法中，对每 个局部结构区域的指纹图像质量进行评价，求得每个质量因子作为相应局部结构 在整体指纹匹配的权重。实验结果表明，该算法在一定程度上提高了指纹识别准 确率。 1 2 山东大学硕士学位论文 第2 章基于细节点局部结构的指纹匹配算法 随着传统身份识别的不可靠性与日俱增，基于生物特征的身份识别因其不可 伪造性受到越来越多的关注。自动指纹识别系统( a f i s ) 就是生物特征识别的一 种，包括指纹采集、预处理、特征提取和指纹匹配。指纹匹配处于自动指纹识别 系统中的最后一个环节，也是非常关键的一步，因此成为一个研究的重点。 多年来，国内外众多学者致力于指纹匹配的研究，曾提出了许多用于指纹匹 配的算法【4 3 4 5 1 。但目前普遍用的是基于细节点的匹配算法。也就是说基于细节点 的点模式匹配是指纹匹配的主流方式。常用的细节点有两种，即纹线端点和纹线 分叉点( r i d g eb i f u r c a t i o n ) 【1 2 】，纹线端点指纹线突然结束的位置；而纹线分叉 点则是纹线突然一分为二的位置( 如图2 1 所示) 。这两种特征点在指纹中出现的 几率最大、最稳定、易于检测而且足以描述指纹的唯一性。在这种算法体系下， 指纹被表示成离散的细节点集合，指纹匹配依赖于细节点的匹配。 【a )【b ) 图2 1 指纹特征点的类型( a ) 端点，( b ) 分又点 j a i n m 】在匹配算法中引入脊线信息，并用极坐标来表示细节点的位置和方向， 同时针对每个细节点保存一段相应的线，j a i n 方法用纹线的匹配程度来筛选参考 细节点，然后在极坐标系中用固定大小的约束窗口来寻找匹配细节点对。罗希平【4 别对j a i n 方法做了改进，将纹线信息作为匹配两个细节点的要素之一，同时采用 大小动态调整的约束窗口，即可变大小的限界盒。j a i n 在抽取纹线信息时，对于 端点可以直接抽取和该细节点相连的纹线，对于分叉点必须抽取两个分叉中的一 条。尹义龙【4 6 】在直角坐标系通过计算纹线相似度寻找基准细节点对，然后对待识 指纹图像进行姿势纠正，最后统计匹配结果。该算法对于适当面积的指纹图像表 现出速度快、准确率高的优点，但是基准点对的选取仅考虑端点，也就是说只对 端点所在脊线进行离散采样，而且匹配是通过统计细节点个数来实现的，对小面 积指纹图像的识别也是束手无策。 本文根据细节点( 端点和分叉点) 所在脊线设计了两种局部结构，通过计算 局部结构的相似度，进而融合计算整体指纹的相似度。这样就充分利用了指纹的 山东大学硕士学位论文 所有细节点及其所在脊线和相邻脊线信息，使得特征点的可利用信息更丰富，可 靠性更高。 2 1 算法描述 本文在分析尹义龙等人的基于纹线相似度的指纹匹配算法后，针对采集面小、 细节点数量不足等情况，提出了一种新的基于细节点局部结构指纹匹配算法。 首先利用细节点所在脊线的相似度寻找基准细节点，并进行姿势调整。即所 有的细节点均沿纹线方向进行等距离采样。对于分叉点来说，就是沿分又之前的 纹线进行采样。每一个细节点与其所在纹线的采样点构成一个向量，向量之间的 欧式距离用来度量纹线的相似程度，从而确定细节点之间的对应关系，选择匹配 程度最高的5 个细节点作为参考点，计算旋转平移参数，将旋转平移恢复。 其次，根据细节点类型( 端点和分叉点) 分别设计了相应的局部结构，对于 任意匹配端点，相邻纹线信息是通过对纹线采样获取的。过端点并垂直于端点所 在纹线的线段交其左右相邻纹线于两点，称之为该端点的左右邻点，并分别以相 交所得的左右邻点为中心向两侧采样，这样相当于5 个有相联关系的端点及其所 在纹线构成一种局部结构。即构成端点类型局部结构。对于任意分叉点，与其关 联的三条纹线是可以使用的有效信息。利用分叉点和三个分别来自三条纹线的3 个采样点组成小的d t 网格。即构成分叉点类型局部结构。 最后，通过计算每个局部相似度，进而融合计算出整幅指纹的相似度，来判 断两幅指纹是否同源。 2 2 算法实现 算法流程如图2 2 所示 图像分割图像增强l 1 细节点提取 图像二值化图像绍化i _ 细节点关联 纹线采样 输出匹配结果i i 叫全局匹配_ l 局部匹配_ _ 叫局郫结构设诈 图2 2 算法流程示意图 1 4 山东大学硕士学位论文 2 2 1 指纹图像预处理 指纹图像预处理是指纹特征提取前的不可缺少的一个重要环节，主要用于突 出指纹图像中的纹理、方向信息，消除或者减弱噪声等无用信息。指纹图像预处 理包括指纹图像分割、图像增强、二值化、细化等。 指纹图像分割位于预处理的最前端，就是将指纹图像从背景区域中分割出来， 对于缩短图像处理时间、提高特征提取的准确率都具有重要意义。 图像增强是根据指纹图像纹理的方向性和纹线距离对可恢复的纹线进行恢复 和增强，对于不可恢复的区域进行屏蔽。 二值化即将图像中灰度大于某阈值的像素的灰度置为1 ，小于等于该阈值的像 素的灰度置为0 ，即将图像变为二值图像。 细化就是提取指纹图像的脊线骨架。本文的指纹图像增强和二值化算法采用 文献m 中的提到的八方向增强算法思想。 234)6 l234567 l 7 o0 0o 7l 6)4321 7 65432 图2 3 在一个像素处的8 个指纹脊线方向 从细化后的图像中就能提取出细节点来，但由于噪声的存在和图像质量等方 面的原因，脊线骨架中必然存在的脊线断裂和毛刺等现象，还有可能在一小片区 域内有很多不成形的短脊线，这些都造成提取出来的细节点中有很多的伪细节点， 因而要进行细节点的后处理以尽可能地去掉伪细节点。如图2 4 所示，a 组的脊线 特征容易被错误的提取为b