基于细节点频谱的指纹图像匹配算法研究

陈汉涛，胡旭晓

（浙江理工大学机械与自动控制学院，杭州310018）

基于细节点频谱的指纹图像匹配算法研究

陈汉涛，胡旭晓

（浙江理工大学机械与自动控制学院，杭州310018）

为了提高指纹识别系统对存在位移、缩放和旋转等线性变化的指纹图像识别率，提出一种基于指纹细节点频谱的指纹匹配算法。首先介绍了从频率域提取指纹细节点的频谱特征，利用傅里叶-梅林变换的特性来消除平移、缩放和旋转等线性变化，从而获得稳定的无需再次校准的指纹特征；由于新的频谱特征是以矩阵形式存储的，因此可以直接用欧氏距离来评估两个指纹特征的相似程度，进而完成指纹图像的匹配；最后利用Matlab搭建了一个系统平台，在FVC2002 DB2数据库中进行实验。结果表明：与其他方法相比，笔者提出的方法明显提高了自动指纹识别系统的识别率。

指纹识别；频率域特征提取；傅里叶-梅林变换；免校准

0　引 言

随着现代信息技术的迅速发展，指纹图像识别系统的应用也越来越广泛。由于采集时的手指位置，采集人的手指压力以及现场的环境情况会导致采集到的指纹产生位移、缩放和旋转等线性变化，而现有的自动指纹识别系统对这些存在线性变化的指纹［1-3］识别效果还不能满足实际的需要。

指纹图像匹配是指利用指纹图像的特征来进行指纹匹配，用来匹配的特征可以分为：整体特征、局部特征和超细节特征［4-7］。其中，整体特征可以分为指纹纹线和指纹方向场；局部特征主要是指纹细节点［8］；超细节特征是指纹上的气孔［9］。根据指纹的不同特征，目前已有许多研究者提出多种指纹匹配算法，主要有基于点模式、基于纹理模式和基于频谱的匹配方法。但大多数的指纹匹配算法主要依赖于细节点进行指纹匹配，如Jain等［10］提出了一种基于串距离的算法，该方法首先提出限界盒的思想，并将细节点坐标从直角坐标系转换到极坐标系下，较好地解决了指纹图像匹配中弹性形变的问题。张志禹等［11］将点模式匹配算法与二维主成分分析匹配算法结合起来进行特征比对处理，使得识别的准确性和系统的利用率得到进一步提高。付翔等［12］提出一种新的细节点柱形结构的匹配算法，该算法有效地减少了匹配时间和存储代价，且准确性较高。

但是使用细节点进行匹配时，一般在匹配前都需要有校准环节，不仅仅耗时，而且增加计算复杂度。基于此，为了克服校准环节带来的不便，本文提出了一个新的指纹匹配方法，使用一个固定长度的代码表示指纹的频谱特征，由于频域指纹特征是用一个固定长度的代码表示，并且以矩阵形式存储的，因此匹配时不需要校准，直接用欧氏距离来评估两个指纹特征的相似程度，这样就大大减少了匹配时间，加快了系统的识别速度，同时也提高了系统识别准确率，从而改善整个系统的性能。

1　细节点的频谱特征

设两幅图像为g1（x，y）和g2（x，y），其中g2（x，y）由g1（x，y）沿坐标轴平移（x0，y0）得到。

g1（x，y）和g2（x，y）对应的频谱分别是G1（u，v）和G2（u，v），根据傅里叶变换的公式，可以推出式（2）：

代入式（1），可得出式（3）左右两边具有相同的模值：

式（3）证明了傅里叶变换具有平移不变性。

设有一幅图像g1（x，y）经过旋转和缩放后得到图像g2（x，y）：

其中：α是图像旋转过的角度；σ是图像放大的倍数。

旋转和放大造成的影响在对数极坐标中表现为坐标值的平移。极坐标转换公式为式（5）和式（6）：

其中：（x，y）是直角坐标系坐标；（r，θ）是极坐标系中的坐标。

设g1（x，y）和g2（x，y）转换到对数极坐标空间后对应的表达式分别是g1p和g2p于是有：

可以看出式（7）和式（1）等价，因此可以利用傅里叶转换的平移性质解决这个问题。

1.1基于细节点位置的频谱特征表示（ML）

假设以指纹图像的中心点为中心，R为半径的圆内共有Z个细节点，对于每个细节点，可以使用如下的狄拉克脉冲表示i=1，2，…，Z，（xi，yi）表示第i个细节点的坐标。而mi（x，y）傅立叶变换之后表达式为：

其中：ωx=2πxi/M、ωy=2πyi/N，M和N分别为指纹图像的高和宽。

