1、科技创新指纹识别算法研究 东华理工大学第十届大学生科技创新基金项目 作品名称： 指纹识别算法研究 院系全称： 核工程与地球物理学院 姓名： 温志平 洪运 柏植 张皓 王青卿 目 录摘 要第1章 绪论4 1.1 研究背景和意义4 1.2 指纹识别技术4 1.2.1 指纹识别技术发展现状6 1.2.2 指纹识别技术特点7 1.3 本论文的工作8第2章 指纹图像的分割 9 2.1指纹图像分割概述9 2.2均值方差法11 2.3 仿真结果与结论11第3章 指纹图像的细化 13 3.1 指纹图像细化的预处理13 3.2 指纹图像细化方法介绍13 3.3仿真结果与结论15第4章 指纹图像的特征提取 17
2、4.1 指纹图像特征提取概述18 4.2 特征提取和去伪特征18 4.3 仿真实验与结论19第5章 指纹图像的匹配 20 5.1 指纹图像匹配方法20 5.2 本论文匹配方法介绍21第6章 总结23参考文献25摘要随着信息时代的发展, 自动指纹识别技术已经广泛地应用于公安、海关、银行、网络安全等需要进行身份识别领域。本文概述了自动指纹识别系统的研究现状和指纹识别系统的算法流程，并在此基础上重点研究了指纹图像的分割算法和指纹图像细化算法。首先，本文系统介绍了指纹识别的研究意义及现状，并对指纹识别原理及实现过程做了系统介绍。其次，针对在指纹采集过程中存在着大量的低质量指纹图像，影响指纹识别系统的识
3、别率的问题，本文对指纹图像的分割等预处理作了较为深入的研究，采用了均值方差的指纹图像分割算法，仿真结果表明，该方法有效地改善了指纹图像的质量。此外，对指纹图像的细化作了深入的研究，使用的细化模板虽然数量较多，计算时间比较长，但对于像素的处理很到位，使得毛刺比较少，保持原图像的基本结构特性，还最大地保留了细节特征。最后，研究了指纹识别过程中特征的提取方法，针对细节点提取过程中存在伪特征点的问题，本文采用了一种消除伪特征点的算法。仿真结果表明，这种算法可以有效的去除伪特征点。第1章 绪论1.1 研究的背景及意义科学技术的迅猛发展为人类的生产生活带来了极大的便利，大大地推动了现在社会的进步和发展。在
4、网络化时代的今天，我们每个人都拥有大量的认证密码，比如开机密码、邮箱密码、银行密码、论坛登陆密码等等；并配备了各种钥匙，如门锁钥匙，汽车钥匙，保险柜钥匙等。这些都是传统的安全系统所采用的方式，随着社会的发展，其安全性越来越脆弱。而我们的生活随时都需要进行个人身份的确认和权限的认定。指纹特征是人终生不变的特征之一，而且不同人的指纹特征相同的可能性几乎为零。人体指纹含有天然的密码信息，其具有作为密码信息必须具备的三个重要性质：广泛性，指每一个正常人都有指纹。唯一性，指每一个人的指纹都不同。终生不变性，指非意外事故指纹终身不变。因此，指纹识别技术，作为一种可靠的生物识别技术，受到了人们的重视。尽管人
5、们已经对自动指纹识别技术作了深入广泛的研究，指纹识别技术也获得了不少应用，但是指纹识别的应用在目前并没有获得普及，这主要是因为指纹识别在识别准确性和识别速度方面还远远不能满足很多实际应用的要求。这就要求研究指纹识别环节中若干问题，这对于问题的解决很有意义。1.2 指纹识别技术相对于其它生物识别认证技术而言，自动指纹识别是一种更为理想的身份确认技术，因为指纹相对于其它几种生物特征具有以下一些独特的性质：(1)互异性；世界上两个指纹完全相同的概率小于10-9，几乎为零。(2)不变性；人的指纹特征不随年龄的增长和胖瘦或其他情况的改变而改变。(3)具有和主体永不分离性；这样对主体身份的识别更具真实性。
6、(4)指纹的使用比起其它证卡来说更快捷、安全准确、无干扰，可实现快速登录注册。(5)一个人的十指指纹皆不相同，这样可以方便地利用多个指纹构成多重口令，提高系统的安全性。(6)指纹识别中使用的模板并非最初的指纹图，而是由指纹图中提取的关键特征，这样使系统对模板库的存储量较小。另外，对输入的指纹图提取关键特征后，可以大大减少网络传输的负担，便于实现异地确认，支持计算机的网络功能。1.2.1指纹识别技术发展现状指纹识别算法的研究方向主要分为：基于图像的识别算法和基于特征的识别算法。基于图像的识别算法认为，指纹图像的频域和空域信息可以用来唯一表示并识别不同的指纹。它是一种使用全局信息进行识别的方法，例
7、如使用指纹图像的Fourier频谱来表示和识别指纹。这类算法的问题在于图像特征难以定义和匹配，因此算法的拒识率和误识率较高。基于特征的指纹识别算法是找到并比对指纹的特征。指纹特征的复杂度足以提供用于鉴别的足够特征。目前大多数的自动指纹识别系统使用的都是这类算法。指纹特征多种多样，有特征点、奇异点、域方向图、脊线数目，甚至脊线线型等。对应的匹配方法可以分为：基于点模式的匹配，基于脊线的匹配，基于纹理的匹配以及多种细节特征混合的匹配方法。大多数基于特征的识别算法专注于脊线上的末梢点和分叉点，该方法根据各个特征点的位置和方向来表示和区分指纹，从而使指纹识别问题转化为判断两个特征点集间的最大相似度(最
8、大重合度)的问题。提取该细节特征有多种方法：基于灰度指纹图像直接提取，基于二值图像的特征提取，基于细化图像的特征提取。目前许多公司和研究机构在指纹识别技术领域都取得了突破性的进展，推出许多指纹识别与传统IT技术完美结合的应用产品，这些产品已经被越来越多的用户所认可。中科院自动化所智能生物信怠系统研究组和北京数字指通软件技术有限公司对自动指纹识别技术进行了长期的理论研究和应用系统开发，指纹图像的识别准确率和识别速度已达到国际先进水平。另外，一些公司和机构结合社会应用的实际需求，开发了各种类型的具有独立知识产权的嵌入式指纹识别模块、指纹应用系统软件等，用户反映良好。指纹识别技术多用于对安全性要求比
9、较高的领域，另在商务移动办公领域颇其建树的富士通、三星及IBM等国际知名品牌都拥有技术与应用较为成熟的指纹识别系统。与国外相比，我国在自动指纹识别技术的研究水平上还存在一定的差距。主要表现在：(1)指纹录入设备的质量还不太过关；(2)自动指纹识别算法研究水平还有待提高，在应用上的表现为产品适应性和易用性较差，对干、湿一些的指纹往往不能正确区别，对指纹录入时的旋转、平移比较敏感。1.2.2指纹识别技术特点指纹特征是人终生不变的特征之一，而且不同人的指纹特征相同的可能性几乎为零。人体指纹含有天然的密码信息，其具有作为密码信息必须具备的四个重要性质：广泛性，指每一个正常的人都有指纹。唯一性，指每一个
10、人的指纹都不同。指纹的细节由细微纹点和纹线的起点、终点、分叉等组成。正是这些无穷无尽的细节特征组合构成了指纹的唯一性事实上，甚至包括双胞胎，世界上两个指纹相同的概率小于1109，几乎为零，这就构成了指纹的第一大特点。终生不变性，指纹终身不变即指纹的图案永远不会改变，从人的出现到死后的分解为止(除非指纹受到伤害)。指纹与主体的不可分离性，即指纹不存在丢失、遗忘、被窃取的可能。指纹的使用比起其它证卡来说更快捷、安全、准确、无干扰，可实现快速登录注册，系统兼容性好，也就是说可以独立或者通过联网构成系统并且很容易并入各类证卡和定义识别系统中。因此，指纹识别技术的应用范围极广。在实际应用中，有相当一部分
11、要处理的指纹图像的质量是比较差的。指纹识别系统主要包括4部分：指纹图像采集，指纹图像预处理，指纹特征提取和指纹特征匹配。论文涉及指纹的图像分割、细化和匹配。就现有文献和产品来看，对低质量的指纹图像的处理效果还远不能令人满意。要想使设计的细节特征提取算法能够对低质量指纹图像也能可靠工作，目前看来还是一件难度很大的事情。对于质量很差的图像，如果不经过特殊的增强处理，是很难正确地进行特征提取的。指纹匹配算法的性能主要决定于所提取到的特征点的数目、位置和相互关系的可靠性。要想设计一个对较多真正特征点缺失、较多伪特征点出现和较大形变均不敏感的指纹匹配算法，也是一件十分困难的事。计算复杂性是自动指纹识别技
12、术中一个重要的研究课题。实际应用要求最好自动指纹识别系统能对识别任务实时做出响应，而让指纹匹配算法同时达到高速度和高准确率也是一个难题。1.3本论文的内容及安排本文以研究指纹识别中指纹图像分割、细化、特征提取、匹配等若干问题为研究主体，针对指纹识别技术中分割、细化和匹配进行了仿真和修正。其中分割部分采用了方差均值的方法，细化选取了一种伪特征较少的模板，匹配时以分叉点和端点信息进行匹配。具体的章节和各章的内容安排如下：第1章：在介绍本论文的研究意义，在指纹识别技术的现状和特点的基础上，确定了本文所做的主要工作。第2章：为后续的研究工作奠定基础，本章介绍了均值方差的基础知识和基本理论以及仿真中具体
13、的分割运用算法。第3章：介绍了指纹图像细化的方法并仿真得到结果。第4章：主要介绍了指纹图像细化后的特征提取，需要哪些特征，去除哪些伪特征，以方便和正确地进行匹配工作。第5章：介绍了指纹图像匹配的概念、匹配问题的困难所在和常用方法，给出了一种修改基础上验证用的匹配方法。第6章：总结本文所取得的一些研究成果，并对课题发展进行了展望。第2章 指纹图像的分割2.1 指纹图像分割概述在指纹识别系统中，指纹图像分割是图像预处理的一部分。指纹分割的最基本的依据是图像某些特征和特征集合。图像特征是指纹图像的固有属性,如灰度值,邻域关系,纹线的扭曲程度等。特征集合则是几种的结合。通过提取图像特征,可将原始图像映
14、射到特征空间,使图像特征在特征空间中呈现一定的分布。因此根据以上的的灰度值领域关系，纹线的扭曲程度，指纹图像分割大致分为三类：基于像素的图像分割，基于块特征的图像分割以及基于全局的图像分割。基于像素的指纹图像分割中目前流行多尺度小波变换和阈值法。小波变换和傅里叶变换的出发点都是将信号表示成基函数的线性组合。所不同的是傅里叶变换采用时间属于(一，+)的谐波函数作为基函数，而小波变换的基函数是具有紧支集的母函数 (t)，通过对母函数 (t)进行伸缩和平移得到一个小波序列： ； 式中为伸缩因子，b为平移因子。对于任意函数的连续小波变换：公式（1）为变换公式，公式（2）为重构公式。 （1） （2）计算
15、机中的图像信息是以离散信号形式存放的，在信号处理中，特别是在数字信号处理和数值计算等方面，为了计算机实现的方便，连续小波必须进行离散化，而最基本的离散化方法就是二进制离散，一般将这种经过离散化的小波及其变换叫做二进小波和二进变换。小波变换的特点是压缩比高，压缩速度快，压缩后能保持信号与图象的特征不变，且在传递中可以抗干扰。在指纹识别识别中使用小波变换有助于噪声的滤除以及有利于检测奇异点。但是小波变换的明显缺点是它计算复杂，计算效果也取决于函数的选择。另一种阈值分割就是简单地用一个或几个阈值将图像的灰度直方图分成几个类，认为图像中灰度在同一个灰度类内的像素属同一物体。它是图像分割中最基本的方法。
16、其原理是先定一个阈值，大于此值为1，小于则认为为0；多阀值则可以利用多维函数。此原理在匹配中也可以运用。其优点是计算简单，仅需比较灰度值即可；运算效率较高，速度快；它的缺陷在于仅考虑图像的灰度信息，而忽略了图像的空间信息，对于图像中不存在明显灰度差异或各物体的灰度值范围有较大熏叠的图像分割问题难以得到准确的结果。代表块特征的指纹图像分割目前研究趋势为多种块基本特征如灰度均值、块灰度方差、块方向图等综合运用和重新定义块特征。其中块指的是将图像分个成一个个小的图像块。图像均值就是对每一个单位块的灰度值取均值，方差则反映该块中各点与均值的偏差性、方向。这可以很好的反映纹理的变化趋势。一般来说，常见的
17、方向场的计算分为掩模法和公式法两大类。LinHong等人开发的基于最小均方估计算法，即公式法。 （1） （2）它是利用正交坐标系下，原点到它们组成的坐标点的有向线段与X的正半轴的夹角可来表示该子块的块方向。这种方法最大的优点是易实现，很好体现出纹理，但缺点是对于变化太快的部分出错。此方法的实现是利用方向滤波器。基于全局的图像分割则是根据情况特别是某些特殊场合的利用，如残缺指纹。全局的图像分割可以是人工选定几个特定点后再根据全局的特点来处理，此法也可运用于匹配。基于全局的指纹识别仍处于实验室探索阶段,应用领域中尚不广泛。2.2 均值方差法在图像分割概述中，已经提到基于块特征的指纹图像分割。在这部
18、分将重点介绍均值法差法的计算方法和在仿真中的运用。该算法基于背景区灰度方差小，而指纹区方差大的思想，将指纹图像分成块，计算每一块的方差，如果该块的方差小于阈值为背景，否则为前景。具体步骤分以下三步：(1)将低频图分成MM大小的无重叠方块，方块的大小以一谷一脊为宜。(2)计算出每一块的均值和方差。设指纹图像I的大小为HL，I(i,j)为像素点(i,j)的灰度，AVE和VAR分别为原指纹图像的均值和方差，AVE和VAR可以通过公式(2.1)和(2.2)计算得到。 （2.1） （2.2）(3)如果计算得到的方差几乎接近于0就认为是背景，对于方差不为零的区域在进行阈值分割算法，这种算法主要是根据计算得
19、到的方差来决定其是否为背景区。在使用方差均值法之前还要使用归一法将图变为低频图。归一化的目的是把不同原图像的对比度和灰度调整到一个固定的级别上，为后续处理提供一个较为统一的图像规格。指纹图像的归一化公式如式(2.3)所示，当大于平均值时为加。 （2.3）其中和为期望的灰度均值和方差。 2.3 仿真结果和结论本实验基于Window 7操作系统，Microsoft Visual C+软件环境下。指纹来自于指纹数据库，为了验证这种分割方法的适用性，从数据库中挑选了2幅差异较大的指纹图像。仿真中归一化的参数取了150，取了100，分割的区域大小M取了10。下面的图像为指纹图像归一化和分割结果。 (a)
20、 指纹原始图像 (b) 归一化处理图像 (c) 分割后图像图2-1指纹1的处理结果 图a 指纹原始图像 图b 归一化处理图像 图c 分割后图像图2-2 指纹2的处理结果从图中可以看到用方差均值法分割既适用于比较圆滑的指纹，又适用纹线变化很大的指纹图像。在归一化处理降频和通过区域均值方差的后得到的图像条纹清晰，轮廓分明，对于后面的细化和匹配有很大的帮助。该方法快捷，损坏程度低，缺点是计算有一定的复杂度，要通过2次方差均值来处理。第3章 指纹图像的细化3.1 指纹图像细化的预处理这部分预处理主要为二值化。由于指纹图像脊、谷相间，因此指纹图像的处理常是将指纹图像二值化。灰度图像二值化是将灰度图变换为
21、只有黑和白两种灰度的图像。这样不仅可以压缩原指纹图像的数据量，而且也方便后面的细节特征的提取。灰度图二值化的基本思想是选取适当的灰度阂值，将灰度图像转化为二值图像，阈值的选择是关键，对于阈值的选择，有多种方法，如熵法，Ostu法等。根据是否将图像分块处理，又分全局阈值算法和局部阈值算法两种，全局阈值算法是将整幅图像以一个阈值处理，而局部阈值算法则把原图分成若干个子图，在每个子图中确定闽值，在进行二值化，由于指纹图像在不同区域的亮度和对比度是有差别的，因而全局阈值算法不适用。灰度图二值化的基本思路是选取适当的灰度阈值，将灰度图像转化为二值图像。一般的图像处理中的二值化算法主要是计算整幅图像的灰度
22、平均值，然后将该值作为门限，高于该门限的像素点就置1，反之置0。我们通过研究发现，这种方法虽然简单，但是对噪声较大，图像质量不好的指纹会产生较大的二值化噪声。所以最好选用局部阈值法作为二值化算法。论文中采用了一种动态局部阈值，满足这种条件下的灰度值为128，不满足则灰度值为255。再根据前面判断的是否为背景即Icc值的来修正Icc值：灰度值为128且Icc为1时（非背景指纹纹线时），Icc值为0，像素值置为0。背景和灰度值为255的纹线像素置为1，这做法的目的是去除不确切的点。此时背景为白，纹线为黑。二值化后的图像中的点还要进行修改，修改条件为：当像素为1时，它周围点不大于3个为像素1点则修改
23、为0；当像素为0时，它周围不小于7个点为像素1的点，则修改为1。这种修改是为了使图像连续圆滑。3.2 指纹图像细化方法计算由于灰度过渡区的存在，指纹细化是指纹图像预处理中的一个重要环节，因为一般的特征提取都是在细化的基础上进行的，如果细化不好，将无法使用常规的特征提取算法提取细节特征信息。细化可以便我们得到绞线的单像素的骨架。所谓“骨架”，是指图像中央的骨骼部分，是描述图像几何及拓扑性质的重要方法之一。获取一个图像骨架的过程通常称为对图像“细化”的过程。在文字识别、地质构造识别、工业零件形状识别或图像理解中，先对被处理图像进行细化有助于突出形状特点和减少冗余信息。细化处理是指在指纹图像二值化以
24、后，在不影响纹线连通性的基础上，删除纹线的边缘像素，直到纹线为单像素宽为止。理想细化后的纹线骨架应该是原始纹线的中间位置，并保持纹线的连通性、拓扑结构和细节特征。一种好的细化算法应该满足下列条件：(1)收敛性：迭代必须是收敛的。(2)连通性；不破坏纹线的连接性。(3)拓扑性：不引起纹线的逐步吞食，保持原图像的基本结构特性。(4)保持性：保护指纹的细节特征。(5)细化性：骨架纹线的宽度为1个像素，即单像素宽。(6)中轴性：骨架尽可能接近条纹中心线。(7)快速性：算法简单，速度快。已有的算法迭代按迭代方式的不同分为串行算法和并行算法。在串行细化算法中，当前迭代的结果不仅取决于前一次的迭代迭代图像，
25、而且与当前处理情况有关；而在并行方式中，当前迭代仅仅是由前一次的迭代情况决定，串行细化算法的处理结果依赖于对像素处理的先后顺序，因而像素点的消除或保留不可预测。并行细化算法对图像进行细化时利用相同的条件同时检测所有像素点，其结果具有各向同性，因此从算法原理上并行算法优于串行算法。由于并行细化算法具有快速而准确的特性，因此他一直是人们研究的热点，并且相应的提出了许多并行细化算法，如OPTA细化算法，RWHall细化算法，Rosenfeld细化算法，Zhang & Suen 细化算以及ZR细化算法等等。性能上这些算法各有所长。制约细化的直观表现在计算速度、毛刺和断点上。因而细化中选择一个好的模板很
26、关键。模板分为保留模板和消除模板，消除模板就是根据条件判定这点去除作为背景的模板；保留模板则是根据条件判定这点保留作为前景的模板。这样就可以将较粗的图像曲线细化成很细的以像素为单位的线，大大减少了图像的信息量，有利于匹配的高效进行。本论文中采用了方法步骤如下：（1）建立3维数组，第一组数据为预处理后的图像信息，定义每一个像素点它周围点像素参数。（2）对于满足6种情况的模板，赋值为2 ，其实为像素1情况。对于满足后六种情况的模板赋值为3，别的情况点值不做改变。（3）16种消去模板是在不满足上述情况下衍生的模板，对于满足这些模板的点像素全为0，以上都未涉及的点不做改变。（4）循环进行上述过程，到所
27、有点值不改变为止，最多进行20次细化。3.3 仿真结果和结论先对分割好的图像进行二值化处理，简化后面的细化计算。细算中的模板在一个函数中实现，细化结果如下图所示： 图a 指纹分割图像 图b 指纹二值化图像 图c 指纹细化图像 图3-1指纹1的细化结果 图a 指纹分割图像 图b 指纹二值化图像 图c 指纹细化图像图3-2 指纹2的细化结果从分割后的二值化处理图像中，我们可以看到，整个灰度变成了黑白的二值图像图，图像的条纹比较清楚，它的实现有助于压缩数据量和细化的实现。细化将黑白二值图像细化成了单个像素带宽的指纹图像，由于模板的选择不同，上图中的细化图像一定程度上存在毛刺、分叉、断点等不理想的情况
28、。所以在特征提出前还需稍加处理，细化好的模板选择可以提高图片的质量和细化运算的速度。当然，此次仿真的细化还有待改进。对于细化中出现的毛刺现象，要根据局部特征来修改判定模板来决定这个点的像素，甚至可以减少模板的数量和判断次数，既简化模板，又提高运算速度，这点还可以有很大的深入研究。第4章 指纹图像的特征提取4.1 指纹特征提取概述特征提取就是对细化后的指纹图像提取表示其特征的信息的操作。我们前面所叙述的指纹图像预处理目的就是为指纹的特征提取和最终识别建立一个良好的基础，以保证整个系统识别率比较高。对于自动指纹识别技术而言，选择一种合适的、能表达指纹唯一性的特征量是非常关键的。一般说来，这种特征应
29、有以下性质：(1)单一性：要求这种特征能够充分体现指纹的唯一性。(2)可测试性：适用于指纹匹配算法，便于在匹配算法中应用。(3)紧凑性：要求提取的特征不应包含指纹唯一性以外的冗余信息，并且信息量要尽量小，便于存储、管理和计算。(4)鲁棒性：要求这种特征对噪声的存在与指纹形变不敏感。对于特征点提取的常用算法很多，如：(1)基于二值化的特征提取方法：这种算法对于预处理和增强后得指纹图像进行二值化，然后再提取特征点。(2)基于直接灰度的特征提取方法：这种方法直接从灰度图像出发，通过分析图像的纹理属性和拓扑结构提取特征点。(3)基于细化图像的特征提取方法：这种方法是将指纹图像处理后得到细化图像，通过细化图像提取特征点。为了比较两个指纹是否相同，需要从指纹图像中提取出能表示指纹唯一性的特征。Galton提出的指纹细节点是人工指纹匹配中最常用的特征。指纹由脊线和谷线交替构成，在大多数地方纹线连续且相互平行，而某些局部不连续的地方构成了细节点。Galton定义了4种细节点类型：分叉点，端点，环、岛，并指出细节点具有唯一性，可以用于指纹匹配。目前已定义的特征类型己达150多种，但是这些扩展的特征往往不易提取相互区分，并且它们都可以由端点和分叉点的组合进行描述，这使得端点和分叉点成为最常用的结构特征，也称为细节特征，它被认为是最稳定、最容易检查的，而且
