指纹图像细化算法的研究

钱 超， 王福明

（中北大学，信息与通信工程学院，山西太原 030051）

0 引言

指纹识别的效率和好坏很大程度上依赖于指纹图像的预处理。一个好的预处理方法将大大减少伪特征点数,减少对原始采集图像好坏的依赖。一个优秀的生物特征识别系统要求能实时迅速有效地完成其识别过程。所有的生物特征识别系统都包括如下几个处理过程：采集、比对和匹配。指纹识别处理也一样，它包括指纹图像采集、指纹图像预处理、特征提取、特征值的比对与匹配等过程。使用指纹识别方式的优点在于它的可靠、方便且容易被接受[1]。

预处理在整个自动指纹识别系统的过程中是很关键的一步，是正确地进行特征提取、匹配等操作的基础。采集到的指纹图像由于各种原因的影响，是一幅含多种不同程度噪声干扰的灰度图像，指纹脊线可能被断开、桥接或模糊等，而含有大量噪化的指纹脊线结构会影响着自动指纹识别系统的性能。指纹预处理是指纹特征提取前的不可缺少的一个重要环节，主要用于突出指纹图像中的纹理、方向信息，消除或者减弱噪声等无用信息。指纹图像预处理通常包括指纹图像分割、图像增强、二值化、细化等[2]。

1 指纹图像二值化

指纹图像二值化后，其纹线宽度是不均匀的，这是因为原始图像的质量受到压力大小的影响和图像采集过程中噪声的影响而造成的。虽然纹线的宽度并不包含指纹的特征信息，但它的不均匀性会影响指纹特征的提取，并且指纹识别只对纹线的走向感兴趣，并不关心它的粗细，因此为了减小数据量，提高识别准确性，应对指纹图像进行细化处理[3]。

指纹图像细化方法的一种是可以直接从灰度图像进行，但难以寻找纹线的中心点；另一种则是广泛使用的，把灰度线条图像变成二值图像再进行细化。细化是删除指纹纹线的边缘像素，使之只有一个像素宽度。细化时应保证纹线的连接性、方向性和特征点不变，还应保持纹线的中心基本不变。指纹图像的细化是接受二值化后的指纹图像，并为指纹图像的特征提取和匹配提供图像。细化方法应满足下列条件：

(1)迭代必须收敛。(收敛性)

(2)不破坏纹线的连接性。(连接性)

(3)不引起纹线的逐步吞食。(拓扑性)

(4)保护指纹的细节特征。(保持性)

(5)骨架纹线的宽度为一个像素。(细化性)

(6)骨架尽可能接近纹线中心。(中轴性)

(7)算法简单、速度快。(快速性)

细化从实现的方法上分，可分为两大类：一类是从外到内逐点剥去二值图像的边缘点，如Hildth算法；令一类是从内到外，找到某一中间点，然后按扫描方向寻找其8邻域内也为线条纹中间像素的点，逐次取得细化线。第一种方法中间定位性比较好，易于实现，但往往要经过若干次迭代运算才能得到细化线，速度较慢：第二种方法能保持较好的连通性，但情况复杂，中间定位不准。细化算法按细化处理过程可分为串行细化、并行细化和串并行混合细化。串行细化一次只能处理一个像素，下次操作由上次的操作结果决定。并行细化算法是同时对满足给定条件的像素进行处理，即一次处理所有像素的一个子集[4]。

按细化后图像的连通性可将细化算法分为4连通细化、8连通细化和混合连通细化，4连通指的是细化后图像在水平垂直4个方向上的连通，8连通是细化后图像在水平垂直4个方向再加上正反45度共8个方向上的连通，混合连通是指细化后图像既有4连通也有8连通。其他常用于指纹细化的算法还有方向图中心扫描细化算法、纹线跟踪细化算法等。

浅阅读是走向深阅读过程中的起步阶段。在这个阶段，阅读主体可以大致拟出阅读的提纲或思维导图，至少在脑中会形成对阅读内容的总体印象，判断出下一步需要详读的部分和略读的部分。

现有的指纹细化算法存在很多问题，像细化不彻底、纹线吞噬、骨架偏离纹线中心、细化效率低下等。其中纹线细化不彻底特别是纹线分叉点处细化不彻底，影响纹线分叉点的正确提取。纹线的吞噬往往导致提取的纹线端点位置移动较大。

