指纹识别系统—计算机的设计.doc

1、摘 要由于指纹所具有的唯一性和不变性，以及指纹识别技术具有很高的可行性和实用性，指纹识别成为目前最流行、最可靠的个人身份认证技术之一。本论文对指纹图像基于小波变换的各种处理进行了分析、总结。图像处理包括基于小波变换的指纹图像滤波处理和基于小波的指纹图像增强处理。同时介绍指纹图像的预处理：目的是去除指纹图像中的噪音，将其转化为一幅清晰的点线图，便于提取正确的指纹特征。它分四步进行，即灰度滤波、二值化、二值去噪、细化。本文针对基于点模式匹配的指纹匹配算法速度较慢的现状,设计了一种新的指纹匹配方法,即利用纹线匹配技术来寻找基准点对的指纹匹配算法.实验证明,该算法匹配速度很快,误识率低,准确性高,并具

2、有图象旋转平移不变性.对面积适中的指纹图象,匹配结果可以满足在线应用的需要.该算法有望发展成为一种实用、有效的指纹匹配技术.关键词:指纹图像增强，细化，特征提取，特征匹配，二值化，指纹图像滤波AbstractDue to the uniqueness and invariability of fingerprints, and better feasibility and utility of fingerprint verification technology, the automated identification based on fingerprints is becoming a

3、n attractive alternative to the traditional methods of identification. In this paper, we have analyzed the image processing of fingerprint images which are based on wavelets transforms. The image process is mainly composed of two sections, which are fingerprint filtering process and fingerprint the

4、enhancement which are based on wavelets transform. At the same time, there to be introduce the fingerprint preprocess. The fingerprint preprocess is to remove noise and it will translate into a plain point-line image, which is convenient for extracting the perfect fingerprint character. Because the

5、fingerprint matching algorithm based on point pattern matching is not quick enough, a new fingerprint matching algorithm is presented here. Lines matching technique is used in the algorithm for seeking pairs of reference minutiae. Through experiments, the algorithm is proved accurate, quick, and inv

6、ariable to translation and rotation of images. According to fingerprint images of moderate sizes, the needs of online application can be met. The algorithm is expected to be a convenient and effective fingerprint matching technique. Key words：fingerprint image enhancement ，feature extraction, featur

7、e fingerprint image compression thinning, matching,1 绪 论1.1、指纹自动识别技术的历史、现状和未来自动指纹识别技术是一种有着广泛应用背景的身份鉴定技术。本论文主要介绍了自动指纹识别系统的指纹图像处理和指纹匹配两部分。指纹识别的基本原理为：采用细节点坐标模型来做细节匹配，即对指纹的脊线末梢和指纹的脊线分支点提取特征点来鉴定指纹。具体的自动指纹识别系统框图见图1-1。 图1-1 自动指纹识别系统框图考古证实，公元前7000年到6000 年以前，古叙利亚和中国，指纹作为身份鉴别己经开始应用。考古发现，在这个时代，一些粘土陶器上留有陶艺匠人的指纹

8、，中国的一些文件上印有起草者的大拇指指纹，在 Jercho 的古城市的房屋留有砖匠一对大拇指指纹的印记等。虽然指纹的一些特征己经被人们认识和接受而不能证明，但指纹己广泛应用社会的各个方面。19世纪初，科学研究发现了至今仍然承认的指纹的两个重要特征：一是两个不同手指的指纹脊线的式样(ridge pattern)不同，另外一个是指纹脊线的式样终生不改变。这个研究成果使得指纹在犯罪鉴别中得以正式应用。(主要代表性的事件有：1896年阿根廷首次应用，然后是1901年的苏格兰，20世纪初其他国家也相继应用到犯罪鉴别中) 20世纪 60年代，由于计算机可以有效的处理图形，人们开始着手研究利用计算机来处理指

9、纹。从那时起，自动指纹识别系统 AFIS在法律实施方而的研究和应用在世界许多国家展开。20世纪80年代，个人电脑、光学扫描这两项技术的革新，使得它们作为指纹取像的工具成为现实，从而使指纹识别可以在其他领域中得以应用，比如代替IC卡。现在(90 年代后期)，低价位取像设备的引入及其飞速发展，可靠的比对算法的发现为个人身份识别应用的增长提供了舞台。对指纹识别技术来说，被广泛接受意味着在影响千万人的日常生活的各个地方使用。通过取代个人识别码和口令，指纹识别技术可以阻止非授权的访问，可以防止盗用 ATM、蜂窝电话、智能卡、桌面 PC、工作站及其计算机网络；在通过电话、网络进行的金融交易时进行身份认证；

