### Paper Menu >>

### Journal Menu >>

J. Biomedical Science and Engineering, 2009, 2, 656-660 doi: 10.4236/jbise.2009.28096 Published Online December 2009 (http://www.SciRP.org/journal/jbise/ JBiSE ). Published Online December 2009 in SciRes. http://www.scirp.org/journal/jbise Fingerprint image segmentation using modified fuzzy c-means algorithm Jia-Yin Kang1, Cheng-Long Gong1, Wen-Juan Zhang2 1School of Electronics Engineering, Huaihai Institute of Technology, Lianyungang, China; 2School of Computer Engineering, Huaihai Institute of Technology, Lianyungang, China. Email: jiayinkang@gmail.com Received 16 July 2009; revised 31 August 2009; accepted 1 September 2009. ABSTRACT Fingerprint segmentation is a crucial step in finger- print recognition system, and determines the results of fingerprint analysis and recognition. This paper proposes an efficient approach for fingerprint seg- mentation based on modified fuzzy c-means (FCM). The proposed method is realized by modifying the objective function in the Szilagyi’s algorithm via in- troducing histogram-based weight. Experimental re- sults show that the proposed approach has an effi- cient performance while segmenting both original fingerprint image and fingerprint images corrupted by different type of noises. Keywords: Fingerprint; Segmentation; Fuzzy C-means; Histogram; Robustness 1. INTRODUCTION Fingerprint segmentation is an important issue in finger- print recognition system. A fingerprint image usually has to be segmented to remove uninterested regions before some other steps such as enhancement and minutiae detec- tion so that the image processing will consume less CPU time. A fingerprint image generally consists of different regions: non-ridge regions, high quality ridge regions, and low quality ridge regions. Fingerprint segmentation is usu- ally to identify non-ridge regions and unrecoverable low quality ridge regions and exclude them as background [1]. Most segmentation methods are block-wised ones which divide the fingerprint image into un-overlapped blocks and decide on the type (background and foreground) of each block. Some other methods are pixel-wised ones which determine the type of each pixel. Fingerprint segmentation typically computes the feature (or feature vector) of each element, block or pixel, and then determines the element’s type based on the feature (vector). The features used in fingerprint segmentation mainly include statistical features of pixel intensity, directional image and ridge projection signal et al. Fuzzy c-means (FCM) clustering algorithm, an unsu- pervised clustering technique, has been widely used in image segmentation since it was proposed [2,3]. Com- pared with hard c-means algorithm [4], FCM is able to preserve more information from the original image. However, for one thing, it is noise-sensitive for not tak- ing into account the spatial information [5]; for another, it is supposed that each feature date has the same contri- bution to classifying results [6]. To solve the first problem, recently, many researchers proposed the algorithms ac- counting for spatial information via modifying the ob- jective function of standard FCM algorithm [5,7,8]. To solve the second problem, Li et al. [6] proposed a modi- fied clustering algorithm via introducing feature weight of the data. Generally, fingerprint image is gray level image and is inevitably corrupted by noise during acquisition. Con- sequently, data feature of the fingerprint is the pixel’s gray value. From the gray level histogram of the finger- print image, it is easily known that the occurrence fre- quencies of the different gray levels are usually different. Therefore, different gray level pixel has different con- tribution to clustering results. In this paper, we propose a modified algorithm for noisy fingerprint image segmentation. The proposed approach is based on modified fuzzy c-means which is robust to noise. Our method achieves more desirable performance com- pared to standard FCM and Szilagyi modified FCM in [8]. The paper is organized as follows. In Subsection 2.1, standard FCM clustering algorithm is described. Subsec- tion 2.2 presents the proposed modified FCM algorithm to segment the fingerprint. In Section 3, the experimental results are presented. Finally, Section 4 gives our con- clusions and discussions. 2. METHODOLOGY 2.1. Standard FCM Algorithm The FCM algorithm assigns pixels to each category by using fuzzy memberships. J. Y. Kang et al. / J. Biomedical Science and Engineering 2 (2009) 656-660 657 SciRes Copyright © 2009 JBiSE Let denotes an image with {,1,2, ,|} d ii Xxi Nx N pixels to be partitioned into classes, where c i x represents features data. The algorithm is an iterative optimization that minimizes the objective function de- fined as follows [3]: 2 11 cN m mkii ki k J uxv (1) with the following constraints: 11 {[0,1]| 1,,0, cN ki kiki ki uuiuN }k (2) where represents the membership of pixel ki ui x in the cluster, is the class center; || denotes the Euclidean distance, is a weighting exponent on each fuzzy membership. The parameter controls the fuzziness of the resulting partition. The membership functions and cluster centers are updated by the follow- ing expressions: th kk vth k 1m || m 2/( 1) 1 1 () ki c ik m lil uxv xv (3) and 1 1 N m ki i i kN m ki i ux v u (4) In implementation, matrix V is randomly initialized, and then U and V are updated through an iterative proc- ess using Eq.s 3 and 4 respectively. 2.2. Modified FCM Algorithm Szilagyi et al.proposed a fast FCM clustering algorithm, EnFCM [8], which is used for gray level image segmen- tation. The algorithm accounts for pixel spatial informa- tion. Before the algorithm implementation, a linearly- weighted sum image , composed by original image and local neighboring average of each pixel in original image , was calculated as follows: 1() 1i ii jN R j x x N (5) where i is the gray value of the pixel in the image th i . stands for the set of neighbors falling into a local window around i i N x , ad n R N iits cardinality. The pa- rameter a n the second term controls the effect of the penalty. In essence, the addition of the second term in Eq.5, equivalently, formulates a spatial constraint and aims at keeping continuity on neighboring pixel values around s i i x . Accordingly, the modified objective func- tion was described as follows: 2 11 q c m slkll kl k J uv (6) where {,1,2, ,} ll q is the data set rearranging from he image defined in Eq.5 according to gray level. {}(1,2, , k Vvk)c { } kl Uu represents the prototype of the cluster, th k(1,2, ,,1,2, ,)k cl q represents the fuzzy membership of gray value l with respect to cluster . denotes the number of the gray level of the given image which is generally much smaller than . kq Nl is the number of the pixels having the gray value equal to l, where 1, 2,,lq . Naturally, 1 q l lN . Similar to the standard FCM algorithm, under the constraints that 11 c kl ku for any l, minimize s J de- fined in Eq.6. Specifically, taking the first derivatives of s J with respect to and , and zeroing them, re- spectively, two necessary but not sufficient conditions for kl uk v s J will be obtained as follows: 2/( 1) 2/( 1) 1 () () m lk kl cm lr r v u v (7) 1 1 qm lkll l kqm lkl l u v u (8) Obviously, in Eq.6, gray level was viewed as the clas- sified data. Hence, the number of classified data only depends on gray level, and doesn’t enlarge with the in- creasing of image size. However, Eq.6 doesn’t take dif- ferent gray level which has different influence on classi- fying results into consideration, i.e., Eq.6 considers that every gray level has the same contribution to the classi- fying results. Actually, according to the gray level histo- gram of the fingerprint image, it is clear that the occur- rence frequencies of different gray level are different. Therefore, different gray level has different contribution to clustering results. Based on above analysis, we modi- fied the objective function in Eq.6 as follows: 2 11 q c m sllkll kl k J wu v (9) where is the weighting coefficient of l w(1,2,,) llq , and can be computed via histogram as follows: ,0,1, l l wl N ,q (10) where q denotes the number of the gray level of the given image. l is the number of the pixels having the 658 J. Y. Kang et al. / J. Biomedical Science and Engineering 2 (2009) 656-660 SciRes Copyright © 2009 q JBiSE gray value equal to l, where . Naturally, 1, 2,,l 1 q l l N , , i.e., can be viewed as the occurrence probability of each gray level. Hence, from Eq.10, it is known that the weighting coef- ficient of each gray level can be given by the normalized image histogram. 11 q l lw (1,2, l wl c k ,q 1u ) Similarly, under the constraints that 1 kl u for any l, minimize Js defined in Eq.9. Specifically, taking the first derivatives of Js with respect to and , and zeroing them, respectively, two necessary but not sufficient conditions for Js will be obtained as follows: kl k v 2/( 1) 2/( 1) m m 1 kl c r u () () lk lr v v (11) 1 1 qm ll m kl llk l q ll l wu wu k v 1/ l wq 1cN ,2,,)c l w 1m (12) From Eq.12, it is known that the function of weight- ing coefficient lies in adjusting the clustering center. Eq.9 will degenerated to Eq.6 while . The modified FCM algorithm (spatially weighting FCM clustering algorithm, called SWFCM) can be summarized as follows: Step 1: Fix and 2; then select ini- tial class prototypes ; set (1 k vk 0 to a very small value. Step 2: Compute the new image in terms of Eq.5 in advance. Repeat: Step 3: Compute/modify kl with by Eq.s 11 and 12. k v kl Step 4: Update with the modified k v by Eq. 12. Until (|| new old VV 2ma ) 3. RESULTS AND DISCUSSIONS In the following experiments, we first execute the three segmentation algorithms, FCM, EnFCM and SWFCM on an original fingerprint image in Subsection 3.1. Then perform the three segmentation algorithms on noisy fin- gerprint images corrupted, respectively, by Gaussian noise and salt and pepper noise to investigate the robustness of the algorithms in Subsection 3.2. Finally, the Subsection 3.3 gives the corresponding quantitative comparisons for the segmenting results presented in Subsection 3.1 and 3.2. In all the following experiments, we set the parame- ters , , , . 2c55 10 3.1. Results on Original Fingerprint Image To compare the segmenting performances of the above three algorithms, FCM, EnFCM and SWFCM, we apply these algorithms to an original test fingerprint image as shown in Figure 1(a) with the size of pixels, and the corresponding segmenting results are, respec- tively, displayed in Figures 1(b,c,d). 300 300 As shown in Figure 1, it is clear that our proposed algorithm performs more visually significant than other two methods do. More detailed quantified comparison according to execution time and iteration step are given in the next subsection. 3.2. Results on Fingerprint Images Corrupted by Noises To examine the above three algorithms’ robustness to noise, we apply the three algorithms on fingerprint images cor- rupted by noises. Figure 2(a) is the original image with no noise and Figures 2(b) and 2(c) are the same images corrupted, respectively, by the Gaussian noise (0, 0.05 d ) and the salt and pepper noise with noisy density 0.02 . The segmenting results on Figures 2(a) and 2(b) are shown in Figures 3 and 4, respectively. (a) (b) (c) (d) Figure 1. Fingerprint image segmentation. (a) Original fingerprint image; (b) Fingerprint segmentation result using FCM; (c) Fingerprint segmentation result using EnFCM; (d) Fingerprint segmentation result using SWFCM. (a) (b) (c) Figure 2. Fingerprint image. (a) Original image; (b) The im- age corrupted by Gaussian noise; (c) The image corrupted by salt and pepper noise. J. Y. Kang et al. / J. Biomedical Science and Engineering 2 (2009) 656-660 659 SciRes Copyright © 2009 JBiSE Figure 3. Segmenting results on fingerprint image corrupted by Gaussian noise. (a) Fingerprint segmentation result using FCM (b) Fingerprint segmentation result using EnFCM (c) Fingerprint segmentation result using SWFCM. Figure 4. Segmenting results on fingerprint image corrupted by salt and pepper noise. (a) Fingerprint segmentation result using FCM; (b) Fingerprint segmentation result using EnFCM; (c) Fingerprint segmentation result using SWFCM. Both from Figures 3 and 4, We can visually see that FCM is influenced by the Gaussian noise and the salt and pepper noise to different extents, respectively, which indicate that FCM algorithm lacks enough robustness to both the Gaussian noise and the salt and pepper noise, while EnFCM and SWFCM can basically eliminate the effect of the noises. Although the segmenting results using EnFCM and SWFCM are visually almost same, more detailed quantified comparison according to exe- cution time, iteration step and signal-to-noise ratio (SNR) are needed to further investigate in the next subsection. 3.3. Quantitative Segmenting Results Comparisons We tabulate quantitative segmenting comparisons in Tables 1,2,3 of the above three algorithms for Figures 1,3,4, respectively. From Tables 1,2,3, we can obviously see that the it- eration step of SWFCM is less than that of FCM and EnFCM. Furthermore, the execution time (CPU: 2 GHz, Memory: 1GHz, Operating system: windows XP, Soft ware: Matlab 7.0) of SWFCM is reduced compared with FCM and EnFCM due to both the less iterations and only dependence on the number of the gray-level (256) rather than the image size itself (300 ). q N300 Table 1. Comparison scores of three methods corresponding to Figure 1. Algorithm T N FCM 5.123 35 EnFCM 3.841 28 SWFCM 3.077 23 Table 2. Comparison scores of three methods corresponding to Figure 3. Algorithm T N SNR FCM 3.198 17 28.075 EnFCM 2.573 13 28.591 SWFCM 1.967 11 31.308 Table 3. Comparison scores of three methods corresponding to Figure 4. Algorithm T N SNR FCM 3.130 14 22.157 EnFCM 2.217 8 24.972 SWFCM 1.048 4 27.872 Note: In the above three tables, T stands for execution time with the unit of second; N stands for iteration step. From Tables 2 and 3, we can also see that the SNR of SWFCM is less than that of FCM and EnFCM. From this results, it can be concluded that the newly-proposed algorithm give rise to better denoising performance than both FCM and EnFCM algorithms. 4. CONCLUSIONS In this paper, an automatic modified FCM clustering algorithm for fingerprint segmentation was proposed. The proposed algorithm is realized by modifying the objective function in the Szilagyi’s algorithm via intro- ducing the gray histogram-based weighting. Experimen- tal results show that proposed method can dramatically speed up FCM, and can achieve better denoising per- formance compared with EnFCM. Therefore, the pro- posed approach will be promising in real fingerprint recognition system, in which the fingerprint images are contaminated by noises heavily. 5. ACKNOWLEDGMENTS The authors would like to address appreciations to anonymous review- ers for their valuable comments and suggestions to improve the pres- entation of this paper. This work was supported by the Jiangsu Post- doctoral Science Foundation (Grant No. 0901077C), the HHIT Science Foundation (Grant No. Z2008035) and Postdoctoral Science Founda- tion of China (Grant No. 20090451167). REFERENCES [1] J. P. Yin, E. Zhu and X. J. Yang. (2007) Two steps for fingerprint segmentation. Image and Vision Computing, 25, 1391–1403. [2] D. Zhang and Y. Wang. (2006) Medical image segmenta- tion based on FCM clustering and rough set. Chinese Journal of Scientific Instrument, 27, 1683–1687. [3] W. J. Chen, M. L. Giger and U. Bick. (2006) A fuzzy c-means (FCM)-based approach for computerized seg- mentation of breast lesions in dynamic contrast-enhanced MR images. Academic Radiology, 13, 63–72. [4] J. M. Gorriz, J. Ramirez and E. W. Lang. (2006) Hard c-means clustering for voice activity detection. Speech Communication, 48, 1638–1649. [5] K. S. Chuang, H. L. Tzeng and S. W. Chen. (2006) Fuzzy 660 J. Y. Kang et al. / J. Biomedical Science and Engineering 2 (2009) 656-660 SciRes Copyright © 2009 JBiSE c-means clustering with spatial information for image segmentation. Computerized Medical Imaging and Graphics, 30, 9–15. [6] J. Li, X. B. Gao and L. C. Jiao, (2006) A new feature weighted fuzzy clustering algorithm, Acta Electronica Sinica, 34, 89–92. [7] S. C. Chen and D. Q. Zhang. (2004) Robust image seg- mentation using FCM with spatial constraints based on new kernel-induced distance measure. IEEE Trans. Sys- tems Man Cybernet, B, 34, 1907–1916. [8] L. Szilagyi, Z. Benyo and S. M. Szilagyii. (2003) MR brain image segmentation using an enhanced fuzzy c- means algorithm. 25th Annual International Conference of IEEE EMBS, 17–21. |