SOFT IMAGE SEGMENTATION BASED ON CENTER-FREE FUZZY CLUSTERING

Ma Runing（马儒宁），Zhu Yan（朱燕），Ding Jundi（丁军娣）

（1.College of Science，Nanjing University of Aeronautics and Astronautics，Nanjing，210016，P.R.China；2.School of Computer Science and Technology，Nanjing University of Science and Technology，Nanjing，210094，P.R.China）

INTRODUCTION

Image segmentation is a technique of partitioning agiven image into multiple uniform and nonoverlapping regions［1－2］.It is an important operation in several applications of image processing，since it represents the first step of low-level processing of image.

The concept of soft image segmentation is not a new one.Each pixel has a″degree of belonging″to more than one region in soft segmentation［3］.The approaches to soft segmentation contain fuzzy clustering algorithms，fuzzy rulebased approach，relative fuzzy connectedness algorithms［4］，PDE model for soft segmentation［5］，stochastic model based approaches［6］and so on.A great many improved techniques have been proposed in recent years，such as the approaches based on Gaussian mixture model［7－8］.

Clustering methods are one of the most used algorithms in image segmentation，because they are intuitive and，some of them，easy to be implemented.Fuzzy clustering algorithms are precise for their flexibility.Therefore they can reflect the fuzziness and uncertainty of image［9］.The experimental results demonstrate the validity of segmentation based on fuzzy clustering.

Fuzzy clustering algorithm is an unsupervised clustering algorithm based on iterative optimization of objective function.The traditional fuzzy clustering algorithms，such as the classical fuzzy C-means clustering （FCM）［10］，possibilistic C-means clustering （PCM）［11－13］，need calculate the cluster center. Many questions arise because there may be no″true″cluster centers［14］.Each cluster is represented by all of the points in this cluster instead of its center point.So there is no need to calculate the cluster center.We just need formulate the similarity between the sample and the cluster to confirm the cluster which the samples belong to.The above idea is the center-free fuzzy clustering［14］.

A new soft image segmentation method based on center-free clustering is proposed in this paper.The method merges the small regions instead of the pixels.It is too complex to merge the pixels because of the huge number.Some proposed methods that merge the regions are initially segmented by mean-shift segmentation［15－16］.Meanshift is proven in generating robust and accurate segmentation results for color images［17］.So it is chosen for initial segmenting in the new method.After initial segmentation，many small available regions can be obtained.Then center-free clustering is used to merge these small regions.Quantitative analyses prove that center-free cluster is less sensitive with respect to noise.Because of the capabilities and advantages of center-free clustering algorithm，soft image segmentation based on center-free fuzzy clustering is suitable to be implemented.Compared with traditional image segmentation methods based on clustering，the experimental results show that the new method can get much better effect.

1 CENTER-FREE FUZZY CLUSTERING AND DATA CLUSTERING RESULTS

The idea of center-free fuzzy clustering algorithm is that every point in one cluster has its own contribution in presenting that cluster.The similarity between the sample and the cluster ensure the cluster which the sample should belong to.Now the center-free clustering algorithm is introduced.

For the dataset X＝｛x1，x2，…，xn｝∈Rd×n，each sample has a membership of more than one cluster.So each cluster is considered to be a fuzzy set of the sample-set.Every classification result is represented by the membership matrix U，and uijis the membership of the jth sample belonging to the ith cluster.Obviously，uijshould satisfy

（1）uij∈［0，1］，i＝1，2，…，c；j＝1，2，…，n，where cis the number of expected clusters，nthe size of the given dataset X.

Point-to-cluster similarity is defined： The similarityρijbetween the jth sample xjand the ith cluster Viis an average weighted similarity fromxjto any number of the ith cluster.That is

According to the definition，the objective function of the center-free fuzzy clustering algorithm can be formulated as follows

In Eq.（1），because the item umik·rkjindicates the similarity of xjto sample xkin the ith cluster that is weighted by the membership ofcan be considered as a sum of the linearly weighted similarity between xjto any number of the ith cluster.Therefore，it is easy to know that whenρijgets the maximum，the sample xjwill belong to the ith cluster.Minimizing the objective function is to assign each sample to the cluster which the sample is most similar to.