10、在建筑物或工作场所，指纹识别技术可以取代钥匙、证件、图章和卡阅读器。然而，必须指出的是，指纹识别技术到目前在国内乃至世界上仍未普及，其主要原因是：(1)速度慢，目前一般系统辨别时需要数秒钟甚至更长；(2)价格高，系统过于昂贵；(3)性能差，错误拒识率（False Reject Rate：FRR）和错误接受率（FalseAccepted Rate：FAR）过高。因此，对快速而精确的指纹识别方法的研究有着重要的科学意义和应用价值。一般来说，一个指纹自动识别系统(Automated Fingerprint Identification System：AFIS)主要包括指纹图像提取子系统、指纹识别子系

11、统和指纹压缩存储子系统几个部分组成。其中，指纹识别子系统是整个系统的核心部分，包括指纹图象处理、特征提取、指纹分类及匹配等四部分。本文将主要对指纹图象处理和特征提取的部分算法加以讨论和研究。1.2、本文的主要研究工作本文主要的研究内容是在VC+环境下实现指纹图像的小波变换和预处理，同时还研究指纹特征提取及匹配算法问题。全文对小波的基本理论进行了简要介绍，并对指纹图像小波变换的实现、基于小波变换频率特性的应用指纹图像滤波处理、指纹图像增强处理的理论以及VC+编程实现进行了比较深入地研究，并列出了实现程序。此外，本文还在对指纹图像的预处理方法进行分析和研究的基础上，提出了一套指纹预处理算法，采用该

12、算法可以得到清晰的指纹点线图，效果较为突出。第2章 VC+环境下小波变换及指纹图像处理2.1 小波的基本理论2.1.1 小波分析图像处理小波变换是最近20多年来发展起来的用于信号分析和信号处理的一种新的域变换技术。由于小波变换是把信号在不同尺度上进行小波展开，它更适合于处理突变信号和非平稳信号。小波变换技术已受到人们极大的重视。Fourier变换是数学分析中最古老的学科之一，即一个信号可表示成一系列正弦和余弦函数之和。但Fourier变换只有频率分辨率而没有时间分辨率，这就意味我们可以确定信号中包含的所有频率，但不能确定具有这些频率的信号出现在什么时候，只适宜处理平稳信号。在非平稳信号的分析中

13、，人们希望存在一种变换函数，能够满足在高频信号中，有相对小的时间间隔以便给出较高的精度，而在低频信号中能够以相对较宽的时间间隔给出完全的信息。小波是有限宽度的基函数，这些基函数不仅在频率上而且在位置上是变换的，它们是有限宽度的波。基于它们的变换称为小波变换。小波变换具有时间一频率自动伸缩能力，这种能力可以在任何希望的频率范围上产生频谱信息。小波理论的提出可追溯到1910年Haar提出的规范正交基。1975年Caldern发表了接近小波级数展开的再生公式，1981年Stromberg对Harr系进行了改进，证明了小波函数的存在性。1984年法国地理学家Morlet在分析地震波的局部性质时引入了小

14、波的概念，继而Y. Meyer于1986年创造性地构造出了具有一定衰减性的二进小波函数，扫除了人们对于小波函数是否存在的疑虑，从而真正掀起了小波研究的热潮。同年，S. Mallat将多分辨率分析的概念引入了小波分析及小波函数的构造中，并将小波函数的构造统一于多分辨率分析的框架之下，同时，Mallat提出的快速算法使小波变换从理论研究进一步走向各种应用领域。1988年Daubechies构造出了具有紧支集的正交小波集。1989年，Goifman, Meyer和Quake等引入了小波包。1990年，崔锦泰和王建忠构造了基于样条函数的单正交小波函数。1992年，Coher, Daubechies,

15、Feauveau提出了具有紧支撑的双正交小波基。至此，小波理论系统的构架得以建立，它为原来信号处理领域里各自独立的方法，如多尺度分析、拉普拉斯金字塔、精确重建滤波器组等提供了一个统一的理论框架。随着理论研究的不断深入和应用领域的不断扩展，小波分析越来越显示出它的独特魅力。1、小波概念小波变换的定义是把某一被称为基本小波(也叫母小波mother wavelet)的函数做位移后，再在不同尺度下与待分析的信号做内积: (2.2)等效的频域表示是: (2.3)式 中和分别是和的傅里叶变换。小波变换有以下特点:1) 有多分辨率(multi-resolution)，也叫多尺度(multi-scale)的特

