1 Introduction

Image segmentation is the core technology of image processing, analysis, recognition and understanding (Sun et al. 2016a, b; Zhu et al. 2016a, b). With the development of Internet, information processing and related areas, many topics are relevant to image processing (Li et al. 2014a, b, 2017b, d). The success of many topics, such as object recognition, video surveillance, depends on accurate segmentation (Huang et al. 2017; Li et al. 2017c). Also, image segmentation emerges in new areas such as copy–move forgery detection (Li et al. 2017a), in which the test image is segmented into semantically independent patches prior to keypoint extraction, and the copy–move regions can be detected by matching between these patches. In essence, image segmentation is to group the pixels in the given image into different clusters according to their features. In many cases, the given image is complex, and many kinds of artifacts exist. When the pixels are contaminated by noise, the feature values of the pixels will be affected greatly, and conventional segmentation algorithms perform poor. To the best of our knowledge, there are no segmentation algorithms that can be performed on images of any kind. Also, in other complex images such as medical images, the feature values of pixels are not the true values due to the imaging principle. In medical images, the intensity of pixels is the average value of the pixels locating in the same slice, which may belong to different organs or tissues (Ji et al. 2010, 2011). Therefore, conventional “hard” methods that assign the pixel to one organ or tissue are not suitable to segment complex images due to the relevance between neighbor pixels. In this paper, fuzzy clustering approaches will be investigated, because they can admit one pixel to several classes concurrently and can retain information as much as possible.

Fuzzy C-means, abbreviated as FCM, is a typical fuzzy clustering algorithm which is simple and efficient. It was proposed by  Dunn (1974) and later extended by  Bezdek (1981). In FCM, only pixel intensity is considered, and as a result, FCM is sensitive to noise and other image artifacts (Pham and Prince 1999; Pham 2001). Aiming at this problem, many improved versions were proposed. In these improved algorithms, neighbor information is introduced into the objective function, and the segmentation results are improved greatly. However, when used in complex images with high-level noise, these improved algorithms still perform poor, and the reason is that only information in the neighbor window is utilized. In our opinion, all information in the given image should be utilized, not limited to local ones (Zhao et al. 2011a, b; Zhao 2013). For example, there are many pixels with similar neighborhood configuration to one given pixel and can be utilized to enhance the robustness of the algorithm. These pixels may exist far from the given pixel and cannot be considered in the improved algorithms mentioned above (Liu et al. 2015; Gong et al. 2013). In this paper, the information provided by the neighbor pixels is called local information, while that provided by the pixels far from the given pixel is called non-local information. In this paper, one improved fuzzy algorithm is proposed, which can be divided into two phases. In the first phase, the model of pixel relevance between different pixels is investigated. Based on pixel relevance, non-local information is incorporated into fuzzy clustering algorithm in the second phase, which can enhance the robustness to noise and image artifacts.

Fig. 1
figure 1

Pixel relevance between neighbor pixels and the central one. a Image with noise; b intensities of pixels in the red box; c pixel relevance between the central pixel and the neighbor pixels (color figure online)

Full size image
Fig. 2
figure 2

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

Full size image
Fig. 3
figure 3

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

Full size image
Table 1 SA (%) on the first synthetic image with different noises
Full size table
Table 2 Comparison of partition coefficient \(V_\mathrm{pc}\) on the synthetic images with different noise
Full size table
Table 3 Comparison of partition entropy \(V_\mathrm{pe}\) on the synthetic images with different noise
Full size table
Fig. 4
figure 4

Segmentation results of one medical image corrupted by 30% Rician noise. a Noisy image corrupted by Rician noise of level 30%. b FCM result. c BCFCM result. d BCFCMS1 result. e BCFCMS2 result. f EnFCM result. g FGFCM result. h FLICM result. i KWFLICM result. j PRFLICM result

Full size image
Fig. 5
figure 5

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

Full size image
Fig. 6
figure 6

Segmentation results of another medical image corrupted by 30% Rician noise. a Noisy image corrupted by Rician noise of level 10%. b FCM result. c BCFCM result. d BCFCMS1 result. e BCFCMS2 result. f EnFCM result. g FGFCM result. h FLICM result. i KWFLICM result. j PRFLICM result

Full size image

