指纹识别技术的研究

1、指纹自动识别系统 21 指纹识别技术的研究【摘要】由于指纹的唯一性和不变性，指纹识别己成为当前最流行、最方便、最可靠的个人身份认证技术之一。本文以自动指纹识别系统的处理流程为线索，介绍了系统的三个部分：指纹预处理、特征提取和指纹匹配。在前人工作的基础上，我们在各个环节都提出了自己的方法，结合那些经典的算法，在很大程度上提高了图像的处理效果与匹配结果。在指纹增强阶段，我们结合方向图与频率图修改了Gabor滤波器；在细化阶段，我们对传统的OPTA算法进行了一些改进；在指纹匹配阶段，我们着重研究了基于点模式的细节匹配。此外，我们还成功的实现了各个算法，完成该指纹识别系统，经实验证明，该系统能够快速准

2、确的识别指纹，达到了预期目的。【关键字】图像分割，图像增强，二值化，细化，特征提取，特征匹配一 课题研究背景（一）指纹识别的发展历史最早记载的人的手印和脚印大约在4000年前古埃及建造金字塔的年代。在那个年代。一些粘土陶器上留有陶艺匠人的指纹，中国人曾经在官方文件上按自己的指纹，公元前300年前的按有指纹的文件现在还存在，直到现在这种签名方式仍然被采用。早在1880年英国人亨利福兹就提出了用指纹识别系统识别犯罪。到20世纪70年代，由于计算机的广泛应用和模式识别理论的发展，人们已开始研究使用计算机进行指纹的自动识别。目前世界各国都在争先研究和开发实用指纹识别系统。（二）指纹识别的研究现状指纹识

3、别是生物识别技术中最早应用、价格最低廉的分支。目前的指纹自动识别系统采用了先进的光电识别办法，采集一个指纹信息，然后经相关的识别算法进行判断。根据已掌握的报道资料来看，目前的自动指纹识别系统已具有如下特点：(1)可靠性：采用独特的容错技术，既使指纹有破坏，即指纹不全或指纹随时间有自然的变化时也不影响正确识别。(2)快捷性：大多数系统鉴别时间仅需1-3s，登录注册一个新客户只需1分钟的时间。(3)灵活性：一个指纹信息的代码可以压缩到几十个字节到几百个字节，因此可以存放在一个磁条上或者一张二维条码卡上或者IC卡上。 (4)安全性 ：所有个人代码都经过了特殊加密。通过所存储的代码不可能复原源指纹，彻

4、底避免了指纹冒用。因此既使证卡丢失，也不存在安全问题。(5)方便性：目前出现的各类指纹识别系统一般外观设计精巧、结实，采用了精密独特的光电系统，具有全程液晶提示，备有多种安装模式。(8)实时性：可实现完整的跟踪、实时报警功能。迄今为止 ，自动指纹识别技术的研究虽然已经取得了很大的成绩，但同时也面临一些严重的困难:(1)指纹采集技术有待提高就实际应用来讲，目前的指纹采集设备还不能很好地满足需要，这己经成为制约自动指纹识别技术发展的一个瓶颈。(2)指纹预处理及匹配算法有待加强目前存在的指纹增强算法主要存在以下几个问题:分割算法过于武断，一般分割算法不考虑上下文问题，只是根据实际图像分块后得到的参数

5、直接进行图像分割，这样很容易造成在前景图像中由于小部分不清晰而被判断为背景的情况，这样将对后续处理产生严重影响；细节点编码彼此互不兼容，目前，在细节点编码过中，除了编码过程中都需要的坐标等小部分公共信息，其余信息往往根据自己系统的需要来进行提取，如周围细节点数，与中心点的夹角等，这样非常不利于系统的升级和扩展，对数据库的扩展也有很大的限制，不利于整个指纹识别研究的发展。（三）指纹识别的应用前景指纹识别技术是当今应用最为广泛的生物特征识别技术，有着广阔的应用前景。在刑侦司法领域，刑侦用指纹识别系统可以用来鉴别罪犯。在民用领域，指纹识别技术可以通过多种方法应用到各个方面。通过使用指纹验证来取代各个

