一种指纹奇异点快速搜索方法

摘要

本发明涉及一种指纹奇异点快速搜索方法，步骤如下：(1)判断指纹特征A是否有三角点，如果有三角点，进行三角点快速搜索，否则进入步骤(2)；(2)判断指纹特征A是否有中心点，如果有中心点，进行中心点快速搜索，否则进入步骤(3)；(3)按照普通快速搜索方法搜索；(4)如果搜索成功返回成功，否则返回搜索失败；(5)搜索流程结束。本发明有益的效果是：使用同类型奇异点周围的指纹特征信息来计算2个指纹特征相似度，以达到能够快速计算相似度的效果。

权利要求

1.一种指纹奇异点快速搜索方法，其特征在于：步骤如下：（1）、判断指纹特征A是否有三角点，如果有三角点，进行三角点快速搜索，否则进入步骤（2）；

（2）、判断指纹特征A是否有中心点，如果有中心点，进行中心点快速搜索，否则进入步骤（3）；

（3）、按照普通快速搜索方法搜索；

（4）、如果搜索成功返回成功，否则返回搜索失败；

（5）、搜索流程结束；

其中，三角点快速搜索步骤如下：

（1.1）以指纹特征A的三角点为中心，选择半径Rmin到半径Rmax，统计其中所有的特征点信息集合：{AX[0]，AX[1]…AX[o]}，共o+1个特征点，如果指纹特征A有2个三角点，统计2个环形区域内所有的特征点；

（1.2）j=0；

（1.3）如果j

（1.4）选取指纹特征Bj，判断特征Bj是否有三角点，如果特征Bj没有三角点，则记录相似度得分Sj=0，把j加1后的结果再赋值给变量j，进入步骤（1.3）；如果特征Bj有三角点，则进入（1.5）步骤；

（1.5）以指纹特征Bj的三角点为中心，选择半径Rmin到半径Rmax，统计其中所有的特征点信息集合：{BX[0]，BX[1]…BX[pj]}，共pj+1个特征点，如果Bj有2个三角点，统计2个环形区域内所有的特征点；

（1.6）快速计算A、Bj选择的特征点集合之间的相似度，即比对o个和pj个特征点之间的相似度，记录到得分Sj中，把j加1后的结果再赋值给变量j，进入步骤（1.3）；

（1.7）寻找相似度得分Sj最大的Bj，记录为Bz；

（1.8）比对A、Bz，如比对成功，则返回搜索成功，搜索流程结束，否则三角点搜索失败，进入步骤（2）；

其中，中心点快速搜索步骤如下：

（2.1）以指纹特征A的中心点为中心，选择半径Rmin到半径Rmax，统计其中所有的特征点信息集合：{AX[0]，AX[1]…AX[o2]}，共o2+1个特征点，如果指纹特征A有2个中心点，统计2个环形区域内所有的特征点；

（2.2）j=0；

（2.3）如果j

（2.4）选取特征Bj，判断特征Bj是否有中心点，如果特征Bj没有中心点，则记录相似度得分Sj=0，把j加1后的结果再赋值给变量j，进入步骤（2.3）；如果特征Bj有中心点，入步骤（2.5）；

（2.5）以特征Bj的中心点为中心，选择半径Rmin到半径Rmax，统计其中所有的特征点信息集合：{BX[0]，BX[1]…BX[p2j]}，共p2j+1个特征点，如果Bj有2个中心点，统计2个环形区域内所有的特征点；

（2.6）快速计算A、Bj选择的特征点集合之间的相似度，即比对o2个和p2j个特征点之间的相似度，记录到得分Sj中，把j加1后的结果再赋值给变量j，进入步骤（2.3）；

（2.7）寻找相似度得分Sj最大的Bj，记录为Bz；

（2.8）比对A、Bz，如比对成功，则返回搜索成功，搜索流程结束，否则中心点搜索失败，进入步骤（3）。

说明书

一种指纹奇异点快速搜索方法

技术领域

[0001] 本发明涉及生物特征识别领域，尤其是一种指纹奇异点快速搜索方法。

背景技术

