一种新的指纹奇异点快速检测方法一种新的指纹奇异点快速检测方法摘要：摘要：作为指纹最重要的全局特征之一，奇异点在基于模型的方向场计算、人工合成指纹、指纹分类、指 纹特征匹配等方面发挥了非常重要的作用。在指纹方向场分割的基础上提出了一种称之为方向丰富度的特 征，并据此形成了一种新的指纹奇异点快速检测方法。该方法首先将指纹方向场分割为一系列互不重叠的 同质区域；然后通过同质区域边缘检测及边缘端点提取实现了奇异点快速定位；最后依据奇异点处方向丰 富度特性判断其类型。实验验证了本文算法的有效性。关键词：关键词：指纹；奇异点；方向场；分割1 引言引言生物特征识别技术是根据每个人独有的可以采样 和测量的生物学特征和行为学特征进行身份识别的技 术。由于生物特征不像各种证件类持有物那样容易窃 取, 也不像密码、口令那么容易遗忘或破解, 所以在 身份识别上体现了独特的优势, 近年来在国际上被广 泛研究。自动指纹识别系统(AFIS)由于其体积小，成 本低，易操作，可靠性高等优点越来越受到人们的青 睐，成为最重要的生物识别技术之一。 作为指纹最重要的全局 特征之一，奇异点在基于模 型的指纹方向场计算1-3、人 工合成指纹4-5、指纹分类6-7、指纹特征匹配8等方面发挥了非常重要的作用。奇异 点被定义为方向不连续的 点，文献9给出了两种类 型描述：core点为最内部弯 曲纹线处的最高点或最低 点，delta点为三条不同纹线 汇合形成的三角区域。图1给出了一对典型的core 点 和delta 点。 迄今为止，已有大量的指纹奇异点检测方法被提 出，从宏观上，可以将其分为以下几类： 1) 基于poincare index的方法7,10-12，此类方法通 过计算围绕一个点的封闭曲线上的方向变化累计量来 确定该点的poincare index值，当值为1/2、-1/2时分别 对应core点和delta点。该类方法思路简单、能较好地 确定奇异点的位置及类型，因此成为目前运用最为广 泛的指纹奇异点检测算法。但由于需要计算每个点的 方向变化累计量，计算效率并不高，同时存在如何选择最佳窗口形状及尺寸(虽然文献11采用多尺度窗口 来解决窗口尺寸的问题，并获得了较好的结果，但该 文也指出其增加了计算量，降低了运行效率)等问题。 2) 基于点方向概率分布的方法。此类方法通过观 测一个区域内的方向分布情况来确定该区域内是否有 奇异点，典型的方法包括Parzen window方法13、方向 直方图方法14、muiti-space KL方法15及ridge flow codes方法16等。以上方法能确定奇异点的位置信息， 但由于不能判断类型信息，因此不能称之为完整的解 决方案。文献17提出了基于指纹二值图像的点方向 场计算方法，并在点方向场的基础上定义了一种称之 为fault lines，并指出fault lines相交处即为指纹奇异点， 最后提出了基于SEA算法的奇异点检测方案，但该工 作没有给出理论或实验证明其提取的奇异点是否为公 认的奇异点。 3) 基于形态分析的方法。该类方法通过对纹线或 方向的形态进行分析，将类似于或的区域，确 定为core点；类似于的区域定为delta点，典型的方 法包括文献18,19等。此类方法的计算复杂度较高， 抗噪声能力也较差。 4) 其它类方法。如文献20提出的基于Gaussian- Hermite矩及主成分分析的方法、文献21提出的基于 角点检测及纹线跟踪的方法等。该类方法也同样存在 运算复杂、效率较低的问题。 一个好的指纹奇异点检测算法应具备以下几点要 求： 1) 能准确定位出奇异点的位置并判断相应的类型 (core点或者delta点)； 2) 具有较低的漏检率(未检测到已有奇异点的概 率)和误检率(将非奇异点误识为奇异点的概率)； 3) 简单实用，运行效率高。 其中前两点分别强调算法的功能性及准确性，第Fig.1. core point and deltapoint in fingerprint图1 指纹图像中典型的core 点和delta 点三点强调的是实用性。目前，绝大多数算法都把工作 的重心放在前两点，尤其是为了追求准确性而追加了 许多繁杂的额外开销，使得算法的实用意义并不明显。 对于自动指纹识别系统中的算法，简单实用性显得尤 为重要，因为指纹识别包括两个非常有意义的运用方 向：大库识别(指纹库达到百万甚至千万以上的数量级)、 基于嵌入式系统的识别(识别系统运行于运算能力较低 的单片机上，如门禁系统)。 受文献17工作的启发，本文在指纹方向场分割 的基础上提出了一种称之为方向丰富度的特征，并据 此形成了一种新的指纹奇异点快速检测方法。大量实 验表明：与目前占据绝对主流的poincare index方法相 比，在准确性方面，两者各有优、缺点，本文方法的 误检率明显低于后者，漏检率略高于后者；在简单实 用性方面，本文算法的平均运算速度是后者的17.4倍， 具有明显优势；与文献17算法相比，本文算法的误 检率及漏检率均低于文献17算法，且本文算法的平 均检测速度是其2.2倍。2 方向场计算方向场计算绝大多数指纹奇异点检测算 法都是在指纹方向场的基础上进 行的，本文也不例外。本节将简 单介绍指纹方向场计算方法，为 详细阐述后面的工作做好铺垫。 在文献22的基础上，通 过引入新的窗口模版(如图2所 示)，形成了本文所采用的方向 场计算方法，其大致过程如下：() 对于指纹图像，根据式(1)分别计算每个像I 素点点沿，方向的梯度向量；XY(1) TT yxyyxIxyxIyxGyxG ),(,),(),(),() 将整幅图像分割成一系列互不重叠的大小为的内层块，为每个内层块分配一个具有共同ininWW 中心点，大小为的外层窗口，根据式(2)、outoutWW(3)分别计算每个内层块梯度向量及块一致性，同时统 计每个内层窗口所对应的外层窗口中所含有的有效点 梯度向量(即非 0 向量)的个数；(2)TWxWyWxWysysxT ByBxoutoutoutout yxGyxGGinGin 1111),(),(,(3) outoutoutoutWxWysysxWxWysysxB yxGyxGyxGyxGCohin1111),(),(),(),(其中， ),(),(2),(),( ),(),(22yxGyxGyxGyxG yxGyxGyxyxsysx() 确定块一致性阀值及有效点个数阀值，对每个内层块，若其块一致性或者有效点个数小于相 应得规定阀值，则将该块的块梯度向量置为0向量；() 对每个块梯度向量为0向量的内层块，采用 文献21中基于迭代的方法，重新估计其块梯度向量；() 依据式(4)将每个内层块的梯度向量转化为 块方向。(4) 00 )(tan00 )(tan0 )(tan21211 -1 -1ByBxBxByByBxBxByBxBxByGinGinGinGinGinGinGinGinGinGinGinII图3给出了一组该方法计算出的方向场结果图(其中，)，3inW21outW3 . 06outoutWW可以看出该方法计算出的结果更加平滑，方向的连续 性较好，为后面的方向场分割奠定了良好的基础。Fig.2. The new template图 2 新的窗口模版(a) (b) (c)(d) (e) (f)Fig.3. The orientation results calculated by our method. (a)(c) are original images, (d)(f) are the corresponding orientation results.图3 本文算法计算出的方向场结果图。(a)(c)为原始指纹图像，(d)(f)为相应的方向场结果图(每个点的方向值乘以80后所对应的灰度图象)3 基于方向场分割的指纹奇异点快速检测方法基于方向场分割的指纹奇异点快速检测方法基于已有指纹奇异点检测算法的分析可以发现： 本质上，各种算法都是通过提取指纹奇异点处的某种 特有特征来实现检测的，特征的鉴别能力、稳定性及 易提取性直接决定了该算法的功能性、准确性和简单 实用性。本文在指纹方向场分割的基础上提出了一种称之 为方向丰富度(Orientation Abundance Degree, OAD)的 新特征，并据此形成了一种简单、有效的指纹奇异点 快速检测方法。该方法的主要过程包括：指纹方向场 分割；奇异点定位；奇异点类型判断。 以下将详细阐述每个步骤的内容，首先给出一组 相关定义：定义定义1(同质区域). 将指纹图像中点处的方),(yx向记为，则同质区域为所有满足),(yxO),(的点所构成的集合，即),(yxO,0 ;),(),(),(yxOyx定义定义2(同质区域排序). 按照同质区域所表示的角 度大小进行的排序，其精确描述为： 假设指纹方向场被分割为个互不重叠的同质区n域，记第 ()个同质区域为，若将同质区ini 1i域的升序排列描述为： niLL,21则该排列满足：1),( ,),(jjdcba),(),(dcObaO其中，。11nj定义定义3(方向丰富度). 以点为圆心，为半),(yxr径构成的圆形区域内所包含的同质区域的),(ryxR子区域构成的集合，其精确描述为：记同质区域的子区域为，则ii),(;),(ryxRyxOADiiii图4给出了将图3中(d)(f)的方向场划分为4个同质区域的结果图(其中，灰度值由小到大分别表示， )4, 0(，)，从结果图中可以较为明 )2,4( )43,2( ),43(显地观测到所有同质区域向奇异点处汇集的趋势。同 时，图4亦给出了奇异点处方向丰富度被放大后的效 果图(其中标号1、2、4、5为core点处的方向丰幅度效 果图，标号3、6为delta点处的效果图)。 基于已展示的奇异点处的方向丰富度效果图及大 量相同实验结果的观察，可以总结出以下两条规律： 规律一：规律一：指纹奇异点处的方向丰富度包含的子区 域分别来源于所有的同质区域，即UniiSPOAD1规律二：规律二：core点处的方向丰富度所包含的子区域 以core点为中心，在顺时针方向呈现升序排列(在图4 中表现为子区域的灰度值由小到大变化)；与此同时， delta点处在逆时针方向表现出升序排列。上述两条规律分别构成了利用方向丰富度进行奇 异点定位及类型判断的基础。 为了充分验证利用方向丰富度检测奇异点的功能 可靠性，以下给出严格的证明。 证明一证明一：分析过程：分析过程：文献12给出了改进的poincare index计算公式，如式(5)所示：(5)10)(21),(Nkkjipoincare其中，otherwisekkifkkifkk)(2)( )(2)( )()(),(),()(mod)1(mod)1(kkNkNkyxyxk是以给定点为中心的具有个像素的),(kkyx),(jiN封闭曲线上沿第个点的坐标， ，k1, 2 , 1 , 0NkL在上沿顺时针1递增。若poincare index的值为，则给定点21),(ji为core点，若值为，则为delta点