基于结构的指纹分类技术研究

　　自动指纹识别系统是生物特征识别研究的一个热点，而指纹分类又是指纹识别系统的核 心技术。在大型的指纹数据库中，待识别指纹与样本数据库中的大量指纹逐一进行比对，是及其耗费时间的。为了减少搜索时间和计算复杂性，把样本数据库中的指纹分为几类，将属 于不同类别的指纹分别保存在不同的数据库中，待识别指纹只需与属于同类的子数据库中的样本逐一比对。从某种意义上讲，指纹分类实际上就是粗糙的指纹匹配过程，它为自动指纹识别系统提供了一个索引机制。

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

　　1 分类算法概述

　　国内外学者已经对指纹分类算法进行了大量的研究。大致可分为下面几种：种是基于奇异点的分类，主要依靠指纹的core点和delta点的个数以及它们之间的拓扑关系来确定指纹属于哪种类型。此类方法要求指纹图像必须能够采集到core点和delta点，但由于一些采集器采集面积的限制，要保证能够采集到delta点还是比较困难的，而且对于受噪声干扰程度比较严重的低质量图像不仅奇异点的定位比较困难，还往往容易检测到许多虚假的奇异点，直接导致了此算法的准确率。第二种是基于结构的指纹分类。主要有Raffaele Cappelli等人使用动态模板的分类方法，这些方法使用了图像的一些整体结构，因此比其它大多数使用局部信息的分类方法更加有效，但对于一些低质量的指纹图像，很难获取指纹准确的结构。第三种是结合奇异点和脊线结构的指纹分类方法，此种方法不单单依赖于奇异点，同时使用了脊线的结构，但对于低质量的指纹图像，此方法获取的奇异点与脊线结构同样是不准确的，因此对于低质量指纹依然是不能够准确的分类。第四种是基于方向场的指纹分类，主要是根据各类指纹图像的方向图的相似和差异来确定指纹的类型。此方法对低质量也有一定的局限性。目前国内外的指纹分类算法大部分都是把指纹分为4类或5类。

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

　　2 图像预分割

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

　　本算法使用的测试图像有如下特点（如图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的模板对以上公式进行简化，如图4所示。

　　选取图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象素的矩形区）内的主要方向。这样对于一般的图像区域来说，由于脊线走向的规律性，个别象素点噪声的影响将被消除。除了去噪作用以外，块方向图还可以降低模式空间的维数，减少运算量，而数据的信息量却不受很大影响。另外一种措施是计算每个点2倍方向角θ（θ∈[0,180°]）的正、余弦值，即sin2θ和cos2θ。将一维的角度标量值变为二维矢量，而后对这个二维矢量的每个分量分别加以平滑。但对于本算法使用的测试图像，通过实验比较表明，块方向图的平滑效果更一些，如图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 测试样本分类结果

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