结合改进遗传算法与局部阈值法的指纹图像分割*

王群峰 徐迎晖

（广东工业大学自动化学院）

结合改进遗传算法与局部阈值法的指纹图像分割*

王群峰 徐迎晖

（广东工业大学自动化学院）

在改进型遗传算法和局部阈值法的图像分割技术基础上，提出一个相互融合的方法。与融合前的 2种算法相比，改善了由于图像边界分割不完全和局部模糊不清造成无法分割的问题。实验结果表明：这种融合的方法比单独使用1种方法分割效果更好。

改进型遗传算法；局部阈值法；指纹图像；图像分割

0 引言

在自动指纹识别系统中，采集指纹后需对指纹图像进行一系列的预处理。其中，图像分割的好坏对后续处理影响很大。指纹图像包括前景区和背景区。由于背景区存在大量噪声，指纹图像分割就是要将背景区域从指纹图像中最大限度地分离出去，这样既减少伪特征数量，提高特征提取的准确率，同时节省处理时间。

指纹图像分割一般是根据一种或者多种图像信息进行分割。采用的方法主要有灰度阈值、方向图信息、纹线频率、纹理框架结构和信息熵等。其中，灰度阈值计算比较简单，且利用阈值进行指纹图像分割一直是众多学者研究的热点，并已提出很多阈值选取方法。如大津展之提出的最大类间方差法[1]，该方法是全阈值分割法，虽然其简单快捷的性能优于其他灰度直方图法，但大多数图像不可能只有一个波谷而使图像明显地分为2部分，故单独使用该方法存在较大缺陷；Kapur等提出最佳熵阈值方法[2]，该方法应用信息熵的知识，寻找使指纹图像信息熵最大的阈值进行分割，其原理比较简单，但指纹信息的概率密度函数的计算是个难点；还有早期的基于自动阈值选择法和均匀化误差阈值法，都是寻找最佳阈值进行图像分割。以上几种方法都是基于单一的全阈值进行指纹图像分割，应用在其他图像处理时，具有反应快、时间短等特点。但指纹识别系统要求指纹图像分割的精度较高，单一的全阈值分割法无法满足要求。

在指纹采集过程中，光照、汗液、按压力度不均等都会对指纹图像产生很大的影响。若采集到的指纹灰度不均，局部对比度低，阈值法很难达到最佳的分割效果，但利用局部阈值法进行指纹图像分割，局部对比度低的问题会得到改善。局部阈值法分割主要依赖于子块图像的大小和领域像素的局部特性，故对指纹图像的前景与背景对比度并不敏感。其缺点是当子块图像在指纹图像边缘时，会出现指纹图像边缘分割不完全现象。

选择图像分割算法时，需考虑既能减少分割过程时间，又能有效保留指纹信息，优化指纹识别系统的处理性能，并且面对不同质量的指纹分割具有良好的鲁棒性。本文根据全阈值和局部阈值法的优缺点，在对不同指纹图像分析及分割算法研究的基础上，提出了基于改进的遗传算法和局部阈值法融合的指纹图像分割法。

1 改进的遗传算法

1.1 传统遗传算法

遗传算法[3]是一种多目标、自适应和具有强大搜索能力的处理工具。它具有并行搜索能力，应用于图像分割的最佳阈值求取，可大大缩短寻找最佳阈值的时间。传统遗传算法常根据个体的适应度大小采用轮盘赌选择策略[4]，其基本思想是根据染色体适应度的比例确定个体的被选取概率或生存概率。这样选择算子虽然简单，易于实现，但存在2个问题：1) 局部最优解，在进化初期适应度很高的个体被选择的概率很大，进而繁殖出很多后代，这样种群单一而无法继续进化使搜索陷入局部最优；2) 收敛性差，进化后期接近最优解时，在最优解附近来回摆动，收敛速度慢。因此，在遗传算法的基础上提出了改进遗传算法。

1.2 改进遗传算法

1.2.1 改进选择算子

本文选择算子的改进采用了逐次减少最大值的选择法。为使种群具有多样性将轮盘赌选择改为直接选取最优多个个体的方法。其基本思想是选择计算个体适应度后，进行排序后再选择，同时若选定某个个体后，下次再计算适应度时相应地减少该个体比例的大小。重复此操作，直至产生种群大小为M ，这样既保证种群的多样性，又减小早熟的可能性。具体过程如下：

1) 选择计算比例选择算子，计算比例公式

这种选择算子只与个体适应度的次序有关，与适应度大小没有直接的联系。显然这种方法不仅能够保证最优个体被选中，而且选择后的种群不会单一。

1.2.2 交叉和变异概率的改进

从式(2)、式(3)可以看出，当待交叉个体或待变异个体适应度值等于最大适应度值时，交叉和变异概率为零，这种状况将导致局部解不发生变化或在附近来回摆动，此时优良个体却不一定是全局最优的，这样就出现了局部最优解现象。

为防止交叉和变异概率出现为零现象，可使用式(4)、式(5)改进自适应交叉和变异概率。动态确定交叉和变异概率，既可避免进化过程不收敛，又可以防止优良的基因因为变异而被淘汰。改进后的遗传算法，种群优良个体可以从局部最优解中摆脱出来，进而获得全局最优解。

