CN101276411B - 指纹识别方法 - Google Patents

Abstract

本发明涉及一种指纹识别方法，由指纹特征提取和特征匹配两个步骤组成：特征提取包括针对于预处理的指纹图像提取细节点特征，对初选的细节点进行剪枝，对剪枝后的细节点特征进行可靠性验证，以及进行特征矢量编码；特征匹配首先利用脊线曲率特征进行图像校准，降低了校准的复杂度，然后利用指纹的邻域关系特征进行匹配分值的计算和匹配点对的统计，根据匹配的点对数和匹配分值，利用多级判别体系来判断两枚指纹的相似度。本方法具有识别率高、识别速度快，可靠性强等优点。

Description

指纹识别方法

技术领域

本发明涉及一种生物识别技术，具体涉及一种指纹识别方法。

背景技术

由于人的指纹千差万别，几乎没有重复，因此指纹识别是身份识别的一种重要方法。指纹识别技术是指对采集到的指纹图像信息进行计算机图像处理和模式识别的一项综合性技术。

指纹识别的大致过程是：首先通过指纹采集设备获取指纹图像，然后对该图像进行预处理，以方便提取指纹特征，特征提取后，再通过模式匹配的方法判别两者的一致性，若特征值相似，则可判定为同一人的指纹，反之，则判定两指纹不是来自同一枚手指。

现有指纹识别方法一般仅考虑指纹的细节点局部特征，普遍存在识别率低、识别速度慢等问题。

发明内容

本发明的目的在于克服现有技术的上述缺陷，提供一种识别率高，识别速度快的指纹识别方法，通过分析细节点的邻域关系和脊线曲率构建稳定性更好的特征矢量，然后利用匹配的细节点对总数和匹配分值之和构建多级判别体系。

本发明用到的一些定义含义如下：

指纹的细节点是指指纹脊线上的端点或者分歧点；

脊线间的平均距离λ：是指细化后脊线间的平均宽度，用象素的个数表示，对于大小为300×300，分辨率为500DPI的指纹图像，脊线平均距离为10个象素，也即λ＝10；

细节特征的方向：根据特征的类型不同，其方向的计算方法也有差异。对于端点，它的方向可由以下方法计算而得：从端点出发，沿脊线跟踪λ个象素，用一元线性回归求出这些点的拟合直线，该直线的方向就是所求特征端点的方向。而对于分歧点特征，它的方向可由从分歧点出发的两条同方向脊线的方向角的平均值确定，而脊线的方向角可通过上面介绍的一元回归线性拟合的方法求得。

特征点间的距离d：是指细节特征点间的欧氏距离。假定两个特征点的位置坐标分别为：(x1，y1)，(x2，y2)，则距离d为：

$d=\sqrt{{(x_1-x_2)}^2+{(y_1-y_2)}^2}$

特征点的结构数Nm：是指以细节特征为中心，R为半径的圆或正方形内细节特征的个数。下标m可用e或b取代，分别表示端点和分歧点的个数。例如，可以采用正方形模板，半径为3λ/2。

特征点垂直对比度Varo：该参数的计算需要借助于没有进行二值化的灰度图像。在16×16的灰度图像块中，选取中心象素作为待测点。根据预处理确定的块方向，过待测点作该方向的垂线，沿垂线在待测点两边各取4个象素点，则这8个象素的灰度方差就被认为是待测点的垂直对比度，为方便起见，这一块中所有象素的垂直对比度都等于中心点的垂直对比度，那么如果细节特征所处的图像块已知，则其垂直对比度也就可以测得。

特征点平行对比度Varp：该参数的计算类似于垂直对比度，仍需要借助于没有进行二值化的灰度图像。在16×16的灰度图像块中，选取中心象素作为待测点。根据预处理确定的块方向，沿该方向在待测点两边各取4个象素点，则这8个象素的灰度方差就被认为是待测点的平行对比度，为方便起见，这一块中所有象素的平行对比度都等于中心点的平行对比度，那么如果细节特征所处的图像块已知，则其平行对比度也就可以测得。

以上定义在论文“指纹细节特征提取与剪枝”(王崇文，李见为等，光电工程，2002，No.4，pp67-70)中已有详细定义。在该论文中提出的指纹图像的表示方法为将指纹图像表示为一个二维矩阵，每一个象素就是矩阵的一个元素，取值为0～255，矩阵的维度就是图像的宽和高。在本发明中，继续采用这些定义和图像的表示方法。

本发明提出了一种指纹识别方法，由指纹特征提取和特征匹配两个过程组成：

所述指纹特征提取的过程为：针对于预处理的图像进行细节特征初选；对初选后的细节特征进行剪枝；对剪枝后的细节点特征进行可靠性验证；最后根据细节点的邻域关系和脊线曲率特征构建特征矢量；

所述特征匹配的过程为：首先利用脊线的曲率特征进行匹配参考点对的识别；然后利用极坐标对图像进行校准；接着利用自适应弹性匹配方法进行细节点配对和匹配分值计算；最后利用匹配的点对数和匹配分值，采用多级判别体系进行指纹匹配。

