1 Introduction

Image segmentation is one of the most important techniques in image understanding and computer vision, and has been applied in many fields like object detection, video surveillance, medical imaging, etc[1–8]. In essence, image segmentation is to partition one given image into homogeneous, non-overlapping regions with respect to some characteristics, such as gray value, texture and shape. Till now, image segmentation is still one bottleneck in digital image segmentation due to the complexity of images. For example, medical images suffer from partial volume effect(PVE), intensity inhomogeneity(IIH)[9, 10], and natural images suffer from image artifacts, which make the value of one pixel be affected by different objects in the image. Therefore, it is difficult to assign one single class to the affected pixels. For this reason, conventional “hard” segmentation methods are not suitable to segment these complex images, because they restrict each pixel exclusively to one class. As a result, fuzzy clustering has been extensively applied, for it admits one pixel belonging to several classes concurrently and can retain information as much as possible.

Of fuzzy clustering algorithms, FCM is a typical one, and has been widely applied in image segmentation for its simplicity and efficiency. FCM was first proposed by Dunn[11] and later extended by Bezdek[12]. As is well known, FCM performs well in noise-free images, while poor when noise, outliers or other image artifacts exist. This is because spatial information is not considered in the objective function [13–16]. To improve segmentation results in noisy images, various improved algorithms have been proposed. For example, bias-corrected version of FCM(BCFCM) was proposed by Ahmed[17], in which spatial information was incorporated into the objective function of FCM. In BCFCM, the impact of spatial information is weighted by one constant parameter α, the selection of which will affect the segmentation result greatly. To overcome this problem, Stelios and Chatzis proposed one parameter-free algorithm—-FLICM[18], in which one fuzzy factor was defined to replace the parameter α in BCFCM. With the help of the fuzzy factor, the membership of neighbor pixels in one local window will converge to one similar value, whether the central pixel is contaminated or not.

In FLICM, the damping extent of neighbor pixels on the central one is based on the Euclidean distance between pixels, which makes FLICM perform poor in complex images. To improve the performance, FLICM was improved by introducing a trade-off weighted fuzzy factor and kernel method[19], termed as KWFLICM. However, only local information is utilized in FLICM and KWFLICM, and when the noise degree is high, both algorithms perform poor. To get satisfying segmentation results, one improved fuzzy clustering algorithm is proposed in this paper, in which pixel relevance will be utilized into the fuzzy factor to define the damping extent. Based on the novel fuzzy factor, non-local information can be considered in the procedure of segmentation, which can well enhance the robustness while preserving image details, better than FLICM and KWFLICM.

The rest of this paper is organized as follows. In the next section, conventional FCM and typical improved algorithms are introduced. Section III introduces the proposed algorithm in detail, and then experimental results on various images are presented. Finally, a short but brief conclusion is drawn.

2 Related work

2.1 Conventional FCM

As is well known, FCM is one typical clustering algorithm in pattern recognition and machine learning. The target of FCM is to minimize the weighted distance between pixels and cluster centers. Formally,

$$ F=\displaystyle\sum\limits_{i=1}^{C}\sum\limits_{j=1}^{n} u_{ij}^{m} d_{ij}^{2} $$
(1)

where C is the predefined number of clusters, n is the number of pixels in the given image, u i j is the membership of the j-th pixel belonging to the i-th cluster, and the constraint \({\sum }_{i=1}^{C} u_{ij}=1\) is satisfied. m ≥ 1 is the parameter to control the fuzziness of the clustering results, and d i j =∥x j −v i ∥ is one norm metric, denoting the Euclidean distance between the j-th pixel and the i-th cluster center. The membership and cluster centers are updated iteratively, and this process will stop when \(\max |u_{ij}^{p+1}-u_{ij}^{p}|<\varepsilon \) or the predefined number of iterations is satisfied.

As is shown in (1), spatial information is not considered in FCM, which will make FCM sensitive to noise and other image artifacts. To solve this problem, many algorithms were proposed to improve the robustness to noise.

2.2 BCFCM and its variants

Bias-corrected version of FCM(BCFCM) was proposed by Ahmed[17], which improved FCM by adding one spatial term, and the label of one pixel was affected by those of neighbor pixels. Formally,

