基于二部图最佳匹配的指纹匹配方法

摘要

本发明公开了一种基于二部图最佳匹配的指纹匹配方法，首先采用局部匹配以获得一系列参考点对，然后在更高层次上对已获得的参考点对通过构建拓扑结构进行验证，使匹配效果达到全局最优。本发明包括：计算输入指纹细节点与模板指纹任意细节点对相似度；构造二部图的步骤；利用KM算法得出最佳匹配。更进一步包括通过建立细节点的拓扑结构去除错误匹配点对的步骤。本发明凸显了图像匹配中的全局性，进一步提高了算法鲁棒性，抗噪能力强，能够兼顾匹配精度和运算时间，使匹配效果达到全局最优。

说明书

技术领域

本发明属于图像处理技术领域，涉及一种指纹识别技术，更为具体地说，是设计一种基 于二部图最佳匹配的指纹匹配方法。

背景技术

信息化社会中，身份认证是安全快速地进行信息传递的基础，而传统的身份认证由于极 易伪造和丢失，越来越难以满足社会的需求，目前最为便捷与安全的解决方案无疑就是生物 识别技术。生物特征识别技术是利用人的生理特征或行为特征，来进行个人身份的鉴定。它 不但简洁快速，而且利用它进行身份的认定更为安全、可靠、准确；同时更易于配合电脑和 安全、监控、管理系统整合，实现自动化管理。由于其广阔的应用前景、巨大的社会效益和 经济效益，生物特征识别技术已引起各国的广泛关注和高度重视。指纹识别是生物特征识别 技术中发展较为快速的分支，指纹具有唯一性和易采集性的特点，应用范围非常广泛。而自 动指纹识别系统(AFIS)由于其体积小、成本低、易操作、可靠性高等优点越来越受到人们的 青睐，成为最重要的生物识别技术之一。

一般的自动指纹识别方法包括：图像采集、图像分割、方向场估计、图像增强、二值化 及细化、特征点提取、特征匹配等步骤。特征匹配作为整个系统中的最后一步，其主要任务 是根据事先提取出的特征将输入指纹细节点与模板指纹细节点进行匹配，如果匹配上的细节 点对数超过某一阀值，则判定输入指纹与模板指纹匹配，完成特征识别。

目前，已有大量的指纹匹配算法被提出，现有指纹匹配算法大致可分为以下几类：基于 相关性的匹配；基于点模式匹配；基于脊线特征的匹配等等。其中基于点模式的匹配是目前 研究最为活跃、应用最为广泛的指纹匹配方法。基于点模式的匹配方法已有大量的研究工作， 其中有：基于全局匹配的方法和基于局部的匹配方法。其中，基于全局匹配的方法主要通过 构建细节点局部特征并对该局部特征计算相似度，最后进行全局配准并计算匹配分数。但由 于刚性形变，弹性形变，部分重叠等原因，都会导致误识率的升高，从而使得细节点匹配的 正确率降低。基于局部匹配的方法也同样通过细节点局部特征获取两幅带匹配指纹图像之间 的参考点对，最后基于所有参考点对的局部匹配结果计算匹配分数，由于不同指纹可能在局 部范围表现出较好的相似性，使得该类方法的误识率较高。此外，指纹图像由于手指皮肤过 干、过湿、手指纹路很浅、手指有伤口、蜕皮，手指在采集时有脏物，采集设备的成像特性， 采集平面上的残留物等原因产生的噪声影响，都会使特征集不可靠而降低细节点匹配效果。 综上所述，现有的基于点模式的指纹匹配方法具有不少缺陷，正确率较低。

发明内容

为解决上述问题，本发明公开了一种基于二部图最佳匹配的指纹匹配方法，首先采用局 部匹配以获得一系列参考点对，然后在更高层次上对已获得的参考点对通过构建拓扑结构进 行验证，使匹配效果达到全局最优。

为了达到上述目的，本发明提供如下技术方案：

一种基于二部图最佳匹配的指纹匹配方法，包括如下步骤：

