分布式海量指纹识别

姚丽莎，徐国明，陈乃金，周 欢

(安徽新华学院信息系统软件研究所，安徽 合肥 230088)

近年来，指纹识别技术现今已经发展成熟，国内外许多指纹识别研究成果主要描述如何构造特征描述符。目前指纹描述符主要分为基于细节点的描述符和基于纹理的描述符两类。TICO M[1]提出一种基于方向信息的描述符，PARK U[2]提出描述指纹信息的SIFT[3]描述符，JIANG X[4]提出最近邻描述符，CHEN X[5]提出固定半径的特征描述符，FENG J[6]提出混合描述符可以结合细节点和纹理特征，CAPPELLI R[7]提出细节点柱形编码(Minutia Cylinder-Code，MCC)结构。

但是，指纹识别领域目前的研究重心主要在提高指纹识别的准确度，忽略了海量指纹数据识别的时间问题，海量指纹识别的实用性成为主要难题。MIRON R[8]提出了一种新的指纹识别架构，在多个服务器上分别放置大量的指纹数据，在各个服务器上顺序检索指纹，检索成功后结束。该架构虽然解决了数据集分布式存储的问题，但是仍为集中式计算，并未实现分布式并行计算，不能完成实时检索。PERALTA D[9]根据指纹的分布式特点，在多个节点上进行指纹数据分布，在每个节点上并行的检索指纹，可以解决海量指纹数据实时检索的问题。目前的指纹识别系统主要通过暴力匹配，而这对于海量指纹是不适用的。本文提出了分布式海量指纹识别技术，首先对采集的指纹进行特征提取，然后利用指纹特征对指纹进行全局指纹分类，最后利用匹配界限盒方法进行指纹匹配以完成未知指纹数据的身份确认。利用分布式网络计算的运算特性，设计了一个分布式海量指纹识别系统。

1 指纹数据的压缩及存储

在海量指纹数据检索的过程中，需要从数据库下载一些待比对的指纹图像到本地，为了满足应用需要，对指纹数据进行压缩传输。目前，存在一种压缩方法可以满足对指纹图像数据进行压缩传输的现实应用要求，可以把原有的指纹特点保存，这种压缩方法就是小波压缩[10]。小波变换子频段编码的实现方法：①用一组滤波器采用重复卷积的方法，把采集信号分为低频和高频。②统计低频和高频分量，量化特征相类似的编码器。③在解码时，为了重建图像需要对低频分量和高频分量进行插值和共轭滤波。基本原理如图1所示。

图1 子频段编码原理图

1.1 小波变换子频段编码的工作过程

小波变换子频段编码的主要工作包括：①一个滤波器(Qualcomm，low pass)把输入端在水平方向的信号进行卷积，同时另一个滤波器(Qualcomm，low pass)把输入端在垂直方向的信号进行卷积[11]。②能够获得四块面积，把这四块面积与原图像进行相比，可以看到占到原图面积的25%，这四块面积包括：低频分量LL、垂直方向的高频分量HL、水平方向的高频分量LH和对角线方向的高频分量HH。③编码高频分量以及量化编码，编码低频分量以及量化编码。④继续分解垂直高频分量得到二级小波分解和三级小波分解，编码也类似[12]。三级小波分解如图2所示。

图2 三级小波分解

1.2 图像压缩

图像压缩具体做法包括：设置一个阈值σ，把经过小波变换得到的水平、垂直和对角细节分量值与该阈值σ比较，再把小于等于σ的细节分量值设置为“0”。由此进行编码，这样就实现了图像压缩。

编码是压缩的最后一个步骤。通常结合赫夫曼编码和快速余弦变换方法来压缩低分辨率子图HH，去除细节子图的高频分量，结合Huffman编码来压缩图像。使用赫夫曼编码方法包括以下步骤：①按降序排列概率的大小。②对两个最小的概率进行加法运算，然后一个新的概率集合就构成了，按降序排列概率的大小，以此类推，一直到只存在两个概率为止。③码子需从最后开始完成反向分配，对最后两个概率一个赋予“0”，一个赋予“1”。对码子进行概率统计。然而在实际应用中，每幅图像的出现概率是不同的，对于任何图像压缩而言，需要进行概率统计。

2 分布式海量指纹识别技术

分布式网络是把指纹数据库分布存储，根据不同地域，将指纹存储在不同地方。并且每个分数据库根据指纹特征分类存储指纹数据信息，每一个分数据库服务器同时搜寻，进而提高对未知指纹数据身份确认的速度。

2.1 分布式海量指纹识别系统组成

海量指纹数据库识别系统包括3个部分：①利用指纹采集设备对个体进行指纹采集，然后对采集的指纹进行指纹预处理和特征提取。②计算机发送采集的指纹数据到数据库服务器。③利用全局指纹分类系统验证采集的指纹，通过以上操作进行未知指纹数据的身份确认。原理图如图3所示。

图3 分布式海量指纹识别系统的原理图

图4 分布式海量指纹识别系统架构