$$ F=\displaystyle\sum\limits_{i=1}^{C}\sum\limits_{j=1}^{n} u_{ij}^{m} d_{ij}^{2}+\displaystyle\frac{\alpha}{N_{R}}\sum\limits_{i=1}^{C}\sum\limits_{j=1}^{n} \sum\limits_{r\in N_{j}}u_{ij}^{m} d_{ir}^{2} $$
(2)

in which N j is the neighbor window centering around pixel j, and N R is its cardinality. The parameter α controls the effect of the neighbor term, which is usually determined by trial-and-error experiments.

In BCFCM, the neighbor information has to be computed in each iteration. Therefore, BCFCM is of low efficiency. To reduce the time complexity, Chen and Zhang proposed two variants of BCFCM, named FCMS1 and FCMS2[20], in which the neighbor information was replaced with the information in the median-filtered image or mean-filtered image. Formally,

$$ F=\displaystyle\sum\limits_{i=1}^{C}\sum\limits_{j=1}^{n} u_{ij}^{m} \|x_{j}-v_{i}\|^{2}+{\alpha}\sum\limits_{i=1}^{C}\sum\limits_{j=1}^{n} u_{ij}^{m} \|\overline{x}_{j}-v_{i}\|^{2} $$
(3)

where \(\overline {x}_{j}\) is intensity of the j-th pixel in the mean-filtered image or the median-filtered image, corresponding to FCMS1 or FCMS2, respectively.

As is well known, the mean-filtered image and the median-filtered image can be computed in advance, making FCMS1 and FCMS2 have low time complexity in comparison with BCFCM. Moreover, since the mean filter and median filter are robust to Gaussian noise or Salt & Pepper noise, so are FCMS1 and FCMS2.

2.3 EnFCM

To speed up the process of image segmentation, Szilagyi et al. proposed an enhanced FCM (EnFCM)[21]. Before segmentation, one linearly-weighted sum image ξ between the original image and its mean-filtered image is firstly calculated by

$$ \xi_{i}=\frac{1}{1+\alpha}\left( x_{i}+\frac{\alpha}{N_{R}}\sum\limits_{j\in N_{i}}x_{j}\right) $$
(4)

where α has the same role as that in BCFCM. Based on the histogram of ξ, the objective function of EnFCM can be defined as

$$ F=\sum\limits_{i=1}^{C}\sum\limits_{j=1}^{L} \gamma_{j} u_{ij}^{m}(\xi_{j}-v_{i})^{2} $$
(5)

where L is the number of gray levels of the image ξ, γ j is the number of pixels with intensity value j. Usually, the number of gray levels is much smaller than that of pixels. As a result, the efficiency of EnFCM is much higher than that of other algorithms.

2.4 Fast generalized fuzzy C-means clustering(FGFCM)

Due to the difficulty of selecting the parameter α in (4), EnFCM cannot retrieve better results in most medical and natural images. To overcome this, Cai et al. proposed FGFCM[22], which was motivated by the idea of EnFCM. Similarly, FGFCM performs segmentation with the help of the histogram of the sum image. Different from EnFCM which is based on the linearly weighted sum image, FGFCM is based on the non-linearly weighted sum image. In FGFCM, one local pixel similarity measure S i j is defined, which incorporates both the local gray information and local spatial information. Formally,

$$ \xi_{j}=\displaystyle\frac{{\sum}_{r\in N_{j}}S_{jr}x_{r}}{{\sum}_{r\in N_{j}}S_{jr}} $$
(6)

In FGFCM, the similarity between the center pixel j and neighbor pixel r is defined as

$$ S_{jr}=S_{jr}^{S}\times S_{jr}^{G} $$
(7)

where \(S_{jr}^{S}\) and \(S_{jr}^{G}\) are spatial similarity and gray similarity, respectively. In FGFCM, \(S_{jr}^{S}\) and \(S_{jr}^{G}\) are defined as

$$ S_{jr}^{S}=\exp\{-\max(|p_{j}-p_{r}|,|q_{j}-q_{r}|)/\lambda_{S}\} $$
(8)
$$ S_{jr}^{G}=\exp\left\{-(x_{j}-x_{r})^{2}/(\lambda_{G}{\sigma_{j}^{2}})\right\} $$
(9)