所述指纹特征提取的具体过程为：

1、指纹细节点初选：初步选出所有的细节点，记录下这些细节特征的类型和位置坐标，以便于下一步的剪枝处理。

2、细节点剪枝：

对于细化后的点线指纹图，所述细节特征剪枝的伪特征包括：因为脊线断裂产生的两个错误端点；因为脊线的错误连接和断开产生的伪分歧点和伪端点；在对非平滑脊线进行细化后产生的短枝；因为脊线间的错误连接产生伪分歧点。可以针对每一类细节伪特征分别进行剪枝。

删除了伪细节特征后，可以进一步根据指纹图像的拓扑性质来对存留的细节特征进行可靠性检测。由指纹图像可以看出，分歧点侧面的脊线与形成分歧点的脊线分支平行，可以基于这个特性对分歧点的可靠性进行检测。

3、构建特征矢量：

本发明构建特征矢量的方法为：在本发明中，为了减少指纹形变对特征匹配的影响，定义了一种新的细节特征矢量，它总共包含24个元素，表示方法如下：

FC＝{x，y，ω，var，f，cx，cy，r，d1，a1，s1，l1，d2，a2，s2，l2，d3，a3，s3，l3，d4，a4，s4，l4}

各元素的含义如图11所示：m0是当前待研究的细节特征点，即中心细节点，它的方向为o0(该方向值可以在预处理阶段获得)。以m0为坐标原点，以o0为x轴的正方向，构建坐标系(如图虚线所示)，m1，m2和m3是分别位于第一、第二和第三象限的细节特征点，这些特征点应该是在各象限所有细节点中距离m0最近的。oi是各细节点mi的方向，x和y是中心细节点m0在原来坐标系中位置坐标，ω是包含中心细节点的局部脊线方向，即图中的o0。考虑到特征提取过程中误差，用参数var和f取代了类型参数，var是在原始指纹图像中以m0为中心的局部窗口内各象素的灰度方差，f是在原始指纹图像中包含m0的局部窗口的频率，它代表局部窗口中脊线的频率。这两个参数都可以在指纹预处理阶段获得。

如果仔细观察指纹图像，就会发现大多数的脊线在有限长度内可以当作是圆弧的一部分，基于这一点，本发明使用了3个参数来表示与细节特征点相连的脊线，它们分别是cx，cy和r。把与细节特征点相连的脊线看作是一段圆弧，利用圆弧上的三个点就得到所在圆的中心坐标和半径。考虑到弹性形变的影响，利用最小二乘法去拟合脊线，最后用中心的平均坐标cx、cy和半径的平均值r来表示与细节特征点相连的脊线。

di，si，ai和li(i＝1，2，3，4)是中心细节特征点的邻域关系特征，它们描述了中心细节点m0与周围细节点mi之间的关系。di分别是mi到m0的距离，ai是m0方向角所在直线与mi方向角所在直线的夹角，si是m0与mi连线所在直线分别和m0方向角所在直线的夹角。l1，l2，l3和l4分别是mi特征点在所有细节点集合中的索引。考虑到在某些情况下无法为某个象限确定合适的细节特征，例如，在图11中，在第四象限找不到合适的细节点，那么就用一个特殊的极小值来标识d4，s4，a4和l4，如-1。

注意到在特征矢量FC中，各分量特征都来自于相对量或统计量，因此该特征矢量具有旋转不变和平移不变等特性。另外，对于任意的细节点，它们的特征矢量FC的长度都是一样的，这为我们计算矢量之间的相似性带来很大的方便。

二、指纹特征匹配

所述特征匹配的过程为：首先利用脊线的曲率特征进行匹配参考点对的识别；然后利用极坐标对图像进行校准；接着利用自适应弹性匹配方法进行细节点配对和匹配分值计算；最后利用匹配的点对数和匹配分值，采用多级判别体系进行指纹匹配。具体处理流程如图1右半部分所示。

1.识别匹配参考点对：如果用穷举法对输入指纹和模板指纹的每个点对的相似性进行计算，显然是非常耗时的，本发明提出了一种基于脊线的曲率特征来识别存在对应关系细节点对的新方法。首先，需要对已经获得的两个点集的矢量特征按照曲率大小的顺序排序，如果输入指纹的第i个细节点和模板指纹的第j个特征点存在对应关系，那么与这两个特征点相连的脊线的曲率r_i和r_j也应该是基本相同的，并且该曲率是不随图像旋转或平移所变化的，于是有如果|r_i-r_j|＜T_r，其中T_r为给定的阈值，则可以利用公式

计算两个细节特征的相似度。如果S(i，j)＞Ta，则可以认为对应点对已经找到。否则如果计算了所有曲率相同的点对之间的相似度，没有哪个点对的相似度大于给定的阈值Ta，则可以把具有最大相似度的点对作为后续图像校准的中心。如果点对的最大相似度小于给定的阈值Tb，则可以直接判断两个图像不匹配。

