基于GPU的局部指纹频谱特性估计的实现

，

(信息工程学院，浙江 杭州 310023)

自动指纹识别系统在过去的50年里不断地被研究开发，其中仍然有很多开放性的研究课题，特别是当获取的指纹图像质量较差，指纹特征不明显的时候.为了能够准确地从指纹图像中获取指纹特征，指纹图像增强成为了自动指纹识别系统中必不可少的一个步骤.已知自适应指纹图像增强系统在等误差率、认假率和不匹配率等方面都有很好的表现[1-2].其中局部指纹频谱特性估计是该指纹图像增强系统的核心组成部分，由于其需要对大量的局部指纹图像进行频谱特性估计，因此仅仅利用CPU进行运算需要消耗较长时间.

近年来，GPU已经发展演变成了一种高并行度，多线程的多核处理器，它强大的计算能力和极大的内存带宽让其不再局限于传统的3D图像处理，而是更多地被广泛用于通用并行计算[3-5].由英伟达公司开发的CUDATM运算平台为开发人员提供了一套针对GPU的编程模型，使得GPU具备了解决复杂计算问题的能力，同时大大简化了GPU编程[6].如今通过CUDA的GPU编程已经在信号处理领域，特别是图像处理领域被广泛应用[7-9].此外，由于不同局部指纹的频谱估计之间具有高度的独立性，非常适合多线程实现.因此，将该基于GPU的并行实现方法，应用于已知指纹增强系统，以提高已知指纹增强系统局部指纹频谱估计的运算速度.

1 局部指纹频谱特性估计

由于局部指纹在频谱特性上相似于一个带噪声的正弦信号，因此只需要模拟正弦信号寻找主频率的方式便可以估计出局部指纹的纹线频率及其方向，即局部指纹的频谱特性.所要优化的局部指纹频谱特性估计大致可以分为3个步骤[1]：

步骤1采用SMQT对局部指纹进行动态范围调整，增强局部指纹的对比度，以解决局部指纹可能存在的对比度较差问题[10]，即

IH(m1,m2)=SMQT{IL(m1,m2)}

(1)

式中：IL(m1,m2)为一张M1×M2的局部指纹图像；IH(m1,m2)为对比度增强后的局部指纹图像，其中m1∈[0,M1-1]，m2∈[0,M2-1].

步骤2对增强后局部指纹图像IH(m1,m2)进行幅度谱计算，即

G(ω1,ω2)=|J{IH(m1,m2)}|

(2)

式中J{IH(m1,m2)}为对局部指纹图像IH(m1,m2)的二维傅里叶变换.

步骤3遍历幅度谱G(ω1,ω2)，获得幅度峰值Pi，从而筛选获得最大峰值PD及其对应的频率ωD,x与ωD,y，然后利用峰值计算峰度因子，用于判断局部指纹噪声大小，即

(3)

式中N为幅度谱中所含的峰值数.由于每个局部指纹含有一组频谱特征，因此整个指纹图像可以用特征图PD(n1,n2)，ωD,x(n1,n2)，ωD,y(n1,n2)和Q(n1,n2)来表示.

2 CUDA架构及其编程模型

从图像处理到通用并行计算，GPU强大的运算能力得益于其单指令多线程的体系架构，这种体系架构能够让程序员直接为线程编写程序，从而能够实现线程间独立计算，同时也能进行线程之间的相互协调通信，英伟达公司推出的CUDATM便是一种通用的并行计算架构.在CUDA架构中，GPU可以被看成是一组流处理器，配备有多种形式的内存，如全局内存、局部内存、纹理内存和共享内存等.一个多线程程序被划分成多个CUDA程序块，不同程序块之间相互独立，被自动平均分配给GPU的不同流处理器，如图1所示.

图1 多线程CUDA编程与GPU流处理器Fig.1 Multi-threaded CUDA programing with GPU streaming multiprocessors

此外CUDA运算平台还为GPU提供了一套编程模型(图2)，在CUDA编程模型中，程序员可以在CPU端以调用核函数的方式来来访问GPU，并且可以指定需要调用的线程块数量以及线程块中的线程数量.这些线程会组织成三级层次结构，线程组成线程块，线程块在线程格上运行，每一个线程和线程块都会有相应的内置标识符threadId和blockId来进行标识.

图2 CUDA编程模型Fig.2 CUDA programing model

3 基于GPU的指纹局部特性估计的实现方法

首先将整个指纹图像划分成一定数量的局部指纹图像，然后调用相应数量的CUDA线程块来实现并行处理不同局部指纹的功能.此外，对于其中某一块，相应CUDA线程块中的多个线程会被调用，来对其中的SMQT，2DFFT和特性估计进行并行优化.由于整个处理过程中指纹图像具备只读的属性，因此采用CUDA纹理内存来存储指纹图像以提高读取效率.图3简略地表示了线程块B(i,j)处理相应局部指纹图像IL(i,j)的过程，采用(i,j)标识线程块和局部指纹图像，即i和j分别表示局部指纹图像所在行数与列数.