where (p j ,q j ) is the spatial coordinate of pixel j, λ S and λ G are scale parameters of gray and spatial information, and σ j is the variance of those pixels centering around the j-th pixel. FGFCM provides good segmentation results in images of low-level noise, but the selection of parameters is one difficult task, just as that in BCFCM and EnFCM.

2.5 Fuzzy local information C-means algorithm(FLICM)

In image segmentation, it is very difficult to balance between noise insensitiveness and image details. In the improved algorithms mentioned above, this task is accomplished by adjusting corresponding parameters, which is very difficult for complex images. Aiming at this problem, Krinidis and Chatzis proposed one parameter-free algorithm—-FLICM[18]. In FLICM, one fuzzy factor G k i was introduced, which played the role of α in the improved algorithms mentioned above and could well control the tradeoff between noise insensitiveness and image detail preservation. Moreover, different from the other improved algorithms, FLICM is free of parameters. In FLICM, the fuzzy factor is defined as

$$ G_{ij}=\displaystyle\sum\limits_{r\in N_{j}}\frac{1}{d_{jr}+1}(1-u_{ir})^{m} \|x_{r}-v_{i}\|^{2} $$
(10)

in which d j r is the Euclidean distance between pixel j and pixel r. With the application of fuzzy factor G i j , the corresponding membership values of the non-noisy pixels, as well as the noisy pixels that falling into the local window will converge to a similar value, and thereby balance the membership values of the pixels that located in the window[19]. In FLICM, the objective function is defined as

$$ F=\sum\limits_{i=1}^{C}\sum\limits_{j=1}^{n} [u_{ij}^{m}(x_{j}-v_{i})^{2}+G_{ij}] $$
(11)

The membership and cluster centers can be updated iteratively by minimizing the objective function in (11), formalized as

$$ u_{ij}=\displaystyle\frac{1}{{\sum}_{k=1}^{C}\left( \displaystyle\frac{\|x_{j}-v_{i}\|^{2}+G_{ij}}{\|x_{j}-v_{k}\|^{2}+G_{kj}}\right)^{1/(m-1)}} $$
(12)
$$ v_{i}=\displaystyle\frac{{\sum}_{j=1}^{n}u_{ij}^{m} x_{j}}{{\sum}_{j=1}^{n}u_{ij}^{m}} $$
(13)

3 Proposed Method

As is mentioned before, one fuzzy factor is introduced into FLICM to replace α in BCFCM, making FLICM free of parameters. In the fuzzy factor, the influence of neighbor pixels on the central one, also called the damping extent, is exerted flexibly by using their Euclidean distance from the central one[23]. If the distance is small, the damping extent on the central pixel is big, otherwise it is small. In the procedure of image segmentation, the membership of pixels having big damping extent on the central one, together with that of the central pixel, will converge to similar values. But when the central pixel is noisy, it fails to analyze the impact of neighbor pixels, for it is not conformity with the discrepancy between neighbor pixels. To overcome this, KWFLICM was proposed by using local coefficient of variation and kernel function. However, in complex images, especially those of high-level noise, FLICM and KWFLICM perform poor. This paper holds the idea that the reason is that only local information is utilized in the two algorithms.

As is well known, there is much information that can be utilized in the segmentation, not limited to local ones. For example, there are many pixels with similar neighborhood configuration to one given pixel, and these pixels should be utilized to enhance the robustness of FLICM. However, these pixels don’t exist in the neighbor window and cannot be considered in FLICM and KWFLICM. To overcome this, one improved algorithm will be presented in this section, in which pixel relevance will be adopted to measure the damping extent. With the help of pixel relevance, non-local information in the whole image can be considered, which can improve the robustness to image artifacts.

3.1 Pixel relevance

Compared with those algorithms using local information, the algorithm utilizing the pixels with similar configurations to guide the segmentation is preferable. As is well known, considering more information means low efficiency. To balance the segmentation quality and efficiency, one search window centering around the given pixel will be defined, and only the pixels in the window with similar configuration will play a positive role in guiding the procedure of image segmentation. As is analyzed above, measuring the similarity between pixels accurately is very important, which will be termed as pixel relevance in the proposed algorithm. The phase “non-local” means that the number of pixels considered in this paper is bigger than that in other improved local algorithms, since the radius of the search window can be big enough to cover all pixels in this image.