相似度计算公式中T是预先定义的阈值，|FC_i-FC_j|是两个特征矢量的欧氏距离。相似度S(i，j)指明了两个细节特征点的匹配可能性，值越大匹配的可能性越高。可以看出0＜＝S(i，j)＜＝1，对于S(i，j)＝1说明两个细节特征完全匹配，而对于S(i，j)＝0则说明两个细节点完全不相同。

2.图像校准：图像校准的目的在于消除两幅指纹图像的几何形变。利用平移变换参数和旋转变换参数可以修正图像间的刚性形变。对于非线性形变，因为其主要出现在图像中心区域，其表现形式为非线性的向外辐射。因此，采用极坐标表示方法是一种更有效的解决方法。首先把输入指纹图像和模板指纹图像原来笛卡儿坐标系下的细节点转换到极坐标下，极坐标的原点为上一步骤中确定的参考对应点对；然后把新的特征矢量集合按照极角的升序进行排列。

进行图像校准的步骤如下：

1)把输入指纹图像和模板指纹图像原来笛卡儿坐标系下的细节点转换到极坐标下，极坐标的原点为上一步确定的对应参考点对，转换公式如下所示。

$\left(\begin{array}{c}{\mathrm{pr}}_i\\ e_i\\ {\mathrm{\θ}}_i\end{array}\right)=\left(\begin{array}{c}\sqrt{{(x_i-x_r)}^2+{(y_i-y_r)}^2}\\ {\tan }^{-1}\left(\frac{y_i-y_r}{x_i-x_r}\right)-{\mathrm{\ω}}_r\\ {\mathrm{\ω}}_i-{\mathrm{\ω}}_r\end{array}\right)$

式中(x_i，y_i，ω_i)^T是细节点在原来坐标系下的取值，(x_r，y_r，ω_r)^T是图像校准中心在原来坐标系的值，(pr_i，e_i，θ_i)^T是转换后细节点极坐标的值，其中pr_i代表极径，e_i代表极角，θ_i代表细节点i的方向与校准中心细节点方向的差值。这样一来，就可以把原来的特征矢量FC改成一种更为简洁的形式FC′＝(pr_i，e_i，θ_i，var，f，r)，其中var，f和r的含义和FC中定义一样。

2)把新的特征矢量集合按照极角的升序进行排列，结果如下：

$P_a^{\′}=\left\{\right[{\mathrm{pr}}_1^P,e_1^P,{\mathrm{\θ}}_1^P,{\mathrm{var}}_1^P,f_1^P,r_1^P]...[{\mathrm{pr}}_m^P,e_m^P,{\mathrm{\θ}}_m^P,{\mathrm{var}}_m^P,f_m^P,r_m^P\left]\right\}$

$Q_a^{\′}=\left\{\right[{\mathrm{pr}}_1^Q,e_1^Q,{\mathrm{\θ}}_1^Q,{\mathrm{var}}_1^Q,f_1^Q,r_1^Q]...[{\mathrm{pr}}_n^Q,e_n^Q,{\mathrm{\θ}}_n^Q,{\mathrm{var}}_n^Q,f_n^Q,r_n^Q\left]\right\}$

3.细节点配对与匹配计算：由于存在非线性变形，这就要求匹配算法要有一定的弹性。通常，在匹配过程中，会利用一个边界盒来进行弹性匹配，即在模板指纹的细节点上放一个边界盒，然后检查对应的输入指纹位置，看是否有细节点落在边界盒内。

4.指纹匹配：计算完所有存在对应关系的细节点对的匹配分值后，则可以得到匹配的细节点对总数Nm和匹配分值之和Mm，其中M_m＝∑S(i，j)。下面将介绍多级判别体系：

首先，如果N_m≥12或N_m/Max(N，M)≥0.6，其中N和M分别是指纹模板和输入图像细节点的数量，则可以直接判断两幅指纹图像来自同一个手指；

否则，如果N_m＜6，则可以直接判断两幅指纹图像不匹配；

如果10≤N_m≤11并且M_m≥T1，则也可以判断两幅指纹图像匹配成功；

如果8≤N_m≤9并且M_m≥T2，则也可以判断两幅指纹图像匹配成功；

其他情况都可以判断两幅图像不匹配。

其中T1和T2都是预先设定的阈值，可根据一定数量的指纹样本统计而得。

本发明的优点在于：(1)由于构建的指纹特征矢量不仅包含细节点本身的位置、方向、类型信息，还包含细节点周围的邻域关系信息和脊线曲率信息，从而保证了它的平移、旋转不变性，也更能反映指纹纹线的全局信息；(2)基于这种新的特征矢量，在指纹匹配时一方面利用脊线曲率特征进行图像校准，降低了校准的复杂度，另一方面利用指纹的邻域关系特征进行匹配分值的计算，利用匹配的细节点对总数和匹配分值之和构建多级判别体系，增加了匹配的鲁棒性；(3)细节点的伪特征剪枝以及可靠性验证，保证了细节点提取的可信度。

本发明的目的、特征和优点将结合实施例并参照附图进一步说明。

附图说明

图1为本发明的指纹识别流程框图。

图2为指纹细节点初选使用的3×3模板。

图3为常见伪特征结构示意图。

