基于结构的指纹分类技术

    摘要：指纹分类技术是指纹数据库的一个重要的索引机制。提出了一种基于指纹方向图的结构分类算法。通过图像分割，抽取图像的有用部分，而后基于指纹方向图，寻找指纹奇异点，利用脊线跟踪技术和规则确定指纹的类别。

    关键词：指纹分类 方向图 脊线跟踪 图像分割

指纹识别是一种重要的生物特征鉴别技术。每一个人都有自己特有的指纹特征。随着计算机技术的不断发展，自动指纹识别系统（AFIS）已在公安、金融领域得到广泛的应用。图1显示了几种典型的指纹图像。

实践表明，指纹识别技术具有高准确性和可信度。但是，指纹识别常常需要在大规模的数据库上进行计算。如果没有一种有效的数据库分类机制，输入的指纹图像将不得不同数据库中大量的指纹数据逐一进行比对，系统工作将非常繁重。为了减少搜索时间和计算的复杂度，必须对指纹进行分类。这样查询只需在指纹数据库中的一个相应子集中进行，从而节省了运算时间并降低了运行复杂度。

指纹分类技术的核心问题是如何确定指纹分类类别。具体分类方法很多，类数也不确定。依照公安部的标准，指纹被为为以下七类：弓型、左箕、右箕、斗型、缺指、其它、未知。

1 分类算法概述

指纹分类技术主包括计算机图像处理和模式识别两方面的内容。指纹分类技术可以看作指纹在大尺度下的粗略匹配。输入指纹首先被划归为预先已定义好的某一类，而后在更精细的尺度上，在这一类中进行精确的指纹比对。目前指纹分类算法通常有两种分类，一种是根据采用的理论方法划分，划分通常划分为统计方法、结构方法、人工神经网络方法、变换域方法等。另一种是从实际问题考虑的角度出发，大致可分为两类：一类是模型方式，这类方法主要基于指纹特征点的数目和相对集团，更接近于人的思维习惯；另一类是全局方式，根据整个图像脊线特征或方向信息进行分类，这类方法常采用统计理论方法。

本文提出了一种基本结构的实现方法，依照指纹的方向图信息，寻找奇异点。根据奇异点的数目和相关位置，设计逻辑规则进行判决。主要处理过程如图2所示。

2 图像预分割

在指纹分类的过程中，输入的指纹图像往往是一幅含有大量噪声的灰度图像，特别是现场指纹，噪声化现象更严重。这些干扰和不利因素将影响最终的分类结果，使得系统的整体 性能和准确率降低。

图像预处理的目的就是在尽量保存指纹特征信息条件下，去除原始指纹图像的错误信息和冗余部分。预处理工作的好坏直接影响后续指纹分类的有效性。由于指纹分类和特征点提取等处理过程必须在预处理完成之后进行，因此预处理的时间复杂度也就成为影响整个指纹系统运行速度的一个重要因素。同图像处理中经常使用的预处理技术不同，指纹的预处理工作有其特别之片。指纹是由突起的脊线和凹陷的脊沟组成的表皮图案，这是一个灰度值交替变化的纹理图案。在这种情况下，中值滤波、均值滤波一类的去噪措施将无能为力。首先因为这些技术都是基于图像象素值平稳变化这一假设的；第二，因为指纹图像在局部上有很强的空间频率分布性和方向性。研究表明，效果好的预处理方法往往是利用了这些先验知识。目前常用的预处理方法主要有空域增强法和频域滤波法，空域方法包括方向图、二值化、细化、修补、腐蚀等，频域方法包括FFT、Gabor滤波等。本算法主要采用了两种方法：一是指纹图像的预分割；另一是方向图处理及滤波。

本算法使用的测试图像有如下特点（如图3a所示）：（1）指纹图像比较模糊，变形时也很严重；（2）指纹的位置和大小不定，很多图像有明显旋转；（3）背景区的干扰很多，有很多方字和条纹线。针对以上情况，本算法采用预分割技术来排除文字、条纹线的干扰，提取图像的有用信息。预分割主要由两步组成：粗限定和细限定。