Formally, the search window around the i-th pixel is represented as \({W_{i}^{r}}\), and the height and width of \({W_{i}^{r}}\) is (2r + 1). In the proposed algorithm, all information provided by pixels in \({W_{i}^{r}}\) will be considered. In this paper, pixel relevance between the two pixels i and \(j\in {W_{i}^{r}}\) is denoted as S(i, j), and is defined as

$$ S(i,j)=\frac{1}{Z_{i}}\exp\left( -\frac{\|X_{N_{i}}-X_{N_{j}}\|^{2}}{h^{2}}\right) $$
(14)

in which N i and N j are two image patches centering around the i-th and j-th pixel (the size of image patch is assigned 3 × 3 in this paper), h is the filtering degree parameter, controlling the decay of S(i, j). Z i is the normalizing factor, defined as

$$ Z_{i}=\sum\limits_{j\in {W_{i}^{r}}}\exp\left( -\frac{\|X_{N_{i}}-X_{N_{j}}\|^{2}}{h^{2}}\right) $$
(15)

As is analyzed in [24], h is very crucial to the segmentation results and the selection of this parameter is often done manually. To overcome this problem, h is determined adaptively instead of using a single value for all the pixels. Concretely, h is calculated based on the statistical characteristics in its search window, which is called self-tuning[25].

$$ h=\sqrt{(\sum\limits_{r\in N_{i}}(x_{r}-x_{i})^{2})/N_{R}} $$
(16)

where N i is the set of pixels in \({W_{i}^{r}}\), and N R is its cardinality. In addition, the patches are often with different geometrical structures due to the positions of pixels. To compute pixel relevance accurately, the geometrical structures of \(X_{N_{i}}\) and \(X_{N_{j}}\) in this paper are supposed to be the same, which can make the improved algorithm more robust to image artifacts.

According to the definition in (14) and (15), 0 ≤ S(i, j) ≤ 1 and \({\sum }_{j\in N_{i}}S_{ij}=1\) hold. If \(X_{N_{i}}\) and \(X_{N_{j}}\) are similar, the pixel relevance S i j is close to 1, otherwise, S i j is close to 0.

Let’s take one example in Fig. 1a to illustrate the computation of pixel relevance. The intensities of pixels in the red box is tabulated in Fig. 1b, and corresponding pixel relevances between the central pixel(the central one with intensity value 66) and the pixels in the search window are presented in Fig. 1c. According to (14), the value of pixel relevance between the pixel in the search window and the central pixel depends on the similarity between corresponding patches. As is shown in Fig. 1c, pixel relevance between A and the central pixel is larger than that between B and the central pixel, even though the distance between A and the central pixel is larger than that between B and the central pixel. The same situation happens to C and D, as is shown in Fig. 1b and c.

Fig. 1
figure 1

Pixel relevance based on non local information(the radius of \({W_{i}^{r}}\) is 7). a image with noise; b intensities of pixels in the red box; c pixel relevance between the central pixel and those in the search window

Full size image

3.2 Description of the proposed algorithm

In FLICM, the damping extent of neighbor pixels on the central one will make the membership of pixels in local window converge to similar values, making FLICM robust to image artifacts. However, there are two shortages of FLICM: (1)since the damping extent is measured by the Euclidean distance, the irrelevant pixels in local window should also have similar membership values, which is unreasonable; (2) only local information is considered in FLICM, resulting in poor performance. The first problem is solved by KWFLICM by introducing one trade-off weighted fuzzy factor and kernel function. However, information adopted in KWFLICM is also limited to local context, which will make KWFLICM perform poor in complex images. Aiming at this problem, FLICM will be improved by non-local information, which can enhance the robustness of the algorithm in complex images.

According to (10), neighbor pixels will have larger damping extent on the central pixel than faraway pixels, which will make neighbor pixels have similar membership with that of the central one. Based on this principle, FLICM can be improved to make the memberships of relevant pixels converge to similar values. Formally, if S(i, j) between the i-th pixel and \(j\in {W_{i}^{r}}\) is large, the damping extent of the j-th pixel on the i-th pixel should be big, and vice versa. Therefore, the membership of the two pixels will converge to similar values, and in turn enhance the robustness of the proposed algorithm. Based on the analysis, the fuzzy factor in the proposed algorithm can be defined as follows.