步骤A，获得输入指纹I，对输入指纹I和模板指纹T内的所有细节点进行标号， I_i(i∈1…m)，T_j(j∈1…n)；

步骤B，遍历输入指纹I的所有细节点，对于输入指纹I中的第i个细节点计算I_i与模板指纹 T内的所有细节点T_j(j∈1…n)之间的相似度IS_ij，选取相似度最小的点对并记录对应的输入指 纹细节点编号，模板指纹细节点编号和相似度值；遍历模板指纹T的所有细节点，对于模板指 纹T中的第j个细节点，计算T_j与I_i(i∈1…m)之间的相似度TS_ij，选取相似度最小的点对并记录 对应的输入指纹细节点编号，模板指纹细节点编号和相似度值；

步骤C，根据步骤B中记录下信息，构造二部图；

步骤D，对于步骤C构造的二部图，采用KM算法计算得出令所有边权的和最大的匹配。

进一步的，还包括步骤E：构建细节点的拓扑结构去除错误匹配的细节点对。

进一步的，所述步骤B包括如下步骤：计算各输入指纹细节点I_i(i∈1…m)与各模板指纹 细节点T_j(j∈1…n)之间的相似度S_ij，构造相似度矩阵Similar_Arr(m，n)：

所述步骤C包括如下步骤：根据步骤B中记录下的相似度值和细节点对编号，将相似度 矩阵Similar_Arr中对应的S_ij乘以-10000，将剩余值附为无穷小，构造二部图。

进一步的，所述步骤E包括如下步骤：

对任意细节点对(I_i，T_j)，在输入指纹中选取11个距离细节点I_i最近的细节点 P_k(k＝1…11)，计算它们与点I_i的欧氏距离dI_ik和角度差dA_ik：

${\mathrm{dI}}_{\mathrm{ik}}=\sqrt{{(x_i-x_k)}^2+{(y_i-y_k)}^2}$

dA_ik＝I_i，dir-P_k，dir

${\mathrm{dA}}_{\mathrm{ik}}=\left(\begin{array}{cc}{\mathrm{dA}}_{\mathrm{ik}}-\pi & {\mathrm{dA}}_{\mathrm{ik}}\ge \frac{\pi }{2}\\ {\mathrm{dA}}_{\mathrm{ik}}+\pi & {\mathrm{dA}}_{\mathrm{ik}}<-\frac{\pi }{2}\end{array}\right)$

同样在模板指纹中选取11个距离细节点T_j最近的细节点Q_k(k＝1…11)，计算它们与点T_j的欧氏距离dI_jk和角度差dA_jk：

${\mathrm{dI}}_{\mathrm{jk}}=\sqrt{{(x_j-x_k)}^2+{(y_j-y_k)}^2}$

dA_jk＝I_j.dir-P_k.dir

${\mathrm{dA}}_{\mathrm{jk}}=\left(\begin{array}{cc}{\mathrm{dA}}_{\mathrm{jk}}-\pi & {\mathrm{dA}}_{\mathrm{jk}}\ge \frac{\pi }{2}\\ {\mathrm{dA}}_{\mathrm{jk}}+\pi & {\mathrm{dA}}_{\mathrm{jk}}<-\frac{\pi }{2}\end{array}\right)$

对于细节点对(I_i，T_j)，若对应邻接细节点距离比且方向差 |dA_ik-dA_jk|＜thr_dir，则细节点对(I_i，T_j)的邻接点匹配数加1，当细节点对(I_i，T_j)的邻接点 匹配数小于等于3时去除该匹配点对。

与现有技术相比，本发明具有如下优点和有益效果：

本发明采用二部图最佳匹配凸显了图像匹配中的全局性，通过建立细节点的拓扑结构来 去除错误匹配点对，进一步提高了算法鲁棒性，抗噪能力强，能够兼顾匹配精度和运算时间， 使匹配效果达到全局最优。

附图说明

图1为待匹配指纹初步匹配结果；

图2为二部图示意图；

