 Open Access
 Total Downloads : 262
 Authors : Bhagyalakshmi S, Biju V. G.
 Paper ID : IJERTV4IS050183
 Volume & Issue : Volume 04, Issue 05 (May 2015)
 DOI : http://dx.doi.org/10.17577/IJERTV4IS050183
 Published (First Online): 06052015
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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 Cmeans 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 tradeoff 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; graylevel constraint; spatial constraint; image segmentation; kernel metric; modified weighted fuzzy factor.

INTRODUCTION
Image segmentation is the process of extracting foreground from background of an image. Fuzzy cmeans (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 nonrobust because of ignoring spatial contextual information in image and use of nonrobust 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 Cmeans 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 graylevel information to form a nonlinearly 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 Cmeans Clustering (FLICM) algorithm which incorporates the local spatial information and graylevel 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 Cmeans 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 tradeoff` 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 graylevel distribution and different spatial constraint.
More recently M.Gong et al. [10], proposed a variant of FLICM algorithm (KWFLICM), which incorporates a tradeoff
weighted fuzzy factor and kernel metric which are parameter free. The tradeoff weighted fuzzy factor depends on the spatial distance of all neighboring pixels and their graylevel 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 tradeoff 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 graylevel 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

METHODOLOGY
MKWFLICM algorithm is a variant of KWFLICM algorithm. The tradeoff 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 graylevel constraint computed in each iteratio of the algorithm. So in the proposed algorithm the graylevel constraint is calculated as described below.

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 graylevel 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 nonEuclidean 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 nonnegative.
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

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



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

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.

(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.

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.

(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.


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

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

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

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 :4248.

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

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

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

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

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

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.

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