根据根纹图的灰度分布，粗限定可以大致确定指纹图中指印的相应位置。可采用式（1）所示的8×8的平滑模板对图像进行平滑和二值化处理。平滑实际上是一种增强措施，目的是突出指纹图像的有用部分，便于投影和分割处理。经过处理，孤儿噪声点的影响将被忽略。而后沿水平和竖直两个方向对图像进行投影，并对同一方向上的灰度值进行累计，根据灰度值的分布，由外向内搜索边界，从而确定图像中的有效区域的范围。

粗限定后对大多数图像来说，文字和条纹部分都可排除在外，图像已基本可用。但由于精确度分布随机性及背景干扰等原因，有些图像分割效果不好，对于后续判决将会有很大影响，所以还应采和细限定技术进一步分割图像。具体过程是对粗限定后的图像再进行投影，寻找每一方向上的灰度最大累计值，根据这个峰值确定相对域值，并由内向外搜索边界，这一过程是对粗限定的修正。采用相对域值来提高顶处理的适应度，可以去除部分指纹图像中第二指节的冗余部分。

通过两步限定过程，我们得到满意的分割图像，如图3（b）所示。

3 方向图计算

方向图计算有两个功能：一是为后续处理做准备，因为指纹奇异点的提取依赖于方向图；二是去除噪声。方向图用纹线的方向来表示该纹线，用方向场代替原图像，实际上相当于对指纹原图像的一种变换表示。同一般的滤波技术相比，它可以利用指纹图像的局域方向性有效地去除噪声，保留有用信息。一般有两种方向图，一种是点方向图，表示源指纹图像中每一象素点脊线的方向；另一种是块方向图，表示源指纹图像中每一个图像块内脊线的总体方向。点方向图的计算式如下：

若点（i,j）的方向为K(i,j)，则：

（ik,jk）∈Dk(i,j)

式中，Dk(i,j)为以点（i,j）为中心的沿第k方向的连续N个象素位置，G（i,j）为（i,j）点象素灰度值。

为了实际计算的方便，通常使用一个9×9的模板对以上公式进行简化（参见文献[1][2]），如图3所示。

选取图4所示的8个方向，分别对每一个方向计算求和式：

S0=G(i-2,j-4)+G(i-1,j-2)+G(i+1,j+2)+G(i+2,j+4) (3)

设Sp和Sq分别代表8个方向中最大的方向和与最小的方向和。p和q代表相应的方向。如果C点位于脊沟上，那么C点的方向定义为p，否则为q。用D表示象素点C的方向，则：

通过（4）式可以得到指纹的方向图。通常这是一幅噪声化严重的图像，必须利用指纹图像的领域方向相似性加以处理。去噪的措施有两种：一种是利用块方向图，具体措施是统计一个小区域（如8×8象素的矩形区）内的主要方向，亦即将该区域内点方向数最多的方向作为区域的主方向[1～2]。这样对于一般的图像区域来说，由于脊线走向的规律性，个别象素点噪声的影响将被消除。除了去噪作用以外，块方向图还可以降低模式空间的维数，减少运算量，而数据的信息量却不受很大影响。另外一种措施是计算每个点2倍方向角θ（θ∈[0,180°]）的正、余弦值，即sin2θ和cos2θ。将一维的角度标量值变为二维矢量，而后对这个二维矢量的每个分量分别加以平滑[1～2]。从原理上看，这种平滑工作既可在点方向图上进行，也可在块方向图上进行。但对于本算法使用的测试图像，通过实验比较表明，块方向图的平滑效果更一些，如图5的所示。

4 分类

4.1 奇异点提取

根据奇异点的数目和相对位置可进行判决分类。对于用于识别的细节特征来讲，这里的奇异点指的是较为“宏观”的脊线特征。常用的奇异点有两种：中心点（core）和三角区（delta）。中心点处于指纹图像的中心，常用来进行指纹的定位。三角区则是指纹模式中另一类特征点，在该点处指纹脊线分叉为三种走向，如图6所示。

相对于指纹图像的其它区域而言，奇异点有许多特殊性质。比如对于给定指纹图像的任意一点，在其邻域内作一条包围该点的闭合曲线，沿该闭合曲线旋转一周计算所得到的方向向量的旋转总和。对于不同性质的点，这个总和值是不同的，中心点对应的值为180°，三角区对应的值为-180°，而一般的图像区域对应值为0°。利用这一特性，我们可找出图像中的奇异点。

