Ieee Transactions On Fuzzy Systems, Vol. Xxx, No. Xxx, Xxx 2017 1 .

IEEE TRANSACTIONS ON FUZZY SYSTEMS, VOL. XXX, NO. XXX, XXX 2017a lower computational cost than FCM S, since both meanfiltered images and median-filtered images can be computedbefore the start of the iterative stage. However, both FCM S1and FCM S2 are not robust for Gaussian noise, as well as forknown noise intensity. Moreover, it is difficult to ascertain thetype of noise and intensity before using FCM S1 or FCM S2.Enhanced FCM (EnFCM) [20] is an excellent algorithmfrom the viewpoint of its low computational time; it performsclustering based on gray level histograms instead of pixels ofa summed image. The computational time is low because thenumber of gray levels in an image is generally much smallerthan the number of its pixels. However, the segmentation resultproduced by EnFCM is only comparable to that producedby FCM S. To improve the segmentation results obtainedby EnFCM, Cai et al. [21] proposed the fast generalizedFCM algorithm (FGFCM) which introduced a new factor asa local similarity measure aiming to guarantee both noiseimmunity and detail-preservation for image segmentation, andmeanwhile removes the empirically-adjusted parameter α thatis required in EnFCM, and finally performs clustering ongray level histograms. Although FGFCM is able to improvethe robustness and computational efficiency of FCM to someextent, they require more parameters than EnFCM.To develop new FCM algorithms, which are free from anyparameter selection, Krinidis and Chatzis [22] proposed arobust fuzzy local information c-means clustering algorithm(FLICM) by replacing the parameter α employed by EnFCMwith a novel fuzzy factor that is incorporated into objective function to guarantee noise-immunity and image detailpreservation. Although the FLICM overcomes the problemof parameter selection and promotes the image segmentation performance, the fixed spatial distance is not robustfor different local information of images. Gong et al. [23]utilized a variable local coefficient instead of the fixed spatialdistance, and proposed a variant of the FLICM algorithm(RFLICM) which is able to exploit more local context information in images. Furthermore, by introducing a kernelmetric to FLICM, and employing a trade-off weighted fuzzyfactor to control adaptively the local spatial relationship, Gonget al. [24] proposed a novel fuzzy c-means clustering withlocal information and kernel metric (KWFLICM) to enhancethe robustness of FLICM to noise and outliers. Similar toFLICM, KWFLICM is also free of any parameter selection.However, KWFLICM has a higher computational complexitythan FLICM. In fact, the parameter selection depends on imagepatches and local statistics.Image patches have been successfully used in non-localdenoising [25], [26] and texture feature extraction [27], anda higher classification accuracy can be obtained by usingthe similarity measurement based on patch. Therefore, patchbased denoising methods, where the non-local spatial information is introduced in an objective function by utilizing a variantparameter, which is adaptive according to noise level for eachpixel of images [24], are extended to FCM to overcome theproblem of parameter selection to improve the robustness tonoise. However, it is well known that patch-based non-localfiltering and parameter estimation have a very high computational complexity. To reduce the running time of FLICM and2KWFLICM, Zhao et al. [28] proposed neighborhood weightedfuzzy c-means clustering algorithm (NWFCM) which replacesthe Euclidean distance in the objective function of FCMwith a neighborhood weighted-distance obtained by patchdistance. Even though the NWFCM is faster than FLICMand KWFLICM, it is still time-consuming because of thecalculation of patch distance and parameter selection. To overcome the shortcoming, Guo et al. [29] proposed an adaptiveFCM algorithm based on noise detection (NDFCM), wherethe trade-off parameter is tuned automatically by measuringlocal variance of grey levels. Despite the fact that NDFCMemploys more parameters, it is fast since image filtering isexecuted before the start of iterations.Following the work mentioned above, in this study, wepropose a significantly fast and robust algorithm for imagesegmentation. The proposed algorithm can achieve good segmentation results for a variety of images with a low computational cost, yet achieve a high segmentation precision.Our main contributions can be summarized as follows: The proposed FRFCM employs morphological reconstruction (MR) [30], [31] to smooth images in order to improve the noise-immunity and image detailpreservation simultaneously, which removed the difficultyof having to choose different filters suitable for differenttypes of noise in existing improved FCM algorithms.Therefore, the proposed FRFCM is more robust thanthese algorithms for images corrupted by different typesof noise. The proposed FRFCM modifies membership partition byusing a faster membership filtering instead of the slowerdistance computation between pixels within local spatialneighbors and their clustering centers, which leads to alow computational complexity. Therefore, the proposedFRFCM is faster than other improved FCM algorithms.The rest of this paper is organized as follows. In SectionII, we provide the motivation for our work. In Section III, wepropose our algorithm and model. The experimental resultson synthetic images, real medical images, aurora images, andcolor images are described in Section IV, Finally, we presentour conclusion in Section V.II. M OTIVATIONTo improve the drawback that FCM algorithm is sensitiveto noise, most algorithms try to overcome the drawback byincorporating local spatial information to FCM algorithm,such as FLICM, KWFLICM, NWFCM, etc. However, a highcomputational complexity is a problem for them. In fact,the introduction of local spatial information is similar toimage filtering in advance (see Appendix A). Thus, localspatial information of an image can be calculated beforeapplying the FCM algorithm, which will efficiently reducecomputational complexity, such as FCM S1 and FCM S2.Besides, if the membership is modified through the use ofthe relationship of the neighborhood pixels, but the objectivefunction is not modified, then the corresponding algorithm willbe simple and fast [32]. Motivated by this, in this paper, weimprove FCM algorithm in two ways: one is to introduce