基于位置的细节点频谱可以表示为：

为了减少由于空间域中细节点微小的的坐标变化而引起的灵敏度变化，本文使用高斯低通滤波器来衰减较高频率。现在每一个细节点由一个高斯脉冲表示，二维高斯公式g（x，y）在空间域及其傅立叶变换后G（ωx，ωy）是：

根据傅立叶变换具有平移不变性，所以频谱M的大小可以表示为：

1.2基于细节点位置和方向的频谱特征表示（MO）

本文提出了一种基于细节点位置的细节点频谱特征。但是指纹细节点除了位置信息以外，还有一种非常重要的性质：方向信息，因此，上文中的狄拉克脉冲函数上可以加入方向信息，mi（x，y）变为mi（x，y，θ），其傅立叶变换后为：

1.3指纹细节点频谱特征提取流程

特征提取流程如图1所示，具体步骤如下：

a）利用指纹图像中心点和细节点信息（包括细节点位置和方向信息），构建狄拉克脉冲函数，利用傅里叶变换从空间域转换到频率域，通过傅立叶-梅林变换，获取细节点的频谱并且把它作为指纹的特征信息，图1中R取值为75。

b）分割指纹图像信息和背景，由于在频率域内，需要的有效区域大多集中在中心点附近，且为了节省时间和提高工作效率，本文对频谱图进行分割。使用本文的方法，频谱图中指纹的特征信息集中在半径为r的圆环中，rmin＜r＜rmax，取rmin=6，rmax=25。

图1　特征提取流程

c）对分割出的环状指纹频谱作对数极坐标转换。在数学上，我们假设图像信息是连续信号，只需利用极坐标-笛卡尔坐标转换式（5）和式（6）就可，以实现。但是在实际应用中计算机采集和存储的均为离散信号，转换成极坐标时，有些定义域的整数点和值域的整数点并非一一对应，也就是说当r和θ取整数值时，（r cosθ，r sinθ）不一定是整数值，这就要求我们在转换时采用插值的方法，估算出各个极坐标对应的值。

d）最后，再对该图像进行一次二维快速傅里叶变换，取模值并压缩特征信息，最终得到免校准的指纹特征。这种指纹特征是使用的20×180矩阵形式表示。

1.4仿真

指纹图像的幅频特性表示如图2所示，其中图2（a）和图2（c）是同一枚手指，图2（e）和图2（g）是同一枚手指，图2（b）、图2（d）、图2（f）、图2（h）分别是图2（a）、图2（c）、图2（e）、图2（g）在极坐标下的细节点位置频谱。

图2　极坐标下基于细节点位置的频谱

从图2中可以看出，不同的指纹的幅频特征相差极大，而相同指纹的幅频特征则类似，但也存在着平移变化，因此可以利用傅里叶转换的平移性质解决这个问题。

2　指纹特征匹配

上文重点介绍了免校准的指纹图像特征及其具体的提取方法。考虑到本文中的频域指纹特征是以矩阵形式存储的，本文选用了简单有效的欧式距离匹配方法。事实上欧氏距离在二维空间中就是两点间的距离。可以直接用欧氏距离来评估两个指纹特征的相似程度。并设立一定的阈值［17］，认为相似度超过域值的就是同一枚指纹，而相似度小于域值的就是不同指纹。

将两枚指纹提取出的指纹特征进行比对，也就是计算出指纹特征对的欧氏距离集合并累加，把这个值成为指纹见比对的“分数”，并以此来衡量指纹特征间的相似程度，理论上欧氏距离越小的指纹特征越相似，也就是比对的得分越小指纹相似度越高，但是这与平时理解的习惯不服，因此，在搭建系统平台时，对比对分数进行了归一化处理，使其集中在0到1之间，并将该分数与1的差值作为新的比对分数，这样就将指纹间的比对结果变成了了分数越高越相似。

3　实验

系统采用的软件平台是Matlab 2013a。数据库采用的是国际指纹识别比赛所使用的FVC指纹库［15-16］（FVC2002，DB2），此指纹库包含100个指纹图像，每个指纹通过光学扫描仪分别采集了8个样本，共计800幅指纹图像。

在所有的FVC指纹库中，FVC2002指纹库的应用非常普遍，是国际指纹识别大赛公认的识别较常用的指纹库，也是比较难的库，包含很多低质量指纹和存在线性变化的指纹，如图3所示，图3（a）与图3（b）间存在平移，而图3（b）与图3（c）间存在旋转，这给指纹识别带来了巨大的挑战，采用传统的指纹识别方法将在校准环节耗费大量时间，且无法保证其准确性。因此选用FVC2002指纹库来评估本文提出的自动指纹识别系统的性能。