6、计算机应用程序的密码就是最为典型的实例。把指纹识别技术同IC卡结合起来是目前最有前景的研究方向之一。由于指纹识别技术的诸多优点，可以预料，一方面指纹识别系统将会在一切需要验证身份的场所发挥越来越重要的作用，其应用领域将会进一步拓宽;另一方面，由于市场的推动，指纹识别技术也会不断提高，在其识别可靠性、速度、成本等方面进一步朝实用化迈进。（四）指纹识别的基本原理指纹识别是一种利用人体固有的生物特征进行个人身份识别的技术，具有唯一性和不变性等重要特征，因而在信息安全领域、个人身份识别领域等许多方面得到广泛应用。随着计算机图像处理和模式识别技术的发展，使自动指纹识别成为可能。自动指纹识别系统(Auto

7、matic Fingerprint Recognition System，AFRS)一般有4个主要过程：指纹图像采集，指纹图像预处理、特征提取，特征匹配。在一开始，通过指纹采集设备读取到人体指纹的图像，取到指纹图像后，要对原始图像进行初步的处理，这样使指纹图像更加清晰。接下来，自动指纹识别系统从指纹图像中找寻细节点，包括端点、分歧点和交叉点等，进而提取这些细节点的特征数据，有的算法把细节点与方向信息组合起来产生更多的数据。这些数据，通常称为模板。最后，通过计算机模糊比较的方法，把两个指纹的模板进行比较，计算出它们的相似程度，最终得到两个指纹的匹配结果。（五）论文的主要研究内容本论文中，我们就国

8、内外指纹研究工作进行比较，提出了一套指纹识别算法，能在较短的时间内较准确地识别指纹。指纹识别过程一般分为指纹图像采集、图像预处理、特征提取和特征匹配四大部分，如图1-1。本论文研究后面三部分，对已采集的指纹图像进行处理和匹配。指纹预处理部分包括图像分割、图像增强、二值化和细化四部分，如图1-2。图像分割是将要处理的有效图像部分从整个指纹图像中分离出来，这样一方面减少了后续处理的步骤的数据量，另一方面也避免了因为部分图像区域不可靠而导致伪特征的产生。图像增强包括两个部分，首先是对原始图像上模糊但有可能恢复的部分进行增强，然后再对整幅图像滤波，消除指纹脊线间的断裂和粘连。图像二值化是提取经增强处理

9、的指纹图像的脊线，用”1”表示脊线上的点，”0”表示背景和谷线，从而把原始灰度图像转化为二值图像。图像细化是进一步把二值指纹脊线细化为单像素宽度的骨架线，这是为了方便以后的特征提取。本文是在前人工作的基础上摸索并设计了这套指纹的自动识别系统，如图1-3所示，该系统对前人的某些工作做了改进，并提出了自己的一些思想和算法，经实验验证，效果较好，达到了预期目的。 图1-1 指纹识别框架图 图1-2 预处理流程图图1-3 指纹识别系统图二 算法分析与设计（一）图像分割算法分析与设计1 算法分析指纹图像的分割通常位于预处理的前端，其目的是去掉图像中不含纹路的区域和由于噪音太大而无法恢复的低质量纹路区域，

10、使后续处理能够集中于有效区域。分割处理不仅能提高特征提取的精确度，而且还能大大减少指纹预处理的时间，因此是指纹图像处理中的重要组成部分。指纹分割的一般方法是将图像分割成许多互不重叠的小块，并计算每块的特征向量，根据特征向量来判断某块为前景还是背景。指纹分割中常用的主要特征包括灰度方差、方向图、频率图和纹线峰平均灰度值与谷平均灰度值之差（对比度）等。2 算法设计较好的指纹的图像分割算法应在分割的过程中保护有效的指纹的纹理特征，从而提高指纹特征的精确度，优化了整个识别系统得处理速度和效率。有效区域的分割的意义非常明显。首先，可以为以后的操作缩小范围，节省计算时间；其次，可以排除背景区域的干扰，提高