2.2 分布式海量指纹识别系统工作流程

分布式海量指纹识别系统的工作流程包括：①利用指纹采集设备对个体进行指纹采集。②计算机通过预处理和对采集的指纹进行特征提取，利用计算机将采集的指纹数据发送到指纹数据库主服务器中。③指纹数据主服务器将特征信息发送给每个指纹数据分服务器。④每个指纹数据分服务器对特征信息进行提取,并在指纹数据库分服务器中搜寻，然后将结果发送到指纹数据主服务器。⑤指纹数据主服务器把结果发送到计算机。具体流程如图4所示。

2.3 指纹预处理

指纹预处理目的是提高指纹图像的质量，将特征提取的准确性提高。本文预处理过程包括图像分割、增强、二值化和细化。指纹预处理流程图如图5所示。

图5 指纹预处理流程图

2.3.1 指纹图像分割

因为指纹与图像背景难以区分，需要对指纹图像进行分割。背景的梯度值较低，而指纹图像的梯度场值比较高。因此，利用梯度场来进行指纹图像分割，即采用分型维数来分割指纹图像。图像块的分形维数描述了其纹理和灰度分布的复杂程度，其是单位区域上的梯度，利用前景与背景的分形维数可以区分图像的前景和背景。本文利用分形维数来分割指纹图像的背景与前景，具体步骤如下：

2.3.1.1 定义F盒维数

即设F是Rn上的任意非空的有界子集，Nσ是直径最大为σ、可以覆盖F的集合的最少个数。则F的盒维数定义为：

(1)

2.3.1.2 计算图像的盒维数

图像中像素点的灰度值表示为Z=f(x,y)，其中，(x,y)为像素点的位置坐标，Z代表对应点的灰度值。设图像大小为M×M，将图像的XY平面分成大小为σ×σ的格子，设该XY坐标系中格子(i,j)里像素点灰度最大值为uσ(i,j)，灰度最小值为bσ(i,j)，且定义两者的差值为：

(2)

对于所有边长σ、格子非空的盒子总数Nσ的计算公式为：

(3)

2.3.1.3 计算梯度值

2.3.1.4 通过梯度阈值分割前景和背景

图像质量不同，阈值的取值也不同。通常，若图像平滑则阈值取30～40，若图像平滑度不够则阈值取50。单位区域阈值通过计算单位区域上的平均梯度来取值。其算法是：f(x,y)为图像的函数，T(x,y)为某位置(x,y)的梯度，则T(x,y)=f(x,y)。设A为分割阈值，若T(x0,y0)>A，则(x0,y0)点属于指纹图像的前景。若T(x0,y0)

2.3.2 指纹图像增强

采用Gabor增强算法实现指纹图像增强。用该图像块的纹线方向设置每块图像对应的滤波器的方向，用该图像块的纹线频率设置每块图像所对应的滤波器的频率。指纹图像的增强效果受滤波器通带大小设置的影响。设置较大通带时，噪声的抑制效果不明显，增强效果不佳，但对频率和方向误差有一定程度的容忍；设置较小通带时，滤波器的频率和方向选择性较强，因此对滤波器频率和方向的误差较敏感，但是对分离枯连纹线和连接断裂纹线的效果佳。先验值表明，滤波器窗口设为11时，滤波效果佳。具体算法如下：①拆分指纹图像为互不相交的区域；②分别计算各区域指纹的频率和方向；③为每个图像区域构建相应的增强模板；④对所有图像区域进行滤波。图6为原指纹图像，图7为增强后的指纹图像。

图6 原指纹图像

图7 增强后的指纹图像

2.3.3 二值化和细化

为了使指纹纹线脊的灰度值趋于一致，需对指纹图像进行二值化。对于纹线上的黑点来说，黑点大多分布在沿纹线方向的附近区域，其灰度值的和较小。白点大多分布在纹线方向的垂直方向附近，其在垂直方向上灰度值的和较大。对于纹线之间的白点来说，白点大多分布在沿纹线方向的附近区域，其灰度值的和较大，黑点大多分布在纹线方向的垂直方向附近，其在垂直方向上灰度值的和较小。因此，如果某点的法向灰度和大于切向灰度和，则判定黑点在脊线上，反之则白点在谷上。设f(x0,y0)为该点的灰度值，其方向场为ο(x0,y0)，σ为某一范围。

H为切向像素值和：

(4)

V为法向像素值和：

(5)

如果V大于H，那么该点在脊线上，反之在谷线上。

为了删除纹线的边缘像素，突出指纹纹线主要特征，对指纹图像进行细化处理。本文的细化算法采用查表法。

2.4 指纹分类

指纹是表皮上最突出的一条线，是指手指末端的凹凸皮肤的线条。因为每个指纹不相同，所以指纹又被人们称为“人体身份证”。指纹的特征包括全局和细节特征[13]。

