1 指纹分类算法
    分类算法的基本步骤是：
    （1）图像预处理：为使指纹图像有相同的均值和方差，对原始图像进行归一化处理，然后根据图像灰度信息对图像分割，把背景区分割出来；
    （2）计算方向图" title="方向图">方向图：计算指纹图像每一点的方向；
    （3）提取特征：根据方向图，找出指纹的奇异点；
    （4）分类：根据中心点数目和指纹特定区域的流向把指纹分为四类。
    程序流程图如图2。

1.1 图像预处理
    预处理包括归一化、背景分割。归一化就是把原始图像的灰度均值和方差变换为期望得到的均值和方差。
    归一化后，对图像进行分割，利用灰度信息把指纹区和背景区分开。
    图3是一幅指纹图像的分割结果。

1.2 方向图的计算与平滑
    输入的指纹图像大小为240×264，分成8×8的小块。首先计算每一点的方向，把平面空间量化成8个方向码，通过式（1）计算每一点的方向。
   

    其中：D(i,j)表示点(i,j)的方向码；N这里取值为8。G(i,j)表示点(i,j)的灰度值；w表示以点(i,j)中心，在方向为d的直线上，每一边的点数。G(i_k,j_k)_d表示d方向的直线上所取像素点的灰度值。点的方向码的计算解释如下：在某一个点较小的范围内，纹线上的点的灰度值相差不大，而纹线上与非纹线的点的灰度值相差较大。因此沿着纹线计算的差的绝对值之和较小，而沿着其他方向计算出的差的绝对值之和则较大。
    为了保证方向图的抗干扰能力，可在块划分不变的情况下，适当扩展方向码的统计区域。块的划分尺寸为8×8，而统计该区域的方向码时，则按照12×12的扩展区域。统计每一小块对应区域中每一个方向码的像素点数，像素点数最多的方向码就是该小块的主方向。
    为了消除局部的方向图计算误差，对方向图进行平滑。平滑方式采用3×3均值滤波器实现平滑滤波^[6]。图4给出了滤波前后的方向图。

1.3  奇异点寻找与修正
    进行指纹分类前，先将指纹的特征点找出来。对指纹分类有用的是指纹的奇异点：中心点（core）和三角点（delta）。文献[1]中介绍了判定中心点和三角点的方法。在中心点沿着逆时针方向一周的角度变化量（不大于90度）为180度，在三角点沿着逆时针方向一周的角度变化量（不大于90度）为-180度。
    在实际计算时，由于方向图的划分、干扰的存在，根据上述判据找到的中心点和三角点有可能是伪奇异点，需要根据实际情况作一些修正，删除伪奇异点。修正奇异点的准则如下：
    （1）如果指纹纹线在局部变化较大，就有可能出现相邻两个小块的方向互相垂直，这可能使中心点和三角点重合。这种情况都发生在中心区域而不是三角区域，所以需要删除与中心点重合的三角点。
    （2）指纹图像的边缘区域噪声较大，容易出现伪奇异点，所以在计算出的奇异点的一个适当的邻域内如果有背景区，则删除该奇异点。
    （3）由于噪声的影响，或是手指上有较大的皱纹，会使计算出的奇异点中出现相邻很近的中心点和三角点，这些都是伪奇异点。所以，如果存在一个中心点和一个三角点距离小于设定的阈值，则删除这两个点，并进一步删除与这两个点距离小于阈值的其它奇异点；
    （4）对于指纹纹线在特征区域变化较大的情况，有可能在一个特征区域找出多于一个的奇异点。所以，在经过上述三步伪奇异点的删除后，使用聚类分析方法，把余下的中心点和三角点分成几个聚类，每一个聚类的中心就是最后得到的奇异点。
    图5给出了一幅质量较差的指纹图像奇异点修正前和修正后的情况。

    本文根据中心点数目组织分类判据将指纹分为三类：0个中心点为弓形， 2个中心点为斗形，1个中心点为左箕形或右箕形。需要根据实际情况对此判据作进一步修正和改进。当中心点个数为1，存在三角点。如果三角点与中心点的距离小于一个阈值，则该指纹为弓形。
1.4 左箕、右箕的区分
    对于中心点个数为1的指纹，可以根据中心点下方指纹纹线的流转方向进一步把指纹分成左箕形、右箕形。左箕形指纹纹线流向左方，右箕形流向右方。
    对中心点下方一定角度的区域进行90°的方向滤波，可以通过方向码之间的计算近似实现方向滤波：
   

    P是滤波值，N是该区域小块的个数，p_i是每一小块的滤波值，D_i是小块的方向码，D₀是滤波方向，在这里D₀＝4（90°）。不考虑与D₀垂直的方向码。
    P为负是左箕形，否则为右箕形。
    图6给出了两种类形特征区域内指纹纹线的流向。

1.5 斗形的索引参数计算
    斗形指纹在汉族人中所占比例很大，大约在一半左右。因此有必要对斗形指纹进行细分。实际情况中,很难从结构特征把斗形分成几个可以互相分得开的子类。本文以斗形的长短轴之比Flatness作为斗形的数据库索引参数，对斗形进行连续分类。
分别以8个方向码为坐标轴，将指纹方向图在两个垂直的方向投影，计算投影比。取最大的投影比为Flatness，作为索引参数。
    对斗形指纹，利用其长短轴之比，作为斗形指纹的索引，在数据库中查找，是连续分类思想在斗形指纹进一步分类上的体现。文献[7]提出了不同于传统的明确的排他性分类（exclusive classification）的连续分类（continuous classification）概念。通过一定的特征提取方法，得到一个特征向量，然后把这个特征向量当作索引（a access key）。对于一个给定的容差ρ，在特征空间里，以待查样本为中心，以ρ为半径的超球作为待查样本的搜索域。实际上，存在大量无法归入既定类别的杂形指纹，和可以同时归入一个以上类别、连指纹专家都无法确定其类别的模棱两可的指纹，这都影响了传统排他性分类算法的正确率。而对于连续分类，则不存在这种干扰。不过文献[7]提出的分类算法主要是针对油墨滚动按捺的指纹图像，而且有很大的算法复杂性，不适于实时系统。本文对斗形索引参数的计算，是连续分类思想在研究实时系统算法上的一个尝试。
    图7是方向码为0，3的两个坐标的示意图。

    图8是900个斗形指纹样本的参数Flatness的分布图。由图8可以看出，应用斗形指纹的长短轴之比Flatness，可以把斗形指纹很好地排列开来。

2 实验结果
    利用本算法对2150个指纹采集样本进行实验，这些样本来自215个手指，每个手指采集10次。分错样本63个，分类准确率达97.1％。具体结果见表1。