（信号与信息处理专业论文）基于mmx技术的指纹图像并行处理算法.pdf

大连理工大学硕士学位论文 摘要 由于指纹的唯一陛和不变性，以及指纹识别技术的实用性和可行性，指纹识别已成 为最流行、最方便和最可靠的身份认证方式之一，在当前社会生活的诸多方面得到了广 泛应用。随着社会的发展，人们对指纹识别系统的性能也提出了更高的要求，准确、快 速的指纹识别系统依然是个很困难的研究任务。 m 技术是专门为多媒体和通信应用而开发的，它是对i n t e l 体系结构的最重要的 加强。蛐慨技术增加了5 7 条新指令、8 个新的6 4 位数据寄存器和4 种新的数据类 型，它提供了一种单指令多数据( s m 皿) 的并行处理机制即在一条指令中并行地处理2 个、4 个甚至8 个数据，这种并行操作可以几倍地提高对数据的处理效率。当在指纹图 像处理中转用m m x 优化的代码时，能在保持与原有算法处理结果相同的同时，大幅度 提高处理速度。 本论文对指纹识别系统中的预处理和特征提取部分做了深入的研究，并提出了若干 基于m m x 技术的并行处理算法： ( 1 ) 在求方向图过程中，本文提出了一种基于m m x 技术的方向图并行计算算法，该 算法先对梯度和方向图公式做合理的变换，然后利用m m x 技术进行4 并行的计算。 ( 2 ) 在对指纹图像进行动态阈值二值化时，针对原二值化算法运算量大的特点，本文 提出了一种改进的动态阀值二值化方法，该算法通过对指纹方向进行量化，减少了大量 的重复操作。 ( 3 ) 在细化过程中，本文提出了一种基于m m x 技术的指纹图像并行细化算法，该算 法能够完成一个前景点的4 x 4 邻域与4 个模板的并行匹配操作。 ( 4 ) 在特征提取方面，本文提出了一种基于m m x 技术的计算交叉数和8 邻域纹线 点数的并行算法。在后处理过程中，本文利用纹线跟踪的结果，总结出几种典型伪特征 结构的特征，进而对其进行识别和滤除，达到滤除伪特征点的目的。 对论文中提到的所有算法，本文均进行了模拟实验。实验结果表明，本文提出的新 算法能在保持与原有算法处理结果相同的同时，运算速度得到明显提高。 关键词：a 彻( 技术；指纹识别；并行处理；方向图；二值化；细化；特征提取 后处理 基于m m x 技术的指纹图像并行处理算法 f i n g e r p r i n ti m a g e sp a r a l l e lp r o c e s s i n ga l g o r i t h m s b a s e do nm m x t e c h n o l o g y b e c a u s eo f u n i q u e n e s sa n di n v a r i a b i l i t y , t h ef i n g e r p r i n ti d e n t i f i c a t i o ni sb e c o m i n g o n eo f t h em o s t p o p u l a rp e r s o n a la u t h e n t i c a t i o nt e c h n o l o g i e s ，a n di th a sb e e nu s e di nm a n yr e g i o n s w i mt h e d e v e l o p m e n t o ft h e s o c i e t y p e o p l e d e m a n df o r h i g h e rp e r f o r m a n c e o ft h e i d e n t i f i c a t i o ns y s t e m ，s oa ne x a c ta n df a s tf 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 mi ss t i l lad i f f i c u l t r e s e a r c h s u b j e c t m m x t e c h n o l o g yi sd e v e l o p e df o rm u l t i m e d i aa n dc o m m u n i c a t i o na p p l i c a t i o n s , i ti sa n e n h a n c e m e n to fi n t e la r c h i t e c t u r e t h et e c h n o l o g ya d d st i f f ：y - s e v e nn e wi n s t r u c t i o n s ，e i g h t r e g i s t e r so fs i x t y - f o u rb i t sa n df o u rk i n d so fd a t at y p e s ，a n di t a f f o r d sap a r a l l e l o p e r a t i o n m e t h o do f s i m dt h a ta s i n g l ei n s t r u c t i o nd e a l st w o ，f o u ro re i g h td a t a , t h ep a r a l l e lo p e r a t i o n c a l l i m p r o v e t h ec o m p u t a t i o ne f f i c i e n c y w h e n u s i n gm m x c o d ei nf i n g e r p r i n ti m a g e s p r o c e s s i n g ， i tc a r lo b v i o u s l yi m p r o v et h ec o m p u t a t i o ns p e e dw i t ht h es a m er e s u l t s a f t e r s t u d y i n go np r e p r o c e s s i n g a n df e a t u r ee x t r a c t i o n o f f i n g e r p r i n ti m a g e s ，t h ep a p e r p r o p o s e ss o m e n e w p a r a l l e lp r o c e s s i n ga l g o r i t h m s b a s e do nm m x t e c h n o l o g y ： ( 1 ) w h e nc a l c u l a t i n gd i r e c t i o ni m a g e , ap a r a l l e lp r o c e s s i n ga l g o r i t h m sb a s e do nm m x t e c h n o l o g yi sp r o p o s e d , t h ea l g o r i t h mf i r s t l yi r a n s f o r m st h ef o r m u l aa n dt h e nu s e sm m x t e c h n o l o g y t 0c a l c u l a t ei na f o u r - p a r a l l e lw a y ( 2 ) w h e nb i n a r i z a f i o n , t h ep a p e rq u a n t i t a t e sd i r e c t i o ni no r d e rt or e d u c em a n yr e p e a t i n g c a l c u l a t i o i l s ( 3 ) i nt h ep r o c e s so ft h i n n i n g , ap a r a l l e lt h i n n i n ga l g o r i t h mb a s e do nm m xt e c h n o l o g yi s p r o p o s e d ，i t u s e s m m x t os y n c h r o n o u s l y c o m p a r e t h e n e i g h b o u r s o f 4 x 4 w i t h f o u r t e m p l a t e s ( 4 ) i nt h ea s p e c to f f e a t u r ee x t r a c t i o n ，t h ep a p e re s t i m a t e sf e a t u r eb yc a l c u l a t i n ga c r o s s n u m b e ra n d8 - n e i g h b o u r r i d g ep o i n tn u m b e rw i t hm m xt e c h n o l o g y i nt h ep o s t - p r o c e s s i n g ，t h e p a p e r i d e n t i f i e sa n de l i m i n a t e ss o m e t y p i c a l f a l s ef e a t u r es t r u c t u r e s s i m u l a t i o n e x p e r i m e n t s h a v eb e e nm a d ef o ra l lo l da n dn e w a j 9 0 6 t h m s r e s u l t ss h o w t h a t a l ln e w a l g o r i t h m sg i v e n i nt h i sp a p e rc a n s i g n i f i c a n t l yi m p r o v e t h ec o m p u t a t i o n e f f i c i e n c y w i t h t h es a m er c s u l t s k e y w o r d s ：m m xt e c h n o l o g y ：f i n g e r p r i n t i d e n t i f i c a t i 0 1 1 ：p a r a ii e l p r o c e s s n g ： d ir e o t i o n i m a g e ；b i n a r i z a t i o n ；t h in n in g ；f e a t u r ee x t r a c t i o n ：p o s t - p r o c e s s i n g 独创性说明 作者郑重声明：本硕上学位论文是我个人在导帅指导卜- 进行的研究 工作及取得研究成果。尽我所知，除了文l + j 特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我- 同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名： 旋纽垒日期：迹堡主旦垡 大连理工大学硕士学位论文 1 绪论 1 1m m x 技术简介 随着声音、图像、视频及通信等多媒体技术在个人计算机平台上的应用日趋普及， p c 处理数据的数量及复杂性迅速膨胀，微处理器承受着前所未有的压力。要更好的满 足广大用户对多媒体数据处理日益增长的需求，单纯依靠提高c p u 的速度( 提高c p u 时钟频率，优化c p u 的执行部件和流水线) 和增加插件插卡等传统手段已呈现出某种 程度的苍白与贫乏，p c 平台的微处理器必须提出满足多媒体数据处理的解决方案。鉴 于上述理由，作为全球c p u 芯片主要供应商的i n t e t 公司于1 9 9 7 年初适时推出了m m x ( m u l t i m e d i ae x t e n s i o n ，多媒体扩展) 技术。在早期的i n t e l 体系结构中，当8 0 8 8 8 0 8 6 仅 能处理8 位和1 6 位数据时，8 0 8 7 就能够处理直到6 4 位的复杂得多的数据类型，以及 在8 0 8 7 寄存器与内存之间传送直到8 0 位的数据类型，这些特点对m m x 技术的引入很 重要。 m m x 技术 1 】是对i n t e l 体系结构的最重要的加强，它在p e n t i u m 芯片技术基础上增 加了5 7 条新指令、8 个新的“位数据寄存器和4 种新的数据类型。m m x 技术新增的 5 7 条指令由单指令多数据( s i n g l ei n s t r u c t i o nm u l t i p l ed a t a ，s n v t d ) 技术来展现出其在多 媒体及通信方面的应用。简单地说，s i m d 技术主要是让每一条指令可并行地在多项数 据中运作。采用m m x 技术的处理器拥有充分的能力加速多媒体及通信应用程序的运 行，可在执行有大量计算的通信及多媒体任务的同时腾出足够的余地来执行其他任务和 应用程序。m m x 技术一方面采用众多多媒体及通信算法中固有的并行机制，同时它并 不增加额外的寄存器硬件和处理器状态，以保持与现有操作系统及应用程序的完全兼 容，从而使应用程序获得更高水平的性能。 通过对目前多媒体和数据通信软件中大量计算密集型程序的分析知，这些程序在整 个软件系统中的代码量不足1 0 ，但占其系统运行的9 0 的计算时间【2 】，这部分程序 代码通常具有如下特征： ( a ) 比较短的整型数据变量( 如1 6 位音频数据、8 位图像数据) ； 蚴小面频繁的循环( 如d c t 、f f d ； ( c ) 大量的加、乘和累加( 立口f i r 滤波、矩阵运算) ； ( d ) 可以高度并行执行( 如图像处理) ： ( e ) 计算量庞大 n - - 维图形、视频压缩) 。 基于m m x 技术的指纹图像并行处理算法 针对上述特点，m m x 技术被设计为一套与原浮点硬件体系结构兼容的基本的通用 的整数指令，它可简便的应用于各种多媒体及通信应用程序。 m m x 技术的定义非常简单，它包含以下技术要点： ( 一) 新的数据类型 m m x 指令系统主要的数据类型是紧缩的定点整数，而多个整数字被紧缩成一个单 一的6 4 位数并被移入6 4 位m m x 寄存器。m m x 技术所支持的数据类型为带符号和未 带符号的定点整数：字节、字、双字及四字。 m m x 技术的4 种数据类型为： ( 1 ) 紧缩字节：八个字节紧缩为一个6 4 位的数，其中各字节相互独立； ( 2 ) 紧缩字：四个1 6 位的字紧缩为一个6 4 位的数，4 个字相互独立，这是m m x 技术最核心的数据类型； ( 3 ) 紧缩双字：两个3 2 位的双字紧缩为一个6 4 位的数，这2 个双字相互独立； ( 4 1 四字；一个“位的数。 ( 二) m m x 寄存器 m m x 指令体系中新增了8 个“位宽的m m x 寄存器，其编号为m m 0 - 一m m 7 ，这8 个寄存器利用的就是现有的x 8 6c p u 内8 个通用浮点f f p ) 寄存器中的低6 4 位。与x 8 6 的通用寄存器不同，m m x 寄存器仅能作为数据寄存器而不能作为地址寄存器。这8 个 6 4 位寄存器支持新增的4 种数据类型，汇编程序员可根据不同的m m x 指令把寄存器 中的6 4 位数据视为彼此无关的8 个字节、4 个字、2 个双字或1 个6 4 位数据。m m x 指令的两个操作对象是在1 6 个字节、8 个字、4 个双字或2 个6 4 位数据间成双对应的 运算操作。正是在此基础上，m m x 技术体现出其s i m d 特征即在一条指令中同时处理 2 个、4 个甚至8 个数据，这种并行操作可加快多媒体和通信应用的某些大计算量的循 环的速度。 ( 三) m m x 指令 m m x 技术提供了新的5 7 条操作码，它们是为紧缩数据的高速算术、逻辑、比较 操作而设计的，主要涉及到以下几个功能领域： ( 1 ) 算术指令：加、减、乘和乘加； ( 2 ) 比较指令：比较指令按照相等或大于的要求分别比较两操作数中的各个相关数 据元素，根据比较结果产生全l 或全0 的屏蔽位： ( 3 ) 转换指令：转换指令用于紧缩数据类型间的转抉操作； ( 4 ) 逻辑十旨令：逻辑指令对6 4 位数据进行按位逻辑操作； 一2 大连理工大学硕士学位论文 ( 5 ) 移位指令：逻辑右移、逻辑左移和算术右移指令对每个数据元素进行一定位数 的移位操作； ( 6 ) 数据传送指令：数据传送指令用于m m x 寄存器之间的数据转移或者m m x 寄 存器与内存之间的“位或3 2 位数据的存取； ( 7 ) e m m s ：e m m s 指令负责清空m m x 状态。 m m x 技术支持一种新的算法一饱和算法，它与传统的环绕算法形成鲜明的对比。在 传统的环绕模式中，上溢或下溢的结果被截去，只有结果的低位才返回，进位被忽略。在 饱和模式中，上溢或下溢的结果被饱和成数据类型的最大或最小值。例如对于8 位的像 素数据，0 表示黑，2 5 5 表示白。当运算结果超过2 5 5 时，如在环绕模式下，返回结果将变 成o ，因而将黑自颠倒。而使用饱和运算，将使该值为2 5 5 ，因而误差不大。可看出饱和算 法特别适合色彩计算，反映了多媒体处理的实际情况，同时也减少了由于溢出判断、处 理所进行的内部操作，加快了运算速度。 m m x 技术可满足建立在当前和未来算法上的p c 应用程序的大部分需求，其技术 基础为s i m d 技术，即由一条单一指令并行地处理许多条信息，这种并行操作大幅度提 高了c p u 性能。在目前的多媒体、通信等应用程序中均含有能够对短数据类型实现循 环操作的复杂算法，而m m x 指令可并行地对多个紧缩在6 4 位寄存器中的不同类型整 型数据进行算术运算或逻辑运算。例如，一幅采集到的2 5 6 色灰度指纹图像象素数据通 常表现为8 位的整数，当使用m m x 技术时，8 个相邻的象素数据被紧缩成一个6 4 位 的数，并被移入一个m v i x 寄存器，这6 4 位长的紧缩型数据不能看成为一个完整的连 续的“位数，8 个字节相互独立。执行m m x 指令时，它将所有8 个象素数据共6 4 位 从m m x 寄存器一次性取出，并行地对这8 个值进行数学或逻辑操作，最后将结果写入 m m x 寄存器。几乎所有依靠重复和循环方式对小整数数据进行的运算都能从m m x 技 术中获益。 7 下面我们以计算向量点积z = a 。+ q ( 所有各因数均为1 6 位) 为例来说明m m x 技 丽 术的优势： p m a d d w d 紧缩字乘法累加指令分别将两寄存器中8 个16 位数据对应相乘，产生4 个3 2 位的结果，并把左边的2 个乘积加在一起作为一个结果，同时把右边的2 个乘积 加在起作为另一个结果。 p a d d d 指令完成在环绕模式下两对有符号3 2 位数据的加操作。 p s r l d 指令完成逻辑右移操作。 一3 基于h 岱仪技术的指纹图像并行处理算法 7 合理应用这些指令，可以完成x = 口。+ c 。这样的向量计算，应用m 正x 指令的计 i = 0 算过程如图1 1 所示： 一曲de 耳i 习 酬如de 耳工毋 卫 碉 工 珂 匣亟主画叵亟主童立圈 叵亟互巨囹 p a d d d4 -+ 一 巨亟三巨至圈 p a d d d 忙：麓刊：冀j 了f i 呜。qi 丑时1 7 ，l p s r l d 二图 图1 1 杰n * c i 的计算过程 f 培1 1f l o wd i a g r a mo f av e c t o rd o tp r o d u c t 应用h m d ( 指令和传统的x 8 6 处理器指令计算杰a i * e i 所用指令数见表1 1 ，从表 中可以看出，该向量计算仅需两次乘法( p m a d d w d 指+ ) 和两次加法( p a d d d 指令) 及 其它几条指令配合即可完成；若使用现有的x 8 6 系处理器的指令，需进行1 6 次载入、8 次乘法、7 次加法并进行8 次移位，共需使用4 0 条指令。使用 岱技术后仅需原来 三分之一的指令，并且大部分h m 指令在个时钟周期内完成，因而m 0 正x 技术的优 - 4 霾 大连理工大学硕士学位论文 势更为突出，在多媒体及通信算法中，应用m m x 技术后能达到不应用m m x 技术的速度的 1 5 到2 倍 3 。 表1 1 两种方法使用指令数比较 t a b l e1 1i n s w l l c t i o nc o m p a r i s o no f t w o a l g o r i t h m s 1 2 生物识别与指纹识别技术简介 从古到今，身份识别一直是人类的一种重要需求。人们为了保护自身财产、信息等 的安全，使用各种办法来识别目标人物的身份，从而给予不同的授权。然而传统的身份 识别技术只是对密码或者某种介质( 如钥匙、证件等 的认证，由于主要是借助体外 物，无论使用多长的密码或者任何一种介质，一旦被盗或遗忘，其身份就容易被他人冒 充或取代。如何准确鉴定身份，保证财产和信息的安全昵? 信用卡号、银行帐号、网络 登陆号，生活中需要记忆的密码越来越多。如何不用记忆这些密码而又不用担心自己身 份无法认定呢? 正在悄然兴起的生物识别技术正好可以解决上述问题。 生物识别技术是指利用人体生物特征进行身份认证的种技术 4 】，生物特征是指唯 的、可测量或可自动识别的生理特征或行为特征，它具有“人人不同，相对不变，随 身携带”的特点。生理特征多为先天性的，如指纹、眼睛虹膜、脸像等；行为特征则多 为后天性的，如笔迹、步态等。生物识别系统通过对生物特征进行取样，提取其唯一的 特征并且转化成数字代码，然后将这些代码组成特征模板。人们同识别系统进行交互 时，系统获取其特征并与数据库中的特征模板进行比对，以确定是否匹配，从而决定接 受或拒绝该人。生物识别技术是目前最为方便与安全的识别技术，它不再需要人们记住 复杂的密码，也不需随身携带钥匙、证件之类的东西，它认定的是人本身。 理论上，只要满足下面的条件，人的任何生理特征或行为特征都可以用作身份识别 5 ：( 1 ) 普遍性，即每个人都拥有该特征；( 2 ) 唯一陛，即没有哪两个人拥有同样的 该特征：( 3 ) 永久性，即该特征不会随时间而变化； ( 4 ) 可采集性，即该特征能够被 定量地测量出来；( 5 ) 易实现性，即容易实现，包括资源消耗少，工作环境要求不苛 刻： ( 6 ) 可接受性，即人们乐意接受这种识别方式；( 7 ) 难欺骗性，即冒充者很难通 过提供假特征欺骗识别系统。 5 基于m m x 技术的指纹图像并行处理算法 基于这些特征，人们已经发展了手形识别、指纹识别、面部识别、语音识别、虹膜 识别、签名识别等多种生物识别技术。相对于其它生物识别技术，例如语音识别及视网 膜识别等，指纹识别是一种更为理想的身份确认技术，原因如下： ( 1 ) 唯一胜：指纹是独一无二的，两人之间不存在着相同的指纹，即使是同一个 人不同手指的指纹，纹线走向及纹线的断点和交叉点等各不相同； ( 2 ) 稳定性：指纹是相当固定的，很难再发生变化，比如它不会随年龄、健康状 况的变化而变化，是终生不变的； ( 3 ) 可行眭：指纹样本可通过一定的设备和手段采集到，易于开发识别系统： ( 4 ) 安全性：每个人十指的指纹皆不相同，可以利用多个指纹构成多重口令，提 高系统的安全性： ( 5 ) 实用性：指纹识别中使用的模板并非最初的指纹图像，而是由图像提取的关 键特征，所需存储的信息量小，而且在实现异地确认时，可以大大减少网络传输负担， 支持网络功能。 可以看出，指纹识别技术相对于其他生物识别方法有许多独到之处，具有很高的实 用性和可行性。近年来，国内外学者对指纹识别技术进行了深入和广泛的研究，取得了 较大的进展，其研究的重点主要集中在如何提高识别率和速度。目前，指纹识别已成为 最流行、最方便、最可靠的身份认证方式之一，已被广泛应用到社会生活的许多领域如 公安、门禁、企业考勤等。随着数字化、信息化程度的不断提高，人们对指纹识别系统 的性能提出了更高的要求。快速、准确的指纹识别系统仍然是一个很困难的研究任务。 1 3 指纹识别系统的构成 一个优秀的指纹识别系统要求能快速、准确地完成其识别过程。一般来讲，指纹识 别系统包括如下几个处理过程：指纹图像输入、预处理、特征提取、特征分类与特征匹 配等，该系统的流程框图如图1 2 所示： 一6 一 大连理工大学硕士学位论文 图1 2 自动指纹识别系统 f i g 1 2a 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 i o ns y s t e m 下面对图1 2 所示自动指纹识别系统的各个部分做简单介绍。 ( 1 ) 图像输入 将一个人的指纹采集下来输入到计算机是进行指纹识别的首要步骤，传统的指纹 采集方法是用手指蘸上墨水或印油在纸上按压，然后用扫描仪摄取。由于这种方法费时 较长且不可靠，该方法已经被淘汰。另一种方法是利用光的反射特性来获得指纹图像， 该方法陕速有效，宜于实时操作。 本文试验所使用的是d i g i t a lp e r s o n a 公司的 u a r e u2 0 0 0 指纹扫描器，外形如图1 3 所 示。该扫描器能够自动读取指纹图像，并通过 u s b 接口把数字化的图像传送到计算机。对于需 要进行身份验证的膝上型电脑、桌面计算机或其 他的个人电脑装置，它是很理想的配件。它集成 精密光学系统、l e d 光源和c m o s 摄像头协同 工作，在图像摄取时进行电压控制、自动矫正， 并使用即插即用的u s b 接口。 7 图1 3 指纹扫描器 f i g 1 3f i n g e r p r i n ts c r l l l l e r 基于i v l m x 技术的指纹图像并行处理算法 ( 2 ) 预处理 通常经指纹扫描器采集的原始指纹图像不可避免地具有对比度不统一、含有大量噪 声等缺点，我们需要去除这些噪声才能正确地进行特征提取、分类、匹配等操作，因而 预处理在整个自动指纹识别系统中是很关键的第一步。 由于特征提取的方法不同，所采用的预处理方法也有所不同。目前，从大的方面 分，主要有两种特征提取方法：一种是直接从原指纹图像中提取统计性特征，它对预处 理要求比较少，只要将图像增强一下就可以：一种是从预处理后的细化二值图像中提取 细节点特征，这种方法对预处理的要求比较高。 ( 3 ) 特征提取 美国国家标准局提出了用于鉴定指纹的四种细节特征：端点、分歧点、交叉和不确 定。目前大部分指纹识别系统使用的细节特征都是美国联邦调查局( f b i ) 提出的细节 点匹配模型 6 ，它利用末梢点与分支点( 如图1 4 所示) 这两种特征来鉴定指纹。末梢点 指的是纹线突然结束的位置如图1 4 ( a ) 所示，分叉点是指纹线一分为二的位置如图 1 4 ( a ) 所示。大量的统计结果表明，使用这两类特征点就足以描述指纹的唯一性。 ( a ) 末梢点分支点 图1 4 末梢点和分支点 f i g 1 4m d g ee n d i n ga n db i f u r c a t i o n 特征提取负责给指纹图像的特征点赋予一些参数、标记，使得用这些参数、标记能 把每一个指纹唯一地区别开来。在实际过程中，由于指纹输入时外界因素的影响以及预 处理不完全都可能导致提取出的特征点中含有很多的伪特征点，为了提高指纹识别系统 的识别率，要求在特征提取后进行后处理来识别和滤除这些虚假特征。 ( 4 ) 指纹分类 在一些大型的指纹系统中，输入的指纹要与几万、甚至上千万个指纹进行匹配。为 了减少搜索时间、降低计算的复杂性，需要将指纹以一种精确且一致的方式分配到每个 指纹子库中。这样，输入的指纹只需要跟子库中的指纹相匹配就可以了。指纹分类技术 8 大连理工大学硕士学位论文 越完善，能够划分的类型越细，样本数据库每个类别中所包含的样本数量就会越少，对 一次识别任务来讲，需要比对的次数和时间开销就会越少。 指纹分类被认为是指纹匹配的初级阶段。在大部分研究中，指纹一般分为5 类：漩 涡型( w h o r l ) 、左环型( 1 e f tl o o p ) 、右环型( r i g h tl o o p ) 、拱型( a r c h ) 、尖拱型 ( t e n t e da r c h ) 。 ( 5 ) 指纹匹配 指纹匹配是用当前输入的指纹特征与事先保存的模板特征相比对，从而判断这两个 指纹特征是否来源于同一个手指。英国学者e r h e r r y 认为，只要两枚指纹有1 2 1 3 个 特征点重合，就可以确认为是同一个指纹。但是由于采集过程中的变形、特征点定位的 偏差、真正特征点的缺失和伪特征点的存在等问题，即使是两枚同源的指纹，所获得的 特征信息也不可能完全一样，因而指纹匹配的过程必然是一个模糊匹配问题。因而，识 别的结果也不可能保证i 0 0 的准确。指纹识别系统的重要衡量标志是识别率，它主要 由两部分组成：拒判率( f a l s er e j e c tr a t e ，f r r ) 和误判率( f a l s ea c c e p tr a t e ， f a r ) ，可以用1 0 的数或百分比来表达这两个数。f r r 和f a r 是互相矛盾的，我们 可以根据不同的用途来调整这两个值。图1 _ 5 所示的r o c ( r e c e i v e ro p e r a e 珥c u r v e ) 一曲 线给出了f a r 和f r r 之间的关系。 1 8 1 6 1 垂 岛1 2 三1 0 石8 芒6 士 2 0 图1 5 据判率和误判率关系曲线 f i g1 5r e l a t i o nc u r v eo f f r ra n df a r 由于f r r 和f a r 是相互矛盾的，这就使得在实际应用系统的设计中，要权衡易用性 和安全性。一个有效的办法是比对两个或更多的指纹，从而在不损失易用性的同时，最 大限度地提高了系统的安全性。 9 一 基于m m x 技术的指纹图像并行处理算法 1 4 本文主要研究内容与结构安排 本文主要研究如何应用m m x 技术来进行指纹图像的并行处理。经过阅读大量 m m x 技术和指纹图像处理方面的文献资料，本文将m m x 技术应用到预处理和特征提 取部分并相应地提出了若干基于m m x 技术的并行处理算法，这些算法在w i n d o w s 平 台上用汇编语言和m m x 指令嵌入到v i s u a lc + + 6 0 中得以实现。 本文的结构安排如下： 第一章简单地介绍了雠技术、生物识别与指纹识别技术、指纹识别系统的构成。 第二章主要研究指纹图像预处理过程所包含的指纹图像分割、求块方向图、二值化 和细化算法，其中将详细阐述如何应用m m x 技术对块方向图、动态阈值二值化和细化 这些算法进行改进，给出实验结果并予以分析。 第三章主要研究特征提取及后处理过程，阐述了基于m m x 技术的特征提取并行算 法的设计与实现以及特征提取后，如何识别和滤除伪特征，给出实验结果并予以分析。 最后将对本文所做的工作进行总结。 1 0 一 大连理工大学硕士学位论文 2 指纹图像预处理算法及其基于m m x 技术的改进 2 1 引言 在指纹图像采集过程中，由于表面皮肤特性、采集条件以及成像传感器特征差异等 各种原因的影响，采集到的指纹图像是一幅含多种不同程度噪音干扰的灰度图像，指纹 脊线可能被断开、桥接或模糊等，这种噪化的指纹脊线结构严重影响着指纹识别系统的 性能。预处理的目的就是将输入的( 直接采集进来的) 低质量、有噪声的指纹原图像处理 成单象素宽度的二值图像，它是整个指纹识别系统的重要组成部分，它的结果将直接影 响特征提取和匹配的复杂度，关系到整个系统豹识别率。长期以来人们对指纹图像的预 处理做了大量的研究：l i nh o n g 等人提出的预处理方法分为三个步骤【7 ，首先求指纹 方向图，然后由方向图求频率图，最后用由此得到的g a b o r 滤波器对原图像进行滤波， 这种方法计算量比较大，而且求频率图时容易产生偏差；l a w r e n c e0 g o r m a n 等人提出 了一种专门针对指纹图像的滤波器 8 ，得到的滤波器具有脊线方向上的平滑性和其垂直 方向上的分离性，能够根据图像脊和谷的周期性、灰度变化规律来滤除原图像中的噪 声，其缺点在于计算的复杂性；b m m e h t r e 提出了一种上下文滤波器【9 ，它是一系列 上下文相关的滤波器组，使用时根据某一块的方向从滤波器组中选择个相应的滤波器 来对这块进行滤波。 本文采用从指纹的细化二值图像上进行特征提取的方法，因而它要求事先把原始灰 度指纹图像变换为纹线宽度为一个像素的二值图像。指纹图像预处理过程包括图像分 割、求方向图、二值化和细化这四个步骤，如图2 1 所示： 霍 万 二 细 翁 向 覆 图 化 图2 1 预处理框图 f i g 2 1t h ef l o w o f p r e p r o c e s s i n g 图像分割通过识别和割除指纹图像的背景区来大大减少后续步骤的计算量；方向图 是指纹原图像的一种变换表示方法，它描述了指纹图像中每一像素点所在脊线或谷线在 基于m m x 技术的指纹图像并行处理算法 该点的切线方向，作为一种可直接从原始灰度图像中得到的有用信息，它的计算是指纹 识别技术中必不可少的一步；二值化是从灰度指纹图像得n - - 值指纹图像，当对二值图 像作进一步处理时，图像的几何性质只与0 和1 的位置有关，不再涉及到象素点的灰度 值，使后续处理变得更简单更快速；细化就是抽取图像的骨架即将宽度大于一个象素的 纹线转变为一个象素宽的纹线的处理过程。经过这四个步骤的预处理就可以得到一幅细 化的二值图像，在这基础上我们就可以进行特征的提取工作。 2 2 指纹图像的简单分割 指纹图像经指纹扫描器采集后直接输入到计算机，由于在采集过程中按捺时用力不 均匀、扫描器镜片上有污垢等原因，所得图像的背景区往往含有深浅不均的噪声。同 时，指纹扫描器在图像采集以及数字化的过程中，由于量化精度及非线性特性等的影 响，也不可避免地引入噪声。如图2 2 所示，这是在实验过程中采集到的三幅指纹图 像。从图中可以看出，它们含有大量的背景噪声。如果不对其加以处理，会使得后续处 理变得更加复杂。 图2 2 原始指纹图像实例 f i g 2 2e x a m p l e so f o r i g i n a lf i n g e r p r i n ti m a g e 根据指纹图像被噪声干扰的程度及能否正确恢复，可把图像细分为4 类区域【1 0 ： ( 1 ) 白背景区：指不含纹线的边界区，该区域往往由于扫描器镜片污垢等原因而呈现深 浅不等的灰度；( 2 ) 前景区：指纹线清晰连续、几乎没有噪声干扰的区域；( 3 ) 背景 区：指噪声干扰严重、纹线无法辨认、很难恢复的区域；( 4 ) 模糊区：指纹线断续不清 晰、有噪声干扰、但不太严重的区域。指纹图像分割的目的就是割除白背景区和背景 区，保留前景区，尽可能保留模糊区中能恢复的部分。 1 2 大连理工大学硕士学位论文 本文采用一种比较简单的分割方法 11 来割除白背景区。它通过计算块灰度均值和 块灰度方差，然后与阈值进行比较来识别和割除指纹图像的背景区。 假设足，力代表指纹图像中( f ，力处盼灰度值，将图像分成大小为m m 的块，这里 m 的大小以包含一脊一谷( 即一周期) 为宜。通过以下方法来判别前景区与背景区： ( 1 ) 块灰度均值m e q n 。第，功块的均值计算方法如下： r f - 1 m 一1 m e a n = l f ( i + m m ，j + n x m ) l m ) ( 2 1 ) l t - 0j e oj ( 2 ) 块灰度方差v a r i a n c e 。第沏，z ) 块的方差计算方法如下： 广村一l 盯一1 v a r i a n 舭i ( 加+ 朋m ，j + n x m ) - m e a n ) 2j ( m m ) ( 2 2 ) l t = o - oj ( 33 设置合适的均值阈值t t 和方差阈值t 2 ，当m e a n t 1 且v a r i a n c e 1 0 ，小块大小为6 6 。在实验过程中，本文分 别使用基于文献 1 2 1 的算法和本文提出的算法来求图2 2 所示的三个指纹图像的块方向 图，两种算法求得的块方向图完全相同，为了把方向图直观地表示出来，我们把各块方 向近似到0 ，8 ，z 4 ，3j r 8 ，7 j 8 等8 个方向上，并用线段描绘出来。图2 7 所示为图2 2 中各指纹图像经分割后与其方向图叠加后的效果。可以看出，求得的方向 图比较平滑，能够正确地表达指纹纹线的走向。 ( a ) 拱形( b ) 环形( c ) 旋涡形 图2 7 指纹方向图实例 f i g 2 7e x a m p l e so f f i n g e r p r i n td i r e c t i o ni m a g e 表2 1 所示为两种算法计算6 幅不同指纹图像的块方向图所耗费的时间比较其中 单位为毫秒( m s ) e 从表2 。l 可以看出，本文改进算法的处理速度比原算法提高了将近2 倍。 表2 1 计算块方向的时间比较 t a b l e 2 1t i m e c o m p a r i s o n b e t w e e n t w o d i r e c t i o n a l g o r i t h m s 下面对原算法和本文新算法的计算复杂性进行具体分析 ( 1 ) 计算4 个q ( f ，_ ，) 2 1 基于m m x 技术的指纹图像并行处理算法 原算法：2 4 次读操作，8 次乘操作，8 次移位操作，2 0 次加操作，4 次存操 作； 本文新算法：8 次读操作，5 次加操作，3 次存操作。 ( 2 ) 计算4 个g ，( f ，) 原算法：2 4 次读操作，8 次乘操作，8 次移位操作，2 0 次加操作，4 次存操 作； 本文新算法：8 次读操作，5 次加操作，3 次存操作。 从上面的分析可以看出： 本文新算法计算g ；( f ，j ) 和g 。( f ，j ) 所需的指令数仅为原算法所需指令数的2 5 ，而 且原算法用到乘法指令，该指令花费的时间比加、减、移位等指令要多。 得到g ( f ，力和g ，( f ，) 后，新算法通过利用m m x 技术提供的积和指令充分体验它 的优越性。 2 4 改进的指纹图像二值化方法 二值化是指纹图像预处理中必不可少的一步。对灰度指纹图像进行二值化处理，一 方面当对二值图像作进一步处理时，图像的几何性质只与0 和l 的位置有关，不再涉及 到像素的灰度值，使处理变得简单、快捷。另一方面还可以去除大量的粘连，为后面的 特征提取和匹配作准备。在很多数字图像处理的应用中，二值化的图像也被广泛应用。 所谓图像的二值化是指通过设定阈值( t h r e s h o l d ) 把灰度图像变成仅用两个值分别 表示图像的目标和背景的二值图像。图像二值化可根据下列的阈值处理来进行： 删= 信毙鬻 c z z 。， 通常，用二值图像g ( i ，j ) 中的1 值部分表示目标子图，0 值部分表示背景子图。 2 4 1 固定阈值法与动态阈值法 二值化图像的方法很多，关键在于阈值的选择。阈值主要可以分为两类：全局阈值 和局部阈值【1 4 。全局阈值是对整个图像采用一个阈值进行划分，例如：非零像素置 “1 ”二值化、固定阈值二值化、判断分析二值化、基于灰度差直方图的阈值法等。局 部阈值是将图像分成一些子块，对于每一子块选定一个阈值，例如：动态阈值法。 固定阈值法 1 5 是指根据图像的先验知识，如假设文字图像中文字占全图的百分比 为p 9 6 ，试取系列的阈值t ，当使用某个t = t 0 时，其分割以后的图像中文字所占的比例 等于或接近p 时，那么就可以选定t o 为阈值。 2 2 大连理工大学硕士学位论文 动态闽值法先将图像分为若干个胛”的方块，对每一方块计算平均灰度值，然后 将方块中每个像素点的灰度值与平均灰度值进行比较，若大于平均灰度值，则将该像素 点灰度值置为2 5 5 ：反之则置为0 。分块的大小不同，其二值化处理结果也不同。 固定阈值法算法简单，但需要有图像的先验知识。对于指纹这种特殊的图像而言， 假设其目标子图和背景予图各占一半是符合实际情况的，但是该方法也有一定的局限 性，对于残缺或灰度不均匀的指纹图像，其处理效果不太理想，容易产生断线。动态阈 值法能根据图像的局部灰度自动选择合适的阈值，对原指纹灰度图要求较低，二值化效 果较好。 本文采用一种基于方向图的动态阈值二值化方法 1 2 1 ，这种方法将指纹图像自身的 方向结构特点与源图像灰度值变化特点结合起来，确定对图像中每一像素点二值化的动 态阈值。但是，该算法阈值的获得比较复杂，计算量较大，为此，本文对该算法做了一 些改进。 2 4 2 基于方向图的动态阈值二值化 指纹图像的局部如图2 8 ( a ) 所示： ( a ) 原始图像谷脊变化波形图 图2 8 指纹谷脊变化波形图 f i g ：2 8w a v e f o r mo f r i d g ea n dv a l l e y 方框y 方向是该块的纹线方向，x 方向是其法线方向。以法线方向上各像素点的灰 度值做一曲线，可得到近似于正弦的波形图，如图2 8 c o ) 所示。显然，该波形图的波谷 对应指纹图像的脊线点，而波峰则对应指纹图像的谷点。若所考察的当前像素点恰好落 在波谷上，则该点就是指纹脊线点：若所考察的当前像素点恰好落在波峰上，则该点就 是指纹谷点。谷点