[0002] 生物特征识别技术是指利用人体生物特征进行身份认证的一种技术。生物识别系统是对生物特征进行取样，通过提取特征的算法将取样出的生物特征转化成数字特征，并进一步将这些特征组合而成的特征模板，存入数据库中。在识别系统进行身份认证时，识别系统获取现场生物特征，转换为数字特征并与数据库中存放的特征模板进行比对，计算出二者之间的相似度，以确定是否匹配，从而决定接受或拒绝该人。

[0003] 指纹是生物特征的一种，具有唯一、再生、不可抵赖、方便提取、易于辨识等特点。目前指纹识别技术是生物特征识别技术中最成熟的技术，已被全球大部分国家政府接受与认可，已广泛地应用到政府、军队、银行、社会福利保障、电子商务和安全防卫等领域。

[0004] 指纹识别技术主要包括指纹图像采集、指纹图像预处理及图像增强、指纹特征提取、指纹特征比对和搜索等。在指纹识别系统工作中一般均需要使用到1:N搜索，对于N很大的系统，搜索时间占整个指纹识别工作时间的绝大部分。所以指纹搜索的速度、性能在很大程度上决定了整个指纹识别系统的速度，性能，占用很重要的地位。

[0005] 判定2个指纹特征是否为同一指纹产生，需要进行指纹特征比对，即精确计算2个指纹特征的相似度，如果相似度大于某个阈值，则可判定2个特征为同一手指产生，即比对通过。指纹特征包含了较多的信息，指纹特征比对需要较大的计算量，占用较多的时间。在应用中，需要在N个待搜索指纹特征{B[1]，B[2]，B[3]...B[N]}中寻找是否有和指纹特征A比对通过的指纹特征。如果将A和{B[1]，B[2]，B[3]...B[N]}，一一进行指纹比对，则需要时间为：N*time(time为2个指纹特征比对的平均时间)。这样在N很大时候，需要的时间会很长，导致实时性下降，从而无法在产品中得到应用。

[0006] 所以提出了指纹快速搜索算法，即通过快速计算，在N个待搜索特征中找到k个最相似的指纹特征{C[1]，C[2]......C[k]}，需要时间一般＜(N*time)/10。这样只要将A和k个指纹特征{C[1]，C[2]......C[k]}一一做指纹比对，即可找到是否有指纹特性和指纹特征A比对通过。例如：专利：02110873.0《指纹识别方法与系统》中提到了在模糊匹配阶段，使用简约数据链表计算相似度，并取出相似度最高的若干个特征，进入精确比对阶段。专利：200810207425.4《快速指纹搜索方法及快速指纹搜索系统》中提到了一种快速指纹搜索方法。

发明内容

[0007] 本发明的目的正是要解决上述技术存在的不足，而提供一种指纹奇异点快速搜索方法，可以极大加快包含奇异点信息的指纹特征搜索速度。

[0008] 本发明解决其技术问题采用的技术方案：这种指纹奇异点快速搜索方法，步骤如下：

[0009] (1)、判断指纹特征A是否有三角点，如果有三角点，进行三角点快速搜索，否则进入步骤(2)；

[0010] (2)、判断指纹特征A是否有中心点，如果有中心点，进行中心点快速搜索，否则进入步骤(3)；

[0011] (3)、按照普通快速搜索方法搜索；

[0012] (4)、如果搜索成功返回成功，否则返回搜索失败；

[0013] (5)、搜索流程结束。

[0014] 本发明中，所述的三角点快速搜索步骤如下：

[0015] (1.1)以指纹特征A的三角点为中心，选择半径Rmin到半径Rmax，统计其中所有的特征点信息集合：{AX[0]，AX[1]...AX[o]}，共o个特征点，如果指纹特征A有2个三角点，统计2个环形区域内所有的特征点；

[0016] (1.2)j＝0；

[0017] (1.3)如果j＜N，进入下一步骤(1.4)，否则进入步骤(1.7)；

[0018] (1.4)选取指纹特征Bj，判断特征Bj是否有三角点，如果特征Bj没有三角点，则记录相似度得分Sj＝0，j＝j+1，进入步骤(1.3)；

[0019] (1.5)以指纹特征Bj的三角点为中心，选择半径Rmin到半径Rmax，统计其中所有的特征点信息集合：{BX[0]，BX[1]...BX[pj]}，共pj个特征点，如果Bj有2个三角点，统计2个环形区域内所有的特征点；