16、点，可以由粗及细地逐步观察信号。2) 可以看成用基本频率特性为的带通滤波器在不同尺度下对信号做滤波。由于傅里叶变换的尺度特性可知，这组滤波器具有品质因数恒定，即相对带宽(带宽与中心频率之比)恒定的特点。注意，越大相对频率越低。3) 适当地选择基小波，使在时域上为有限支撑，在频域上也比较集中，就可以使在时、频域都具有表征信号局部特征的能力， 因此有利于检测信号的瞬态或奇异点。正如上所述，小波分析的一个主要优点就是能够分析信号的局部特征。比如说，采用小波分析可以发现叠加在一个非常规范的正弦信号上的一个非常小的畸变信号的出现时间。传统的傅里叶变换只能得到平坦的频谱上的两个尖峰。利用小波分析可以非常准

17、确地分析出信号在什么时刻发生畸变。小波分析可以检测出许多其他分析方法忽略的信号特性，例如，信号的趋势、信号的高阶不连续点、自相似特性。小波分析还能以非常小的失真度实现对信号的压缩与消噪，它在图像数据压缩方面的潜力已经得到确认。在二维情况下，小波分析除了“显微”能力外还具有“极化”能力(即方向选择性)，因而引人注意。2、小波在图像处理中的应用图像处理是小波分析应用的重要领域，近年来小波分析已被证明是进行图像处理强有力的工具之一，由于小波分析技术可以将信号或图像分层次按小波基展开，并且可以根据图像的性质及事先给定的图像处理要求确定到底要展开到哪一级为止，从而不仅能有效地控制计算量，满足实时处理的需

18、要，而且可以方便地实现通常由子带编码技术实现的累进编码(即采取逐步浮现的方式传送多媒体图像)。同时，小波变换具有放大、缩小和平移的功能，能够很方便地产生各种分辨率的图像，从而适合于不同分辨率图像的处理。因此，近十年来，基于小波变换的图像压缩算法得到了很大发展，取得了许多重要的成果，而且越来越成为该领域研究和应用的热点。2.1.2 连续小波变换 1、定义对任意信号，f(t)的连续小波变换定义是: (2.1)a为尺度因子，b为平移因子。如果满足容许条件; ，则称为容许小波，可由恢复原信号 (2.2)其中， 根 据Parseval 恒等式： (2.3)可见 f(t)的连续小波变换就相当于f(t)通过

19、传递函数为的系统的输 出 。2、特性在介绍小波特性之前先给出窗函数的概念。（1） 定义 :非平凡函数L2(R)，称为一个窗函数.如果也是属于L2(R)的，一个窗函数的的中心t2与半径，定义分别是: (2.4) (2.5)假定与都是窗函数，窗函数的中心与半径分别用t2与半径给出，那么函数是中心在b+at*且半径等于a的一个窗函数，因此由(2.1)式可知连续小波积分给出了信号f(t)具有时间窗b十at*-a,b+at*+a 的局部信息;窗函数的中心与半径分别用w*与表示，则由(2.5)式可知除了一个倍数与一个线性相位移。外，连续小波变换还给出了f的一个具有频率窗的局部信息.由以上分析可知当尺度a变

20、化时，对应一系列带通系统，并且可以得出以下结论:（1）信号f(t)的连续小波变换就是一系列带通滤波器对f(t)滤波后的输出，a反映了带通滤波器的带宽和中心频率，b则为滤波输出的时间参数。（2）a变化，带通滤波器的带宽和中心频率也变化。a变小，中心频率变大，带宽变宽:a变大，中心频率变小，带宽变窄f(t)通过带通滤波器滤波，对分析信号的局部特性很有价值。信号变化缓慢的地方，主要为低频成份，频率范围也较窄，此时小波变换带通滤波器应相当于a大的地方:反之，信号发生突变的地方，主要是高频成份，频率范围也较宽，小波变换的带通滤波器相当于a小的情况。即伸缩因子a有大到小变化，滤波的范围也从低频到高频变化。

21、2.1.3 离散小波变换 将连续小波变换的尺度a离散化按照2的幕级数进行，和时间位移b进行离散化，就得到离散小波变换。通常a的离散化按照2的幂级数进行，即：,b的离散化为。所以，信号f(t)的离散小波变换(DWT)定义为: (2.6) (2.7)其中取离散正交小波基，是尺度j下的f(t)的离散小波变换，离散小波变换具有以下的特性;1、是小波函数以在尺度上的伸缩和时域上的平移得到的。随j的变化，在频域上处于不同的频段，随k的变化，在时域上处于不同的时段，所以离散小波变换是一种信号的时间一频率分析;2 、尺度j减小时, 在时域上伸展，在频域上收缩，中心频率降低变换的时域分辨率降低，频域分辨率提高;

