引用本文
王璐, 吴春生, 张宇. 基于内存比对的CAFIS系统指纹比对方法改进研究[J]. 刑事技术,2014,39(5): 14-17
WANG Lu, WU Chun-sheng, ZHANG Yu. Improvement of fingerprint matching method for CAFIS system based on memory matching[J]. Forensic Science and Technology,2014,39(5): 14-17  
Permissions
Copyright©2014, 《刑事技术》编辑部
《刑事技术》编辑部
基于内存比对的CAFIS系统指纹比对方法改进研究
王璐, 吴春生, 张宇
北京市公安局刑侦总队,100054

作者简介:王 璐(1987—),女,内蒙古凉城县人,助理工程师,研究生,从事指纹鉴定工作、指纹系统算法研究。Tel:15210716283; E-mail:wangzemo@gmail.com

基金: 北京市科技计划(No.Z121100000312099)
摘要

目的 研究改进现有指纹自动识别系统的比对速度。方法 将大量的比对数据提前加载到内存中,结合多线程并行计算,达到一次加载多次使用的目的。结果 多组测试数据证明内存比对方式可以有效减少访存时间,提高了整体比对速度。结论 指纹系统的内存比对方式是快速可行的比对方法。

关键词: 内存计算; 指纹比对速度; GPU计算
中图分类号:DF794.1 文献标志码:A 文章编号:1008-3650(2014)05-0014-04
Improvement of fingerprint matching method for CAFIS system based on memory matching
WANG Lu, WU Chun-sheng, ZHANG Yu
Beijing Public Security Bureau, Beijing 100054, China
Abstract

Objective To explore a method for improving the matching speed of CAFIS (China Automated Fingerprint Identification System). Methods Match the preloading data in memory by multi thread parallel computing method and return the result to user interface. Results According to many experiment results, with this method, the memory access time was reduced and the matching speed can be improved. Conclusions Memory matching is an effective way for improvement of CAFIS system.

Keyword: memory algorithm; fingerprint technology; GPU

指纹作为物证之首, 其特征的唯一性和不变性已经经过了历史的检验并得到公认[1]。长期以来指纹鉴定都是确定犯罪嫌疑人的可靠手段[2], 指纹自动识别系统的广泛应用为公安机关快速准确锁定犯罪嫌疑人提供了保障。从20世纪60年代, 一些国家如美国、英国、法国等开始了对指纹自动识别系统(Automated Fingerprint Identification System, AFIS)的研制。随着应用的深入, 指纹信息库的容量也不断攀升。例如, 美国联邦调查局(FBI)从1999年7月开始建立了综合指纹自动识别系统(IAFIS), 2006年库容量超过了4700万人[3]。北京市公安局自1990年开始应用指纹自动识别系统, 截至到2014年1月底, 指纹系统约存有本地十指数据数百万人, 全国协作共享十指指纹数据千余万人。指纹信息存储量的大幅攀升, 给指纹的比对查询和管理带来了新挑战。2010年北京市公安局通过国家课题“ 千万人级指纹自动识别和全国异构系统查询关键技术研究” , 研制成功基于CPU和GPU相结合的指纹快速比对方法, 其中基于图形处理器(Graphics Processing Units, GPU)的通用计算在高性能计算领域中是一个新的发展趋势[4]。利用GPU比对单元可以将原有的比对速度从3000枚/秒提升到了40万枚/秒, 比对效率大大提高。虽然比对速度大幅提升, 但由于设备不足等客观条件的制约, 仍然不能及时地满足快速增长的实战比对需求。

普通硬盘I/O速度大约为100MB/秒。1枚指纹特征数据大约为1kB, 40万枚指纹特征数据大约占400MB, 即读取40万枚数据需要4秒的时间。一个CPU比对单元每秒可以比对3000枚指纹数据[5], 比对40万枚指纹需要大约133秒, I/O时间占整体比对时间的比例为4/(4+133)=2.9%, 以CPU为主的比对单元由于计算速度慢, I/O瓶颈问题不明显。千万人级指纹自动识别和全国异构系统查询关键技术研究完成后, 使用了GPU比对单元, 一个GPU单元比对40万枚指纹只需一秒钟, 读取仍需要4秒, 而I/O时间占整体比对时间的比例为4/(4+1)=80%。可以明显看出, 制约指纹比对速度的瓶颈不再是计算速度而是I/O读写速度。在单机多线程的GPU比对应用中, I/O瓶颈问题更为突出。因此, 指纹的比对速度仍是一个非常关键的现实问题。在现有条件下, 如何进一步提高比对速度是一项重要的研究内容。

