自动指纹识别算法研究

自动指纹识别算法研究

学术研究

search

自动指纹识别算法研究

刘福元，王玲

（湖南大学电气与信息工程学院，湖南　长沙　４１００８２）

【摘　　要】论文对自动指纹识别系统（Ａｕｔｏｍａｔｅｄ　Ｆｉｎｇｅｒｐｒｉｎｔ　Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ　Ｓｙｓｔｅｍ，简称ＡＦＩＳ）的算法进行了研究，在指纹比对算法方面提出了一种新的方法，此方法不但解决了指纹匹配算法参考点寻找问题，而且不用考虑指纹采集时角度和位移的影响。算法通过了仿真，并给出了各过程指纹处理图片。【关键词】自动指纹识别；预处理；特征点；指纹匹配

【中图分类号】ＴＰ３９１　　　　【文献标识码】Ａ　　　　【文章编号】１００９－８０５４（２００７）　０２－００７０－０３

The study of automated fingerprint identification algorithm

LIU Fuyuan, WANG Ling

(College of Electrical and Information Engineering Hunan University, Changsha 410082, China)

【Abstract】The algorithm is studied in AFIS, and provided a novel algorithm in matching. This algorithm not only couldsolve the problem of finding the referenced point of matching algorithm, but also don't need to considerate the influenceangle and displacement when enrolling. The algorithm has been emulated and provided the processing pictures ofFingerprint.

【Keywords】Automated fingerprint identification; Preprocessing; Minutiae; Matching

匹配、纹理结构匹配、混合的匹配方法。点模式匹配算法很

１　　引言

生物识别技术是依据人的体貌、声音等生物特征进行身份验证的科学解决方案，现有的生物识别技术大致上包括指纹识别技术、掌纹识别技术、视网膜识别技术、虹膜识别技术、面相识别技术、声音识别技术、笔迹识别技术等。作为生物识别技术中最主要的一种技术—指纹识别技术将有着广泛的应用背景。由于受到指纹本身的因素和采集条件的影响，采集到的指纹会受到不同程度噪声的干扰，在指纹匹配之前都要对指纹图像做增强处理。指纹图像增强算法多数是基于方向场的图像滤波算法［１］［２］，本文采用一种基于方向场估计的图像Ｇａｂｏｒ滤波算法。指纹匹配算法是指纹识别系统的核心步骤，传统的匹配算法大致可以分为以下三类：点模式

多，主要有Ｓｈｉｌ－ｈｓｕ　Ｃｈａｎｇ等人［３］的基于二维聚类的快速算法、Ｘｕｄｏｎｇ　Ｊｉａｎｇ等人［４］的基于局部和全局的匹配算法；纹理结构匹配算法主要由Ａ．Ｋ．　Ｊａｉｎ等人［５］提出来的；混合匹配算法由Ａ．　Ｒｏｓｓ等人［６］提及。不管是点匹配算法还是结构匹配算法，点匹配算法［４］中的局部匹配算法，特征点发生了位移或者角度变化，将对匹配算法带来一定的影响；而结构匹配算法［５］中必须寻找指纹中心参考点，然后根据参考点得到指纹码进行匹配，如中心参考点发生了误差，将对指纹特征码带来误差。本文提到的匹配算法完全不考虑指纹的中心点和指纹的角度和位移的影响，只需要得到正确的分叉特征点的信息就可以对指纹进行匹配。

２　　指纹预处理

由传感器取得的灰度指纹图像（见图１）存在一定的噪声干

扰，为了使指纹识别更快、准确率更高，必须对指纹进行一定的预处理。

２．１　方向图估计

指纹的脊线方向已广泛应用于指纹图像增强、纹型的特征提取、指纹自动分类、方向模板的匹配、编码重构等许多

ｗｗｗ．ｃｉｓｍａｇ．ｃｏｍ．ｃｎ

自动指纹识别算法研究

学术研究

Acade关键处理环节。求取指纹方向图常用的方法主要有梯度法、切缝法、抽样法和投影法，而本文综合性能、去噪、计算复杂度等方面采用梯度法求方向场。算法基本思想：在每一个像素点上用梯度算子估计梯度的水平和垂直分量，然后分块最优化各个块中的方向。具体步骤如下：

