技术领域\n本发明涉及指纹识别技术领域,尤其涉及同时融合方向图特征和细节点特征进行识别的 技术。\n背景技术\n随着社会的发展与进步,进行快速、有效、自动的人身辨别的实际要求日益迫切,重要 部门保安、过境控制、移民检查、机密或贵重物品保存场所的进出、防止信用卡欺骗、网络 安全等都需要进行可靠的人身鉴别。在身份验证的依据中,钥匙、证件可能会丢失、被盗或 复制,密码又容易被忘掉、混淆或被偷看,而生物特征(包括指纹、人脸、手形、手写签名、 虹膜等)是人的内在属性,不会出现上述情况,因此成为最理想的辨别依据。其中,指纹识 别是应用最普遍、识别率最高、最容易被接受的个人身份认定方法。作为物证之首,指纹识 别已有一个非常漫长而且成果丰富的历史。基于计算机的自动指纹识别始于二十世纪60年 代,它首先应用在刑事侦破中。近年来,指纹自动识别从刑事应用逐渐推广到考勤、门禁、 银行保险箱、社会保险等领域,我国也已初步决定在新一代身份证中引入指纹信息进行个人 身份认证。在911恐怖事件后,基于指纹自动识别的个人身份识别更得到前所未有的重视。\n目前的指纹自动识别方法主要是基于细节点特征的,即提取细节点(指纹中脊线的终结 点或交叉点)作为特征来表征指纹图像,通过比对这些特征进行识别。其步骤一般包括:指 纹图像采集、方向图(指纹纹理的方向)提取、图像增强、指纹脊线细化、细节点提取等。 围绕着如何更好更快地提取细节点,近二十年来国内外研究单位做出了大量工作,并且现有 指纹产品都是基于这种方法的,如美国BAC公司的SecuTouch,日本Sony公司的FIU-500, 美国BII公司的Veriprox,韩国Bogo公司的Bogo2000,美国DP公司的U.are.U 2000, 美国Identix公司的Biologon等。\n随着指纹识别应用的推广,现有系统和方法在大范围应用上的不足越来越显现出来。最 近发表的一篇论文(S.Pankanti,S.Prabhakar,and A.K.Jain.On the individuality of fingerprints.Proceedings of IEEE International Symposium of CVPR,Vol.1,USA,Dec 2001,pp:805-812)指出,目前的很多指纹系统中对于一枚指纹平均只能获得36个真的细 节点,而通常认为,两枚指纹之间如果有15个以上的细节点比对成功就可以判断为同一个手 指,考虑到用计算机方法提取出的细节点在坐标和方向上会出现一定误差,则将某一个手指 的指纹判断为另一个的概率大于4.26×10-7(图1中给出了两枚不同指纹被判断为同一手指的 例子)。如果考虑到提取出的细节点中有假点的话(对于任何方法都必然会出现这种情况), 则错误率还会大大增大,达到10-3的程度,严重影响识别的结果。\n出现以上问题的一个根本原因在于指纹的特征表达不够完备。指纹这一比较复杂的模式 单用细节点来描述是远远不够的。可以说,这一问题已成为当前指纹识别的一个瓶颈问题。 要解决这一问题,必须从全新角度重新研究指纹的特征表达问题,寻求新的可以描述指纹个 体差异和自身稳定性的特征。当然,由于实际应用的限制,这些新的特征应该有简约的表达 (以方便存储)。在所有可以查到的专利或发表文献中,与本发明思路比较接近的有:在(A.K. Jain,S.Prabhakar,L.Hong and S.Pankanti.Filterbank-based fingerprint matching. IEEE Trans.on Image Processing,Vol.9,2000,pp:846-859)中利用多滤波器的响应 进行编码,以这些编码作为特征进行指纹识别,在(A.Ross,S.Prabhakar,and A.K.Jain. Fingerprint matching using minutiae and texture features.Proc.ICIP 2001,Vol.3, Greece,Oct 2001,pp 282-285)中采用与上述思路类似的编码加上细节点信息进行指纹识 别,都获得了一定的效果,但其问题是需要存储空间非常大,造成应用的障碍。改进效果也 不是很理想。本发明方法则利用方向图作为新的指纹表示的特征,将方向图用模型表达,只 需存储少量参数;在指纹识别时将细节点和方向图模型参数一同使用,所需增加的存储空间 远远小于前述方法,而且特征更稳定可靠。而且由于方向图在指纹识别多个步骤都要应用, 保存方向图参数有利于设计新的实用的技术方案。\n发明内容\n本发明的目的是提供多特征的实用的指纹表示方法及相应的识别技术,能够在存储指纹 特征时保存更多有用的信息供指纹比对时使用。本发明采用模型对指纹方向图进行描述,计 算出任意指纹的方向图模型参数;在指纹比对阶段,能够用存储的模型参数恢复指纹方向图, 进而进行任意两个指纹的方向图比对,再与细节点比对结果结合,从而达到提高传统识别方 法效果的目的。\n本发明的核心思想是将指纹识别中非常重要的方向图只用少量参数表达出来,这样就能 存储这些参数在比对阶段使用,与传统细节点识别方法结合就可以提高识别性能。在指纹中, 细节点反映的是指纹的细节特征,方向图反映的是全局特征,具有很大互补性。又因为方向 图除几个点(奇异点)外都是连续的,因此可以采用二元多项式和奇异函数的加权和来表达 方向图。采用最小二乘法能够求出上述模型的参数。采用传统的融合方法能够实现细节点特 征和方向图特征的结合。其中基于细节点特征的的识别方法可以选用目前使用的任何方法。 本发明仅对其中一种加以介绍。\n我们提出的指纹表示特征包括:奇异点(坐标),细节点(坐标,方向),方向图参数, 有效区域链码。传统方法主要使用前两种,我们则增加使用了方向图参数,有效区域链码。 这些特征与原有特征具有较大独立性,融合起来能够大大提高识别率。\n上述特征可以用定长编码方式存储。以下分别加以介绍:\n奇异点:即方向图不连续的点,分为中心点和三角点。一般中心点少于3个,三角点少 于3个。存储这些奇异点的x坐标,y坐标,每个坐标用一个字节存放(原因见细节点存储 部分)。所以共需12个字节。\n细节点:包括细节点的x坐标,y坐标和方向角度。为节省存储空间,存储实际值大小 的一半(以指纹图像大小(512×320)为例,存储的细节点和奇异点的坐标范围为0-255,方向 值的范围在0到180之间)。因此,一个细节点需要用3个字节表示。一般情况下,指纹的 细节点数量在100以下,所以最多需要300字节表示;\n方向图:方向图的模型参数。以混合模型为例,多项式模型部分一般取n为4,即用两 个四次二元多项式拟合,每个多项式系数为25个参数,所以多项式部分共有参数50个,用 float型(4字节)存储,需200字节;点电荷模型部分只需存储电量,也用float型存储,因 奇异点少于6个,共需24字节存储。\n有效区域:需存储指纹有效区域边界,采用十六边形表示方法,存储顶点x坐标,y坐 标,同细节点类似,存储实际坐标值的一半,共需32字节。\n综上,共需568字节存储指纹特征。如果不存储细节点方向值(可以从方向图特征推出), 则共需468字节。\n下面详细描述基于多特征的指纹识别算法。特征提取阶段的主要步骤包括:有效区域提 取,方向场估计,奇异点检测,方向图建模图像处理与增强,细节点提取;特征比较即识别 阶段的主要步骤包括:细节点比对,方向图比对,决策融合。其中,有效区域提取、方向场 估计、图像处理与增强、细节点提取和细节点比对等各步都可采用传统的方法进行。下面对 各步骤逐一介绍。\n特征提取\n有效区域提取\n通过取指器采集到的原始指纹图中指纹部分并不是充满全图,含有指纹的部分图像在指 纹识别中才有意义,称为有效区域。将原始图像分割为大小为(4×4)的方格,对每个这样的 方格,计算这一区域内所有象素的灰度值的均值与方差,只有两者均满足各自条件时才认为 该点处于有效区域。其中均值和方差的计算依靠下面的公式:\n\n\n这里,Iavg(i,j),Var(i,j)分别表示在以点(i,j)为左上角的方格的灰度均值和方差, I(i+x,j+y)为(i+x,j+y)点的图像灰度值。要求当th1<Iavg(i,j)<th2且Var(i,j)>th3时,标 记该方格为有效,标记为1。其中,阈值选择为:th1=20;th2=220;th3=6。\n对图像上所有的方格进行上述操作,为了去掉噪声影响,需要进行后处理:\n1、3×3滤波,具体做法就是检查包含被检测点在内的其3×3邻域内的9个点,如果只有 该点是有效的,其他都是无效的,那么认为该点为噪声,更改标记为0(表明无效);如果 只有该点是无效的,其他都是有效的,那么认为该点为有效点,更改标记为1(表明有效)。\n2、去掉有效区域中间的“洞”,方法是逐行扫描,填补图像中最左边和最右边的有效点 之间的所有无效点,将其标记为有效1;逐列扫描,填补图像中最上边和最下边的有效点之 间的所有无效点,将其标记为有效1。\n这样就得到了有效区域(长宽分别为原图的1/4)。如图11-2)。\n在基于方向场的比对中,有效区域起着重要的作用,因此需要进行保存。为节省存储空 间,我们采用一个十六边形来近似表示指纹图像有效区域。具体操作如下:\n求出真实有效区域的质心(x0,y0):\n\n其中,E代表有效区域,N代表有效区域内的点数\n从质心(x0,y0)处等角度的向四周16个方向(分别为0,π/8,π/4,…,15π/8)引射线,求出 这些射线与有效区域外边界的交点。具体实现的时候,只要检查射线上的点由有效变成无效, 则说明该点为边界交点。我们只需要存储这些交点的坐标,即十六边形的顶点,就可以恢复 出近似的有效区域。\n由图11-3)可以看出,用这种方法表示的有效区域与真实有效区域基本一致。实验结 果也表明,两者的差别对后面的比对影响极小。\n方向场估计\n方向场是表示指纹脊线走向的一幅图像,其中每点的数值代表了指纹图像中对应点的局 部脊线方向。方向图刻画了指纹的全局信息,在指纹识别中起着重要的作用。本方法中采用 的是基于梯度统计的算法,效果如图11-7)所示。算法如下:\n1、利用Soble算子的水平方向算子Sx和竖直方向算子Sy(见图4)求取点(x,y)的灰度梯 度:\n水平方向: \n竖直方向: \n其中I(i,j)为(i,j)点的灰度值。\n2、把指纹图划分成大小为 的方格, 用下式求取每一方格对应的局部方向θ:\n\n方向场置信度\n方向场置信度是方向场估计的进一步结果。对于方向场中的每一个点,计算其周围一个 小邻域内方向场的一致性,并将其作为该点的可靠性度量,称之为方向场置信度。它的取值 在[0,1]之间。方向场置信度在一定程度上反映了局部图像质量,图像质量越好的区域, 方向场置信度越高,图像质量越差的区域,方向场置信度越低。效果如图11-8)所示。求 取方法如下:\n\n\n其中c(i,j)即点(i,j)的方向场置信度, \n方向场置信度在下面将要提到的方向图建模操作中将作为加权系数使用,具体方法在该 步骤有详细说明。\n奇异点检测\n利用Poincare指数方法在方向场上进行奇异点检测,根据的原则是:普通点的Poincare 指数为0,中心点的Poincare指数为1/2,三角点的Poincare指数为-1/2。点(i,j)上的 Poincare指数的计算过程如下:\nΨx(k)和Ψy(k)分别表示以给定点为中心的半径为8的圆(圆上共有Nψ=25个象素点) 上的第k个点的横、纵坐标。圆上相邻两点的方向变化为:\n\n其中:δ(k)=O(Ψx(k′),Ψy(k′))-O(Ψx(k),Ψy(k));\nk′=(k+1)modNψ;\n这里O(·)表示指纹图像的方向场(值域为[0,180))。\n点(i,j)上的Poincare指数为:\n\n方向场建模\n指纹方向场反映出指纹的全局性信息,对指纹识别非常重要。通常采用的是基于梯度的 方法,它有两个弊病:1、求出的方向场受噪声影响较大;2、不能直接存储方向图,原因是 所需空间过大。因此需要对指纹方向场进行建模,这样可以使求得的方向图更加可靠,并且 需要的存储空间也会非常小。我们采用的混合模型包括两部分,一部分是多项式模型,即对 整个指纹的方向场,用两个二元n次多项式来刻画;另一部分是点电荷模型,即对靠近奇异 点的不在光滑区域的方向场,用标准电荷模型来修正,模型如下:\n\n其中R(x,y)、I(x,y)是混合模型在点(x,y)的取值,PR(x,y)、PI(x,y)是多项式模型在点 (x,y)的取值,H1(k)(x,y)、H2(k)(x,y)是第k个奇异点对应的点电荷模型在点(x,y)的取值; αPC(k)(x,y)表示第k个奇异点对应的点电荷模型在点(x,y)处的权重,计算公式为: R(k)是第k个奇异点对应 的点电荷模型的有效半径,(x0(k),y0(k))是第k个奇异点的坐标;多项式模型在混合模型中的 权重为 \n在中心点附近点(x,y)上的标准点电荷模型为:\n\n其中(x0,y0)是中心点坐标,Q是点电荷电量,R是点电荷影响有效半径,i是虚数单位\n\n在三角点附近,点(x,y)上的标准点电荷模型则为\n\n其中(x0,y0)是三角点坐标,其他符号意义同上。\n模型参数求取步骤如下:\n1、利用公知的加权最小二乘方法,最小化 和 来求解出两个二元四次多项式PR(x,y)、PI(x,y)的系数。\n其中(x,y)是指纹有效区域中任意一点,c(x,y)为点(x,y)的方向场置信度,θ(x,y)为(x,y) 点方向场估计得出的角度。\n2、求解点电荷模型参数\n2.1利用1中求出的多项式模型,求出该模型在各奇异点处的值PR(x0,y0)、PI(x0,y0), 然后利用cos 2θ′(x0,y0)=PR(x0,y0)以及sin 2θ′(x0,y0)=PI(x0,y0)可以反求出θ′(x0,y0),它 可以看作是点电荷模型相对于标准模型的旋转角度:\n\n则旋转后的中心点对应的点电荷模型中的H1、H2可以表示为:\n\n\n三角点对应的电荷模型中的H1、H2为:\n\n\n以上四式中各量含义与前文相同。\n2.2将求得的点电荷模型表达式代入混合模型公式,应用最小二乘法求出各点电荷的电 量,即求解下列的优化问题:\n\nΩ是点电荷起作用区域的点集合,如图9所示。\n多项式模型与点电荷模型及二者混合的结果参见图10。\n图像增强\n图像增强算法采用Gabor滤波方法,即根据各点方向场取值,用Gabor滤波器进行滤波。 滤波后效果如图11-4)所示。滤波算法如下:\n1、求取指定大小的空域掩膜:\nGabor滤波器空域表达形式为\n 其中 \n这里θ∈[0,180)为当前点的方向场垂直方向,x,y为掩膜中各点相对于掩膜中心点的坐 标。各参数取δx′=δy′=5.0,f=0.6,空域掩膜大小为7×7像素。由于对于相同的θ,空域掩 膜是相同的。所以可以在滤波之前将空域掩膜一次求取完成并存储下来,以减少不必要的重 复计算。\n2、自适应滤波:\n对于指纹图像中的点(i,j),假设输入指纹灰度图像为I(x,y),θ为(i,j)点方向场方向垂 直的方向,则用上述滤波器滤波如下:\n 其中W=3;\n然后按下式求取一个数值:\n\n其中L=12为统计数据区域长度,D=2为统计步长,进行脊线提取:如果 F(i,j)>flag(i,j),则(i,j)点位于谷(背景),否则位于脊(前景)。\n细节点提取\n细节点可分为两种,一种是脊线的端点,另一种是脊线的分岔点,如图2所示。细节点的 提取方法我们采用的是基于细化图的方法。分别对前景和背景进行细化,得到两张细化图。 最终结果如图11-5、6)所示。\n具体的细化方法如下:\n对增强后的指纹图像,我们将其二值化(直接选择阈值为128即可)。每个点取值为1 或者0,1表示前景;0表示背景。细化的目标就是考察每一个值为1的点,根据其8邻域的 取值来决定是否将这个待考察的点置为0(即将该点变成背景),通过对全图的几次遍历, 不断将一些前景(值为1)的点变成背景点,从而达到细化的目的。\n我们根据待测点8邻域的不同状态来决定待测点的“去”或“留”。这8个邻域点的所 有可能取值组合有28=256种(每个点只能取1或者0)。我们将每种可能设定为一条规则对 应结果为“1”(保留)或“0”(去除),规则设定的原则是保持原图的骨架。对于指纹脊 线细化,我们定义的骨架,可以理解为图像的中轴,例如一个长方形的骨架是它的长方向上 的中轴线,圆的骨架是它的圆心,环的骨架是类似圆的封闭曲线,直线的骨架是它自身,孤 立点的骨架也是自身。不同应用场合,对骨架的定义可能有不同,我们通过几个例子说明, 图8中给出了几个例子,其中:(1)不能删,因为它是个内部点,如果删去,就没有了骨架; (2)不能删,这是一个特殊要求,尽量保留直线;(3)不能删,这点是骨架,删掉后,改变拓 扑结构;(4)不能删,因为删掉后,原来相连的部分断开,改变拓扑结构;(5)不能删,因为 它是直线的端点;(6)可以删,该点不是骨架;(7)不能删,该点是骨架;(8)可以删,该点 不是骨架。我们简单总结一下,有如下的判据:(1)直线端点不能删除;(2)改变拓扑结构的 点不能删除,例如内部点不能删除、孤立点不能删除等。\n对所有情况按照上面的例子总结,可以得到256个规则,将其结果编码为一张表(其实 就是一个一维数组,标记0~255,共256个元素),每个待测点的8邻域的值对应一个0到 255的数,将这个数作为索引,查表中对应的值,如果是1表示保留;0表示该点被去掉(即 将这个待测点的值置为0)。\n索引方法如图7,Aij代表8个邻域中的点,索引定义为:\nindex=A32×20+A31×21+A21×22+A11×23+A12×24+A13×25+A23×26+A33×27\n按照索引值找到表table中对应的元素table[index],其中索引值index的取值范围在 [0,255]内的整数,如果table[index]为1,则保留该点(值不变);如果为0,则将该点 置0。我们采用的表如图6所示。从图8的八个例子中选出两个作说明如下:\n图8-2):中心(待测)点不能删,因为:\nindex=1×20+0×21+0×22+0×23+1×24+0×25+1×26+0×27=81,\ntable[81]=1,所以表示该点不能去掉。\n图8-8):中心(待测)点可以删,因为:\nindex=1×20+1×21+0×22+0×23+0×24+0×25+0×26+0×27=3,\ntable[3]=0,所以表示该点可以去掉。\n我们总结一下细化的步骤:\n第一步,给出索引方法,例如按照图7中设定的方法;\n第二步,根据规则给出索引表,例如按照图6中设定的表;\n第三步,遍历全图所有值为1的点,计算索引,判断是否保留;\n第四步,如果第三步没有去掉任何点,则下一步,否则重复第三步。\n第五步,后处理,我们将在下面详细介绍:\n求出细化图后的操作如下:\n第一步,按照细化图,初步确定细节点中的端点(本身为1且周围8个点中有且仅有一 个点为1)和分岔点(本身为1且周围8个点中有且仅有三个点为1)。\n第二步,沿着细节点生长,对细节点进行后处理:\n(a),对于端点,如果在其12×12的邻域内有另一个端点的方向与之接近(角度差小于30 度),则将这两个端点都去掉;\n(b),将形成环形的邻近分叉点连接起来,对于一个分叉点,如果在其12×12的邻域内有 另一个分叉点的方向与之接近(角度差小于30度),则将两者都去掉;\n(c),去除一些小短棒对应的两个端点,对于一个端点,如果沿着它所在脊线经过12个 像素之内就碰到另一个端点,则将两个端点都去掉;\n第三步,筛除方向与该点方向场角度差大于30度的特征点\n对所有注册指纹进行上述特征提取操作并将所得特征存入数据库,包括细节点的坐标和 方向值,混合模型中多项式模型的系数以及点电荷模型中点电荷的电量。\n特征比较\n首先对申请指纹进行上述的特征提取操作,再将其与数据库中注册指纹的特征进行比较。\n细节点比对\n细节点的比对过程分为细节点配准和细节点匹配两个步骤。\n由于用于比对的两枚指纹间存在旋转和平移,必须利用细节点配准的方法补偿旋转和平 移偏差。我们采用的是基于Hough变换的配准方法。简单解释为:将两个指纹的各自的细节 点分别构成两个点集(各有M和N个细节点),从两个点集中各选一个细节点分别表示为 (x1,y1,θ1)和(x2,y2,θ2),利用它们之间的坐标、方向可以求出一个平移量和旋转量: Δθ=θ2-θ1。遍历所有细节点对(共M×N对),将所有的平移和旋 转量进行投票,即统计(Δx,Δy,Δθ)出现的次数,得票最高的平移旋转量就是最终使用的平移 旋转量,同时记录得票数vote。\n根据下面的公式进行点的旋转平移变换:\nx″=x′×cos(Δθ)-y′×sin(Δθ)+Δx;\ny″=x′×sin(Δθ)-y′×cos(Δθ)+Δy;\n其中(x′,y′)是旋转平移前的坐标,(x″,y″)是旋转平移后的坐标。对于有效区域,分别对 应变换前的顶点坐标和变换后的顶点坐标;对于细节点,则分别对应配准前和配准后的坐标。\n将两枚指纹有效区变换之后就可以计算两枚指纹(记为r,t,并假设r为基准,t向r 旋转平移)之间的公共有效区域。求取方法如下:设两幅配准好的指纹有效区域分别为Rr、Rt, 则公共有效区域为Rc=Rr∩Rt,其中Rt是由指纹t的未配准的有效区域按上面求得的参数旋 转平移得到,实际上是旋转平移了十六个顶点的坐标。\n对于这两枚已经配准好的指纹,进行细节点比对。最终得出的是0~1之间的一个数,表 示两枚指纹细节点集合的相似度。当两幅配准好的指纹图中的两个细节点距离小于某一阈值 (取为8像素)时,认为这两个点比对成功,匹配成功点对计数加1。最终可以求出:\n\n其中count表示比对成功的细节点对数,countr表示指纹r在两幅指纹公共有效区域内 的细节点个数,countt表示指纹t在两幅指纹公共有效区域内的细节点个数。Th为经验阈值, 取为12。\n方向图比对\n首先按照基于细节点的对准方法对方向图进行对准。为了设计基于方向图的分类器,需 要定义两个方向图之间的距离度量。设Or,Ot分别为两幅已经对准的指纹的方向图,公共有效 区域为Rc(与细节点比对所用公共区域相同,不用重复求取),则这两幅方向图的距离为:\n\n其中,|Rc|为公共的有效区域面积,Oz(i,j)(z=r,t)为方向图由z中方向图模型恢复出 的点(i,j)的方向,。恢复方法如下:\n首先,按照方向场建模中给出的公式:\n\n计算出点(i,j)的R(i,j)、I(i,j),其中各符号意义与前文完全相同,然后根据下式恢复方向场:\n\nf(Or(i,j),Ot(i,j))为度量角度差的函数。选为指数函数:exp(-β×(|Or(x,y)-Ot(x,y)|%90)), 其中%表示取余数运算,β=10。\n为了与基于细节点的方法作融合,将距离转换为相似度。相似度=1-S(Or,Ot)。\n决策融合\n在分别利用细节点和方向图对指纹进行比对后,通过分类器融合可以得到最终的识别结 果。这两种特征从不同的方面刻画了指纹:细节点刻画了指纹局部的脊线分布特征;方向图 刻画了指纹全局的纹线走向。因此它们可以构成对指纹的更好的特征表示。在识别阶段,由 它们构造的分类器相辅相成,互为补充,例如:基于方向图的识别,可以克服传统的基于细 节点的识别方法因为细节点过少或假点过多而造成的误识别。我们在6616幅指纹数据库上的 实验表明,融合可以大幅度提高指纹识别的准确性和鲁棒性。决策融合的具体方法很多, 我们采用的融合策略如下。\n设采用细节点和方向图进行识别的输出分别为X1,X2(两个数),这两个识别过程可以看 为两个分类器,假设它们是相互独立的,即X1,X2相互独立,则它们的联合概率密度可以利 用两个分类器的概率密度相乘得到:\nP(X1,X2|w1)=P(X1|w1)P(X2|w1);\nP(X1,X2|w2)=P(X1|w2)P(X2|w2);\n其中,P(X1,X2|w1)表示在样本(X1,X2)(即一个输入指纹与一个参考指纹之间的两个 比对结果)属于w1类(即输入指纹与参考指纹实际上属于同一个手指)时的概率,P(X1,X2|w2) 表示在样本(X1,X2)属于w2类(即输入指纹与参考指纹实际上属于不同手指)时的概率。 P(X1|w1)表示属于w1类的指纹对,用细节点比对结果为X1的概率密度,P(X2|w1)表示属于 w1类的指纹对,用方向图比对结果为X2的概率密度,P(X1|w2)表示属于w2类的指纹对,用 细节点比对结果为X1的概率密度,P(X2|w2)表示属于w2类的指纹对,用方向图比对结果为 X2的概率密度。\n我们可以通过一定数量的训练样本,计算出“真实的指纹比对”和“虚假的指纹比对” 的概率分布,即P(X1|w1)、P(X2|w1)、P(X1|w1)和P(X2|w2)。方法采用Parzen窗进行非 参数估计,窗函数推荐采用高斯窗,对于一维分布,公式如下:\n\n其中 N′为训练样本个数,视实际数据量而定,推荐2000以上;hN 为窗宽,取为0.02;xi为第i个训练样本的比对结果。具体算法如下:\n将相似度的[0,1]区间100等分,令上式中的x分别取0,0.01,0.02,…,1(实际计算出的相似 度要按照这个精度进行近似),按照上式计算细节点比对相似度的类条件概率密度P(X1|w1)、 P(X1|w2)和方向图比对的类条件概率密度P(X2|w1)和P(X2|w2),这四个量计算中存储为四 个包含101个元素的数组,用float型(4字节)存储,共需要1616字节。最后写成文件,以 用于后面的在线决策融合过程。在线的决策融合只需要从文件中读取相应的数值,计算出联 合概率密度即可,不需要在线估计概率密度。\n在线应用时,得到两个指纹之间细节点比对的相似度和方向图比对的相似度后,利用事 先估计出的P(X1|w1)、P(X1|w2)、P(X2|w1)和P(X2|w2)得到P(X1,X2|w1)和P(X1,X2|w2)。 再采用下面的分类器判断这两个指纹是否属于同一手指(即属于w1类还是w2类):\n\n其中λ为似然比阈值,根据实际要求选择。推荐使用25。\n实验表明,按照上述参数设置,指纹识别系统的错误接受率(即将其他手指的指纹认为 是这个手指的)一般在0.01%附近,而错误拒绝率(将同一手指的指纹认为是其他手指的) 在10%-20%之间,比单用细节点比对时可以降低10%左右。λ增大会使FAR减小,同时使FRR 增大。实际使用中应适当权衡。\n附图说明\n图1两枚不同指纹,但细节点比对上25个;\n图2是多特征指纹识别系统的组成;\n图3是指纹多特征提取的流程;\n图4为Sobel算子,1)为水平方向算子,2)为竖直方向算子。\n图5为细节点与奇异点的类型,1)为细节点,其中点(1-1)为端点,点(1-2)为分 叉点,2)为奇异点类型,点(2-1)为中心点,点(2-2)为三角点;\n图6为细化索引表;\n图7为细化索引建立方式示意图;\n图8是细化的八个例子;\n图9是点电荷模型起作用区域,C1,C2表示两个中心点,D1,D2表示两个三角点:\n图10是混合模型计算中的中间结果,其中,1)是多项式模型拟合结果,2)是点电荷模 型结果,3)是多项式模型与点电荷模型混合的结果;\n图11是指纹识别各步骤中间结果,其中,1)是原始指纹图,2)是原始有效区域,3) 是用十六边形表示的有效区域,4)是位于有效区域内增强的指纹图(以下各图均在有效区域 内),5)是对“脊”(前景)的细化图,6)是对“谷”(背景)的细化图,7)是用基于梯 度的方法求得的方向场图,8)是方向场置信度的灰度级表示,灰度级越高(越亮)表示该点 方向场置信度越高,9)是用混合模型拟合得出的方向场图,10)是最终求得的细节点在指纹 图像中的位置(为突出细节点位置,对指纹图像作了弱化)。\n图12是单纯使用细节点和使用多特征的系统性能对比。\n具体实施方式\n我们的发明已在普通PC计算机上实现,对操作系统没有要求。\n本发明的特征在于,它依次含有以下两个阶段:\n注册阶段,计算机在离线状态下对所有注册的指纹进行特征提取和存储,这个阶段依次 含有以下步骤:\n(1).对计算机进行初始化:\n设定:用以下多特征表示指纹:\n奇异点,即方向场不连续的点,它包含:\n中心点:少于三个;\n三角点:少于三个;\n奇异点的X坐标,Y坐标各用一个字节存放,共12个字节;\n细节点,包括它的X、Y坐标和方向角度,每个细节点用3个字节表示,细节点数小 于100,最多存入300字节;\n方向图,使用混合模型,它含有:\n多项式模型部分:用两个二元四次多项式拟合,n=4,每个多项式系数是25个参数, 共计50个,用4字节的float型存储,共200字节;\n点电荷模型部分,用float型存储,在奇异点数小于6个时,共24字节;\n有效区域链码,用十六边形表示指纹有效区域边界,存储16个顶点的X、Y坐标,共 32字节;\n存储以上四个指纹特征共占用568字节;\n在指纹有效区域的检测步骤中,对于已经按4×4大小方格分割的原始指纹图像而言, 当以点(i,j)为左上角的一个方格内的灰度均值Iavg(i,j)和方差Var(i,j)处于下述范围内 时,该方格为有效,标记为1,否则无效,标记为0,即:\nth1<Iavg(i,j)<th2且同时Var(i,j)>th3;\n其中th为阈值,th1=20,th2=220,th3=6;\n在方向场估计的步骤中,方向场一致性水平的上限值为Tc=1.5;\n在方向场建模的步骤中,多项式模型中多项式阶次为4,中心点处点电荷模型有效作 用半径为10像素,三角点处点电荷模型有效作用半径为15像素;\n在图像增强的步骤中,Gabor滤波器空域表达形式G(x,y,θ)中的参数值 δx′=δy′=5.0,f=0.6,空域掩模大小为7×7像素;\n(2).计算机通过取指器采集所有注册指纹的原始图像并存储;\n(3).检测指纹的有效区域,它依次含有以下步骤:\n(3.1)把原始图像分割成大小为4×4像素的方格;\n(3.2)计算机按下式计算以点(i,j)为左上角的一个方格内的灰度均值Iavg(i,j)和方 差Var(i,j):\n\n\n其中I(i+x,j+y)为(i+x,j+y)点的图像灰度值;\n(3.3)计算机按下式判断上述每一个方格是否有效:\n若th1<Iavg(i,j)<th2且同时Var(i,j)>th3,则该方格有效,标记为1,否则为0;\n(3.4)消噪声处理:\n(3.4.1)对上述图像进行3×3滤波,即对图像上所有的点,检查其3×3邻域内9 个点,若只有该点是有效的,而其它8个点是无效的,则该点判断为噪声,标记 改为0;若只有该点是无效的,而其他8个点是有效的,则该点标记改为1;\n(3.4.2)去掉有效区域中的“洞”:即逐行对上述图像扫描,填补最左边和最右边 的有效点之间的所有无效点,把它们的标记为有效;逐列扫描,填补最上边和最 下边的有效点之间的所有无效点,把它们的标记为有效;\n这样得到了指纹图像的有效区域,长、宽分别为原图的1/4;\n(3.5)求取真实的有效区域的质心(x0,y0):\n \n其中,E代表有效区域,N代表有效区域内的点数;\n(3.6)从质心(x0,y0)处等角度地向四周16个方向引射线,求出这些射线与有效区域 外边界的交点,并存储;\n(4).用基于梯度统计的算法进行方向场估计,它依次含有以下步骤:\n(4.1)利用Soble水平方向算子Sx和竖直方向算子Sy求取点(x,y)的灰度梯度:\n水平方向: \n竖直方向: \nI(i,j)为(i,j)点的灰度值;\n(4.2)把指纹图划分成大小为 的方格, 用下式求取每一方格对应的局 部方向θ:\n\n(4.3)计算方向场置信度,取值在[0,1]之间,对于方向场中的每一个点,计算其 周围 大小的一个邻域内方向场的一致性,其中 即:\n\n\n其中c(i,j)即点(i,j)的方向场置信度;\n(5).用Poincare指数法在方向场上进行奇异点检测:\n设:Ψx(k)和Ψy(k)分别表示以给定点即所求点为中心的半径为8个像素的圆上的第 k个点的横、纵坐标,圆上共有Nψ=25个象素点;\n则圆上相邻两点k′、k的方向变化为:\n\n其中:δ(k)=O(Ψx(k′),Ψy(k′))-O(Ψx(k),Ψy(k));\nk=(k+1)modNψ;\nO(·)表示该指纹图像k′或k点的方向场在[0,180)之间;点(i,j)上的Poincare 指数可以用下式表示:\n\n当Poincare指数为0时,给定点为普通点;当Poincare指数为1/2时,给定点为中 心点;Poincare指数为-1/2时,给定点为三角点;\n存储奇异点的检测结果;\n(6).建立方向场混合模型,计算混合模型的模型参数,即多项式系数和点电荷电量;\n(6.1)对有效区域内所有点,利用公知的加权最小二乘方法,分别最小化 和 求解出两 个二元四次多项式PR(x,y)、PI(x,y)中各项的系数;其中(x,y)是指纹有效区域中任意 一点,c(x,y)为点(x,y)的方向场置信度,θ(x,y)为步骤(4)中在(x,y)点方向场估计 得出的角度;\n(6.2)求解点电荷模型参数:\n(6.2.1)利用(6.1)中求出的多项式模型,求出该模型在各奇异点(x0,y0)处的值 PR(x0,y0)、PI(x0,y0),然后根据下式计算出点电荷模型的旋转角度θ′(x0,y0):\n\n中心点(x0,y0)附近满足 的点(x,y)上的点电荷模型 为:\n\n\nQ是待求的中心点点电荷电量,R是已经给定的中心点点电荷影响有效半径; 在三角点(x0,y0)附近满足 的点(x,y)上的点电荷模型 为:\n\n\nQ是待求的三角点点电荷电量,R是已经给定的三角点点电荷影响有效半径;\n(6.2.2)应用最小二乘法求出各点电荷的电量,即求解下列的优化问题:\n\n其中Ω是点电荷起作用区域的点集合,R(x,y)、I(x,y)是混合模型在点(x,y)的取 值,按照如下公式求取:\n\n其中PR(x,y)、PI(x,y)是多项式模型在点(x,y)的取值,H1(k)(x,y)、H2(k)(x,y)是 第k个奇异点对应的点电荷模型在点(x,y)的取值;αPC(k)(x,y)表示第k个奇异点 对应的点电荷模型在点(x,y)处的权重,计算公式为: R(k)是第k个奇异点对应的点电荷模 型的有效半径,(x0(k),y0(k))是第k个奇异点的坐标;多项式模型的权重为 \n(7).用Gabor滤波方法增强图像,其步骤如下:\n(7.1)Gabor滤波器空域表达形式为:\n 其中 \nθ∈[0,180)为当前点的方向场垂直方向,x,y为掩膜中各点相对于掩膜中心点的坐 标,δx′=δy′=5.0,f=0.6,空域掩膜大小为7×7像素;\n(7.2)自适应滤波:\n假设输入指纹灰度图像为I(x,y),θ为(i,j)点方向场方向垂直的方向,则用上述滤 波器滤波如下:\n 其中W=3;\n然后按下式求取一个数值:\n 其 中L=12为统计数据区域长度,D=2为统计步长,进行脊线提取:如果 F(i,j)>Flag(i,j),则(i,j)点位于谷,即背景,否则位于脊,即前景;\n(8).基于细化图的细节点提取和存储,它依次包含以下步骤:\n(8.1)在保持原图的骨架即不改变拓扑结构和不删除直线端点的前提下,根据以待测 点为中心的8邻域的不同状态来决定待测点的“去”或“留”,“去”用“0”表示, “留”用“1”表示;\n(8.2)建立一维索引表table,标记索引为0~255,共256个元素,每个元素取1表 示保留,0表示去掉;\n(8.2)遍历有效区域内所有点,考察其8邻域,对所有排列组合通过下面的公式映射 到0~255之间:\nindex=A32×20+A31×21+A21×22+A11×23\n +A12×24+A13×25+A23×26+A33×27;\n其中,Aij代表8个邻域中的点的值,然后通过查询索引表中索引值为index的元素 即table[index],决定该待测点是否保留或者去掉;\n(8.4)重复(8.3)直到没有被去掉的点出现;\n(8.5)细化后处理:\n(8.5.1),按照细化图,初步确定细节点中的端点,即本身为1且周围8个点中 有且仅有一个点为1的点;分岔点,即本身为1且周围8个点中有且仅有三个点 为1的点;\n(8.5.2),沿着细节点生长,对细节点进行后处理:\n(8.5.2.1),对于端点,如果在其12×12的邻域内有另一个端点的方向与之接 近(角度差小于30度),则将这两个端点都去掉;\n(8.5.2.2),将形成环形的邻近分叉点连接起来,对于一个分叉点,如果在 其12×12的邻域内有另一个分叉点的方向与之接近(角度差小于30度),则将两者 都去掉;\n(8.5.2.3),去除小短棒对应的两个端点,对于一个端点,如果沿着它所在 脊线经过12个像素之内就碰到另一个端点,则将两个端点都去掉;\n(8.5.3),筛除方向与该点方向场角度差大于30度的特征点;\n对所有注册指纹进行上述特征提取操作(1)~(8)并将所得特征存入数据库,包括细节点的 坐标和方向值,混合模型中多项式模型的系数以及点电荷模型中点电荷的电量;\n验证阶段:\n(1)~(8)与注册阶段相同\n(9)细节点比对\n(9.1)用基于Hough变换的西节点配准方法补偿旋转和平移偏差,即把两个指纹各自 的细节点分别构成各自含有M和N个细节点的点集,从两个点集中各选一个细节点分 别表示为(x1,y1,θ1)和(x2,y2,θ2),利用它们之间的坐标、方向求出一个平移量: 一个旋转量:Δθ=θ2-θ1,遍历所有M×N对细节点对,统计 (Δx,Δy,Δθ)出现的次数,得票最高的平移旋转量就是最终使用的平移旋转量,同时记 录得票数vote;\n下面用到的坐标变换都可以由下面的公式实现:\nx″=x′×cos(Δθ)-y′×sin(Δθ)+Δx;\ny″=x′×sin(Δθ)-y′×cos(Δθ)+Δy;\n其中(x′,y′)是旋转平移前的坐标,(x″,y″)是旋转平移后的坐标;\n(9.2)公共有效区域提取:\n记注册指纹r和申请指纹t配准后的有效区域分别为Rr、Rt,设以r为基准,t 向r旋转平移,则公共有效区域为Rc=Rr∩Rt,其中Rt是由指纹t的有效区域按(9.1) 求得的参数旋转平移得到,具体是按(9.1)中公式旋转平移十六边形的十六个顶点的 坐标实现;\n(9.3)按(9.1)中公式旋转平移指纹t中所有细节点的坐标,并将其与指纹r中所有细 节点进行比对,记录比对成功即距离小于8像素的细节点的对数;\n(9.4)计算指纹r,t细节点集合的相似度Mrt,0<Mrt<1:\n\n其中count表示比对成功的细节点对数,countr表示指纹r在两幅指纹公共有效区域 内的细节点个数,countt表示指纹t在两幅指纹公共有效区域内的细节点个数,Th为 经验阈值,取为12;\n(10)方向图比对:\n(10.1)按照(6)中给出的公式:\n\n计算出点(x,y)的R(x,y)、I(x,y),其中各符号意义与(6)完全相同,然后根据如下公 式恢复出方向图:\n\n按照细节点配准得出的参数进行方向图的对准,即将指纹t的方向图中各点的坐标按 照(9.1)中确定的参数根据(9.1)给出的公式进行变换;\n(10.2)设Or,Ot分别为两幅已经对准的指纹的方向图,有效区域即为(9.2)中Rc,不用 重复求取;\n(10.3)按下式计算两幅方向图Or,Ot的距离:\n\n其中,|Rc|为公共的有效区域面积,Oz(x,y)(z=r,t)为方向图z中点(x,y)的方向, f(Or(x,y),Ot(x,y))为度量角度差的函数,选为指数函数: exp(-β×(|Or(x,y)-Ot(x,y)|%90)),其中%表示取余数运算,β=10;\n(10.4)相似度=1-S(Or,Ot);\n(11).用分类器进行决策融合:\n首先定义w1类事件为输入指纹与参考指纹实际上属于同一个手指的情况;w2类事件 为输入指纹与参考指纹实际上属于不同手指的事件;\n(11.1)概率密度估计过程:\n令:\nP(X1|w1)表示:属于w1类的指纹对,用细节点比对结果为X1的概率密度;\nP(X2|w1)表示:属于w1类的指纹对,用方向图比对结果为X2的概率密度;\nP(X1|w2)表示:属于w2类的指纹对,用细节点比对结果为X1的概率密度;\nP(X2|w2)表示:属于w2类的指纹对,用方向图比对结果为X2的概率密度;\nP(X1|w1)、P(X2|w1)、P(X1|w2)和P(X2|w2)用 表示,并用如下公式求取:\n\n其中 N′为训练样本个数,即相应的比对结果的个数,四组 数据数量推荐均在2000以上,这些比对是离线进行的;hN为窗宽,取为0.02;x分 别取0,0.01,0.02,…,1,即将相似度的区间[0,1]100等分,分别按照上式计算 P(X1|w1)、P(X2|w1)、P(X1|w2)和P(X2|w2),这四个量计算中存储为四个包含101 个元素的数组,用float型(4字节)存储,共需要1616字节;最后写成文件;\n(11.2)在线决策过程:\n按照细节点和方向图比对得出的结果比对的结果( X1′,X2′),从存储概率密度的文件 中读取相应的数值,计算出联合概率密度:\nP(X1′,X2′|w1)=P(X1′|w1)P(X2′|w1),\nP(X1′,X2′|w2)=P(X1′|w2)P(X2′|w2),\n运用下述决策规则进行决策:\n若 则判定指纹属于同一手指;\n若 则判定指纹属于不同手指;\n其中λ是决策阈值,选用25。