The rest of the paper is organized as follows. Section 2 introduces the related algorithms, including conventional fuzzy C-means algorithm and typical improved ones. The model of pixel relevance is proposed in Sect. 3, and then one improved algorithm based on non-local information and fuzzy clustering algorithm is proposed. Section 4 presents the corresponding experiments of the proposed algorithm on different images, and one short but important conclusion is drawn in the last section.

2 Related works

2.1 Conventional fuzzy C-means algorithm

Fuzzy C-means is a typical clustering algorithm in pattern recognition and machine learning, the target of which is to minimize the weighted distance between pixels and cluster centers. In FCM, the objective function is defined as

$$\begin{aligned} F=\sum _{i=1}^C\sum _{j=1}^n u_{ij}^m d_{ij}^2, \end{aligned}$$
(1)

where n is the number of pixels in the given image, C is the predefined number of clusters, and \(u_{ij}\in [0,1]\) is the membership of the jth pixel belonging to the ith cluster, satisfying \(\sum _{i=1}^C u_{ij}=1\). \(m>1\) is a parameter to control the fuzziness of the clustering results. \(d_{ij}=\Vert x_j-v_i\Vert \), where \(x_j\) is the intensity value of the jth pixel and \(v_i\) is the value of the ith cluster center. To minimize the objective function with the constraints, Lagrange multiplier method is adopted, and the following function will be created.

$$\begin{aligned} J=\sum _{i=1}^C\sum _{j=1}^n u_{ij}^m d_{ij}^2 +\sum _{j=1}^n \lambda _j\left( \sum _{i=1}^C u_{ij}-1\right) . \end{aligned}$$
(2)

Based on \(\displaystyle \frac{\partial J}{\partial u_{ij}}=0\) and \(\displaystyle \frac{\partial J}{\partial v_{i}}=0\), the update equations of the cluster centers and the memberships will be deduced as follows.

$$\begin{aligned} u_{ij}= & {} \displaystyle \frac{\Vert x_j-v_i\Vert ^{-2/(m-1)}}{\sum _{k=1}^C \Vert x_j-v_k\Vert ^{-2/(m-1)}}, \end{aligned}$$
(3)
$$\begin{aligned} v_i= & {} \displaystyle \frac{\sum _{j=1}^n u_{ij}^m x_j}{\sum _{j=1}^n u_{ij}^m}. \end{aligned}$$
(4)

If \(\max \{|u_{ij}^{p+1}-u_{ij}^p|\}<\varepsilon \) holds or the predefined number of iterations is satisfied, the procedure will be terminated, in which \(\varepsilon \) is the predefined threshold. Then the maximum membership procedure method will be adopted to retrieve the segmentation results, which will assign the jth pixel to the kth class with the highest membership.

As shown in Eq. (1), only intensity information is utilized in FCM. As a result, FCM is sensitive to noise and cannot retrieve good results in complex images. To solve this problem, many improved algorithms were proposed in relevant literature, and several typical ones are illustrated as follows.

2.2 FCM-related algorithms

To make fuzzy clustering algorithms more robust, many improved algorithms were proposed, such as bias-corrected version of FCM (denoted as BCFCM) (Ahmed et al. 2002), BCFCMS1 and BCFCMS2 (Chen and Zhang 2004), enhanced FCM (denoted as EnFCM) (Szilágyi et al. 2003), fast generalized fuzzy C-means clustering (denoted as FGFCM) (Cai et al. 2007) and fuzzy local information C-means algorithm (denoted as FLICM) (Krinidis and Chatzis 2010). In these improved algorithms, various spatial information is added to the objective function of FCM. For example, in FLICM, a fuzzy factor has been added to reflect the impact of neighbor information, which is defined as follows.

$$\begin{aligned} G_{ij}=\displaystyle \sum _{r\in N_j}\frac{1}{d_{jr}+1}(1-u_{ir})^m \Vert x_r-v_i\Vert ^2. \end{aligned}$$
(5)

With the help of \(G_{ij}\), the corresponding membership values of the all pixels that falling into the local window will converge to a similar value, including noisy pixels and non-noisy ones (Gong et al. 2013). By adding the fuzzy factor, the objective function of FLICM can be defined as