IEEE TRANSACTIONS ON FUZZY SYSTEMS, VOL. XXX, NO. XXX, XXX 2017local spatial information using a new method with a lowcomputational complexity and the other is to modify pixels’membership without depending on the calculation of distancebetween pixels within local spatial neighbors and clusteringcenters. The proposed algorithm on image segmentation willbe implemented efficiently with a small computational cost.A. Motivation of Using MRBy introducing local spatial information to an objectivefunction of FCM algorithm, the improved FCM algorithms areinsensitive to noise and show better performance for imagesegmentation. Generally, the modified objective function ofthese algorithms is given as follows:Jm N XcX2umki kxi vk k i 1 k 1N XcXGki ,(1)i 1 k 1where f {x1 , x2 , · · ·, xN } represents a grayscale image, xiis the gray value of the ith pixel, vk represents the prototypevalue of the k th cluster, uki denotes the fuzzy membershipvalue of the ith pixel with respect to cluster k. U [uki ]c Nrepresents membership partition matrix. N is the total numberof pixels in the image f , and c is the number of clusters.The parameter m is a weighting exponent on each fuzzymembership that determines the amount of fuzziness of theresulting classification. The fuzzy factor Gki is used to controlthe influence of neighborhood pixels on the central pixel.Different Gki usually leads to variant clustering algorithms,such as FCM S, FCM S1, FCM S2, FLICM, KWFLICM,NWFCM, etc. From these algorithms, we found that theform of Gki directly decides the computational complexityof different clustering algorithms. For example, in FCM S,the Gki is defined asα m XGki ukxr vk k2 ,(2)NR kir Niwhere α is a parameter which is used to control the effect ofthe neighbors term, NR is the cardinality of uki , xr denotesthe neighbor of xi and Ni is the set of neighbors within awindow around xi .For FLICM, the Gki is defined asX1mGki (1 ukr ) kxr vk k2 ,(3)dir 1r Nii6 rwhere dir represents the spatial Euclidean distance betweenpixels xi and xr . It is obvious that the Gki is more complexthan that in FCM S, and thus FLICM has a higher computational complexity than FCM S. In FCM S1 and FCM S2,the Gki is defined as2Gki αumki kx̂i vk k ,(4)where x̂i is a mean value or median value of neighboringpixels lying within a window around xi . The Gki in FCM S1and FCM S2 has a more simplified formPthan FCM S, and theclustering time can be reduced because r Ni kxr uk k2 /NRis replaced by αkx̂i uk k2 .3Although FCM S1 and FCM S2 simplified the neighborsterm in the objective function of FCM S, and presentedexcellent performance for image segmentation, it is difficultto ascertain noise type that is required to choose a suitablefilter (mean or median filter). FCM S2 is able to obtain goodsegmentation results for images corrupted by Salt & Peppernoise, but it is incapable of doing so for images corrupted byGaussian noise. FCM S1 produces worse results comparedwith FCM S2. In practical applications, we expect to obtaina robust x̂ in which different types of noise are efficientlyremoved while image details are preserved. Motivated by this,we introduce MR to FCM because MR is not only able toobtain a good result, but also it requires a short running time[33]. Therefore, in this paper, we introduce MR to FCM toaddress the drawback produced by conventional filters. MRuses a marker image to reconstruct original image to obtaina better image, which is favorable to image segmentationbased on clustering. Similar to FCM S1 and FCM S2, thereconstructed image will be computed in advance, and thusthe computational complexity of the proposed algorithm islow. We will present the computation of reconstructed imagein details in Section III.B. Motivation of Using Membership FilteringIn FCM algorithm, according Pto the definition of the objectcfunction and the constraint that k 1 uki 1 for each pixelxi , and using the Lagrange multiplier method, the calculationsof membership partition matrix and the clustering centers aregiven as follows:kxi vk k 2/(m 1),uki Pc 2/(m 1)j 1 kxi vj kPN muki xi.vk Pi 1Nmi 1 uki(5)(6)According to (5), it is easy and fast to compute uki by usingvector operation for FCM algorithm. However, it is complexand slow to compute uki shown in (7) for improved FCMalgorithm such as FLICM and KWFLICM because vectoroperation cannot be used in the computation of Gki in (3). 1/(m 1)kxi vk k2 Gki,(7)uki Pc 1/(m 1)2j 1 (kxi vj k Gji )Therefore, multiple loop program is employed by FLICM andKWFLICM, which causes a high computational complexity.On the one hand, the introduction of Gki in (7) is able toimprove the robustness of FCM to noisy image segmentation,but on the other hand, the introduction of Gki causes a highcomputational cost. Clearly, there is a contradiction betweenimproving the robustness and reducing the computationalcomplexity simultaneously for FCM [34]. We found that if Gkican be computed in advance, the contradiction will disappearbecause the uki in (7) can be computed by using vectoroperation without multiple loops.In this paper, we introduce membership filtering to FCMto address the contradiction mentioned above. First, becausea reconstructed image is computed in advance, we perform

