基于二维主成分分析的指纹识别算法

计 算 机 工 程 第 34 卷 第7期

Vol.34 No.7 Computer Engineering ·人工智能及识别技术·

文章编号：1000—3428(2008)07—0215—03

文献标识码：A

2008年4月

April2008

中图分类号：TP18

基于二维主成分分析的指纹识别算法

金莉莉，李勇平，汪勇旭，王 琳

（中国科学院上海应用物理研究所，上海 201800）

摘 要：提出一种基于指纹统计特性的识别算法。该算法根据奇异点的位置和方向，提取指纹图像的感兴趣区域(ROI)，并使用二维主成分分析(2DPCA)的方法进行统计特征的提取和识别。在FVC2002指纹数据库上进行实验，结果表明：相对于PCA，该方法的计算速度更快。相对于传统的基于特征点的方法，该方法的实现更为简便。 关键词：指纹识别；二维主成分分析；奇异点

Fingerprint Recognition Algorithm Based on Two-dimensional

Principal Component Analysis

JIN Li-li, LI Yong-ping, WANG Yong-xu, WANG Lin

(Shanghai Institute of Applied Physics, Chinese Academy of Sciences, Shanghai 201800)

【Abstract】This paper proposes a fingerprint recognition algorithm based on statistics. Region of interest of a fingerprint image is extractedaccording to the position and direction of the singular points. Then the two-dimensional principal component analysis approach is applied to thetraining images represented by ROIs to get the statistical feature space. Fingerprint recognition is performed in the feature space using Euclideandistance classifier. Experimental results obtained on the fingerprint database of FVC2002 prove that the method has the advantages of fastcomputation speed compared with PCA, and simple implementation compared with traditional minutiae-based approach. 【Key words】fingerprint recognition; two-dimensional principal component analysis; singular points

1 概述

指纹识别技术是一种非常重要的生物特征识别技术，应用十分广泛。指纹的唯一性、终生不变及与主体不可分离等特性使其在传统的安全领域有着无法取代的地位。随着计算机和模式识别技术的发展，指纹识别技术已经成为计算机操作系统确认用户的手段，指纹考勤系统、门禁系统等也应运而生。

指纹特征的匹配是指纹识别系统中一个非常重要的环节，包括：基于图形图像的算法[1]，基于脊线结构的算法[2-4]，基于特征点匹配的算法[5-6]等。目前，大部分的自动指纹识别系统(AFIS)都是采用基于特征点匹配的方法，主要思想为：研究指纹脊线端点和叉点的坐标及方向的信息，根据这些信息进行匹配。而基于图像统计特征的指纹识别算法却少见报道，文献[7]提出了一种利用图像统计特征的基于PCA的指纹识别方法，并得到了较好的识别效果，然而这种方法要求把二维的人脸图像矩阵转化为一维向量，形成高维的向量空间，导致运算量过大，更重要的是这样做会丢失图像的二维结构信息。针对PCA的方法，本文提出了一种基于二维主成分分析(2DPCA)的统计识别算法，该算法针对二维图像矩阵，其协方差矩阵直接由原图像矩阵计算求得，其特征矢量维数与PCA方法相比大大减小，因此，提取特征的时间也大大缩短。本算法关注的是指纹图像中含识别特征的部分——指纹图像的感兴趣区域(Region of Interest, ROI)，通过识别ROI来进行指纹的识别。

独特性可以使其成为指纹分类的重要依据，而且两枚指纹奇异点周围的区域不可能完全相同，因此，将奇异点附近的区域定义为指纹的ROI。通过检测到的指纹奇异点来提取指纹的ROI。

2.1 奇异点的检测

笔者选用Poincare Index法[8]来进行奇异点的提取，此方法是指纹奇异点检测中一种非常经典、直观且简洁的方法，具体算法如下：

令ο(x,y)表示指纹图像的方向场，场中给定点(i,j)的Poincare Index值定义为

Poincare(i,j)=

1N 1

∑ (t) (1) 2πt=0

其中，

(t)(t)<π2

(t)= π+ (t) (t)≤ π (2)

π (t)其他

(t)=ο(x[t+1]modN,y[t+1]modN) ο(xt,yt) (3)

当Poincare(i,j)=1/2时，点(i, j)为core点Poincare(i, j)=-1/2，则点(i,j)为delta点。

基金项目：中国科学院“百人计划”择优支持基金资助项目“多种生物特征识别”；上海市浦江人才计划基金资助项目(05PJ14111) 作者简介：金莉莉(1981－)，女，硕士研究生，主研方向：生物特征识别；李勇平，研究员、博士、博士生导师；汪勇旭，助理研究员、硕士；王 琳，博士研究生

收稿日期：2007-06-24 E-mail：jinlili@

2 指纹图像ROI的提取

在指纹图像中，奇异点位于图像的中间区域，奇异点的