$$\begin{aligned} F=\sum _{i=1}^C\sum _{j=1}^n \left[ u_{ij}^m(x_j-v_i)^2+G_{ij}\right] . \end{aligned}$$
(6)

Also, the objective function is minimized with the constraints \(\sum _{i=1}^C u_{ij}=1(j=1,2,\ldots ,n)\). Using Lagrange multiplier method, the memberships and cluster centers can be updated as follows.

$$\begin{aligned} u_{ij}= & {} \displaystyle \frac{1}{\sum _{k=1}^C \left( \displaystyle \frac{\Vert x_j-v_i\Vert ^2+G_{ij}}{\Vert x_j-v_k\Vert ^2+G_{kj}}\right) ^{1/(m-1)}}, \end{aligned}$$
(7)
$$\begin{aligned} v_i= & {} \displaystyle \frac{\sum _{j=1}^nu_{ij}^m x_j}{\sum _{j=1}^nu_{ij}^m}. \end{aligned}$$
(8)

Though the robustness of FCM can be improved with the help of the spatial information, these improved algorithms perform poor when the image is complex or the noise level is high. This paper holds the idea that the reason for such poor performance is that only the spatial information of local window is utilized. However, there is much information that can be utilized in the procedure of image segmentation. For example, there are many pixels with similar configurations to the given pixel, not limited to local context. However, these pixels are located far away from the given pixel and cannot be considered in the improved algorithms mentioned above. To overcome this, one improved clustering algorithm is presented in this paper, the starting point of which is to replace the local information with non-local information.

3 Pixel relevance

In the algorithms mentioned in Sect. 2, the impact of spatial information on the central pixel is weighted by one parameter, such as \(\alpha \) in BCFCM and EnFCM, \(S_{ij}\) in FGFCM and the fuzzy factor \(G_{ij}\) in FLICM. As analyzed in Buades et al. (2008) and Zhang et al. (2012), this impact can be seen as pixel relevance between neighbor pixel and the central one. If pixel relevance between neighbor pixels is more accurate, much better results can be retrieved. However, pixel relevance in these improved algorithms cannot reflect the true relation between pixels. For example, pixel relevance in BCFCM is assigned as a constant, and this setting leads to a blurring effect near the edges. When the noise level is high, current improved algorithms cannot perform well. In  Zhang et al. (2017a, b), we found that the statistical information is insensitive to image artifacts. Therefore, we will construct an image patch centering the given pixel, and pixel relevance will be measured by using the similarity of corresponding image patches.

Given two pixels i and j, two image patches \(N_i\) and \(N_j\) centering around the two pixels are constructed, and the pixel relevance between the two pixels is defined as

$$\begin{aligned} S(i,j)=1-\displaystyle \frac{\sum _{p=1}^{|N_i|} \left| N_i^p-N_j^p\right| }{|N_i|*255}, \end{aligned}$$
(9)

where \(|N_i|\) is the cardinality of \(N_i\) and \(N_i^p\) is the pth value of image patch \(N_i\). The constructed image patches are often with different geometrical structures due to the positions of pixels. In order to compute pixel relevance accurately, the geometrical structures of \({N_i}\) and \({N_j}\) are desired to be the same, which can make our algorithm more robust to image artifacts. As shown in Eq. (9), if the two image patches are the same, S(i, j) is equal to 1. The more similar the two patches are, the closer S(i, j) is to 1, and vice versa.

We take one example shown in Fig. 1a to illustrate the computation of pixel relevance. The intensities of pixels in the red box are tabulated in Fig. 1b, and corresponding pixel relevances between the central pixel (in yellow) and the considered pixels are presented in Fig. 1c. According to Eq. (9), the value of pixel relevance between the central pixel and the neighbor pixels depends on the similarity between corresponding image patches. As is shown in Fig. 1c, pixel relevance between the pixel with intensity value 78 and the central pixel is larger than that between the pixel with intensity value 112 and the central pixel, even though the intensity value of the central pixel is closer to the pixel with intensity value 112, larger than the pixel with intensity value 78.

Compared with previous work (Zhang et al. 2017a), pixel relevance is unnecessary to be normalized in this paper. The reason is that when non-local information is considered, all information in the search window will be utilized. When the pixel relevance is normalized, many pixel relevance values will be close to 0, which makes the non-local information play low role in the procedure of image segmentation.

