Image Segmentation using Kernel Metric and Modified Weighted Fuzzy Factor

Image Segmentation using Kernel Metric and Modified Weighted Fuzzy Factor

Bhagyalakshmi S M.Tech Scholar

Dept. Computer Science College of Engineering Munnar Kerala, India

Biju V. G. Associate Professor

Dept. Electronics and Communication College of Engineering Munnar Kerala, India

AbstractIn this paper, a modified Kernel Weighted Fuzzy Local Information C-means clustering (MKWFLICM) algorithm for image segmentation is proposed. The proposed method is a modification of Kernel Weighted Fuzzy Local Information C- means clustering (KWFLICM) algorithm. In the proposed method the trade-off weighted fuzzy factor in KWFLICM algorithm is modified by replacing the local coefficient of variation with a distance measure. . The proposed algorithm is tested by applying on a synthetic image corrupted by salt & pepper noise, speckle noise and additive white Gaussian noise (AWGN). Performance of MKWFLICM algorithm is evaluated using the parameters, Segmentation Matching Factor (SMF), Segmentation Accuracy (SA) and Normalized Mean Square Error (NMSE).Results shows that the proposed algorithm is fast and efficient compared to KWFLICM.

KeywordsFuzzy clustering; gray-level constraint; spatial constraint; image segmentation; kernel metric; modified weighted fuzzy factor.