11、算法的精度和效率。有些文献的算法采用的canny算子，该方法使得分割后图像的效果有了明显提高，但是需要很大的计算代价，对于有限的系统资源是不允许的。我们采用的是一种更简洁的算法，虽然在精度上稍有降低，但是在速度上可以提高80。算法步骤如下：(1) 用边缘提取算子提取灰度图像的边缘。得到二值边缘图。零值表示背景，非零值表示边缘(2) 用半径为n像素的圆形结构元，对二值边缘图做一次数值形态学的闭运算，平滑边界并对有效区域的内部的孔洞进行填充(3) 用半径为m像素的圆形结构元，对步骤（2）的结果进行一次开运算。去除毛刺和小目标噪声。最后得到非零区域就是指纹的有效区域 (a) 指纹原始图像 (b) 指

12、纹图像分割区域 图2-1 指纹图像处理及分割区域仿真结果如图2-1所示，其中（a）为指纹原始图像，（b）为原始图像的分割区域。（二）图像增强算法的分析与设计1 算法分析数字图像处理中采用的通用的图像增强方法如均值滤波、低通滤波、边缘增强等对指纹这种具有一定特性脊线和谷线交替的图像的增强效果并不理想，这是因为这些方法都是针对图像中存在的随机噪声，然而模糊的指纹图像主要存在纹线缺陷的结构性噪声。理想的指纹图像是脊线和谷线交替构成，脊线和谷线粗细均匀，在大部分区域，脊线之间和谷线之间近似平行，且呈现连续的、方向平缓的曲线形态。由于指纹图像存在这些特性，指纹图像可以近似的看成具有特定方向和频率的平面正

13、弦波，如图2-2所示。基于这一特性，利用具有方向和频率选择特性的带通滤波器可以实现很好的增强效果。采用这种方法关键是滤波器选择和设计、求取指纹的方向图和指纹频率。图2-2 Gabor滤波坐标旋转图在指纹的增强算法中，常用的算法大致上可以分为两种：一类是从空域上进行滤波去噪处理；另一类是从频域上进行细节增强。但这两中方法各有缺点：空域滤波器往往设计复杂并且过多依赖精确方向场的求取，频域滤波器则是从整幅图像的频域空间进行全局的增强，因此又造成对细节信息的忽视。Gabor滤波器是带通滤波器，它以其在空域良好的方向选择性，在频域有良好的频域选择性，因而在计算机视觉领域得到了广泛的应用。利用Gabor滤

14、波器在这种在两个域内的良好性质来进行指纹图像的增强，取得了很好的效果。2 算法设计Gabor 滤波器实际上是一种Gauss 窗的加窗Fourier 变换。Gabor 变换是英国物理学家Gabor 提出来的，1980 年Daugman 首先将一维Gabor 小波推广到二维，并用于视觉简单神经元的视野感受模型。Gabor 在空间的时域和频域视图如图2-3和2-4 所示。图2-3 Gabor滤波器空间函数形式图2-4 Gabor滤波器频率响应一个平滑对称的Gabor滤波器有以下的一般形式： 2-1其中 在式（2-1）中，f为从x轴上的方向的正弦的频率，和分别为高斯包络的在轴方向和y轴方向的空间常量。

15、本文所提出的基于Gabor滤波器的增强算法。其主要步骤为：（1）灰度规格化：可使输入的指纹灰度图达到到预先规定的均值和方差（2）方向图估计：从规格化后的指纹灰度图中求得指纹方向图（3）计算指纹的平均频率：从规格化后的指纹灰度图中求得指纹的平均频率（4）滤波处理：对规格化后的指纹灰度图进行Gabor滤波用以得到增强的指纹图像下面就这四步骤进行逐步分析：（1）灰度规格化在对指纹图像 Gabor 滤波之前，需要对指纹图像进行规格化处理，其目的是将指纹图像的灰度值的均值和方差调整到所期望的均值和方差，以消除传感器本身的噪声和手指对传感器表面的压力不均而带来的灰度差异。假设指纹图象I 为M N 大小，令

