一種改進的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.