全局特征是指人们通过眼睛能够看到的指纹特征，主要包括：①模式区：包含指纹整体特征的地方，通过模式区域可以区分指纹的类别。②三角点：断点、核心点或两纹线间出现的第一个分岔点，如图8所示。三角点可以用于线的计数和跟踪。③纹数：在模式区中指纹纹路的个数。④样式线：包围模式区的纹线开始平行的地方所出现的交叉纹路，其通常很短就中断了，但其外侧线开始连续延伸。⑤中心点：指纹纹线的渐进中心，常作为读取指纹的参考点。中心点位置如图8所示。

图8 指纹全局特征

局部特征指的是指纹上的节点。每个人的指纹总体特征可能相似，但是它们的节点是不可能一样的。图9给出了常见的细节点类型。

图9 常见的局部细节点类型

节点包括：①端点：纹线终结点。②分歧点：两条平行纹线的分开起点。③分叉点：一条纹线分开成多条的起点。④孤立点：一条很短的线以至于形成一个点。⑤环点：一条纹线分开成为两条之后，又合并成一条。⑥短纹：一条很短的线，但不至于形成一个点的纹路。

利用奇异点的类别和个数对指纹进行分类。奇异点包括了中心点和三角点，它描述了指纹的整体特征，提取特征点提取进行指纹分类。指纹分类可以依据一个中心点类型、两个中心点类型、一个中心点和一个三角点类型、零个三角点和零个中心点类型，用这四种类型进行分类。

判定奇异点需要使用Poincaré公式，求Po值：

(6)

Poincaré是对某点周围一圈求方向场差的积分。方向场差求得值越大，Po值越大。其周围方向场变化越剧烈，则奇点存在的可能性越大。

在数字指纹学中，需要用离散Poincaré建立数字模型，表示的方法为方格计算法。取一个5×5的方格，计算(i,j)为中心各以D或d为半径的区域方向场差的和。

在5×5方格内，以(i,j)为中心，形成顺时针方向闭合曲线D1,D2,…,D12。该闭合曲线的Po值为：

(7)

在3×3方格内，以(i,j)为中心，形成顺时针方向闭合曲线D1,D2,…,D8。该闭合曲线的Po值为：

(8)

由于受图像中存在噪声等因素的影响，指纹可能存在伪奇异点。为了消除伪奇异点，计算闭合曲线顺时针方向以(i,j)为中心的Po值。只有3×3方格和5×5方格的Po值相同时，候选奇异点才作为真正的奇异点。

2.5 指纹匹配

指纹匹配是指对输入样板图像对比纹预留模板图像中的所有特征点的匹配，该流程如图10所示。设模板特征点为P，样板特征点为P′，若P约等于P′，则给分数累加上相应的分数。用相似度公式计算出相似度，与合格阈值进行对比，若小于合格阈值则返回比对成功，若大于合格阈值则返回比对失败。指纹匹配算法采用匹配界限盒，固定界限盒模型如图11所示，设定角度误差上限为A，距离误差上限为D，如果线性匹配误差在界限盒内，由表示模板上某个特征点与样板上对应特征点是匹配的，因此就在相似度公式的分数项加分，完成线性匹配算法。

图10 特征点匹配流程图

图11 固定界限盒模型

匹配界限盒流程伪代码为：

总分数=0；

比对特征个数=0；

For eachPin 模板

For eachP′ in 样板

If (P与P′没用被比对过且是否相似(P与P′相似分数))

{

总分数+=相似分数;

比对特征个数++;

标记P被比对过

标记P′被比对过

}

3 实验结果分析

本文利用分布式网络设计了一个分布式海量指纹识别系统，该系统包括指纹数据主服务器和分服务器。①在主服务器上打开一个指纹图像；②通过主服务器连接到分服务器；③在分服务器进行测试；④在分服务器的Search ID框中，输入from 2 to 6；⑤在分服务器获取未知指纹；⑥通过分服务器向主服务器发送比对结果。

采用国际标准测试库FVC2004指纹库中的指纹作为标准指纹库进行测试，采用文献[7]中新的细节点柱形编码(MCC)结构的指纹识别技术和国际商用的BioCore SDK进行对比实验。对比结果如表1所示。

表1 不同识别算法对FVC2004的验证结果比较

在表1中，相等错误率(EER)表示给定匹配相似度下误识率(FAR)和拒识率(FRR)相等时的错误率。可以看出，本文算法的识别准确率和识别效果与其他两种算法相差不大，但是识别效率大大提高了。

4 结语

目前指纹识别的研究大多都集中于如何提高指纹识别的准确度，但是忽略了匹配的时间开销，即没有在海量数据下考虑问题。因此在海量指纹电子档案中快速比对指纹是一个很大的难题。本文提出了分布式海量指纹识别技术，通过小波变换对指纹进行压缩并存储在分布式网络中，提高算法效率。首先，通过分形维数分割指纹图像背景，采用Gabor增强算法进行指纹预处理；然后，提取指纹奇异点，利用奇异点的个数和类别对指纹进行分类；最后，通过匹配界限盒完成指纹匹配。实验结果表明，分布式海量指纹识别在海量指纹识别上具有很好的性能，提高了实时识别的效率。