通过对一般细化算法存在的问题，进行改进，以减少伪特征的个数，对细化算法中的消除模板和保留模板进行改进，并模糊了消除模版的概念，扩大了消除模板的范围[5]。

2 改进的OPTA算法

OPTA算法是一种典型的基于模板的图像细化算法（如图1至图3所示），算法核心是通过应用消除和保留这两套模板来达到对原图细化的目的。OPTA算法用到的是与其相邻的10个像素。从图像的左上角元素开始进行，首先用该像素的8个邻域与8个细化模板(消除模板)相匹配，若与任何消除模板都不匹配，不做任何改变；若与其中的任一消除模板匹配，则再与保留模板相匹配，若存在与一个保留模板匹配，则不做任何改变，若与任何保留模板都不匹配，则把该像素改为0。该算法按从左上角到右下角的顺序进行，处理完一个过程即为一次迭代，“迭代”反复进行，直到没有一个像素的值被改变为止。其中迭代的次数依赖于图像的大小、纹线的形状和图像的质量[7]。

图1 OPTA算法所取的邻域

图2 OPTA细化算法的消除模板(×表示任意，可以为0或1)

图3 OPTA细化算法的保留模板(×表示任意，可以为0或1)

下面给出几个细化中的定义：

目标点与背景点：目标点指像素值为1的点，背景点指像素值为O的点。

单像素宽：考察纹线上每一点的8邻点，纹线端点的8邻点中只有一个目标点，纹线连续点的8邻点有两个目标点，纹线分叉点有3个目标点，且每点8邻点最多只有3个目标点。符合上述条件即为单像素宽。

边界点：属于目标点，且其4邻点中至少有一个为背景点。

端点：属于边界点，且其8邻点中只有一个属于目标点。

关键点：删除该点后会引起纹线的不连通，又叫做断点。

消除模板：判断是否符合消除的条件。

保留模板：对符合消除条件的像素，判断与其相邻的同一行或同一列是否有非0点，如没有则直接删除该点，否则保留该点[9]。

OPTA算法能满足收敛性、连接性、拓扑性和保持性，能得到较好的细化效果。但该算法得到的细化骨架存在在分叉点处细化不彻底，细化后的纹线不光滑，纹线有较多毛刺且纹线扭曲不在纹线中心的问题。因此不满足细化的中轴性和细化性。同时，它采用两个不同大小模板分两次进行计算，其速度也受到影响。为了解决OPTA算法存在的问题，人们提出了一种改进的OPTA算法，改进后的OPTA算法（见图4）消除模板仍采用OPTA的消除模板。而在保留模板中，当前中心点的去留除了与消除模板有关外，还取决于另一个“l"值周围点的情况：若该“1"值为中心的3×3邻域和消除模板相同，则该“1"值应该被删除，否则删除当前中心点。

图4 改进的OPTA算法的保留模板

3 改进的OPTA算法的不足及改进

改进后的OPTA算法仍然存在一定的局限性，突出表现在某些纹线方向位置容易产生毛刺。经过研究发现，毛刺的出现对纹线方向十分敏感。纹线方向角在第2像限的时候容易出现毛刺，特别是纹线近似水平和垂直的时候.毛刺的出现尤其明显。故推测毛刺的产生和模板不完全对称有关。对于图5(a)，可以看到2个小的毛刺，但是细化没有去掉。对于5(c)中的纹线，细化完成后同样产生了毛刺。主要原因是由于消除模板中没有包含这种情况。

图5 毛刺的细化

分叉处的细化不彻底主要原因是由于消除模板不完善。如图6（a），第四行第三列的点是个多余的像素点，删除这个点并不影响纹线的连通线；对于图6（c），第二行第三列的点是多余的像素点，造成了不完全的细化，但若只是删除该点，又会造成纹线的中断，所以应对其进行一定程度的细化，即将第二行第三列的点删除，即置为0，同时将第二行第四列的点置为1，保持了纹线的连通性[10]。

图6 分叉点处的细化

针对上文中对毛刺的产生和分义处的细化小彻底的原因分析，本文使用了针对性的消除模板和保留模板。针对毛刺的消除模板如图7。针对未完全细化的情况，引入特定的消除模板，如图8所示。

