基于连续方向场的多尺度指纹奇异点检测算法

1、基于连续方向场的多尺度指纹奇异点检测算法汤婷,孙林森,吴小培安徽大学计算机科学与技术系，合肥 (230039）（）摘 要:本文在连续方向场的基础上，对经典Poincaré Index公式进行了改进，结合点方向场和块方向场，提出了一种基于多尺度的指纹奇异点检测算法。传统基于点方向场的奇异点检测精度较高，但是速度较慢，且对于低质量的指纹图像容易误判；传统基于块方向场的奇异点检测不会发生误判，但是精度不高。本文将二者有机结合起来，既实现了指纹奇异点检测的精度，又避免了误判现象。关键词:指纹；奇异点检测；方向场；Poincaré Index中图法分类号 TP391.411 引 言每

2、个人的指纹各不相同，指纹因具有终生的稳定性、可靠性、可采集性和方便性等突出优点1已经成为个人身份认定的重要手段。因而,自动指纹识别系统(Automated Fingerprint Identification System,AFIS）已成为当前一个重要的研究课题,有着非常广阔的应用前景2。一般来讲，基于计算机的自动指纹识别系统通常由图像输入、预处理、特征提取、匹配等几部分组成。虽然近年来，国内外提出了很多有效的指纹识别方法，但在实际应用中仍然存在一定的问题，特别在如何进一步提高指纹识别的运算速度等方面还有不少有待于提高的地方。为了减少搜索时间和计算的复杂度,必须对指纹进行分类,这样查询、匹配只

3、需在指纹数据库中的一个相应子集中进行,从而节省了运算时间,降低了运算复杂度.所以,指纹分类不仅能够为大型指纹库提供重要的索引机制,而且还能够优化系统的运行,提高AFIS的效率和性能,为AFIS的普及应用奠定良好的基础3.而指纹分类算法大多是根据指纹模式区（pattern area）4中奇异点(Singular point or singularity)的类型、数目和相对位置等信息来实现的。所以，准确可靠地检测奇异点的类型、数目和位置，是自动指纹识别系统中的一项关键技术。2 传统算法介绍传统算法一般有两种:(1)利用指纹点方向场(point orientation field)6对图像中所有的点

4、进行旋转角度差值的计算得到Poincaré Index值5,从而得到奇异点的位置。很显然,这种做法虽然能够最终求得奇异点，但由于对所有点进行运算,使得这种算法过于耗时且有时还会漏判.(2)利用指纹的块方向场(block orientation field)7来计算Poincaré Index值，进而检测指纹奇异点，而块方向场的变化是分块连续的，整体连续过渡性差,精确度不高,不能精确地反映指纹脊线的真实走向，这使得奇异点的定位误差较大,将会对以后的匹配带来很大的影响.另外，由于传统的Poincaré Index只能反映向量场的旋转角度，而不能完全反映向量场的旋转方向

5、，而且计算Poincaré Index时只用一条封闭曲线，因而会提取出大量的伪奇异点。 本文结合了点方向场和块方向场的优点，在此基础上，提出了基于连续方向场8的多尺度指纹奇异点检测算法。由于用了点方向和块方向两种尺度，因而能有效提高指纹奇异点的定位精度；同时，对Poincaré Index公式进行了改进，改进后的Poincaré Index不仅能精确表示向量场的旋转角度，而且还能精确表示向量场的旋转方向;在此基础上，对指纹连续方向场中的每一点，用大小两条封闭数字曲线计算Poincaré Index 值来精确定位指纹奇异点.所以，该算法能够在像素级水平精确

6、定位指纹奇异点(core点和delta点）,精确度达到一个像素，并且，使每个有效的奇异点区域只检测到一个候选奇异点，有效地解决了低质量指纹图像奇异点检测中精确定位和可靠性判断的难题，为AFIS中高精度的指纹分类、匹配等关键技术奠定了良好的基础。本文第3章介绍了多尺度检测的具体算法。第4章详细描述基于多尺度的指纹奇异点检测算法的实现。第5章给出了实验结果。最后总结全文。3 基于连续方向场的多尺度指纹奇异点检测算法3.1 指纹图像的背景分割 从采集到的的原指纹图像中分割出有效的指纹区域，是指纹图像预处理的首要步骤，所有的后继处理都是针对有效指纹区域进行的。3.2 计算指纹点方向图本文采用邻域方向模

7、板法9计算指纹的点方向场,并在此基础上进一步计算连续方向场8,设P表示输入的灰度指纹图像，其大小为M×N，M，N的取值范围一般由指纹输入设备的分辨率决定。P(x,y)表示像素点(x,y)的灰度，取值范围一般是0到255的整数，表示输入图像有256个灰度级。将指纹纹线的方向在02之内划分成8个方向,即以图像中每个像素点为中心,每隔/8确定一个方向,方向的取值分别为1,2,3,8,具体的方向划分见下图:7654387654328211C112234567834567图1 8方向的9×9方向模板具体计算步骤如下9:（1） 对指纹图像中的每一点P(x,y),在以该点为中心的9

8、15;9 窗口内，分别计算8个方向上的灰度和Si，Si也叫做该方向上的切缝和, 即对图1中标有i（ i=1， 2， 3， ， 8； 分别代表8个方向）的位置的像素灰度值求和,然后对灰度和进行平均，得到8个方向的灰度平均值；（2）将这8个平均值按两两垂直的方向分成4 组:1和5为一组，2和6为一组， 3和7为一组,4和8为一组，分别计算每组中两个平均值差的绝对值: （1）其中，i为脊线方向(i=1，2，3，4)；(3)取差值的绝对值最大的两个方向作为可能的脊线方向,即若imax=ord（） （2）其中:ord(Ai)=i, ord()为取数组(向量）A 的元素Ai的下标i的函数，则方向imax

9、和imax+4 为像素P(x,y)处可能的脊线方向；(4)取imax和imax+4两个方向中像素灰度平均值与像素P(x,y)的灰度值S比较接近的方向,作为该像素点P(x,y)的脊线方向D(x,y):(3)imax 若|S-|<|S-|imax+4 否则D(x,y)=以此方法分别对指纹图像中每一个像素点进行处理,便可得到指纹的点方向场D(x,y)。3.3 连续方向场8在计算出指纹的点方向场D(x,y)后， 采用连续滑动的w×w窗口（模板）来对点方向图D(x,y)进行平滑处理,本文取17×17 的平滑窗口对点方向场中每一点P(x,y)进行平滑，即在以此点为中心的w

10、5;w窗口范围内，进行方向直方图统计，具体做法为10:（1）分别统计该w×w窗口内方向值为i（i=1， 2， 2， ， 8，分别代表8个方向）的像素个数Ni；（2）把方向直方图中峰值所对应的方向（即w×w窗口内方向统计数最大的一个方向） 作为该点P(x,y)的方向O(x,y): （4） 其中: ord(Ai)=i, ord()为取数组(向量)A的元素Ai 的下标i的函数。以此方法分别对点方向场D(x,y)中的每一点进行平滑处理，便可得到平滑点方向场O(x,y),也叫指纹的连续方向场(continuous orientation field)。3.4 对指纹连续方向场分块将连

11、续方向场划分成多个不相重叠的图像块,大小为w×w,方向值为i(i=1，2，3，8,分别代表8个方向），然后统计每个小块里方向值为i的像素个数ni；把方向直方图中峰值所对应的方向（ 即w×w窗口内方向统计数最大的一个方向）作为该块M(x,y)的方向。块方向图是一个矩阵，每个元素都是18。块方向以块为单位。4 基于连续方向场的多尺度指纹奇异点检测算法在求得的指纹分块后的方向场M(x,y)后,奇异点的检测主要分以下两步:4.1 指纹图像Poincaré Index的计算Poincaré Index法是指纹奇异点检测最经典、直观而简洁的方法，是在指纹方向场中计算

12、Poincaré Index值来检测指纹奇异点，早在1984年就被Kawagoe和Tojo5用来检测指纹奇异点。设(x,y)是指纹图像的方向场,在方向场中的给定点(i,j)的Poincaré Index值计算公式如下:Poincare（i，j）= （5） + if - otherwise(k)= if|<(6) (7)其中,(xk,yk)以给定点(i,j)为中心的具有N 个像素的封闭数字曲线上沿逆时针方向第k 个点的坐标,k =0， 1， 2， ， N-1，在封闭数字曲线上沿逆时针方向递增。如果Poincaré Index值为1/2， 那么该给定点（i，j）

13、就是core点，若为-1/2,则为delta点。当/2(k)时,(k）=-(k)就大于0,且有0(k）/2,表示当方向场逆时针旋转一个正角度(k)时，还等价于逆时针旋转一个正的补角（-(k)）,显然是不对的，因此，(k)就不能完全反映向量场的旋转方向，由此计算出的Poincaré Index只能反映向量场的旋转角度，而不能完全反映向量场的旋转方向。因此,根据奇异点附近指纹方向变化的规律和Poincaré Index的物理意义，本文对以上经典的Poincaré Index计算公式进行了如下四点改进10:(8)（1）将(k) 的计算公式（6） 中的“-(k) ”改为“

14、(k)- ”，即将公式(6)改为公式(8): (k) if|(k)|</2(k)- otherwise(k)=(k)+ if(k)-/2 这样， 当/2(k)时,(k)= (k)- 就小于0，且有- /2(k）0， 表示当方向场逆时针旋转一个正角度(k)时，等价于顺时针旋转一个负的补角（(k)-）,因此，(k)就能精确表示向量场的旋转方向，由此计算出的Poincaré Index既能精确表示向量场的旋转角度，又能精确表示向量场的旋转方向。(2) 对指纹连续方向场O(x,y)中的每一点P(x,y)，我们分别计算两个Poincaré Index值，所用的封闭数字曲线有两个

15、：一个是点P(x,y)邻域的 2×2 矩形数字曲线1，如图2所示，其周长为 4 个象素；另一个是以点P(x,y)为圆心，半径为 4 个象素的圆形数字曲线2，其周长为 24 个象素，对应的Poincaré Index值分别记为Poincare1(x,y)和Poincare2(x,y)。取这两个模板的主要原因是：模板尺寸越小，检测的奇异点位置越精确，且图像边缘处的奇异点越易检测到，同时计算量也较小；用两个封闭数字曲线分别计算两个Poincaré Index值，可以有效地去除伪奇异点，使每个奇异点区域只有一个候选点符合条件，提高了算法的鲁棒性，避免了对候选奇异点的后处理

16、过程。(x,y+1)（x+1，y+1）(x,y)（x+1，y）图2 检测奇异点使用的封闭数字曲线(3)为了简化计算，直接用方向码18来计算Poincaré Index值，而不是用角度值，这样就避免了三角函数运算和乘除法运算，大大降低了计算复杂度，提高了运算速度。(4）因为是用18方向码来代替像素值,所以本文将（8）式中的用数字8来代替计算Poincaré Index的值，即(k) if|(k)|<4(9)(k)=(k)+ 8 if(k)-4(k)- 8 otherwise4.1.1 计算以块为单位的方向场的Poincaré Index值对分块后求出的指纹块方

17、向场，以块为单位，取w×w个块，在该领域内对每一块(点)计算Poincaré Index值,所用的封闭数字曲线块M(x,y)邻域的2×2矩形数字曲线,如图2所示，其周长为4个像素。对应的Poincaré Index值记为Poincare(x,y)。4.1.2 指纹图像奇异点的检测用上述方法将奇异点的位置大致找出来,确定了在哪个块内可能有奇异点。然后在回到分过块后的连续方向场中，对那些可能存在奇异点的块,计算以该块M(x,y)为中心的3×3领域块中的每一点，对其分别计算该点的Poincaré Index值，所用的封闭数字曲线是点P(x,

18、y)领域的2×2矩形数字曲线1,如图2所示,其周长为4个像素，对应的Poincaré Index值记为Poincare1(x,y)。然后再用半径是4个象素的封闭数字曲线计算该块M(x,y)中每个点的Poincaré Index值,并将其记为Poincare2(x,y).同理，直接用方向码18 来计算Poincaré Index值。4.2 指纹图像奇异点判据4.2.1 对以块为单位的块方向场中的每一像素点M(i,j)根据4.1.1所求得的Poincaré Index值，设置奇异点的判据如下:（1） 若Poincare（i,j）=+0.5，则该块M

19、(i,j)含有core点；（2） 若Poincare（i,j）=-0.5，则该块M(i,j)含有delta点；（3） 否则，该块M(i,j)为普通块（即不含奇异点） 。4.2.2 对4.2.1所确定的块M(i,j)内的每一点P(x,y)根据4.1.2的方法所求得的Poincaré Index值,设置奇异点的判据如下:（1） 若Poincare1(x,y)=+0.5，且Poincare2(x,y)>=+0.5,则该点P(x,y)是core点；（2） 若Poincare1(x,y)= -0.5，且Poincare2(x,y)<= -0.5,则该点P(x,y)是delta点；（

20、3） 否则，该点P(x,y)为普通点(非奇异点）。 如果检测到core点的总数Nc大于2， 或者delta点的总数Nd大于2，则返回到3.3 节，对平滑后的点方向场O(x,y)，按3.3节方法（公式(4)）再进行一次平滑处理,然后按以上4.14.2方法重复，直到core点的总数Nc和delta点的总数Nd都不大于2为止。5 实验结果及分析为了验证本文所述算法的有效性，笔者在微机上用MATLAB语言实现了上述算法并对指纹图像进行了实验测试。从实验结果中选择了右旋型、双螺纹型和螺纹型各一幅具有代表性的指纹列于文中，如图3所示,分别用点方向场,块方向场和本文的算法提取出奇异点并进行了比较，实验结果如

21、图所示， 图中白色正方形的中心点为core点，白色三角形的中心点为delta点。 图3 各指纹原图图4 用点方向场检测奇异点 图5 用块方向场检测奇异点 图6 本文算法检测指纹奇异点6 结束语本文在点方向图和块方向图的基础上提出了一种新的基于两种方向图的多尺度奇异点检测算法。从结果中可以看出,用点方向图检测奇异点容易错判,而用块方向图检测奇异点时点位置不够精确.本文的方法则很好的解决了上述问题,能够在像素级水平精确定位指纹奇异点(core点和delta点）,每个有效的奇异点区域只检测到一个候选奇异点，有效地解决了低质量指纹图像奇异点检测中精确定位和可靠性判断的难题，为自动指纹识别系统中高精度的

22、指纹分类、匹配等关键技术奠定了良好的基础。参考文献:1PANKANTI S, PRABHAKAR S, JAIN A K.On the individuality of fingerprintsJ.IEEE Transactions on PAMI, 2002, 24(8) : 1010- 1025.2 JAIN A K, HONG L, BOLLE R.On- line fingerprint verificationJ.IEEE Transactions on PAMI, 1997, 19( 4) : 302- 314.3 ZHANG W W,WANG S,WANG Y S.Structu

23、re matching algorithm of fingerprint minutiae based on core point J.Acta Automatica Sinica, 2003, 29( 6) : 842- 850.4 Federal Bureau of science of fingerprints: classification and usesM.Washington D C: U S Government Printing Office,1984.5KAWAGOE M, TOJO A.Fingerprint pattern classificationJ.Pattern

24、 Recognition, 1984, 17( 3) : 295- 303.6Rao A R.A taxonomy for texture description and York:Springer verlag,1990.7L OGorman,J V approach to fingerprint filter rn Recognition.1989(1):29-388 聂桂军, 吴陈.自动指纹识别系统中连续分布方向图的研究J.中国图象图形学报, 2005,10(3):315-319.9 马笑潇,黄席樾,周欣,等.指纹自动识别系统中的关键技术方向图J.重庆大学学报(自然科学版),2001,2

25、4(3):9194.10 聂桂军,吴陈.基于连续分布方向图的指纹奇异点检测J.计算机工程与应用， 2006.35:198-20211D. Maio and D. Maltoni, Direct Gray-Scale Minutiae Detection in Fingerprints, IEEE Transactions on PAMI, 1997.12R. Cappelli, A. Lumini, D. Maio and D. Maltoni, Fingerprint Classification by Directional Image Partitioning, IEEE Transac

26、tions on PAMI, 1999.13Maio and D. Maltoni, Real-Time Face Location on Gray-Scale Static Images", Pattern Recognition, vol.33, no.9, pp.1525-1539, 2000.14R. Cappelli, D. Maio and D. Maltoni, Multi-space KL for Pattern Representation and Classification", IEEE Transactions on PAMI, 2001. 15D.

27、 Maio, D. Maltoni, R. Cappelli, J.L. Wayman and A.K. Jain, FVC2000: Fingerprint Verification Competition", IEEE Transactions on PAMI, 2002.16R. Cappelli, D. Maio and D. Maltoni, A Multi-Classifier Approach to Fingerprint Classification", Pattern Analysis and Applications, 2002.17R. Cappell

28、i, D. Maio, D. Maltoni, J.L. Wayman and A.K. Jain, Performance Evaluation of Fingerprint Verification Systems", IEEE Transactions on PAMI, 2006.作者简介:汤婷 1985年生,女,硕士研究生,主要研究方向为数字图像处理、生物特征识别;孙林森 1984年生,男, 硕士研究生,主要研究方向为数字图像处理、生物特征识别;吴小培 1966年生,男,教授,博士生导师,主要研究方向为智能信息处理、模式识别与人工智能、数字图像处理.A Multi-Scale Fingerprint Singular Points Detection Algorithm Based on Continuous Orientation FieldTang Ting, Sun Linsen, Wu XiaopeiDepartment of Computer Scienc