22、尺度j增大时， 在时域上收缩，在频域上伸展，中心频率升高，变换的时域分辨率提高，分辨率的时频域分析。频域分辨率降低。所以，离散小波变换是一种多分辨率的时频域分析。2.1.4 指纹图像二维小波变换概念及算法1、概念：一维信号的离散小波变换很容易推广到二维的情况。假设是一个一维的尺度函数，是相应的小波函数，那么，可以得到一个二维小波变换的基础函数：， 2、算法 图像可以看作是二维的矩阵，一般假设图像矩阵的大小为NN，且有N2n（n为非负的整数）。那么每次小波变换后，图像便分解为4个大小为原来尺寸的子块频带区域，如图2-2所示，分别包含了相应频带的小波系数，相当于在水平方向和竖直方向上进行隔点采样。

23、进行下一层小波变换时，变换数据集中在LL频带上，图2-3所示为3层小波变换的系数分布。 等式（2.11）至等式（2.14）说明了图像小波变换的数学原型。LL频带，该频带保持了原始图像内容信息，图像的能量集中于此频带： (2.11) HL频带，该频带保持了图像水平方向上的高频边缘信息： （2.12） LH频带，该频带保持了图像竖直方向上的高频边缘信息： （2.13） HH频带，该频带保持了图像在对角线方向上的高频信息： (2.14)其中表示内积运算。图2-2 一次离散小波变换后的频率分布 图2-3 3层小波变换后的频率分布2.1.5 二维小波变换编程实现及运行结果 下面将详细地按编程步骤对图像小

24、波变换地实现进行分析。（1）函数描述DWT_Once完成一次图像的小波变换（2）函数参数short *spOriginData：二维指针，指向原始的图像数据short *spTransData0：小波变换系数，存放一次水平变换后的小波系数short *spTransData1：小波变换系数，存放一次数值变换后的小波系数int nHeight：图像属性参数，数值为原始图像的高度值int nHeight_H：图像属性参数，数值为原始图像高度值的一半int nWidth：图像属性参数，数值为原始图像的宽度值int nWidth_H：图像属性参数，数值为原始图像宽度值的一半int layer：小波变换

25、的层数，数值为1层float fRadius：小波变换因子，在调用时候已指定数值为1.414（3）函数代码void CWvltTrans:DWT_Once(short* spOriginData, short* spTransData0, short* spTransData1, int nHeight, int nHeight_H, int nWidth, int nWidth_H, int layer, float fRadius)int Trans_W, /图像扫描线控制：横坐标Trans_H, /图像扫描线控制：纵坐标Trans_M, /图像矩阵的横坐标Trans_N; /图像矩阵的纵

26、坐标short Trans_Coeff0; /小波变换系数signed short Trans_Coeff1;fRadius=1.414; /变换滤波系数 /本模块完成变换系数的赋值采样 /行变换,第一次（layer=1时）时nHeight即为原始图像的高度值 for(Trans_H=0; Trans_HnHeight; Trans_H+) if(layer = 1) /layer=1时，nWidth_H为原始图像宽度值的一半for(Trans_N=0; Trans_NnWidth_H; Trans_N+) Trans_W=Trans_N 1)for(Trans_N=0; Trans_NnWi

27、dth_H; Trans_N+)Trans_W=Trans_N1;spTransData0Trans_HTrans_N = spTransData1Trans_HTrans_W;spTransData0Trans_HnWidth_H+Trans_N= spTransData1Trans_HTrans_W+1;for(Trans_H=0; Trans_HnHeight; Trans_H+)for(Trans_N=0; Trans_N1); /逻辑非操作后数值加1Trans_Coeff1=Trans_Coeff1+1; /系数预测spTransData0Trans_HnWidth_H+Trans_

28、N= spTransData0Trans_HnWidth_H+Trans_N+Trans_Coeff1; /完成一个偶系数的边界处理Trans_Coeff1 = (spTransData0Trans_HnWidth_H-1+spTransData0Trans_HnWidth_H-2)1);Trans_Coeff1=Trans_Coeff1+1;spTransData0Trans_HnWidth-1= spTransData0Trans_HnWidth-1+Trans_Coeff1; /完成一个奇系数的边界处理Trans_Coeff0= (spTransData0Trans_HnWidth_H+

29、spTransData0Trans_HnWidth_H+1)2);spTransData0Trans_H0 = spTransData0Trans_H0+Trans_Coeff0; /提升，整数到整数的变换for(Trans_N=1; Trans_N2);spTransData0Trans_HTrans_N= spTransData0Trans_HTrans_N+Trans_Coeff0; /水平方向的变换结束 /竖直方向的变换开始，数据源未水平变换后的小波系数for(Trans_M=0; Trans_MnHeight; Trans_M+)for(Trans_N=0; Trans_NnWidt

30、h_H; Trans_N+)spTransData0Trans_MTrans_N*=fRadius;spTransData0Trans_MTrans_N+nWidth_H/=fRadius;/行提升后的数据在spTransData0中，spTransData0中的数据自然奇偶有序for(Trans_N=0; Trans_NnWidth_H; Trans_N+) /列变换for(Trans_M=0; Trans_MnHeight_H; Trans_M+)Trans_H =Trans_M1; /频带LL部分spTransData1Trans_MTrans_N = spTransData0Trans