图3　存在线性变化的指纹图像

3.1应用示例

FVC2002，DB2指纹库中共有来自100枚指纹的800幅图像。若全部选取作为试验用，则会出现假指纹样本过多，与真指纹对出现一个数量级的差距，造成不必要的统计误差，因此，为平衡在识别过程中的真指纹比对次数和假指纹的比对次数，在识别过程中选取的真指纹和假指纹的数量情况如表1所示。

表1　实验选择的真假指纹样本情况

3.2结果分析

除本文中提出的免校准频域指纹特征外，本实验还选择了两种指纹特征作为对照实验。由于方向场特征的实验效果普遍比细节点的识别效果差，如此选择了细节点位置和方向［18］作为第一个对照指纹特征，另外，为证明本文对傅里叶-梅林变换做的改进工作确实有效，同时也采用了仅作傅里叶-梅林变换的频谱作为特征的对照实验。

应用4种不同指纹特征的自动指纹识别系统的ROC曲线对比图如图4所示，为了方便观察，把图像在对数坐标中展示。

点状虚线是仅作傅里叶-梅林变换的频谱作为特征的指纹识别系统的ROC曲线，实线是基于细节点位置频谱特征作为特征的指纹识别系统的ROC曲线，虚线是基于细节点位置和方向频谱特征作为特征的指纹识别系统的ROC曲线，绿色点划线是使用细节点作为特征的指纹识别系统的ROC曲线。图4中的对角线与ROC曲线的交点就是等误差率（EER）的值。

首先比较点状虚线和实线，本文提出的ML性能有了大幅提升，等误差率从12.2%下降到4.1%这证明本算法对传统傅里叶-梅林变换所做的改进是具有可行性和有效性的。再比较点划线和虚线，使用细节点系统的等误差率为2.0%，略高于本文提出的MO，但是对于民用场合，两者的系统性能均在可接受范围之内，且本文提出的指纹特征无需校准，计算复杂度低，可以更快地得出比对结果。最后，比较基于ML和MO，从图6中可以看出，MO要优于ML，这也就说明利用细节点位置信息和方向信息要比只利用细节点位置信息效果要好。

整体上来说，基于细节点位置和方向的算法效果最好，MO次之，ML略低于MO，而仅作傅里叶-梅林变换的频谱算法效果最差。

图4　4种不同指纹特征对应的系统ROC曲线

实验中，半径R对等错率有着重要影响，如图5所示。

图5　半径R对等错率影响

如图5所示，半径R对等错率（EER）影响是很明显的，且R取值大小对MO和ML影响基本类似。半径R较小时，等错率比较大，这也与半径小时细节点个数很少相吻合；当R大于80时，随着R增大，等错率也随之增大，这也与R过大，圆的范围可能已经超出了图像的边界相吻合；等错率最低一般出现在R为70到80之间时。本文试验中，R取值取75。

实验中还发现如果出现丢失或者虚假细节点时，也会影响到等错率（EER），效果如图6所示。当提取的细节点个数相差不大时，等错率比较理想，当细节点个数相差很大时，等错率就不是很理想了，从图6中可以看出，丢失或者虚假细节点的比例低于15%时，对等错率是没有明显影响的，当比例高于20%时，开始对等错率有明显影响了。当丢失或者虚假细节点的比例大于25%时，对 ML影响比对MO要大，但是若丢失或者虚假细节点的比例大于27%时，这种影响对于MO要大。

图6　丢失或者虚假细节点对等错率影响

4　结 论

为了提高自动指纹识别系统对存在线性变化的指纹图像的识别率，本文提出一种指纹细节点频域特征，这种特征不同于常用的空间域指纹，没有方向场和细节点直观，但是实验结果表明，此频域特征同样具有唯一性和稳定性，可以用于指纹识别系统。经过傅里叶-梅林变换的该特征不受平移、旋转和缩放等影响，在后续的指纹比对环节不需要复杂的校准，可以就直接使用，从而减少了指纹识别系统的环节，加快了匹配速度。而利用Matlab构建的自动指纹识别系统在FVC2002 BD2指纹库上的运行结果也表明该系统是有效的，其ROC曲线表明，该系统具有较高的识别准确度，两种方法的等错率均低于4%，可以用于各种普通民用指纹识别场合，此外，由于本文的方法具有比对速度快，法适用于处理大规模指纹库的情形，以及对速度要求很高的场合。同时，本文只消除了线性变化对指纹识别的影响，没有对其他低质量指纹的问题进行处理，下一步研究重点是改进处理方法，对于模糊的指纹进行处理，以进一步提高指纹的识别率和匹配速度。