$$ G_{ij}=\displaystyle\sum\limits_{k\in {w_{j}^{r}}}S(j,k)(1-u_{ik})^{m} \|x_{k}-v_{i}\|^{2} $$
(17)

Compared with FLICM, the proposed algorithm has several improvements, summarized as follows.

(1) the Euclidean distance is removed from fuzzy factor, and faraway pixels with similar configurations can also play positive role on the central one;

(2) pixel relevance is introduced into the fuzzy factor to measure the damping extent, which is defined as the patch similarity between corresponding pixels;

(3) one search window \({W_{j}^{r}}\) is defined to replace N j , and non-local information can be considered.

In the proposed algorithm, pixel relevance is defined as the patch similarity between corresponding pixels, with the help of which non-local information can be considered into the fuzzy factor to measure the damping extent. Therefore, the proposed algorithm is denoted as NLFCM, and the framework is illustrated in Algorithm 1. Also, the updating equations of membership and cluster centers in the proposed algorithm are also the same as those in FLICM.

figure g

When the algorithm has converged, a defuzzification process takes place to convert the fuzzy image to the crisp segmented image. In a general way, the maximum membership procedure method is adopted. This procedure assign the j-th pixel to the k-th class with the highest membership. Formally,

$$ k=\arg\{\max\{u_{kj}\}\} \qquad(k=1,2,\ldots,C) $$
(18)

4 Experimental Study

This section will present the experimental results on different images, including three synthetic images, three medical images and three natural images. To illustrate the robustness of the proposed algorithm, these images are contaminated with different types of noise. We will compare the proposed algorithm with several FCM-related ones: FCM, BCFCM, FCMS1, FCMS2, EnFCM, FGFCM, FLICM and KWFLICM. For all compared algorithms, we set m = 2, ε = 10−5 and 3 × 3 neighborhood is adopted for local search. In BCFCM, FCMS1, FCMS2 and EnFCM, α is assigned 2. In FGFCM, λ G and λ S are assigned 2 and 3 respectively.

4.1 Results on synthetic images

The first experiment applies the algorithms on three synthetic test images, which could be obtained from [19]. The first image with 128 × 128 pixels includes two classes of two intensity values taken as 20 and 120, as shown in Fig. 2a. The other two images with 256 × 256 pixels and 244 × 244 pixels, including four intensity values taken as 0, 85, 170 and 255, are presented in Figs. 3a and 4a, respectively. To assure the efficiency of the proposed algorithm, the size of the search window is assigned as 7 × 7, and the selection of the radius will be discussed later.

Fig. 2
figure 2

Segmentation results of the first synthetic image. a Original image. b Noisy image corrupted by Gaussian noise of level 20%. c FCM result. d BCFCM result. e FCMS1 result. f FCMS2 result. g EnFCM result. h FGFCM result. i FLICM result. j KWFLICM result. k NLFCM result

Full size image
Fig. 3
figure 3

Segmentation results of the second synthetic image. a Original image. b Noisy image corrupted by Salt & Pepper noise of level 30%. c FCM result. d BCFCM result. e FCMS1 result. f FCMS2 result. g EnFCM result. h FGFCM result. i FLICM result. j KWFLICM result. k NLFCM result

Full size image
Fig. 4
figure 4

Segmentation results of the third synthetic image. a Original image. b Noisy image corrupted by Gaussian noise of level 30%. c FCM result. d BCFCM result. e FCMS1 result. f FCMS2 result. g EnFCM result. h FGFCM result. i FLICM result. j KWFLICM result. k NLFCM result. It needs to be clear that there are 4 clusters in the result of NLFCM, of which the two in the right part need to be distinguished carefully

Full size image

Considering the existence of different types of noise in the synthetic image, segmentation accuracy(SA) is adopted to evaluate the effect of the algorithms, which is defined as the sum of the pixels correctly classified divided by the number of all pixels. Formally,