With the help of pixel relevance, more information can be utilized in the procedure of image segmentation, not limited to local window. However, considering more information means low efficiency. To balance the segmentation results and efficiency, one search window will be defined, and only the pixels in the search window with similar configurations will play positive role in guiding image segmentation. In this paper, the search window centering around the ith pixel will be denoted as \(W_i^r\), where r is the radius. In the following experiments, r is assigned as 3, meaning that the size of \(W_i\) is \(7\times 7\).

Table 4 Comparison of \(V_\mathrm{pc}\) and \(V_\mathrm{pe}\) on medical images with Rician noise (30%)
Full size table
Table 5 Comparison of SAs for brain images with Rician noise (30%)
Full size table

4 Proposed algorithm

Based on the analysis mentioned above, this section will introduce pixel relevance into the objective function of the proposed algorithm. For a pixel, the pixels with higher relevance will have similar membership, playing positive role in the procedure of image segmentation. That is to say, if S(i, j) is big, the damping extent of the jth pixel on the ith pixel should be big, and vice versa. Then the membership of the pixels with higher relevance will converge to similar values and in turn enhance the robustness of the proposed algorithm. Therefore, the fuzzy factor in the proposed algorithm can be defined as follows.

$$\begin{aligned} G_{ij}=\displaystyle \sum _{k\in W_j^r}S(j,k)(1-u_{ik})^m \Vert x_k-v_i\Vert ^2. \end{aligned}$$
(10)

Considering pixel relevance is utilized in the improved algorithm, the proposed algorithm is denoted as PRFLICM, and the framework is illustrated in Algorithm 1.

Fig. 7
figure 7

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

Full size image
Fig. 8
figure 8

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

Full size image
figure a

5 Experiments and analysis

In order to verify the effectiveness of our algorithm, the comparison of the segmentation results will be performed between the proposed algorithm and the competing algorithms, including FCM, FCMS, FCMS1, FCMS2, FGFCM, EnFCM, FLICM and KWFLICM. Corresponding parameters in the related algorithms are assigned as follows: \(m=2\), \(\varepsilon =1e-5\) and \(3\times 3\) neighborhood is adopted for local search. \(\alpha \) is assigned to 2 in BCFCM, FCMS1, FCMS2 and EnFCM. \(\lambda _G\) and \(\lambda _S\) are assigned to 2 and 3 in FGFCM, respectively.

Also, three evaluation criteria have been adopted to compare the algorithms.

Fig. 9
figure 9

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

Full size image
Table 6 Comparison of \(V_\mathrm{pc}\) and \(V_\mathrm{pe}\) on natural images
Full size table
  1. (1)

    Segmentation accuracy (SA) is defined as the sum of the correctly classified pixels divided by the number of all pixels. Formally,

    $$\begin{aligned} \mathrm{SA}=\displaystyle \sum _{i=1}^C\frac{A_i\cap C_i}{\sum _{j=1}^C C_j}, \end{aligned}$$
    (11)

    where \(A_i\) is the set of pixels belonging to the ith class; \(C_i\) is the set of pixels belonging to the ith class in the reference image.

  2. (2)

    Partition coefficient \(V_\mathrm{pc}\) (Bezdek 1975a) is one validity function to evaluate the algorithms, defined as

    $$\begin{aligned} V_\mathrm{pc}=\sum _{i=1}^C\sum _{j=1}^n u_{ij}^2/n. \end{aligned}$$
    (12)
  3. (3)

    Partition entropy \(V_\mathrm{pe}\) (Bezdek 1975b) is another validity function to evaluate the clustering algorithms, defined as

    $$\begin{aligned} V_\mathrm{pe}=-\sum _{i=1}^C\sum _{j=1}^n \left( u_{ij}\log u_{ij}\right) /n, \end{aligned}$$
    (13)

    where n is the number of pixels in the given image.

Obviously, one good algorithm should have higher SAs and less fuzziness, and the latter means bigger \(V_\mathrm{pc}\) and smaller \(V_\mathrm{pe}\).

5.1 Experiments on synthetic images