[0020] (1.6)快速计算A、Bj选择的特征点集合之间的相似度，即比对o个和pj个特征点之间的相似度，记录到得分Sj中，j＝j+1，进入步骤(1.3)；

[0021] (1.7)寻找相似度得分Sj最大的Bj，记录为Bz；

[0022] (1.8)比对A、Bz，如比对成功，则返回搜索成功，搜索流程结束，否则三角点搜索失败，进入步骤(2)。

[0023] 本发明中，中心点快速搜索步骤如下：

[0024] (2.1)以指纹特征A的中心点为中心，选择半径Rmin到半径Rmax，统计其中所有的特征点信息集合：{AX[0]，AX[1]...AX[o2]}，共o2个特征点，如果指纹特征A有2个中心点，统计2个环形区域内所有的特征点；

[0025] (2.2)j＝0；

[0026] (2.3)如果j＜N，进入下一步骤(2.4)，否则进入步骤(2.7)；

[0027] (2.4)选取特征Bj，判断特征Bj是否有中心点，如果特征Bj没有中心点，则记录相似度得分Sj＝0，j＝j+1，进入步骤(2.3)；

[0028] (2.5)以特征Bj的中心点为中心，选择半径Rmin到半径Rmax，统计其中所有的特征点信息集合：{BX[0]，BX[1]...BX[p2j]}，共p2j个特征点，如果Bj有2个中心点，统计2个环形区域内所有的特征点；

[0029] (2.6)快速计算A、Bj选择的特征点集合之间的相似度，即比对o2个和p2j个特征点之间的相似度，记录到得分Sj中，j＝j+1，进入步骤(2.3)；

[0030] (2.7)寻找相似度得分Sj最大的Bj，记录为Bz；

[0031] (2.8)比对A、Bz，如比对成功，则返回搜索成功，搜索流程结束，否则中心点搜索失败，进入步骤(3)。

[0032] 本发明有益的效果是：使用同类型奇异点周围的指纹特征信息来计算2个指纹特征相似度，以达到能够快速计算相似度的效果。

附图说明

[0033] 图1为本发明的叉点示意图；

[0034] 图2为本发明的端点示意图；

[0035] 图3为本发明的中心点示意图；

[0036] 图4为本发明的三角点示意图；

[0037] 图5为本发明中原始图像A变为具有特征A的细化图像A的示意图；

[0038] 图6为本发明中原始图像B变为具有特征B的细化图像B的示意图；

[0039] 图7为本发明中奇异点搜索总流程图；

[0040] 图8为本发明中三角点搜索流程示意图；

[0041] 图9为本发明中中心点搜索流程示意图。

具体实施方式

[0042] 下面结合附图和实施例对本发明作进一步说明：

[0043] 本发明所述的这种指纹奇异点快速搜索方法，包括原始图像的图像处理、细化的脊线图、指纹特征提取和指纹特征的比对，本发明中，指纹特征提取，包括细节点、中心点的指纹特征提取，指纹比对流程：寻找基准点、特征旋转对齐、计算综合相似度的方法；所采用的方法见本公司申请的专利200610065297.5；

[0044] 奇异点附近细节点的比对：已知1个指纹特征A，1个待比对指纹特征B，比对指纹特征A和B，确定A、B是否为同一指纹产生。

[0045] 1：N搜索--已知1个指纹特征A，N个待搜索指纹特征{B[1]，B[2]......B[N]}，在N个待搜索指纹特征中寻找出是否有1个和指纹特征A来源于同一指纹的指纹特征。

[0046] 奇异点快速搜索原理：

[0047] 奇异点快速搜索基于下列简单事实：

[0048] 如果指纹特征A中含有某类奇异点a、指纹特征B中含有同类奇异点b，如果指纹特征A、B是同一枚指纹产生，则奇异点a必然和奇异点b对应，即奇异点a附近的特征信息和奇异点b附近的特征信息相似度很高。

[0049] 根据此原理，如果指纹特征A中含有某类奇异点a、指纹特征B中含有同类奇异点b，而奇异点a和奇异点b相似度很低，则指纹特征A和指纹特征B是同一枚指纹的可能性必然很低。