Obviously，this objective function is independent on any cluster center.It only involves the fuzzy membership.So the similarity between the sample and the cluster is changed by fuzzy membership matrix.

When we deal with the dataset，the goal is to find the fuzzy membership matrix U＝（uij）c×n，so that objective function Jccfr（U）is minimized under

The steps and the iterative formulas of this algorithm are described in detail.For the dataset X＝｛x1，x2，…，xn｝，where xj＝（xj1，xj2，…，xjd）T∈Rd，c∈｛1，2，…，n｝is the number of expected clusters，fuzzy factor m＞1.Jccfr（U）under the re-will reach its minimum when Eq.（3）is true.

This condition can be easily proved with Lagrange multiple method.

Proof

The Lagrange function is constructed as follows

In Eq.（4），we take the derivative of L，partial with respect to uij.The equation equals to zero.Eq.（5）can be obtained.

That is

Finally we get

The proof is finished.

The steps of the center-free fuzzy clustering algorithm are given as follows：

Step 1 Give the number of clusters c （1≤c≤n），the fuzzy factor m，a threshold parameter ε，the time of iteration t＝1.Initialize the fuzzy membership matrix U（0）.

Step 2 Compute the point-to-cluster similarity by using Eq.（1）.

Step 3 Update the fuzzy membership matrix Uby using Eq.（3）.

Step 4 The algorithm stop if E＝‖U（t＋1）－U（t）‖＜ε.Otherwise，t＝t＋1and go to Step 2.

This paper uses four artificial different databases to test center-free fuzzy clustering algorithm.The artificial databases，as shown in Fig.1，include″Normrand2″（Fig.1（a）），″Normrand2 with noises″（Fig.1（b）），″Semicircle″（Fig.1（c）），and″Block5″（Fig.1（d））.

Fig.1 Four synthetic data sets

The clustering results of the center-free fuzzy clustering algorithm，FCM，PCM，FPCM，and PCA are shown in Figs.2－6.Comparing these clustering results，it is easy to find that the center-free fuzzy clustering algorithm is much better than the other four methods.If we analyze in detail，to the manifold-structured clusters，only the center-free clustering algorithm can obtain correct results.For Block5，although these five methods all have errors，the center-free clustering algorithm has the minimum error rate.

The error rates of above experimental results are counted，as shown in following Table 1.

Fig.2 Clustering results of center-free fuzzy clustering

Fig.3 Clustering results of FCM

Fig.4 Clustering results of FPCM

Fig.5 Clustering results of PCM

Table 1 Classification error rates of five clustering methods%

2 PROPOSED SOFT IMAGE SEGMENTATION METHOD

Considering the superiority of center-free fuzzy clustering algorithm in data experiment，the soft image segmentation based on center-free fuzzy clustering is proposed.The framework of this method is as follows.Firstly the mean-shift method is chosen for initial segmentation，then center-free fuzzy clustering is used to merge regions（the color vector is extracted as feature），and the final segmented image is obtained.

Fig.6 Clustering results of PCA

Thinking about the difficulty of merging pixels，we want to extend the merging of pixel to the merging of region.For this purpose，the initial image segmentation is necessary.This step needs to segment an original image into many small regions.There are so many methods to realize this step，such as mean-shift method， watershed method and otsu＇s method.Although image segmentation using these methods can obtain the over-segmented image，these low-level segmentation methods provide a good basis for region merging.In this paper，the mean-shift method is chosen for initial segmentation.It can obtain smaller number of regions and maintain the image edge better.Because the number of regions is smaller，every region contains much more pixels.Its advantage is that it can reduce the impact of noise.So the actual conditions of the area can be reflected.Some experiments can illustrate the advantage of mean-shift method.The initial segmentation results by mean-shift，watershed and otsu′s methods are shown in Fig.7.