图4为删除因图像模糊带来的伪特征流程图。

图5为删除因脊线断裂造成的伪特征流程图。

图6为删除短枝和桥形伪特征流程图。

图7为分歧点可靠性检验流程图。

图8为分歧点可靠性检验示意图。

图9为端点可靠性检验流程图。

图10为端点可靠性检测示意图。

图11为特征矢量示意图。

具体实施方式

现结合附图对本发明做进一步说明。

本发明所述的指纹识别方法由指纹特征提取和特征匹配两个步骤组成，下面分别加以叙述。

一、指纹特征提取

所述特征提取的过程为：针对于预处理的图像进行细节特征初选；对初选后的细节特征进行剪枝；对剪枝后的细节点特征进行可靠性验证；最后根据细节点的邻域关系和脊线曲率特征构建特征矢量；具体处理流程如图1左半部分所示。现对每一处理流程分述如下：

(一)指纹细节点初选：本实施例采用论文“指纹细节特征提取与剪枝”

(王崇文，李见为等，光电工程，2002，No.4，pp67-70)中提出的指纹细节点初选方法。使用了一个3×3的小窗口在细化后的指纹点线图上确定细节特征点的位置。假定脊线上的点用“1”表示，背景用“0”表示，如图2所示，M是待检测点，X1......X8为M的八邻域点，呈逆时针排列。如果M是端点，那么必须满足下面公式(1)：

$C_N=\underset{k=1}{\overset{8}{\mathrm{\Σ}}}|X_{k+1}-X_k|=2,X9=X1---\left(1\right)$

如果M是分歧点，则满足下面的公式(2)：

$C_N=\underset{k=1}{\overset{8}{\mathrm{\Σ}}}|X_{k+1}-X_k|=6,X9=X1---\left(2\right)$

用3×3的模板逐点对细化后的指纹图像的脊线进行检测，就可初步选出所有的细节特征，记录下这些细节特征的类型和位置坐标，以便于下一步的剪枝处理。

(二)细节点剪枝：对于细化后的点线指纹图，主要有如图3所示的几种伪特征结构。图3(a)是因为脊线断裂产生了两个错误端点；而3(b)和3(c)是因为脊线的错误连接和断开产生了伪分歧点和伪端点；3(d)是在对非平滑脊线进行细化后产生的短枝；3(e)是因为脊线间的错误连接产生伪分歧点。本实施例采用论文“指纹细节特征提取与剪枝”(王崇文，李见为等，光电工程，2002，No.4，pp67-70)中的细节点剪枝算法，针对每一类细节伪特征分别进行剪枝。

1消除图像的边缘效应

在图像的边缘，由于指纹传感器本身的原因以及图像预处理过程的不完整性，一般有大量的伪特征。可采用以下办法消除它们：对初选出的特征，计算它们与边界的距离，当距离小于预先设定的阈值Td时(本实施例中，针对256×256的指纹图像，Td取25)，则认为该特征点不可靠，从指纹特征中删除该点的记录。

2删除图像的模糊部分带来的伪特征点

图像的模糊部分，在细化之后，会出现大量的断点和分叉，这些对于指纹识别来说，都是些不可靠的信息。因此要去除这部分的伪特征点。去除这些伪特征点可以利用两个标准，首先是在单位区域内的细节密度标准，接着又考虑到在图像清晰可靠的区域，特征的垂直对比度应比较大，而平行对比度则比较小。所以，去除步骤如下：

算法一(如图4所示)：

(1)计算各特征点的结构数Ne和Nb；

(2)如果(Ne＞Te)，其中Te为预先设定的端点的个数(本实施例中取5)，执行步骤(6)；

(3)如果(Nb＞Tb)，其中Tb为预先设定的分歧点的个数(本实施例中取3)，执行步骤(6)；

(4)如果(Ne+Nb＞Ts)，其中Ts为预先设定的结构数(本实施例中取6)，执行步骤(6)；

(5)如果((Varo-Varp)/logB＜Tc)，其中B为灰度图像块的均值，Tc为预先设定的对比度阈值(Tc的值可以用统计方法获得。本实施例利用一定数量的指纹样本图像，用人工方法精确标定包含细节特征的图像块，计算各图像块的(Varo-Varp)/logB，求得均值M，以0.75M作为Tc的备选值)，执行步骤(6)，否则执行步骤(7)；

(6)删除该特征点，算法结束；

(7)保留该特征点。

3、删除因脊线断裂造成的伪特征点

如图3(a)、(b)、(c)所示的由于指纹脊线断裂和误连会产生一些伪细节特征，对于这些伪特征，主要考虑细节点间的距离和方向关系，故采用以下的方法对其进行处理：

算法二(如图5所示)：

(1)确定一特征点m1，计算其方向θ1；

(2)如果存在另一特征点m2，满足(d(m1，m2)＜Td1)，其中Td1为预设的距离阈值(本实施例中Td1设置为单倍指纹宽度)，删除特征点m1和m2；

