一种改进的Mean Shift指纹图像分割算法*

王科飞, 王 慧

(1. 吉林工商学院 信息工程分院, 长春 130062； 2. 长春工业大学 计算机技术与工程学院, 长春 130012)

由于每个人的指纹都有唯一可测量特征点的特殊属征， 因此, 指纹识别是一种可靠的鉴别身份方式[1-2]. 指纹识别就是通过分析指纹的全局特征和指纹的局部特征确认一个人的身份, 广泛应用于数据通信、 公共安全、 金融安全、 刑侦、 信息安全和医疗等领域[3]. 指纹识别系统(automatic fingerprint identification system, AFIS)由指纹图像采集环节、 指纹图像预处理过程、 指纹增强环节、 特征提取、 指纹分类和指纹匹配环节等部分组成[4-5]. 而指纹图像分割归属于指纹图像预处理， 提高特征提取的精确度是指纹识别的首要目标， 分割处理是其实现的重要方法， 该过程要求尽量去除无效区域， 尽量完整地保留有效区域， 因此要求分割算法具有较高的精准度.

作为指纹图像预处理的重要组成部分, 图像分割的目的是把指纹有效区域(即前景区域)与背景区域和模糊区域(即部分质量较差、 在后续处理中很难恢复的区域)进行有效分离[6-8], 以便使后续特征提取和特征匹配过程的处理能在有效指纹区域进行. 本文分析了传统指纹图像分割算法的优缺点, 并提出一种改进的Mean Shift指纹图像分割算法. 结果表明, 该算法能准确提取指纹图像, 并能有效去除噪声, 保证了指纹区域的完整性和有效性.

1 传统指纹图像分割算法

传统指纹图像分割算法主要有基于灰度方差的图像分割算法、 基于方向信息的图像分割算法及基于角部灰度均值的图像分割算法[9].

基于灰度方差分割方法： 先对指纹图像进行分块, 然后分别计算每个块内像素点的灰度均值和方差, 再根据指纹图像的质量确定方差的阈值. 图像质量越高, 阈值越大; 反之, 图像质量越低, 阈值越小. 通常根据一幅指纹图像的整体方差和每块的局部方差最大值确定, 把指纹图像的每一块与阈值进行比较, 完成对前景区域或背景区域的确定[10-11]. 指纹图像前景区域由指纹脊线与谷线组成, 前景区域中指纹脊线与谷线的灰度差较大, 所以它的灰度统计特性中局部灰度方差也较大[12]. 此外, 对于指纹背景区域图像, 其局部灰度方差却较小. 因此, 可以利用图像的局部方差对指纹图像进行分割, 该方法即为局部灰度方差分割法. 在应用中, 对于质量较好、 高对比度图像使用这种分割方法效果较好. 但实际应用中由于环境的不同, 相对于低对比度或噪声图像, 导致该方法通常不能很好地检测出图像中的噪声区域, 因此其分割效果通常不理想[13-14].

方向图像的分割方法： 在区分指纹区域及背景区域问题上, 直接根据指纹区域纹理的方向性实现. 对于最常用的梯度法方向图分割[7]： 先利用梯度算子计算出指纹图像中每个像素点的梯度向量(Gx,Gy)T, 其中:Gx表示水平方向梯度分量;Gy表示垂直方向梯度分量. 然后将梯度分量的方向扩大一倍, 得到向量(Gx′,Gy′)T, 则

(1)

求平均梯度向量, 得到

(2)

其中w×w为局部邻域大小.

根据平均梯度方向可求得每个像素点纹线的方向

(3)

并求出每个像素点的方向一致性度量

(4)

则每个w×w块的方向一致性度量为

(5)

因此, 该方法只有在方向性引导的指纹区域才能较准确地分辨出指纹区域. 但应用中出现的纹线不连续、 单一灰度等方向难以正确估计的区域及中心、 三角附近方向变化剧烈的区域, 使用该方法直接用于分割的效果均不理想.

2 基于改进的Mean Shift指纹图像分割算法

2.1 Mean Shift的工作原理 对于给定的d维空间, 存在n个样本xi(i=1,2,…,n), 核函数的密度估计如下:

(6)

其中K(x)=k(‖x‖2)表示核函数, 这里剖面函数k满足非负、 非增和分段连续. 通过核函数K(x)可计算出点x的Mean Shift向量:

(7)

定义g(x)=-k(x), 可得其对应的核函数

G(x)=g(‖x‖2),

(8)

则mK(x)可修改为

(9)

定义yj(j=1,2,…), 如果x=yj为核的当前位置, 则下一个中心位置yj+1为

(10)

通过迭代地执行式(3)直至收敛, 可得

mK(yj)=yj+1-yj.

(11)

2.2 改进的Mean Shift分割算法的实现 针对指纹图像的特点, 本文改进了Mean Shift分割算法, 把经过初始分割的每个区域Bj抽象为一个样本点. 在区域Bj中, 将灰度信息的均值作为相应样本点的均值向量:

(12)