IEEE TRANSACTIONS ON FUZZY SYSTEMS, VOL. XXX, NO. XXX, XXX 2017clustering on the gray level histogram of an image reconstructed by MR. After obtaining fuzzy membership partitionmatrix, we use membership filtering to modify membershippartition matrix to avoid the computation of distance betweenpixels within local spatial neighbors and clustering centers.We present our proposed method in details in Section III.III. M ETHODOLOGYIn this study, we employ MR to replace mean or medianfilters due to its robustness to noise. MR is able to efficientlysuppress different noise without considering noise type. Moreover, MR algorithm is fast as parallel algorithms exist for theimplementation of MR. Motivated by the idea of EnFCM, weperform clustering on the gray level histogram of an imagereconstructed by MR to obtain a fuzzy membership matrixvia iteration operation. Finally, a filter is employed to modifythe membership partition matrix. Using this method, we canobtain a good segmentation result requiring less time.A. General Overview of the Proposed MethodologySimilar to EnFCM, the clustering of the proposed FRFCM isperformed on the gray level histogram, and thus the objectivefunction can be written asJm q XcX2γl umkl kξl vk k ,(8)l 1 k 1where ukl represents the fuzzy membership of gray value lwith respect to cluster k, andqXγl N,(9)l 1where ξ is an image reconstructed by MR, and ξl is a graylevel, 1 6 l 6 q, q denotes the number of the gray levelscontained in ξ, it is generally much smaller than N . ξ isdefined as follows:ξ RC (f ),(10)Cwhere R denotes morphological closing reconstruction, andf represents an original image.Utilizing the Lagrange multiplier technique, the aforementioned optimization problem can be converted to an unconstrained optimization problem that minimizes the followingobjective function:!q XccXXm2J m γl u kξl vk k λukl 1 , (11)kll 1 k 1k 1where λ is a Lagrange multiplier. Therefore, the problem ofthe minimization of objective function is converted to findingthe saddle point of the above Lagrange function and takingthe derivatives of the Lagrangian J m with respect to theparameters, i.e., ukl and vk .By minimizing the objective function (8), we obtained thecorresponding solution as follows:kξl vk k 2/(m 1),ukl Pc 2/(m 1)j 1 kξl vj k(12)4Pqγl umkl ξlvk Pi 1qm .γuli 1kl(13)According to (12), a membership partition matrix U [ukl ]c q is obtained. To obtain a stable U, (12-13) are repeatedly implemented until max{U(t) U(t 1) } η, where η is a(t)minimal error threshold. Because ukl is a fuzzy membershipof gray value l withrespect to cluster k, a new membership0partition matrix U [ukl ]c N which corresponds to theoriginal image f , is obtained, i.e.,(t)uki ukl , if xi ξl .(14)To obtain a better membership partition matrix and to speedup the convergence of our algorithm, we modify uki by usingmembership filtering. Considering the trade-off between performance of membership filtering and the speed of algorithms,we employ a median filter in this paper as follows:000U med{U },(15)where med represents median filtering.Based on the analysis mentioned above, the proposed algorithm FRFCM can be summarized as follows:Step 1: Set the cluster prototype value c, fuzzificationparameter m, the size of filtering window w and the minimalerror threshold η.Step 2: Compute the new image ξ using (10), and thencompute the histogram of ξ.Step 3: Initialize randomly the membership partition matrixU(0) .Step 4: Set the loop counter t 0.Step 5: Update the clustering centers using (13).Step 6: Update the membership partition matrix U(t 1)using (12).Step 7: If max{U(t) U(t 1) } η then stop, otherwise,set t t 1 and go to Step 5.Step 8:0 Implement median filtering on membership partitionmatrix U using (15).B. Morphological ReconstructionFor FCM algorithm, the rate of convergence is alwaysdecided by the distribution characteristics of data. If thedistribution characteristic of data is favorable to clustering,the corresponding number of iterations is small, otherwise, thenumber of iterations is large. FCM is sensitive to noise becausethe distribution characteristics of data is always affected bynoise corruption, which causes two problems. one is that theresult obtained by FCM algorithm is poor for noisy imagesegmentation; the other is that the number of iterations ofFCM is larger for an image corrupted by noise than the imageuncorrupted by noise. It is well known that the distributioncharacteristic of data can be described by histogram. If thehistogram is uniform, it is difficult to achieve a good and fastimage segmentation. On the contrary, it is easy if the histogramhas several apparent peaks. Fig. 1 shows an example.Fig. 1 shows that the histogram of original image has twoobvious peaks while the histogram of image corrupted byGaussian noise has no obvious peaks except extremum (0 and255). There are two obvious peaks in Fig. 1(f), similar to

