Abstract
In this paper we introduce a new fuzzy c-means objective function called kernel induced fuzzy c-means based on Gaussian function for the purpose of segmentation of medical images. The originality of this algorithm is based on the fact that the conventional FCM-based algorithm considers no spatial content information, which makes it sensitive to noise. The new algorithm is formulated by incorporating the spatial neighbourhood information into the spatial neighbourhood into the original FCM algorithm by apriori probability and initialized by a kernel function induced histogram based FCM algorithm. The probability in the algorithm that indicates the spatial influence of the neighbouring pixels on the centre pixel plays a key role in this algorithm and it obtains efficient method for calculating membership and updating prototypes by minimizing the new objective function of Gaussian based fuzzy c-means. The performance of proposed algorithm has been tested with medical images to reduce the inhomogeneities and to allow the labelling of a pixel to be influenced by the labels in its immediate neighbourhood. Also this paper compares the results of proposed method with the results of existing basic fuzzy c-means.
Introduction
Cluster analysis is playing an important role in solving many problems in medical field; psychology, biology, sociology, pattern recognition and image processing. Due to the limitations in image equipments in MRI, the images have the following technical hitches: low spatial resolution, non-uniformity effect induced by radio-frequency, low contrast, and unclear borders between tissues. Thanks to the fuzzy set theory [1], this involves the idea of partial membership described by a membership function. fuzzy clustering, as a soft segmentation method, has been widely studied and successfully applied to image segmentation [2–4, 7]. MR image signals have highly affected by shacking of patient’s body and patient’s motion. So the medical MRI is seriously affected and it has improper information about the anatomic structure. Hence the segmentation of medical images is an important one before it to go for treatment planning for proper diagnosis. Initially segmentation was made manually; but manual segmentation is more difficult, time -consuming and costly. Automatic brain tumor segmentation from MR images which is not an easy task that involves various disciplines covering image analysis, mathematical algorithms [8–10] and etc. Numerous techniques have been developed for image segmentation and a tremendous amount of thorough research has been reported in the literatures [11–14, 25].
In recent world, many of the segmentation methods are based on the unsupervised clustering algorithms. Unsupervised clustering is a process for ordering objects in such a way that samples of the identical group are more similar to one another than samples belonging to different groups. Currently fuzzy c-means of fuzzy clustering plays main role in unsupervised clustering method for segmenting medical images [15]. In [5], proposed a geometrically guided FCM algorithm based on a semi-supervised FCM technique for multivariate image segmentation. In their work, the geometrical condition information of each pixel is determined by taking into account the local neighbourhood of each pixel.
The main disadvantages of fuzzy clustering technique are its need for a large amount of time to converge and it is more sensitive to the noise and outliers in the data, because of squared-norm to measure similarity between prototypes and data points. To cluster more general dataset, lots of algorithms have been proposed by replacing the squared-norm with other similarity measures. A recent development is to use kernel method to construct the kernel versions of FCM algorithm, [16, 17] proposed KFCM for clustering the incomplete data and medical image segmentation. However a disadvantage of KFCM in segmentation of medical images it is not considered about any spatial information in image context; which makes it compute the neighbourhood term in each step, which is very time consuming. In order to reduce the computation time MST initialization FCM, modified KFCM by adding the penalty term, and Histogram based FCM [18–21]. Although the above methods are claimed to be robust to noise, they are confronted with the problem of selecting the parameters that control the role of the spatial constraints.
In this paper, the efficient kernel induced fuzzy c-means based on Gaussian function (EKFCM) clustering algorithm for image segmentation is proposed. The algorithm is developed by incorporating the spatial neighbourhood information into the standard FCM clustering algorithm by apriori probability. The probability is given to indicate the spatial influence of the neighbouring pixels on the centre pixel, which can be automatically decided in the implementation of the algorithm by the fuzzy membership. The new fuzzy membership of the current centre pixel is then recalculated with this probability obtained from above. The algorithm is initialized by a given kernel function using histogram based FCM algorithm, which helps to speed up the convergence of the algorithm. The experimental results using random data show that the proposed method can achieve comparable results to those from many derivatives of efficient KFCM algorithms and are effective and more robust to reduce the noise and outliers.
Formulation of proposed method histogram based FCM algorithm
Kernel method
Recently, the powerful technique of kernel function using learning machines were proposed and found to have successful applications such as signal processing pattern recognition and image processing etc. Kernel method often studies and employs a high-dimensional feature space S for having nonlinear classification boundaries. For this a mapping is given below;
φ : R
p
→ S is used where by an object x is mapped into S:
As x is the p-dimensional vector, φ (x) may have the infinite dimension. In the nonlinear classification method, an explicit form of φ (x) is unavailable, but the inner product is defined by:
The function K (x, y) is called a kernel function and we assume this known function, as Gaussian radial basis function:
Fuzzy c-means algorithm
This method was first introduced by Dunn in [22] and improved by Bezdek in [23]. It is based on minimization of the following objective function:
where m is any real number greater than 1, u ij is the degree of membership of x i in the cluster j, x i is the ith of p - dimensional measured data, c j is the p -dimension centre of the cluster and || * || is any norm expressing the similarity between any measured data and centre.
Fuzzy partitioning is carried out through an iterative optimization of the objective function shown above, with the update of membership u
ij
and the clustercentres c
j
by:
This iteration will stop when
where ∈ is a termination criterion between 0 and 1, whereas k is the iteration steps. This procedure converges to a local minimum or a saddle point of J m .
Histogram based fuzzy c-means clustering algorithm
The standard FCM algorithm is an iterative operation, which calculates the centroids and membership function pixel-by-pixel when it is used for image segmentation. Thus, the convergence of the algorithm is very slow which makes it impractical for image segmentation. To deal with this problem, the graylevel histogram of image is employed to the algorithm developed by Yong Yang in [21]. Let us define the non-negative integrate set G ={ Lmin, Lmin + 1, … Lmax } as graylevel, where Lmin is the minimum graylevel, Lmax is the maximum graylevel, therefore the grayscale is Lmax - Lmin.
For image size S × T, at point (s, t), f (s, t) is the grayvalue with 0 ≤ t ≤ (T - 1). Let His (g) denote the number of pixels having graylevel g. Therefore, the histogram function can be written as:
where g ∈ G, δ (0) =1 and δ (g ≠ 0) =0 with this graylevel histogram His (g), using the objective function of the FCM is
where u
ig
represents the membership degree of the graylevel g to cluster i, and with the followingconstraint:
Kernel function induced histogram based FCM algorithm
This paper proposes a modification in histogram based FCM by introducing kernel function that allows the clustering of objects to be more reasonable. The modified proposed objective function is given by
where φ stands as map and the distance function can be expressed using in product space as
To obtain kernel induced FCM based Gaussianfunction the distance function can be modified as
where g ∈ G and i = 1, 2, 3 …… …… C.
Let us express G (g, v
i
) as Gaussian function
where σ is a parameter which can be adjusted by users.
Using the expression (2) we obtain G (g, g) =1 and G (v
i
, v
i
) =1, so the distance function can be rewritten as
Substituting (3) in (1) kernel induced histogram based FCM is given by
To obtain equation for calculating membership we minimizing the objective function
subject to the constraints
Therefore, the above objective function (4) can be minimized using one Lagrangian multiplier:
where λ is a Lagrange multiplier,
subject to the constraints
Expanding Equation (5) is
Taking the partial derivative of objective function with respect to u and setting the first derivative to zero by necessary condition of Lagrangian method, we have
since the partition matrix in an objective function, it satisfies the following conditions
we obtain
using Equation (6) we obtain the general equation for getting memberships
The general equation is used to obtain membership ranks for objects in data for finding meaningful groups.
Using Gaussian, the histogram based FCM objective function can be written as
Taking the partial derivative of objective function (5) with respect to vi and setting the result to zero, we have the general form of updating center as
The new FCM algorithm now only operates on the histogram of the image.
The objective function (I) of the standard FCM algorithm does not take into account any spatial information, which means the clustering process is related to graylevels independently of the pixels of image segmentation. Therefore, the limitation makes FCM to be very sensitive to noise. However, according to the theory of Markov random field, most pixels belong to the same class as their neighbors; which mean that the class probability of a pixel depends on class memberships of its neighbour clusters. By this way it can reduce the possible influence of noise and overlapping clusters in [24]. The general principle of the technique presented in this paper is to incorporate the neighbourhood information into the FCM algorithm during classification.
Let us express G (x
k
, v
i
), between pixel x
k
and vi as the product of a feature similarity term and spatial proximity term:
The fuzzy membership function given in (II) can be extended to:
where k = 1, 2 …… … n is the number of image data and P
ik
is equal to a priori probability of data point k belonging to cluster i, which can be automatically determined by the following neighbourhood model. Hence the kernelized new objective function of the KFCM algorithm is changed as
Similar to that of histogram based FCM algorithm, the degrees of membership and the cluster centers can be updated via:
where P ik the apriori probability is that kth pixel belongs to ith cluster and is computed as:
where N k denotes the total number of points in the neighbourhood of x k and NN i (k) denotes the number of the neighbouring points that belongs to cluster i after defuzzification. In this paper, the defuzzification is carried out with the maximum membership procedure. The maximum membership produce assigns object k to the class c with the highest membership.
The proposed kernel induced histogram FCM algorithm is initialized with the above fast FCM algorithm. Once the fast FCM stopped, the EKFCM algorithm continues with the values for the prototypes and membership values obtained from the fast FCM algorithm. The kernelized FCM algorithm then iteratively updates its apriori probability, membership and centroids with these values. When this improved, Efficient KFCM algorithm has converged, another defuzzification process takes place in order to convert the fuzzy partition matrix to a crisp partition matrix that is segmented.
Set the cluster centroids vi according to the histogram of the image, fuzzification parameter m, the values of C and ∈>0 Compute the histogram using (IV) Compute the membership function using (7) Compute the cluster centroids using (9) Go to stage (3) and repeat until convergence Compute the apriori probability using (14) with the obtained results of membership function and centroids. Recomputed the membership function and cluster centroid using (12) and (13) with the probabilities. If the algorithm is convergent, go to stage (9), otherwise go to stage (6) Image segmentation after defuzzification using (15) and then a region labeling procedure is performed.
Results and discussion
This section describes some experimental resultson random data, corrupted with noise to show thesegmentation performance of the proposed method. First, for the initialization of the kernel induced histogram based FCM produced; the centre of clusters is found. Then the center of the cluster and its convergence of standard FCM and EKFCM are determined under successive interactions of experiments using random data (Fig. 1 and Table 1). The standard FCM algorithm and the numbers of updated centres are high under the objective function of Euclidean distance measures. This takes more iteration to converge the termination value of algorithm. With the new efficient objective function based kernel distance measure the termination value is achieved, with very less iteration and with much better performance in getting membership (Table 2) than standard FCM. Table 3 gives the number of iteration to achieve the results of cluster on the random data by standard FCM and EKFCM. It is clear from the final cluster, membership (Table 2) and scatter diagram (Fig. 2), that our proposed EKFCM is much faster than the standard FCM and the method is converged fast to terminate condition with less run time.
To test the effectiveness of EKFCM, the kernel induced histogram based FCM is used as centre. This is done to find out the fuzzy membership and appropriate number of clusters. Thus, we have concluded the final optimal clusters formed as 3. This algorithm has also reduced the number of iterations. The EKFCM clustering algorithm has the following membership value intimacy (Table 2 and Table 4).
Conclusion
Thus, this paper has proposed the efficient kernel induced fuzzy c-means based on Gaussian function for image data analyzing. The algorithm was formulated by introducing kernel function, Gaussian function, histogram based objective function and Lagrangian methods, with basic objective function of the FCM algorithm to have proper effective segmentation of the image data and to overcome the noise sensitiveness of conventional FCM clustering algorithm. It has presented an efficient kernel induced histogram based FCM algorithm for image data segmentation. The main contribution of this algorithm is to incorporate the spatial neighbourhood information into the standard FCM algorithm by apriori probability. It can be automatically decided in the algorithm based on the membership function of the centre pixel and its neighbouring pixels and also compares the results with standard FCM segmentation. It is clear from our comparison that EKFCM performed better than FCM. The results reported show that the proposed kernel histogram based objective function of FCM is an effective approach to construct a robust image segmentation algorithm. We hope that the proposed method can also be used to improve the performance of other FCM-like algorithms based on Euclidean distance functions.
Footnotes
Acknowledgments
We would like to thank the reviewers for their constructive comments. We thank to Er.S.R Vijay shreenivas, Director, Vickram College of Engineering for his encouragement and support given. I also thank Dr.A.Sathya, Faculty of Mathematics, Satyabhama University, Chennai for her timely help throughout this work.