$$ SA=\displaystyle\sum\limits_{i=1}^{C}\frac{A_{i}\cap C_{i}}{\displaystyle\sum\limits_{j=1}^{C} C_{j}} $$
(19)

where A i is the set of pixels belonging to the i-th class found corresponding algorithm, C i is the set of pixels belonging to the i-th class in the reference image.

To compare these algorithms furthermore, two cluster validity functions are selected to evaluate the algorithms, which are the partition coefficient V pc[26] and the partition entropy V pe[27]. Formally,

$$ V_{\text{pc}}=\sum\limits_{i=1}^{C}\sum\limits_{j=1}^{n} u_{ij}^{2}/n $$
(20)
$$ V_{\text{pe}}=-\sum\limits_{i=1}^{C}\sum\limits_{j=1}^{n} (u_{ij}\log u_{ij})/n $$
(21)

where n is the number of pixels in the given image. The final partition of the image with less fuzziness means better performance. Hence, the best clustering is achieved when V pc is maximal and V pe is minimal.

Fig. 2c–k presents the segmentation results of the nine algorithms for Fig. 2b, which is corrupted by Gaussian noise of level 20 %. It needs to explain that the intensities of pixels in our experiments are assigned as the value of corresponding cluster center, and the segmentation results may have different color. Obviously, the ideal segmentation result is to be the same as Fig. 2a. However, noise still exists in the segmentation results of FCM, FCMS1, FCMS2, EnFCM and FGFCM, as is obviously shown in Fig. 2c–k. The results of the five algorithms without spatial information or with local spatial information are not satisfying. On the contrary, the results of BCFCM, FLICM, KWFLICM and NLFCM proposed in this paper are excellent, and almost all noise is removed in the process of segmentation.

Table 1 tabulates the comparison of the segmentation accuracy of these nine algorithms on noisy images corrupted by Gaussian noise and Salt & Pepper noise with varying degrees. It needs to be noted that the SA value is the average value of ten runs. In our experiments, the noise degrees are adopted 15 %, 20 % and 30 %. It can be seen from Table 1 that the SAs of FLICM, KWFLICM and NLFCM are much better than those of the other algorithms. What’s more, the SAs of these three algorithms are more stable.

Table 1 Segmentation accuracy(SA%) on the first synthetic image with different noise
Full size table

The segmentation results on the other two synthetic images are presented in Figs. 3 and 4. There are 256 × 256 and 244 × 244 pixels in the two synthetic images, contaminated with Salt & Pepper noise(30 %) and Gaussian noise(30 %) respectively. As is shown in Fig. 3, there is still much noise in the results of FCM, BCFCM, FCMS1, FCMS2, EnFCM and FGFCM, while a small portion of noise in the results of FLICM and KWFLICM. Compared with the former eight algorithms, NLFCM can remove almost all the noise, and the segmented regions are also homogeneous, meaning that NLFCM is with higher SA and performs better than other algorithms.

The partition coefficient V pc and the partition entropy V pe on the three synthetic images contaminated by Gaussian noise or Salt & Pepper noise with varying degrees are compared in our experiments, presented in Tables 2 and 3. It needs to be noted that the values of V pc and V pe are the average values of ten runs.

Table 2 Comparison of Partition coefficient V pc on the synthetic images with different noise
Full size table
Table 3 Comparison of Partition entropy V pe on the synthetic images with different noise
Full size table

As is shown in Tables 2 and 3, the V pc and V pe values of NLFCM are comparable to or even better than those of the other algorithms on the images corrupted by Gaussian noise. When the given image is contaminated by Salt & Pepper noise, the V pc and V pe values of NLFCM are not so well. However, when Salt & Pepper noise is added to the image, the results retrieved by the other algorithms cannot be accepted. Comparatively, the result of NLFCM is satisfying, and the segmented regions are more homogeneous, which can be seen from Figs. 3c–k and 4c–k.

4.2 Results on medical images