［1］Ryu C，Kong S G，Kim H.Enhancement of feature extraction for low-quality fingerprint images using stochastic resonance［J］.Pattern Recognition Letters，2011，32（2）：107-113.

［2］Yu C，Xie M，Qi J.An effective algorithm for low quality fingerprint segmentation［C］//Intelligent System and Knowledge Engineering，2008：3rd International Conference on.IEEE，2008，1：1081-1085.

［3］Cappelli R，Maio D，Maltoni D，et al.Performance evaluation of fingerprint verification systems［J］.Pattern Analysis and Machine Intelligence，IEEE Transactions on，2006，28（1）：3-18.

［4］Liu F，Zhang D.3D fingerprint reconstruction system using feature correspondences and prior estimated finger model［J］.Pattern Recognition，2014，47（1）：178-193.

［5］Bian W，Luo Y，Xu D，et al.Fingerprint ridge orientation field reconstruction using the best quadratic approximation by orthogonal polynomials in two discrete variables［J］.Pattern Recognition，2014，47（10）：3304-3313.

［6］Cao K，Yang X，Chen X，et al.Minutia handedness：a novel global feature for minutiae-based fingerprint matching［J］.Pattern Recognition Letters，2012，33（10）：1411-1421.

［7］Jirachaweng S，Hou Z，Yau W Y，et al.Residual orientation modeling for fingerprint enhancement and singular point detection［J］.Pattern Recognition，2011，44（2）：431-442.

［8］Feng J.Combining minutiae descriptors for fingerprint matching［J］.Pattern Recognition，2008，41（1）：342-352.

［9］Zhao Q，Zhang D，Zhang L，et al.Adaptive fingerprint pore modeling and extraction［J］.Pattern Recognition，2010，43（8）：2833-2844.

［10］Jain A K，Hong L，Pankanti S，et al.An identityauthentication system using fingerprints［J］. Proceedings of the IEEE，1997，85（9）：1365-1388.

［11］张志禹，侣 薇.一种基于混合匹配的指纹识别方法［J］.微型机与应用，2011，30（2）：42-44.

［12］付 翔，毛紫微，刘重晋，等.构建细节点柱形结构的指纹匹配算法［J］.计算机科学与探索，2012，6（7）：586-592.

［13］Xu H，Veldhuis R.Binary representations of fingerprint spectral minutiae features［C］//Pattern Recognition（ICPR），2010 20th International Conference on.IEEE，2010：1212-1216.

［14］臧 炅，袁 杰，都思丹.基于Fourier—Mellin变换的指纹匹配算法研究［J］.计算机仿真，2009（3）：231-233.

［15］田 捷，杨 鑫.生物特征识别理论与应用［M］.北京：清华大学出版社，2009.

［16］Jayaraman U，Gupta A K，Gupta P.An efficient minutiae based geometric hashing for fingerprint database［J］.Neurocomputing，2014，137：115-126.

［17］Tong X，Liu S，Huang J，et al.Local relative location error descriptor-based fingerprint minutiae matching［J］.Pattern Recognition Letters，2008，29（3）：286-294.

［18］Choi H，Choi K，Kim J.Fingerprint matching incorporating ridge features with minutiae［J］. Information Forensics and Security，IEEE Transactions on，2011，6（2）：338-345.

Research of Fingerprint lmage Matching Algorithm Based on Spectral Minutiae

CHEN Han-tao，HU Xu-xiao
（School of Mechanical Engineering&Automation，Zhejiang Sci-Tech University，Hangzhou 310018，china）

In order to improve the recognition rate of fingerprint images with displacement，rotation and scale，this paper proposes fingerprint matching algorithm based on the spectral of fingerprint minutiae.Firstly，this paper extracted the feature of fingerprint minutiae in frequency domain.Secondly，this paper used the characteristics of Fourier-Mellin transform（FMT）to eliminate the linear changes（such as translation，scaling and rotation）to obtain the alignment-free and stable fingerprint feature.Since the new fingerprint minutiae spectral feature was stored in the form of matrix，Euclidean distance could be directly used to evaluate the similarity degree of two fingerprint features so as to complete the fingerprint image matching.Finally，this paper utilized matlab to build a system platform and carried out experiment in the FVC2002 DB2 database.The experimental result shows that：compared with other methods，the proposed method significantly improves the precision of the automatic fingerprint recognition system.

fingerprint recognition；extraction of frequency domain feature；FMT；alignment-free

TP391.4

A

1673-3851（2015）06-0858-06

（责任编辑：陈和榜）

2015-01-26

浙江省自然科学基金项目（LZ14E050003）

陈汉涛（1987-），男，安徽枞阳人，硕士研究生，主要从事图像识别、自动控制方面的研究。