—215—

2.2 ROI的提取

ROI的提取在本方法中非常关键，因为ROI图像的质量直接影响到最后的识别效果。在提取ROI的过程中，首先根据奇异点来确定ROI中心点的位置，然后建立其方向，最后依照中心点的方向，在指纹图像中分割出一个m×n的子块，该子块就是ROI。具体分以下3种情况进行讨论：

(1)如果只检测到一个core点或一个delta点，那么认为这个点就是中心点。以此点为中心，在5×5的方向区域中计算每个方向（0,1,2,…,7）上的灰度差绝对值的和，如式(4)所示，方向的确定如图1所示。

Sd=|fd(i,j) fd(i1,j1)|+|fd(i,j) fd(i2,j2)|,d=0,1,",7 (4)

J(x)=tr(Sr) (6)

其中，Sr表示训练图像的投影特征向量的协方差；tr(Sr)表示Sr的迹；J(x)最大化的意义是：所有训练图像在X向量上投影后，得到的投影样本的总体分散度最大。

协方差矩阵Sr为

Sr=E(Y EY)(Y EY)T=E[AX E(AX)][AX E(AX)]T=

E[(A EA)X][(A EA)X]

T

(7)

则有

tr(Sr)=XT[E(A EA)T(A EA)]X (8)

令

C=E[(A EA)T(A EA)] (9)

其中，fd(i,j)为点(i,j)的灰度值。ROI的方向就是Sd取值最小即灰度变化最小的方向。

i,j)

其中，C称为图像协方差矩阵，它是n×n的非负定矩阵。设

训练图像集为A1,A2,",AM，Aj表示其中的第j幅图像，每幅图像的大小为m×n，用训练图像直接得到协方差矩阵C，即

C=

1MT