16、I(i,j)表示象素点(i,j)的灰度级数，Av 和分别表示指纹图象的均值和方差，G(i,j)表示象素点(i,j)规格化后的级数，见式2-4。Av 和分别可由公式2-2 和2-3得到。 2-2 2-3 2-4 其中，和分别表示假设的均值和方差，由实验确定，其值大小根据图像采集器分辨率的高低，此处=125，=125。规格化后的图像如图2-5所示。 (a) 指纹原始图像 (b) 指纹规格化后图像 图2-5 指纹原始图像与规格化后的图像（2）方向图估计指纹的脊线方向已给广泛的应用于指纹图象增强、纹型的特征的提取、指纹自动分类、方向模板的匹配、编码重构等许多关键处理环节。就方向图的形式可以分为两种，一

17、种是点方向图，即求出每个方向点的方向，另一种是区域方向图，即求取图像中每个局部区域中的主导方向，以该方向代表该区域中所有像素的方向。相比而言，点方向图精度较高，但计算量较大，耗时较长，对于一个实际系统来说我们采用速度快又能达到系统要求的算法，所以我们选用区域方向图算法。求取指纹方向图常用的方法主要有梯度法、切缝法、抽样法和投影法，而本文综合性能、去噪、计算复杂度等方面采用梯度法求方向场。基于脊线区域梯度方向图的算法流程如下：(1) 将规格化后的指纹图像进行分块，分成大小为W W （1717）像素的子块(2) 计算子块中每个像素点的水平梯度向量Gx(s,t)和垂直梯度分量Gy(s,t)，此处采用

18、Sobel 算子求取水平梯度和垂直梯度分量。算子采用如下模版 (3)计算每块以(i,j)为中心的局部方向, 见式2-7 2-5 2-6 2-7 (4) 通过上式求得指纹每个子块的区域方向，但是由于噪声的影响，其方向并不一定完全正确。由于局部脊线除奇异点除外，相邻子块之间变化都是比较缓慢，因此我们可以采用一个低通滤波器，此处采用一个55 的模版做低通平滑滤波。为了进行低通滤波，子块的方向必须转换为连续的矢量场 2-8 2-9和 分别表示矢量场x 和y 的分量，分别见式2-8和2-9。和 平滑滤波由公式2-10 和2-11 得到 2-10 2-11为滤波器窗口宽度，即为5，为滤波器各点权值，此处全

19、为1(5) 求得以中心点处(i,j)的脊线方向见式2-12 2-12 (a) 指纹原始图像 (b) 指纹方向图 图2-6 指纹原始图像与指纹方向图图2-6给出了指纹原始图像和图像的方向图。（3）计算指纹的平均频率指纹纹理除了具有稳定的方向性的特点外，还具有稳定的频率性特点。在指纹图像的一个局部区域内，脊线和谷线的纹理走向近似平行，同时沿脊线和谷线方向的灰度分布近似正弦包络。脊线频率定义为两条相邻脊线之间间距的倒数，通过定义该包络线中的极大值和极小值，就能计算出相应的脊线和谷线的间距，进而得到脊线的频率。在子块中以中心象素(i,j)处画一个长为m，宽为n 的矩形方向窗口，如图2-2 所示。其中m

20、 为预先估计的脊线间距均值，与该块脊线方向一致，n 可取指纹预先估计的脊线间距三倍左右。然后计算沿n 方向上各象素的平均灰度值，每个平均灰度值为沿m 方向上m 象素的统计平均，具体如下式： 2-13 2-14 2-15式中d=0,n-1。取m=32，n=16。其中I (x,y)是象素点(x,y)的灰度值， 是子块的域方向。由式2-13 得到Xk后，就能定位脊线和谷线的中心点，对局部子块的平均脊线或者谷线间距取导数，即求出子块的脊线频率(i,j)。（4）滤波处理通过上面的计算，我们已经得到了指纹图像的频率F0、梯度方向，下面我们就是要确定Gaussian 包络的标准偏差和。和的值将决定指纹增强的

21、效果，如果它们的值越大，去噪效果越明显，同时也会带来一些伪脊线和伪谷线；如果该值越小，虽然不会带来伪脊线和伪谷线，但是去噪能力将大大减弱。所以在进行程序设计它们必须合理，才能达到最佳效果，通过试验数据得到，把它们都舍为4.0。前面我们对Gabor 滤波器进行了详尽的分析，令灰度规格化的图像为G，增强后的图像为E（式2-17），利用离散卷积求出子块中每个像素增强后的值。 2-16 2-17其中是Gabor滤波器模板的大小，表示分割出的背景图像。增强后的指纹图像如图2-7所示。 (a) 指纹原始图像 (b) 指纹Gabor增强图像 图2-7 指纹原始图像与Gabor增强后的图像（三） 图像二值化算

