（信号与信息处理专业论文）基于mmx技术的指纹图像匹配识别算法研究.pdf

大连理工大学硕士学位论文 摘要 生物认证技术已经越来越多的被应用到日常生活，如考勤、登记、远程控制、自动 查询、门禁控制等等。由于指纹识别技术的高实用性和可行性，指纹识别己成为目前市 场占有率最高的生物认证方式，在诸多方面得到了广泛应用。随着科技的不断进步，人 们对指纹识别系统的性能也提出了更高的要求，准确、快速的指纹识别系统始终是一个 研究的热点问题。 针对指纹识别中计算最复杂、最关键的匹配部分，本文给出了一种基于m m x 技术 的检索与匹配算法实现并行实时匹配。m m x 是一种多媒体扩展结构技术，它极大提高 了计算机在多媒体和通信应用方面的功能，是对i n t e l 体系结构的最重要的加强。m m x 技术提供了5 7 条新指令、8 个6 4 位数据寄存器和4 种新的数据类型，它基本原理是利 用单指令多数据( s i m d ) 的并行处理机制即在一条指令中并行地处理2 个、4 个甚至8 个 数据，这种并行操作可以几倍地提高对数据的处理效率。当在指纹图像识别中应用m m x 优化的代码，能够大幅度提高处理速度。 本论文对指纹识别系统中的检索和匹配部分做了深入的研究，并给出了相应的基于 m m x 技术的并行处理算法： ( 1 ) 为了实现在大型指纹库下的指纹图像快速匹配，本文采用了检索与匹配相结合的 识别方案。首先对原来的三角形特征检索向量进行改进，设计了一种适合m m x 技术指 令集的三角形特征检索向量；进而给出了基于m m x 技术的有序排列检索算法。在有序 排列检索算法中利用了分配排列和散列法与m m x 技术结合，快速寻找到可能匹配的三 角形，大大缩短检索时间。 ( 2 ) 在关键的匹配阶段，本文给出了一种基于m m x 技术的匹配算法并引入了二次匹 配的思想。首先将检索信息引入匹配过程中，利用检索到的匹配三角形顶点间相互匹配， 解决指纹匹配参考的选择问题。设计了一种新的适合m m x 技术的匹配结构，用最佳匹 配三角形作为中心参考来代替原来的中心参考点匹配模式，用长度来代替角度的计算。 在完成第一次全局匹配之后，为克服指纹的非线性形变带来的影响，提出了用近邻匹配 特征点代替原选定中心参考三角形找出在第一步匹配中可能遗漏的细节点对，从而达到 较高的正确识别率。 对论文中提到的所有算法，本文均进行了模拟实验。实验结果表明，本文给出的新 的检索和匹配算法除了具有平移、旋转不变性外，在匹配速度和容忍非线性形变方面具 有良好的性能。 关键词：自动指纹识别系统；f l n x 技术；并行处理；指纹检索；指纹匹配 大连理1 ，大学硕士学位论文 f i n g e r p r i n ti m a g ei d e n t i f i c a t i o na 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 a b s t r a c t d u et oi t sp r a c t i c a b i l i t ya n df e a s i 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 nn o wp o s s e s s e st h e l a r g e s tm a r k e ts h a r eo fb 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 o l o g y , a n di t h a sb e e nu s e di nm a n y r e g i o n s i nt h em o s tc o m p l e xa n dm o s tp i v o t a lm a t c h i n gs t a g e ，n e wm a t c h i n ga l g o r i t h m sb a s e d o nm m x t e c h n o l o g ya r ep r e s e n t e df o rp a r a l l e la n dr e a l - t i m em a t c h i n gm m x i sam u l t i m e d i a e x t e n s i o ns t r u c t u r e t e c h n o l o g y ，i tg r e a t l yi m p r o v et h ec o m p u t e rp e r f o r m a n c ei n t h e a p p l i c a t i o no fm u l t i m e d i aa n dc o m m u n i c a t i o n m m xt e c h n o l o g y a d d sf i f t y s e v e nn e w i n s t r u c t i o n s ，e i g h tr e g i s t e r so fs i x t y - f o o rb i t sa n df o u rn e wk i n d so fd a t at y p e s ，a n di ta t t b r d sa p a r a l l e lo p e r a t i o nb yt h em e t h o do fs i m dt h a tas 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 t d a t a s e v e r a lc o r r e s p o n d i n gp 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 xt e c h n o l o g ya r e p r e s e n t e d ： ( 1 )i no r d e rt oi m p l e m e n tf 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 ni nf a c eo fl a r g ed a t a b a s e ，t h i s p a p e rp r e s e n t saf i n g e r p r i n ti d e n t i f i c a t i o na p p r o a c hb yi n t e g r a t i n gt h ei n d e x i n ga n dm a t c h i n g a l g o r i t h m s f i r s t l y ，an e wt r i a n g l ef e a t u r ei n d e x i n gv e c t o ri sp r o p o s e db ym o d i t 、y i n gt h e t r i a n g l e m i n u t i a ef e a t u r ev e c t o r t h e n ，a na l g o r i t h mw i t hr e g u l a ra r r a yb a s e do nm m x t e c h n o l o g yi sa d v a n c e d t h eh a s h i n ga n dd i s t r i b u t i o na r r a yc o m b i n e dw i t hm m xt e c h n o l o g y a r eu s e dt os e e kt h ep o t e n t i a lt r i a n g l e sq u i c k l yf o rd e c r e a s i n gt h ei n d e x i n gt i m e ( 2 )i nt h ep i v o t a lm a t c h i n gs t a g e ，an e wm a t c h i n ga l g o r i t h mb a s e do nm m x t e c h n o l o g yi sp r e s e n t e da n dt h ei d e ao f s e c o n dm a t c hi si n t r o d u c e d t h em a t c ho ft h em a t c h e d i ni n d e x i n gp e r i o dt r i a n g l ev e r t i c e si su s e dt os o l v et h ep r o b l e mo fs e l e c t i n gt h em a t c h r e f e r e n c e an e wm a t c h i n gs t r u c t u r ei sc o n s t r u c t e df o rm m xi n s t r u c t i o ns e t ，u s i n gt h et r i a n g l e o fh i g h e s ti n d e x i n gs c o r ea st h er e f e r e n c ei n s t e a do fm a t c h e dp a i ro fm i n u t i a ea n dn on e e dt o c o m p u t et h ea n g l e a l lt h ep r o p o s e da l g o r i t h m sh a v eb e e ni m p l e m e n t e di nap r a c t i c a lf i n g e r p r i n ti m a g e p r o c e s s i n gs y s t e mi nt h ep a p e r t h ep r o p o s e di n d e x i n ga n dm a t c h i n ga l g o r i t h mp e r f o r m sw e l l b o t hi nm a t c h i n gs p e e da n di nt o l e r a t i o no ft h en o n l i n e a rd e f o r m a t i o n b e s i d e si t ss h i f ta n d r o t a t i o ni n v a r i a n tp r o p e r t y k e yw o r d s ：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 e a l i o ns y s t e m ；m m xt e c h n o l o g y ；p a r a l l e l p r o c e s s i n g ；f i n g e r p r i n ti n d e x i n g ；f i n g e r p r i n tm a t c h i n g 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研 究工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含 为获得大连理工大学或者其他单位的学位或证书所使用过的材料。与 我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说 明并表示了谢意。 作者签名；i 兆堑日期：迎z ：f 2 ：，驴 大连理_ 丁大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名： 导师签名： 坳垦望 讶对字 2 盟丘年_ 里月_ 上旦_ 日 大连理丁大学硕七学位论文 1 绪论 1 1 生物识别技术概论 可靠的身份认证一直是人们所追求的。从最初阶段的各种机械钥匙到后来的数字密钥 如密码或条形码等，现在已经发展到利用人体所固有的生物特征来辨识与验证身份。生物 识别( 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 o l o g y ) 是当今数字化生活中最高级别的安全密钥系统。目 前，生物识别技术已经被越来越多的应用到日常生活中。笼统来说，生物特征识别技术是 为了进行身份验证而采用自动技术测量其身体特征或是个人行为特点，并将这些特征或特 点与数据库的模板数据进行比较，完成认证的一种解决方案【l 】。由于人体特征具有人体所固 有的不可复制的唯一性，这一生物密钥相对于传统的身份认证方式具有无法复制、失窃或 被遗忘等优点，近些年来得到了飞速发展。 生物特征识别技术的基本工作就是对那些普遍存在的、可测量或可自动识别和验证的 生物特征进行统计分析。可用于身份认证的生理或行为特征必须具有以下特性1 2 】：普遍性， 即是所有人都拥有的特征；唯一性，即仅通过特征的差异就可以唯一的确定当事人的身份； 稳定性，即此特征不会随时问或空间的变化而变化；可获取性，即能对此特征进行采集和 定量处理。常用的身体特征包括：指纹、掌形、眼睛( 视网膜和虹膜) 、人体气味、脸型、 皮肤毛孔、手腕，手的血管纹理和d n a 等；行为特点包括：签名、语音、行走的步态、击 打键盘的力度等。所谓的生物识别的核心在于如何获取这些生物特征，并将之转换为数字 信息，存储于计算机中，利用可靠的匹配算法来完成验证与识别个人身份的过程。下面针 对几种比较典型、应用范围较广的生物识别技术进行阐述，并分析其优缺点。 ( 1 ) 指纹识别 指纹识别技术是目前生物识别技术中应用最广泛的技术1 3 1 。公安机关利用指纹来确定某 些事实，为侦查破案、起诉和审判提供资料和证据 4 1 ，其他学科和部门也在研究和应用指纹， 例如利用指纹图像验证身份证或工作证的真假：银行以指纹图像作为取款凭证，避免冒领 事件；在一些高级宾馆、要害部门装备指纹锁，以控制进出人员；人寿保险公司存储指纹 作为备查辨认的依据等等 指纹是指手指末端正面皮肤上凸凹不平的纹路。尽管指纹只是人体皮肤的一小部分， 却蕴含大量的信息。这些皮肤的纹路在图案、断点和交叉点上是各不相同的，在信息处理 中将它们称作“特征”。据统计，世界上两个不同手指的指纹完全相同的概率小于1 0 - 9 ， 可以认为世界上还没有完全相同的两枚指纹。依靠特征惟一性，可以把一个人与他的指纹 对应起来，通过比较他的指纹特征和预先保存的指纹特征，就可以验证其真实身份。 相对于其它身份识别技术，指纹识别是一种更为理想的身份确认技术，不仅具有许多 独到的信息安全角度的优点，更重要的是还具有很高的实用性和可行性 2 1 。因为每个入的指 一l 一 基丁m m x 技术的指纹图像匹配算法研究 纹独一无二，两人之间不存在相同的指纹；每个人的指纹是相当固定的，很难发生变化， 指纹不会随着人年龄的增长或身体健康程度的变化而变化；指纹样本便于获取，易于开发 识别系统，实用性强，目前已有标准的指纹样本库，方便了识别系统的软件开发，识别系 统中完成指纹采样功能的硬件部分也较易实现；一个人的十指指纹皆不相同，因此可以方 便地利用多个指纹构成多重口令，提高系统的安全性，并不增加系统设计的负担；指纹识 别中使用的模板并非最初的指纹图像，而是由指纹图像中提取的关键特征，因此存储量较 小，对输入的指纹图像提取关键特征后，可以大大减少网络传输的负担，支持计算机的网 络功能，便于实现异地确认。 ( 2 ) 人脸识别 人脸识别可以说是人们日常生活中最常用的身份确认手段，也是当前最热门的模式识 别研究课题之一。人脸识别就是通过与计算机相连的摄像头动态捕捉人的面部，同时把捕 捉到的人脸与预先录入的人员库存人脸进行比较识别。因为人们对这种技术没有任何的排 斥心理，所以从理论上讲，人脸识别可以成为一种最友好的生物特征身份认证技术。 人脸识别的优点在于四：不需要被动配合，可以用在某些隐蔽的场合；这种识别方式可 远距离采集人脸；利用已有的人脸数据库资源，可更直观、更方便地核查该人的身份，因 此可以降低成本。 但人脸识别的缺点也是显而易见的。人脸的差异性并不是很明显，误识率可能较高； 对于双胞胎，人脸识别技术不能区分；人脸的持久性差，例如长胖、变瘦等；人的表情也 是丰富多彩的，这也增加了识别的难度；人脸识别受周围环境的影响较大。由于这些困难， 人脸识别的准确率不如其它技术。 ( 3 ) 虹膜识别 虹膜是瞳孔与巩膜之间的环形可视部分，具有终生不变性和差异性。人眼中的虹膜是 由随瞳孔直径变化而拉伸的复杂纤维状组织构成。人在出生前的随机生长过程，造成了各 自虹膜组织结构的差异。虹膜总体上呈现一种由里到外的放射状结构，包含许多相互交错 的类似斑点、细丝、冠状、条纹、隐窝等形状的细微特征。这些特征信息对每个人来说都 是惟一的，其惟一性主要是由胚胎发育环境的差异所决定的。通常人们将这些细微特征信 息称为虹膜的纹理信息。 虹膜识别技术的优点是：精确度高 6 1 ；建库和识别的速度快；无需人工干预；用者无需 与设备直接接触。而缺点是：虹膜技术对于盲人和眼疾患者无能为力而且系统成本过高。 需要比较好的光源，对黑眼睛识别比较困难。 ( 4 ) 语音识别 这里的语音识别是指说话人识别，又称声纹识别技术。语音识别可以采用两种方式： 第一种是依赖原文。系统将一句话与访问者相联系，对每个访问的人，系统会给出不同的 - - 2 - - 夫连理1 = 大学硕士学位论文 句予提示。应对说话者不断变化的主要方法是动态的变化，这包括一系列的声音向量描述 的说话方式，然后计算访问者和允许进入者说话方式的差距。另一种是不依赖原文的。访 问者不必说同样的句子，因此系统应用的惟一信息就是访问者的语音特征。 语音识别技术的优点是t l l ：方便、系统的成本非常低廉；对使用者来说不需要与硬件直 接接触，而且说话是一件很自然的事情，所以语音识别可能是最自然的手段，使用者很容 易接受；最适于通过电话来进行身份识别。 语音识别技术的缺点是：准确性较差，同一个人由于音量、语速、语气、音质的变化 或其它很多原因容易造成系统的误识；当模板数量大到一定程度之后，语音特征就不足以 惟一区分开每个人，而且它容易受到背景噪音、被检查者的身体状况的影响；语音可能是 所有生物特征中最容易被伪造的，至少现在可以用录在磁带上的语音来进行欺骗：高保真的 录音设备是非常昂贵的。因此基于语音特征的识别系统很难达到基于指纹或者视网膜识别 系统的准确率。 ( 5 ) 签名识别 签名识别也被称为签名力学辨识，它建立在签名时的力度上，分析的是笔的移动，如 加速度、压力、方向以及笔划的长度，而不仅仅是签名的图像本身。每个人都有自己独特 的书写风格。签名识别有两种形式：静态签名和动态签名。静态签名只使用签名的几何特 征；动态签名除了使用签名的几何特征外，还使用书写时的笔顺、速度、力度等特征。签 名识别技术的关键在于区分出不同的签名部分，有些是习惯性的，而另一些在每次签名时 都不同。 签名识别技术的优点在于1 7 1 ：人类在很久以前就开始使用签名来鉴别身份，因此签名识 别对于使用者来说有着良好的心理基础，容易被使用者接受。缺点是签名识别的速度比较 慢、所用的硬件设备价格昂贵并且签名很容易被伪造。 总体说来，现有的生物认证技术，绝大部分都是基于语音或图像等多媒体信息处理的。 它们通常计算量较大，程序中含有高度重复的循环代码。因此，如何能够提高计算效率、 减少处理时间，实现实时认证，一直是困扰人们的一个难题。 1 2m m x 技术概要 多媒体与其说是复杂的技术，倒不如说是海量数据。实时连续地处理声音和影像等多媒 体信息的要求使个人计算机( p c ) 负担越来越重，以往的方法是通过开发专用的d s p ( d i g i t a l s i g n a lp r o c e s s i n g ) 来分担中央处醐c p u ) 的工作，使总体性能得以提高。但同时，系统的 成本也相应的提高了。有鉴于此，i n t e l 公司推出了m m x 技术，提升了c p u 的信号处理能 力，使得没有d s p 或专用加速芯片的p c 机也能实时处理多媒体信息。m m x i s l ，是英语 m u l t i m e d i ae x t e n s i o n ( 即多媒体扩展指令集) 的缩写。m m x 是i n t e l 公司为提高p c 机处 理多媒体和通信的能力而推出的新一代处理器技术，同时也是对i n t e l 体系结构指令集的扩 一3 一 基于m m x 技术的指纹图像匹配算法研究 展。 通过对目前大量实际应用程序的分析，如图形、m p e g 、视频、音乐合成、语音压缩、 语音识别、图像处理、游戏、视频会议等，从中找出计算最为密集的代码段 9 1 ，这部分程序 代码通常具有如下一些共同特征： ( 1 ) 较短的整型数据变量( 如1 6 位音频数据、8 位图像数据) ； ( 2 ) 不长但高度重复的循环( 如d c t 、f f t ) ； ( 3 ) 大量的加、乘和累加( 如f i r 滤波、矩阵运算) ； ( 4 ) 计算密集型算法( 如三维图形、视频压缩) ； ( 5 ) 可以高度并行执行的操作( 如图像处理) 。 针对这些共性要求，i n t e l 开发了一套基本通用整数指令，可简便地用于各种多媒体和 通信应用程序，这就是m m x 技术。m m x 技术是对i n t e l 体系结构的最重要的加强，它在 p e n t i u m 芯片技术基础上增加了5 7 条新指令、8 个6 4 位数据寄存器和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 i m d ) 技术 来展现出其在多媒体及通信方面的应用。简单地说，s i m d 技术主要是让每一条指令可并 行地在多项数据中运作。采用m m x 技术的处理器拥有充分的能力加速多媒体及通信应用 程序的运行，可在执行有大量计算的通信及多媒体任务的同时腾出足够的余地来执行其他 任务和应用程序。m m x 技术一方面利用了众多多媒体及通信算法中固有的并行机制，它 通过增加新的通用指令和定义新的6 4 位数据类型使微型计算机平台性能达到一个新水平， 同时又与基于i n t e l 体系结构平台的软件和操作系统保持兼容。 m m x 技术的定义非常简单，它包含以下技术要点【l o l ： 紧缩字节( 8 x 8b i t s ) 6 3 4 84 73 23 l1 61 5870 紧缩字( 4 x 1 6b i t s ) 6 34 84 73 23 1 1 61 50 紧缩叔字( 2 3 2b i t s ) 6 3 3 23 1 0 4 字( 6 4b i t s ) 6 30 图1 1 紧缩数据类型 f i g 1 1p a c k e dd a t at y p e - 4 - 大连理工大学硕士学位论文 ( 1 ) 引入新的数据类型 m m x 指令系统主要的数据类型是紧缩的定点整数，而多个整数字被紧缩成一个单一 的“位数并被移入6 4 位m m x 寄存器，如图1 1 所示。m m x 技术所支持的数据类型为有 符号和无符号的定点整数：字节、字、双字及四字。 m m x 技术的4 种数据类型为： 紧缩字节：8 个8 位的字节紧缩为一个6 4 位的数，其中各字节相互独立； 紧缩字：4 个1 6 位的字紧缩为一个6 4 位的数，4 个字相互独立。这是m m x 技术 最核心的数据类型； 紧缩双字：2 个3 2 位的双字紧缩为一个“位的数，这2 个双字相互独立； 四字：一个6 4 位的数。 ( 2 ) 采用s i m d 技术 s m m 技术运用单指令同时并行地处理多个数据元素，从而提高了程序的运行效率。 m m x 技术支持对字节( 8 位) 、字( 1 6 位) 、双字( 3 2 位) 和新的4 字( 6 4 位) 整数数 据类型的并行操作 ( 3 ) 新增6 4 位m m x 寄存器 m m x 指令体系中新增了8 个6 4 位宽的m m x 寄存器，其编号为m m 0 一m m 7 ，这8 个， 寄存器利用的就是现有的c p u 内8 个通用浮点f f p ) 寄存器中的低6 4 位。与x 8 6 的通用寄存 器不同，m m x 寄存器仅能作为数据寄存器而不能作为地址寄存器。m m x 技术通过在i a 浮点寄存器和f p 状态之上使用寄存器和状态的别名，保留了与现行操作系统和应用程序的 完全兼容性。因此，没有增加新的寄存器或状态来支持m m x 技术。这意味着操作系统使 用标准机制与f p 状态相互作用来保存和恢复m m x 指令代码。 ( 4 ) 高效指令，超强应用性能 在目前的高级多媒体、通信和图形等应用程序中均含有对短数据类型实现循环操作的 复杂算法，m m x 指令集所引入的新的通用指令可并行地对多个紧缩在“位寄存器中的不 同类型( 8 位、1 6 位和3 2 位) 数据元素进行算术运算和逻辑运算。一条m m x 指令能同时 操作8 个字节，且一个时钟周期能执行两条指令，这意味着一个时钟周期能处理完1 6 字节 的数据元素。这些指令通过采用密集计算算法，对一小段数据进行局部化操作和循环操作， 从而增强了应用程序的性能。几乎所有靠重复和循环方式对整数数据进行计算的应用都能 从m m x 技术中获益。 ( 5 ) 降低处理器开销 除了性能上的提高，m m x 技术还为其它功能释放了附加的处理器周期，使得过去依赖 额外硬件的应用，现在只用软件就能执行。降低处理器开销能更好地实现并行操作，这一 特色已被今天许多操作系统所利用。根据i n t e l 的分析，对于某些功能，性能改进的幅度为 基丁二m m x 技术的指纹图像匹配算法研究 5 0 4 0 0 ，相当于一个新卅：处理器所带来的性能提高。在软件内核里，已观察到3 5 倍以上的更大的加速。 m m x 技术提供了新的5 7 条操作码，它们是为紧缩数据的高速算术、逻辑、比较操作 而设计的，按功能可分为7 类：算术运算指令，比较指令、转换指令、逻辑运算指令、移 位指令、数据传送指令、置空m m x o ；m m x ) 状态指令。 7 下面我们以计算向量点积j = y a , c ( 设所有变量均为1 6 位) 为例来说明m l d x 技术 i - 0 的优势【叼： p 川由de 耳i 习孕舯e 乓王 习 e 正 田 正罩田 叵再0 圈臣互j 至互习e 至三三三二三童臣至囹e ! ：! ：! i ! ：! ! = ：! ：! i i 砷。c a l c lia 2 。c 2 + 却。c li i j - - - ，- - - j p a d d d+ + 叵至三巫珂 _ _ _ _ _ _ 。_ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - 。- j - _ _ 。i - - 。_ 。_ 。_ 。 _ _ _ 。一 区翌圈i ! ：竺：! i 竺：! ：! ：l p a d d d 4-4- r 。q 啕。一 i 。q 乜c ，+ 和。i 却。c 矿 i 。r 4 + a 7 。c 7 匿翌圈 l 。c | 抽。bi h + 幻。c 7i p s r l d 二豳 7 图1 2 口，+ q 的计算过程 i = o f i g 1 2 f l o w c h a r t o f a v e c t o r d o t p r o d u c t 大连理工大学硕士学位论文 p m a d d w d ：紧缩字乘法累加指令分别将两寄存器中8 个1 6 位数据对应相乘，产生4 个 3 2 位的结果，并把左边的2 个乘积加在一起作为一个结果，同时把右边的2 个乘积加在一 起作为另一个结果。 p a d d d ：指令完成在环绕模式下两对有符号3 2 位数据的加操作。 p s r l d ：指令完成逻辑右移操作。 7 合理应用这些指令，可以完成x = 罗a l q 这样的向量计算，应用m m x 指令的计算 。1 一= 0 过程如图1 2 所示。 7 应用m m x 指令和传统的x 8 6 处理器指令计算罗口。* c j 所用指令数见表1 1 ，从表中可 磊 以看出，该向量计算仅需两次乘法( p m a d d w d 指令) 和两次加法( p a d d d 指令) 及其它几 条指令配合即可完成；若使用现有的x 8 6 系处理器的指令，需进行1 6 次载入、8 次乘法、7 次加法并进行8 次移位，共需使用4 0 条指令。使用m m x 技术后仅需原来三分之一的指令， 并且大部分m m x 指令在一个时钟周期内完成，因而m m x 技术的优势更为突出，在多媒 体及通信算法中，应用m m x 技术后能达到不应用m m x 技术的速度的1 5 到2 倍。 表1 1 两种方法使用指令数比较 t a b 1 1i n s t r u c t i o nc o m p a r i s o no f t w oa l g o r i t h m s 此外，m m x 技术支持一种新的算洪饱和算法，它与传统的环绕算法形成鲜明的对比。 在传统的环绕模式中，上溢或下溢的结果被截去，只有结果的低位才返回，进位被忽略。在饱 和模式中，上溢或下溢的结果被饱和成数据类型的最大或最小值。例如对于8 位的象素数 据，0 表示黑，2 5 5 表示白。当运算结果超过2 5 5 时，如在环绕模式下，返回结果将变成o ，因 而将黑白颠倒。而使用饱和运算，将使该值为2 5 5 ，因而误差不大。可看出饱和算法特别 适合色彩计算，反映了多媒体处理的实际情况，同时也减少了由于溢出判断、处理所进 行的内部操作，加快了运算速度。 1 3 本文主要研究内容与结构安排 本文主要工作是研究如何应用m m x 技术来进行指纹图像的匹配识别；设计基于 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 h 6 0 中加以实现。 本文的结构安排如下： 第一章概述现行的生物认证技术和m m x 技术的要点。 第二章主要讨论本文工作所涉及的自动指纹识别系统的构成、指纹识别技术的现状 和指纹的预处理及特征提取算法，其中具体包括了对图像分割、方向图计算、基于方向 图的二值化、细化、纹线跟踪和伪特征滤除等算法的描述。 第三章主要研究指纹图像特征的检索算法，阐述了基于m m x 技术的并行有序检索 算法的设计与实现，给出实验结果并予以分析。 第四章重点研究指纹图像特征基于检索信息的匹配算法，阐述了基于m m x 技术的 并行定点匹配算法的设计与实现，其中引入了分步匹配的算法，给出实验结果并予以分 析。 第五章对本文所做的工作进行总结，同时对m m x 技术和指纹识别技术的应用和发 展进行展望。 大连理工大学硕士学位论文 2 指纹识别技术概述 2 1 引言 人们使用指纹识别身份已经有很长的历史了【1 2 1 。考古学家证实，公元前7 0 0 0 年到 6 0 0 0 年以前，在古叙利亚和中国，指纹作为身份鉴别己经开始应用。考古发现，在这 个时代，一些粘土陶器上留有陶艺匠人的指纹，在古城市的房屋留有砖匠的指纹，中国 的一些文件上印有起草者的大拇指指纹等。由此可见，虽然当时指纹的一些特征并未被 证明，但在当时已经被人们认识和接受。 现代指纹识别技术起源于1 6 世纪晚期1 1 3 1 。在1 6 8 4 年，英国植物形态学家g r e w 发 表了一篇论文，阐述他关于指纹的脊、谷和孔状结构的系统研究“2 j ，这被认为是指纹研 究方面的最早一篇科学论文。从那时起，许多后来者在指纹研究方面做出了努力。1 7 8 8 年，m a y e r 对指纹的结构做出了详尽的描述1 1 3 1 ，并对许多指纹特征下了定义。1 8 8 0 年， f a u l d 第一次科学的阐述了指纹的稳定性与唯一性【1 2 1 ，这些发现奠定了现代指纹识别技 术的基础。在1 9 世纪晚期，g a l t o n 引发了指纹的深入研究，他在1 8 8 8 年介绍了指纹的 细节特础”j 。1 8 9 9 年，h e n r y 做出了又一次重要进步，他建立了著名的“h e n r y 系统” 用于指纹分类【1 2 1 。直到2 0 世纪早期，指纹上携带的信息才被完全理解，有关指纹的生 物特性叙述如下： 指纹是指手指表面由交替的“脊”砸d g e s ) 和“谷”( v a l l e y s ) 组成的平滑纹理模式，。 其形成取决于胚胎中形成手指表皮部分的初始环境，有很强的随机性。人类人口倘若 按照6 0 亿计算，则需3 0 0 年才有可能出现重复的指纹，其重复出现的概率几乎为零。 而一个人在母腹七个月时，其指纹就已定型，且不变异。 一枚指纹的特征如图2 1 所示。 这些特征被用来区分不同的指纹。其中： 端点：一条纹线终止的地方； 分叉点：一条纹线分裂成两条的地方； 中心点：指纹的几何中心，是纹线产生最大曲率的地 三角点：三种不同方向的纹线汇聚的地方； 交叉：两条纹线产生交叉的地方； 小岛：一条很短小的纹线； 汗腺孔：脊线上的小孔，系汗腺。 端点和分叉点是最为常用的特征。通常的算法都要 交曼 中心点 分叉点 靖点 小岛 三角点 汗膝孔 图2 1 指纹特征 f i g 2 1f i n g e r p r i n tf e a t u r e 基于m m x 技术的指纹图像匹配算法研究 记录它们的位置和方向。中心点和三角点在刑侦系统中普遍使用，而在民用系统中并不 常用。因为这些应用中所使用的采集器往往面积较小，较难完整地采集到中心点和三角 点。交叉和小岛由于计算上的困难，在实际的系统中往往不予采用。 有人曾提出用汗腺孔来进行指纹识别，但这种方法要求指纹采集设备要有非常高的 分辨率。所以在实际的系统中没有采用。 关于指纹特征的研究成果使得指纹识别技术在犯罪鉴别中得以正式应用，并被法律 正式强制接收成为一种有效的个人身份识别方法，并且成为一项标准的法庭程序。2 0 世纪6 0 年代，由于计算机可以有效地处理图形，人们开始着手研究利用计算机来处理 指纹。从那时起，自动指纹识别系统a f i s 在法律方面的研究和应用在世界许多国家展 开。2 0 世纪8 0 年代，个人电脑、光学扫描这两项技术的革新，使得它们作为指纹取像 的工具成为现实，从而使指纹识别可以在其他领域中得以应用。 现在，指纹在越来越多的领域得到了广泛的应用，被认为是身份认证的物证之首。 ( 1 ) 信息安全领域：如个人计算机系统使用指纹进行验证，网上银行、电子商务的安全 交易等；( 2 ) 数据通信领域：如指纹识别技术作为生物密钥可对加密传输数据进行二次 加密，增加安全性；( 3 ) 公共安全方面：如指纹门锁、汽车门锁、个人指纹身份证等；( 4 ) 金融安全方面：如指纹智能卡、指纹终端、指纹保险箱、指纹储蓄卡、大额取款客户身 份确认等；( 5 ) 其他方面：如指纹考勤、个人医疗档案管理、保险受益人确认、海关及 民航快速通关认证等。 随着许多指纹识别产品的开发，指纹识别技术的普及应用已经指日可待。但是，目 前指纹识别技术仍是国内外科研人员研究的热点，主要原因有：市场上的指纹产品有很 强的针对性，只能在某一专门系统得到应用：出于知识产权保护和商业利益等原因，指 纹识别的核心技术仍然只被少数企业和技术机构所拥有，为了获得自主产权的和绝对安 全的系统，必须自主开发；随着市场的扩大和要求的提高，设计开发速度更快、性价比 更高的系统势在必行。因此，开发性能可靠、成本较低的自动指纹识别系统将给我国安 全技术、防伪技术、身份识别技术，特别是i t 产业带来重要的革新。 2 2 自动指纹识别系统的构成 自动指纹识别系统 j a l ( 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 i o ns y s t e m ，简称a f i s ) 已经 被广泛应用。除了传统公安领域的应用，自动指纹识别系统还作为计算机操作系统识别 用户的手段，以及访问网络资源的口令，另外，它可作为嵌入系统用于银行a t m 卡和 信用卡的确认方式，以及智能i c 卡的双重确认，还可以用于雇员、海员身份鉴定、家 用电子门锁等许多方面。 本文采用的自动指纹识别系统框图如图2 2 所示，指纹识别技术主要涉及指纹图像 采集、指纹图像预处理、特征提取、保存数据、特征向量的比对与匹配等过程。 大连理工大学硕士学位论文 图 像 输 入堋蓁篙 图2 2 自动指纹识别系统 f i g 2 2a m o m a t c 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 结 果 输 出 首先，通过指纹读取设备读取到人体指纹的图像，并对原始指纹图像进行初步的处 理，使之更清晰。然后，指纹识别算法建立指纹的数字表示特征数据，这是一种单 方向的转换，可以将指纹转换成特征数据，但不能将特征数据转换成为指纹，而且两枚 不同的指纹不会产生相同的特征数据。特征文件的存储是从指纹图像上找到被称为：细 节点”( m i n u t i a e ) 的数据点( 指纹纹路的分叉点或末梢点) 。有些算法把细节点和方向信 息组合产生了更多的数据，这些方向信息表明了各个节点之间的关系，有些算法也处理 整幅指纹图像。总之，这些数据通常称为模板，保存为一个指纹样本的记录。最后，通 过计算机模糊比较的方法，把两个指纹的模板进行比较，计算出它们的相似程度，最终 得到两个指纹的匹配结果。目前国际上在数据存储上仍然没有一种模板的标准，也没有 种标准公布的抽象算法。 为了使系统能够实时、快速地完成识别任务，要求构成该系统的各个模块能够彼此 良好地衔接起来，所以每个部分所涉及的算法必须高效、省时，既要完成自己的任务， 又要为后面提供可靠、方便的数据，使整个系统的性能提高。实际的指纹识别系统往往 由于应用环境、系统规模、实现思路以及具体算法的不同，而在系统整体框架上有所出 入。例如。一般的小型应用，如家庭门禁、指纹保险箱等，就不需要分类步骤，而有些 系统直接从原始指纹图像中提取特征，不需要二值化、细化等预处理操作。 2 3 指纹图像的预处理及特征提取 2 3 1 指纹图像的采集 传统的指纹采集方法是用手指蘸上印油在纸上按压，然后用扫描仪摄取，由于这种 方法存在严重的不可靠性，该方法已经被淘汰。当今所使用的主要指纹采集技术有光学 指纹采集技术，半导体指纹采集技术和超声波指纹采集技术i l 。 ( 1 ) 光学指纹采集技术是目前应用最广泛的指纹采集技术，光学指纹采集设备始于1 9 7 1 年，其原理是光的全反射( f t i r ) 。光线照到压有指纹的玻璃表面，反射光线由c c d 去获得， 基于m m x 技术的指纹图像匹配算法研究 反射光的量依赖于压在玻璃表面指纹的脊和谷的深度以及皮肤与玻璃间的油脂和水分。光 线经玻璃照射到谷的地方后在玻璃与空气的界面发生全反射，光线被反射到c c d ，而射向 脊的光线不发生全反射，而是被脊与玻璃的接触面吸收或者漫反射到别的地方，这样就在 c c d 上形成了指纹的图像。 ( 2 ) 半导体传感器是1 9 9 8 年在市场上才出现的，这些含有微型晶体的平面通过多种 技术来绘制指纹图像。常用的有硅电容指纹图像传感器、半导体压感式传感器、半导体 温度感应传感器。半导体指纹传感器采用了自动控制技术( a g c 技术) ，能够自动调节 指纹图像象素行以及指纹局部范围的敏感程度，在不同的环境下结合反馈的信息便可产 生高质量的图像。例如，一个不清晰( 对比度差) 的图像，如干燥的指纹，都能够被感 觉到，从而可以增强其灵敏度，在捕捉的瞬间产生清晰的图像( 对比度好) ；由于提供 了局部调整的能力，图像不清晰( 对比度差) 的区域也能够被检测到( 如：手指压得较 轻的地方) ，并在捕捉的瞬间为这些象素提高灵敏度。半导体指纹采集设备可以获得相 当精确的指纹图像，分辨率可高达6 0 0 d p i ( 每英寸点数) ，并且指纹采集时不需要象光 学采集设备那样，要求有较大面积的采集头。由于半导体芯片的体积小巧，功耗很低， 可以集成到许多现有设备中，这是光学采集设备所无法比拟的，现在许多指纹识别系统 研发工作都采用半导体采集设备来进行。 ( 3 ) 超声波指纹图像采集技术被认为是指纹采集技术中最好的一种，但在指纹识别系 统中还不多见，成本很高，而且还处于实验室阶段。超声波指纹取像的原理是：当超声 波扫描指纹的表面，紧接着接收设备获取的其反射信号，由于指纹的脊和谷的声阻抗的 不同，导致反射回接受器的超声波的能量不同，测量超声波能量大小，进而获得指纹灰 度图像。积累在皮肤上的脏物和油脂对超声波取像影响不大。所以这样获取的图像是实 际指纹纹路凹凸的真实反映。 三种方式的比较如表2 1 所示，可见，这几种指纹采集技术都具有它们各自的优势， 也有各自的缺点，可以根据实际需要来选择采用哪种技术的指纹采集设备。 大连理工大学硕十学位论文 表2 1 指纹采集技术比较 t a b 2 1c o m p a r i n go f f i n g e r p r i n ti m a g ea c q u i s i t i o n 本文在实验中采用d i g i t a lp e r s o n a 公司的 u a r e u2 0 0 0 指纹扫描器，如图2 3 所示。该扫 描仪能够自动捕捉指纹图像，通过u s b 口将数字 化的图像送入电脑内存中。它集成了精密光学系