（模式识别与智能系统专业论文）基于关联概率模型的指纹识别算法.pdf

基于关联概率模型的指纹识别 摘要 近十几年的生物识别技术的迅猛的发展和广泛的应用前景已经吸引了许多 研究者的极大的兴趣。而基于指纹身份识别技术也因其良好的可靠性而逐渐应 用到人们生活中。科研工作者对于基于指纹生物识别技术的研究方兴未艾，有 关指纹识别的产品和新技术也日新月异。 指纹识别是寻找一个最佳的形变模型来模拟指纹图像中形变( 非线性或线 性) ，使得两幅指纹图像之间的差异最小。因此，如何提取指纹图像的特征信息、 建立最优的形变函数、以及定义指纹特征信息之间的差异评估函数一直是影响 识别算法性能的重要因素，也是从事指纹识别研究工作者所需解决的难点。虽 然，人们已经提出很多种方法来解决这些问题，但都有其局限性。因此，本文 借助大数定律的思想，来分析和设计本文的自动指纹识别算法，并提出了一种 基于关联概率模型的指纹识别算法。在本文中与其它算法的不同之处在于： 第一，以多尺度原理对指纹图像进行增强处理。 第二，根据指纹特征和纹理模式的独特性，定义了综合细节点和细节点之间 的关联关系等来描述指纹图像的唯一性。 第三，利用指纹的综合信息，构造指纹的局部拓扑结构，建立了一个相似度 与形变的关联概率模型来动态分析指纹图像的形变。 第四，对影响算法性能的各种参数进行统计分析，采用基于最大熵原则的多 阈值方法搜索出最优的性能参数。 基于f v c 数据库的实验结果表明本文提出的基于关联概率模型的指纹识别 算法是有效性。 关键词：生物识别技术，关联概率模型，关联关系，可变界限盒，综合细 节点 注：本文丁作得到了国家杰出青年科学基金项目( 6 0 2 2 5 0 0 8 ) ，国家重大基础 研究前期研究专项项目( 2 0 0 2 c c a 0 3 9 0 0 ) ，8 6 3 高科技发展计划项目 ( 2 0 0 2 a a 2 3 4 0 5 1 ) ，国家自然科学基金项目( 6 0 1 7 2 0 5 7 ，6 9 9 3 1 0 1 0 ，6 0 0 7 1 0 0 2 ， 3 0 2 7 0 4 0 3 ，6 0 0 7 2 0 0 7 ) 的资助。 摘要 f i n g e r p r i n t i d e n t i f i c a t i o nb a s e do nc o r r e l a t i v e p r o b a b i l i t y m o d e l y u l i a n gh e a il a b s ，i n s t i t u t eo f a u t o m a t i o n ，c h i n e s e a c a d e m yo fs c i e n c e s d i r e c t e db yp r o f e s s o rt i a nj i e a b s t r a c t t h eb i o m e t r i ci d e n t i f i c a t i o n t e c h n o l o g y h a sa t t r a c t e di n t e r e s t so f r e s e a r c h e r sf o ri t s r a p i dd e v e l o p m e n t a n dt h er e l i a b i l i t yo ff i n g e r p r i n t b a s e d i d e n t i f i c a t i o nt e c h n i q u e sh a sm a d ei tt ob ew i d e l yu s e di nc i v i l i a na p p l i c a t i o n t h em a t c h i n gb e t w e e nt w of i n g e r p r i n t si st of i n da n o p t i m a l d e f o r m a t i o n t r a n s f o r m a t i o nm o d e lt os i m u l a t et h ed e f o r m a t i o n si nf i n g e r p r i n t sa n dm i n i m i z e t h ed i f f e r e n c eb e t w e e nt h et w o i m a g e s t h e r e f o r e ，e x t r a c t i n gf i n g e r p r i n t f e a t u r et or e p r e s e n ta f i n g e r p r i n t ，b u i l d i n ga no p t i m a ld e f o r m a t i o nm o d e l ，a n d d e f i n i n g am e a s u r e m e n tf u n c t i o no ff i n g e r p r i n tf e a t u r e sa r ev e r yi m p o r t a n t p a r t so faf i n g e r p r i n ti d e n t i f i c a t i o nm e t h o d ，i nw h i c ht h er e s e a r c h e r sh a v eb e e n i n v o l v e d ，a t t h o u g hm a n ym e t h o d s h a v eb e e n p r o p o s e d t os o l v et h e s e p r o b l e m s ，m o s to ft h e ma r eo n l yd e s i g n e dt os o l v es o m es p e c i a lp r o b l e m sa n d n o ta n a l y z ea n ds o l v ea l lm e n t i o n e dp r o b l e ma b o u taf i n g e r p r i n ti d e n t i f i c a t i o n m e t h o d w es t a t i s t i c a l l yd e s i g no u rf i n g e r p r i n tm e t h o db a s e do nc o r r e l a t i v e p r o b a b i l i t ym o d e l t h eh o v e ii d e a so ft h i sm e t h o da r ei i s t e da sf o i l o w s ：f i r s l w ed e f i n ec o m p r e h e n s i v em i n u t i a e ，i n c l u d i n gm i n u t i a ea n dt h e i ra s s o c i a t e d t e x t u r e ，t op r e s e n taf i n g e r p d n t s e c o n d w ec o n s t r u c tal o c a lf e a t u r es t r u c t u r e w i t ht h ec o m p r e h e n s i v em i n u t i a et ob u i l das i m i l a r i t y d e f o r m a t i o n p r o b a b i l i t y m o d e lt od y n a m i c a l l ya n a l y z ed e f o r m a t i o n si naf i n g e r p r i n t ，t h i r d ，w eu s et h e m u l t i l e v e lt hr e s h o l ds e l e c t i o n b y m a x i m u me n t r o p yc r i t e r i o nt os e tt h e t h r e s h o l d su s e di no u r m e t h o d f i n a l l y , ad y n a m i c s c a l e a p a c e m e t h o di su s e d t oe n h a n c e f i n g e r p r i n t s c o m p a r e d w i t ho t h e rm e t h o d si nl i t e r a t u r ea n do u r p r e v i o u s 基于关联概率模型的指纹识昴 i n v a r i a b l e b o u n d i n gm e t h o d ，o u r m e t h o di sm o r ee f f i c i e n ta n de f f e c t i v e k e yw o r d s ：b i o m e t r i c a l i d e n t i f i c a t i o n t e c h n o l o g y , c o r r e l a t i v ep r o b a b i l i t y m o d e l ，r e l a t i v er e l a t i o n s h i p ，i n v a r i a b l e b o u n d i n g ，c o m p r e h e n s i v em i n u t i a e i i i 独创性声明 本人声明所成交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果。与我同工作的同志对本研究所做的任何贡献 均己在论文中作了明确地说明并表示了谢意。 签名 f 期 关于论文使用授权的说明 本人完全了解中圉科学院自动化研究所有关保留、使用学位论文的规定，即： - p 幽科学院自动化研究所有权保留送交论文的复印件，允许论文被查阅和借阅； 可以公御论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名 导师签名日期： 基于关联概率模型的指纹识别 1 1 背景 第一章引言 指纹是用影像设备采集手指上类似流体状的纹理而获取的图像。1 9 世纪初， 科学研究发现了至今仍被认可的指纹的两个重要特征，一是两个不同手指的指 纹纹理的式样( r i d g ep a t t e r n ) 不同，另外个是指纹纹理的式样终生不改变。这个 研究成果使得指纹在罪犯鉴别 1 1 中得以正式应用。在应用之初，都采用手工的 方法，即将指纹卡片存放在指纹库中，需要时从指纹库中人工查找、由指纹专 家对比指纹卡。这种方法一方面效率低下，另一方面投入的人力资源太大。为 了克服这些缺点，从本世纪六十年代开始，随着计算机技术的发展，人们开始 着手研究利用计算机来处理指纹。从那时起，许多国家开展了自动指纹识别系 统( 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 ) 在法律实施方面的 研究和应用工作【2 。 指纹具有唯性( 任意两个手指不存在相同的纹理式样) 、不变性( 纹理式 样习i 随时问变化) 、普遍性( 每个人都拥有其独特的纹理式样) 、可采集性( 纹 理式样可以定量采集) 。因此，指纹识别技术是目前应用最广泛的生物识别技术。 另外，指纹识别技术比其它的生物识别技术( 如签名、入脸、语音等) 更成熟、 性能更稳定可靠【3 】。因此，自动指纹识别系统有着广泛的应用背景。除了传统 的在法律公安上的应用外，自动指纹识别系统还可作为计算机确认用户的手段， 以及访问网络资源的口令1 2 。另外，它可用于银行a t m 卡和信用卡使用的确认， 及各类智能i c 4 ，5 ，6 的双重确认；还可用于雇员证明、海关身份鉴定、家用 电子门锁等许多方面。此外，在现实生活中还有许多地方使用了指纹进行身份 认证，如硬盘、准考证、驾照、身份证、i c 卡等，并且市场上已经有相关的产 品，如指纹硬盘已经面世，在本文中就不一一列举。随着技术的发展，a f s 将会得到越来越多的应用，并且所占的比例越来越大。 此外对于一个应用系统，还要考虑一些其他指标，( 1 ) a f i s 识别性能，包 括识别率，识别速度，系统鲁棒性，系统所需资源和影响系统性能的各种其它 因素等。( 2 ) 可接受性：指用户对该系统的接受程度。同时，由于应用市场的 第一章引言 扩大、电子器件的降价和小型化的不断发展，a f i s 的研究已从过去以光学传感 器为主转移到面向半导体传感器为主。更高的识别率，更低误识率，更快的识 别速度一直是a f i s 研究者追求的目标。n c l ，自动指纹识别系统还有着重要的 研究意义。 1 2 问题简述 基于指纹的生物识别技术越来越引起科研工作者的广泛关注和兴趣，并在该 领域中做出了大量工作。研究方法不断推陈出新，指纹识别技术因而日新月异。 目前，指纹识别方法大致可分为基于细节点 7 ，8 ，9 、基于全局特征( 采用了指 纹纹理特征来对指纹进行分类 1 0 ，1 1 ，1 2 ，1 3 ，也用于识别 1 4 ) 、基于综合特 征( 包括细节点以及部分纹理 1 5 ，1 6 ，1 7 ，1 8 ，1 9 ) 等三类。基于细节点的指纹 识别算法首先要确定细节点，然后比较细节点的分布来确定两幅指纹是否来自 同一手指。这类指纹识别算法因其存储代价小而被得到广泛应用。但是，该算 法存在着因丢失了大量纹理特征，严重地影响算法的识别性能等缺陷；另一个 缺陷是这种算法( 无论是点模式匹配还是图模式匹配) 。因细节点数目各异而造 成细节点排列上的困难，影响计算速度。基于全局特征的指纹算法是匹配指纹 的全局纹理特征，计算两幅指纹的最大互信息。该方法不仅应用于指纹分类算 法，而且被应用到指纹识别中。但是这类方法存在有需要一个可靠的、高精度 的参照点，对指纹的非弹性形变难以处理，而且对存储代价要求高等缺陷。但 是，以上两类算法优缺点互补。因此，许多的研究工作者提出了基于综合特征 ( 包括细节点及部分纹理) 的指纹识别算法。这类方法具有如下几个优点：首 先，纹理特征能加速调整细节点模板：其次，纹理特征能弥补细节点所不能反 应的指纹特征。部分纹理与细节点结合更能全面描述一个指纹，而且所需的代 价比较小：第三，该类算法能融合以上两类算法的许多方法；最后，该类算法 的优越性能，因而得到指纹研究工作者的广泛关注。 总之，以上匹配算法的所需要做的首要工作是恢复指纹图像的几何影像形变 及错位等问题 2 0 。因此，在指纹识别中必须考虑这些指纹图像中可能存在的 线性或非线性形变。但是，目前大部分已有的算法依赖一个前提条件：待匹配 的两幅指纹图像是使用相同配置、相同采集仪来采集的，即同模态；并且，这 些指纹允许存在一定程度的噪声。匹配算法的目的是：对给定的两幅指纹，寻 基于关联概率模型的指纹识别 求使这两幅图像的灰度( 或特征) 相似度之间差异达到最小。在这种情况下，主 要的t 作常常是对指纹形变问题的研究，建立个定义在有穷的形变参数空间 的带参数的形变变换模型，最后进行形变参数最优化处理。 闲此，对于指纹识别算法来说，存在如下难题： 第一，以最小代价来全面真实地描述指纹的纹理式样，反映指纹的独特性。 第二，建立有效的指纹图像形变模型，以及图像之间的相似度的测量： 第三，在有穷维的参数空间中搜索出最优形变参数，使形变变换后的图像之 刚的狄度或特征差异最小。 1 3 主要工作 本文的主要工作： 第一，采用动态多尺度图像增强的方法对指纹图像进行图像增强处理，并且 从处理后的图像中提取综合细节点、构造图像的局部特征结构、定义细节点之 间的关联关系。 第二，提出了一种基于关联概率模型指纹识别算法。建立一个关联条件概率 模型来描述指纹图像的局部区域差异与形变之间的关系。根据预先假定的形变 模型，比较局部区域纹理特征，估计出图像局部的形变与相似度之间的关联概 率模型；采用概率统计方法在参数空间中估计最优的参数，使得任意两幅指纹 剧像之阍的差异值最小。 第三，对影响算法性能的各种参数进行统计分析，采用基于最大熵原则的多 阂值方法搜索出最优的算法中的各种阈值。 1 4 本文结构 第二章给山r 提炼指纹特征的方法。期望所提炼的指纹特征能全面、真实地 描述指纹。本章的主要内容包括图像的图像增强、后处理( 二值化与细化) 、指 纹特征的提取等。 第三章分析了指纹图像中的局部形变模式，建立指纹图像的形变模型来分析 指纹的形变。首先，基于图像成像的映射原理，建立一个带参数的形变变换模 型；然后提出了一个形变与相似度的关联概率模型来描述指纹图像的局部区域 差异与形变之间的关系。基于大数定律的基本思想，采用几何平均方法估计参 数空间中最优的形变参数。最后，采用最大熵原则作多闽值选择，使得图像之 间的差异值最小。 4 基于关联概率模型的指纹识别 2 1 指纹图像增强 第二章提取指纹特征 在实际应用中，由于受手指本身的因素和采集条件的影响，采集到的指纹图 像会不同程度地受到各种噪声的干扰。因此，在进行图像分类和匹配之前一般 需要对采集到的指纹图像做增强处理。现有的指纹增强算法多数是基于局部脊 线力向估计来进行增强处理。如d o u g l a sh u n g 2 1 3 等人的自适应的局部脊线方 向的增强算法和l i nh o n g 2 2 等人的使用g a b o r 滤波器的算法。虽然，这些方 法对于质量较好的指纹图像而言，取得了很好的效果。但是，它们存在如下两 方面的问题：一方面，受噪声污染严重的区域淹没了指纹特征；另一方面，正 是在这样的区域对局部脊线方向的估计是不可靠的，因而难以获得好的增强效 果。因此，为避免这些问题，本文采用从图像的全局信息出发，采用动态多尺 度的方法 2 3 ，2 4 ，2 5 ，2 6 来对图像进行增强处理。 2 1 1 线性尺度空闻 尺度空问理论采用多级灰度方式来为建立视觉图像处理模型提供一个标准 方法。一个两维图像，1 ( 置妇的尺度空度表达：帮肛詹可以表示为f ( 丑力与标 准高斯函数甑( 五力的卷积所构成的序列函数，即： f l ( x ，y ；f ) = ，( x ，y ) 圆g f ( x ，y x ，、p 0 2 + y 2 ) ，2 1 2 ( 2 1 ) l g t 【墨川2 三；f 一； ，其中参数f 是标准高斯序列函数的尺度参数。序列函数( 五j ，：幻可以通过它 的微分方程的解来产生，即： a f 工= 告v ，v = 告( a ，+ ay ：) ( 2 2 ) ，且它的初始值定义为( 置j ，：0 ) = “丑订。 在图像尺度空间中，若尺度增大，图像丢失的信息也越多。小尺度图像空 第二章提取指纹特征 问e t 巾包含大尺度图像空间的特征；大尺度图像空间将会丢失图像的细微特征， 即：一般只包含图像全局的结构特征，同时也含有被压缩过程中所产生的噪声。 分别用系列方差为d 。( k ：l ，2 ，n ) 的标准高斯滤波函数甑( 五力对图像 以置力进行滤波处理，得到尺度为6 。( k = l ，2 ，n ) 的空间序列 l ，( k ：l ，2 ，门) ，并计算各相邻尺度空间之间的特征差异，记为： d k = 上听一l q ( 后= 1 2 ，九一1 ) ( 2 3 ) 令觑= f - l 。这样就得到了一个尺度空间表达式以及描述。用公式2 4 构造图 像“置力： f = l 玑+ d k ( 2 4 ) k = o 2 1 2 方向估计 一般的指纹图像都有比较清晰的方向场，方向场估计的准确性直接决定了图 像增强算法的效果。为估计方向场，把纹理的走向分为如下8 个方向( 图2 1 ) 图2 1 一个像素的8 个指纹纹理方向 为估计图像中的每一个像素的纹理方向，首先在以该像素为中心的9 x 9 窗 口内，计算出8 个方向上的灰度平均值，即将图2 1 中标了( 1 = o ，1 ，7 分别 代表8 个方向) 的位置的像素灰度值取平均得到g n 然后将这8 个平均值按两 两垂直的方向分成4 组，即0 和4 一组，1 和5 一组，2 和6 一组，3 和7 一组， 计算每组中两个平均值的差值：钳i = 研胡一研j q - 4 ( 卢o ，l ，2 ，3 为四个纹理方 向) 。接着，取差值的最大绝对值的两个方向为可能的脊线方向，若： m a x = 盯g t 2 e 搬3 ) ( q ( ) ) ( 2 5 ) 则方向如，和j 。，。为该像素点的可能的纹理方向，若该像素点的灰度值为6 r e y , 则纹理方向为 6 基于关联概率模型的指纹识别 ： l j g r e y - 一c ? g 缀譬4 1 dg r e y4 ) ( 26 ) ：= jg 【j + ) b ) i + 4 o t h e r w i s e 即取j 。和j 。方向中灰度平均值与该像素的灰度值比较接近的方向作为该像素 处的纹理方向，从而得到该像素的方向的估计值。 为减少噪声对方向的影响，保证方向场估计的准确性，本文采用通用的做法， 将图像分成1 6 1 6 的小块，以小块内所有像素的方向的平均值作为该小块的纹 理方向，该小块内每个像素的纹理方向都取为该小块的纹理方向，具体做法是， 先计算浚小块内方向估计值为i ( i = 0 ，l ，7 分别代表8 个方向) 的像素个数，记 为 i ，然后将该小块图像的纹理方向取为： b = a r g m a x ( i ) ) ( 2 7 ) 2 ，1 3 动态多尺度空间( d s s ) 的图像增强 尺度空间理沦被广泛应用于图像分割、边缘检测等计算机图像处理领域中。 研究的重点是对象的轮廓。而指纹图像具有类流线型纹理模式的图像，具有独 特的纹理特征，脊线与谷线相互交叉，交替出现，适合于尺度空间理论。本文 将尺度空间理论应用于指纹图像增强，是为了过滤掉指纹图像的噪声。首先将 指纹图像分解成各尺度下的子图像，用各尺度下高斯滤波函数滤除各尺度下的 图像中的噪声。然后，融合各尺度下的子图像。每次增强处理过程都能消除指 纹图像巾的部分噪声，多次循环，可以得到一幅性能更好、更清晰的增强处理 后的指纹图像。但是，用尺度空间理论进行指纹图像增强需要深入讨论如下两 个问题：其。，尺度参数的选择；其二，尺度函数序列长度的选择。 类似于小波原理，假设动态尺度参数ok = 2 ( a = - l ，2 ，1 7 0 ) ( 其中凰是尺 度空间的大小，也是尺度函数序列长度，7 0 是可变的，因此dk = 2 。被称之为动态 尺度，它所构成的尺度空间被称之为动态尺度空间( d y a d i cs c a l e s p a c e ， d s s ) 2 4 ，2 6 ) ，m = l o g ：( 2 * 0 ( 其中，是指纹脊线平均宽度，并可以利用方法 1 1 来计算) 。 处理指纹图像，a 首先，用标准方差为d f 2 ( k = - i ，2 ，肠) 的高斯序列 函数生成指纹图像，的动态尺度空间厶( k = - i ，2 ，凰) ，l = f xg m 并由公 式( 2 1 ，2 2 ) 得到特征序列图像历( k = - 0 ，1 ，i 7 0 一1 ) 。噪声的影响将在尺度 空间厶中被削弱，厶中的灰度值反映了指纹图像中的纹理信息；特征序列研含 旃二章提取指纹特征 柯，所包含，但被k 。遗漏的特征信息。但由于现也存在噪声干扰，本文使用方 差为口。= 2 “1 ( 肛l ，2 ，肠) 的高斯函数对现进行处理，记：7 产觑g 。 在传统的增强方法 2 2 ，2 3 中，这些方法会在平滑过程中丢失图像特征以， 即由于过度平滑，一些真实的特征同噪声一齐被滤掉。而动态尺度空间进行滤 波处理时，t 保留了各个尺度下的真实特征，同时能滤除掉各尺度下的噪声。 令乓为在尺度2 “下的增强后图像，可以计算出在尺度2 。下的增强图像层，即： 1 2 5 5 e k ( f ，) = 0 ，忙。或壤一1 ( f ，j ) - l ( j ) + 反( f ，n ，o ，点山( f 棚g “( f ，力一厶( “) j ；( 2 ，8 ) 2 5 5 x ( e k - 1 ( i , j ) - _ i l k + l ( i , j ) - 一l k ( i , j ) ，o ，峨舶j ) 吃，z ，0 d7 。所以( 3 6 ) 式可以简化为： 基于关联概率模型的指纹识别 也即 其中 川“鲁她棚1 去r 慨7 ) 阱瓢堋删 ( 3 8 ) a = c o s s c o s p s i n o s i n s i n 口 b = s i n 口s i n 妒c o s p c o s o s i m p c = c o s # s i n 6 p d = c o s 庐c o s o ( 3 9 ) 口d b c = c o s o c o s = f ( z os i n o c o s b + t = ) z o f 2 = 厂( 一z os i n e + t y ) z o 从3 8 式可以看出平面物体在不同位置下的投影图像之间满足仿射变换关 系。因此，有以上推导，可以得出结论：图像的形变可以使用仿射变换模型进 行近似地模拟。 3 2 指纹图像映射关系 w e l g r i m s o n ( 1 9 9 4 ) 等人详细地分析了特征位置的偏差对以上两种方法 的影响，由于仿射变换和仿射不变量对误差非常敏感。在很多情况下导致无匹 配或仿射匹配不存在，因此必须寻找鲁棒的仿射匹配方法。文 3 7 提出了一种 基于活动原点的放射变换匹配方法。其基本思想是仿射坐标架中的原点坐标带 有两个可以在一定误差范围内变化的调整参数。由于坐标原点坐标是不确定的， 因此仿射坐标架也可以是活动的，由该仿射坐标架建立的仿射变换也可带有两 个可以在一定误差范围内变化的调整参数，这两个参数在匹配其它点时起到调 节作用。理论分析和试验表明该方法优于传统的仿射变换方法。并推导如下： 对于两个仿射坐标架( 塌，腼，腮) 和( 用。，1 1 1 2 ，1 1 1 。) ，其中仍和1 1 1 ， 分别是两个仿射架的原点，设毋= ( x i ，儿) ，i l l 产( j7 。，y7 。) ( 产l ，2 ，3 ) ， 则有： 第三幸暴于荚联_ i i ! f 牢模型的指纹识别 ( 簧) = a ，( ；i ) + r = ( ：2 ) ( 芰) + ( ) c 。， ，= 。，x _ 2 一- y x l 。，x 3 - 一x y i 。八 ( y x ：z 一- y x jx y 3 ，- - 一x y i 。，i 一1 ( s - ，) 心) 一m ( 笼) 给定点= ( tj ，) ，仿射变换乖( 膨7 ) 将其变换到点p ”= ( 肖”，r ”) ( 分m ( 分r ( 3 1 2 ) ( 3 1 3 ) 点p 和点p 是否匹配取决于点p ”和点p 之间的距离d ( p ”，劫是否小于某个 给定的阈值g 其中： d ( p ”，p ) 刊p ”一p i ( 3 1 4 ) 如果珊是可以活动的，也即皿+ 俨置+ 而且+ 一，其中俨似届a y ) ，a x 2 + a y 2 e ， 是给定的常数，则有： m ( 血，妙，= l y x ：一- y x l 。- 一z 缈b c 蠹二i ) ( 爱：费x y 3 ，- - 一x y ) i ， ( s - s ， 丁c 触，妙，= 晦) = ( 薏) 一m c 缸，母，( 爱) c 。，e ， 这里麒置力和t ( a x , 力表示带有两个调整参数，以下不再说明。同 样考虑p 和卢，仿射变换a ( a x , a y ) = ( 麒a x , 力，t ( a x , 力) 将p 变换到 荣、p 。t x ，访= t x ”y “、， ( 多) = m ( a z ，缈) ( ；：) + 丁( 缸，缈) ( 3 1 7 ) 点p 和点p 是否匹配取决于是否存在( 五a y ) 满足，+ ， o ) 表示x o 与j 之间的相似度函数。 细节点单形f ( 只j ) 与f ( e 力之间的最终的相似度可以表示为： 叩描鼢黧觌。k “兄 扭z ， 另外，f * ( k = l ，2 ，3 ，4 ) 为阈值，经验上分别设定为1 6 ，1 0 ，1 5 ，1 5 。s ( i ，) 的值越大，表示细节点单形占( f ) 和f ( e 力越相似。为了确定细节点单形中 的细节点之间的对应关系，本文定义了细节点单形的方向索引，定义如下： o ( f 棚= 捂糍靴。) ( “) ( 32 2 ) 现在来计算细节点单形之间的差异，其反映图像局部特征之间的形变。目 前，许多的方法 1 6 ，1 7 是采用孤立的细节点或局部特征之间的差异作为图像局 部之间的形变。这些方法有一个明显的缺陷在于这些形变是孤立的，没有有机 地结合其它局部特征之间的形变，难以合理分析全局的形变。因此，本文采用 统计方法，建立形变与相似度之间的关联概率模型，综合分析图像全局的形变。 本文采用公式3 2 3 来计算局部结构( 细节点单形) 的形变： g f ，力= fr丁 垮州嘶唧培电t 唧m n l 也飞呐彬吨- a e j t 施舻0 ；( 3 2 3 1r “ 怪丑“( 蛳嘞，女嚆机t 嘶屯女m n l 也飞) 嗡2 也) ，“f ) = 1 ； 其中，a * 0 ( 1 膏2 t + 2 ) ，且有 rr2 旯+ 而+ t + 如r + = 1 = l = l女= 1 ( 3 2 4 ) 基于关联概率模型的指纹识别 在这里本文仅以旋转形变为例来描述本文如何建立关联条件模型去分析形 变，计算出最优的变换模型。 3 3 2 关联概率模型 两幅指纹图像的局部结构进行一一比较后，本文可以得到一系列的形变样 本值和相似度样本值，形变数据可以为寻找最优的形变模型提供便利，而相似 度数据是独立于形变，是图像的独有的基本特征，本身可以用于图像识别。但 是，由于这些相似度与达到识别还相差定距离，且存在误差。因此需要根据 形变变换模型对图像特征做进一步的调整和对局部相似度数据做深入的校验， 然后进行识别。 在本文的匹配方法中，指纹图像的局部相似度不仅作为下一步图像识别基 础，同时为构造形变模型，分析图像之间的形变提供数据依据。因此，本文在 使用相似度来衡量局部匹配的有效性的同时，还用于形变分析。基于以上思想， 本文定义了相似度与形变的关联概率模型。相似度与形变的关联概率模型的基 本思想是：若图像的局部相似度越大，则其形变在全局形变分析，形变模型的 建立中所占的份量就越重要。本文用函数f 来表示以形变为自变量的相似度函 数，具体构造方法如下： f ( ，) f ( g 1 ，( 口) = s ( i ，) 艿( 研，- o ) ( 4 2 8 ) i = 1j = l 。 其中，占( 曲函数是一个冲击函数，当x = o 时j ( 曲= l ；否则为0 。函数，反映了 指纹图像的形变与相似度之间的关联关系，为分析和设计一个形变变换模型提 供很好的理论依据。所生成的图像f 和6 的关联概率函数见闺3 2 。 第二章摧于关联概率摸型的指纹识别 5 0 0 4 0 0 3 0 0 2 0 0 1 0 0 o 1 0 0 图3 1 来自同一手指的指纹图像尸和占 图3 2 图3 1 中的两幅图像之间的关联函数 由于图像局部结构的匹配过程中存在误差或误匹配，虽然这些误差是随机 的，很难对整个模型的全局构成大的影响，但是，需要进行滤波处理以避免影 响下一步计算最优参数的精度。滤波函数( 公式3 2 6 ) 是类高斯滤波函数。滤 波处理后的关联概率函数见图3 3 。 c ( o = o 5 ( 1 一c o s ( d r d ) ) ，f _ 1 ，2 d + l r 口2 6 ) 基于关联概率模型的指纹识别 由大数定律可以得出，在线性形变( 或类似线性形变) 的关联概率函数服 从高斯分布。 4 0 0 0 3 5 0 0 3 0 0 0 2 5 0 0 2 0 0 0 1 5 0 0 1 0 0 0 5 0 0 0 _ _ l 【 ，lfk 3 3 3 形变参数分析 2 0 04 0 0 图3 3 滤波后的关联概率函数 关联概率函数的最大值所在位置可视为形变模型参数的最优值，使得在参 数值的形变模形下的两幅指纹图像之间的差异达到最小。为了精确定位和计算 这些参数的数值，本文采用几何平均的方法来估计出最优的形变参数值。具体 的方法是： 由上节分析，得出形变与相似度的关联概率函数具有正态分布。首先取置 信度为0 9 4 0 0 ，置信区间为 ，一九o ，“+ 九o ( k = 1 1 7 7 4 )( 其中和叮分别 是关联函数的均值和方差) ；然后在该置信区间内对形变参数取几何平均值。由 高斯函数分布可知，在u 九6 的位置上的关联函数的值的大小恰好是关联函数 最大值的一半。因此，可以不计算关联函数的方差，而直接采用公式3 2 7 计算 平均的形变误差： “l + 丸叮l h ? + 丸口l x 。= i f ( x ) d x 阿( 川。 ( 3 ，2 7 ) u , - 2 0 f“l 一2 0 - 第三章基于关联概率模型的指纹识骨 公式3 2 7 的物理意义是在置信度为0 9 4 0 0 的条件下，取相似度与形变的 关联概率函数的质心作为最优的形变参数。本文的实验也证明该公式的有效性。 在文献中有许多方法介绍 6 ，9 ，2 8 ，2 9 如何建立图像的形变模型，并取得了 比较好的性能。但是本文的方法借鉴大数定律的思想来分析形变参数，同以上 提到的方法相比较，具有更强的鲁棒性。 采用同样的方法可以估计计算图像的平移参数t 和，并将这些参数引入 到公式3 1 9 中，从而得到个具体的参数化的仿射变换模型。 3 ，4 基于关联概率模型的匹配模式 在3 2 和3 ，3 节定义了一个带参数的最优仿射变换模型来模拟指纹图像中 的形变变换，且在3 3 节中描述了如何计算指纹局部之间的相似度。在这一章 中，应用第3 2 节中所定义的带参数的仿射变换模型来对局部匹配结果进行校 验。校验的具体方法如下： 对于任意对细节点单形f ( 只j ) 和豇g 力，若它们的相似度大与0 ，则 利用固定界限盒的方法 1 7 来判断它们是否为有效匹配单元。首先确定与细节 点单形占( 只) 相关联的细节点对麒只，j ) 和麒只b ) ，及与细节点单形f ( e 力 相关的细节点职e 力和似0 ：然后采用仿射变换模型( 公式3 1 9 ) 变 换这对细节点觚只乃) 和肌只日j ，并映射到模板图像中，看是否分别落入 以细节点麒e ，0 和麒每0 为中心界限盒以内；若是，则为有效匹配，否 则，表示为细节点单形( i ) 和双最力之间的匹配为误匹配。遍历所有细节 点单形的匹配结果，直至全部。 指纹图像的局部特征可能存在相似性( 正如第2 2 中对指纹图像特征所分 析的) 。因此，在采用界限盒方法对匹配结果进行校验后，将使用细节点关联关 系对匹配结果进行再次校验。本文的方法是： 步骤一，选择待校验的局部匹配结果。对于任意一对细节点单形占( ei ) 和 f ( 力，若它们的相似度大于0 ，即进入下一步；否则，重新选择。 步骤二，确定与细节点单形瓦只d 相关联的细节点对职只一和以只 g ，) ，及与绍节点单形( 最力相关的细节点顾动和以匠o ： 步骤三，汁算两对细节点麒只n ) 和麒e 砌，以只日0 和觚ee 0 的、 基于关联概率模型的指纹识别 在关联关系上的相似性。令关联关系的相似度为c ( i ，力( o 。( j ，d 1 ，计算方 法类似串匹配参见 1 6 。若任意对细节点之问的关联关系的相似度不大于o ， 则细节点单形f ( 只j ) 和f ( 力之间的匹配为误匹配； 步骤四，所有局部结构结果被遍历后，分析得到图像f 和占之间的相似度， 方法如下： m f f 、肿f g 、 j = 芝窆。d ( _ ，1 ) x c ( r , ，r t ) ) c ( e t ，e 1 ) ) ( 3 2 9 ) k = li = i 为了得到最优的匹配结果，即使s 最大，采用在下一节中将介绍的基于最 大熵原则的多阈值选择的方法来调节各个闽值使s 最大。 3 5 基于最大熵原则的多阈值选择 阈值选择方法是图像处理和图像识别领域中最重要也是最常用的方法之 一+ 。人们为阀值的自动选择付出了巨大的努力，提出了很多方法 3 9 ，4 0 ，4 1 。 另外，近年来提出的新方法还有包括j u i c h e n gy e n 等人的用最大相关性原则 来选择闽值的方法 4 2 ，a p i k a z 等人的基于图像拓扑稳定状态的方法 4 3 ， n p a p a m a r k o s 等人的用有理多项式来拟合灰度直方图两个峰间的区域，再用该 有理多项式的极小值决定阈值的方法 4 4 ，l i a n g k a ih u a n g 等人的通过极小 化图像的某种模糊测度来决定灰度阈值的方法 4 5 ，还有很多其它的方法 4 6 ，4 7 ，4 8 。 基于最大墒原则选择阅值是常用的阈值选择方法之一，由r p u n 首先在 4 9 ，5 0 中提出。这种方法的目的在于将图像的灰度直方图分成独立的类，使得 各类的总熵最大，从信息论角度来说就是使这样选择阈值获得的信息量最大。 人们为解决计算量问题提出了各种不同的方法，j ，g o n g 等人 5 1 提出了一个快 速递归算法来减少计算不同阈值下的熵值时所需的计算量，这种方法并没有解 决需要考虑的情况太多，搜索空间太大这一根本问题。h d c h e n g 等人介绍了 一种求最大熵的模拟退火算法 5 2 ，但模拟退火算法同样有计算量很大，收敛 速度很慢的问题，有关图像处理中的模拟退火算法的详细讨论请参看 5 3 。 文献中有多种不尽相同的最大熵原则，本文采用其中具有代表性的 工n k a p u t 等人 1 4 提出的最大熵原则来讨论多阈值问题。 第二章基于关联概率模型的旨纹识勇 先考虑单阏值选择，即把识别效果用一个阈值将识别结果分成识别成功和拒 识两个区域的情况，其目的是使在测试样本的算法性能达到最优。用丑) ， a ，屏表示识别结果的概率分布，如果把阈值设置在识别结果级别s ，将 获得两个概率分布，一个包含1 到s 间的识别结果级别，另一个包含矿1 到7 问的识别结果级别，这两个分布如下： 一：鱼，且，丝； p sp ，p s b ：卫l ，卫生，。，。；( 4 3 0 ) 1 一p s 1 一p 。1 一且 。 n = e p , 与每一个分布相关的熵为： 令 篆= - - 粪+ 晋汪以研，羹去魄尚刮。妒咖皆 庐( j ) ：( ( 彳) + h ( 曰) ) ：l o g p , ( 1 一只) + 量+ h a - m s ( 4 3 2 ) p sl p s 闽值s 设置为 s = a r g 峄盼( s ) ) ( 4 3 3 ) 上述单阈值选择原则能直接推广到多闽值选择情况，此时( 3 ) 式变为 s i j 2n 她鼢。) = l o g ( b ) + 1 0 9 ( b ) + + l o g ( b ) i = 0 j = 5 l + jl ，5 + 1 p fl o g p t s l e p i = 0 p jl o g p ,p , l o g p ， ( 4 3 4 ) 竺卫生一一一生! ! j ， “ p i芝a 其中k 是类数，闽值( s 1 ，s 2 s k ) 设为 ( s i ，s 2 一- ，s t ) = a r g m a x ( ( 5 1 ，s 2 ，) ) ) ( 4 3 5 ) 8 1 ，5 2 ， 基于关联概率模型的指纹识别 第四章实验结果 4 1 实验数据与评测标准 目前，指纹识别算法的测试数据集主要有如下两类：第一类是n i s t ( n a t i o n a li n s t i t u t eo fs t a n d a r d sa n dt e c h n o l o g y ，是美国国家标准局的 缩写) 指纹库。n i s t 一4 5 5 、n i s t 一9 5 8 、n i s t 1 4 5 6 、n i s t 一2 4 5 7 和n i s t 一2 7 是它所颁布的标准指纹库，这也是指纹理论研究中评价算法优劣的最常用的数 据库。 另外，f v c 是模式识别协会i a p r ( i n t e r n a t i o n a la s s o c i a t i o no fp a t t e r n r e c o g n i t i o n ) 年会举办的指纹算法竞赛，2 0 0 0 年 3 0 和2 0 0 2 5 4 年分别举办 了两届，使用的数据库分别是f v c 2 0 0 0 和f v c 2 0 0 2 指纹认证数据库，它们是最 新的用于算法评测的标准数据库。f v c 2 0 0 0 和f v c 2 0 0 2 指纹认证数据