22、法分析与设计1算法分析指纹图像是由不同灰度的两类区域组成的，所谓二值化就是通过设定阈值，把它变为仅用两个灰度值分别表示图像的前景和背景颜色的二值图像。我们对局部自适应阈值法进行了研究并有所改进，现介绍如下：局部自适应阈值法对原始指纹图像要求较低，处理效果也较好，算法的复杂度一般，容易编程实现，是一种比较好的二值化算法。但是当WW分块落在两种区域会引起误判：（1）当落在谷线较多的区域时，会使得一部分甚至大部分的像素点被判定为脊线（2）当落在脊线较多的区域时，会使得一部分甚至大部分的像素点被判定为谷线基于以上原因，需要对传统的局部自适应阈值法进行改进。首先利用传统的局部自适应阈值法的思想，根据指纹

23、图像中每一部分的明暗度来确定阈值。在求取指纹图每一块大致的阈值的基础上，对可能的误判进行矫正，即对谷线较多和脊线较多的区域的阈值进行调整。算法对阈值进行调整的思想是这样的：设定一个谷线门限Tg，当区域阈值小于Tg时，说明窗口内谷线较多，当前阈值偏小，可适当增大；同样设定一个脊线门限Tj，当区域阈值大于Tj时，进行减小调整。小于Tg和大于Tj范围称之为调整范围。2 算法设计算法相当于在二值化的过程中进行了一次平滑操作，因此取得了较好的二值化效果，其描述如下：（1）将经过滤波的图像划分为WW的分块（2）计算第k块的灰度平均值和方差，并将方差设为初始阈值 ， 2-18（3）如果方差低于设定的Tvar

24、值，且均值低于Tm值，那么本块内所有点灰度为0，并返回第（2）步；否则进行第（4）步（4）借助参数，进行以下调整，为通过实验获得的经验值 2-19（5）对k块的每个像素点，进行以下处理 2-20算法的流程图如图2-8所示 图2-8 指纹图像二值化流程图二值化后的图像如图2-9所示。 (a) 指纹原始图像 (b) 指纹二值化图像 图2-9 指纹原始图像及其二值化后所得图像（四）图像细化算法分析与设计1 算法分析细化又称为骨架化，是图像分析、特征提取及模式识别中的常用技术。细化的主要作用是去除不必要的纹线粗细信息，节省内存，便于从指纹图像中提取细节特征，从而提高指纹图像的处理速度和效率。我们对传统

25、的OPTA算法进行了研究与改进，具体介绍如下：OPTA算法是较为典型的图像模板细化算法。该算法从图像的左上角元素开始，按照从左到右，从上到下的顺序对图像进行扫描，每个像素点均抽取如图2-10所示的10个相邻像素，然后将其与事先规定的模板进行比较。如果和图2-11所示的8个消除模板中的任意一个匹配（模板中非“”值的所有点与该位置对应的领域中的像素点的值都相等）时，则准备去除点P（即P=0），否则保留P。 图2-10 OPTA算法抽取的邻域 图2-11 OPTA算法消除模板 图2-12 OPTA算法保留模板为了保持连通性，准备去除的点再和图2-12所示的两个保留模板进行比较，如果匹配，则P仍保留，

26、否则P才真正删去。处理完整图像的过程为一次迭代，这种迭代反复进行，直到没有一个像素的值被改变为止，迭代的次数依赖于图像的大小和纹线的形状。OPTA算法能满足收敛性、连接性、拓扑性和保持性，对指纹图像的细化能达到较好效果。但该算法在三叉点处往往细化不全；细化后的指纹脊线不光滑，有许多毛刺，且纹线扭曲，不在纹线中心，因此不能满足细化性和中轴性，会给以后的指纹提取带来困难。另外，采用两个大小不同模板分两次进行运算，其快速性受到影响。2 算法设计对OPTA算法进行研究会发现：细化不全是保留模板造成的，保留模板本意是避免同一行（列）中两个“1”同时被删除，已保证连通性。但该条件包含过大，并非所有这种情况

