（通信与信息系统专业论文）自动指纹识别关键算法的研究.pdf

青岛理工大学工学硕士学位论文 摘要 ：7 ： 随着社会信息化、智能化与自动化的高速发展，传统的身份识别技术已经远 远不能满足实际应用中准确性、快速性的需求，取而代之的是基于信息处理技术 的现代生物识别技术。其中，指纹识别以其所特有优越性质，已成为应用范围最 广的生物识别技术之一。尽管自动指纹识别技术的相关研究已经取得了一定程度 的进展，但是由于信息的飞速膨胀，如何准确、快速的识别指纹仍然是一个亟待 解决的难题。 自动指纹识别是通过综合图像处理、模式识别、计算智能等多领域知识，自 动处理指纹图像中相关的特征信息，来判断指纹身份的生物识别技术。在分析和 总结前人研究成果的基础上，本文对指纹识别过程中的图像增强、特征匹配进行 了深入细致的研究，设计并实现了集成本文研究成果的自动指纹识别系统。 ( 1 ) 为了尽可能地保留指纹纹理信息的同时减少噪声的影响，借助小波变换的 多分辨率分析特征，提出了一种基于小波的指纹图像增强方法。该方法通过小波 多尺度分解，将原始图像分为频率不同的子图，然后根据各频率子图信息与噪声 含量不同的特性，对低频子图进行方向滤波，对高频子图进行降噪处理，将处理 后的小波系数重构得到初步增强的指纹图像，为了进一步突出细节信息，再对指 纹图像进行反锐化掩膜后处理。实验结果表明，该方法可以在增强指纹的纹理信 息的同时滤除噪声，从而较好的改善了图像的质量。 ( 2 ) 针对指纹匹配过程中基准点定位不准确与耗时太长问题，提出了一种基于 改进基准点定位的指纹匹配算法。该算法借助指纹图像的中心点，构造局部细节 结构，并在此结构上利用全等三角形原则求取基准点，然后将所有细节特征转化 到极坐标中，利用可变界限盒的方法进行匹配。实验结果表明，该算法所确定的 基准点较为准确，而且耗时缩短，有效地提高了识别率与执行效率。 ( 3 ) 在详细需求分析的基础上，设计并实现了本文的自动指纹识别系统，集成 了本文所有研究成果。该系统能够直观地展示用户操作的处理结果，较为方便、 实用，为将来的实际应用奠定了基础。 关键词：指纹识别，图像增强，特征点提取，特征匹配，自动指纹识别系统 青岛理工大学工学硕士学位论文 a b s t r a c t w 陆t l l er a p i dd e v e l o p m to f 血e l l i g e n a n d 嬲t o m 撕o n ，也et r a d i t i o n a l i 制 ，几) y ( 竿) 出 ( 2 - 1 ) 其中口为尺度因子，6 为平移因子。 由于图像处理的离散化、数字化要求，离散小波变换可以表示为： d 胛( 肌，玎) = 2 了厂( 后) 甲( 2 ”七一刀) ( 2 - 2 ) ( 2 ) 反锐化掩膜 在图像增强领域中，图像的对比度是决定其主观质量优劣的重要因素。假设 6 青岛理工大学工学硕士学位论文 厂( z ，y ) 为原始图像，厂o ，y ) 为处理后的图像，那么，图像增强可以表示为 厂( 毛y ) = 饥厂“y ) 】，其中研 通常为非线性且连续的函数。对于图像的有限灰度 级，量化误差通常会引起信息丢失，致使一些敏感的边缘因为与相邻像素点的合 并而消失，尽管经过自适应直方图均衡处理可以克服这些问题，但是它却不能处 理不同尺寸的图像特征。因此产生了一类图像边缘算法，而反锐化掩膜就是这类 算法的具体实现。 其离散形式定义为： 厂o ，歹) = o ，_ ，) + 札厂0 ，歹) 一( f ，j ) 】 ( 2 - 3 ) 其中，厂( f ，歹) 是原始图像的一个模糊版本。 2 1 2 前人相关研究成果及分析 目前图像增强方法主要有空域方法和频域方法。空域方法是直接对图像各像 素点的灰度进行卷积滤波，以达到增加脊谷对比度的目的。该类算法复杂度较低， 运算较快，但是却忽略了全局信息；频域方法是对图像进行变换后在变换域中对 图像参数进行运算，然后通过逆变换得到增强的图像。该类算法增强效果一般较 为理想，但是由于需要准确计算指纹的方向图以及脊线的频率，使得计算复杂度 较高，难以实现大规模的实时应用。 小波理论作为一种新兴的时频分析方法，是传统傅立叶变换的继承和发展， 并以其多分辨率分析所具有的时频局部化特性，有效地克服了g a b o r 傅里叶变换 在单分辨率上的缺陷。该方法可以对高频采用逐渐精细的时域或空域步长，于是 可以聚焦到分析对象的任意细节，因此特别适合于处理图像信号这一类非平稳信 源。在这种新理论支持的基础上，一类新的基于小波变换的增强方法应运而生。 穆国燕等【3 5 】提出了基于小波变换和纹理滤波来增强指纹图像的方法，对小波域内 所有频率的子图像进行了同样的纹理滤波，重构后得到了一定的增强效果；王建 英等3 6 】提出了一种基于小波变换的图像增强算法，利用低频系数子图像在小波域 计算指纹纹线方向，从而有效地抑制了高频噪声对纹线方向的影响，取得了较好 的效果；田俊等【3 刀提出了一种在小波域对指纹图像进行g a b o r 滤波增强的算法， 使图像的质量得到了明显的增强。但是该类方法没有充分利用小波变换的多尺度 7 青岛理工大学工学硕士学位论文 分析特性，也没有考虑到噪声对图像质量的影响。 2 1 3 本文指纹图像增强算法 指纹图像增强的根本目的是突出图像中的脊线信息，增加脊谷的对比度，同 时滤除引入的噪声对图像质量的影响。根据高斯噪声的特性可知，高斯噪声的小 波变换仍然是高斯噪声，它分布于整个小波域中，因此大部分噪声分布在高频子 图像中；再根据小波变换的原理可知，对指纹图像进行多尺度分解后，所得到的 低频子图像的小波系数分布与原始图像的灰度分布大致相同，并且图像的能量大 部分都集中在该区域。也就是说，低频子图像很好地保留了原始图像的纹理信息 和绝大部分能量，而只含有较少的噪声分量；高频子图像主要包含很少的图像细 节信息，但却包含了大部分的噪声分量。 鉴于上述各个频率子图像所包含分量的特性差异，结合图像的不同处理方法， 本文提出了一种基于小波变换的指纹图像增强新方法。该方法首先将图像进行多 糖： 尺度分解，在小波域对低频子图像进行纹理滤波，以增强指纹的纹线信息，而且 对断裂的纹线具有一定的连接作用；对高频子图像进行自适应加权均值滤波降噪 处理，从而滤去大部分噪声对图像质量的影响。然后将调整后的小波系数进行完 全重构，得到初步的小波增强图像。然而，均值滤波降噪的同时也弱化了指纹图 像的高频细节信息，因此，采用反锐化掩膜的方法对初步小波增强图像进行后处 理，最终达到保留纹线的同时去除噪声影响的目的。本文方法的详细过程介绍如 下： ( 1 ) 指纹图像规格化： 由于指纹采集仪器在各种环境下不同的光照强度，或者指纹表面的干湿、汗 渍的影响，使得所采集到的不同图像的灰度分布差异很大。指纹图像规格化处理 的目的是减少这种图像灰度的差异，使图像的灰度分布达到预先设置的均值和方 差。具体的规格化过程如下： 假设厂( f ，) 为原指纹图像上的像素灰度值，厂( f ，) 为规格化后的像素灰度值， 那么就有 8 青岛理工大学工学硕士学位论文 ( f ，) = 眠+ 一瓴力妇 叫， 耻、型竽塑 。撕 卜v 其中，m 和仃z 为原图像的均值与方差，m 。和仃；为已经预先设置的均值与方差。 采用上述原理对原始指纹图像规格化效果如图2 1 所示。 ( a ) 原始图像( b ) 规格化图像 图2 一l 原始图像与规格化效果图 从图2 1 可以看出，原始图像( a ) 中间区域灰度均值明显小于边缘地带灰度均 值，而经过规格化处理之后，这种灰度分布差异明显减弱。 ( 2 ) 小波分解： 指纹图像要进行小波分解，实质上就是把图像信号分解成不同频带范围内的 图像分量，因此，要进行小波分解最重要的问题就是小波基函数的选择与分解层 数的确定。文献 3 8 】对此进行了详细的分析描述，本文选用长度适中的d b 4 小波， 对指纹图像进行2 层分解。小波分解结果如图2 2 所示。 9 青岛理工大学工学硕士学位论文 图2 2 小波分解结果 从图2 2 可以看出，图像经过1 层小波分解后，产生l l l 、h l l 、l h l 和h h l 四个频带分量；图像的2 层小波分解，实际上就是将1 层分解后所产生的低频分 量l l l 再进行一次小波分解，因而又得到了u 2 、h l 2 、l h 2 和h h 2 四个频带分 量。 ( 3 ) 小波系数的处理： 根据低频子图小波系数分布与原始图像的灰度分布大致相同的特性，对2 层小波分解后的低频子图l l 2 的小波系数进行纹理滤波，具体步骤如下： 步骤1 ：计算出指纹块方向，并量化到8 个不同的方向上。假设9 ( f ，歹) 为以点 ( f ，) 为中心的块区域的方向，g ，( “，1 ，) 和q ( “，v ) 分别为点在x 方向和y 方向上的梯 度。则有： 即= 三舭 器】 ( 2 - 5 ) 其中， j + 兰，+ 竺 肘o ，力= 2 q ( 甜，力g ( 掰，力 ( 2 6 ) w w 。百，1 f o ，o ( f ，_ ，) ：塞( g ：( “，v ) 一嘭( “，v ) ) ( 2 7 ) 峙， 1 0 一 青岛理工大学工学硕士学位论文 在该步骤中，梯度值是由大小为3 3 的s o b c l 模板计算而得。根据该思路，计 算原始图像图2 1 ( a ) 的x 方向和y 方向上的梯度，结果如图2 3 所示： ( a ) x 方向上的梯度 ( b ) y 方向上的梯度 图2 3 指纹图像的工方向和y 方向上的梯度图 步骤2 ：根据平均滤波器与分离滤波器的设计原则，设计出水平方向上的滤波 模板；其它方向上的模板系数可由水平方向模板旋转相应的角度得到。水平滤波 模板系数分布如图2 4 所示。 z 32 z 3zzz2 z 3z 3 、| 3 2 y 3yyy2 y 3y 3 ) “32 x 3xxx2 x 3 x 3 u 32 u 冯uuu2 u 3u 3 x 32 x 3xxx2 x 3x 3 y 32 y 3yyy2 y 3y 3 z 32 z 3一z zz一2 z 3z 3 图2 4 水平方向滤波器系数分布图 只要上图中的系数满足u x 】，0 、z 0 和u + 2 x + 2 y 一2 z = 0 就可以作 为滤波模板来使用。 步骤3 ：根据上述指纹块方向选择相应方向上的滤波模板，对低频子图像进行 滤波，以达到增强纹理信息的目的。 在高频子图上，根据噪声的高斯性质，采用自适应加权均值滤波算法去除。 该滤波算法采用某像素点邻域内灰度值的加权平均值来代替原像素点的灰度值， 其加权系数取决于该像素灰度值与块均值的差异程度，也就是说，如果某像素灰 青岛理工大学工学硕士学位论文 度值与块区域均值越接近，则说明该像素点相对于块区域内其它像素点的可靠程 度越高，其加权系数就应该越高。具体步骤如下： 步骤1 ：假设厂( f ，力为高频子图像的小波系数，对其进行甩刀分块，则子图像 内各点的加权系数可由公式( 2 8 ) 计算得出： 一 口( f ，j ) = - + 卜力一砉胁m 2 l 亿8 ) l_ ，v 窖li 步骤2 ：滤波后的小波系数g ( f ，_ ，) 可由公式( 2 9 ) 计算而得： ( 叫) 口( 州) g g ) = 竺l _ 一 口( 叩) “v 耐 ( 2 9 ) ( 4 ) 小波重构： 将调整后的低频、高频小波系数组合在一起，进行小波完全重构，得到初步 的小波增强图像。 ( 5 ) 反锐化掩膜后处理： 由反锐化掩膜的原理可得，将小波变换后的低频子图像扩展成原始图像大小， 这样就得到了原始图像的模糊版本，即公式( 2 3 ) 中的厂o ，) ，而其中的厂伉) 为 小波重构后所得到的初步增强图像，夕( f ，- ，) 为经过反锐化掩膜后所得到的最终增强 图像。 2 1 4 实验结果及分析 根据本文提出的各频率子图像小波系数的处理方法，结合2 1 3 节所述的图像 规格化和反锐化掩膜原理，在双核2 9 3 g h z 、2 g b 内存的计算机上对部分指纹图 像进行了增强实验，并与文献 7 】、文献 1 0 】等方法作了比较。各方法消耗时间均值 如表2 1 所示；各方法不同的增强结果如图2 5 所示。 表2 1 各方法消耗时间均值 图像增强方法名称 消耗时间( m s ) 文献【7 】空域滤波方法 9 6 3 本文小波增强方法 1 2 6 9 1 2 青岛理工大学工学硕学位论文 ( a ) 文献【7 空域增强结果( b ) 本文小波增强结果( c ) 文献 1 0 】g a b o r 增强结果 图2 5 不同方法的增强结果 由于目前尚无统一的指纹图像增强效果客观评价指标，所以本文采用主观定 性分析方法。从图2 5 可以看出，三种增强方法对纹线的断点都有一定的连接作用， 也能够有效地增加脊谷对比度，并不能借此直接判断算法的优劣。然而所有增强 图像的最终目的都是应用于后续的指纹处理过程，包括二值化、细化等，于是本 文将不同方法所得到的增强图像统一进行了基于分块自动阈值分割的二值化处理 ( 具体原理及过程参见2 2 节) ，由二值化效果来间接判断增强算法的优劣。各方法 增强图像的二值化效果如图2 6 所示。 ( a ) 文献 7 】增强图像二值化( b ) 本文增强图像二值化( c ) 文献【1 0 】增强图像二值化 图2 - 6 不同方法增强图像的二值化效果 从图2 6 二值化的效果来看，文献 1 0 】所采用的g a b o r 滤波增强方法效果最优， 能够很好的去除噪声，而且脊线信息也得到了加强，但是该方法耗时太长，几乎 是本文方法耗时的3 倍，难以用于大量实时处理；文献 7 】所采用的空域方向滤波 增强方法的效果一般，虽然能够在一定程度上保留指纹的脊线信息，但是由于该 1 3 青岛理工大学工学硕士学位论文 方法本身并没有降噪的功能，致使噪声对增强结果产生了很大的影响，使纹线中 出现了大量的小孔及小桥，这是后续细化处理效果最主要的影响因素之一，实验 表明，该方法效果很大程度上依赖于指纹图像的噪声含量，适宜用于高质量指纹 图像的实时处理；本文方法能够很好的加强纹线的信息，同时滤除了噪声的影响， 对断点也有较强的连接能力，虽然本文方法增强后的纹线在视觉上不如g a b o r 滤 “ 波光滑，但却不会影响后续的细化效果，而且本文方法耗时较短，与空域滤波增 强方法耗时相差不大，可以用于大量含噪声指纹图像的实时处理。综上所述，本 文方法能够在较短的时间内加强纹线信息，同时滤除噪声的影响，在增强效果和 运算时间的权衡中占有一定的优势。 2 2 二值化 指纹图像经过增强处理之后，由于脊线和谷线灰度差异较大，使得指纹纹理 结构明显。因此，对增强图像进行二值化处理就是要将脊线分离出来，有助于下 一步细化操作。所谓二值化【3 卅是指将指纹图像变为o 或l 取值的黑白图像。常见 的二值化方法m 】分为固定阂值二值化和局部动态阈值二值化。其中，上文对增强 图像进行评价时所用的二值化方法属于后者。 2 2 1 常见的二值化方法 哆 ( 1 ) 固定阂值二值化 固定阈值二值化是指根据图像本身的先验知识，确定出一个合理的阈值， 将灰度值不小于该阈值的像素点判定为脊线点，将其灰度值定义为1 ；同理，判定 灰度值小于该阈值的点为谷线点，将其灰度定义为0 。该方法可用公式( 2 1 0 ) 表示， 即： 厂c 功手 三参；葛三； c 2 一。， 其中，r 为根据先验知识所确定的阈值。 ( 2 ) 局部动态阈值二值化 局部动态阈值二值化( 1 5 】借助了上述固定闽值二值化的思想，利用局部区域内 目标像素的邻域灰度分布情况，确定出适合于该区域的二值化阂值，常用的方法 有分块均值法【4 2 】等。 1 4 青岛理工大学工学硕学位论文 顾名思义，分块均值法就是将增强后的图像进行分块，利用指纹图像灰度分 布在局部区域变化不大以及指纹前景与背景灰度差异明显的特性，取每一块的灰 度均值作为该块的二值化阈值，从而实现指纹脊线的提取。 2 2 2 实验结果及分析 本文根据上节所述的固定阈值二值化算法和局部动态阈值二值化算法的思 想，在双核2 9 3 g 】舷、2 g 内存的计算机上对部分指纹图像进行了系列二值化处理 实验，图2 7 显示了其中灰度分布不均匀的指纹图像1 、灰度分布较为均匀的指纹 图像2 的实验结果。 ( a ) 原始图像1 ( d ) 原始图像2 ( b ) 固定阈值二值化( c ) 局部动态阈值二值化 ( e ) 固定阈值二值化( o 局部动态阂值二值化 图2 7 部分二值化实验结果 由图2 - 7 可以看出，对于整幅指纹图像中灰度分布不均匀的指纹( 图2 7 ( a ) ) ， 采用固定阂值( 在本文中，设置固定阈值为0 5 ) 时，效果较差，如图2 7 ( b ) 所示，而 采用局部动态阈值( 在本文中，采用分块均值法，即以每块的均值作为该块的二值 化阈值) 时，效果较好如图2 7 ( c ) 所示；对于整幅图像中灰度分布较为均匀的指纹( 图 1 5 育岛理工大学工学硕士学位论文 2 - 7 ( d ) ) ，采用局部动态阈值法仍然能够得到比固定阈值法更好的效果如图2 7 ( e ) 、 ( d 所示。 2 3 纹线细化 大部分的指纹匹配算法都是在前景分割后的二值化图像基础之上的。然而， 经过上述的二值化处理之后，所得的图像中不但含有大量的冗余信息，很大程度 上影响了指纹处理程序的运算速度，而且大部分纹线仍然具有一定的宽度，影响 了细节特征的准确提取。为了便于快速准确的提取指纹的细节特征信息，需要进 行细化处理。所谓纹线细化，是指在不影响纹线连通性的前提下，将指纹脊线的 骨架提取出来，即使脊线变为单像素宽。常见的纹线细化算法有o p t a ( o n e p 鹪s 1 1 1 i m l i n ga l g o r i t h i n ) 细化算澍1 8 1 和快速细化算法【冽。 2 3 1 常见的纹线细化方法 譬 ( 1 ) o p t a ( o n e p a l s st h i 如i n g 舢g o r i t h m ) 细化算法 6 i 原始o p t a 细化算法包含8 个消除模板和2 个保留模板，由于这些模板的构 造并不完善，使得原始o p t a 细化算法不能达到a f i s 所要求的准确度。冯星奎等 【1 刃对其进行了改进，构造了8 个消除模板和6 个保留模板，然而，该改进算法在 分叉点处仍然具有一定的缺陷。王业琳等【4 3 】对冯星奎的算法进行了改进，将消除 模板增加到了8 个，并且删除了保留模板的部分特殊情况，从而很好地解决了算 法在分叉点处的缺陷，得到了较好的细化效果。该改进算法的细化思想大致如下： 从二值化图像的一端开始，取脊线点为目标点。对于每一个目标像素点，判 断是否符合某个消除模板，如果符合任意一个消除模板，再判断其是否同时符合 某一个保留模板。对于任意一个脊线点，如果符合任何一个消除模板，同时又不 符合任意一个保留模板，则需要删除该点，否则，保留该点。按照这样的方法， 遍历图像的所有脊线点，直到没有任何脊线点被删除为止。 ( 2 ) 快速细化算法 。 快速细化算法数学形态学的一种处理方法，该类方法通过遍历二值化图像上 每一个脊线像素点，通过8 邻域的相关规则，判断其是否为边界点，如果是边界 点，则删除该点。循环执行上述操作，直到没有任何点被删除为止。 对于任意脊线像素点，其8 邻域结构如图2 8 所示： 1 6 青岛理工大学工学硕士学位论文 p 8p lp 2 p 7 彩 p 3 p 6p 5 p 4 图2 8 像素点p o 的8 邻域示意图 8 邻域像素点构成了一个有序集合嘏，昱，与，只，只，忍，b ，丑) ，在此，定义2 个 特征量肌7 ：s ! m 为8 邻域中非零像素点的个数，及毽m 为8 邻域中像素卜l 变化次 数，具体公式定义如下： 8 删= ：鼻 ( 2 1 1 ) - _ 8 硼洲= 1 只+ 。一只i 。 j 皇l 根据指纹图像边界点的特点，定义细化规则如下： ( 2 - 1 2 ) ( 1 ) 1 疆，s 膨 7 ( 2 ) 兀毽m = 2 ( 3 ) 置只另= 0 ( 4 ) b 只b = 0 对于每一个目标像素点，判断上述细化规则，如果满足，则删除该点。循环 执行这一操作，直到没有任何点被删除为止。 2 3 2 实验结果及分析 本文根据上节所述的o p t a 细化算法和快速细化算法的思想，由于二者都能 够在大量实时处理环境下取得令人满意的效果，而快速细化算法在运算复杂度上 较o p t a 细化算法低，因此，本文采用快速细化算法，并在双核2 9 3 g h z 、2 g 内 存的计算机上对部分指纹图像进行了纹线细化处理实验，图2 9 显示了其中灰度分 布不均匀的指纹图像l 、灰度分布较为均匀的指纹图像2 的纹线细化处理结果。 1 7 青岛理工大学工学硕士学位论文 ( a ) 原始指纹图像1( b ) 纹线细化效果 ( c ) 原始指纹图像2( d ) 纹线细化效果 图2 9 部分纹线细化实验结果 由图2 9 可以看出，无论原始图像灰度分布均匀与否，经过2 2 1 节所述的动 态阈值二值化分割后，在快速细化算法的处理下，均能够得到较为清晰的、单像 素宽的点线图，给后续特征点提取打下了坚实的基础，所得到的结果符合自动指 纹识别系统大量实时处理的要求。 2 4 小结 本章从指纹图像预处理的大致流程出发，介绍了指纹增强、二值化、细化的 理论原理、作用及具体的处理过程，并就指纹图像增强算法进行了详细深入的分 析。在前人相关研究成果的基础上，结合小波变换的多分辨率分析特性，并根据 不同频带中噪声含量不同的性质，提出了一种兼顾图像去噪和增强纹理信息的基 于小波的指纹图像增强算法，实验证明，该方法能够在保留和增强指纹纹理信息 的基础上有效地去除图像中的大部分噪声影响，取得了较好的效果。 1 8 一青岛理工大学工学硕士学位论文 第3 章指纹特征提取 在实际的生活中，人对某个特定的模式进行识别时，一般都是通过提取其特 征信息，然后判断出哪些特征信息可以对识别的结果产生直接的影响，即提取其 主要特征，这个过程就称作特征提取。同样地，指纹识别就是通过提取指纹图像 中能够直接影响判决结果的特征点信息，进而比对其类型、位置、方向等属性， 最终拟合出最佳的识别结果。 3 1 特征点及其提取 目前，细节点仍然是应用最为广泛的特征信息【“ 5 0 】，然而在指纹图像中大约 有1 0 0 多种不同类型的细节点，如果将这么多种类的细节点全部应用于匹配过程 中，当然能够显著改善识别结果的准确性，但同时势必会增加额外的存储与运算 开销，这显然不是实时指纹识别所期望的。 为此，本文选取两类最能表征指纹纹路的细节点：端点和分叉点。实际指纹 图像中两类细节点分别如图3 。l ( a ) 所示，其中右侧红色圆圈所标示细节点类型为端 点，放大后如图3 1 c b ) 所示；左侧红色圆圈所标示细节点类型为分叉点，放大后如 图3 1 ( c ) 所示。 ( a ) 实际指纹图像( b ) 端点( c ) 分叉点 图3 1 实际指纹图像及其细节点 指纹特征点提取的目标是尽可能准确地记录下每一个特征点的坐标、类型、 方向等属性点信息，以便后续的指纹匹配算法的顺利进行。目前常用的方法有基 于灰度图像【5 1 1 、二值图像5 2 1 、细化图像跚等多种方法。由于基于灰度图像的特征 】9 青岛理工大学工学硕士学位论文 点提取算法不需要经过二值化、细化等可能导致信息丢失的操作，使得其结果最 为准确，但是算法在每次追踪过程中需要设置合理的起始点，使得运算相当复杂， 难以实现实时应用；基于细化图像的特征点提取算法的主要缺陷是从二值图像上 提取所得到的细节点中伪细节点数目过多，且难以去除，算法的鲁棒性差； 因此，为了尽可能准确、快速地提取细节点，本文在细化图像的基础上，首 先利用2 3 1 节提及的数学形态学中的8 邻域模型提取出整幅图像中的所有细节 点，然后通过进行的细节点后处理操作除去其中所含的大量伪细节点，进一步提 高细节特征的准确度。下面详细介绍基于形态学指纹特征点提取的具体过程。 根据2 3 1 节所述数学形态学描述方法，对于细化后的图像上的每一个脊线点i 其8 邻域模型如图3 2 ( a ) 所示，端点及分叉点的8 邻域数学模型分别如图3 2 ( b ) ( f ) 所示。 p 8 p lp 2 p 7 澎 p 3 p 6p 5 p 4 ( a ) 8 邻域模型 p 8 彩 p 2 p 7 彩 p 3 p 6p 5 p 4 ( b ) 端点l( c ) 端点2 p 8 彩 p 2 p 7 彩 p 3 p 5 殇 ( d ) 分叉点l( e ) 分叉点2( f ) 分叉点3 图3 2 脊线点、端点、分叉点的8 邻域模型 根据公式( 2 1 1 ) 、公式( 2 1 2 ) 关于肌愿膨、兀硌膨的定义，借助上述细节特征 点的8 邻域数学模型，定义细节特征点提取规则如下： ( 1 ) 如果肌毽m = 1 ，且及硌膨- 2 ，则该脊线点为端点，记录其属性信息； ( 2 ) 如果肌毽m = 3 ，且删= 6 ，则该脊线点为分叉点，记录其属性信息； 3 2 特征点后处理 由于指纹图像质量、进行细化处理时产生的畸变等原因的影响，使得所提取 出的细节特征信息中包含了一定量的伪细节信息。为了保证所提取出的细节点属 青岛理工大学工学硕士学位论文 性信息的准确性，需要对其进行合理的后处理【洲6 】，细节特征点所需要进行的后 处理主要有边缘伪细节点的去除、模糊部分伪细节点的去除、毛刺伪细节点的去 除等。下面将详细介绍各步骤流程。 ( 1 ) 边缘伪细节点的去除 由于指纹采集环境的原因以及图像预处理过程的不同，在图像的边缘地带， 一般含有大量的伪细节特征。对于每一个特征点，计算其与边界的距离，如果该 距离小于预先设置的阈值r ，则认为该细节点不准确，应从指纹特征点集中删除该 点的记录，反之则需保留。 ( 2 ) 模糊部分伪细节点的去除 指纹图像的模糊部分在进行细化处理时会产生大量的断点和分叉点，而这些 伪特征信息都不是我们所期望的，因此，需要去除这部分伪细节特征点。在此， 引入两个参考量：细节特征点的结构数肫和肠，细节特征点的对比度玩加和 玩巾。所谓细节特征点的结构数是指以该细节点为中心，周围半径为r 的区域内 所有类型细节特征点的个数，其中肫为区域内的端点个数，册为区域内的分叉 点个数。而细节特征点的对比度则是指在灰度图像上以该细节点为中心，按照一 定方向所取出8 个像素点的灰度方差，其中玩加为按照指纹纹线的方向取点所计 算出的平行对比度，玩伊为按照垂直于指纹纹线方向取点所计算出的垂直对比度。 指纹模糊部分伪细节点去除的具体步骤如下： 步骤l ：计算各特征点的结构数肫和肠，各特征点的对比度玩阳和玩仞， 并根据玩阳和阮印的值计算： 砌：堡生 ( 3 1 )，栉= o i j lj l o g 拶 其中b 为块区域内的灰度均值； 步骤2 ：如果结构数盹和册超过预先设置的阈值，则认为该处细节点密度过 大，删除该点记录； 步骤3 ：如果砌小于预先设置的阈值，则认为该处细节点水平对比度与垂直 对比度较为接近，因而该细节特征点并不可靠，删除该点记录； ( 3 ) 毛刺短线等伪细节点的去除 2 1 青岛理工大学工学硕士学位论文 毛刺和短线产生的原因主要是二值化处理后图像不够平滑。在经过特征提取 之后，其细节特征点之间距离较小，因此，本文以分叉点为中心，预先设置一个 半径值，查找在该半径范围内是否有端点出现，如果有，则认为这两个细节点为 由毛刺或短线产生的伪细节点，删除这两个点的记录。 3 3 实验结果及分析 指纹图像经过预处理之后，已经成为较为清晰地单像素宽的点线图，为后续 细节特征点的提取提供了极为有利的条件。本文在指纹预处理结果的基础上，结 合上文3 1 节所述的特征点类型、特征点提取方法和3 2 节所述的特征点后处理方 法，在双核2 9 3 g h z 、2 g 内存的计算机上对部分指纹图像进行了特征点提取及后 处理实验，其实验各步骤效果如图3 3 、图3 4 所示。其中，各图像中符号“o 和“ 分别用来标注细节特征点中的端点和分又点。 ( a ) 原始图像l( b ) 特征点初步提取结果( c ) 去除边缘伪特征点结果 ( d ) 去除模糊部分伪特征点结果( e ) 去除毛刺短线等伪特征点结果 图3 - 3 指纹图像l 特征提取及后处理结果 青岛理工大学工学硕士学位论文 ( a ) 原始图像2( b ) 特征点初步提取结果( c ) 去除边缘伪特征点结果 ( d ) 去除模糊部分伪特征点结果( c ) 去除毛刺短线等伪特征点结果 图3 _ 4 指纹图像2 特征提取及后处理结果 对于质量较低的原始指纹图像l ，经过初步特征点提取之后所产生的特征点数 目较多，如图3 3 ( b ) 所示，其中含有大量的伪细节特征点，主要分布在图像的边 缘部分、图像模糊部分以及整幅图像中出现的毛刺短线部分。经过边缘特征点去 除、模糊部分伪特征点去除、毛刺短线伪特征点去除以后，结果分别如图3 3 ( c ) 、 图3 3 ( d ) 、图3 3 ( e ) 所示，能够去除原细节特征点集中所含有的大部分的伪特征 点信息，确保了后续特征点匹配结果的准确度。 对于质量较高的原始图像2 ，初步提取的特征点集中含有的伪特征点较少，在 经过特征点后处理之后，进一步提高了细节特征点的准确度。 3 4 小结 本章简要介绍了指纹特征点类型、各类特征点提取算法的缺陷与不足，进而 选择了本文所用的两类细节特征点，即端点和分叉点，并在细化图像的基础上采 用数学形态学中的8 邻域模型进行了特征点的提取，最后对所提取到的细节点进 青岛理工大学工学硕士学位论文 行后处理，以除去其中大部分的伪细节点，保证了特征点集的准确性。实验结果 表明，该方法能够快速地提取细节特征点，且所得的细节特征点集满足后续操作 所要求的准确度，适用于自动指纹识别系统。 青岛理工大学工学硕士学位论文 第4 章指纹图像匹配 指纹匹配是自动指纹识别技术的关键环节，它直接决定了整个指纹识别系统 的优劣，如何提高识别率并减少算法复杂度是指纹匹配所要研究的核心问题。目 前，最常用的指纹匹配算法是由美国f b i 提出的点模式匹配法【5 7 1 ，它利用脊线端 点与分叉点这两种类型的细节点来鉴定指纹，通过将细节点表示为点模式的细节 特征，从而将指纹匹配问题转化为一个点模式匹配问题。 指纹图像的匹配原本需要解决平移、旋转和形变等多种问题，然而如果找到 一对基准点对，则只需要解决旋转和形变问题。j a i n 5 8 】等指出在极坐标系中能更好 地描述非线性形变；同时我们也不需要考虑输入图像与模板图像的对应点之间的 平移关系；而且，在极坐标系中很明显比在直角坐标系中更加有利于处理两幅图 像间的旋转。因此在指纹匹配的算法中，一般要先找到一对或几对匹配的基准点， 然后通过将所有的细节特征点进行极坐标变换，并将旋转图像进行姿势校正，最 后再进行比对，计算出匹配点对数和匹配分数进而判断两幅图像是否匹配。 4 1 前人相关研究成果及分析 根据上文所述指纹匹配思想，王磊【5 9 】提出了一种三角形基准点定位的匹配算 法，该算法对于质量较高的指纹图像能够达到一定的匹配准确率。原算法主要包 括基准点定位及旋转因子的求取、极坐标转换及姿势校正、界限盒匹配及结果判 决三部分。下面将对每一部分做出详细的说明。 4 1 1 基准点定位及旋转因子求取 假定两个含有不同数量的点的集合p 和q 分别为模板和输入图像细节点集。 首先在模板点集尸中任意取一点只，再在输入图像的细节点集q 中寻找与其类型 相同的点g ，然后判断与这两个点距离最近的点p 。、g 。或次近点p ：、g ：的类型是 否相同；如果相同，则继续判断以这三个点为顶点的三角形卸；p 。p 2 与g ，g 。g ：是 否近似全等以及对应边的角度差是否近似相等，即钟，铭， 青岛理工大学工学硕士学位论文 铭铭；如果相等，则认定p ，和g ，为基准点对，计算旋转因子 p = l 3 ( b l + b 2 + 1 9 1 2 ) ；如果上述任何判断出错，则变换a 并重新寻找g ， 直到找到基准点对或者查遍所有的细节点为止。 4 1 2 极坐标变换及姿势校正 对于两个特征点集尸和q ，分别以它们对应的基准点p ，和g ，为极坐标原点， 进行坐标变换，具体的变换公式如下： ) ，。一y 。、 ( 4 1 ) y ，一y 。1 l 4 。l j x t x c ) 其中k ，只) 为待转换的细节特征点直角坐标，g ，q ) 为转换后的极坐标，g 。，y 。) 为 基准点直角坐标。 对于输入图像q 的极角吒，应该以模板图像p 为基准进行校正，校正公式为： 吃= 巳一口 ( 4 2 ) 特征点集校正后，将两个点集中的特征点按照极角递增的顺序排列，以利于 下一步的匹配。 4 1 3 界限盒匹配及结果判决 对于非线性形变问题，引入可变界限盒的概念，如图4 1 所示。对靠近基准点 的细节特征点，较小的形变会对极角造成较大的影响，而对极半径却影响相对较 小；反之，远离基准点的细节特征点发生形变时，对极半径影响较大，而对极角 影响相对较小。于是半径为r 的细节点处界限盒所取参数计算如下： f ，一册口刀 矿 ，一s 拓p ，一j m 口刀 厂口破淞一s 切= ，一s 切矿，一s m 口盯 ，一s 沈 ，一，a 唱p 其中，s 泐：二； 一 口 ， i 口一s 肌口刀 矿 口一s 姚 口一s m 口彪 口穆g 彪一s 妇= 口一s 沈 矿 口一s 加口盯 1 2 ) 1 9 尺( 聊口砌一s c d ，p r ) ( 4 - 6 ) 其中r 为预先设置的阈值。只要上式的值为1 ，就认为两个指纹匹配成功，否则， 匹配失败。 4 2 本文提出的指纹匹配算法 由于采集到的指纹图像受到噪声等外界原因影响造成边缘部分提取的细节点 中含有大量的伪细节点，或者图像中模糊部分中含有大量的伪细节点，造成了上 述三角形定位算法的运行时间较长，算法的执行效率较低；另外，指纹中含有伪 细节点的特征点集可能形成符合上述算法但又不是对应基准点的全等三角形，如 图4 - 2 所示，模板图像中出份c 与输入图像中衄近似全等，而且对应边的角度 2 7 青岛理工大学工学硕士学位论文 差也近似相等，但是彳点与x 点却不是对应的基准点，这样就造成了误判，从而 增加了虚警概率，降低了识别的精度。 ( a ) 模板图像( b ) 输入图像 图4 2 三角形全等的错误情况 鉴于上述算法的一些缺陷，为了进一步提高识别精度、减少运算复杂度，本 文借助中心点的选取，构造局部结构，并在局部结构上进行基准点对的选取。下 面详细介绍具体步骤。 4 2 1 中心点的选取 中心点定义为图像的曲率场中最大值所对应的像素点，也就是图像中纹线方 向变化最大的点，位于指纹纹路的渐进中心，周围纹线大致呈半圆趋势。目前， 最常用的求取中心点的方法是尸。扬陀索引法【6 l 】，通常情况下，由于该方法求取 的中心点不够准确，因此不能将其作为基准点直接用于指纹匹配，而是用作指纹 分类的依据【6 2 1 。然而细节点的相对位置较为固定，适宜作为基准点。在本文中， 中心点只起参考作用，因而中心点的位置不必太精确，上述算法可以直接应用。 具体的计算过程如下： p d 伽c 口坨( f ，- ，) 2 去从 降7 ) 其中 万( 七)矿 + 万( 七) 矿 一艿( 七)矿 懈) i 三 砸) 一詈 沁三 万( | i ) = d ( o ) ，o ) ) 一d ( y ；o ) ，( 力) 2 8 石 万 ，(【 = 七从 。； 。：皇垒坠呈些篁耋里羔墅些鎏二。一 4 2 2 构造局部结构 f = o + 1 ) m o d 以所求得的中心点为圆心，取与圆心距离为尺m i n 到r m a x 之间的细节点组成 局部特征点集，即图4 3 所示的环形区域，以这个局部结构为对象，求取三角基准 点，这样一方面简化了基准点求取的计算，提高了程序的执行效率；另一方面， 也在一定程度减小了上文所述的三角形全等但不是基准点对情况的概率，在一定 意义上提高了算法的识别率。 4 2 3 基准点定位 ji r ) 卢产a o 加o 鹄。一lx 厂。 k 峰义么： k 夕 夕 图4 _ 3 构造局部区域示意图 在局部结构上求取基准点的具体过程如f ： ( 1 ) 假定两个含有不同数量的集合p 仞。，p 2 ，p 。) 和q ： g 。，g ：，g 。) 为分别由 模板和输入图像所产生的局部细节点集。任意取两个局部结构中的点p ，和g j ，判 断它们的类型是否相同，如果类型相同，则p ，和g ，可能为基准点对，执行步骤2 ； ( 2 ) 判断距离p ，和g ，最近点p 。，g 。和次近点p 2 ，9 2 的类型是否相同，如果类型 也相同，则p ，和g ，可能为基准点对，执行步骤3 ，否则返回步骤1 ； ( 3 ) 判断以上述三点为顶点的三角形的边长是否大致相等，即ib p 。矧g ，g - i ， 2 9 青岛理工大学工学硕士学位论文 lp ，p 2 | lg 9 2l ，lp l p 2i ig 。9 2i ，如果符合条件，则执行步骤4 ，否则返回步骤1 ； “) 判断以上述三点为顶点的三角形对应边的角度差是否大致相等，即 鲻，铭，铭铭，如果符合条件，则认定p ，和g 为基准点 对，计算旋转因子p = 1 3 ( q 1 + 幺2 + 研2 ) ，否则返回步骤1 ； 4 3 实验结果及分析 本文根据改进基准点定位算法，结合4 1 2 、4 1 3 节所述的极坐标变换和可变 界限盒匹配方法，在双核2 9 3 g h z 、2 g 内存的计算机上对国际指纹识别竞赛公布 的数据库f v c 2 0 0 4d b 3 、d b 4 分别进行了匹配实验，并与文献 5 9 算法作了比较。 该数据库共有来自1 0 0 个手指的8 0 0 幅指纹图像，各算法消耗的时间均值如表4 _ l 、 表4 2 所示，其r o c 曲线如图4 4 、图4 5 所示。 表4 1 各算法在d b 3 上消耗的时间均值 基准点定位校正匹配总消耗时间 本文算法 1 8 9 2 m s 3 3 m s1 9 2 5 m s 文献 5 9 算法 2 3 1 1 m s 3 1 m s 2 3 4 2 m s 表4 _ 2 各算法在d b 4 上消耗的时间均值 基准点定位校正匹配总消耗时间 本文算法 1 5 2 7 m s 3 2 m s1 5 5 9 m s 文献 5 9 】算法 2 0 7 3 m s 3 3 m s2 1 0 6 m s 从表4 1 及表4 2 可以看出，本文算法在基准点定位的时间上比文献 5 9 】算法 少，从而节省了总的匹配时间，这是由于本文算法是在局部结构中寻找基准点， 而不是所有的细节特征点集。 垒坠塑兰三塑些竺壑堡乙二一 一文献【5 9 】算法 一本文算法 l o 图“各算法在d b 3 上的r o c 曲线 文献 5 9 】算法 本文算法 图4 _ 5 各算法在d b 4 上的r o c 曲线 评价指纹匹配算法的性能的主要指标有r o c 曲线( r e c e i v i n go p e r 池gc u n ，e ， 接收机工作特性曲线) 线下面积和e e r ( e q u a le n 0 rr a t e ，等错率) 。其中r o c 曲线 用于描述自动指纹识别系统的工作特性，曲线上的每一个点都是由某个匹配判决 条件下f 胍和n 吼瓜所确定的，而等镨率e e r 则是指f 胍和删r 相等时f m r 的取值。 所谓f m r ( f a l s em a t c hr a t e ，错误匹配率) 是指在统计意义上人群中手指被错 误识别的比率；而f n m r ( f a l s en o n m a t c hr a t e ，错误未匹配率) 是指在统计意义上 人群中手指不能被识别的比率；因而，任何自动指纹识别系统都应该尽量保证具 3 i ， 氢 觚 3 一 盛苫蠹 青岛理工大学工学硕士学位论文 有较低的f m r 和n m r 。其具体计算公式如式( 4 8 ) 、式( 4 9 ) 所示： 凇：了_ 善坐型雩坠竺l _ 1 0 0 ( 4 8 ) ，口西p ，咒口f ( 历，l “力l + c b ，7 p c f ，九口f c 矗聆“所 、7 撇：墨堕! ：翌旦翌竺! 丝：竺竺 2 0 纪z ，z “m 1 0 0 ( 4 9 ) 式中，励厶p 一所口砌一刀绷指错误匹配的指纹数目，c d 艘甜一所口砌一以“m 为正确匹 配的指纹数目；而厶p ，l d 珂m 口砌以姗是指错误不匹配指纹的数目，乃勉z 删埘是 指整个比对过程中，指纹匹配的总次数； 结合图4 4 及图4 5 可以看出，本文算法比文献【5 9 算法的r o c 曲线更接近原 点，即线下面积更小，而且当f m i b n 卟很时所得的e e r 更低，说明本