(3)如果存在另一特征点m2，满足(d(m1，m2)＜Td2且θ1-θ2≈±π)，其中θ2为特征点m2的方向角，Td2为预设的距离阈值(本实施例中Td2设置为1.5倍指纹宽度)，则删除特征点m1和m2。

4、删除短枝和桥形伪特征点

如图3(d)和(e)是由短枝和桥形造成的伪特征点。仔细观察这两种结构，短枝分歧点的两个分支一般在一条直线上，而第三条分支的方向一般与另两条有明显差异；对于桥形分歧点，一般是两条分支共线，而第三条与之近似垂直。本发明在算法中用到了三个预设值θbs1、θbs2、θbs3，θbs1表示两条分支垂直(本实施例中设为75度)，θbs2和θbs3都表示两分支共线(本实施例中分别设置为15度和25度)，下面介绍处理的算法过程：

算法三(如图6所示)：

(1)对于每一个分歧点，搜索其各条分支，如果各条分支的长度均大于λ，则执行以下步骤，否则执行步骤(2)；

(a)用一元线性回归的方法估算各分支的方向；

(b)如果有两条分支共线即夹角小于θbs2且第三条分支垂直于共线的两分支，沿垂直的分支搜索，搜索长度为5λ/6；如果找到另一个特征点——分歧点或端点)，则找到短枝或桥形，删除这两个伪细节；

(c)如果有两条分支共线即夹角小于θbs2且第三条分支不垂直于共线的两分支，沿第三条分支搜索，搜索长度为3λ/2；如果找到另一个端点，则找到短枝，删除这两个伪细节；

(2)如果只有两条分支长度大于λ，则执行以下步骤，否则执行步骤(3)；

(a)用一元线性回归的方法估算这两条分支的方向；

(b)如果这两条分支共线即夹角小于θbs3，沿第三条分支搜索，如果找到端点或分歧点，则为短枝或短桥形，删除这两个伪细节；

(3)如果最多只有一条分支长度大于λ，则删除该分歧点和长度不满λ分支上的端点。

删除了伪细节特征后，可以进一步根据指纹图像的拓扑性质来对存留的细节特征进行可靠性检测。由指纹图像可以看出，分歧点侧面的脊线与形成分歧点的脊线分支平行，基于这个特性，本实施例用论文“指纹细节特征提取与剪枝”(王崇文，李见为等，光电工程，2002，No.4，pp67-70)中提到的可靠性验证方法对分歧点的可靠性进行检测：

算法四(如图7所示)：

(1)对于每一个分歧点的每一条分支，用3λ/2个点来进行直线拟合，估算出各分支的方向角；

(2)沿各分支跟踪，如果在λ长度内出现另一细节特征，则该分歧点不可靠，算法结束；

(3)沿各分支跟踪至λ/2处，在垂直于各分支的方向上，检测是否在3λ/2的范围内存在临近脊线(如图8(a)所示)；

(4)如果有一条以上脊线未找到，则该分歧点不可靠，算法结束；

(5)如果都找到了临近脊线，则标记该分歧点为一般可靠；

(6)定义一个矩形ABCD，其中AC的长度为3λ/2，AB的长度为4λ(如图8(b)所示)；

(7)从临近脊线与矩形的左交点P0和P1出发，沿临近脊线搜索；

(8)如果发现一个端点，则该分歧点不可靠，算法结束；

(9)如果存在右交点P2和P3，则该分歧点高度可靠。

对于端点特征，由指纹图像可知，脊线端点两侧的脊线逐步靠近，以保证指纹脊线间的距离保持基本恒定。基于此特性，我们用以下算法来验证端点的可靠性：

算法五(如图9所示)：

(1)用λ个点来进行直线拟合，估算端点所在脊线的方向角；

(2)如果端点所在脊线的长度小于λ，则该端点不可靠，算法结束；

(3)从端点出发，沿脊线跟踪至λ/2处，在垂直于脊线的方向上，检测是否在±3λ/2的范围内存在临近脊线；

(4)如果找不到两根脊线，则该端点不可靠，算法结束；

(5)定义一个矩形ABCD，其中AB的长度为3λ/2，AD的长度为3λ(如图10所示)；

(6)从临近脊线与矩形的左交点P0和P1出发，沿临近脊线搜索；

(7)如果一条脊线与AC或BD相交且另一条临近脊线与DC相交，则标记该端点一般可靠；

(8)如果在搜索过程中发现另一特征点，则该端点不可靠，算法结束；

(9)如果两条临近脊线都与DC相交，则检测：

(a)如果两临近脊线的夹角小于预设阈值θw(本实施例设为10度)也即两脊线近似平行，则该端点高度可靠；否则该端点一般可靠，算法结束；

(b)如果在P2和P3之间检测到另一脊线，则该端点不可靠，算法结束；

(三)构建特征矢量：在本发明中，为了减少指纹形变对特征匹配的影响，定义了一种新的细节特征矢量，它总共包含24个元素，表示方法如下：

FC＝{x，y，ω，var，f，cx，cy，r，d1，a1，s1，l1，d2，a2，s2，l2，d3，a3，s3，l3，d4，a4，s4，l4}