1 实验原理

内存比对方式是将大量的比对数据提前加载到内存中, 结合多线程并行计算, 达到一次加载多次使用的目的, 可以有效减少访存时间。同时, 随着计算机硬件设备的发展, 以及内存价格的下降, 服务器系统内存容量也越来越大。因此, 采用内存计算的方式, 是进一步提高指纹系统整体比对效率的有效可行的方法。

从计算存储技术的角度看, 由于服务器在处理数据时, CPU首先会从其内存中找数据, 内存里没有, 再从硬盘上读取。在传统比对计算中, 磁盘访问时间是一个主要的瓶颈。研究发现, 如果让比对工作在读写速度快很多倍的内存中进行, 而不用访问物理磁盘, 将会大大提升处理性能。所谓“ 内存计算” , 实质上就是CPU直接从内存而不是硬盘上读取数据, 进行计算、分析, 是对传统数据处理方式的一种加速。将指纹的比对计算工作放在内存中进行, 结合多进程的并行计算可以减少访存时间, 有效的提高了指纹比对的速度, 进而更好的发挥指纹工作在主动打击犯罪过程中的特殊作用。

2 材料和方法
2.1 样本数据制作

放入内存中的样本数据要保证可以供多个进程并行使用, 所以要确保内存中的数据可以共享。在本程序通过进程间共享内存映象文件来达到内存共享的目的。要把样本数据以文件的形式映像到内存, 首先必须调用CreateFileMapping()函数, 它的第一个参数是由CreateFile()函数打开并返回的文件句柄, 其他参数用来指定内存块的安全性访问权限及容量大小, 其中最后一个参数为内存映像对象指定名字, 通过调用CreateFileMapping函数和OpenFileMapping函数, 其他进程可用这个名字来访问相同的文件映像。

当内存映像对象由CreateFileMapping()创建成功后, 可以调用MapViewOfFile函数把文件映像到进程地址空间上, 这个函数需要用一个由CreateFileMapping()函数返回的句柄, 并允许指定访问模式和映像的字节数, 以及文件映像对象中的偏移量。当用完映像文件后, 可以通过调用UnmapViewOfFile函数, 释放映像内存并把一些映像数据写入文件(除非它是交换文件), 如果想立即把数据写回磁盘文件, 就需要调用FlushViewOfFile()函数把映像内存写入文件。

2.2 实验设备

CPU单元测试机器:使用Intel酷睿i5双核处理器, 2.67GHz主频, 内存4G。经对测试计算机的硬盘I/O进行测试:读:100MB/秒, 写:100MB/秒。

GPU测试机器一:GeForceGTX580GPU, 该设备为Fermi架构, 具有1.5GB显存、16个SM(Stream Multiprocessor)、512个SP(Stream Processor)。硬盘读写速度100MB/秒。

GPU测试机器二:GeForceGTX580GPU, 该设备为Fermi架构, 具有1.5GB显存、16个SM(Stream Multiprocessor)、512个SP(Stream Processor)。硬盘读写速度200MB/秒。

2.3 方 法

指纹内存计算程序主要由三部分功能组成, 首先是将样本数据提前加载到内存里, 其次在内存里将检材数据和样本数据进行比对计算, 最后对计算结果进行处理并返回。

程序的第二个主要部分是在共享内存中进行比对计算, 在第一部分中使用函数CreateFileMapping创建一个共享的文件数据句柄, 并使用MapViewOfFile获取了共享的内存地址, 在第二部分中使用OpenFileMapping函数在另一个进程里打开共享文件的名称, 这样就可以实现不同的进程共享数据。

此时程序加载指纹比对算法的动态库, 将MapViewOfFile函数返回的进程地址返回给比对函数, 内存中的比对工作便可以开始进行。