27、下的中心点都应保留，保留与否还应取决于同行（列）中另一个“1”值周围的情况。若另一个“1”周围点与消除模板匹配而应删除时，中心点“1”值才应保留，都则中心点“1”值应该删除。细化后指纹脊线毛刺多、纹线扭曲在一定程度上是由消除模板造成。消除模板4个中，当“”为0时，这时与它们匹配的方窗中心“1”值被去掉后，纹线出现凹凸不平，导致纹线扭曲，迭代中也容易形成毛刺。通过对OPTA算法的分析，我们提出了一种新的细化算法，对消除模板进行改造，并重新构造保留模板。该算法采用统一的44模板，如图2-13所示。左上角的33方窗为消除模板区域。图2-13 改进的OPTA算法的统一模板构造消除模板时，算法采用图2-

28、14所示的8个模板，其中前4个模板能有效的去除边缘化的凸出物，保证了细化后的指纹骨架处于指纹脊线中心，避免了细化后的指纹骨架出现毛刺。构造保留模板时，按前面所分析的结果来实现，即当前中心点的去留考虑到另一个“1”值周围点的情况，构造的保留模板如图2-14所示。图2-14 改进的OPTA算法的消除模板图2-15 改进的OPTA算法的保留模板集体算法是从左上角开始，对每个像素（模板中为P5）均抽取出如图2-15所示的15个相邻像素，先将其中的8个邻域像素与8个消除模板比较，如果与所有消除都不匹配，P5保留；否则，再和6个保留模板进行比较，如果与任意一个匹配则保留P5，否则删去。重复上述过程，直到没

29、有像素值被改变为止。改进的OPTA算法能够对指纹图像充分细化，纹线光滑无毛刺，骨架处于纹线中心线，细化后的图像扭曲小，能最大程度的保留指纹的细节特征，因此是一种较好的模板细化算法。指纹图像经细化后，由于脊线上有可能存在小的突起，在细化后的骨架线上呈现出小的短枝，这样就会产生伪端点和伪分歧点，所以在细化后必须加入打毛刺的程序，删除那些长度小于阈值T的短枝。（1）毛刺的删除毛刺的一端是端点，另一端表现为分叉点。一般毛刺的长度是很短的，根据这一特点，如果从任一端点出发，沿着沿线跟踪，若在很短的距离内遇到了分叉点，则有理由认为跟踪过的指纹纹线部分为毛刺，应予以删除。（2）短线的删除短线是长度小于给定阈

30、值的一小段孤立纹线。一般来说，那些小于指纹纹线（脊线或谷线）宽度的纹线大多属于短线，应予以删除。实验证明以上介绍的细化图像后处理算法的确能有效地提高图像质量。细化图像及其后处理所得图像如图2-16所示。 (a) 指纹细化图像 (b) 细化图像后处理所得图像 图2-16 指纹细化图像及其后处理所得图像 （五） 特征提取算法分析与设计1 算法分析 二值化细化后的图像对于图像的特征提取非常有利。但是，二值图像总存在某些缺陷（存在伪特征）。在指纹的特征提取中，一般都会选取细化指纹上的两种特征：纹线的端点和纹线的分歧点。如图2-17所示。 图2-17 脊线端点和分歧点在提取的过程中，我们就选取了上述两种

31、特征：脊线的分歧点和端点。在得到可靠的二值图像后，只需要一个33的模板便可将端点和分歧点提取出来。33的模板如图2-18所示，P是待检测的点，P1、 P2、 P8是它的8个邻域点，沿顺时针方向排列，R(1)、R(2)、R(8)分别是点 P1、 P2、 P8的灰度值。如果P是端点，则它的8个邻域点满足：， 2-21如果P是分歧点，则它的8各邻域点满足：， 2-22这样就可以找到特征点，并记录它们的类型和位置。为了提取特征点的属性，就需要对特征点所在纹线的情况进行了解，因此引入纹线跟踪技术。顾名思义，纹线跟踪就是从纹线的一端出发，沿着纹线的走向，到达该纹线的另一端。传统的算法是直接对灰度纹线进行跟