IEEE TRANSACTIONS ON FUZZY SYSTEMS, VOL. XXX, NO. XXX, XXX 2017(a)(b)5(c)(d)(e)(f)Fig. 1: Comparison of distribution characteristics of data for noisy image and filtered image. (a) Original imge “cameraman” (image size:512 512). (b) Histogram of the original image (c) Image corrupted by Gaussian noise (the mean value is zero, and the variance is 5%)(d) Histogram of (c). (e) image filtered by a mean filter (3 3). (f) Histogram of (e).TABLE I: Comparison of number of iterations for three different images (the numbers represent the averages of repeating 100 times).Numbers of iterations with standard deviations(a)(b)(c)(d)(e)Original image (Fig. 1(a))Noisy image (Fig. 2(a))Filtered image (Fig. 2(c))21.06 1.9138.46 7.5124.56 1.48(f)noisy image. Mean filter is efficient for the optimization ofdata distribution because the number of iterations is reduced.In this paper, we introduce MR to FCM algorithm tooptimize distribution characteristic of data before applyingclustering. MR is able to preserve object contour and removenoise without knowing the noise type in advance [35], whichis useful for optimizing distribution characteristic of data.There are two basic morphological reconstruction operations, morphological dilation and erosion reconstructions [36].Morphological dilation reconstruction is denoted by Rfδ (g)that is defined as(i)Rfδ (g) δf (g),(16)where f is the original image, g is a marker image and g 6(1)f , δ represents dilation operation, and δf (g) δ(g) f ,(i)δg (f ) δ(δ (i 1) (g)) f , and stands for the pointwiseminimum.By duality, morphological erosion reconstruction is denotedby Rfε (g) that is defined as(i)Rfε (g) εf (g),(17)(1)(g)(h)Fig. 2: Comparison of noise removal using different methods. (a)Image corrupted by Gaussian noise (the mean value is zero, and thevariance is 5%). (b) Image corrupted by Salt & Pepper noise (thenoise density is 20%). (c) Filtered result using mean filtering for (a).(d) Filtered result using mean filtering for (b). (e) Filtered result usingmedian filtering for (a). (f) Filtered result using median filtering for(b). (g) Filtered result using MR for (a). (h) Filtered result using MRfor (b).the original Fig. 1(b), demonstrating a mean filter is efficientfor the removal of Gaussian noise. We implemented FCMalgorithm on three images: original image, the image corruptedby Gaussian noise (the mean vlaue is zero, and the varianceis 5%), and the image filtered by a mean filter (the size of thefiltering window is 3 3). Table I shows the comparison ofnumber of iterations of FCM for the three images (c 2).Table I shows that the number of iterations of FCM is thesmallest for the original image and it is the largest for thewhere g f , ξ represents erosion operation, and εf (g) (i)ε(g) f , εg (f ) ε(ε(i 1) (g)) f , and stands for thepointwise maximum.The reconstruction result of an image depends on theselection of marker images and mask images [37]. Generally,if the original image is used as a mask image, then thetransformation of the original image is considered as themarker image. In practical applications, g ε(f ) meets thecondition g 6 f for dilation reconstructions and g δ(f )meets the condition g f for erosion reconstructions. Thus,g ε(f ) and g δ(f ) are always used to obtain a markerimage due to simplicity and effectiveness.Based on the composition of erosion and dilation reconstructions, some reconstruction operators with stronger filtering capability can be obtained, such as morphological openingand closing reconstructions. Because morphological closingreconstruction, denoted by RC , is more suitable for texturedetail smoothing, we employ RC to modify original image.RC is defined as follows: εδRC (f ) RR.(18)δ (ε(f )) δ Rf (ε(f ))f