图3 局部频谱特性估计模型Fig.3 The model of local spectrum estimation

3.1 SMQT的并行优化

针对SMQT中大量的平均值计算[10]，采用顺序寻址的CUDA并行归约算法来对其中的求和过程进行优化，图4简要地阐述了8个数并行规约求和的过程，首先利用4个线程将数据两两求和，并将求和结果存储于共享内存中.然后再利用其中两个线程将求和结果再次两两相加，以此类推，最后这8个数的和被存储于共享内存的第一块单元中.显然，如果需要对N个值进行求和，求和的步骤便可以从单线程的N-1次缩减到log2N次.

图4 顺序寻址的并行规约算法Fig.4 The model of local spectrum estimation

3.2 2DFFT的并行优化

由于CUDA提供的cuFFT库是一个只能在主机端调用的应用接口，并不能在设备端调用，因此只能重新实现设备端的2DFFT，图5简要地阐述了多线程2DFFT的实现过程.每一个CUDA线程块中的线程都会对局部指纹的某一行数据进行一维FFT运算，并将运算结果按转置的方式存储.等到所有线程都完成运算，再一次并行地对每一行数据进行一次一维FFT，其转置后的运算便是最终2DFFT的结果.

图5 2DFFT的并行实现过程Fig.5 The model of local spectrum estimation

3.3 特性估计的并行优化

利用CUDA线程块中的多线程，对局部指纹图像的幅度函数进行并行峰值遍历搜索.每个线程都会定义一个3×3的矩阵，用以判断幅度值在其领域内是否为最大值，从而独立完成对一行数据的峰值搜索.因此对于一个N1×N2的二维幅度函数，CUDA线程块中的N1个线程被充分调用.图6阐述了一个线程完成一行数据峰值遍历搜索的过程，其中每一行的最大峰值都会被保存下来，用于获得最终的频谱峰值及其坐标的同时计算峰度因子.峰度因子的计算式为

(4)

图6 一行数据的峰值搜索过程Fig.6 Peak search for a row of magnitude values

式中PD,M为每行最大峰值PD,i的最大值.由于整个过程对局部指纹的幅度函数只存在读取操作，因此不同线程之间完全并行，不需要进行内存加锁使得不同线程之间串行化.

4 实验结果及分析

实验在Intel Xeon E5-1620 3.5 GHz 的CPU，NVIDIA Geforce GTX 1080 的GPU以及8G DDR4 内存的硬件环境下完成，利用Visual Studio将基于GPU的局部指纹频谱估计接入完整的指纹图像增强系统并生成可执行文件.然后通过Matlab调用的方式，将FVC2000数据库中不同传感器来源的指纹图像输入测试.结果显示：将该基于GPU的局部指纹频谱估计应用于已知指纹增强系统中，指纹增强效果显著[1].以其中3个样本为例，效果如图7所示，其中图7(a～c)为原始指纹图像，图7(d～f)为分别对应的增强指纹图像.

图7 基于GPU指纹图像样本增强效果Fig.7 The examples of the fingerprint enhancement based on GPU

实验还对数据库中所有指纹的局部频谱估计执行时间进行统计，根据3种尺寸进行分类，得出相同尺寸指纹样本局部频谱特性估计执行时间的平均值，结果如表1所示， 其中加速比是指CPU平均执行时间与GPU平均执行时间的比值.实验结果表明：采用该基于GPU的实现方法，局部指纹频谱特性估计的计算时间显著减少，并且随着指纹尺寸的增加，效果越明显.

表1局部指纹CPU频谱估计与GPU的执行时间比较

Table1ThecomparisonoftheCPUbasedlocalfingerprintspectrumestimatorwithGPUbasedlocalfingerprintspectrumestimator

指纹尺寸CPU平均执行时间/msGPU平均执行时间/ms加速比324×2401 664.43989.701.68300×3002 089.731 099.611.90364×2562 144.611 065.922.01

5 结 论

针对已知指纹图像增强系统基于CPU实现执行时间较长的缺点[1]，提出了一种基于GPU的局部指纹频谱特征估计的实现方法，利用GPU多核心多线程的特点对不同局部指纹图像进行并行化处理，并对其中单个局部指纹处理中的SMQT，2DFFT以及特性估计3部分进行了并行优化，最后利用CUDA平台成功将其实现. 实验结果表明：通过该基于GPU并行运算的实现方法，已知指纹图像增强系统局部指纹频谱特性估计的执行时间显著减少，因此将该方法应用于这个已知指纹图像增强系统，可以提高其运行效率，使得该指纹图像增强系统有更大的应用前景.