图3为二部图匹配结果图；

图4为经过错误去除步骤的最终匹配结果。

具体实施方式

以下将结合具体实施例对本发明提供的技术方案进行详细说明，应理解下述具体实施方 式仅用于说明本发明而不用于限制本发明的范围。

本发明提供的基于二部图最佳匹配的指纹匹配方法，包括如下步骤：

步骤A，首先，将输入指纹I，模板指纹T内的所有细节点进行标号I_i(i∈1…m)， T_j(j∈1…n)，其中，m为输入指纹I中细节点的数量，n为模板指纹T内细节点的数量。

步骤B，确定输入指纹与模板指纹任意细节点对的相似度：遍历输入指纹的所有细节点， 对于输入指纹I中的第i个细节点计算I_i与模板指纹T内的所有细节点T_j(j∈1…n)之间的相似 度IS_ij，选取相似度最小的点对并记录对应的输入指纹细节点编号，模板指纹细节点编号和相 似度值；遍历模板指纹的所有细节点，对于模板指纹T中的第j个细节点，计算T_j与I_i(i∈1…m) 之间的相似度TS_ij，选取相似度最小的点对并记录对应的输入指纹细节点编号，模板指纹细节 点编号和相似度值。这样，针对输入指纹和模板指纹中的个细节点，都能够找到对应模板中 与之相似度最小的细节点，由此得到的初步匹配结果，如图1所示，其中左侧为输入指纹， 右侧为模板指纹。

本例在选取相似度最小的点对时，首先计算各输入指纹细节点I_i(i∈1…m)与各模板指纹 细节点T_j(j∈1…n)之间的相似度S_ij，构造相似度矩阵Similar_Arr(m，n)如下

求取Similar_Arr中每一行的最小值，并将该最小值以及相对应的输入指纹细节点编号， 模板指纹细节点编号存入Couple1中，Couple1的物理意义即为对输入指纹中任意细节点，在 模板指纹中寻找到的与之最为匹配的细节点。同理，求取Similar_Arr中每一列的最小值，并 将该最小值以及相对应的模板指纹细节点编号，输入指纹细节点编号存入Couple2中，Couple2 的物理意义即为对模板指纹中任意细节点，在输入指纹中寻找到的与之最为匹配的细节点。

具体的说，计算两细节点(如细节点p、q)之间的相似度，首先需要获得两个细节点的OMD， 细节点的OMD通过以下步骤计算：

