指纹自动识别系统多种算法互补能力研究
[姚越武1 
, 丁宏2 , 马继雄1 , 王刚3 , 罗昌英3 ]
, 丁宏引用本文
姚越武, 丁宏, 马继雄, 王刚, 罗昌英. 指纹自动识别系统多种算法互补能力研究[J].刑事技术, 2017,42(5):385-388
YAO Yuewu, DING Hong, MA Jixiong, WANG Gang, LUO Changying. Complementation between Various Algorithms of AFIS and the Practical Value[J]. Forensic Science and Technology,2017,42(5): 385-388
doi: 10.16467/j.1008-3650.2017.05.010
Permissions
YAO Yuewu, DING Hong, MA Jixiong, WANG Gang, LUO Changying. Complementation between Various Algorithms of AFIS and the Practical Value[J]. Forensic Science and Technology,2017,42(5): 385-388
doi: 10.16467/j.1008-3650.2017.05.010
Copyright©2017, 《刑事技术》编辑部
《刑事技术》编辑部
指纹自动识别系统多种算法互补能力研究
第一作者简介：姚越武（1962—）,男,江苏常州人,学士,高级工程师,研究方向为指纹检验。电子邮箱：zjhzyyw@sina.com
摘要
单一算法指纹自动识别系统在LT比对（即正查——现场比十指Latent to Ten-print）时均存在一定的漏比率（即错误拒绝率FRR）,不同算法指纹自动识别系统错误拒绝的样本并不完全重合,即不同识别算法之间存在互补性。本文通过在一套指纹自动识别系统中同时加载多套不同来源算法进行比对,获得各套算法单独比对、融合比对的结果,再通过对这些比对结果的分析、比较,验证了不同识别算法具有互补性,使用多套异构识别算法进行比对,能够有效降低错误拒绝率,提高识别系统的比对精度这一结论。
关键词:
指纹自动识别系统; 多算法; 融合; 精度提高
中图分类号:DF794.1
文献标志码:A
文章编号:1008-3650(2017)05-0385-04
Complementation between Various Algorithms of AFIS and the Practical Value
Abstract
AFIS (automatic fingerprint identification system) plays an important role for a case-concerned fingerprint to match against one of the recorded fingerprints in it. The match depends on AFIS-adopted algorithm to determine whether there is identity between the compared fingerprint and one of those stored. It has been found that FRR (false rejection rate) always exists when only single one algorithm was employed by the AFIS to make comparison from one case-extracted latent fingerprint to someone’s ten fingerprints (Latent to Ten-print, LT) that is kept in the AFIS. Another discovery also showed that the wrongly rejected samples are not completely identical in different AFIS because of the adoption of various algorithms in the involved AFIS, suggestive of the complementation between various algorithms. Such a complementation should be utilized to assure the accuracy and validity of a match (the case identification). Therefore, this study tries to integrate multiple algorithms of fingerprint’s match into one AFIS, performing the same LT search through both various single algorithm and combinations of these algorithms. Consequently, the FRR is effectively reduced, resulting in LT search having its accuracy improved.
Key words:
AFIS; latent search; multiple matching algorithm; fusion; accuracy improvement
目前国内刑侦指纹自动识别系统的数据库规模已经突破千万人级, 正在向5000万人乃至1亿人级别的库容迈进, 如浙江省厅指纹总库中的捺印指纹档案已达3700余万人份, 公安部正在筹建亿人级的全国指纹大库。随着指纹档案库容量越来越大, 指纹的比中概率会逐渐降低, 这必然导致案件指纹漏查的数量增大, 特别是一些大要案件指纹的漏查, 往往会造成不可挽回的经济损失或社会影响。然而, 目前国内外的指纹核心算法已经发展到一个相对稳定的瓶颈阶段, 在当前算法理论没有突破性进展的情况下, 任何一套单一算法要想提高哪怕是1 %的精度均已非常困难。同时, 在指纹识别实战应用中, 受数据噪音影响（例如, 指纹图像采集质量、现场指纹的残缺、模糊、变形）和识别算法普适性的限制, 基于单一算法的识别系统不能完全适应所有现场指纹比对的要求, 这一点在公安部《2013年上半年全国公安机关指纹协查工作情况通报》中也得到一定程度的印证, 该通报表明：各省应比中而未比中、但被其他省的异构系统比中的现场指纹共546枚, 这种现象出现在目前国内所有在用的7套国内外指纹自动识别系统中[1]。
笔者认为在一套指纹自动识别系统中集成多套识别算法, 利用算法之间的互补性来提高系统的整体比对精度, 是一种可行的技术方案。为了验证这个技术方案的可行性和实际效果, 我们开展了在一套指纹自动识别系统中加载3套不同来源算法的实验。限于篇幅, 本文仅对正查, 即LT比对[2]的结果进行讨论。
1 实验部分
1.1 实验系统环境
实验在浙江省公安厅PU-AFIS指纹自动识别系统中进行, 我们在一套指纹自动识别系统中加载了3套不同来源算法, 如图1所示：
 | 图1 测试实验的网络拓扑、识别算法部署示意图Fig.1 Schematic diagram of experimental design |