逐步计算各个像素点上的梯度分量，可以采用３×３大小的Ｓｏｂｅｌ模板计算像素（i，j）的梯度幅值Gx（s，t）和Gy（s，t）。

Sobelx＝｛（－１，０，１）；（－２，０，２）；（－１，０，１）｝

j）为中心的局部方向θ（i，最优方向估计：计算每块以（i，j），取W＝１６，θ

可由下式得：

则取f （i，j）＝１，否则取f （i，j）＝０，可得到图４所示的二值化图。

２．５　细化

本文采用的算法是逐层迭代算法，本算法把一次迭代分为两次扫描，细化过程中由周边向中间逐层细化，细化后的脊线位于原图的中轴。令ＢＮ为３×３窗口内目标像素的个数：

。细化过程重复执行两个步骤：

第一步：从左到右，从上到下顺序扫描图像，对同时满足以上四个条件的像素，如果P１×P３×P７＝０，且P１×P５

×P７＝０，则将其作上标志。

第二步：从左到右，从上到下顺序扫描图像，对同时满足以上四个条件的像素，如果

图１　原始图像　　　图２　指纹方向图　　图３　滤波增强图

P１×P３×P５＝０，且P３×P５×P７＝０，则将其作上标记。

当扫描完整幅图像后，去掉作了标志的像素。重复一、二步骤直到得到单位宽

２．２　脊线频率估计图４　二值化图　　　　图５　细化图　　　　　图６　特征提取图度的线条为止。经过此细化

指纹纹理除了具有稳定的方向性特点外，还具有稳定的频率性特点。在指纹图像的一个局部区域内，脊线和谷线的纹理走向近似平行，同时沿脊谷方向的灰度分布近似正弦包络。脊线频率定义为两条相邻脊线之间间距的倒数，通过定义该包络线中的极大值和极小值，就能计算出相应的脊线和谷线的间距，进而得到脊线的频率，如图２所示。

２．３　指纹增强

本论文所选用的是具有良好的方向和频率选择性的Ｇａｂｏｒ滤波器，偶对称Ｇａｂｏｒ

滤波器定义如下：

过程可以得到单像素的８连通的指纹图像，如图５所示。

３　　指纹特征点提取

脊线端点和分支点是指纹图像中最典型的特征。在指纹自动识别系统中，这两个最基本的特征被参考为特征点。为了确定指纹图像中特征点的具体位置，此算法采用一个３×３的模板来提取指纹特征，中心像素点P０和其周边像素（P１，…，P８），R（n）为周边像素的对应值。可以通过求交叉数C来判定细节特征，C的值相当于某点周围８个像素顺序变化次数的一半，判断公式为：C＝０．５

｜R（i＋１）－R（i）｜，其中

R（９）＝R（１）。如果C＝１，则模板中心为纹线端点；C＝３，则为分支点。扫描完整幅图像后，可以得到其全部特征点（见图６）。

θ为Ｇａｂｏｒ滤波器的方向，f为频率，δx和δy（本文取δx＝δy＝４）为Ｇａｂｏｒ滤波器沿两个坐标轴x和y空间尺度常数，u和v是旋转后的坐标系。图３是经过滤波增强后的图片。

２．４　二值化

二值化目的是把指纹灰度图像变成０和１的两个灰度级的图像，前景点（指纹脊线）取作１，背景点取作０，把指纹脊线提取出来，以便后续处理。根据指纹图像中脊线和谷线宽度大致相等的特点，本文采用局域自适应二值化算法，把指纹图像分成Ｗ×Ｗ（Ｗ为纹线周期）子块，在每一个子块内计算灰度平均值

，若某一点的灰度值f （i，j）＜Avv，

４　　指纹比对