[0050] 这样我们仅选取奇异点附近一定范围内的特征信息进行快速相似度计算。这样由于减少了计算的特性信息量，减少了大量的计算量，从而提高了搜索的运算速度。

[0051] 这种指纹奇异点快速搜索方法，步骤如下：

[0052] (1)、判断指纹特征A是否有三角点，如果有三角点，进行三角点快速搜索，否则进入步骤(2)；

[0053] (2)、判断指纹特征A是否有中心点，如果有中心点，进行中心点快速搜索，否则进入步骤(3)；

[0054] (3)、按照普通快速搜索方法搜索；

[0055] (4)、如果搜索成功返回成功，否则返回搜索失败；

[0056] (5)、搜索流程结束。

[0057] 本发明中，所述的三角点快速搜索步骤如下：

[0058] (1.1)以指纹特征A的三角点为中心，选择半径Rmin到半径Rmax，统计其中所有的特征点信息集合：{AX[0]，AX[1]...AX[o]}，共o个特征点，如果指纹特征A有2个三角点，统计2个环形区域内所有的特征点；

[0059] (1.2)j＝0；

[0060] (1.3)如果j＜N，进入下一步骤(1.4)，否则进入步骤(1.7)；

[0061] (1.4)选取指纹特征Bj，判断特征Bj是否有三角点，如果特征Bj没有三角点，则记录相似度得分Sj＝0，j＝j+1，进入步骤(1.3)；

[0062] (1.5)以指纹特征Bj的三角点为中心，选择半径Rmin到半径Rmax，统计其中所有的特征点信息集合：{BX[0]，BX[1]...BX[pj]}，共pj个特征点，如果Bj有2个三角点，统计2个环形区域内所有的特征点；

[0063] (1.6)快速计算A、Bj选择的特征点集合之间的相似度，即比对o个和pj个特征点之间的相似度，记录到得分Sj中，j＝j+1，进入步骤(1.3)；

[0064] (1.7)寻找相似度得分Sj最大的Bj，记录为Bz；

[0065] (1.8)比对A、Bz，如比对成功，则返回搜索成功，搜索流程结束，否则三角点搜索失败，进入步骤(2)。

[0066] 本发明中，中心点快速搜索步骤如下：

[0067] (2.1)以指纹特征A的中心点为中心，选择半径Rmin到半径Rmax，统计其中所有的特征点信息集合：{AX[0]，AX[1]...AX[o2]}，共o2个特征点，如果指纹特征A有2个中心点，统计2个环形区域内所有的特征点；

[0068] (2.2)j＝0；

[0069] (2.3)如果j＜N，进入下一步骤(2.4)，否则进入步骤(2.7)；

[0070] (2.4)选取特征Bj，判断特征Bj是否有中心点，如果特征Bj没有中心点，则记录相似度得分Sj＝0，j＝j+1，进入步骤(2.3)；

[0071] (2.5)以特征Bj的中心点为中心，选择半径Rmin到半径Rmax，统计其中所有的特征点信息集合：{BX[0]，BX[1]...BX[p2j]}，共p2j个特征点，如果Bj有2个中心点，统计2个环形区域内所有的特征点；

[0072] (2.6)快速计算A、Bj选择的特征点集合之间的相似度，即比对o2个和p2j个特征点之间的相似度，记录到得分Sj中，j＝j+1，进入步骤(2.3)；

[0073] (2.7)寻找相似度得分Sj最大的Bj，记录为Bz；

[0074] (2.8)比对A、Bz，如比对成功，则返回搜索成功，搜索流程结束，否则中心点搜索失败，进入步骤(3)。

[0075] 名词解释：

[0076] 1、指纹细节点：指纹细节点指指纹脊线的端点和叉点，叉点如附图1所示，端点如附图2所示；

[0077] 2、指纹奇异点：指纹奇异点是指纹中非常重要的特征，指纹奇异点分2种：中心点，三角点；中心点如附图3所示，指纹最内层脊线的顶点，它描述了指纹的整体特征。三角点如附图4所示，即：有3组脊线通过的点。

[0078] 除上述实施例外，本发明还可以有其他实施方式。凡采用等同替换或等效变换形成的技术方案，均落在本发明要求的保护范围。