The first experiment is performed on two synthetic images. To illustrate the advantage of the proposed algorithm, various noise is added to the image: the first image is with Gaussian noise of 20% level, and the second image is with Salt&Pepper noise of 30% level. The segmentation results of corresponding algorithms are illustrated in Figs. 2 and 3.

As shown in Figs. 2 and 3, image artifacts still exist in the results of FCM, BCFCMS1, BCFCMS2, EnFCM and FGFCM, and all noise is removed by BCFCM, FLICM, KWFLICM and PRFLICM. Also, we compare the SAs of these algorithms on the first synthetic image with different noise, tabulated in Table 1.

As listed in Table 1, the SAs of the proposed algorithm are higher than those of the other improved algorithms. Also, the values of \(V_\mathrm{pc}\) and \(V_\mathrm{pe}\) are compared, shown in Tables 2 and 3. It is to be noted that the \(V_\mathrm{pc}\) and \(V_\mathrm{pe}\) values are the average values of 10 runs.

As tabulated in Tables 2 and 3, the partition coefficients and the partition entropies of the proposed algorithm are better than those of the other algorithms, meaning that considering pixel relevance to guide the procedure of image segmentation is reasonable. Moreover, the two parameters of PRFLICM are more stable, comparable to those of KWFLICM and better than the other algorithms.

5.2 Experiments on medical images

PRFLICM is performed further on three medical images, including 2 magnetic resonance (MR) images from BrainWeb images (Buades et al. 2008) and one computed tomography (CT) image from  Krinidis and Chatzis (2010). As introduced in  Gong et al. (2013), medical images are often contaminated with Rician noise. In our experiments, the first two images are corrupted by 30% Rician noise (\(s=30\)) MathWorks, and the third image is corrupted by 10%. The number of clusters is predefined as 4, and the segmentation results of the nine algorithms are presented in Figs. 4b–j, 5b–j and 6b–j.

As shown in Figs. 4, 5 and 6, noise still 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 PRFLICM.

To compare these algorithms quantitatively, \(V_\mathrm{pc}\) and \(V_\mathrm{pe}\) are adopted, and corresponding values on these three images are tabulated in Table 4. As shown, PRFLICM has the best \(V_\mathrm{pc}\) and \(V_\mathrm{pe}\), meaning that the membership values in the proposed algorithm are more crisp.

Moreover, 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 (Buades et al. 2008), the SAs on CSF, GRY and WHT of the nine algorithms are presented in Table 5. As shown from Table 5, the segmentation accuracy of PRFLICM is higher than that of the other algorithms, meaning that our algorithm can segment different tissues accurately.

5.3 Experiments on natural images

In this subsection, the proposed algorithm is performed on three natural images, two from  Besser (1990), and the other is from  Krinidis and Chatzis (2010). The number of clusters of the three images is predefined as 2, 3 and 2. To compare the results with other algorithms, the first two figures are contaminated with Salt&Pepper noise (15%) and Gaussian noise (15%), and the third figure is to retrieve the saliency region. The segmentation results of the nine algorithms on the three natural images are presented in Figs. 7b–j, 8b–j and 9b–j.

\(V_\mathrm{pc}\) and \(V_\mathrm{pe}\) are compared in our experiments, and the results are presented in Table 6. As shown from Table 6, more crisp membership values are obtained by PRFLICM, resulting in higher \(V_\mathrm{pc}\) and smaller \(V_\mathrm{pe}\).

6 Conclusions and future work

In this paper, an improved clustering algorithm is proposed for image segmentation. In our algorithm, based on the fact that statistical information is insensitive to image artifacts, image patches are constructed centering corresponding pixels, and pixel relevance is measured based on the similarity of corresponding image patches. With the help of pixel relevance, non-local information is added into the procedure of image segmentation. Then, more information can be utilized to guide the procedure of image segmentation, which can improve the robustness of the proposed algorithm. Experiments on synthetic, medical and natural images show that our algorithm outperforms other FCM-related algorithms. However, the selection of the radius of search window is a key issue for the proposed algorithm. The large radius will be adopted to resist the effect of high-level noise, while a small one will be done to resist the effect of low-level noise. In addition, the boundaries of the segmentation results may be blurred, shown in Figs. 3 and 8. Hence how to select the radius of the search window to balance the segmentation effect and efficiency should be investigated in the future work, which will also deblur the boundaries of the segmentation results.