图8中，a-d是对应于第一种未完全细化的情况的消除模板，e-h是对应于第二种未完全细化情况的消除模板。a-d模板中的中心点为应该删除的点，e-h中荻色背景的点是进行了变换，即将模板中有灰色背景的对应位置中的0变换成1，而l变换成0。选样，第二种未完全细化的情况就得到了有效的解决。

图7 针对毛刺的消除模板

图8 针对未完成细化的消除模板

图9 修正后的消除模扳(一)

以在OPTA提出的消除模板为基础，在基础上添加上述12个消除模板；以文献[6]提出的保留模板为基础.在消除模板的基础上修正保留模板。修正后的结果如图9～图11所示。

图10 修正后的消除摸板㈡

图11 修正后的消除模板(三)

把消除模板分为3类：类一：如图 9中(a)-(h)，类二：如图10中(i)-(p)，类三：如图11中(q)-(t)。(i)-(p)是属于可直接删除的，不需要进行保留模板匹配，因为(m)-(p)是OPTA原消除模板的特例，这类模板应先于OPTA原消除模板进行匹配，以免重复计算。细化从图像的左上角开始进行，对于每一像素取其8个邻域的像素，与类二的消除模板匹配，若存在一个模板与其匹配，则删除该点(即修改为0)。否则与类一、类三匹配，若不存在模板与其匹配，则停止：若存在一个模板与其匹配，记匹配的消除模板为m，并取该像素的i5邻域的像素，与保留模板相匹配，如不存在任何保留模板匹配时，若m为类一，则删除该点，否则，对相对应的模板的对应位置进行变换。

4 实验结果及分析

在采用OPTA算法对指纹图像进行细化操作所得的细化结果中产生的毛刺很多，在三叉点处细化不全，在处理后的结果图中可以看到有些指纹的纹线发生了断裂的情况，出现了一些相互不连接的断线。破坏了指纹本身的连接性和拓扑性。改进的OPTA细化算法与OPTA算法相比在细化整体效果上有了明显提高，尤其是对细化过程中产生的毛刺和细化不彻底的处理得到了很好的效果，纹线连接性好。在计算速度方面，OPTA算法采用两个大小不同的模板进行两次计算，计算速度慢，改进的OPTA算法克服了OPTA的这个缺点。经过以上的分析可知，本文中采用MATLAB7.0进行实验,指纹库采集分辨率为500 dpi,指纹采集设备为PIS2004光学指纹采集仪,图像尺寸大小为640×480，实验仅作同源样本间的交叉比对。这表明指纹频率能量能准确反映样改进的OPTA细化算法是合理可行的，并且能得到较好的细化结果，满足细化处理的要求。实验结果如图12所示。

图12 实验结果

[1]陈茂林,戚飞虎.基于最优梯度估计及小波变换的指纹图像处理技术[J].上海交通大学学报,2001,35(2):181-183.

[2]Ling Hong,Wang Yfei,Anil K Jain.Fingerprint image enhancement：algorithm and performance evaluation[J].IEEE Transactions on PaRem Analysis and MachineIntelligence,1 998,20(8):777-789.

[3]柯渝.指纹识别系统中的预处理与后处理研究[D].厦门:厦门大学,2004.

[4 ]Jie Zhou,Jinwei Gu.A model—based method for the computation of fingerprints’orientation field[J].IEEE Transactions On Image Processing,2004,13(6):821-835.

[4]周晔华.指纹图像预处理算法研究[D].南京:南京理工大学,2008.

[5]王业琳,宁新宝,尹义龙.指纹图像细化算法的研究[J].南京大学报,2003(7):468-475.

[6]唐海勇,唐世钢,邵岩.线条纹图像的细化[J].哈尔滨理工大学学报,2002(4):50-53.

[7]Jie Zhou,David Zhang,C.Y Wu.Orientation analysis for rotated human facedetection[J].Image Vision Compute,2002(20):257-264.

[8]冯星奎,李林艳,颜祖泉.一种新的指纹图像细化算法[J].中国图象图形学报,1999(10):835-838.

[9]赵伟.指纹图像的预处理和细化算法的研究[D].重庆:重庆大学数理学院,2007.

[10]闰俊红.指纹图像预处理研究[D].呼和浩特:内蒙古工业大学,2006.