各元素的含义如图11所示：m0是当前待研究的细节特征点，即中心细节点，它的方向为o0(该方向值可以在预处理阶段获得)。以m0为坐标原点，以o0为x轴的正方向，构建坐标系(如图虚线所示)，m1，m2和m3是分别位于第一、第二和第三象限的细节特征点，这些特征点应该是在各象限所有细节点中距离m0最近的。oi是各细节点mi的方向，x和y是中心细节点m0在原来坐标系中位置坐标，ω是包含中心细节点的局部脊线方向，即图中的o0。考虑到特征提取过程中误差，用参数var和f取代了类型参数，var是在原始指纹图像中以m0为中心的局部窗口内各象素的灰度方差，f是在原始指纹图像中包含m0的局部窗口的频率，它代表局部窗口中脊线的频率。这两个参数都可以在指纹预处理阶段获得。

如果仔细观察指纹图像，就会发现大多数的脊线在有限长度内可以当作是圆弧的一部分，基于这一点，本发明使用了3个参数来表示与细节特征点相连的脊线，它们分别是cx，cy和r。把与细节特征点相连的脊线看作是一段圆弧，利用圆弧上的三个点就可以得到所在圆的中心坐标和半径。考虑到弹性形变的影响，利用最小二乘法去拟合脊线，最后用中心的平均坐标cx、cy和半径的平均值r来表示与细节特征点相连的脊线。

di，si，ai and li(i＝1，2，3，4)是中心细节特征点的邻域关系特征，它们描述了中心细节点m0与周围细节点mi之间的关系。di分别是mi到m0的距离，ai是m0方向角所在直线与mi方向角所在直线的夹角，si是m0与mi连线所在直线分别和m0方向角所在直线的夹角。l1，l2，l3和l4分别是mi特征点在所有细节点集合中的索引。考虑到在某些情况下无法为某个象限确定合适的细节特征，例如，在图11中，在第四象限找不到合适的细节点，那么就用一个特殊的极小值来标识d4，s4，a4和i4，如-1。

二、指纹特征匹配

所述特征匹配的过程为：首先利用脊线的曲率特征进行匹配参考点对的识别；然后利用极坐标对图像进行校准；接着利用自适应弹性匹配方法进行细节点配对和匹配分值计算；最后利用匹配的点对数和匹配分值，采用多级判别体系进行指纹匹配。具体处理流程如图1右半部分所示。现对每一处理流程分述如下：

1.识别匹配参考点对：首先，需要对已经获得的两个点集的矢量特征按照曲率大小的顺序排序，如果输入指纹的第i的细节点和模板指纹的第j个特征点存在对应关系，那么与这两个特征点相连的脊线的曲率r_i和r_j也应该是基本相同的，并且该曲率是不随图像旋转或平移所变化的，于是有如果|r_i-r_j|＜T_r，其中T_r为给定的阈值(在本实施例中，对于分辨率为500DPI的指纹图像，其T_r取25)，则可以利用公式计算两个细节特征的相似度。如果S(i，j)＞Ta(在本实施例中，Ta的取值为0.75)，则可以认为对应点对已经找到。否则如果计算了所有曲率相同的点对之间的相似度，没有哪个点对的相似度大于给定的阈值Ta，则可以把具有最大相似度的点对作为后续图像校准的中心。如果点对的最大相似度小于给定的阈值Tb(在本实施例中，Tb的取值为0.25)，则可以直接判断两个图像不匹配。

相似度计算公式中T是预先定义的阈值(T的值可以用统计方法获得。本实施例利用一定数量的指纹样本图像，用人工方法精确标定具有完全对应关系的指纹细节，计算各对应点对的特征矢量的欧式距离，求得均值M和方差δ，以M+2δ作为T的备选值)，|FC_i-FC_j|是两个特征矢量的欧氏距离。

2.图像校准：图像校准的目的在于消除两幅指纹图像的几何形变。利用平移变换参数和旋转变换参数可以修正图像间的刚性形变。对于非线性形变，因为其主要出现在图像中心区域，其表现形式为非线性的向外辐射。因此，采用极坐标表示方法是一种更有效的解决方法。进行图像校准的步骤如下：

1)把输入指纹图像和模板指纹图像原来笛卡儿坐标系下的细节点转换到极坐标下，极坐标的原点为上一步确定的对应参考点对，转换公式如下所示。

$\left(\begin{array}{c}{\mathrm{pr}}_i\\ e_i\\ {\mathrm{\θ}}_i\end{array}\right)=\left(\begin{array}{c}\sqrt{{(x_i-x_r)}^2+{(y_i-y_r)}^2}\\ {\tan }^{-1}\left(\frac{y_i-y_r}{x_i-x_r}\right)-{\mathrm{\ω}}_r\\ {\mathrm{\ω}}_i-{\mathrm{\ω}}_r\end{array}\right)$