2 遗传算法在指纹图像分割中应用

在指纹图像分割中，种群的个体是图像的灰度值。运用遗传算法解决指纹图像分割问题时必须进行4个重要的步骤：1) 把指纹图像灰度值编解码成染色体；2) 调整初始种群规模及繁殖代数；3) 设计目标适应度函数；4) 生殖参数的调整与确定。遗传算法在图像处理中应用流程如图1所示[3]。

图1 遗传算法在图像分割中应用流程[3]

2.1 编码和解码

因为指纹图像的灰度值范围为0～255，所以使用8位的二进制码将各个染色体编码，这样每个染色体代表一个分割阈值，即00000000～11111111之间任何数值都代表一种可能的阈值。当进化趋向它们之间的任何值时，二进制所对应值是最佳阈值。

2.2 初始化种群及种群规模

初始群体的规模会影响遗传算法的执行效率。种群规模太小时，意味着搜索空间小，搜索效率差，最大可能会早熟陷入局部最优解；种群规模太大时，计算复杂性增加。本文设定每代种群的个数为25，最大繁殖代数为200，初始解是采用随机函数产生25个0～255之间的随机数。

2.3 适应度函数的确定

利用适应度函数评估解的优劣，通常在编写适应度函数过程中，所得函数值越大，说明图像的前景和背景的差别就越大，分割效果越好。本文采用 Otsu法提出的适应度函数?，进行指纹图像分割阈值的选取。

2.4 生殖参数选定

3 局部阈值分割算法

由于指纹扫描仪所处环境等原因，采集的指纹图像会存在噪声，例如明暗不均、区域对比度不大等。指纹原图如图2(a)所示。若只用一个固定的全局阈值对整幅图像进行分割，即使阈值选取得非常合理，也不能兼顾图像的各种情况。改进前遗传算法处理的图像如图2(b)所示。本文通过改进型遗传算法进行图像分割，指纹图像的边界清晰，但是在原图像中亮度较暗的区域，出现严重的模糊现象。改进型遗传算法处理的图像如图2(c)所示。

基于上述现象，提出一种局部阈值分割算法对指纹图像进行分割，具体步骤如下：

2) 计算每个子块内像素的梯度值。利用 Sobel算子计算出水平梯度和垂直梯度，并且求出梯度的幅值。如式(8)～式(10)所示。

5) 分割处理后，再用3×3邻域平滑滤波器对所得指纹图像进行平滑处理。

该分割法抗噪能力强，计算简单，易于实现，但也有缺点。若子图像在目标区域或背景区域，可以根据统计结果对其进行分割，效果良好；若子图像恰好在边界时，使用该方法将产生失真，此时局部阈值法可能会失效；若背景区域和前景区域灰度变化不明显时，使用这种方法边缘部分存在很大的噪声。局部阈值法处理后的图像如图2(d)所示。

4 两种算法结合

图2 指纹原图和4种算法处理后的图像

图3 结合两种算法的处理流程

5 实验结果分析

用Matlab R2010b编程实现本文算法。由图2(b)和图2(c)的仿真结果可看出，虽然后者效果较好，但不明显，且出现粘连现象。其原因可能是原指纹图像前景与背景对比度低。由图2(c)和图2(d)的仿真结果可知，利用局部阈值法可改善粘连现象，但引入了边缘分割不完全现象。其原因是指纹图像分块时，部分小块落在背景区。由图2(c)～图2(e)对比可知：结合改进型遗传算法和局部阈值法的指纹图像分割效果比单独使用其中一种方法的效果要好。

[1] 李贤阳,黄婵.一种结合改进Otsu法和改进遗传算法的图像分割方法[J].实验室研究与探索,2012,31(12):57-61.

[2] 宋家慧.基于遗传算法的最大熵阈值的图像分割[J].电子工程师,2005,31(2):60-63.

[3] 雷英杰,张善文. Matlab遗传算法工具箱及应用[M].西安：西安电子科技大学出版社,2004.10.

[4] 杨平,郑金华.遗传选择算子的比较与研究[J].计算机工程与应用,2007,43(15):59-62.

[5] 曹道友,程家兴.基于改进的选择算子和交叉算子的遗传算法[J].计算机技术与发展,2010,20(2):44-47.

Segmentation of Fingerprint Images Using Improved Genetic Algorithm and Local Threshold Method

Wang Qunfeng Xu Yinghui
(Dept. of Automation, Guangdong University of Technology)

This paper puts forward an improved adaptive genetic algorithm, and then combined with the advantages of the improved genetic algorithm and local threshold value method of image segmentation technology, a fusion method is proposed. Compared with the two algorithms, the problems of boundary segmentation of incomplete and ambiguous are improved. The experimental results show that the method can obtain better segmentation than a single method of them.

Improved Genetic Algorithm; Local Threshold; Fingerprint Image; Image Segmentation

王群峰，男，1987年生，硕士研究生，主要研究领域：图像处理、模式识别。E-mail: 190554341@qq.com

广东省工业高新技术领域科技计划项目 (2013B010401028）

徐迎晖，男，1977年生，博士，副教授，硕士研究生导师，主要研究领域：信息隐藏与保密通信、语音与图像信息处理、电路/嵌入式/DSP系统应用等。