本文提出了一种更方便快捷的比对算法，此算法是根据指纹特征码来进行指纹匹配，每个分叉点在指纹图像中都有属于自己的坐标位置，图像不管如何变化，他们之间的参数关系是不变的，因此根据这一特征，我们可以考虑以分叉点之间存在这种关系作为该图像的特征码。由于任意两分叉点之间有着纹线条数不变的，并且不管指纹图像在录入过程中发生了怎么变化（旋转、位移、局部放大等），分叉点之间纹数条数是一定的，因此我们将分叉点之间的纹数条数作为图像的特征码值。据统计，一枚指纹图像上分叉点的个数都是

信息安全与通信保密 ２００７．２

71

自动指纹识别算法研究

学术研究

search

超过１０个的，并且分叉点的分布存在不规则性，这就使分叉点之间的纹线条数全部相同的概率很小，而且每个分叉点中也有类似的情况，那么出现相同特征码的概率几乎为零，使得以纹线条数作为特征码可以实现比对。假设点Ａ、Ｂ、Ｃ、Ｄ和Ｅ是某指纹图像的所有分叉点，它们之间纹数可用一个完全图来表示，而该完全图的邻接矩阵即为本文所需的特征码。设点Ａ、Ｂ、Ｃ、Ｄ、Ｅ间纹线条数的完全图邻接矩阵１如下所示：

得到指纹图像的特征码，即分叉点间纹线数的邻接矩阵，从而可以对任意两个指纹的图像的邻接矩阵进行比较来实现指纹比对。但是同一手指采样方式的不同导致图像的差异（例如图像与其旋转后的图像），分叉点排列顺序被打乱，采样过程中特征点的丢失或假特征点增加，都将导致邻接矩阵的不同，所以不能使用原始的邻接矩阵直接进行比较，邻接矩阵必须处理过后才能进行比对。对邻接矩阵做如下处理：

—对邻接矩阵的每一行的数据从小到大进行排序，结果如矩阵２所示。

—由于两分叉点之间的指纹数是不会超过两位数，因此将矩阵中数据长度为２的字符串（数据长度不超过两位），不足的字符用０代替，例如７＝＞０７。

—将每一行中的数据按顺序连成一个字符串，因此Ｎ行的矩阵就有Ｎ字符串，整数数组变成一维字符串数组，上式中第一行形成的字符串就为：０００１０２０３０４。

—对一维数组按从小到大的顺序进行排序，最后将数组按顺序连成一个字符串。

通过上述处理，我们将得到一个非常有规律的字符串，这也是指纹图像真正的特征码。而同一指纹的不同图案的特征矩阵（特征点都得相同）即便其特征邻接矩阵不相同，但经过上述处理，最终得出的字符串必然是匹配的。虽然我们在前面算法中对假特征点做了一些处理，但是对个别假的分叉特征点会对比对算法带来比对困难，所以必须要对这些误差进行容错。由于特征点一般都是集中指纹图像的中心四周，对于能够识别的图像，经过处理后减少或增加的特征点数几乎很少，因此本文对指纹图像的容错范围是两个特征分叉点，也就是说两幅图像的特征分叉点数之差最大不超过３个。以下是两幅指纹图像特征码容错匹配的算法：

（１）　设指纹图像Ａ有M个分叉点，指纹图像Ｂ有N个分叉点，且M＞＝N，S＝M－N，S＜＝３，那么则将从Ａ中取M－

72

ｗｗｗ．ｃｉｓｍａｇ．ｃｏｍ．ｃｎ

S个点（这总共将有CM－SM种情况）与Ｂ进行匹配，若匹配，结束匹配，返回匹配成功；否则进入（２）。

（２）　若S＋K＞３，K＝１，结束匹配，返回匹配不成功；否则在Ａ中取M－S－K分叉点与Ｂ中的N－K分叉点进行匹配（这总共将有CM－S－KMCN－KN种情况），若匹配，结束匹配，返回匹配成功；否则K＝K＋１，进入（２）直至结束，返回结果。

５　　结论

本文主要实现了指纹基于Ｇａｂｏｒ的预处理算法和特征点提取算法，而且提出了一种新的字符串匹配算法，该算法主要特征是不需要寻找中心参考点，也不需要考虑采集的指纹图片、模板角度和特征点距离不一致问题，而且可以大大提高匹