1. INTRODUCTION

   Image segmentation is the process of extracting foreground from background of an image. Fuzzy c-means (FCM) clustering algorithm is one of the most widely used fuzzy clustering algorithms for image segmentation. This method is developed by Dunn [1] in 1973 and improved by Bezdek [2] in 1981. Conventional FCM works well on most of the noise free images but it cannot accurately segment images corrupted by noise and outliers. Results of FCM are non-robust because of ignoring spatial contextual information in image and use of non-robust Euclidean distance. Biju V.G. and Mythili P. [3] proposed an improved FCM algorithm based on genetic algorithm for image segmentation. To deal with the problem of ignoring spatial contextual information, many improved FCM algorithms have been proposed by modifying the original FCM objective function by incorporating local spatial information.

   M.Ahmed et al. [4] formulated FCM_S algorithm by modifying the objective function of the standard FCM algorithm. Although the spatial contextual information can increase sensitivity to noise to some extent, still it lacks enough robustness to noise and outliers and is not suitable for revealing non Euclidean structure of input data due to the use of Euclidean distance. Also the spatial neighbourhood term calculated in each iteration is time consuming.

   D.Zhang and S.Chen [5], proposed a kernel based fuzzy clustering algorithm (KFCM) which introduces a kernel

   induced distance measure into the objective function of FCM to replace the conventional measures. A spatial penalty term considers the effect of neighbouring pixels on the central pixel. But the calculation of penalty term in each iteration is very time consuming. Reference [5] also proposed two variants of FCM_S, FCM_S1 and FCM_S2 which uses a mean filtered and median filtered image to increase robustness of FCM to noise by directly modifying the objective function. FCM_S1 and FCM_S2 are proposed to simplify the computation of parameters and then extended them to corresponding kernalized versions KFCM_S1 and KFCM_S2.

   L. Szilagyi et al. [6] proposed Enhanced Fuzzy C-means Clustering (En_FCM) algorithm to speed up the clustering process for grey level images. Image segmentation is performed on a linearly weighted sum image. By introducing a new factor the amount of required calculation is considerably reduced. Thus the computational time of En_FCM is very small. W.Cai.S et al. [7] proposed Fast Generalized Fuzzy C- means Clustering (FGFCM) algorithm. FG_FCM combines both spatial and gray-level information to form a non-linearly weighted sum image and clustering is performed. A new factor local similarity measure is used to guarantee both noise immunity and detail preserving for image. Its computational time is also very small. En_FCM and FG_FCM need some parameters whose selection is to be made by either trial and error or by experience. Also these algorithms do not directly apply on the original image.

   S. Krinidis and V. Chatzis [8], proposed Fuzzy Local information C-means Clustering (FLICM) algorithm which incorporates the local spatial information and gray-level information in a novel fuzzy way. The major characteristic of FLICM is the use of a fuzzy local similarity measure which guarantees noise insensitiveness and image detail preservation. This fuzzy factor replaces the parameters used in above algorithms. M.Gong et al. [9], proposed Reformulated Fuzzy Local information C-means Clustering (RFLICM) algorithm in which local coefficient of variation is adopted to replace the spatial distance. This algorithm introduces the reformulated factor as a local similarity measure to make a trade-off` between image detail and robustness to noise. But it is unreasonable to ignore the effect of spatial distance constraint on the relationship between central pixel and neighboring pixels, when the size of window is enlarged. Also the damping extent of neighbors cant be accurately calculated when there is same gray-level distribution and different spatial constraint.

   More recently M.Gong et al. [10], proposed a variant of FLICM algorithm (KWFLICM), which incorporates a trade-off

   weighted fuzzy factor and kernel metric which are parameter free. The trade-off weighted fuzzy factor depends on the spatial distance of all neighboring pixels and their gray-level difference simultaneously. Kernel metric uses Gaussian Radial basis function kernel. The kernel parameter is determined by using a fast bandwidth selection rule based on the distance variance of all data points. But in KWFLICM the fuzzy factor computed in each iteration step is time consuming.

   In this paper, a trade-off weighted fuzzy factor is designed whose computation cost is minimum. This weighted fuzzy

   B. Calculating The Modified Weighted Fuzzy Factor

   The weighted fuzzy factor is calculated based on the local spatial constraint and gray-level constraint. The spatial constraint gives the damping extent of the neighboring pixels with the spatial distance from the central pixel. The spatial constraint makes the influence of the pixels within the local window to change flexibly according to their distance from the central pixel. So more local information is used in the algorithm. The spatial constraint is defined as follows

   1

   factor gives more accurate segmentation result compared to KWFLICM. The rest of this paper is organized as follows. In the second section, details of the proposed algorithm is

   wsc

   (dij 1)

   (4)

   described. In Section III, Results and discussion is presented. Conclusions are drawn in section IV.

   Where

   dij is the spatial Euclidean distance between the

2. METHODOLOGY

   MKWFLICM algorithm is a variant of KWFLICM algorithm. The trade-off weighted fuzzy factor in KWFLICM algorithm is modified by replacing the local coefficient of variation with a distance measure. The computation of this modified weighted fuzzy factor is easier than that in KWFLICM, and it makes the algorithm efficient.

   central pixel i and neighboring pixels j in the local window N i .

   To reflect the relationship between central pixel and neighboring pixels the intensity distance is also considered. KWFLICM is computationally time consuming because of the gray-level constraint computed in each iteratio of the algorithm. So in the proposed algorithm the gray-level constraint is calculated as described below.

   1. General Framework of MKWFLICM Algorithm

      Let I be an image having N pixels. Pixels in the image is

      wid

      1 M

      N

      I

      M k1 i

      (k )I N j

      (k ),

      I N j

      (k ) 0

      (5)

      denoted as xi (i=1.N). This image is to be segmented into c

      Where

      I and I are the intensity vectors of two same

      clusters. The objective function of MKWFLICM is defined as

      Ni N j

      follows

      sized square image patches N i

      and N j . M denotes the number

      J m

      N c

      m

      uki (1 K (xi , vk )) Gk

      (1)

      of pixels in the image patches. The definition of gray-level constraint allows to use more local information. Here natural

      Where

      i1k 1

      u ki

      represents the membership matrix,

      logarithm function is used to map this distance into the intensity distance factor, which is defined as

      1 K (xi , vk )

      represents a non-Euclidean distance measure

      wgc 1 log( wid )

      (6)

      based on kernel method, m is the fuzzyfication parameter, vk

      Here the constant one guarantees wgc

      to be non-negative.

      is the cluster prototype and

      Gki

      is the reformulated fuzzy

      Therefore the weighted fuzzy factor is written as

      factor. The reformulated fuzzy factor is written as follows

      N c

      Gk i

      m wij

      (1 uki

      ) m (1 K ( x

      j , vk ))

      (2)

      wij

      wsc

      .wgc

      (7)

      u

      ki

      i1k 1

      i j jNi

      1. Calculating The Distance Based On Kernel Metric

         Where

         N i stands for the set of neighbors in a window

         Kernel method aims at transforming the complex non-

         around xi ,

         wij

         is the modified weighted fuzzy factor of pixel

         linear problems in original low dimensional feature space to the problems which can be easily solved in the transformed

         in a local window around

         xi ,

         (1 u ki ) m

         is a penalty which

         space. Commonly used kernel method is Gaussian Radial Basis Function kernel (GRBF). The kernel distance is defined

         can accelerate the iterative convergence to some extent. The as

         membership matrix must satisfy the following equation.

         x v 2

         u ki 0,1

         c

         k1

         u ki

         1 and 0

         N

         u ki i 1

         N, k

         (3)

         K ( xi , vk ) exp

         i k

         (8)

         Where parameter is the bandwidth. It is calculated by

         Step 1: Set the number c of the cluster prototypes,

         using a fast bandwidth selection rule based on the distance variance of all pixels in the image, defined as follows.

         fuzzyfication parameter m, and window size the stopping condition .

         N i and

         Given an image X, where

         xi denotes the pixels in the

         Step 2: Initialize randomly the fuzzy cluster prototypes.

         Step 3: Set the loop counter b = 0.

         image, x is the mean of the image, di represents the

         distance from each pixel xi to x and d is the mean of the distances. Then bandwidth is calculated as follows.

         Step 4: Calculate the modified weighted fuzzy factor and the kernel distance as described in sections B and C.

         Step 5: Update the partition matrix using equation (14) Step 6: Update the cluster prototypes using equation (15)

         N Step 7: If max

         vnew vold

         < then stop, otherwise, set

         xi

         x i1 (9)

         N

         2

         b = b+ 1 and go to step 4.

         When the algorithm has converged a defuzzification

         process takes place in order to convert the fuzzy partition matrix to a crisp partition. Generally maximum membership

         di xi x

         (10)

         procedure is adopted. This procedure assigns a pixel i to the

         class C k

         N

         with the highest membership.

         di

         Ck argmaxuki, k 1,2,……c. (16)

         d

         i1

         N (11)

         Then bandwidth is given as

         1

         N

3. RESULTS AND DISCUSSIONS

   The efficiency of the proposed algorithm (MKWFLICM) is tested and compared with KWFLICM algorithm. The

   1

   (d

   d ) 2 2

   (12)

   segmentation result of MKWFLICM algorithm is evaluated

   i

   N 1 i1

   So the parameter is determined by the distance variance of all the data points. Then the distance based on kernel method is

   using the parameters, Segmentation matching factor (SMF), Segmentation accuracy (SA) and Normalized mean square error (NMSE). The mathematical expression of Segmentation matching factor is as follows

   D

   x v 2

   c Ai Aref

   2

   ik 1 exp

   i k

   (13)

   SMF

   i1Ai Aref

   (17)

   Where c is the number of clusters, Ai

   represents the set of

   1. Proposed Algorithm

   pixels belonging to the i th class found by the algorithm, while

   The updating formulas for minimizing

   J m , with respect to

   Aref

   represents the sets of pixels belonging to the i th class in

   u ki

   u

   and v k is given as follows

   1

   ki 1 K(x , v ) w (1 u

   ) m (1 K(x , v

   ))

   the reference segmented image.

   Segmentation accuracy is defined as the sum of correctly classified pixels divided by the sum of the total number of

   c

   i k

   ij kj

   jNi

   ji

   j k

   pixels.

   l1 1 K(x , v ) w (1 u ) m (1 K(x , v ))

   i l ij kj j l

   c Ai Ci

   N (u m K ( x

   jNi

   ji

   , v ) x )

   (14)

   SA

   i1

   c

   j

   C j1

   (18)

   th

   ki i k i

   Where Ai

   represents the sets of pixels belonging to the i

   v i1

   k N m

   (15)

   class found by the algorithm, while Ci represents the set of

   i1

   (uki K ( xi , vk ))

   pixels belonging to the i th class in the reference segmented image.

   So the proposed algorithm is as follows.

   Normalized mean square error (NMSE) is an estimator of the overall deviation between predicted and measured vales. NMSE cost vary between 0 and 1. Zero value shows perfect segmentation. NMSE is given by

   1 M N 2

   N i j

   M ( xij xij )

   NMSE

   1 M N

   (xij )

   (19)

   Numerical values obtained on applying different levels of speckle noise are shown in Table II. MKWFLICM algorithm has an average of 6.09% improvement in SMF and 3.04% in SA.

   MN i j

   Where

   xij

   is the reference image and

   xij

   is the

   TABLE II. SEGMENTATION MATCHING FACTOR (%) AND

   S

   segmented image, images are of size M N .

   For evaluating the performance of the proposed algorithm, a synthetic image of size 80×80, having intensity values 30 and 90 is generated. Then different levels of Salt & Pepper, Additive White Gaussian and Speckle noise are added to the image. For each level of noise, average of five values of segmentation matching factor and segmentation accuracy is shown in Table I, II and III. Segmentation result on the synthetic image corrupted by Salt & Pepper noise is shown in Fig.1. Fig. 1(a) and 1(b) shows original image and reference image respectively. Image corrupted by 0.15 noise density is shown in Fig.1(c). Segmentation result of KWFLICM and MKWFLICM algorithm are shown in Fig. 1(d) and 1(e) respectively.

   Table I gives the Segmentation matching factor and Segmentation accuracy of KWFLICM and MKWFLICM algorithms on the synthetic image corrupted by Salt & Pepper noise. The noise densities applied varies from 0.05to 0.25. From the result, the proposed algorithm gives an average of 4.002% improvement in SMF and 2.002% improvement in SA.

   1. (b) (c)

   (d) (e)

   Fig. 1. Segmentation results on the synthetic corrupted by Salt & Pepper noise (d=0.15). (a) Original image. (b) Reference image. (c) Noisy image.

   1. KWFLICM result. (e) MKWFLICM result

      TABLE I. SEGMENTATION MATCHING FACTOR (%) AND SEGMENTATION ACCURACY (%) FOR THE SYNTHETIC IMAGE WITH DIFFERENT LEVELS OF SALT & PEPPER NOISE.

      Noise density (d)	SMF		SA
      	KWFLICM	MKWFLICM	KWFLICM	MKWFLICM
      0.05	98.188	99.394	99.094	99.697
      0.10	96.088	98.651	98.044	99.325
      0.15	94.185	98.001	97.091	99.000
      0.20	91.493	97.027	95.744	98.513
      0.25	88.744	95.637	94.366	97.816

      EGMENTATION ACCURACY (%) FOR THE SYNTHETIC IMAGE WITH DIFFERENT LEVELS OF SPECKLE NOISE.

      variance (v)	SMF		SA
      	KWFLICM	MKWFLICM	KWFLICM	MKWFLICM
      0.05	98.006	98.825	99.003	99.413
      0.10	87.231	92.194	93.616	96.097
      0.15	77.856	85.619	88.928	92.809
      0.20	72.169	79.975	86.084	89.988
      0.25	67.556	76.701	83.778	88.350

      Table III shows the results obtained on applying Additive White Gaussian noise. Noise levels applied varies from 1 dB to 10 dB. MKWFLICM has an average improvement of 9.17% in SMF and 5.40% in SA.

      TABLE III. SEGMENTATION MATCHING FACTOR (%) AND SEGMENTATION ACCURACY (%) FOR THE SYNTHETIC IMAGE WITH DIFFERENT LEVELS OF GAUSSIAN NOISE

      SNR (dB)	SMF		SA
      	KWFLICM	MKWFLICM	KWFLICM	MKWFLICM
      1	64.720	76.070	79.275	86.484
      3	72.661	84.611	84.313	91.650
      5	81.104	92.273	89.559	95.975
      7	88.348	96.450	93.791	98.188
      10	96.038	99.334	97.978	99.666

      Fig. 2. shows the segmentation results of the synthetic image corrupted by speckle noise (v=0.05). Fig. 2(a) and 2(b) shows the original and reference image respectively. Noisy image is shown in Fig. 2(c). Segmentation results of KWFLICM and MKWFLICM are shown in Fig. 2(d) and 2(e) respectively.

      1. (b) (c)

   (d) (e)

   Fig 2. Segmentation result on synthetic image corrupted by Speckle noise (v=0.05). (a) Original image. (b) Reference image. (c) Noisy image.

   (d) KWFLICM result. (e) MKWFLICM result.

   The computation time of the two algorithms for the synthetic image with different types of noises is compared in Table IV. 2.16 GHz, Pentium N3520 processor and 2GB

   RAM is used. From the table it can be seen that the computation time for the proposed algorithm is smaller than that of the KWFLICM algorithm.

   Noise	KWFLICM	MKWFLICM
   Salt & Pepper (d = 10)	78.99	57.02
   Speckle (v = 10)	328.89	146.88
   Gaussian (SNR = 10)	188.09	77.34

   TABLE IV. COMPUTATION TIME (S) FOR THE ALGORITHMS ON THE SYNTHETIC IMAGE CORRUPTED BY DIFFERENT NOISES

   Table V, VI and VII gives the normalized mean square error of the two algorithms on the synthetic image corrupted by Salt & Pepper, Gaussian and Speckle noises respectively. For each level of noise average of five values of Normalized mean square error is shown in the Tables.

   Table V shows the Normalized mean square error obtained on applying Salt & Pepper noise. From the Table, the average error of KWFLICM is greater than that of MKWFLICM by 0.0639. Comparison of Normalized mean square error obtained on applying different levels of Speckle noise is shown in Table VI. Average error of KWFLICM is 0.0715 greater than that of MKWFLICM.

   TABLE V. NORMALISED MEAN SQUARE ERROR OF THE SYNTHETIC IMAGE CORRUPTED WITH SALT & PEPPER NOISE.

   Noise density (d)	0.05	0.10	0.15	0.20	0.25
   KWFLICM	0.0947	0.1436	0.1784	0.2173	0.2559
   MKWFLICM	0.0551	0.0850	0.1084	0.1389	0.1831

   Variance (v)	0.05	0.10	0.15	0.20	0.25
   KWFLICM	0.0943	0.2679	0.3487	0.3968	0.4290
   MKWFLICM	0.0769	0.1964	0.2601	0.3088	0.3370

   TABLE VI. NORMALISED MEAN SQUARE ERROR FOR THE SYNTHETIC IMAGE CORRUPTED WITH SPECKLE NOISE.

   Table VII shows NMSE value obtained on applying Additive White Gaussian noise. For AWGN noise, average error of MKWFLICM is 0.1168 lesser than that of KWFLICM.

   SNR (dB)	1	3	5	7	10
   KWFLICM	0.4981	0.4164	0.3299	0.2496	0.1422
   MKWFLICM	0.3686	0.2864	0.2023	0.1351	0.0597

   TABLE VII. NORMALISED MEAN SQUARE ERROR OF THE SYNTHETIC IMAGE CORRUPTED WITH ADDITIVE WHITE GAUSSIAN NOISE.

4. CONCLUSION

KWFLICM and MKWFLICM algorithms are applied to noisy synthetic image. The results shows that the proposed algorithm is able to attain a maximum segmentation accuracy

of 99.69% for an image corrupted with 0.05 noise density Salt & Pepper noise. MKWFLICM algorithm has better segmentation accuracy than KWFLICM. Also the time taken for the proposed algorithm for segmentation is lesser than that of the KWFLICM algorithm. From Table IV it is clear that MKWFLICM is a fast and efficient algorithm for segmentation. Table V, VI and VII shows that the error rate of MKWFLICM is smaller than KWFLICM.

REFERENCE

1. J. Dunn, A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters, J. Cybern., vol. 3,no. 3, pp. 3257, 1974.

2. J. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms. New York: Plenum, 1981.

3. Biju V G, and Mythili P, 2012. A Genetic Algorithm based Fuzzy C Mean Clustering Model for Segmenting Microarray Images, International Journal of Computer Applications, Vol 52, No.11 :42-48.

4. M. Ahmed, S. Yamany, N. Mohamed, A. Farag, and T. Moriarty,A modified fuzzy C-means algorithm for bias field estimation and segmentation of MRI data, IEEE Trans. Med. Imag., vol. 21, no. 3,pp. 193199, Mar. 2002.

5. S. Chen and D. Zhang, Robust image segmentation using FCM with spatial constraints based on new kernel-induced distance measure, IEEE Trans. Syst., Man, Cybern., B, Cybern., vol. 34, no. 4, pp. 1907 1916,Aug. 2004.

6. L. Szilagyi, Z. Benyo, S. Szilagyii, and H. Adam, MR brain image segmentation using an enhanced fuzzy C-means algorithm, in Proc.25th Annu. Int. Conf. IEEE EMBS, Nov. 2003, pp. 1721.

7. W. Cai, S. Chen, and D. Zhang, Fast and robust fuzzy C-means clustering algorithms incorporating local information for image segmentation, Pattern Recognit., vol. 40, no. 3, pp. 825838, Mar.2007.

8. S. Krinidis and V. Chatzis, A robust fuzzy local information C-means clustering algorithm, IEEE Trans. Image Process., vol. 19, no. 5, pp.13281337, May 2010.

9. M. Gong, Z. Zhou, and J. Ma, Change detection in synthetic aperture radar images based on image fusion and fuzzy clustering, IEEE Trans. Image Process., vol. 21, no. 4, pp. 21412151, Apr. 2012.

10. M. Gong, Y. Liang, J. Shi, W. Ma, and J. Ma, Fuzzy c-means clustering with local information and kernel metric for image segmentation, IEEE Trans. Image Process., vol. 22, no. 2, pp. 573584, Feb. 2013.