32、踪，这种算法实现起来过于复杂，本文采用了一种新的快速纹线跟踪算法8邻域编码纹线跟踪算法：用8邻域编码来同时表示当前点的类型和8邻域像素的状态，然后通过查表的方法来判断所要跟踪的下一点。该算法避免了8邻域信息的重复计算，速度得到了显著提高。 图2-18 特征提取模板2 算法设计8邻域编码是图像处理中一种常用的技术。由于细化二值图像中每个像素点只需1比特的数据（0或1）就可以表示，那么，如果把P点8邻域像素数据按一定顺序放入一个字节（8比特）中，就可以用该字节数据来表示P点的8邻域信息，称之为点P的8邻域编码。对于图2-2所示的8邻域点，我们定义8邻域编码顺序如图2-19所示： 图2-19 P点的

33、8邻域编码则P点的8邻域编码公式为： 2-23虽然8比特的8邻域编码在理论上有256种可能值，但对于8邻域的细化二值指纹图像，由分析可知，只有60种数值，而且对应于某种特定的类型，则仅对应几个数值。根据该数据，就可以准确识别该中心点的类型和8邻域状态，然后用查表的方法判断下一个待跟踪点。分析细化二值指纹图像可以发现，虽然某点的8邻域灰度值有各种组合，但是一幅8邻域最简的细化图像上的纹线点只有如下3种情况，而且每种情况也只有有限的若干种组合。其中，端点和分歧点就是我们在特征提取中要提取的特征点。(1)Cn(P)=1、Sn(P)=1称为端点，即1各中心点的8邻域中只有1个黑点(2) Cn(P)=3

34、、Sn(P)=3称为分歧点，即1个中心点的8邻域中共有3各黑点(3) Cn(P)=2、Sn(P)=2或者Sn(P)=3称为连续点，即1各中心点的8邻域中有2个或3个黑点下面简要给出8邻域编码纹线跟踪算法的步骤：(1)对细化二值指纹图像的各像素点进行8邻域编码，并保存(2)当前点为指定起始点（x，y），指定起始方向Dc，设初步步长L=0(3)判断是否达到规定步长，是则终止；否则根据Dc方向与坐标增量表更新当前点（x，y）(4)由当前点8邻域编码查编码与类型表，判断是否为端点或分歧点，是则终止，否则继续(5)求Dc的补码，从连续点方向表中选与该补码不同的方向编码作为新的Dc，且步长为L=L+1，返

35、回（3）具体流程图如图2-20。 图2-20 8邻域编码纹线跟踪算法流程图这样就将一幅指纹图像转换为了一个由细节点组成的平面点集。在细节匹配中，对应脊线将被用来对需要进行匹配的两个平面集进行校准，而且校准的参数，也就是两个点集中任意一对脊线间的旋转角度，将被用作为判断它们所对应的细节点能否看做是匹配的细节点的条件。指纹所提取的特征点图像如图2-21所示。 (a) 指纹细化图像 (b) 指纹图像特征点 图2-21 指纹细化图像与指纹特征点图像（六） 特征匹配算法分析与设计1 算法分析指纹匹配是指纹识别中的一个重要问题。目前的指纹识别系统主要采用基于节点的匹配方法，我们研究的也是基于点模式的细节匹

36、配。该方法通过某种策略分别从两枚指纹中选取一个节点作为参照节点对，在进行节点匹配时先将参照节点对齐，然后再评估其他节点的匹配程度。令表示第一幅图像中的m个细节点，我们将第一幅图像称为模板图像，表示第二幅图像中的n个细节点，我们把第二幅图像称为输入图像。为了把细节点转换到极坐标系中去，要在模板细节点集和输入细节点集中各选一个参照点作为相应的极坐标系中的原点，并算出其他细节点相对于参照点的极坐标。对模板点集中的每一点Pi (im)和输入点集中的每一点Qj(jn)，定义rotateij为将 Pi和Qj当作参照点对时，从输入图像到模板图像的旋转角度。如果Pi和Qj可以被当成一对对应点，即它们分别对应的