使用本技术针对某部门CAFIS指纹系统的CPU、GPU比对程序, 对32位和64位系统分别进行了测试。

2.4 实验流程

最后将比对程序返回的结果进行格式化处理, 使其成为能够在指纹比对系统中使用的数据。内存计算程序基本流程图如图1所示:

图1 内存计算程序基本流程图

3 结 果
3.1 CPU程序测试结果

由于CPU比对测试相对于GPU而言运行速度比较慢, 而测试机器读写速度较快, 采用内存比对的优势相对不算明显。表1, 表2中的测试样本数据量选择三组数据分别是0.6G、1.2G、1.8G, 每组数据通过两种方式进行比对, 由于内存方式比对中数据提前加载到内存中, 所以内存比对方式的I/O时间为0; 其中样本数据量为1.8G的数据, 分别又进行了1个、2个、4个进程的测试, 通过多个进程比对可以更为明显的显示内存比对的优势。

表1 32位系统CPU内存计算测试结果
表2 64位系统CPU内存计算测试结果
3.2 GPU程序测试结果

32位GPU选取了3组数据, 64位GPU测试程序中选取了5组数据, 如表3、表4所示, 为GPU测试机器一的数据, 可见I/O访存时间几乎是整个比对过程总时间的一半, 使用内存比对方式比对效率可以提高约50%。表5所示, 为GPU测试机器二的数据。由于GPU比对程序运行较快, 可以明显看出I/O访存时间几乎是整个比对过程总时间的三分之一, 在内存比对算法中由于提前将数据加载到内存中, 多个进程并行运算时只需要加载一次内存, 不需要重复进行访存, 减少了I/O的开销, 整体的比对效率可以比硬盘直接比对提高30%。由于条件所限, GPU测试没有进行并行程序的测试, 内存比对结合GPU并行程序会取得更好的效果[6]。

表3 32位100MB/s 读写速度GPU内存计算测试结果
表4 64位100MB/s 读写速度GPU内存计算测试结果
表5 64位200MB/s 读写速度GPU内存计算测试结果
4 讨 论

通过使用内存比对方法可以将原有约每天4000个比对任务提高到约6000个比对任务, 能够充分满足现有的指纹日提交量的需求, 增加单位时间内的比对任务数, 提高系统的工作效率。目前, 我国刑事案件发案率较高, 严重影响到人民群众的生命财产安全。随着交通运输工具的日益发达, 迅速锁定犯罪嫌疑人对犯罪嫌疑人的抓捕和案件的侦破有着极其重要的意义。指纹作为物证之首, 对锁定犯罪嫌疑人有直接作用, 所以指纹自动识别系统的比对速度至关重要。

某部门现行指纹系统中, 有少部分硬件能够满足大内存需求, 但大部分是32位机器, 内存较小, 不能直接使用该算法。进一步的研究将针对这部分机器着眼于如何利用小内存分段存储来实现内存计算, 最终实现小投入大回报的指纹系统升级, 为指纹查询比对工作更好的发挥在主动打击犯罪过程中的特殊作用做贡献。

The authors have declared that no competing interests exist.

参考文献
[1] 刘少聪. 手印学[M]. 北京: 警官教育出版社, 1994: 16-28. [本文引用:1]
[2] 孟柯, 杨华. 对变异指纹鉴定的几点体会[J]. 刑事技术, 2009(1): 53-54. [本文引用:1]
[3] 冯才刚, 吴春生 . HPC超算技术在指纹自动识别系统上的应用[J]. 物证技术研究, 2011( 1). [本文引用:1]
[4] 刘冰, 陆中华, 李新亮, 等. 基于GPU的多重网格Navier-Stokes减算器并行优化方法研究[J]. 科研信息化技术与应用, 2013(3): 56-57. [本文引用:1]
[5] 吴春生, 冯才刚, 迟学斌. GPU 指纹计算程序简述及性能分析[J]. 科研信息化技术与应用, 2012(4): 37-45. [本文引用:1]
[6] 多相复杂系统国家重点实验室多尺度离散模拟项目组. 基于GPU的多尺度离散模拟并行计算[M]. 北京: 科学出版社, 2009: 149-150. [本文引用:1]