如图1, 实验系统采用3套来源不同的指纹识别算法, 分别记为算法1、2、3, 其中算法1、算法3是国内在用的单一算法指纹自动识别系统的算法, 算法2是引自参加过美国NIST测试获较好名次的一套算法。测试环境由两套比对系统组成：
比对系统一：由40个刀片组成, 在每一个刀片上加载了算法1、2、3, 能够同时实现以下比对方式：算法1单独比对; 算法2单独比对; 算法1+算法2串行比对（算法1做筛选比对、算法2在算法1的筛选结果基础上做排名比对）; 算法1+算法3串行比对（算法1做筛选比对、算法3在算法1的筛选结果基础上做排名比对）。
比对系统二：由二台机架式PC服务器组成, 在每台机架式PC服务器上运行算法3的独立比对系统。
实验系统中捺印指纹库数据量为552万人份标准格式数据[3], 实验开始前分别按照算法1~3的要求, 对数据格式进行批量转换。比对系统一和比对系统二的环境列表见表1。
 | 表1 测试实验环境描述表 Table 1 The experimental design and condition |
1.2 相关术语
算法1的比对结果, 记为“ 算法1” ;
算法2的比对结果, 记为“ 算法2” ;
算法3的比对结果, 记为“ 算法3” ;
算法1+2的比对结果, 记为“ 算法1+2” ;
算法1+3的比对结果, 记为“ 算法1+3” ;
算法1、算法1+2、算法1+3的比对结果融合（对三种比对结果重新排名）, 记为“ 结果融合” ;
上述6种算法排名结果的并集, 记录为“ 各算法并集” 。
1.3 实验样本及方法
1.3.1 实验样本
本次实验共选取样本1025对, 这些样本中包括：1996年以来浙江省指纹自动识别系统比中的500对样本及外省市其它指纹自动识别系统比中的525对样本。其中：来自本省内的样本数据, 抽取自浙江省厅指纹自动识别系统已比中数据, 按表2内的数量关系随机抽取。来自外省市的样本数据, 选自于收集到的2008年（含）前全国指纹协查比中的指纹数据, 约3万对数据, 随机抽取500对样本, 因部分案件指纹中有多枚现场指纹均有比中关系, 故最终的样本总数为525对。
| 表2 省内指纹样本数据分布表 Table 2 Fingerprint data chosen from AFIS of Zhejiang province |
1.3.2 实验方法
将上述1025对实验样本中的捺印指纹、现场指纹数据分别导入实验系统中, 然后按照测试方法发送相应的LT比对, 记录、统计各种算法的比对结果。由于数据格式标准化转换以及其他原因, 最终在所有比对方式中有1015个样本成功完成所有的比对, 为客观起见, 相关统计和分析以1015个样本为准。
2 结果与讨论
2.1 LT结果汇总
实验结果见表3及图2。
| 表3 各识别算法及识别算法组合的比对结果汇总表 Table 3 Summary of fingerprints matched/unmatched by single algorithm and/or algorithms combinations |
 | 图2 各算法在不同名次内比中数量情况趋势图Fig.2 The tendency of the quantity of fingerprints matched by single algorithm and/or algorithms combinations in 8 different rankings |