In this subsection, three magnetic resonance(MR) images are involved in our experiment to evaluate the nine algorithms. As is well known, MR images are usually contaminated by Rician noise[24], resulting in the existence of partial volume effect(PVE) and intensity inhomogeneity(IIH)[9, 10]. Of the three images, two are from BrainWeb images[28], and the other is from [18], illustrated in Figs. 5a, 6a and 7a. There are 181 × 217 pixels in Figs. 5a and 6a, while 256 × 255 pixels in Fig. 7a. In our experiments, Rician noise is generated by a code obtained from Ged Ridgway[29], and the first two images are corrupted by 30 % Rician noise(s = 30), and the third image is corrupted by 10 % Rician noise(s = 10), shown in Figs. 5b, 6b and 7b. The number of clusters is predefined as 4, and the segmentation results of the nine algorithms are presented in Figs. 5c–k, 6c–k and 7c–k, respectively.

Fig. 5
figure 5

Segmentation Results of one medical image corrupted by 10% Rician noise. a Original image. b Noisy image corrupted by Rician noise of level 30%. c FCM result. d BCFCM result. e FCMS1 result. f FCMS2 result. g EnFCM result. h FGFCM result. i FLICM result. j KWFLICM result. k NLFCM result

Full size image
Fig. 6
figure 6

Segmentation results of another medical image corrupted by 30% Rician noise. a Original image. b Noisy image corrupted by Rician noise of level 30%. c FCM result. d BCFCM result. e FCMS1 result. f FCMS2 result. g EnFCM result. h FGFCM result. i FLICM result. j KWFLICM result. k NLFCM result

Full size image
Fig. 7
figure 7

Segmentation results of another medical image corrupted by 30% Rician noise. a Original image. b Noisy image corrupted by Salt & Pepper Rician noise of level 10%. c FCM result. d BCFCM result. e FCMS1 result. f FCMS2 result. g EnFCM result. h FGFCM result. i FLICM result. j KWFLICM result. k NLFCM result

Full size image

As is shown in Figs. 5, 6 and 7, much noise exists in the results of FCM, BCFCM, FCMS1, FCMS2, FGFCM, EnFCM, a small portion of noise exists in the results of KWFLICM, and almost all noise is removed by FLICM and NLFCM. Also, due to not considering the gray information in the fuzzy factor, many details disappear in the result of FLICM while appear in the result of NLFCM, shown in Fig. 7i and k.

To compare the algorithms quantitatively, V pc and V pe are adopted to measure the nine algorithms, and corresponding values on the three medical images are tabulated in Table 4. It is to be noted that the V pc and V pe values are the average values of 10 runs. As is shown from Table 4, NLFCM has the best V pc and V pe, meaning that the membership values in the proposed algorithm are more crisp.

Table 4 Comparison of V pc and V pe on medical images with Rician noise(30%)
Full size table

In addition, the task of image segmentation for brain images is to partition the image into four parts: background, cerebral spinal fluid(CSF), gray matter(GRY) and white matter(WHT). Compared with the referenced images of BrainWeb, the SAs on CSF, GRY and WHT of the nine algorithms are presented in Table 5. As is shown from Table 5, the segmentation accuracy of NLFCM is higher than that of the other algorithms, meaning that the proposed algorithm is effective, and can segment corresponding tissues accurately.

Table 5 Comparison of SAs for Brain images with Rician noise(30%)
Full size table

4.3 Results on natural images

In this subsection, the experiments on three natural images will be illustrated. Figs. 8a and 9a with 190 × 123 and 189 × 123 pixels are from [18], while Fig. 10a with 481 × 321 pixels is selected from [30]. The number of clusters of the three images is assigned as 2, 3 and 2, respectively. To compare the results with other algorithms, Figs. 8a and 9a are corrupted by Salt & Pepper noise(15 %) and Gaussian noise(15 %), shown in Figs. 8b and 9b, and the salient region is required to be retrieved in Fig. 10a. The segmentation results of the nine algorithms on the three natural images are presented in Figs. 8c–k, 9c–k and 10c–k.

Fig. 8
figure 8

Segmentation results of the first natural image. a Original image. b Noisy image corrupted by Salt & Pepper noise of level 15%. c FCM result. d BCFCM result. e FCMS1 result. f FCMS2 result. g EnFCM result. h FGFCM result. i FLICM result. j KWFLICM result. k NLFCM result

Full size image
Fig. 9
figure 9