31、_HTrans_N; /频带HL部分spTransData1nHeight_H+Trans_MTrans_N = spTransData0Trans_H+1Trans_N; /频带LH部分spTransData1Trans_MnWidth_H+Trans_N = spTransData0Trans_HnWidth_H+Trans_N; /频带HH部分spTransData1nHeight_H+Trans_MnWidth_H+Trans_N = spTransData0Trans_H+1nWidth_H+Trans_N; /第一次提升奇数坐标系数for(Trans_M=0; Trans_M1);

32、Trans_Coeff1=Trans_Coeff1+1;spTransData1nHeight_H+Trans_MTrans_N = spTransData1nHeight_H+Trans_MTrans_N+Trans_Coeff1;Trans_Coeff1= (spTransData1Trans_MnWidth_H+Trans_N+spTransData1Trans_M+1nWidth_H+Trans_N)1);Trans_Coeff1=Trans_Coeff1+1;spTransData1nHeight_H+Trans_MnWidth_H+Trans_N = spTransData1nHe

33、ight_H+Trans_MnWidth_H+Trans_N+Trans_Coeff1;Trans_Coeff1 = (spTransData1nHeight_H-1Trans_N+spTransData1nHeight_H-2Trans_N)1);Trans_Coeff1=Trans_Coeff1+1;spTransData1nHeight-1Trans_N = spTransData1nHeight-1Trans_N+Trans_Coeff1;Trans_Coeff1 = (spTransData1nHeight_H-1nWidth_H+Trans_N+spTransData1nHeigh

34、t_H-2nWidth_H+Trans_N)1);Trans_Coeff1=Trans_Coeff1+1; /边界处理spTransData1nHeight-1nWidth_H+Trans_N = spTransData1nHeight-1nWidth_H+Trans_N+Trans_Coeff1;Trans_Coeff0 = (spTransData1nHeight_HTrans_N+spTransData1nHeight_H+1Trans_N)2);spTransData10Trans_N = spTransData10Trans_N+Trans_Coeff0;Trans_Coeff0 =

35、 (spTransData1nHeight_HnWidth_H+Trans_N+spTransData1nHeight_H+1nWidth_H+Trans_N)2); /边界处理spTransData10nWidth_H+Trans_N = spTransData10nWidth_H+Trans_N+Trans_Coeff0; /第一次提升偶数坐标系数for(Trans_M=1; Trans_M2);spTransData1Trans_MTrans_N = spTransData1Trans_MTrans_N+Trans_Coeff0;Trans_Coeff0 = (spTransData1n

36、Height_H+Trans_MnWidth_H+Trans_N+spTransData1nHeight_H+Trans_M-1nWidth_H+Trans_N)2);spTransData1Trans_MnWidth_H+Trans_N = spTransData1Trans_MnWidth_H+Trans_N+Trans_Coeff0;/存放小波系数，LL频带的系数进行幅值增强处理，其高频频带的系数则削弱其幅值for(Trans_N=0; Trans_NnWidth; Trans_N+)for(Trans_M=0; Trans_MbfOffBits;unsigned long biHeig

37、ht = lpBitmapInfoHeader-biHeight;unsigned long biWidth = lpBitmapInfoHeader-biWidth;unsigned long biAlign = (biWidth*3+3)/4 *4;unsigned long bmSize = biHeight * biAlign;if(m_pTransfered=NULL)m_pTransfered=(unsigned char*) malloc (bmSize);if(m_pTransfered=NULL)return; /图像矩阵坐标与像素数据int x,y,cur;unsigned char tempR, tempG, tempB;float fTempBufforDisp;short MaxPixVal,MinPixVal,Diff;short *spOriginData, *spTransData0, *spTransData1; /分配图像小波变换所用的数据空间spOriginData = new short* biHeight;spTransData0 = new short* biHeight;spTransData1 = new short* biHeight;m_WvltCoeff= n