Mean-shift is a non-parametric probability density analysis technique.Application domains include clustering and image processing.Meanshift segmentation is a clustering algorithm that performs color and texture segmentation［18］.For the principle of mean-shift vector always pointing to probability density gradient direction，it is an iterative method.When mean-shift is used in image segmentation，each pixel is treated as an initial sample and calculated by using mean-shift.As a result，they can"shift"to the local maximum value.This algorithm needs to input color and spatial information.Each pixel is expressed by ap＋2-dimensional vector（If it is a color image，p＝3.If it is a gray image，p＝1）.Suppose（xs，xr）is the vector，in which xsis the coordinate of pixel and xrthe color information.The pixels belonging to the same region will″shift″to the same local maximum value.The pixels that shift to the same local maximum value are divided into one class.This is the general process of segmentation by using mean-shift.

Fig.7 Initial segmentation results of three different methods

After mean-shift initial segmentation，many small regions are obtained.Features of these small regions should be extracted.Generally，different image characteristics are analyzed such as texture，color，central location，edge and size to achieve image segmentation purpose.As for the color images，each pixel has three components，R，G，B，so the color space can be a feature space.The average value of the color is chosen in these small regions as feature in this paper.When the center-free clustering algorithm is used in data，the samples are the two-dimensional points.In image segmentation，these points can be changed into three dimensions.Obviously，this three-dimensional point represents the RGB average of one region.The reason for extracting this feature is that there is no relationship among the shapes or the sizes of the small regions after initial segmentation.In addition，the color of different regions which belong to the same object will have higher similarity.So it is easy to achieve segmentation results if the color vector is clustered.At last，center-free fuzzy clustering is used to merge these small regions.So we extend the cluster of pixel to cluster of region.Theoretically speaking，the number of expected clusters can be arbitrary constant.But in most cases，the choice of the number depends on the tested picture.Object and background are distinguished according to the general situation.

As for the similarity among the small regions，it is unscientific if the similarity measure is wholly used between the data points as Eq.（1）.That is because the small regions which are not adjacency cannot be clustered.That is to say，the small regions should satisfy the property of connectedness.So the similarity measure Rbetween the small regions is modified as

where ris the same as rin Eq.（1）.

3 SEGMENTATION RESULTS OF DIFFERENT METHODS

To analyze the effect of image segmentation method based on center-free clustering，experiments in OBIC image database are performed.EDISON system—the mean-shift software is used to obtain initial segmentation map.Matlab is used to cluster the small regions.Now the results of final segmentation by different segmentation methods based on fuzzy clustering are shown in Fig.8，and the rows of images in Fig.8are numbered as Fig.8-1—Fig.8-11.

F-measure （Eq.（11））is a measure of the test accuracy.It considers both the precision（Np）and the recall（Nr）of the test to compute the score：Precision is the number of correct results divided by the number of all returned results and recall is the number of correct results divided by the number of results that should be returned.To explain this definition，precision can be seen as a measure of exactness or quality，whereas recall is a measure of completeness or quantity.That is to say，high precision means that the algorithm returns more relevant results than irrelevant ones，and high recall means that the algorithm returns most of the relevant results.F-measure reaches its best value at 1and worst value at 0.

Fig.8 Segmentation results of different methods

The values of Np，Nrand Fof Fig.8are obtained，as shown in Table 2.

Table 2demonstrates that the effect of soft image segmentation based on FCM is almost the same as the segmentation based on FPCM.The segmentation results based on PCM are unsa-tisfied because of the unstable property of PCM.Under the complex conditions，soft segmentation based on center-free clustering is better than the other methods.The cluster number is 3in Fig.8-7and Fig.8-9，so it cannot be measured by F-measure.The quantitative analysis illustrates the superiority of the proposed method.

Table 2 Values of precision，recall，and F-Measure of above experiment

4 CONCLUSION

In this paper，the soft segmentation based on center-free clustering algorithm is propsed.Different from traditional fuzzy clustering，it defines an objective function by using the similarity between the sample and the cluster.The center-free clustering algorithm does not need a center.So it solves the problem of noise sensitivity.Experimental results show that the proposed segmentation method is better than the traditional segmentation methods.Although the method cannot get the best effect of segmentation under some conditions，it has the superiority compared with some other segmentation methods.However，centerfree clustering algorithm can easily entrap into local minimum.The weakness will influence the effect of the proposed method，so it needs to be improved in the later work.

