（信号与信息处理专业论文）afis的算法研究及其设计与实现.pdf

a f i s 的算法研究及其垃计与实现 摘要 本文首先从理沧上研究了指纹自动识别技术，对经典的数字剧像处理方法、 神经网络、数学形态学等在a f l 8 ( 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 i ls y s t e m s ) 中 的应用作了较全面的总结。其次，在系统研究经典数字图像处理方法的基础上， 改进了在a f i s 中应用的经典方法，并对指纹图像细化提出了新的、行之有效的力 法。第三，研究了神经网络在a f i s 中分类器殴计的应用情况，并就其应用和另外 两种非n n ( n e u r a ln e t w o r k ) 分类器作了比较试验。第四，本文在研究数学形态 学的基础 ：，将其引入a f i s 中，并作了探讨和模拟。第五，在系统研究指纹自动 以别技术的前提卜，设计、制作了一套指纹自动识别系统，达到了较满意的效果。 最后，研究了a f i s 中特征点匹配过程的误差问题。 关键词：指纹自动识别系统，指纹图像，口哥艇神经网络，结构元素 南京理 太学硕i “论文 第1 页 a f i s 的算法研究及其设计与实现 a b s t r a c t i nt h i st h e s i s a u t o m a t e df i n g e r p r i n ti d c n t i f i c a t i o nt e c h n o l o g yi sr e s e a r c h e di n t h e o r y a n d t h ea p p l i c a t i o no fc l a s s i c a ld i g i t a li m a g e p r o c e s s i n gm e t h o d s 、n e u r a n e t w o r ka n d m o r p h o l o g yt oa f i si sc o n c l u d e d a tf i r s t s e c o n d l y c l a s s i c a ld i g i t a l i m a g ep r o c e s s i n gm e t h o d s t h a ta r ea p p l i e dt oa f i si sm a d e b e t t e r ，a n dan e w e f f i c i e n t t h i n n i n gm e t h o di sp r e s e n t e dt h i r d l y ，n e u r a ln e t w o r kc l a s s i f i e r st h a ta r ca p p l i e dt o a f i sa r er e s e a r c h e d a n dc o m p a r ew i t ha n o t h e rt w oc l a s s i f i e r st h a ta r en o tn e u r a l n e t w o r kc l a s s i f i e r f o u r t h l y ，b a s e do nm o r p h o l o g yr e s e a r c h i n g ，m o r p h o l o g yi sa p p l i e dt o a f i s ，a n ds o m ea n a l o g i c a lr e s u l t sa r eg i v e n ，t h e n 。as e to fa f i sd e v i c ei sd e s i g n e d b a s e do nt h e s er e s e a r c h i n go f a f i s a tl a s t t h ee r r o rp r o b l e mo f c h a r a c t e r i s t i cp o i n t m a t c h i n g i sr e s e a r c h e d k e y w o r d 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 s ， f i n g e r p r i n ti m a g e ， n e u r a ln e t w o r k s ， s k e l e t o n i z a t i o n ， s t r u c t i n g e l e m e n t 南京理工大学硕士论文 第1 i 页 a f i s 的算法研究厦其设计与实现 1 指纹自动识别系统概述 1 1 指纹识别的意义 指纹被国内外专家、学者誉为“证据之首”，这是由其本身具有的特点决定 的，这些特点是：人各不同、基本不变、触物留痕、认定人身。随着社会的发展 指纹识别不仅被用来作为追查罪犯的工具，也被广泛应用于民用领域：如金融储 蓄、互联网在线贸易等广泛的领域。 1 1 1 人各不同 1 8 8 2 年，英国科学家高尔顿论述了指纹的互异性，也即不存在相同的指纹， 1 9 1 0 年，法国巴黎大学教授太柴氏用数学方法对此加以证明，他把指纹上的细节特 征归为四种，即起点，终点，分歧，结合每个指纹约有1 0 0 个细节特征，经过组 合排列，以4 的1 0 0 次方计算，得出6 1 位数，即4 1 唣1 6 0 6 9 1 0 ”，在以一个世纪 内生存的人口约5 0 亿计算，每人十个指头，即有5 0 0 亿个指纹，用5 0 0 亿除上述的 位数得出一个5 0 位数。就是说要经过5 0 位数长的世纪才可能出现重复的指纹。 因此，世上活着的人中是不可能有两个相同的指纹的。 对同胞胎生的人的指纹进行考察，发现尽管他们的相貌极为相似，但他们的指 纹却没有一个完全相同的。 近百年来的各国指纹档案管理查对和侦破案件中的指纹鉴定实践中，未发现有 指纹完全重复的实例。 这就从理论和实践上都充分证明了指纹人各不同的客观性。而且，实践还进一 步证明了不仅人各不同，就是同一人的手指和手掌的不同区域之间也是各个有别 的。 指纹有了“人各不同”这一特性，为指纹用于身份认证提供了客观依据。 1 1 2 基本不变 任何事物从发生、发展到消亡，都经历过一个由量变到质变的过程，当事物处 在量变阶段，始终保持着其本质的属性及体现这些属性的特征，这就是事物的稳定 性。由于稳定性是包含着量的变化和部分的质变，因此说，稳定性是相对的。 对于指纹同样具有这种相对稳定性，且从实际的考察中发现，它的相对稳定性 很强，从胚胎学角度考察，胎儿3 4 个月即产生指纹了，至6 个月左右的胎儿即形 成了完整的指纹，出生后随着年龄的增长，指纹会变粗，花纹的面积会增大，但到 了成年之后，这些变化即无显著表现，而花纹的类型结构、细节特征的总体布局、 乳突纹线的总数目等方面，自怀胎六个月到出生至死亡之间，始终无明显变化。 指纹相对稳定性很强的特点，还表现于它具有一定的复员性和难于毁灭性。它 的复员性来源于真皮乳头的再生能力。只要不伤及真皮，它的花纹形态和结构以及 全部细节特征都能得以恢复。指纹的难以毁灭性能是与它自身可恢复的性能密切相 关的。 这一观点同样在实践中得到证实。 践，耒发现由于时问变迁、年龄增长， 南京理工大学硕士学位论文 近百年来，各国侦察、审判中个人鉴别的实 指纹完全变成为另外一个样子的实例。相 聋2 页 f i s 的算法研究及其设计与实现 反，从大量的同一人前后相差几十年的相貌、指纹的考察证明，人的相貌可以因年 龄的增长、生理过程的变化而几乎成了两个人样，然而其同一指的指纹却依然如 故。 指纹很强的相对稳定性为把指纹作为身份认证的工具提供了很有利的条件。 1 i 3 触物留痕 手一经接触物体即留下了痕迹，这是唯物的、客观的，指纹的这个特点是与手 掌面附着的汗垢韵性能密切相关的。 1 1 4 认定人身 手印是直接反映人手接触部位的外表结构特性的，这种直接关系使得手印与手 迹、印章等其它痕迹物证不同，可以直接认定人身。 由于指纹具有上述特点，指纹鉴别得到了广泛的应用。例如，利用指纹图像验 证身份证或工作证的真假，因而控制机要单位、军事设施的大门，非法出入国境， 甚至银行亦以指纹图像作为取款凭证，避免冒领事件。在目前日益发展的互联网在 线贸易方面，指纹识别作为一种有效的识别手段，也被纳入i n t e r n e t 贸易的c b s a ( 公共安全框架协议) 。 1 。2 指纹自动识别系统的发展 自十九世纪以来，英国、美国、德国、日本等国纷纷建立起指纹档案，用于协 助破案，但较长时期中，无论是指纹分析，还是指纹存贮和查对都是人工的方式， 利用普通放大镜对指纹进行分类，数线和编码，并以数以千、万计的指纹卡片进行 查对，花费大量的人力和时间，工作效率很低，且重复劳动太多。 二十世纪六十年代，技术先进的国家开始研究以自动化方式来代替落后的人工 操作。经过三十余年的努力，大部分技术先进的国家，如美国、日本、西德、南斯 拉夫、罗马尼亚、加拿大、巴西、瑞典等国家已基本采用了全自动化方式管理指纹 档案。尤其是美国在f b i 的积极推动下，使美国在八十年代初就出现了全自动化指 纹识别商业产品。 所谓半自动化，是指纹分析采用人工方式或人机结台的半自动方式，但存贮和 查对时都采用计算机自动化工作的方式。在指纹分析时，不是沿用老式放大镜观 察，而是借助予带有投影屏幕的指纹分析仪或光笔，对指纹进行分类、定位和编 码，这样，在管理上更加科学简便，减轻了大部分人工劳动。 所谓全自动化，不仅指纹贮存和查对采用自动化方式，而且指纹分析也有电子 计算机自动进行图像识别，这就进一步节省了指纹分析的时间，减轻了人工劳动。 自动存储和查对指纹的技术是既能查对前科又能查对现场的指纹的现代化技 术。它的关键，除了要有一台外存容量很大的计算机外，主要是研制人工智能模拟 自动分析储存和查对指纹的软件程序及适应于计算机自动分析、贮存和查对的分析 编码方法。 据国外资料报道，目前计算机指纹鉴定系统有以下几种类型： 南京理工大擘硕士学位论置第3 页 a f i s 的算法研究厦其设计与实现 l 、十指鉴定系统：该系统能对十指指纹卡片进行自动阅读，分类和查 找，对比，还可与单指鉴定系统联用查对现场指纹。 2 、单指鉴定系统：该系统能对现场指纹进行编码，对一些模糊不清的指 纹或残缺不全的无中心、少三角的指纹进行图像增强处理。并可在指纹档案数 据库中对现场指纹进行查对，查对速度可达每秒1 0 0 0 个单指。有的鉴定系统在 查找比对时，如不能得出唯一肯定的结果，还能找出2 些近似的可疑指纹，再 由专家进行人工鉴定。 3 、十指与单指联用鉴定系统：该系统能对指纹进行全面的鉴定，还可存 入人身描述资料( 如姓名，性别，种族，肤色，出生年、月、日等) 。每天可 存5 0 0 份十指卡片。 4 、手指直接阅读系统：该系统用于手指指纹特征的直接阅读，只要把手 指置于扫描屏上，几秒钟内便可通过计算机查处该人的身份。该系统也可和十 指鉴定系统或其它系统联用，通过普通电话线传递指纹信息，向远距离的指纹 中心进行查询。传送一张十指卡片只需3 0 秒钟，而过去用传真则需1 5 分钟。 5 、 图解笔输入的指纹鉴定系统：该系统借助机械装置读取指纹特征的坐 标数据，然后存入计算机内机械查找比对，它可以用于模糊指纹的特征编码， 这是全自动指纹阅读器不易处理的。用这种图解笔阅读一个指纹特征的时间约 需6 1 0 分钟。 6 、人工编码鉴定系统；这是西德正在使用的指纹鉴定系统它是在常规 编码的基础上划分五种纹型，再按“2 4 ”区出现的特征进行补充编码，输入到 中型计算机内存查，使用这种方法查对速度虽快，但分析速度根慢，每人每天 只能分析8 张。使用这种方法查对一个人的指纹，在1 0 0 万指纹卡片中最多提 出3 张卡片来作鉴定。目前他们正在研究出光电笔标示特征和数线的方法来加 速人工编码。 自动化指纹鉴定系统比指纹档案的人工管理、查找、比对，具有显著的优越 性，主要表现在以下几个方面： l 、储存容量太。如美国斯派里兰德公司为亚利桑那州公共安全署安装 的一套指纹鉴定系统，可以储存1 0 0 多万份指纹卡片，西德拟已数台中型计算 机存贮1 0 0 0 万指纹卡片，目前用人工编码法己存入6 0 万份指纹卡片。 2 、管理人员少。由于艇个系统全部由计算机实行自动控制，所以，只需 少数人即可完成过去由大量人工完成的整琐工作。如安装在亚利桑那州警察部 门的指纹鉴定系统，只需四名技术员和六名雇员，设备流通能力为每天6 3 4 张 指纹卡片。计算机每天工作3 5 个小时，百分之八十二的时间无需看管。一九 七七年一月开始试用，就逐步消除了指纹积案5 万多份。 3 、查对速度快、工作效率高是自动指纹鉴别系统的显著特点。例如，美 国2 5 0 s 型指纹自动鉴别系统约1 分钟就能处理十份十指卡片。南斯拉夫的计算 机系统处理一个单指指纹的时间是6 0 s ，瑞典则是2 0 s 。更为突出的是查对速度 极快，对及时配合破案非常有利。美国的指纹鉴定系统每秒可比对1 0 0 0 1 2 5 0 个手指。日本电器公司和国家警察厅研制成的能快速辨别模糊指纹的识别系 统查找1 个指纹只需5 6 分钟，而人工方法需一个星期。西德某案中的指 纹，以前组织3 0 人整整查了1 个月，而用新方法只要1 个人3 小时即可完成。 4 、工作质量高。美国的2 5 0 l 型单指鉴定系统，能对一些残缺不全、模 糊不清的指纹或无中心、少三角的指纹进行图像增强处理，然后进行查对，准 确率极高。 南京理工大学硕士学位论文第4 页 a f i s 的算法研究及其设计与实现 5 、便于建立网络。美国2 5 0 s 型指纹鉴定系统中的读编控制台利用普通 电话线与中心系统连接，可在远距离迅速可靠的向指纹鉴定中心传递有关资 料，储存指纹档案和人身描述材料，查对现场指纹。因此，可以用来在一个区 域或全国范围内建立指纹快速查询网络。 1 3 我困目前指纹自动识别系统的情况 我国八十年代初已有部分单位开展了利用电子计算机管理指纹档案的研究工 作。目前除公安部门和高校、研究所外，国内已有十几家公司推出了各自的商业化 产品，为我国生物识别领域的发展迈出了一大步。 总体说来，我国的研究情况大体分为三类：1 、全自动化的。其中又分为三 家：1 ) 北京大学的石青云院士进行这方面的研究工作已十几年，北大方正集团以此 为基础成立了北大指纹电子公司，推出了面向警用和民用的商业化产品。另外在西 安交通大学研究基础上成立的西安青松电子公司也推出了自己的指纹识别产品。 2 ) 国内些电子公司利用国外购买的软件包进行的= 次开发的商业产品，或在一些 民营科技力量的研究成果基础上推出的商业化产品。如北京鸭绿江公司等。2 、半自 动化的a 武汉、天津等地在用此法，目前已进入实用阶段。他们主要是采用人工编 码的方法，把指纹分区，每一区有自己的代码，然后按特征点所在位置进行编码。 此法对定中心要求很高，且需人工记住每个区的代码，所以人的工作量仍然很大。 这种方法只有部分地区使用，已处于淘汰期。2 、全自动、半自动兼容式。这是公安 部所属第二研究所曾提出的方法。他们是根据公安部的指示，考虑我们国家经济上 的困难，面向中小城市。他们进行这项研究已近十年，全套软件已经研制成功。所 谓全自动、半自动兼容，是指在这种工作体制下，指纹库所存的文件在自动化和半 自动化两种工作方式下是通用的，全自动工作方式是用一台摄像机或f o p 将指纹输 入，首先进行预处理，获取指纹特征点的坐标及纹线数，然后或者用于建档，或者 用于对比。半自动化工作方式是在一台数字化仪上直接将指纹特征点坐标取出( 不 需要进行预处理) ，这是人工进行的，但相对来讲，人的工作量太大。 1 - 4 本文研究的主要内容 虽然自八十年代初，我国就开始研究指纹自动识别技术，并在九十年代陆续推出商业 化的指纹识别产品，但在识别率方面仍然不能使人满意。 本文首先从理论上研究了指纹自动识别技术，对经典的数字图像处理方法、神经网 络、数学形态学等在a f i s 中的应用作了较全面的总结。 其次，在系统研究经典数字图像处理方法的基础上，改进了在a f i s 中应用的经典方 法，并对指纹图像细化提出了新的、行之有效的方法。 第三，研究了神经网络在a f i s 中分类器设计的应用情况，并就其应用和另外两种非 n n ( n e u r a ln e t w o r k ) 分类器作了比较试验。 第四，本文在研究数学形态学的基础上，将其引入a f i s 中，并作了探讨和模拟。 第五，在系统研究指纹自动识别技术的前提下，设计、制作了一套指纹自动识别系 统，达到了较满意的效果。 最后，研究了a f i s 中特征点匹配过程的误差问题。 南京理工大学硕士学位论文 第5 页 a f i s 的算法研究及其设计与实现 2 指纹知识简介 2 1 指纹的一般形态 手掌面的皮肤比较复杂，已三种不同形态的结构布满在整个手掌面，即届肌褶 纹、皱纹和乳突纹。其中乳突纹即是指皮肤组织的凸凹结构，显示在表面上的细小 凹凸纹路，其形态为线条状，呈有规则的定向排列。它是皮肤细胞组织的一种结构 ( 排列) 形式，指纹即指指头乳突花纹。 2 1 1 指纹单一线条的般形态 根据纹线自始至终的流程所呈现的基本形态，可以分为以下几种： l 、直线形纹线从一方流向另一方，基本呈直线状态，有横直、竖直、 斜直之分。 2 、波浪线纹线呈凹凸波浪式状态，有规则不规则之分。 3 、 弧形线纹线中间弯曲呈圆弧状，有横孤、纵弧之别 4 、弓形线纹线弯曲呈弓状，其弓顶较高，两头有返转现象。 5 、 角形线纹线弯曲呈拐角状，有左拐、上拐、下拐之分。 6 、箕形线纹线拐弯后返回原方向，呈簸箕形。 7 、 环形线纹线呈闭口的圆圈，似环状。 8 、 螺形线纹线的另一端，饶起点旋转惆以t - ，呈螺旋形。 9 、 曲形线纹线的两端以相反的方向弯曲，呈“s ”状或“，状，厉又 朝一个方向旋转。 1 0 、 点形线纹线断续呈点状虚线，或单独的一个乳突点。 就以上所述绘其基本形态如下： 一i ( 2 ) 1 卜、r 、 ( 3 ) 、u ( ( 4 ) 八八 ) v ( 6 ) 夕夕乡，d 夕夕 ( 7 ) 南京理i 大学硕士学位论文第6 页 a f i s 的算法研究及其设计与实现 ( 8 ) 9 ( 9 )z ( 1 0 ) ， - 图2 1 1 单一线条的基本形态 2 1 2 指纹的组合形态 上述各单一一形态的纹线，在手指手掌各部位的分布，并非杂乱无章，它们以诌： 多相同的纹线在一起，占据一定的位置，形成一种体系，若干种1 i 同的体系义可构 成复杂的图案花样。据统训，中国人的指头花纹，有2 5 左右由二种体系组成， 9 75 左右由三种体系构成，称这三种体系为三个系统，定义如下： 1 、 内部系统居于花纹中间。通常纹线较细密，但数量不定。内部系统 的中心结构和形态的复杂多样性，构成了花纹划分类型的主要依据。 2 、 外围系统纹线从左、上、右三面包围了系统，纹线数量较多。 3 、根基系统分布在内部系统的下面，即基底部位。 三个系统的纹线在某处汇台，构成三角形，称它为三角，三角所在位置与花纹 中三角数量有关。每个花纹中三角数量为1 3 个不等。一个三角的，在内部系统的 左侧或右侧；两个三角的左、右两侧、或上、下两侧各一个；三个三角的多呈左、 忆右分布。三角的三个边分别由三个系统直接参与汇合的纹线组成。 三角的各个角分别由不同的两个系统纹线组成： 上角：由内部系统和外围系统的边线相交构成。 外角：由外部系统和根基系统的边线相交构成。 下角：由内部系统和根基系统的边线相交构成。 图2 一l 指纹的三角图示 三角的外边，又称为外角的上部支流，底边又称为外角的下部支流。上、f 支 流构成三个系统的分界线。在划定三个系统的界标时，有时上、下部支流的纹线较 短此时可顺其外侧纹线继续追踪而标定。 2 2 指纹纹型的基本分类 随着科学研究的深入，指纹工作实际应用的发展，指纹分类从简到繁，由粗至 细逐步趋于完善。 根据指纹客观存在的形态结构和纹线分布规律，结合实际工作的经验，便利用 指纹存档、查对、检验、鉴定等工作的开展，我们按照指纹整个花纹的总体结构， 将其分成四各基本类型，即弓形纹、箕形纹、斗形纹和混杂形纹。略述如下： 南京理i 大学硕士学位论文第7 页 a f i s 的算法研究及其设计与实现 1 弓形纹 主要由弓形线、横商线层叠f 叮成，纹线由方流向另 乃，- 串部 向上弯曲呈弓，不返转，依其形态不同，又有弧形线、帐形线之分。 弧形纹由多数弧度较小的弧形线在上部，少数横直线在p 部构成。自指 尖到指节，纹线弧度逐渐变小，到指节附近的纹线与指节屈肌线1 f 行。用一直线连 接多数弧形线的凸出点作为中轴线，观察中轴线上的上端或弧形线的凸面倾同可分 出三种倾向的弧形纹，即左倾弧、无倾弧、右倾弧。 帐形纹由多数弧度较大的弓形纹线在上部、少数横直线在下部，中心部 位有一根以上的垂线或斜形线支撑着弓形线而组成，形似帐篷，在支撑线的根基部 位，常形成类三角。依支撑垂线斜形线上端的朝向可分i 种倾向帐形纹，即左倾 帐、无倾帐和右倾帐。 2 箕形纹内部花纹中心有一根以上的箕形线，其上部和两侧外例山较多的 ，_ j 形线包饶，下部有一些波浪线和横直线作为根基线这三个系统组合而成。通常构 成一个三角，位于箕枝靠根基的一侧，个别的有两个三角，位于箕头的上下两侧， 或左右两侧。对箕形纹，依其内部形态可分为瘦长箕、普通箕、和胖圆箕；依其箕 口部位的形态不同可分为开口箕和闭口箕。依其倾斜流向不同又可分为左箕和右 箕。根据实际观察和统计，左手约9 4 7 4 为右箕，约5 2 6 为左箕。右手则恰恰 相反人们习惯地把出现率占绝大多数的称为f 箕，少数相反的称为反箕。 3 斗形纹 内部花纹中心有一根以上的环形线，或曲形线，其上部和两侧外同 由较多的弓形线包饶，下部有一些波浪线羽i 横直线组合而成，有两个以r 的! 角。 斗形纹依其花纹内部形态，可分为以下七种类型： 环形斗中心花纹一条以i 的环形线组成。崩 直线把所有环形线按长轴h 向 连结起来，称中心轴，依此轴线的倾斜方向可以看出环形斗的不同倾向，人敏司分 为左倾环形斗、无倾环形斗和右倾环形斗。 螺形斗中心花纹由一条以上的，起点方向一致的螺形线组成的斗形纹，按其向 外旋转方向的不同可分左螺斗、右螺斗两种。根据实际观察和统计，左手指纹左螺 多，右手指纹右螺多，人们称这种出现率高的为正螺，少数相反方向的为反螺。 纹形斗花纹中心有两条以上的螺形线相对绞饶旋转，其起点明确可靠，遥呼成 对，或一左一右，或一上一下，均不顶连其它纹线者均称绞形斗。依据花纹中心蝶 形线的旋转方向不同，分为左螺绞，右螺绞。 双箕形斗花纹中心有两条以上独立、圆滑、顺势的曲线相重叠向一个方向饶旋 的斗，或在一条曲线的两个弯头内各有一个完整的箕形线相绞向同一个方向旋转的 斗，均为双箕形斗。按其旋转方向的不同可分为左旋、右旋两种。 曲形斗花纹中心仅有一条完整的曲线，其上下两个回转弯曲部分圆滑顺势，最 后朝一个方向旋转的为曲形斗。这条曲形线上下两个回转的假箕头内亟，可能是空 腔，亦可能有一条以上的纹线跟着盘绕，按曲形斗的旋转方向，可将其分为左曲 斗、右曲斗。 囊形斗花纹中心条以上的闭1 ：3 箕形线内部，仅有一条以上达到弧形线，其i “i 商廊对向外角共同组成三角，并且不与引向外角的纹线相接触。 其它斗凡花纹中心不属上述六种形态，混淆不清，无固定结构，但中心形态符 台斗形纹条件者，列为其它斗。 4 混杂形纹 凡上述j 种单一纹型不能包括，而由两种纹型混合组成的花纹，或一些形态奇 特，结构杂乱而无法归入弓、箕、斗形纹的花纹均称混杂形纹。 南京理工大学硕士学位论文第8 页 a f is 的算法研究及其设计与实现 按其内部花纹的形态，大致可分为1 、箕帐混合纹。2 、箕斗混合纹。3 、并列 箕形斗。4 、并列斗形纹。5 、杂形纹。6 、箕形纹。这6 种形态。 各种纹型如图2 2 1 。 南京理工大学硕士学位论文第9 页 j 形纹a ) 弧形纹b ) 帐 口纹 譬簟簿蕃譬警、 南京理工大学硕士学位论文 箕形纹 q 形纹 吖二i j 鼎i ， 藿毳霉餮嚣 b j 纹，t ) 并列箕h ) 筻引混禽 图22 i 得种纹犁图示 第o 酉 a f i s 的算法研究及其设计与实现 3 经典算法在a f i s 中的应用及其改进 3 1a f i s 的理论研究发展及趋势 自动指纹识别系统( a u t o m a t e df i n g e r p r i n ti d e n t i f i c a t j o i ls y s t e m s ，通常 缩写为a f i s 或a f i s s ，我们采用a f i s 的缩写形式。) 是一种模式识别系统。模式 一词的含义是可被仿效的标本，也可以理解为一类东西的理想模型，这个类- i j 的任 一实例都是它不尽完善的复制品，通过对许多实例的观察，进行归纳提炼，j 口成模 式概念，即所谓的“学习”过程；以体现一个类的属性为模式准则，用以衡量所给 的样本，从而辨认出该样本是哪一类的成员，则是“识别”过程。可见，模式识别 与分类有关，它在了解足以辨认样本的特性后，可以将样本分配到一个指定的类 中。 模式识别系统都由两个过程所组成，即设计和实现。设计是指用一定数量的样 本( 叫作训练集或学习集) 进行分类器的设计；实现是指用所设计的分类器对待识 别的样本进行分类决策，基本识别系统主要由四个部分组成：数据获取，预处理、 特征提取和选择、分类决策。框图如图3 1 3 所示。 乱八1 数据获取h 预处理h 特征提取和选择h 分类决策卜输出 【_ j 【_ 一1 ，_ 一【。，_ j 1 数据获取：即模式输入过程，通过测量，采样和量化将研究对象的信息用训 算机可以运算的符号来表示。 2 预处理：预处理的目的是去除噪声、加强有用信息并对输入仪器或其它因素 所造成的退化现象进行复员。 3 特征提取和选择：为了有效地实现分类 ：! = 别，就要对原始数据进行变换，得到 最能反映分类本质的特征，这就是特征提取和选择的过程。 4 分类决策：就是在特征空间中用统计方法把识别对象归为某一类别。 最初出于控制犯罪的需要，a f i s 得到很大重视并得以深入研究。早在本世纪五 十年代中期，美国联邦调查局( f b i ) 就联台美国国家标准局( n b s ) 、c o r n e l1 航 空实验室和r o c k w e l l 公司对a f i s 的算法进行了深入研究，此后f b i 再术停止过对 a f i s 的采集、预处理、分类器设计和指纹图像压缩方面的研究。从五十年代到九十 年代初，整个研究基本是采用经典数字图像处理方法，就指纹图像的特点进行改 进，这也是迄今为止a f i s 中最主要的方法。九十年代初，随着一些新的公司加入 a f i s 商业化的竞争者行列，开始在a f i s 中引入自适应神经网络技术，同时小波变 换理论也被应用到a f i s 中，不过应用重点主要在指纹图像压缩方面。 本章我们主要讨论了指纹图像预处理的经典方法，并提出了改进后的方法。在 指纹图像细化方面，我们尝试推出了一项新的方法，并获得了相当满意的效果。 3 2 指纹图像的增强及其算法改进 指纹图像的增强技术分空域和频域( 主要是f o u r i e r 变换) 两类。 3 2 1 空域增强技术 南京理工大学硕士学位论文 a f i s 的算法研究及其设计与实现 术语“空域”是指组成图像像素的集合体，空域法是直接作用于这些像素的方 法。空域处理函数可表示为 g ( x ，y ) = h f ( x ，y ) 式中f ( x ，y ) 是输入图像，g ( x ，y ) 是所得到的图像。定义在( x ，y ) 某个邻域的h 是作用在f 上的一个算子，它也能作用于一串输入图像。 图3 2 1 1 图像中( x ，y ) 点的3 3 邻域 一l - 1 1 一l 8一l 一1一l l 图3 2 1 2 检测出不同与常量背景 的孤立点的掩模 一种常用于增强和复原的空域技术建立在应用所谓褶积掩模( 也可称样板、窗 口或滤波器) 的基础上。一个掩模基本上可为一个小的二维数组( 例3 3 ) ，如图 3 2 l1 所示的那样，选择它的系数以检测一幅图像的已知特性。为了引入这个概 念，假定我们有一幅强度为常量的图像，图像中有许多强度不同于背景的孤立点。 可用图2 所示的掩模将这些点检测出。其过程如下：掩模的中心( 标值为8 ) 围绕 着图像移动。在图像的每个像素位置上，将包含在掩模内的每个像素乘上相应的掩 模系数，即掩模中心的像素值乘8 ，其相邻的8 个像为零。相反，如果掩模中心位 于孤立点中的某一点，其和将不为零。如果孤立点在掩模的非中心位置，其和电不 为零，但响应值将弱一点。通过和值同门限值的比较可消除这些较弱的响应。如图 3 2 1 3 所示，于一个点( x ，y ) 的3 3 邻域，如果我们设w 1 ，w 殳，w 9 代表掩模 的系数，并研究点( x ，y ) 的8 个相邻值，我们可将先前的讨论归纳为执行下面的运 算： h f ( x ，y ) = w 。，g 一1 ，y 一1 ) + w 2 ，b l ，y ) + w ，g 一1 ，y + 1 + w , f ( x ，y 1 ) + w 5 ，0 ，y 卜w 6 f ( x ，y + 1 卜 w ，( x + 1 ，y 1 ) + w 。，0 1 ，y ) + w o f ( x + l ，y 十1 ) 州 w 2鹕 6 t , y - 1 )( x - 1 , y )* l ，y + d w 4v v 5 荫 仉p 1 )似” 伍y + 1 ) 订、帕 田 针l 一)o 件1 y )针l ，+ d 图3 2 ，1 3 一个通用的表示掩模系数 和相关图像像素的3 3 模板 这种处理形式要比上述讨论的点的检测要有力得多。例如邻域处理可以被用来 降低噪声。获得可变的图像门限、计算特征量度和获得一个物体的轮廓等。 3 2 1 1 直方图均衡化 南京理工大学硕士学位论文 第1 2 页 a f i s 的算法研究及其设计与实现 直方图均衡化是指将原图的直方图通过变换函数修整为均匀的直方图，然后按 均衡直方图修整原图像。 在离散情况下，直方图仅能接近于概率密度函数，很少能在均衡后获得完全平 直的直方图。 直方图均衡实质上是减少图像的灰度等级以换取对比度的扩大。由于在均衡化 过程中，原直方图上频数较小的灰度级被并入少数几个或一个灰度级中，对应的图 像部分得不到增强。若这些灰度级所构成的图像细节较重要，则以采用局部自适应 的直方图均衡化较适宜，简称为l a h e ( l o c a la d a p t i v eh i s t o g r a m e q u a l iz a t i o r ) 。本法用个滑动窗口，先计算该窗口的直方图，再对这个局部直 方图进行均衡以实现对窗口中心像素灰度级的修整。窗口从左至右和从上而下移 动，完成对整幅图像灰度的修整。选用的窗口可为方形或矩形，也可为圆形或椭圆 形，窗口大小可变，在进行直方图运算时，可计及窗口内所有像素，电可仅取水 平、垂直及对角方向的像素。图3 2 1 1 显示l a h e 对指纹图像应用的实例。其中， 图a 为原图像、图b 为l a h e 后的图像。 ( a ) 3 2 1 2 直方圈规定化 图3 2 11 l a t h e 实例 ( b ) 有时人们希望增强后的图像，其灰度级的分布不是均匀的，而是具有规定形状 的直方图，这样可突出感兴趣的灰度范围。对此，可用直方图规定化来实现。 先以连续分布情况为例。设p r 为原图像的灰度函数。p z ( z ) 为希望得到的增强 图像的灰度密度函数。它们各自的直方图分别如图3 2 1 2 1 ( a ) 、( c ) 所示。 如果对p r 和p z ( z ) 分别用下式： = r k ) = p ，“) = ”，加 r = o j = o 其中n 表示一幅图像总像素、表示第k 个灰度级吒出现的频数。 作直方图均衡化处理，则可得 s = r p ) = ip d r ， o = r ( = 1 m v = g 0 ) = i ( z ， o 2 z 2 1 经过上述变换后的灰度s 及v ，其密度函数是相同的，如图3 2 ，i 2 1 ( d ) 所 示。通过以直方图均衡化作跳板，进而可实现从p r 到p z ( z ) 的转换，即实现直方图 规定化。 南京理工大学硕士学位论文 第1 3 页 a f i s 的算法研究及其设计与实现 首先，利用s = r p ) = f 只咖，o = r = l ，可将原图各点的灰度r 映射成s 。然后 根据s = v 及v = g ( ：) = 陋0 ) 出，o = z 0 时， 就有观察到的图像f ( x ，y ，t ) ，忽略其展开的泰勒级数的高次项时，则有： g ( x ，y ) = i ( x ，y ，o ) = ，g ，y ，f ) 一f 导= b ，y ，r ) 一础v2 ，o ，y ，r ) ， o f 其中，t 是扩散时间间隔的长度，对于数字图像，用差分代替l a p l a c e 算子。 则有： g ( i ，j ) = q f ( i ，j ) 一b f ( i + l ，j ) + f ( i 一1 ，j ) + f ( i ，j + 1 ) + f ( i ，j - 1 ) 式中a 、b 是根据图像类别在实验中确定，且有 a = 1 + 4 kt ，b = kt 根据指纹图像的特点，可用3 3 ，5 5 ，7 7 模板求差分。一般对于2 5 6 x 2 5 6 的指纹图，采用3 3 或5 5 模板就可获得较好的效果。如果采用9 x g 模板， 就可能会在处理一条指纹纹线上的点时跨到另一条纹线上去取信息，造成处理不 当。 指纹图像上的噪声是随机的，因其空间的不相干性，含有较高的空间频谱， 多表现为点状结构，主要影响为纹线上的孔洞及边缘模糊。由于指纹纹线的方向性 很强，在局部区域中，噪声的影响多呈现在纹线流向的方向上，因此，可利用中值 定向滤波去除部分噪声。 由空域的处理公式知： m + l 一】 十，一l 4 g ( m ，n ) = i ( i ，办h ( m i + l ，n 一+ 7 ) 一月 其中m = 1 ，2 ，m ，n = 1 ，2 ，n m7 = m l ，n = n l 南京理i 大学硕士学位论文第1 8 页 a f i s 的算法研究及其设计与实现 若令输入图像阵f 为n x n ，卷积阵h = l x l ，输出阵g 为m m ，则有芡系 式：g ( m ，m ：) = ，0 ，n ：) 叮( m ，一”+ 1 ，m ：一+ 1 ) 为平滑噪声，卷积阵h 须呈低通型。 令f ( x ，y ) 为原始含噪音图像 如( i ，) = 吉，o ，j ) 式中，s 为所定义的滤波窗口，w n m 为n x l l l 窗口的权值，m 为s 中加权的像素 数目，f a v g 为窗口的平均灰度。由于中值滤波可保持边缘信息，故若需要，可重复 进行。 平滑处理的方法通常可选用加权平均法，邻域平均法，定向滤波法。一般取局 部处理，噪声与周围邻近点往往有区别，从图像中取一个区域包含有g 个像素点， 如果中间一点与周围各点很不相同，那么中间一点就是噪声，如果中间一点与周围 点差不多，则就是信息。设立一阈值，把中间一点的灰度与这个区域的平均值相 减，若相差的结果高于闽值，就是噪音，用平均灰度米取代这一点，小于闽值即为 信息，这一点保持原状。 实现二维的平滑滤波，区域一般采用3 3 窗口，用这种方法对图像的四边e 的各点与其周围点进行b p , 较时就缺少一行，这时可用插入法在四边增加一行。 若i 厂b ，y ) 一l ，。g ，y 1 ，为闽值，这时，就用f a v g ( x ，y ) 取代f ( x ，y ) ，否 则，不变。本文所采用的w n m 模板如下： h 2 击良塞：a ：1 3= - ：瞄a 2 乏a 1 2 喜f = 悟羔x 0 暇= ；良乏a 1 2 嚣1 钳0q 0 3 |睨= 粘9 0 0 00 0 1 = i x 睨= i o x 3 i 口3 2 = ；陪；曼= ；搭：誊l 实验结果表明，当指纹图像上噪声的分布比较均匀时，可以采用模板彬，滤波 效果很明显，当指纹图像上某一方向的干扰噪音较严重时，可采用定向滤波的方 法，根据具体的情况，可分别考虑垂直、水平、左斜、右斜四个方向，由于指纹纹 线流向在不同的区域可能有不同的方向，因此，定向滤波的选择可以在局部区域进 行，同一幅图像上也可以在不同的区域选择不同方向滤波。需要指出的是，一般在 图像平滑处理后，会损失一部分边缘信息，造成边缘清晰度下降，因而常在平滑处 理之后，再进行适当的锐化处理。但由于指纹本身的特点及选用平滑算法模板时考 虑了尽量减少边缘信息损失，另外也主要考虑了以后的细化处理，只保留了纹线形 状一即纹线中心线，故锐化处理在这里省去，并不会影响到以后的处理。 南京理工大学硕士学位论文 第1 9 页 a f i s 的算法研究及其设计与实现 3 3 指纹图像二值化的算法研究及其改进 从图像设备输出的指纹数字图像是二维的离散的扶度函数，一一般情况下，为减 少数字图像重现与处理时的失真程度，较精细的量化级是必须的，这就造成了图像 数据量较大，由于指纹图像的特殊性，可以把它看成是黑白相间的纹线所组成。这 样，只需二个量化级就能反映图像本质了。所以，对原始的或平滑过的数字指纹陶 像进行二值化处理，既保留了绝大部分有用信息，又大大压缩了数据量，节省了存 贮空间，加快了处理速度，简化了其后的处理方法。阈值处理算法是产生二值图像 的最基本方法，在较为复杂的模式中，一个固定不变的阈值并不能给出满意的二值 化的效果。此时采用局部闽值方法比较适宜，所谓局部阈值方法即根据某一图像区 域来确定适合于该区域阈值的方法。 我们采用5 5 模板进行局部二值化处理，令 r 0 ，) = 去巾，) j6j i s ，i e s ， 则 占：让0 掣玎( 力 l u 头匕 f ( i ，j ) 为经过前面平滑及锐化后所得图像，g ( x ，y ) 为所得二值图像。图像 二值化以后，由于图像存在边缘噪声或中间孔洞而导致细化失真，所以需进行必要 的修饰处理。 修饰处理的要求： l 、去掉纹线边缘及图像上孤立的点。 2 、 去掉纹线边缘的噪声。 3 、填补孤立的洞或纹线由于干扰产生的缺口。 4 、 连接由于干扰在纹线上产生的断裂或间隙。 具体的处理过程是在3 3 算法模块上进行的。 3 3 1 平滑处理 根据对指纹纹线走向规律的分析及m a l l e s w a r a