受图像噪声的影响，在奇异点提取过程中往往会产生大量伪点，需要加以滤除。可以利用判决规则来排除错误的奇异点。错误的奇异点主要有两类，一是在指纹图像边界，这一部分区域由于提取指纹时的受力不均，往往比较模糊，容易形成伪点；二是相邻的奇异点，这往往是由于某个区域局部噪声过大引起判决失误。对于第一类错误判决，可以采用限定处理区域的办法加以抑制，也就是前面所述的预分割办法。而对于第二类错误，则采用如下步骤处理：

（1）记录所有初步判决产生的奇异点，对于每个奇异点，记录它的位置信息和属性值，即是中心点还是三角区。

（2）沿水平方向逐行扫描，对于每个奇异点，判断它的8邻域内是否存在其它奇异点。如果存在，则执行步骤（3）；否则，扫描下一个奇异点值。

（3）如果领域内的所有奇异点同性，即同为中心点或三角区，则保留最靠后的那个奇导点，其它点标识为伪奇异点；如果领域内所有奇异点不同性，则所有点都标识为伪点，并继续扫描。

（4）当执行至图像是扫时，重新扫描图像，去除所有伪奇异点。

4.2 分类判决

指纹的不同类别有不同数目的奇异点和位置关系，这些奇异点的数目和相对位置决定了指纹的最终分类。决策过程如下：

设中心点的数目为Nc，三角区的数目为Nd。

（1）如果Nc>2或Nd>2，那么执行步骤（2）；否则跳至步骤（3）。

（2）如果迭代次数超过预设值，则将指纹类型设为其它，退出程序；否则平滑块方向图，重新计算奇异点，转回步骤（1）。

（3）如果Nc=Nd=1，利用规则1检验奇异点的位置关系。如果满足，则判为左、右箕纹或弓型纹；否则指纹类型判为其它，退出。

（4）如果Nc=Nd=2，利用规则2检验奇异点的位置关系。如果满足，则判为斗型纹；否则转回步骤（2）。

（5）如果Nc=Nd=0，则判为弓形纹，退出。

规则的作用是检测指纹奇异点的相对位置关系，确保判决的准确性。

规则1：检验箕型纹的位置关系，区别左、右箕或尖弓。由箕型纹的拓补结构可知，中心点总是位于指纹的上部，根据三角区相对于中心点的位置，可分为左、右箕或尖弓。本算法采用了脊线跟踪技术，示意图如图7所示，具体过程如下：

（1）以中心点的坐标为初始点（x0,y0）。

（2）将当前点相邻两个方向块的方向的平均值设为主方向。

（3）沿主方向向下逐块形成中心分界线。

x=x-BlockSize×cosθ

y=y+BlockSize×sinθ （5）

其中，BlockSize代表方向块的大小，θ表示当前位置的主方向。

（4）重复（2）～（3）步直至达到图像边界为止。

（5）设定一域值L，以中心线为界，如果三角区与中心线的最近距离在L内，则判为尖弓（本算法将其归入纠类）；如果位于分界线的左侧，则将指纹判为左箕；如果位于分界线的右侧，则判为右箕。

规则2：检验斗型纹的位置关系。具体差别如下：首先确定最上部的特征点必将为中心点，同时保证两个中心点位于两个三角区特征点连线的一侧。

5 实验结果

本算法对1737张指纹图像进行了测试，最终总的分类错误率为3.3%（详见表1）。从错误率指标来说，与文献[4]大致相当，但本算法的测试样本数要多。同时，我们对文献[1]、[3]、[5]所述的算法进行模拟。实验表明，在相同预处理条件下，本算法的判决的稳定性更好，准确率更高。

表1 测试样本分类结果

　弓型左箕右箕斗型样本数
错误数113
7560
19534
22530
10

本算法是一种改进型的结构分类算法，利用指纹图像的方向图信息寻找奇异点，并根据这些奇异点的数目和相对位置进行判决，确定最终类别。相比于其它算法，本算法在预处理方面进行两步预分割工作，减小了误检风险；同时设计了新的判决规则，利用脊线跟踪和规则检测，判断左、右箕型指纹，提高分类稳定性。