式中(x_i，y_i，ω_i)^T是细节点在原来坐标系下的取值，(x_r，y_r，ω_r)^T是图像校准中心在原来坐标系的值，(pr_i，e_i，θ_i)^T是转换后细节点极坐标的值，其中pr_i代表极径，e_i代表极角，θ_i代表细节点i的方向与校准中心细节点方向的差值。这样一来，就可以把原来的特征矢量FC改成一种更为简洁的形式FC′＝(pr_i，e_i，θ_i，var，f，r)，其中var，f和r的含义和FC中定义一样。

2)把新的特征矢量集合按照极角的升序进行排列，结果如下：

$P_a^{\′}=\left\{\right[{\mathrm{pr}}_1^P,e_1^P,{\mathrm{\θ}}_1^P,{\mathrm{var}}_1^P,f_1^P,r_1^P]...[{\mathrm{pr}}_m^P,e_m^P,{\mathrm{\θ}}_m^P,{\mathrm{var}}_m^P,f_m^P,r_m^P\left]\right\}$

$Q_a^{\′}=\left\{\right[{\mathrm{pr}}_1^Q,e_1^Q,{\mathrm{\θ}}_1^Q,{\mathrm{var}}_1^Q,f_1^Q,r_1^Q]...[{\mathrm{pr}}_n^Q,e_n^Q,{\mathrm{\θ}}_n^Q,{\mathrm{var}}_n^Q,f_n^Q,r_n^Q\left]\right\}$

3.细节点配对与匹配计算：由于存在非线性变形，这就要求匹配算法要有一定的弹性。通常，在匹配过程中，会利用一个边界盒来进行弹性匹配，即在模板指纹的细节点上放一个边界盒，然后检查对应的输入指纹位置，看是否有细节点落在边界盒内。本发明所采用的细节点配对算法利用了自适应弹性匹配方法，即边界盒的范围是随着细节点距离匹配中心的距离的远近而不断调整的。判断两个细节点存在对应关系的条件如下：

两个细节点的极径差值小于给定阈值Δpr(本实施例取单倍纹线宽度λ)；

两个细节点的极角差值小于给定阈值Δe(本实施例取15度)。

假设Pi模板指纹上一个细节点，Qj是输入指纹上与Pi存在对应关系的细节点，则它们直接匹配分值S(i，j)可以用公式

计算。如果匹配分值S(i，j)大于给定的阈值Tm(在本实施例中，Ta的取值为0.70)，则可以认为这两个细节点匹配，在记录它们匹配分值的同时，把已经匹配的细节点总数Nm加1；否则，只记录两个细节点匹配的分值。

4.指纹匹配：计算完所有存在对应关系的细节点对的匹配分值后，则可以得到匹配的细节点对总数Nm和匹配分值之和Mm，其中M_m＝∑S(i，j)。下面将介绍多级判别体系：

首先，如果N_m≥12或N_m/Max(N，M)≥0.6，其中N和M分别是指纹模板和输入图像细节点的数量，则可以直接判断两幅指纹图像来自同一个手指；

否则，如果N_m＜6，则可以直接判断两幅指纹图像不匹配；

如果10≤N_m≤11并且M_m≥T1，则也可以判断两幅指纹图像匹配成功；

如果8≤N_m≤9并且M_m≥T2，则也可以判断两幅指纹图像匹配成功；

其他情况都可以判断两幅图像不匹配。

其中T1和T2都是预先设定的阈值，并且满足T1＜T2。

其中T1和T2都是预先设定的阈值，可根据一定数量的指纹样本统计而得，在本实施例中分别为11和12.5。

Claims (4)

1.一种指纹识别方法，其特征在于由指纹特征提取和特征匹配两个步骤组成：

所述指纹特征提取的过程为：

1)针对于预处理的图像进行细节特征初选；

2)对初选后的细节特征进行剪枝，所述细节特征剪枝的伪特征包括：因为脊线断裂产生的两个错误端点；因为脊线的错误连接和断开产生的伪分歧点和伪端点；在对非平滑脊线进行细化后产生的短枝；因为脊线间的错误连接产生的伪分歧点；

3)对剪枝后的细节点特征进行可靠性验证；

4)根据细节点的邻域关系和脊线曲率特征构建特征矢量，具体步骤为：

定义一种新的细节特征矢量，它总共包含24个元素，表示方法如下：

FC＝{x，y，ω，var，f，cx，cy，r，d1，a1，s1，l1，d2，a2，s2，l2，d3，a3，s3，l3，d4，a4，s4，l4}

其中：x和y是当前待研究的细节点m0即参考细节点在原来坐标系中位置坐标，ω是包含参考细节点的局部脊线方向，参数var是在原始指纹图像中以参考细节点为中心的局部窗口内各象素的灰度方差，f是在原始指纹图像中包含参考细节点的局部窗口的频率，它代表局部窗口中脊线的频率；cx、cy和r表示与细节特征点相连的脊线所拟合圆弧的中心位置坐标和半径；di，si，ai and li(i＝1，2，3，4)是参考细节特征点的邻域关系特征，它们描述了参考细节点m0与周围细节点mi之间的关系；di分别是mi到m0的距离，ai是m0方向角所在直线与mi方向角所在直线的夹角，si是m0与mi连线所在直线分别和m0方向角所在直线的夹角；l1，l2，l3和l4分别是mi特征点在所有细节点集合中的索引；

