1、将图像G（i ，j）划分成大小为W×W的块
2、对每个块分别计算每个像素的梯度d x(I ，j)，d y(I ，j)
dx(i,j)?u??1v??111??S(u?1,v?1)G(i?u,i?v) (3-1)
x11dy(i,j)?u??1v??1??S(u?1,v?1)G(i?u,i?v) (3-2)
y3、根据梯度值计算块方向
由（3-1）、（3-2）式中所求得的梯度依下面几式即可求出局部块的主方向：
i?w/2Vx(i,j)?u?i?w/2v?j?w/2i?w/2j?w/2??j?w/22dx(u,v)dy(u,v) (3-3)
Vy(i,j)?12u?i?w/2v?j?w/2??2(dx2(u,v)?dy(u,v)) (3-4)
?(i,j)??arctan(Vy(i,j)/Vx(i,j)) 若Vx(i,j)?0 (3-5)
?(i,j)??/2 若Vx(i,j)? 0 (3-6)
然后，将所得到的?转换成方向数。 4、平滑方向图
由于指纹图像在局域区域内的纹线方向不会出现大的变化，可以在某一小区域中统计块方向，利用相邻块的矢量和作为本块的方向，以消除噪声。
5、重复（2）到（4）步骤，直到求出所有块的方向。
考虑该算法求一个W×W的块的时间复杂度为：0(?w4)。设图像的大小为m
?m??n?×n，则求整个图像的方向的时间复杂度为O (w4??????)。从算法的时间复
?w??w?杂度来看，求取一个600×800指纹图像的块方向图，假设计算机速度为50MHZ，不同W值对应的运行时间如表3-1。
表3-1 不同W值下对应的计算时间
时间 W=9 1.76 W=7 1.265 W=5 1.14 因此，在实时的指纹识别应用中，指纹图像经滤波、图像增强、二值化、细
11
化之后再提取图像的方向场，需要更多的时间，更难在需要实时识别的大容量数据库中应用。
为了解决这一问题，首先我们考虑去掉二值化这一步，因为在二值化的过程中，无论采用何种先进的算法，都不可避免地产生新的图像噪声。其次，基于指纹方向图的基本原理和指纹的基本特征，由于在纹脊或纹谷上，其灰度值彼此接近，该点与其邻域的灰度值差的和值应为最小，则将所对应的方向指定为该点的局部方向。将原始的指纹图像划分为w×w个块的方向基元，运用统计的方法从指纹图像的局部像素求取方向图后，再求得各个块的方向[7]。
方向图是原始指纹图像的一种变换模式，其中的每一点代表原始图像中该点像素的局部纹理走向。我们用式3-7计算点(i,j)的方向。
Sd(i,j)?min?G(im,jm)?G(i,j), d?1?N (3-7)
m?1M式（3-7）中，G(i,j)为原始图像中位置(i,j)处的像素灰度值，G(im,jm)为点(i,j)沿方向d的第m个领域点的灰度值。M为用来计算方向的邻域点的个数，M的选取与指纹图像的分辨率有关，选取的原则是M大于二倍纹脊或纹谷的宽度，本文中取M=8；N是所取的方向数，一般取4个或8个方向，在本文中我们选取N=8，方向数对应的方向图3-2所示。在实际的应用中，如果仅仅是为了获取指纹的分类结果，可以将N取为4，以加快处理速度，当然要以牺牲误识率为代价。
图3-2 8方向数及对应的方向
求出各点的方向后，将点方向图分为L*L大小的若干块，对每块计算方向直方图，其峰值的方向即为该块方向。在程序上只需要统计八个方向中数据最多的方向即为该块的方向，算法的时间复杂度为遍历所有像素点一次的时间。
12
设图像的大小为U*V，块的大小为w×w,方向数为8，点(i,j)灰度值为
G(i,j)，点方向图的结果保存在数组S(i,j)中。求点方向图的算法描述如下：
1、for i=0 to U-1 2、for j=0 to V-1 3、S(i,j)=0 4、for k=0 to 7 5、for i=0 to 7
6、x?G(i*cos(k*?/8)?j*sin(k*?/8),i*sin(k*?/8)?j*cos(k*?/8)?G(i,j) 7、next 1
8、if x>s(i , j) then s(i , j)=x 9、next k 10、nextj 11、next i
该方法具有算法简单、快速、有效的特点，由于计算量小，时间复杂度仅为0（k*U*V），在运算速度上大大优于原来的算法；另外该算法用小区域内的方向变化代替点方向的变化，具有一定的平滑、抗噪能力的作用，具有一定的鲁棒性。但一定范围内的噪声不可避免，还需要在其邻域内对噪声进行平滑，最后得到准确的指纹方向图。图3-3为用这种方法求得的几种不同纹形的指纹的方向图。
a、螺旋型原图 b、左旋型原图 c、帐型原图 d、拱型原图
a1、螺旋型方向图 b1、左旋型方向图 c1、帐型方向图 d1、拱型方向图
图3-3 算法求得的四种纹型的指纹方向图
13
3.2 指纹特征的提取 3.2.1 脊的滤波
一般的指纹处理算法对于质量好的指纹图像都能获得较好的比对结果，而对于质量较差的图像则可靠性很低，为了提高算法的鲁棒性，通常都要对图像进行滤波和增强，以提高输入指纹的质量，这是后面工作的基础。
由于我们这里讨论的是实时的指纹分类，要求算法的效率高，计算的复杂度相对较小，以达到实时分类的目的。相对分类研究，我们可以作一个简化的假设，即假定指纹的脊与脊之间在小区域内是平行的，在大区域中是相似的平滑曲线。根据这一假设，我们可以设计一个方向滤波器，将不符合这些特征的脊作为噪声去掉，从而最后得到一个质量较高的纹形图像。
将点方向图分为W*W大小的若干块，滤波的算法如下[8]： 1、根据块的方向k选取滤波器Q矩阵； 2、for i=0 to w-1 3、for j=0 to w-1 4、s=0
5、for n= -3 to +3 6、for m= -3 to +3
7、s?s?G(i?n,j?m)?Q((n?3)*7?m?3) 8、next m 9、next n 10、G(i，j)=s ∕ 81
3.2.2 奇异点的提取
指纹的奇异点是指纹核心点和三角点，如图3-4所示。核心点位于指纹纹路的渐进中心，在方向图中，可以认为在该点的小邻域中周围点的方向呈半圆形趋势；三角点位于从核心点开始的第一个分叉点或断点，或两条纹路会聚处、孤立处、折转处，或者指向这些点，在方向图中，可以认为在该点的小邻域中，该点
14
周围的点的方向呈双曲线趋势[9]。
核心点 三角点
图3-4 指纹的奇异点
指纹图像中奇异点的提取是对指纹分类具有重要的意义，指纹分类的算法是通过判断奇异点位置来对指纹进行分类的。目前采用得较多的方法是曲率计算和求Poincare系数，由于Poincare系数可能判断出中心点和三角点，而曲率只能判断中心点，所以采用Poincare系数法。
点(i,j)的Poincare系数的计算公式如下：
1Poincare(i,j)?2???(k)
k?oNcif?(k)??/2??(k),?其中：?(k)???(k??), if?(k)???/ 2
??(k??),if?(k)??/2?Nd? ?(k)?o'(?x(i'),?y(i))?o'(?x(i),?y(i)) i'?(i?1)moN?表示环绕点(i,j)的闭合曲线上的图像点的个数，?x(i)， ?y(i)表示像素
????点i的x，y坐标，O'是经过插值后的指纹方向图。所有角度的取值在??,?。
?22?Poincare系数的物理意义如图3-5所示。单中心点的Poincare系数表示围绕该中心点的闭曲线上的点的方向变化总和为π，纹线绕中心点的角度变化刚好为π，对双中心点来说则为2π。三角点的Poincare系数值表示围绕该三角点的闭曲线上的点的方向变化为-π，这是因为当该三角点的纹路方向1a,1b,1c满足：存在且仅存在两个纹路方向的夹角大于π∕2是，则表示该三个纹路确实是朝着三个差别较大的方向延伸，而不至于将分叉点判断为三角点。而对于普通点来说，Poincare系数的值为0，表示方向的变化为0。
15