一种多特征融合的海量指纹编码和比对方法
一种多特征融合的海量指纹编码和比对方法
【技术领域】
[0001] 本发明提供一种多特征融合的海量指纹编码、比对方法，属于生物特征识别领域， 具体地，设及指纹识别方法。
【背景技术】
[0002] 指纹自动识别技术相对于其他生物特征识别技术具有极好的准确性及较高的经 济实用性。指纹识别技术分为两个过程：（1)指纹注册过程。通过读取指纹图像，发现指纹图 像中的指纹区域，提取指纹区域中可W对指纹相互进行区分的特征。将运些特征数据保存 在数据库中，并作为运枚指纹的代表，从而完成指纹注册过程；（2)特征比对过程。在提取完 新采集的待比对指纹的特征后，对数据库中的指定注册指纹或者数据库中全部注册指纹进 行特征比对，确认新采集的指纹是否在数据库中的过程为特征比对过程。
[0003] 伴随着计算机技术和信息处理与识别技术的不断进步，指纹识别技术得到了迅猛 的发展，现已成为最成熟、最可接受的一种生物特征识别技术，是可W在公安、网络管理、银 行、社保、雇员证明、海关身份鉴定、电子口禁等许多领域广泛深入应用的技术，具有重要的 理论研究意义和市场应用价值。
[0004] 传统的指纹特征提取及比对方法主要是基于细节特征的，即提取细节点特征（指 纹中脊线的终结点或交叉点)代表指纹图像，通过提取运些特征来识别已注册的指纹图像。 对于海量指纹(如上亿甚至上十亿枚指纹），一方面在进行指纹特征提取时，仅仅利用传统 的细节点特征或者纹线特征等是不具备构造出具有准确区分海量指纹能力的指纹特征;另 一方面将待比对指纹与全部注册指纹进行逐一比对的思路因比对工作量巨大也不可取，它 将消耗W月为单位的比对时间。
【发明内容】
[0005] 本发明技术解决问题:克服现有技术的不足，提供一种多特征融合的海量指纹编 码和比对方法，不仅能够满足一般规模指纹比对需求，更重要的是可W满足海量指纹的快 速比对需求，从而可W满足当前及未来指纹识别市场的发展。
[0006] 本发明所述一种多特征融合的海量指纹编码和比对方法，如图1所示，包括W下步 骤：
[0007] 步骤SOI:输入海量注册指纹和一枚待识别指纹，给全部注册指纹标记唯一的ID识 别码。对待识别指纹及全部注册指纹分别构造特征矩阵及细节点矩阵；
[000引其中，所述构造特征矩阵及细节点矩阵包括:通过图像增强、二值化等数字图像处 理方法将原始指纹图像转变成为指纹脊线骨架图，在该图上标记指纹的全部细节特征点 (包括终结点及交叉点）。假设共计有N个细节点，各细节点的表示方法依据中国公安部颁发 的公共安全行业标准GA426-2008明确指纹细节点特征由Ξ项构成:x轴坐标，y轴坐标及细 节点方向与水平线的夹角。可W通过如下的步骤构成细节点与纹线融合的多特征计算结 构:令第i个细节点的位置及角度为αi = (Xi，yi，θi)，iE[l，N]，N为细节点的个数，顺着第i 个细节点追踪指纹脊线，如果能追溯到第j个细节点，其位置坐标及角度为aj = (xj，yj，9j)， jE[l，N]，用直线连接第i，j两点，记录两点之间的距离为Du。在该直线的中屯、做垂线，记录 垂线与i，j两点之间脊线的交点为k，其位置及角度为Qk=(祉，yk，0k)。该结构的示意图如图 2所示。记录k点到沿垂线方向至Iji，j两点之间直线所跨越的纹线数目为Wu，记录第i，j两点 的角度差为Cij = I目广目j I。由此构成1'^特化向重Vp = (ai,C[j,C[k,Wij,Dij, Cij ),pE[l,P],其 中P是N个细节点中，能组成特征向量的最大个数。纵向排列全部特征向量，由此构成了 P行、 12列的特征矩阵。对于全部N个细节点，αι = (Xi，yi，θ〇，i e [ 1，N]，纵向排列，构成N 行、3列的细节点矩阵iWl;。可W用的两个矩阵代表当前指纹的全部特征。
[0009] 步骤S02:构建指纹快速筛选树。筛选树的叶子节点登记具有相似特征评价指标的 注册指纹，形成同类注册指纹列表；
[0010] 其中，所述构造指纹比对快速筛选树包括:从快速筛选树的根节点开始，任意挑选 Wij、Dij、Ci己个指标中的一个，比如Wij作为第一层分支。令k点沿垂线方向至Ijij两点之间直 线所跨越的纹线数目可能出现的最大值为Wmax，则可W将筛选树第一层按照预设的纹线分 配区间Wavg平均分成化bl个独立分支，其牛
在第一层的每个分支下，可W构造 第二层分支。对第二层的每个分支，任意选择化两个指标中的一个，比如化^乍为第二层 分支。令i，j任两点之间直线距离的最大值为Dmax，则可W将第二层按照预设的直线距离分 配区间Davg平均分成Cab2个独立分支，其4
在第二层的每个分支下，可W构 造第Ξ层分支。第Ξ层选择Cu指标。由于角度差的最大值为180度，则可W将第Ξ层按照预 设的角度差区间Davg平均分成化b3个独立分支，其中
由此构造完成指纹快速 筛选树的全部分支（参见图3所示）。进一步开始逐一登记全部注册指纹:针对当前注册指 纹，取其特征矩阵逐次抽取一行特征向量Vp，选择其中的Wu、Du、Cu指标。从快速筛 选树的根节点开始，按照Wu、化层分支顺序，计算
确定当前注册指纹 应登记在第Indexi个分支下;从该分支的第二层开始，计算
'进一步确定当前 指纹应登记在第Index2个分支下;从该分支的下一层开始，计算
I进一步确定 当前指纹应登记在第Index3个分支下，在该分支下构造筛选树的叶子节点。在该叶子节点 登记当前注册指纹的I的只别码。抽取当前指纹的下一行特征向量Vp + l，重复上述工作直到全 部特征向量抽取完毕，开始转入下一枚注册指纹的登记工作。
[0011] 步骤S03:利用待比对指纹的特征矩阵在快速筛选树中检索到与待比对指纹具有 相似特征评价指标的注册指纹列表，对列表中各指纹ID识别码出现频次进行统计，将频次 最高的若干枚指纹取出形成注册指纹嫌疑队列；
[0012]其具体包括:若当前的第P个特征向量包含Wu、Du、Ci己个指标，针对快速筛选树， 采用公式
确定在筛选树的第一层检索进入第Indexi个分支，采用公式
确定第二层选择第Index2个分支，采用公式
确定第Ξ层检索 进入第Index3个分支。在第Ξ层的叶子节点中，提取出全部注册指纹I的只别码，将其加入指 纹相似队列，开始处理第P+1个特征向量。当全部特征向量检索到的指纹ID识别码列表都加 入指纹相似队列后，统计相似队列中指纹ID识别码出现的频数。按照指纹ID识别码出现的 频数从高到低排序，依经验，预先设定一个出现频数的阔值，最终将高于运个阔值的全部指 纹ID识别码作为指纹比对嫌疑队列，进而在步骤S04开展精细匹配。
[0013] 步骤S04:将待比对指纹的指纹细节点矩阵逐一地与嫌疑队列中的注册指纹进行 比对，最终将比对相似度最高的注册指纹作为所述方法的比对结果。
[0014] 具体而言:将待比对指纹的矩阵逐一地与嫌疑队列中全部注册指纹的特征矩 阵采用目前流行的基于细节点特征的指纹比对，得到一个相似度的数值。在逐一比对 结束后，在全部对结果中，挑选相似度得分最高的注册指纹与预设的分数阔值进行比较。如 果高于该阔值，则将该指纹作为待匹配指纹的比中结果返回。否则，则认为待比对指纹在本 次比对中没有比中。
[0015] 本发明具有如下有益的技术效果，
[0016] (1)本发明提出一种多特征融合的指纹编码、比对方法，用于在海量指纹中快速准 确的进行指纹比对。随着指纹应用的日益广泛，本发明的有益技术效果更加明显；
[0017] (2)本发明构造的指纹特征编码方式，有效克服了在海量指纹数据中，仅W细节点 或者纹线作为指纹特征导致指纹区分能力不足的困境；
[0018] (3)本发明构造的快速筛选树方案可W在海量指纹中极大的缩小指纹比对范围， 提高指纹比对效率。
【附图说明】
[0019] 图1本发明实施方法的流程图。
[0020] 图2本发明中细节点与纹线融合的多特征计算结构示意图；
[0021 ]图3本发明中指纹快速筛选树示意图。
【具体实施方式】
[0022] 实施例：
[0023] 如图1所示，该方法包括W下步骤：
[0024] 步骤SOI:输入海量注册指纹和一枚待识别指纹，给全部注册指纹标记唯一的ID识 别码。对待识别指纹及全部注册指纹分别构造特征矩阵及细节点矩阵；
[0025] 依次从待匹配指纹及全部注册指纹中选取一枚指纹作为当前指纹构造特征矩阵。 假定当前指纹有100个细节点，例如选取第1个细节点，其位置及角度为αι= (30,40,45)，顺I 着第1个细节点追踪指纹脊线，能追溯到第10个细节点，其位置及角度为αι〇= (200,50， 135)，则用直线连接第1、10两点，计算得到两点之间的直线距离为170。在该直线的中屯、做 垂线，记录垂线与1、1〇两点之间脊线的交点的位置及角度为化=(100,90,2)。记录该点到 沿垂线方向到第1、1〇两点之间直线所跨越的纹线数目为5,记录第1，10两点的角度差为90。 由此构成一个特征向量VI = (30，40，45，200，50，135，100，90，2，5，170，90)。假定针对所有 细节点，共找到了20个运样的特征向量，因此可W构成特征矩阵Miw;。此外，对于全部100 个细节点，构成100行，3列的细节点矩阵。至此用，Λ?京。X;的两个矩阵代表当前 指纹的全部特征。进一步可W开始构造下一枚指纹的特征矩阵。
[0026] 步骤S02:构建指纹快速筛选树。筛选树的叶子节点登记具有相似特征评价指标的 注册指纹，形成同类注册指纹列表；
[0027] 具体而言，构造快速筛选分支的过程如下:按照Wu构造第一层分支。设定跨越纹线 数的最大值为20,预设的纹线分配区间宽度 为4,则平均分巧
个独立分支。对 于第一层的每一个分支，选择化^乍为第二层分支。设定直线距离的最大值为400,预设的直 线距离分配区间宽度为20,则平均分成
个独立分支。对于第二层的每一 个分支，第Ξ层选择Cu指标。由于角度差的最大值为180度，则预设角度分配区间宽度为30， 则平均分巧
I个独立分支。
[002引将指纹登记到快速筛选树的过程如下：逐一登记全部注册指纹，针对当前第一枚 注册指纹，取其特征矩阵.必Ijm;:.，逐行抽取特征向量，比如抽取第一行特征向量VI中Wp，Dp，Cp Ξ个指标的值分别为5、170、90。从快速筛选树的根节点开始，计算
巧定落 在第2个分支内；从该分支的第二层开始，计算
，确定落在第9个分支内；从 该分支的第Ξ层开始，计I
I确定落在第3个分支内，由此抵达快速筛选树的 叶子节点。在该叶子节点记录当前注册指纹的ID识别码。抽取该指纹的第二行特征向量，重 复上述工作直到全部特征向量抽取完毕，开始转入下一枚注册指纹的登记工作直至全部注 册工作完成。
[0029] 步骤S03:利用待比对指纹的特征矩阵在快速筛选树中检索到与待比对指纹具有 相似特征评价指标的注册指纹列表，对列表中各指纹ID识别码出现频次进行统计，将频次 最高的若干枚指纹取出形成注册指纹嫌疑队列；
[0030] 取得待比对指纹的特征向量第1行，取出其包含Wi，Di，Ci^个指标的值为6、179， 93。针对快速筛选树，计I
确定第一层选择第2个分支，计I
确定第二层选择第9个分支，计算
确定第Ξ层选择第4个分支。在第Ξ层的 叶子节点中，取出全部指纹ID识别码列表（10号，19号，30号，40号），将其加入指纹相似队列 中，开始处理第2个特征向量。取得特征向量第2行，取出其包含化，D2，C2^个指标的指为19、 254, 126。针对快速筛选树，计算
角定第一层选择第5个分支，计算
确定第二层选择第13个分支，计算
i定第Ξ层选择第5 个分支。在第Ξ层的叶子节点中，取出全部指纹ID识别码列表（11号，19号，31号，40号），将 其加入指纹相似队列中，开始处理第3个特征向量。当全部特征向量检索到的指纹ID识别码 列表都放入指纹相似队列后，对相似队列中的指纹ID识别码出现频数统计。11号指纹共计 统计到30次，40号指纹共计统计到25次，19号指纹统计到21次，8号指纹统计到17次，依次类 推。设定频数的阔值为20次，则指纹比对嫌疑队列中存入11号、40号、19号Ξ枚指纹的ID识 别码。
[0031] 步骤S04:将待比对指纹的指纹细节点矩阵逐一地与嫌疑队列中的注册指纹进行 比对，最终将比对相似度最高的注册指纹作为所述方法的比对结果。
[0032] 利用待比对指纹的细节点矩阵依次和11号、40号、19号Ξ枚指纹的细节点矩阵进 行比对。其中40号指纹的比对相似度最高分值为0.99,比预设的阔值0.90高，最终认定40号 ID识别码的指纹作为待匹配指纹的比中结果。
[0033] 总之，本发明通过指纹特征编码及快速筛选树的方式在海量指纹中快速、准确的 完成比对任务。
[0034] 上面对本发明的较佳实施方式作了详细说明，但是本发明并不限于上述实施方 式，在本领域的普通技术人员所具备的知识范围内，还可W在不脱离本发明宗旨的前提下 做出各种变化。
【主权项】
1. 一种多特征融合的海量指纹特征编码和比对方法，其特征在于包括以下步骤： 步骤SOI:输入海量注册指纹和一枚待识别指纹，给全部注册指纹标记唯一的ID识别 码，对待识别指纹及全部注册指纹分别构造特征矩阵及细节点矩阵;所述构造的特征矩阵 及细节点矩阵过程包括： (1) 将原始指纹，即待识别指纹及全部注册指纹图像转变成为指纹脊线骨架图，在该指 纹脊线骨架图上标记该指纹的全部细节特征点，细节特征点包括终结点及交叉点；指纹细 节点特征由X轴坐标，y轴坐标、细节点方向与水平线的夹角三项构成； (2) 构造特征矩阵 令第i个细节点的位置及角度为Cti = (Xi^iJi)，ie[l，N]，N为细节点的个数，顺着第i 个细节点追踪指纹脊线，如果能追溯到第j个细节点，其位置坐标及角度为Α = (^，^，θ〇， je[l，N]，用直线连接第i J两点，两点之间的距离为在该直线的中心做垂线，记录垂线 与i，j两点之间指纹脊线的交点为k，该交点的位置及角度为ak= (Xk，yk，Qk)，k点到沿垂线 方向到i，j两点之间直线所跨越的指纹纹线数目为Wlj，第i，j两点的角度差为C lj= I Q1-Qj I， 由此构成一个特征向量vP = (Cti，a」，Ctk，Wij，Dij，C ij)，p e [ I，P]，其中P是N个细节点中能组成 特征向量的最大个数，纵向排列全部特征向量，构成P行、12列的特征矩阵.5 (3) 细节点矩阵为:对于全部N个细节点Cii= (XijiJi)，ie [I，N]，纵向排列，构成N行、3 列的细节点矩阵M^3; 步骤S02:构建指纹快速筛选树;在筛选树的叶子节点登记具有相似特征评价指标的注 册指纹，形成同类注册指纹列表； 步骤S03:利用待比对指纹的特征矩阵在快速筛选树中检索到与待比对指纹具有相似 特征评价指标的注册指纹列表，对列表中各指纹ID识别码出现频次进行统计，将频次最高 的若干枚指纹取出形成注册指纹嫌疑队列； 步骤S04:将待比对指纹的指纹细节点矩阵逐一地与嫌疑队列中的注册指纹进行比对， 最终将比对相似度最高的注册指纹作为所述方法的比对结果。2. 根据权利要求1所述的多特征融合的海量指纹编码和比对方法，其特征在于：步骤 S02中，所述构造指纹比对快速筛选树包括:从快速筛选树的根节点开始，任意挑选特征矩 阵中的特征评价指标W lj JljXlj三个指标中的一个开始，以^作为第一层分支，令k点到沿 垂线方向到i，j两点之间直线所跨越的纹线数目可能出现的最大值为W max，则将筛选树第一 层按照预设的纹线分配区间Wavg平均分成Cab1个独立分支，其中u在第一层的 每个分支下，构造第二层分支，对第二层的每个分支，任意选择Dij、Cij两个指标中的一个， 以Dlj作为第二层分支，令i J任两点之间直线距离的最大值为Dmax，则将第二层按照预设的 直线距离分配区间Davg平均分成Cab2个独立分支，其中在第二层的每个分支 下，构造第三层分支;第三层选择Clj指标，由于角度差的最大值为180度，则将第三层按照预 设的角度差区间Davg平均分成Cab3个独立分支，其中由此构造完成指纹快速 筛选树的全部分支，形成指纹比对快速筛选树。3. 根据权利要求1所述的多特征融合的海量指纹编码和比对方法，其特征在于：步骤 S02中在筛选树的叶子节点登记具有相似特征评价指标的注册指纹，形成同类注册指纹列 表过程为:针对当前注册指纹，取其特征矩阵M^12，逐次抽取一行特征向量Vp，选择其中的 Wij 指标，从快速筛选树的根节点开始，按照Wij 三层分支顺序，计算确定当前注册指纹应登记在第Indexi个分支下；从该分支的第二层开始， 计算进一步确定当前指纹应登记在第Index2个分支下;从该分支的下一层 开始，计算_进一步确定当前指纹应登记在第Index3个分支下，在该分支下构 造筛选树的叶子节点，在该叶子节点登记当前注册指纹的ID识别码，抽取当前指纹的下一 行特征向量Vp+l，重复上述工作直到全部特征向量抽取完毕，开始转入下一枚注册指纹的登 记工作，直至形成同类注册指纹列表。4. 根据权利要求1所述的多特征融合的海量指纹编码和比对方法，其特征在于：步骤 S03具体实现过程为:若当前的第p个特征向量包含W ij、Dij、Cij三个指标，针对快速筛选树， 采用公式：确定在筛选树的第一层检索进入第Index 1个分支，采用公式确定第二层选择第Index2个分支，采用公式.确定第三层检索 进入第Index3个分支，在第三层的叶子节点中，提取出全部注册指纹ID识别码，将其加入指 纹相似队列，开始处理第P+1个特征向量，当全部特征向量检索到的指纹ID识别码列表都加 入指纹相似队列后，统计相似队列中指纹ID识别码出现的频数;按照指纹ID识别码出现的 频数从高到低排序，依经验，预先设定一个出现频数的阈值，最终将高于这个阈值的全部指 纹ID识别码作为指纹比对嫌疑队列。5. 根据权利要求1所述的多特征融合的海量指纹编码和比对方法，其特征在于：步骤 S04具体实现过程为:将待比对指纹的指纹细节点特征矩阵Mi 3逐一地与嫌疑队列中全部 注册指纹的特征矩阵采用基于细节点特征的指纹比对，得到一个相似度的数值，在逐 一比对结束后，在全部对结果中，挑选相似度得分最高的注册指纹与预设的分数阈值进行 比较;如果高于该阈值，则将该指纹作为待匹配指纹的比中结果返回；否则，则认为待比对 指纹在本次比对中没有比中。
【专利摘要】本发明涉及一种多特征融合的海量指纹特征编码和比对方法，包括：输入海量注册指纹和一枚待识别指纹，给全部注册指纹标记唯一的ID识别码。对待识别指纹及全部注册指纹分别构造特征矩阵及细节点矩阵；构建指纹快速筛选树。在筛选树的叶子节点登记具有相似特征评价指标的注册指纹，形成同类注册指纹列表；利用待比对指纹的特征矩阵在快速筛选树中检索到与待比对指纹具有相似特征评价指标的注册指纹列表，对列表中各指纹ID识别码出现频次进行统计，将频次最高的若干枚指纹取出形成注册指纹嫌疑队列；将待比对指纹的指纹细节点矩阵逐一地与嫌疑队列中注册指纹的细节点矩阵进行比对，最终将比对相似度最高的注册指纹作为所述方法的比对结果。
【IPC分类】G06K9/00
【公开号】CN105488473
【申请号】CN201510862330
【发明人】张威, 赵彤
【申请人】北京东方金指科技有限公司
【公开日】2016年4月13日
【申请日】2015年12月1日
【技术领域】
[0001] 本发明提供一种多特征融合的海量指纹编码、比对方法，属于生物特征识别领域， 具体地，设及指纹识别方法。
【背景技术】
[0002] 指纹自动识别技术相对于其他生物特征识别技术具有极好的准确性及较高的经 济实用性。指纹识别技术分为两个过程：（1)指纹注册过程。通过读取指纹图像，发现指纹图 像中的指纹区域，提取指纹区域中可W对指纹相互进行区分的特征。将运些特征数据保存 在数据库中，并作为运枚指纹的代表，从而完成指纹注册过程；（2)特征比对过程。在提取完 新采集的待比对指纹的特征后，对数据库中的指定注册指纹或者数据库中全部注册指纹进 行特征比对，确认新采集的指纹是否在数据库中的过程为特征比对过程。
[0003] 伴随着计算机技术和信息处理与识别技术的不断进步，指纹识别技术得到了迅猛 的发展，现已成为最成熟、最可接受的一种生物特征识别技术，是可W在公安、网络管理、银 行、社保、雇员证明、海关身份鉴定、电子口禁等许多领域广泛深入应用的技术，具有重要的 理论研究意义和市场应用价值。
[0004] 传统的指纹特征提取及比对方法主要是基于细节特征的，即提取细节点特征（指 纹中脊线的终结点或交叉点)代表指纹图像，通过提取运些特征来识别已注册的指纹图像。 对于海量指纹(如上亿甚至上十亿枚指纹），一方面在进行指纹特征提取时，仅仅利用传统 的细节点特征或者纹线特征等是不具备构造出具有准确区分海量指纹能力的指纹特征;另 一方面将待比对指纹与全部注册指纹进行逐一比对的思路因比对工作量巨大也不可取，它 将消耗W月为单位的比对时间。
【发明内容】
[0005] 本发明技术解决问题:克服现有技术的不足，提供一种多特征融合的海量指纹编 码和比对方法，不仅能够满足一般规模指纹比对需求，更重要的是可W满足海量指纹的快 速比对需求，从而可W满足当前及未来指纹识别市场的发展。
[0006] 本发明所述一种多特征融合的海量指纹编码和比对方法，如图1所示，包括W下步 骤：
[0007] 步骤SOI:输入海量注册指纹和一枚待识别指纹，给全部注册指纹标记唯一的ID识 别码。对待识别指纹及全部注册指纹分别构造特征矩阵及细节点矩阵；
[000引其中，所述构造特征矩阵及细节点矩阵包括:通过图像增强、二值化等数字图像处 理方法将原始指纹图像转变成为指纹脊线骨架图，在该图上标记指纹的全部细节特征点 (包括终结点及交叉点）。假设共计有N个细节点，各细节点的表示方法依据中国公安部颁发 的公共安全行业标准GA426-2008明确指纹细节点特征由Ξ项构成:x轴坐标，y轴坐标及细 节点方向与水平线的夹角。可W通过如下的步骤构成细节点与纹线融合的多特征计算结 构:令第i个细节点的位置及角度为αi = (Xi，yi，θi)，iE[l，N]，N为细节点的个数，顺着第i 个细节点追踪指纹脊线，如果能追溯到第j个细节点，其位置坐标及角度为aj = (xj，yj，9j)， jE[l，N]，用直线连接第i，j两点，记录两点之间的距离为Du。在该直线的中屯、做垂线，记录 垂线与i，j两点之间脊线的交点为k，其位置及角度为Qk=(祉，yk，0k)。该结构的示意图如图 2所示。记录k点到沿垂线方向至Iji，j两点之间直线所跨越的纹线数目为Wu，记录第i，j两点 的角度差为Cij = I目广目j I。由此构成1'^特化向重Vp = (ai,C[j,C[k,Wij,Dij, Cij ),pE[l,P],其 中P是N个细节点中，能组成特征向量的最大个数。纵向排列全部特征向量，由此构成了 P行、 12列的特征矩阵。对于全部N个细节点，αι = (Xi，yi，θ〇，i e [ 1，N]，纵向排列，构成N 行、3列的细节点矩阵iWl;。可W用的两个矩阵代表当前指纹的全部特征。
[0009] 步骤S02:构建指纹快速筛选树。筛选树的叶子节点登记具有相似特征评价指标的 注册指纹，形成同类注册指纹列表；
[0010] 其中，所述构造指纹比对快速筛选树包括:从快速筛选树的根节点开始，任意挑选 Wij、Dij、Ci己个指标中的一个，比如Wij作为第一层分支。令k点沿垂线方向至Ijij两点之间直 线所跨越的纹线数目可能出现的最大值为Wmax，则可W将筛选树第一层按照预设的纹线分 配区间Wavg平均分成化bl个独立分支，其牛
在第一层的每个分支下，可W构造 第二层分支。对第二层的每个分支，任意选择化两个指标中的一个，比如化^乍为第二层 分支。令i，j任两点之间直线距离的最大值为Dmax，则可W将第二层按照预设的直线距离分 配区间Davg平均分成Cab2个独立分支，其4
在第二层的每个分支下，可W构 造第Ξ层分支。第Ξ层选择Cu指标。由于角度差的最大值为180度，则可W将第Ξ层按照预 设的角度差区间Davg平均分成化b3个独立分支，其中
由此构造完成指纹快速 筛选树的全部分支（参见图3所示）。进一步开始逐一登记全部注册指纹:针对当前注册指 纹，取其特征矩阵逐次抽取一行特征向量Vp，选择其中的Wu、Du、Cu指标。从快速筛 选树的根节点开始，按照Wu、化层分支顺序，计算
确定当前注册指纹 应登记在第Indexi个分支下;从该分支的第二层开始，计算
'进一步确定当前 指纹应登记在第Index2个分支下;从该分支的下一层开始，计算
I进一步确定 当前指纹应登记在第Index3个分支下，在该分支下构造筛选树的叶子节点。在该叶子节点 登记当前注册指纹的I的只别码。抽取当前指纹的下一行特征向量Vp + l，重复上述工作直到全 部特征向量抽取完毕，开始转入下一枚注册指纹的登记工作。
[0011] 步骤S03:利用待比对指纹的特征矩阵在快速筛选树中检索到与待比对指纹具有 相似特征评价指标的注册指纹列表，对列表中各指纹ID识别码出现频次进行统计，将频次 最高的若干枚指纹取出形成注册指纹嫌疑队列；
[0012]其具体包括:若当前的第P个特征向量包含Wu、Du、Ci己个指标，针对快速筛选树， 采用公式
确定在筛选树的第一层检索进入第Indexi个分支，采用公式
确定第二层选择第Index2个分支，采用公式
确定第Ξ层检索 进入第Index3个分支。在第Ξ层的叶子节点中，提取出全部注册指纹I的只别码，将其加入指 纹相似队列，开始处理第P+1个特征向量。当全部特征向量检索到的指纹ID识别码列表都加 入指纹相似队列后，统计相似队列中指纹ID识别码出现的频数。按照指纹ID识别码出现的 频数从高到低排序，依经验，预先设定一个出现频数的阔值，最终将高于运个阔值的全部指 纹ID识别码作为指纹比对嫌疑队列，进而在步骤S04开展精细匹配。
[0013] 步骤S04:将待比对指纹的指纹细节点矩阵逐一地与嫌疑队列中的注册指纹进行 比对，最终将比对相似度最高的注册指纹作为所述方法的比对结果。
[0014] 具体而言:将待比对指纹的矩阵逐一地与嫌疑队列中全部注册指纹的特征矩 阵采用目前流行的基于细节点特征的指纹比对，得到一个相似度的数值。在逐一比对 结束后，在全部对结果中，挑选相似度得分最高的注册指纹与预设的分数阔值进行比较。如 果高于该阔值，则将该指纹作为待匹配指纹的比中结果返回。否则，则认为待比对指纹在本 次比对中没有比中。
[0015] 本发明具有如下有益的技术效果，
[0016] (1)本发明提出一种多特征融合的指纹编码、比对方法，用于在海量指纹中快速准 确的进行指纹比对。随着指纹应用的日益广泛，本发明的有益技术效果更加明显；
[0017] (2)本发明构造的指纹特征编码方式，有效克服了在海量指纹数据中，仅W细节点 或者纹线作为指纹特征导致指纹区分能力不足的困境；
[0018] (3)本发明构造的快速筛选树方案可W在海量指纹中极大的缩小指纹比对范围， 提高指纹比对效率。
【附图说明】
[0019] 图1本发明实施方法的流程图。
[0020] 图2本发明中细节点与纹线融合的多特征计算结构示意图；
[0021 ]图3本发明中指纹快速筛选树示意图。
【具体实施方式】
[0022] 实施例：
[0023] 如图1所示，该方法包括W下步骤：
[0024] 步骤SOI:输入海量注册指纹和一枚待识别指纹，给全部注册指纹标记唯一的ID识 别码。对待识别指纹及全部注册指纹分别构造特征矩阵及细节点矩阵；
[0025] 依次从待匹配指纹及全部注册指纹中选取一枚指纹作为当前指纹构造特征矩阵。 假定当前指纹有100个细节点，例如选取第1个细节点，其位置及角度为αι= (30,40,45)，顺I 着第1个细节点追踪指纹脊线，能追溯到第10个细节点，其位置及角度为αι〇= (200,50， 135)，则用直线连接第1、10两点，计算得到两点之间的直线距离为170。在该直线的中屯、做 垂线，记录垂线与1、1〇两点之间脊线的交点的位置及角度为化=(100,90,2)。记录该点到 沿垂线方向到第1、1〇两点之间直线所跨越的纹线数目为5,记录第1，10两点的角度差为90。 由此构成一个特征向量VI = (30，40，45，200，50，135，100，90，2，5，170，90)。假定针对所有 细节点，共找到了20个运样的特征向量，因此可W构成特征矩阵Miw;。此外，对于全部100 个细节点，构成100行，3列的细节点矩阵。至此用，Λ?京。X;的两个矩阵代表当前 指纹的全部特征。进一步可W开始构造下一枚指纹的特征矩阵。
[0026] 步骤S02:构建指纹快速筛选树。筛选树的叶子节点登记具有相似特征评价指标的 注册指纹，形成同类注册指纹列表；
[0027] 具体而言，构造快速筛选分支的过程如下:按照Wu构造第一层分支。设定跨越纹线 数的最大值为20,预设的纹线分配区间宽度 为4,则平均分巧
个独立分支。对 于第一层的每一个分支，选择化^乍为第二层分支。设定直线距离的最大值为400,预设的直 线距离分配区间宽度为20,则平均分成
个独立分支。对于第二层的每一 个分支，第Ξ层选择Cu指标。由于角度差的最大值为180度，则预设角度分配区间宽度为30， 则平均分巧
I个独立分支。
[002引将指纹登记到快速筛选树的过程如下：逐一登记全部注册指纹，针对当前第一枚 注册指纹，取其特征矩阵.必Ijm;:.，逐行抽取特征向量，比如抽取第一行特征向量VI中Wp，Dp，Cp Ξ个指标的值分别为5、170、90。从快速筛选树的根节点开始，计算
巧定落 在第2个分支内；从该分支的第二层开始，计算
，确定落在第9个分支内；从 该分支的第Ξ层开始，计I
I确定落在第3个分支内，由此抵达快速筛选树的 叶子节点。在该叶子节点记录当前注册指纹的ID识别码。抽取该指纹的第二行特征向量，重 复上述工作直到全部特征向量抽取完毕，开始转入下一枚注册指纹的登记工作直至全部注 册工作完成。
[0029] 步骤S03:利用待比对指纹的特征矩阵在快速筛选树中检索到与待比对指纹具有 相似特征评价指标的注册指纹列表，对列表中各指纹ID识别码出现频次进行统计，将频次 最高的若干枚指纹取出形成注册指纹嫌疑队列；
[0030] 取得待比对指纹的特征向量第1行，取出其包含Wi，Di，Ci^个指标的值为6、179， 93。针对快速筛选树，计I
确定第一层选择第2个分支，计I
确定第二层选择第9个分支，计算
确定第Ξ层选择第4个分支。在第Ξ层的 叶子节点中，取出全部指纹ID识别码列表（10号，19号，30号，40号），将其加入指纹相似队列 中，开始处理第2个特征向量。取得特征向量第2行，取出其包含化，D2，C2^个指标的指为19、 254, 126。针对快速筛选树，计算
角定第一层选择第5个分支，计算
确定第二层选择第13个分支，计算
i定第Ξ层选择第5 个分支。在第Ξ层的叶子节点中，取出全部指纹ID识别码列表（11号，19号，31号，40号），将 其加入指纹相似队列中，开始处理第3个特征向量。当全部特征向量检索到的指纹ID识别码 列表都放入指纹相似队列后，对相似队列中的指纹ID识别码出现频数统计。11号指纹共计 统计到30次，40号指纹共计统计到25次，19号指纹统计到21次，8号指纹统计到17次，依次类 推。设定频数的阔值为20次，则指纹比对嫌疑队列中存入11号、40号、19号Ξ枚指纹的ID识 别码。
[0031] 步骤S04:将待比对指纹的指纹细节点矩阵逐一地与嫌疑队列中的注册指纹进行 比对，最终将比对相似度最高的注册指纹作为所述方法的比对结果。
[0032] 利用待比对指纹的细节点矩阵依次和11号、40号、19号Ξ枚指纹的细节点矩阵进 行比对。其中40号指纹的比对相似度最高分值为0.99,比预设的阔值0.90高，最终认定40号 ID识别码的指纹作为待匹配指纹的比中结果。
[0033] 总之，本发明通过指纹特征编码及快速筛选树的方式在海量指纹中快速、准确的 完成比对任务。
[0034] 上面对本发明的较佳实施方式作了详细说明，但是本发明并不限于上述实施方 式，在本领域的普通技术人员所具备的知识范围内，还可W在不脱离本发明宗旨的前提下 做出各种变化。
【主权项】
1. 一种多特征融合的海量指纹特征编码和比对方法，其特征在于包括以下步骤： 步骤SOI:输入海量注册指纹和一枚待识别指纹，给全部注册指纹标记唯一的ID识别 码，对待识别指纹及全部注册指纹分别构造特征矩阵及细节点矩阵;所述构造的特征矩阵 及细节点矩阵过程包括： (1) 将原始指纹，即待识别指纹及全部注册指纹图像转变成为指纹脊线骨架图，在该指 纹脊线骨架图上标记该指纹的全部细节特征点，细节特征点包括终结点及交叉点；指纹细 节点特征由X轴坐标，y轴坐标、细节点方向与水平线的夹角三项构成； (2) 构造特征矩阵 令第i个细节点的位置及角度为Cti = (Xi^iJi)，ie[l，N]，N为细节点的个数，顺着第i 个细节点追踪指纹脊线，如果能追溯到第j个细节点，其位置坐标及角度为Α = (^，^，θ〇， je[l，N]，用直线连接第i J两点，两点之间的距离为在该直线的中心做垂线，记录垂线 与i，j两点之间指纹脊线的交点为k，该交点的位置及角度为ak= (Xk，yk，Qk)，k点到沿垂线 方向到i，j两点之间直线所跨越的指纹纹线数目为Wlj，第i，j两点的角度差为C lj= I Q1-Qj I， 由此构成一个特征向量vP = (Cti，a」，Ctk，Wij，Dij，C ij)，p e [ I，P]，其中P是N个细节点中能组成 特征向量的最大个数，纵向排列全部特征向量，构成P行、12列的特征矩阵.5 (3) 细节点矩阵为:对于全部N个细节点Cii= (XijiJi)，ie [I，N]，纵向排列，构成N行、3 列的细节点矩阵M^3; 步骤S02:构建指纹快速筛选树;在筛选树的叶子节点登记具有相似特征评价指标的注 册指纹，形成同类注册指纹列表； 步骤S03:利用待比对指纹的特征矩阵在快速筛选树中检索到与待比对指纹具有相似 特征评价指标的注册指纹列表，对列表中各指纹ID识别码出现频次进行统计，将频次最高 的若干枚指纹取出形成注册指纹嫌疑队列； 步骤S04:将待比对指纹的指纹细节点矩阵逐一地与嫌疑队列中的注册指纹进行比对， 最终将比对相似度最高的注册指纹作为所述方法的比对结果。2. 根据权利要求1所述的多特征融合的海量指纹编码和比对方法，其特征在于：步骤 S02中，所述构造指纹比对快速筛选树包括:从快速筛选树的根节点开始，任意挑选特征矩 阵中的特征评价指标W lj JljXlj三个指标中的一个开始，以^作为第一层分支，令k点到沿 垂线方向到i，j两点之间直线所跨越的纹线数目可能出现的最大值为W max，则将筛选树第一 层按照预设的纹线分配区间Wavg平均分成Cab1个独立分支，其中u在第一层的 每个分支下，构造第二层分支，对第二层的每个分支，任意选择Dij、Cij两个指标中的一个， 以Dlj作为第二层分支，令i J任两点之间直线距离的最大值为Dmax，则将第二层按照预设的 直线距离分配区间Davg平均分成Cab2个独立分支，其中在第二层的每个分支 下，构造第三层分支;第三层选择Clj指标，由于角度差的最大值为180度，则将第三层按照预 设的角度差区间Davg平均分成Cab3个独立分支，其中由此构造完成指纹快速 筛选树的全部分支，形成指纹比对快速筛选树。3. 根据权利要求1所述的多特征融合的海量指纹编码和比对方法，其特征在于：步骤 S02中在筛选树的叶子节点登记具有相似特征评价指标的注册指纹，形成同类注册指纹列 表过程为:针对当前注册指纹，取其特征矩阵M^12，逐次抽取一行特征向量Vp，选择其中的 Wij 指标，从快速筛选树的根节点开始，按照Wij 三层分支顺序，计算确定当前注册指纹应登记在第Indexi个分支下；从该分支的第二层开始， 计算进一步确定当前指纹应登记在第Index2个分支下;从该分支的下一层 开始，计算_进一步确定当前指纹应登记在第Index3个分支下，在该分支下构 造筛选树的叶子节点，在该叶子节点登记当前注册指纹的ID识别码，抽取当前指纹的下一 行特征向量Vp+l，重复上述工作直到全部特征向量抽取完毕，开始转入下一枚注册指纹的登 记工作，直至形成同类注册指纹列表。4. 根据权利要求1所述的多特征融合的海量指纹编码和比对方法，其特征在于：步骤 S03具体实现过程为:若当前的第p个特征向量包含W ij、Dij、Cij三个指标，针对快速筛选树， 采用公式：确定在筛选树的第一层检索进入第Index 1个分支，采用公式确定第二层选择第Index2个分支，采用公式.确定第三层检索 进入第Index3个分支，在第三层的叶子节点中，提取出全部注册指纹ID识别码，将其加入指 纹相似队列，开始处理第P+1个特征向量，当全部特征向量检索到的指纹ID识别码列表都加 入指纹相似队列后，统计相似队列中指纹ID识别码出现的频数;按照指纹ID识别码出现的 频数从高到低排序，依经验，预先设定一个出现频数的阈值，最终将高于这个阈值的全部指 纹ID识别码作为指纹比对嫌疑队列。5. 根据权利要求1所述的多特征融合的海量指纹编码和比对方法，其特征在于：步骤 S04具体实现过程为:将待比对指纹的指纹细节点特征矩阵Mi 3逐一地与嫌疑队列中全部 注册指纹的特征矩阵采用基于细节点特征的指纹比对，得到一个相似度的数值，在逐 一比对结束后，在全部对结果中，挑选相似度得分最高的注册指纹与预设的分数阈值进行 比较;如果高于该阈值，则将该指纹作为待匹配指纹的比中结果返回；否则，则认为待比对 指纹在本次比对中没有比中。
【专利摘要】本发明涉及一种多特征融合的海量指纹特征编码和比对方法，包括：输入海量注册指纹和一枚待识别指纹，给全部注册指纹标记唯一的ID识别码。对待识别指纹及全部注册指纹分别构造特征矩阵及细节点矩阵；构建指纹快速筛选树。在筛选树的叶子节点登记具有相似特征评价指标的注册指纹，形成同类注册指纹列表；利用待比对指纹的特征矩阵在快速筛选树中检索到与待比对指纹具有相似特征评价指标的注册指纹列表，对列表中各指纹ID识别码出现频次进行统计，将频次最高的若干枚指纹取出形成注册指纹嫌疑队列；将待比对指纹的指纹细节点矩阵逐一地与嫌疑队列中注册指纹的细节点矩阵进行比对，最终将比对相似度最高的注册指纹作为所述方法的比对结果。
【IPC分类】G06K9/00
【公开号】CN105488473
【申请号】CN201510862330
【发明人】张威, 赵彤
【申请人】北京东方金指科技有限公司
【公开日】2016年4月13日
【申请日】2015年12月1日
最新回复(0)