［1］ Senthilkumaran N，Rajesh R.Image segmentation—A survey of soft computing approaches［C］∥2009International Conference on Advances in Recent Technologies in Communication and Computing（Artcom 2009）.Kottayam，Kerala，India：IEEE，2009：844-846.

［2］ Naz S，Majeed H，Irshad H.Image segmentation using fuzzy clustering：A survey［C］∥2010 6th International Conference on Emerging Technologies（ICET）.Islamabad：IEEE，2010：181-186.

［3］ Prewer D，Kitchen L.Soft image segmentation by weighted linked pyramid［J］.Pattern Recognition Letters，2001，22（2）：123-132.

［4］ Udupa J K，Saha P K，Lotufo R A.Relative fuzzy connectedness and object definition：Theory，algorithms，and applications in image segmentation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24（11）：1485-1500.

［5］ Posirca I，Chen Y M，Barcelos C Z.A new stochastic variational PDE model for soft Mumford-Shah segmentation［J］.Journal of Mathematical Analysis and Applications，2011，384（1）：104-114.

［6］ Fuhua C，Yunmei C.A stochastic variational model for multi-phase soft segmentation with bias correction［J］.Advanced Modeling and Optimization，2010，12（3）：339-345.

［7］ Barcelos C A Z，Chen Y M，Chen F H，et al.A soft multiphase segmentation model via Gaussian mixture［C］∥2009 16th IEEE International Conference on Image Processing.Cairo，Eqypt：IEEE，2009：3997-4000.

［8］ Tang H，Dillenseger J L，Bao X D，et al.A vectorial image soft segmentation method based on neighborhood weighted Gaussian mixture model［J］.Computerized Medical Imaging and Graphics，2009，33（8）：644-650.

［9］ Wang Zhen，Yang Meng.A fast clustering algorithm in image segmentation［C］∥2010 2nd International Conference on Computer Engineering and Technology（ICCET）.Chengdu，China：IEEE，2010：V6-592-V6-594.

［10］Hung Ming-chuan，Yang Don-lin.An efficient fuzzy C-means clustering algorithm［C］∥Proceedings IEEE International Conference on Data Mining.California，USA：IEEE，2001：225-232.

［11］Krishnapuram R，Keller J M.A possibilistic approach to clustering［J］.IEEE Transactions on Fuzzy Systems，1993，1（2）：98-110.

［12］Yang M S，Wu K L.Unsupervised possibilistic clustering［J］.Pattern Recognition，2006，39（1）：5-21.

［13］Pal N R，Pal K，Keller J M，et al.A possibilistic fuzzy C-means clustering algorithm［J］.IEEE Transactions on Fuzzy Systems，2005，13（4）：517-530.

［14］Ding Jundi，Ma Runing，Hu Xiaoqing，et al.Fuzzy C-means revisited：Towards a cluster-center-free reformulation［C］∥2010Chinese Conference on Pattern Recognition （CCPR）.Chongqing，China：IEEE，2010：1-5.

［15］Ning J F，Zhang L，Zhang D，et al.Interactive image segmentation by maximal similarity based region merging［J］.Pattern Recognition，2010，43（2）：445-456.

［16］Li Junxia，Ma Runing，Ding Jundi.Saliency-seeded region merging automatic object segmentation［C］∥First Asian Conference on Pattern Recognition（ACPR）.Beijing，China：IEEE，2011：691-695.

［17］Luo Q M，Khoshgoftaar T A.Efficient image segmentation by mean-shift clustering and MDL-guided region merging［C］∥16th IEEE International Conference on Tools with Artificial Intelligence.Boca Raton，FL：IEEE，2004：337-343.

［18］Tai Y W，Jia J Y，Tang C K.Soft color segmentation and its applications［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29（9）：1520-1537.