IEEE TRANSACTIONS ON FUZZY SYSTEMS, VOL. XXX, NO. XXX, XXX 20176In [20], the modified image ξ (ξi )Ni 1 is defined as1ξi (xi αx̂i ) ,1 α(19)According to (18), xi f and x̂i RC (f ), where RC (f )denotes a reconstructed image obtained by RC . To obtaina marker image, a structuring element B including centerelement is required for ε or δ, i.e., εB (f ) f and δB (f ) f .Then, RC is rewritten as εδRC (f ) RR.(20)δ (ε (f )) δB Rf (εB (f ))BfFor example, a disk with radius r can be considered as B. Ifr 0, then RC (f ) f ; else f will be smoothed to differentdegree according to the change of r. Therefore, the effect ofα is similar to r. And thus, we can replace ξ with RC (f ), andthe parameter α will be removed, which solves the problemof noise estimation because MR is able to remove differentnoises efficiently.To show the effect of MR for different type of noise removalin images, Fig. 2 shows comparative results generated by amean filter, a median filter, and RC . The original image isFig. 1(a), and the size of the filtering window employed bythe mean and the median filters is 3 3. For consistency, thestructuring element, in this case, is also a square of size 3 3(r 1).Figs. 2(c, e, g) are filtering results of image corrupted byGaussian noise by using the mean filter, the median filter, andRC respectively. It is clear that RC is efficient for Gaussiannoise removal. Similarly, Figs. 2(d, f, h) are filtering resultsof image corrupted by Salt & Pepper noise by using themean filter, the median filter, and RC respectively. It is alsoclear that RC is efficient for Salt & Pepper noise removal.Therefore, on the one hand, MR removes the difficulty ofchoosing filters for images corrupted by noise; on the otherhand, MR integrates spatial information into FCM to achieve abetter image segmentation. Compared with mean filtering andmedian filtering, Fig. 2 shows that MR is able to optimize datadistribution without considering noise type. Moreover, MR canobtain better results for image filtering than mean and medianfilters, which is important for subsequent clustering and imagesegmentation.C. Membership FilteringAccording to the above results in subsection III.B, wefound that the introduction of local spatial information isuseful and efficient for improving FCM algorithm. However, the computation of distance between pixels within localspatial neighbors and clustering centers does introduce a highcomputational complexity, such as FCM S. Although someimproved algorithms such as FCM S1 and FCM S2, reducecomputational complexity by computing spatial neighborhoodinformation in advance, these algorithms need to ascertainthe noise type before applying an image filter. To exploitspatial neighborhood information during the iteration processof clustering, FLICM and KWFLICM compute the distancebetween the neighbors of pixels and clustering centers ineach iteration. Although FLICM and KWFLICM 0.030.020.000.350.130.020.620.850.98(d)Fig. 3: Comparison of membership partition from FCM and FLICM(c 3, and the iteration step is 10). (a) Original synthetic imageincluded three gray levels (

IEEE TRANSACTIONS ON FUZZY SYSTEMS, VOL. XXX, NO. XXX, XXX 2017 1 Significantly Fast and Robust Fuzzy C-Means Clustering Algorithm Based on Morphological Reconstruction and Membership Filtering Tao Lei, Xiaohong Jia, Yanning Zhang, Senior Member, IEEE, Lifeng He, Senior Member, IEEE, Hongy-ing Meng, Senior Member, IEEE, and Asoke K. Nandi .