配速度。但此算法还存在一些不足：首先，当采集的指纹图片非常模糊，经过预处理后不能得到正确的分叉点和分叉点之间的纹线路数；其次，当指纹图片受到干扰很大时，得到许多虚假的特征点，此算法采用的３个容错分叉点将不能满足要求；最后，该算法在指纹匹配字符串提取方面还有待进一步研究。

参考文献

［１］　Ｌｉｎ　Ｈｏｎｇ　Ｗａｎ，Ｙｉ－　ｆｅｉ　Ｊａｉｎ，Ａ．　Ｆｉｎｇｅｒｐｒｉｎｔｉｍａｇｅ　ｅｎｈａｎｃｅｍｅｎｔ：ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｐｅｒｆｏｒｍａｎｃｅｅｖａｌｕａｔｉｏｎ．　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｔｔｅｒｎ　Ａｎａｌｙｓｉｓ　ａｎｄＭａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，１９９８，２０（８）：７７７～７８９．

［２］　Ｊａｉｎ　Ａ，Ｌｉｎ　Ｈｏｎｇ，Ｂｏｌｌｅ　Ｒ．　Ｏｎ－Ｌｉｎｅ　ｆｉｎｇｅｒ－ｐｒｉｎｔ　ｖｅｒｉｆｉｃａｔｉｏｎ．　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｔｔｅｒｎ　Ａｎａｌｙ－ｓｉｓ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，１９９７，１９，（４）：３０２～３１３．

［３］　Ｃｈａｎｇ　Ｃ　Ｈ，Ｃｈｅｎｇ　Ｆ　Ｈ，Ｈｓｕ　Ｗ　Ｈ，ｅｔ　ａｌ．Ｆａｓｔ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｐｏｉｎｔ　ｐａｔｔｅｒｎ　ｍａｔｃｈｉｎｇ：ｉｎｖａｒｉａｎｔ　ｔｏｔｒａｎｓｌａｔｉｏｎｓ，ｒｏｔａｔｉｏｎｓ　ａｎｄ　ｓｃａｌｅ　ｃｈａｎｇｅｓ．　ＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎ，１９９７，３０（２）：　３１１～３１６．

［４］　Ｊｉａｎｇ，Ｘｕ－ｄｏｎｇ，Ｙａｕ，Ｗｅｉ－Ｙｕｎ．　Ｆｉｎｇｅｒｐｒｉｎｔｍｉｎｕｔｉａｅ　ｍａｔｃｈｉｎｇ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｌｏｃａｌ　ａｎｄ　ｇｌｏｂａｌ　ｓｔｒｕｃｔｕｒｅｓ．Ｉｎ：Ｓａｎｆｅｌｉｕ，Ａ．，Ｖｉｌｌａｎｕｅｖａ，Ｊ．Ｊ．，ｅｄｓ．　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆｔｈｅ　１５ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ．Ｌｏｓ　Ａｌａｍｉｔｏｓ，ＣＡ：ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ　Ｐｒｅｓｓ，２０００：１０４２～１０４５．

［５］　Ａ　Ｋ　Ｊａｉｎ，Ｓ　Ｐｒａｂｈａｋａｒ，Ｌ　Ｈｏｎｇ，ｅｔ　ａｌ．Ｆｉｌｔｅｒｂａｎｋ－Ｂａｓｅｄ　Ｆｉｎｇｅｒｐｒｉｎｔ　Ｍａｔｃｈｉｎｇ．　ＩＥＥＥ　Ｔｒａｎｓ．Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ，２０００，９（５）：　８４６～８５９．

［６］　Ｒｏｓｓ　Ａ，Ｊａｉｎ　Ａ，Ｒｅｉｓｍａｎ　Ｊ．　Ａ　Ｈｙｂｉｒｄ　Ｆｉｎｇｅｒ－ｐｒｉｎｔ　Ｍａｔｃｈｅｒ．　Ｐｒｏｃ．　１６ｔｈ　Ｉｎｔ’ｌ　Ｃｏｎｆ．ＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎ，２００２，３（４）：７９５～７９８．