设p为当前细节点，其方向场角度为α。以p为中心，生成L个环，其半径分别为r₁、r₂…r_L， 假设第1个环的半径为r₁，在该环上采样K₁个点，则第1个采样点p_1，0位于沿α方向与该环的交 点处，其余采样点按逆时针方向依次均匀分布在该环上。假设第1个环上第k个采样点p_1，k的方 向场角度为α_1，k，则该点与p点的相对角度差β_1，k被定义为λ(α_1，k-α）,其中

$\lambda \left(\Delta \right)\left(\begin{array}{cc}\Delta -\pi & \mathrm{if\Delta }\ge \frac{\pi }{2}\\ \Delta +\pi & \mathrm{if\Delta }<-\frac{\pi }{2}\\ \Delta & \mathrm{otherwise}\end{array}\right)$

细节点p的OMD可表示为：

$\mathrm{OMD}\left(p\right)={\left\{{\left\{{\beta }_{1,k}\right\}}_{k=0}^{K_1-1}\right\}}_{1=0}^{L-1}$

对于分别来源于两幅指纹图像的OMD(p)、OMD(q)，通过下式计算细节点p、q之间的相 似度距离，相似度距离越小说明两点越相似：

$\mathrm{Similar}\_\mathrm{dis}=\underset{l=0}{\overset{L-1}{\Sigma }}\underset{k=0}{\overset{K_l-1}{\Sigma }}\left(\right|{\beta }_{l,k}^p-{\beta }_{l,k}^q\left|\right)$

步骤C，构造二部图：根据步骤B中的Couple1和Couple2相似度值和细节点对编号，将 相似度矩阵Similar_Arr中对应的S_ij乘以-10000，将剩余值附为无穷小，以此构造二部图(二 部图示意图如图2所示)，此时二部图两顶点集为两幅指纹(输入指纹和模板指纹)的细节点， 边集为任意一对细节点连线，其中，不存在于Couple1和Couple2的细节点对之间的边权值为 无穷小，存在于Couple1和Couple2中的细节点对边权值为细节点对相似度乘以-10000、将边 权值作为对应的权重，用权重矩阵Weight(M，N)表示如下：

若m＜n则M＝m,N＝n，否则M＝n,N＝m。其中W_mn表示细节点对(m，n)所对应边的边权 值

步骤D，得出最佳匹配：对于已构造的二部图，可以获得输入指纹细节点I_i和模板指纹细 节点T_j之间的边权为W_ij，设顶点I_i的顶标为I[i]，顶点T_j的顶标为T[j]。采用KM算法进行计算， 算法执行过程中的任一时刻，对于任一条边(i，j)，I[i]+T[j]≥W_ij始终成立，最终求得一种匹 配使得所有W_ij的和最大。本例获得的匹配结果如图3。

此外，在步骤D之后，本发明还能够通过构建细节点的拓扑结构去除错误匹配的细节点 对，以获得更为准确的匹配结果，具体过程如下：

对任意细节点对(I_i，T_j)，在输入指纹中选取一定数目距离细节点I_i最近的细节点 P_k(k＝1…11)，计算它们与点I_i的欧氏距离dI_ik和角度差，依据经验，本例中我们取11个细 节点。

${\mathrm{dI}}_{\mathrm{ik}}=\sqrt{{(x_i-x_k)}^2+{(y_i-y_k)}^2}$

dA_ik＝I_i.dir-P_k.dir

${\mathrm{dA}}_{\mathrm{ik}}=\left(\begin{array}{cc}{\mathrm{dA}}_{\mathrm{ik}}-\pi & {\mathrm{dA}}_{\mathrm{ik}}\ge \frac{\pi }{2}\\ {\mathrm{dA}}_{\mathrm{ik}}+\pi & {\mathrm{dA}}_{\mathrm{ik}}<-\frac{\pi }{2}\end{array}\right)$

同样在模板指纹中选取11个距离细节点T_j最近的细节点Q_k(k＝1…11)，计算它们与点T_j的欧氏距离dI_jk和角度差dA_jk。

${\mathrm{dI}}_{\mathrm{jk}}=\sqrt{{(x_j-x_k)}^2+{(y_j-y_k)}^2}$

dA_jk＝I_i，dir-P_k，dir

${\mathrm{dA}}_{\mathrm{jk}}=\left(\begin{array}{cc}{\mathrm{dA}}_{\mathrm{jk}}-\pi & {\mathrm{dA}}_{\mathrm{jk}}\ge \frac{\pi }{2}\\ {\mathrm{dA}}_{\mathrm{jk}}+\pi & {\mathrm{dA}}_{\mathrm{jk}}<-\frac{\pi }{2}\end{array}\right)$

对于细节点对(I_i，T_j)，若对应邻接细节点距离比(dis_down为对应邻接细 节点距离比的下阀值，dis_up为对应邻接细节点距离比的上阀值),且方向差 |dA_ik-dA_jk|＜thr_dir(thr_dir为对应邻接细节点方向差阀值)，则细节点对(I_i，T_j)的邻接点匹配数 加1。若细节点对(I_i，T_j)的邻接点匹配数大于3，则认为细节点对(I_i，T_j)为匹配细节点对，否则 认为不匹配，去除该匹配点对，经过本步骤后匹配结果如图4所示。

本发明方案所公开的技术手段不仅限于上述实施方式所公开的技术手段，还包括由以上 技术特征任意组合所组成的技术方案。应当指出，对于本技术领域的普通技术人员来说，在 不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也视为本发明的 保护范围。