Segmentation results of the second natural image. a Original image. b Noisy image corrupted by Gaussian noise of level 15%. c FCM result. d BCFCM result. e FCMS1 result. f FCMS2 result. g EnFCM result. h FGFCM result. i FLICM result. j KWFLICM result. k NLFCM result

Full size image
Fig. 10
figure 10

Segmentation results of the third natural image. a Original image. b FCM result. c BCFCM result. d FCMS1 result. e FCMS2 result. f EnFCM result. g FGFCM result. h FLICM result. i KWFLICM result. j NLFCM result

Full size image

As is shown from Fig. 8c–h, there is still much noise in the results of FCM, BCFCM, FCMS1, FCMS2, EnFCM and FGFCM, meaning that the results of these algorithms cannot be accepted. From Fig. 8i–j we can see that two little regions exist in the segmentation results of FLICM and KWFLICM. From the segmentation results in Fig. 8 we can see that the visual effect of NLFCM is best, followed by FLICM and KWFLICM, and then the other algorithms. From Fig. 9c–k, we can see that the visual effect of FLICM, KWFLICM and NLFCM are better than the other algorithms.

As can be seen from the results of Fig. 10, there are many textures in Fig. 10a, and traditional algorithms without considering texture features cannot obtain satisfying salient regions, such as FCM, BCFCM, FCMS1, FCMS2, FGFCM, shown in Fig. 10c–h. Also, some small regions still exist in the results of FLICM and KWFLICM, shown in Fig. 10i–j, while the salient region obtained by NLFCM is satisfying. In addition, V pc and V pe are compared in our experiments, and the results are presented in Table 6. As is shown in Table 6, more crisp membership values are obtained by NLFCM, resulting in higher V pc and smaller V pe.

Table 6 Comparison of V pc and V pe on natural images
Full size table

4.4 Discussion of the radius of the search window

As is analyzed from NLFCM, the time complexity of the proposed algorithm is O(n(2r + 1)2 C I), where I is the number of iterations. Also, with the increment of the parameter r, more non-local information will be involved in enhancing the robustness of the algorithm. However, considering more information means low efficiency. Therefore, it is not reasonable to assign the radius r too large value for the complexity of computing. In our experiments, the selection of the radius is performed by trial-and-error method, and the noise level is also considered. That is to say, when the noise level is high, one big radius is needed, and vice versa. As is shown in Fig. 3, Salt & Pepper noise is comparably more difficult to be removed than Gaussian noise. Hence, one large radius is needed when the image is corrupted by Salt & Pepper noise, resulting in low efficiency but good performance. The following figure illustrates the relationship between the radius and the segmentation result.

As is shown in Fig. 11, image artifacts exist in the segmentation result of NLFCM if the radius of the search window is assigned 1, just as the result of FLICM in Fig. 11b and b. When r is assigned 2, there are still two little noisy regions, labelled by the red box in Fig. 11d. When the radius of the search window is assigned 3, no artifacts exist in the segmentation results. In the experiments, we try to construct the relationship between the radius r and the noise degree. However, it is one difficult task. Many factors will affect the selection of the radius, such as the type of the given image, the noise degree, the type of image noise, etc. In the future work, the relationship between the radius and the noise degree will be investigated under condition that the types of image and noise are fixed, and the balance between the performance and computation cost will be also considered. Generally speaking, with the increment of the radius r, NLFCM is computationally consuming, since more pixels are involved in computing the pixel relevance and the fuzzy factor has to be computed in each iteration. However, this drawback can be compensated for its good performance, as is illustrated above.

Fig. 11
figure 11

Segmentation results with different radius of the search window. a Image corrupted by noise. b FLICM result. c NLFCM result(r = 1). d NLFCM result(r = 2). e NLFCM result(r = 3)

Full size image

5 Conclusion

In this paper, one improved fuzzy clustering algorithm named NLFCM is proposed, which is on the basis of FLICM and free of parameters. In the proposed algorithm, pixel relevance is computed based on the similarity of image patches, and with the help of pixel relevance, non-local information can be adopted to guide the procedure of image segmentation. As a result, the robustness of the algorithm can be enhanced greatly. Experimental results on synthetic , medical and natural images show that the proposed algorithm can improve the performance of image segmentation, and can remove noise of any type.