其中:n表示区域Bj中像素点的个数;xi表示Bj中第i个像素点的灰度值.

算法步骤如下：

1) 将初始指纹图像划分为k个区域, 每个区域记为Bj(j=1,2,…,k)；

2) 分别计算每个区域Bj的灰度均值, 得到均值向量记为Mj；

4) 如果存在Ci,Cj(0

5) 将分割区域内和边界填充颜色；

6) 结束.

3 实验结果

实验选用FVC2004指纹库中的DB1库和本文所收集到的指纹库进行本文算法测试, 并与Mean Shift分割算法进行比较. 结果表明, 传统Mean Shift分割算法的平均分割错误率为5.2%, 而本文改进算法的平均分割错误率为4.1%, 可见本文提出的改进Mean Shift分割算法的平均分割错误率明显低于传统的Mean Shift分割算法. 由于本文选用的指纹库有DB1库及本文所收集的随机人员的指纹库, 表明本文提出的算法适应性较强, 有较好的分割性能.

[1] NIE Gui-jun, WU Chen. Studies on Continuously Distributed Directional Image in Automated Fingerprint Identification System [J]. Journal of Image and Graphics, 2005, 10(3): 316-319. (聂桂军, 吴陈. 自动指纹识别系统中连续分布方向图的研究 [J]. 中国图象图形学报, 2005, 10(3): 316-319.)

[2] LI Peng, SONG Shen-min, CHEN Xing-lin, et al. Iterative Sigma Point Particle Filter in Target Tracking Onreentry [J]. Journal of Jilin University: Engineering and Technology Edition, 2009, 39(6): 1585-1589. (李鹏, 宋申民, 陈兴林, 等. 基于迭代sigma点粒子滤波的再入目标跟踪 [J]. 吉林大学学报： 工学版, 2009, 39(6): 1585-1589.)

[3] CAI Xiu-mei, ZHANG Yong-jian, LIANG Hui. Fingerprint Image Segmentation Algorithm Based on Variance and Orientation [J]. Modern Electronics Technique, 2011, 24(12): 111-113. (蔡秀梅, 张永健, 梁辉. 结合方差和方向的指纹图像分割算法 [J]. 现代电子技术, 2011, 24(12): 111-113.)

[4] Jain A K, Prabhakar S, Pankanti S. On the Similarity of Identical Twin Fingerprints [J]. Pattern Recognition, 2002, 35(8): 2653-2663.

[5] LI Yun-qi. Color Image Enhancement Algorithm [J]. Journal of Jilin University: Information Science Edition, 2012, 30(1): 83-87. (李蕴奇. 彩色图像增强的改进算法 [J]. 吉林大学学报： 信息科学版, 2012, 30(1)： 83-87.)

[6] Poorna B. Genetic Algorithm for Fingerprint Matching [J]. WSEAS Transactions on Information Science and Applications, 2006, 3(6): 1173-1178.

[7] WANG Yu-ru, LIU Jia-feng, LIU Guo-jun, et al. People Tracking Based on Multi-regions Joint Particle Filters [J]. Acta Automatica Sinica, 2009, 35(11): 1387-1393. (王玉茹, 刘家锋, 刘国军, 等. 基于多区域联合粒子滤波的人体运动跟踪 [J]. 自动化学报, 2009, 35(11): 1387-1393.)

[8] Mehtre B M, Muthy N N, KaPoor S. Segmentation of Fingerprint Image Using the Direction Image [J]. Pattern Recognition, 1987, 20(4): 429-435.

[9] Comaniciu D, Meer P. MeanShift: A Robust Approach toward Feature Space Analysis [J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2002, 24(5): 603-619.

[10] Comaniciu D, Ramesh V, Meer P. Real-Time Tracking of Non-rigid Objects Using Mean Shift [J]. Compute Vision and Pattern Recognition, 2000, 2: 142-145.

[11] LI Wen-hui, ZHOU Qiang, WANG Ying, et al. Adaptive Tracking Algorithm Based on Particle Filter-Mean Shift [J]. Journal of Jilin University: Engineering and Technology Edition, 2012, 42(2): 407-411. (李文辉, 周强, 王莹, 等. 基于均值偏移粒子滤波的自适应跟踪 [J]. 吉林大学学报： 工学版, 2012, 42(2)： 407-411.)

[12] DI Hui, YU Qi-feng, ZHANG Xiao-hu. An Algorithm for Infrared Image Enhancement Based on Gray Scale Transforms [J]. Journal of Applied Optics, 2006(1): 1123-1128. (邸慧, 于起峰, 张小虎. 一种基于灰度变换的红外图像增强算法 [J]. 应用光学, 2006(1): 1123-1128.)

[13] Capel D, Zisserman A. Super-Resolution from Multi Views Using Learnt Image Models [C]//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Kauai, USA: IEEE, 2001: 627-634.

[14] SHAN Cai-feng, TAN Tie-niu, WEI Yu-cheng. Realtime Hand Tracking Using a Mean-Shift Embedded Particle Fileter [J]. Pattern Recognition, 2007, 100(7): 175-197.