所述特征匹配的过程为：

1)利用脊线的曲率特征进行匹配参考点对的识别，具体步骤为：

首先，需要对已经获得的两个点集的矢量特征按照曲率大小的顺序排序，如果输入指纹的第i个细节点和模板指纹的第j个特征点存在对应关系，那么与这两个特征点相连的脊线的曲率r_i和r_j也应该是相同的，并且该曲率是不随图像旋转或平移所变化的，于是有如果|r_i-r_j|＜T_r，其中T_r为给定的阈值，则利用公式

计算两个细节特征的相似度，如果S(i，j)大于给定的阈值Ta，则认为对应点对已经找到；否则如果计算了所有曲率相同的点对之间的相似度，没有哪个点对的相似度大于Ta，则把具有最大相似度的点对作为后续图像校准的中心；如果点对的最大相似度小于给定的阈值Tb，则直接判断两个图像不匹配；

相似度计算公式中T是预先定义的阈值，T的值用统计方法获得；|FC_i-FC_j|是两个特征矢量的欧氏距离；

2)利用极坐标对图像进行校准，具体步骤为：

(1)把输入指纹图像和模板指纹图像原来笛卡儿坐标系下的细节点转换到极坐标下，极坐标的原点为已经确定的对应参考点对，转换公式如下所示：

$\left(\begin{array}{c}{\mathrm{pr}}_i\\ e_i\\ {\mathrm{\θ}}_i\end{array}\right)=\left(\begin{array}{c}\sqrt{{(x_i-x_r)}^2+{(y_i-y_r)}^2}\\ {\tan }^{-1}\left(\frac{y_i-y_r}{x_i-x_r}\right)-{\mathrm{\ω}}_r\\ {\mathrm{\ω}}_i-{\mathrm{\ω}}_r\end{array}\right)$

式中(x_i，y_i，ω_i)^T是细节点在原来坐标系下的取值，(x_r，y_r，ω_r)^T是图像校准中心在原来坐标系的值，(pr_i，e_i，θ_i)^T是转换后细节点极坐标的值，其中pr_i代表极径，e_i代表极角，θ_i代表细节点i的方向与校准中心细节点方向的差值；这样一来，就把原来的特征矢量FC改成一种更为简洁的形式FC′＝(pr_i，e_i，θ_i，var，f，r)，其中var，f和r的含义和FC中定义一样；

(2)把新的特征矢量集合按照极角的升序进行排列，结果如下：

$P_a^{\′}=\left\{\right[{\mathrm{pr}}_1^P,e_1^P,{\mathrm{\θ}}_1^P,{\mathrm{var}}_1^P,f_1^P,r_1^P\left]\mathrm{\Λ}\right[{\mathrm{pr}}_m^P,e_m^P,{\mathrm{\θ}}_m^P,{\mathrm{var}}_m^P,f_m^P,r_m^P\left]\right\}$

$Q_a^{\′}=\left\{\right[{\mathrm{pr}}_1^Q,e_1^Q,{\mathrm{\θ}}_1^Q,{\mathrm{var}}_1^Q,f_1^Q,r_1^Q\left]\mathrm{\Λ}\right[{\mathrm{pr}}_n^Q,e_n^Q,{\mathrm{\θ}}_n^Q,{\mathrm{var}}_n^Q,f_n^Q,r_n^Q\left]\right\};$

3)接着利用自适应弹性匹配方法进行细节点配对和匹配分值计算；

4)利用匹配的点对数和匹配分值，采用多级判别体系进行指纹匹配，具体步骤为：

计算完所有存在对应关系的细节点对的匹配分值后，则得到匹配的细节点对总数Nm和匹配分值之和Mm，其中M_m＝∑S(i，j)；

首先，如果N_m≥12或N_m/Max(N，M)≥0.6，其中N和M分别是指纹模板和输入图像细节点的数量，则直接判断两幅指纹图像来自同一个手指；

否则，如果N_m＜6，则直接判断两幅指纹图像不匹配；

如果10≤N_m≤11并且M_m≥T1，则也判断两幅指纹图像匹配成功；

如果8≤N_m≤9并且M_m≥T2，则也判断两幅指纹图像匹配成功；

其他情况都判断两幅图像不匹配；

其中T1和T2都是预先设定的阈值，并且满足T1＜T2，根据一定数量的指纹样本统计而得。

2.根据权利要求1所述的一种指纹识别方法，其特征在于：在识别匹配参考点对的步骤中，对于分辨率为500DPI的指纹图像，其T_r取25，Ta的取值为0.75，Tb的取值为0.25。

3.根据权利要求1或2所述的一种指纹识别方法，其特征在于：在识别匹配参考点对的步骤中，利用一定数量的指纹样本图像，用人工方法精确标定具有完全对应关系的指纹细节，计算各对应点对的特征矢量的欧式距离，求得均值M和方差δ，以M+2δ作为T的备选值。

4.根据权利要求1所述的一种指纹识别方法，其特征在于：在指纹匹配的步骤中，T1和T2的值分别为11和12.5。

Images