∑(Aj )(Aj (10) Mj=1

图1 ROI方向的计算

(2)若是找到一个core点和一个delta点，中心点就是core和delta连线的中点。ROI的方向为core到delta的方向。

(3)若找到两个core点，那么中心点就是两个core点连线的中点。ROI的方向为两个点的连线方向。若找到3个或以上的core点，那么中心点的位置就是与整幅图像中心点距离最接近的那个core点。

在指纹中，delta点的个数不会超过1，因此，不用考虑出现多个delta的情况。ROI的提取结果如图2所示。

其中，是所有训练图像的平均图像。

1M=∑Aj (11)

Mj=1因此，准则函数为

J(x)=XTCX (12)

使得J(x)最大的Xopt就是最佳投影向量，找出J(x)的最大值的物理意义是，图像A在Xopt方向上投影后得到的投影特征向量的总体分散程度最大。

指纹识别中只采用一个最佳投影向量是不够的，需要选择满足正交条件且极大化准则函数J(x)的一组投影向量

x1,x2,",xk，事实上，最佳的投影向量组可取图像协方差矩

阵C的对应于前k个较大特征值的正交特征向量。 3.2 特征提取和识别

对指纹图像进行特征提取就是把图像投影到特征空间，选择协方差矩阵C的前k(k≤n)个最大的特征值的特征向量xi(i=1,2,…,k)来构成特征空间。对原指纹图像去均值：

A'j=Aj j=1,2,",M) (13)

图像A'j在特征空间上的投影为

Bji=A'j×xi(i=1,2,",k)Bj=[Bj1,Bj2,",Bjk]

图2 指纹图像及ROI

(14)

Bj就是Aj的特征表示，于是根据每一类指纹来构建模

3 基于2DPCA的特征提取和识别

本文采用2DPCA来进行ROI的特征提取和识别。 3.1 2DPCA的基本原理

2DPCA[9]不是将图像矩阵转换为一维向量，而是直接采用二维图像矩阵表示人脸，然后进行特征提取，能准确地计算协方差矩阵且所需时间少。具体分析如下：设X表示n维的单位化向量，2DPCA将m×n维的图像矩阵A通过式(5)直接投影到向量X上：

Y=AX (5) 得到一个m维的列向量Y，称之为A在X方向上的投影特征向量。对于指纹识别技术来说，一个好的投影方向向量X，可以使投影图像的总体分散程度达到最大。而投影图像的总体分散度可用投影特征向量的协方差的迹来表示，即 ——216

板，存放在指纹库中以备识别。

假设T是一幅待识别的指纹图像，将T去均值：

T'=T (15)

然后将其投影到特征空间，即

Qi=T'×xi(i=1,2,",k)Q=[Q1,Q2,",Q3]

(16)

投影系数Q和各个模板之间进行距离匹配，假设Bj是指纹的一个模板，计算Q和Bj的欧基里德距离：

d(Q,Bj)=∑j Bji

i=1k

2

(17)

最后根据分类规则把待识别图像T归入某一个已知类别，通常采用的是最近邻法：如果d(Q,BL)=min[d(Q,Bj)]，那

j

么图像T属于L类。

针对PCA方法的不足之处，本文提出了基于2DPCA的

错误接收率(FAR)

指纹识别方法。若使用PCA来进行指纹特征的提取和识别，首先必须将图像矩阵转化为一维的向量，由于向量的维数一般较高，就会给随后的特征提取造成困难。如分辨率为80×100的指纹图像，转化为一维向量后维数高达8 000，导致了后续部分非常大的计算量，耗费大量的时间，而且，高维的特征向量会造成类内散布矩阵奇异性问题，从而造成计算最优鉴别矢量集的复杂度。2DPCA直接采用二维的图像矩阵来表示指纹图像，能方便地降低原始特征的维数，不仅减少了计算时间，而且很好地保留了指纹图像的二维结构信息。

相对于传统的基于特征点匹配的指纹识别法，本方法具有实现简便的优势。在传统的方法中，指纹图像的预处理环节是非常繁琐的，包括滤波、二值化、二值化去噪、细化和细化后去噪等，而基于2DPCA的方法只需进行奇异点的检测和ROI的提取，大大简化了特征提取之前的准备环节。在采集指纹时，若手指比较干燥或被采集者的指纹纹路不明显，所得到指纹图像将会出现很多断点，传统方法在提取特征点的时候会引进类似的伪特征点，造成识别的困难，而本文的方法研究的是ROI的统计特性，在识别多断点的指纹时，具有良好的鲁棒性。

4、图5中看出，相对于文献[3,7]的算法，文中所采用的2DPCA算法的识别率最高，在等概率线上，2DPCA所代表的曲线最接近原点。从保留图像信息的完整性而言，2DPCA比PCA具备更大的优势，因为2DPCA是基于图像矩阵的，用它进行图像特征提取更简单、直接，而PCA的方法要求把二维的指纹图像转化为一维向量，这样会丢失图像的二维结构信息。从算法的实现速度和运算的简易程度分析，2DPCA比其他两种方法速度更快、运算更简便，因为使用PCA会导致高维的图像向量空间，运算量非常大， 而2DPCA是以二维图像为基础的，图像的协方差矩阵是直接在原图像矩阵的基础上求得，因此，速度会比PCA快很多；相对于Jain等[3]的算法，本方法的ROI提取更为简单，而且本算法是通过矩阵的相乘来提取图像的特征信息，因此，运算更为简便。

0.500.450.400.350.300.25

0.200.150.100.05

4 实验结果与分析

在2DPCA和PCA的实验中，特征值的选取和最后的匹配结果密切相关，每个特征值对应的是一个特征向量，特征向量包含着图像的特征信息。图3分析了2DPCA和PCA中特征值和指纹ROI图像能量的对应关系。从图中可以看出，当采用2DPCA的方法时，选取前10个特征值，就已经包含了ROI图像95%以上的能量，而采用PCA方法，要获得足够的识别信息，必须选取更多的特征值，通常要选取100个以上。由此可见，2DPCA比PCA运算更为简单。

1.00

图4 Db1中的实验结果

0.950.900.850.80

采用2DPCA方法的结果

采用PCA方法的结果

错误接收率(FAR)

占总能量的比例

0.750.70

图3 特征值数目与图像能量的对应关系

图5 Db2中的实验结果

为了检验算法的有效性，采用FVC2002的Db1和Db2指纹数据库来进行实验。两个数据库各包含880幅大小为388×374像素的灰度指纹图像，图像来自110个不同的手指，每个手指采集8个样本图像。根据本文的算法，首先要提取出指纹图像的ROI，其尺寸为80×100。因此，在识别过程中，使用的是110×8枚80×100的指纹ROI图像。在Db1和Db2中，同时使用2DPCA、Wang[7]和Jain[3] 3种算法进行实验，获得的ROC曲线如图4和图5所示，其中FRR和FAR呈相反方向变化。ROC曲线表示的是FRR和FAR的关系，曲线越靠近原点，说明此方法的识别率越高，算法越有效。从图

5 结束语

本文研究了指纹的统计信息，提出一种新的指纹识别方法，此方法首先用Poincare Index法检测出奇异点，然后根据奇异点的方向切割出指纹的ROI，并用2DPCA来进行ROI的特征提取和匹配。当然本方法还存在很多限制因素。比如提取ROI时依赖于指纹图像的奇异点，然而对于一些质量较差或是没有奇异点的图像，就无法提取出ROI。另外，本方法没有在超过1 000幅指纹图像的数据库中进行实验，其通用性有待进一步的研究和探讨。

（下转第220页）

—217—

验并与传统互信息量分割方法进行了比较。由于篇幅有限，这里仅给出2个图片的实验及比较研究结果；另外，探讨了参数α对分割阈值的影响。

5.1 分割方法比较研究

从图1中的图像分割结果来看，采用经典互信息量分割方法无法完全检测到目标，或目标含有太多背景；但是，本文提出的模糊互信息量分割方法可以完全检测出目标，或检测出的目标中含背景噪声。

从表1来看，参数α越小，对图像分割最佳阈值影响越 大；但是，随着参数α的增大，对图像分割最佳阈值影响越小。特别是当α>4.0时，对模糊互信息量分割方法的影响非常小。因此，针对模糊互信息量图像分割方法，其α选取范围为(0,4.0)。在实际使用模糊互信息量图像分割时，如何从(0,4.0)选取恰当α，使得其分割效果达到最佳是当前图像分割面临的共性问题。

表1 模糊互信息量法中参数α对分割阈值的影响

Lena图 轮胎图 摄影师图细胞图

0.0112620141149

0.101221589119

0.5078124381

1.0068123369

2.00 3.00 4.00 5.0061 58 57 5625 21 16 1664 57 56 56

10.00

50.006

56 58 16 14 56 56

11 11 10 9 7

(a)电线桩原图 (b)互信息量法(t=52) (c)本文方法(t=25,α

=1.0)

6 结束语

本文在传统互信息量的基础上提出了模糊互信息量，并应用于图像分割研究，其分割性能优于基于传统互信息量的分割方法。但是，模糊互信息量分割方法中参数α的选取是当前图像分割面临的共性问题，有待进一步探讨研究。

参考文献

[1] Sezgin M. Survey over Image Thresholding Techniques and

Quantitative Performance Evaluation[J]. Journal of Electronic Image, 2004, 13(1): 145-165.

[2] Rigau J, Feixas M, Sbert M, et al. Medical Image Segmentation

Based on Mutual Information Maximization[C]//Proc. of MICCAI’04. Berlin, Germany: Springer-Verlag, 2004: 135-142. [3] Kim J. A Nonparametric Statistical Method for Image Segmen-

tation Using Information Theory and Curve Evolution[J]. IEEE Trans. on Image Process, 2005, 14(10): 1486-1502.

[4] 吕庆文, 陈武凡. 基于互信息量的图像分割[J]. 计算机学报,

(d)环状原图 (e)互信息量法(t=77) (f)本文方法(t=185,α=2.0)

图1 实验图片及分割结果

5.2 参数选择对阈值的影响

为了探讨模糊互信息分割方法中参数α对分割阈值的影响，采用4个典型图片来进行实验，如图2所示，得出参数α选取的大致范围。

(a)Lena图 (b)轮胎图

2006, 29(2): 297-300.

[5] Pal S K, King R R, Hashion A A. Automatic Gray Level

Thresholding Through Index of Fuzziness and Entropy[J]. Pattern Recognition, 1983, 1(1): 141-146.

[6] Bezdek J C. Pattern Recognition with Fuzzy Objective Function

Algorithms[M]. New York, USA: Plenum Press, 1981.

(c)摄影师图 (d)细胞图

[7] Maes F. Multimodality Image Registration by Maximization of

Mutual Information[J]. IEEE Trans. on Medical Image, 1997, 16(2): 187-198.

图2 4个典型图片

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

（上接第217页）

参考文献

[1] 刘忠伟. 利用局部累加直方图进行彩色图像检索[J]. 中国图象

图形学报, 1998, 3(7): 533-537.

[6] Anil K. Combining Multiple Matchers for a High Security

Fingerprint Verification System[J]. Pattern Recognition Letters, 1999, 20(11-13): 1371-1379.

[7] Wang Yongxu. A Fingerprint Recognition Algorithm Based on

Principal Component Analysis[C]//Proc. of IEEE TENCON’06. Hong Kong, China: [s. n.], 2006.

[8] Kawagoe M, Tojo A, Fingerprint Pattern Classification[J]. Pattern

Recognition, 1984, 17(3): 295-303.

[9] Jian Yang. From Image Vector to Matrix: A Straightforward Image

Projection Technique——IMPCA vs PCA[J]. Pattern Recognition, 2002, 35(9): 1997-1999.

[2] Anil K. A Multichannel Approach to Fingerprint Classification[J].

IEEE Trans. on PAMI, 1999, 21(4): 348-359.

[3] Jain A K, Prabhakar S. Filterbank-based Fingerprint Matching[J].

IEEE Tans. on Image Processing, 2000, 9(5): 846-859.

[4] Jain A, Ross A. Fingerprint Matching Using Minutiae and Texture

Features[C]//Proc. of ICIP’01. New York, USA: IEEE Press, 2001. [5] Ranade S, Rosenfeld A. Point Pattern Matching by Relaxation[J].

Pattern Recognition, 1980, 12(5): 269-275.

——220

本文来源：https://www.bwwdw.com/article/b9q4.html