2、漏查：此处规定未出现在候选名单前200名中的样本, 即记为漏查。
2.2 结果讨论
2.2.1 精度讨论
对正查实验中所有样本、各种算法比对结果排名、排前率进行分析, 以比较各算法精度能力及互补性。从表3与图2可见：
1）在各个名次的比中数量中, 各种融合算法比中数量（精度）均优于任何一套参与融合的独立算法。
2）总体上, 3种算法融合（“ 结果融合” )的结果好于2种算法融合的结果（前5的“ 算法1+2” > “ 结果融合” ）。
3）“ 各算法并集” （所有算法结果的并集）好于任何一套融合算法及独立算法。
“ 各算法并集” 与各独立及融合算法精度比较均有大幅提升, 特别是与单一算法系统（“ 算法1” 及“ 算法3” ）比较, 第一名排前率分别提高34.58个百分点、23.35个百分点, 如此大幅提升, 这在当前技术背景条件下, 对任何一套独立算法来说均是难以想象, 不可企及的。
2.2.2 正查比对的互补性讨论
为了进一步验证各算法互补性, 我们对三种独立算法未比中的结果进行了分析。根据表3结果可知, 算法1前200名内漏比164个样本, 算法2在前200名内漏比91个样本, 算法3在前200名内漏比189个样本。将三个算法漏比的样本分别使用其余两种算法重新比对, 结果见表4~6。
| 表4 算法1未比中样本分析表 Table 4 Analysis of samples unmatched by algorithm 1 |
| 表5 算法2未比中样本分析表 Table 5 Analysis of samples unmatched by algorithm 2 |
| 表6 算法3未比中样本分析表 Table 6 Analysis of samples unmatched by algorithm 3 |
从表4~6可见, 每种算法遗漏的数据都有被其他算法比中的情况。
3 结论
1）现场指纹比对中, 任何算法和算法组合, 均不能保证所有样本都能被比中, 即指纹系统漏比是客观存在。在本研究中, 1015个有效样本中有25个样本是算法1、算法2、算法3及以上三种算法组合融合比对, 均未出现在前200名候选中, 说明这25个样本无法被算法1~3及其组合比中。推而广之, 如果更换算法1~3中任何一种或几种, 均会出现一定数量的样本无法被比中的情况。
2）多算法技术引入, 使系统总的查询准确率明显提高, 漏査率明显降低。
3）引入多算法技术, 系统整体排前率有大幅提高。
4）各算法之间的互补性较强, 没有一套算法可以完全包容其他算法的比对结果。
5）融合算法的精度均好于其中任何一套参与融合的独立算法的精度。但各融合算法与所有算法结果并集比较, 还有明显差距, 说明融合技术的精度能力还有很大的提升空间。
6）测试数据库的指纹细节特征, 是采用其中一套算法提取的, 如果分别在原图基础上提取各算法的细节特征, 有可能各算法间的精度差异会有所不同。
4 待深入的测试研究
由于时间和条件所限, 实验用的捺印指纹数据是采用其中一套算法提取的, 也没有收集到国内在用的其他更多算法比中的样本, 测试实验尚存在一些缺憾, 后期还应开展以下实验, 弥补上述缺憾：
1）针对在本研究中集成的三套算法, 开展由各自算法提取各自的细节特征, 研究细节特征提取算法对比对结果的影响;
2）收集国内在用系统的比中数据, 研究目前集成的三套算法对其他算法比中样本的互补性;
3）优化多算法比对结果的融合算法, 尽可能降低融合算法的结果与所有算法组合的并集的差异, 即提高多算法融合单一结果输出下的比对精度和排前率。
The authors have declared that no competing interests exist.
参考文献
| [1] |
|
| [2] |
|
| [3] |
|