37、脊线相似性到一定程度，则rotateij将取0360间的一个值，否则我们定义rotateij取值为400，以表示Pi和Qj不能作为一对对应点。注意rotateij400表示Pi和Qj对应的脊线相似性到了一定程度。则它们（Pi和Qj）是不是对应点对及rotateij的取值将由如下算法决定。用R表示细节点Pi对应的脊线，r表示细节点Qj对应的脊线。匹配r与R，用式(2-24)计算这两条脊线间的差异： 2-24其中L是记录的脊线中的点个数，R(di)和r(di)分别表示从脊线R与r上的点i到对应的细节点的距离di，R(ai)和r(ai)约分别表示连接脊线R与r上的点i与对应的细节点的直线间的夹角ai

38、。2 算法设计我们的细节匹配算法步骤如下：（1）对每一个i(im)和每一个j(1n)，如果rotateij=400，即细节点Pi和Qj不能被当作对应细节点对，则重复此步并选择另一对Pi和Qj，否则转向步骤（2）。如果所有的细节点对都已考虑过了，则转向步骤（5）（2）将Pi和Qj当作参照细节点，将输入点集和模板点集中的细节点都转换成极坐标（3）将极坐标中的模板细节点和输入细节点按极角递增方向排序，并连接成串，表示如下： 2-25其中和表示对应的极半径、极角和相对于参照点的细节点方向 （4）用后面将要介绍的方法匹配串和，找出匹配分数，记录为m_scoreij。然后转回步骤（1） （5）找出m_sc

39、oreij中的最大值，把它当作输入细节点集与模板点集的匹配分数。如果匹配分数高于一个预先设定的阈值，则认为输入图像与模板图像来自一个指纹，否则认为它们来自不同指纹在介绍匹配串和的方法之前，我们先介绍一下限界盒及其大小，如图2-22所示。图2-22 限界盒示意图 一个限界盒是放在模板细节点上的一个盒子，限界盒的大小用angle_size和radius_size来表示，这个盒子的一对边的极角为常数，另一对边的极半径为常数。用angle_size表示极半径为常数的那对的极角差异： 2-26用表示极角为常数的那对边的极半径的差异： 2-27有的文献中使用了一个固定大小的限界盒，即在所有的模板细节点处，

40、angle_size和radius_size取同样的值。在本文介绍的方法中，它们的值将随细节点的极半径人小而改变，使用可变大小的限界盒是为了使算法对非线性形变更为鲁棒。匹配和的算法描述如下：（1）用式（2-26）和式（2-27）决定每一个模板细节点的限界盒的大小。置m_scoreij=0。（2）进行如下循环：for(int k = 1; k m; k+)for(int l = 1; l = N & ( angle_highk); l+)if(template_pointk和input_pointl满足condition1m_scoreij+;调整限界盒；上述过程中，condition1定义为：

41、 condition1是将 template_pointk和 input_pointl看作对应点对的条件。其含义是，input_pointl应该在template_pointk的接线盒的内部，这两个细节点的方向差异应小于（我们设置=30），rotatekl应小于400，即Pk和Ql对应的脊线不相似。根据上面的算法，我们设计了这套匹配算法，算法对图象效果很清楚有比较好的匹配结果，对图象一定的形变和旋转所带来的误差有比较好的消除，而对指纹图象处理后细化效果不好的指纹匹配结果识别效果不理想。四 总结（一）课题小结由于指纹的唯一性和不变性，指纹识别系统的准确性和快速性，指纹识别己成为当前最流行、最方便、最可靠的个人身份认证技术之一。本文针对指纹识别技术进行了深入研究，提出的指纹识别系统流程包括指纹预处理、特征提取和特征匹配等三大部分。对于指纹预处理，又分为图像分割、图像增强、二值化和细化四部分。图像分割的任务是去掉图像中不含纹路的区域和由于噪音太大而无法回复的低质量纹路区域。图像增强是对模糊区域进行恢复，并增强脊线和谷线的对比度，以保证后续处理的可靠性。二值化的目的是把灰度指纹图像变成0-1取值的二值图像。细化的目的就是将二值图像变成为单像素宽度的骨架图像。在基于点模式指纹匹配系统中，特征提取是从细化二值图像中检测细节点（主要指端点