A multi-objective interval valued fuzzy clustering algorithm with spatial information for noisy image segmentation

Abstract

Interval valued fuzzy c-means (IVFCM) clustering algorithm is one of effective clustering algorithms. When applied to image segmentation, IVFCM includes three problems as follows: (1) It is sensitive to the initial values of algorithm and may easily fall into the local optimal. (2) The algorithm is sensitive to the image noise and cannot obtain the satisfying performance on images corrupted by noise. (3) It always performs image segmentation under one objective function, therefore it cannot meet multiple practical needs. In order to address these problems, a multi-objective interval valued fuzzy clustering algorithm is proposed in this paper. This method constructs two novel interval valued fuzzy fitness functions which utilize the non-local spatial information of the image. Then a new mutation operator combining the interval valued fuzzy information of image is designed. Furthermore, an effective interval valued fuzzy cluster validity index using the non-local spatial information of image is presented to select a single solution from the non-dominated solution set. Experimental results show that the proposed method behaves well in noisy image segmentation.

Keywords

Image segmentation multi-objective optimization interval valued fuzzy clustering non-local spatial information

1 Introduction

Image segmentation, the key step from image processing to image analysis, is a technology and process that divides images into specific and unique regions and extracts the target of interest [1]. Existing image segmentation methods are mainly divided into the following categories: clustering algorithms [2 –4], thresholding techniques [5], region-based approaches [6] and combination of some presented approaches [7]. Since 1998, researchers have been improving the existing image segmentation methods and applying some new theories and methods of other disciplines to image segmentation.

Among clustering algorithms, fuzzy c-means (FCM) clustering algorithm [8] is widely used for image segmentation and has been applied to various areas. However, for FCM and other fuzzy clustering algorithms, the fuzzy membership design includes various uncertainties (e.g., fuzzifier, prototypes, distance measure, etc.). To manage the uncertainty associated with the fuzzifier m, the fuzzy set is extended to an interval type-2 fuzzy set using two fuzzifiers m₁ and m₂ which creates a footprint of uncertainty for the fuzzifier m. Then the interval type-2 fuzzy set is incorporated into FCM to present interval type-2 fuzzy c-means (IT2FCM) approach [9]. In order to process the uncertainty of prototypes, a modified interval valued fuzzy c-means (IVFCM) clustering method was used in dealing with the interval-valued data in [10]. For the uncertainties of distance measure, D’Urso et al. [11] proposed to employ a robust metric based on the exponential distance in the framework of the fuzzy c-medoids clustering mode. However, when applied to image segmentation, FCM, IT2FCM and IVFCM methods encounter two problems. The first issue is that they are sensitive to the initial values of algorithms and easily fall into the local optimums. To solve the problem, Wang et al. [12] presented a global fuzzy c-means clustering algorithm (GFCM) which obtains better clustering results through a deterministic global search procedure. Furthermore, evolutionary algorithms such as genetic algorithm (GA) [13], simulated annealing (SA) [14], ant colony optimization (ACO) [15], and particle swam optimization (PSO) [16] have been successfully applied in fuzzy clustering methods. For example, a novel fuzzy clustering algorithm based on particle swarm optimization was proposed in [17] which achieves global optimized results and owns rapid convergence speed. The second problem is that FCM, IT2FCM and IVFCM algorithms are sensitive to image noise owing to the fact that these methods do not take the spatial information of images into consideration. In order to address this issue, many researchers introduced the image spatial information into the objective functions of fuzzy clustering methods [18 –21]. For FCM, Ahmed et al. [18] modified the objective function of FCM by incorporating a local spatial neighborhood term and proposed FCM algorithm with spatial information (FCM_S). To reduce the computational complexity, Chen and Zhang [19] evaluated the neighbor of each pixel in a pre-filtering step before performing the FCM clustering. They denoted the methods using the neighborhood mean values and median values of the pixel by FCM_S1 and FCM_S2, respectively. In [20], a weighted image patch-based FCM (WIPFCM) algorithm was proposed by using image patches to replace pixels and constructing a weighting scheme to calculate the weights of pixels in each image patch. For images heavily contaminated by noise, the local spatial information cannot obtain satisfying segmentation performance. Therefore, Zhao et al. [21] introduced the non-local spatial information derived from a large image domain of the pixel to construct the spatial constraint term and proposed a fuzzy c-means clustering algorithm with non-local spatial information (FCM_NLS). For IT2FCM, Qiu et al. [22] proposed a modified interval type-2 FCM clustering algorithm which utilized two fuzzifiers and a spatial constraint on the membership functions of IT2FCM to remove image noise.

Various algorithms like FCM, IT2FCM, FCM_S, FCM_NLS, WIPFCM, etc. have been used for the purpose of image segmentation, but most of them use a single objective function to be optimized, which is not equally applicable to all kinds of data sets and cannot meet diverse segmentation needs. To solve this problem, researchers proposed many multi-objective clustering approaches [23 , 29] which optimize multiple validity measures simultaneously. In [23], two cluster validity measures, J_m [24] and Xie-Beni (XB) [25] indexes were optimized at the same time. However, there is a problem that these two validity measures are not completely independent to each other, which may not obtain the good Pareto-optimal solutions. Based on this work, Mukhopadhyay et al. [26] utilized three cluster validity measures including J_m, XB, and PBM [27] as the objective functions. The number of clusters in these methods mentioned above was specified in advance. For the method in [28], it used a variable string length coded strategy to encode cluster centers, so that the number of clusters could be automatically evolved. In addition, two objective functions, global fuzzy compactness and fuzzy separation, were optimized simultaneously and a validity index I [29] was used to obtain a single solution from the final non-dominated solution set.

When applied to image segmentation, interval valued fuzzy clustering algorithms suffer from high sensitivity to noise and initial values. To overcome these shortcomings and obtain satisfactory segmentation performance by optimizing multiple clustering criteria simultaneously, in this paper, we propose a multi-objective interval valued fuzzy clustering algorithm (MIFCA) for image segmentation. In this algorithm, the non-local spatial information derived from the image has been introduced into two completely independent interval valued fuzzy fitness functions viz., global interval valued fuzzy compactness function and interval valued fuzzy separation function, which are optimized simultaneously. Moreover, to overcome premature convergence and maintain the diversity of the population, we design a novel interval valued fuzzy mutation operator utilizing the vagueness and uncertainty of the image. In the final generation, a Pareto-optimal non-dominated set of solutions is produced and it is necessary to choose a single solution from thenon-dominated set. So, an interval valued fuzzy cluster validity index incorporating the non-local spatial information derived from the image is used to select a particular solution. In the experiments, we compared our algorithm with seven other methods, viz. FCM, FCM_S1, IT2FCM, IVFCM, IFCM [30], MOVGA [28] and MSFCA [31] on a synthetic image, some Berkeley segmentation images and MR images contaminated by noise. The experimental results show that MIFCA behaves well in noisy images segmentation.

The remainder of the paper is organized as follows. In Section 2, we present the IVFCM clustering algorithm. Our proposed MIFCA method is described in Section 3. In Section 4, experimental results are presented. Finally, some concluding remarks and discussions are drawn in Section 5.

2 Interval valued fuzzy c-means clustering algorithm

The IVFCM clustering algorithm is a suitable extension of the standard FCM algorithm. It performs a fuzzy partition and a prototype for each cluster by optimizing the following objective function based on a suitable squared Euclidean distance between vectors of intervals:

$\begin{matrix} J_{IVFCM} = \\ \sum_{i = 1}^{C} \sum_{k = 1}^{n} (u_{ik})^{m} \sum_{j = 1}^{p} [{∥ a_{k}^{j} - α_{i}^{j} ∥}^{2} + {∥ b_{k}^{j} - β_{i}^{j} ∥}^{2}] \end{matrix}$ (1) where u_ik ∈ [0, 1] represents the membership degree of the kth interval valued pattern $x_{k}^{j} = [a_{k}^{j}, b_{k}^{j}], (1 \leq k \leq n, 1 \leq j \leq p)$ belonging to the ith cluster $v_{i}^{j} = [α_{i}^{j}, β_{i}^{j}], (i = 1, 2, \dots, C)$ , m ∈ (1, ∞) is a weighting exponent on each fuzzy membership that determines the amount of fuzziness of the resulting classification, and ∥∥ denotes the Euclidean norm. According to the definition of the fuzzy theory, the memberships satisfy the constraint that $\sum_{i = 1}^{C} u_{ik} = 1$ for each pattern. Through minimizing the objective function with this constraint, the fuzzy membership u_ik and cluster centers $v_{i}^{j} = [α_{i}^{j}, β_{i}^{j}]$ can be updated by following equations. $\begin{matrix} u_{ik} = \\ {[\sum_{l = 1}^{C} {(\frac{\sum_{j = 1}^{p} [{(a_{k}^{j} - α_{i}^{j})}^{2} + {(b_{k}^{j} - β_{i}^{j})}^{2}]}{\sum_{j = 1}^{p} [{(a_{k}^{j} - α_{l}^{j})}^{2} + {(b_{k}^{j} - β_{l}^{j})}^{2}]})}^{\frac{1}{m - 1}}]}^{- 1} \end{matrix}$ (2)

$α_{i}^{j} = \frac{\sum_{k = 1}^{n} (u_{ik})^{m} a_{k}^{j}}{\sum_{k = 1}^{n} (u_{ik})^{m}}, β_{i}^{j} = \frac{\sum_{k = 1}^{n} (u_{ik})^{m} b_{k}^{j}}{\sum_{k = 1}^{n} (u_{ik})^{m}}$ (3)

3 Multi-objective interval valued fuzzy clustering algorithm with spatial information (MIFCA)

3.1 Chromosome representation and population initialization

In MIFCA, each chromosome is made up of several interval real numbers which represent the cluster centers. For example, the pixel x_k can be expressed as $x_{k}^{I} = [μ (x_{k}), μ (x_{k}) + π (x_{k})]$ . The left endpoint of the interval real number is represented by membership degree μ (x_k) and the right endpoint is represented by sum of the membership degree μ (x_k) and the hesitation degree π (x_k). The membership degree μ (x_k) is calculated by normalizing gray values of image pixels and the degree of hesitation π (x_k) is calculated by 1 - μ (x_k) - υ (x_k), where υ (x_k) is the non-membership calculated by Yager operator: $υ (x_{k}) = (1 - μ (x_{k})^{δ})^{1 / - δ} 0 < δ < \infty$ (4)

If chromosome i encodes the centers of C_i clusters in d-dimensional space, then its length l_i is 2 × C_i × d, where C_i = max {2, rand () % C^*}, rand() is used to produce a random integer and C^* is the upper limit of the cluster number. Therefore, the number of clusters will change from 2 to C^*. For example, the chromosome i encoding three cluster centers in two-dimensional space is represented in Fig. 1. Each center is considered to be indivisible.

Fig.1

Chromosome representation.

3.2 Interval valued fuzzy fitness functions with non-local spatial information

In MIFCA, an interval valued fuzzy separation function S_I and a global interval valued fuzzy compactness function with non-local spatial information C_IN are constructed as two fitness functions to be optimized simultaneously. Before calculating these two fitness functions, the cluster centers V = {v₁, v₂, ⋯ , v_C} encoded in the chromosome should be firstly decoded. The fuzzy membership function between $x_{k}^{I}$ and $v_{i}^{I}$ can be computed by Equation (5). $u_{ik} = {(\sum_{l = 1}^{C} {(\frac{D (x_{k}^{I}, v_{i}^{I}) + β D (x_{k}^{I^{'}}, v_{i}^{I})}{D (x_{k}^{I}, v_{l}^{I}) + β D (x_{k}^{I^{'}}, v_{l}^{I})})}^{2 / (m - 1)})}^{- 1}$ (5) where m is the fuzzy exponent, $\begin{matrix} D (x_{k}^{I}, v_{i}^{I}) = max {μ (x_{k}) - μ (v_{i}), \\ (μ (x_{k}) + π (x_{k})) - (μ (v_{i}) + π (v_{i}))} \end{matrix}$ is the Hausdorff distance measure between interval value $x_{k}^{I} = [μ (x_{k}), μ (x_{k}) + π (x_{k})]$ of pixel x_k and interval value $v_{i}^{I} = [μ (v_{i}), μ (v_{i}) + π (v_{i})]$ of cluster center v_i, $x_{k}^{I^{'}}$ is the non-local spatial information of the kth pixel and β is the non-local spatial constrained parameter. In Equation (5), the non-local spatial information $x_{k}^{I^{'}}$ is computed by Equation (6) [32]. $x_{k}^{I^{'} (t)} = \sum_{j \in W_{k}^{r}} w_{kj}^{(t)} x_{j}^{I}$ (6) where $W_{k}^{r}$ is the similar patch group of each image pixel. $w_{kj}^{(t)}$ is the weight of image pixel $x_{j}^{I}$ in the window centered at the pixel $x_{i}^{I}$ and is computed using the Equation (7). $w_{kj}^{(t)} = \frac{1}{Z_{k}} exp (- {∥ N (x_{k}^{I (t - 1)}) - N (x_{j}^{I}) ∥}_{2, σ}^{2} / h^{2})$ (7) where $Z_{k} = \sum_{j \in W_{k}^{r}} exp (- {∥ N (x_{k}^{I (t - 1)}) - N (x_{j}^{I}) ∥}_{2, σ}^{2}$ /h²) is the normalized constant, ${∥ N (x_{k}^{I (t - 1)}) - N (x_{j}^{I}) ∥}_{2, σ}^{2}$ is used to calculate the similarity by a Gaussian weighted Euclidean distance and h is the smoothing parameter that controls the decay of the exponential function. t is the number of iteration. When the mean square error $MSE (X_{k}^{I^{'} (t)}, X_{k}^{I^{'} (t - 1)})$ is less than $\frac{MSE (X_{k}^{I^{'} (0)} - X_{k}^{I^{'} (1)})}{20}$ , the iteration is stopped. Subsequently the cluster center $v_{i}^{I}$ is updated using the following Equation (8).

$v_{i}^{I} = \frac{\sum_{k = 1}^{n} u_{ik}^{m} (x_{k}^{I} + β x_{k}^{I^{'}})}{\sum_{k = 1}^{n} u_{ik}^{m}}, 1 \leq i \leq C$ (8)

Then the global interval valued fuzzy compactness function C_IN is computed as Equation (9). $C_{IN} = \sum_{i = 1}^{C} \frac{\sum_{k = 1}^{n} u_{ik}^{m} (D (v_{i}^{I}, x_{k}^{I}) + β D (v_{i}^{I}, x_{k}^{I^{'}}))}{\sum_{k = 1}^{n} u_{ik}}$ (9)

Another fitness function is the interval valued fuzzy separation function S_I which is computed by Equation (10). $S_{I} = \sum_{i = 1}^{C} \sum_{j = 1, j \neq i}^{C} τ_{ij}^{m} D (v_{i}^{I}, v_{j}^{I})$ (10) where is the membership degree of $v_{j}^{I}$ to $v_{i}^{I}$ : $τ_{ij} = \frac{1}{\sum_{l = 1, l \neq j}^{C} {(\frac{D (v_{j}^{I}, v_{i}^{I})}{D (v_{j}^{I}, v_{l}^{I})})}^{2 / - m - 1}}, i \neq j$ (11)

3.3 Selection and Laplace crossover operation

In MIFCA, crowded binary tournament selection method [33] is used to generate the mating pool of chromosomes. The conventional binary tournament method along with a crowded comparison technique is used in this method.

When applying the Laplace crossover operator [34] for crossover, the cluster centers are considered to be indivisible, i.e., the crossover points can only lie in between two cluster centers. Suppose that p_c is the crossover probability, and the Laplace crossover operation works between two parent chromosomes. If $P^{1} = (v_{1}^{1}, v_{2}^{1}, \dots, v_{t}^{1})$ and $P^{2} = (v_{1}^{2}, v_{2}^{2}, \dots, v_{e}^{2})$ are selected from the population to be parents for crossover. First, a random number obeying the Laplace distribution is generated by Equation (12). $ξ = {\begin{matrix} f_{1} + f_{2} \times ln (2 \times rand), & rand < 0.5 \\ f_{1} - f_{2} \times ln (2 - 2 \times rand), & rand \geq 0.5 \end{matrix}$ (12) where rand is a random number that obeys a uniform distribution in [0, 1]. The location parameter f₁ and the scale parameter f₂ are all set to 0.5 [34]. Then the Laplace crossover operation is performed with the crossover probability p_c and the offspring chromosomes $V^{(1)} = (v_{1}^{(1)}, v_{2}^{(1)}, \dots, v_{t}^{(1)})$ and $V^{(2)} = (v_{1}^{(2)}, v_{2}^{(2)}, \dots, v_{e}^{(2)})$ are calculated by Equation (13). $\begin{matrix} v_{l}^{(1)} = v_{l}^{(1)} + ξ | v_{l}^{(1)} - v_{l}^{(2)} | \\ v_{g}^{(2)} = v_{g}^{(2)} + ξ | v_{g}^{(1)} - v_{g}^{(2)} | \end{matrix}$ (13)

3.4 Interval valued fuzzy poisson mutation operator

In the genetic algorithm, the mutation operator can generate new chromosomes and increase the diversity of the population. The design of the mutation operator mainly involves two aspects: the first aspect is the determination of the mutation location, and the second aspect is the determination of the gene value. For the traditional mutation operator, the mutation location is generally set as a single-valued data. The determination of the gene value is generally using a random number to guide the mutation or replace the original gene value. However, these traditional mutation operators do notmake full use of the interval valued fuzzy information of the image to guide the mutation operation, so that the performance of traditional genetic algorithms is not perfect. In order to solve this problem, we modify the traditional Poisson mutation operator [35] and propose an interval valued fuzzy Poisson mutation operator that uses the degree of hesitation to guide the mutation. If the ith cluster center $v_{i}^{I}$ is chosen to be mutated with the mutation probability p_m and the value of dth dimension is $v_{id}^{I}$ , a random number φ in the range [0,1] is generated with Poisson distribution and the mutated gene value is calculated byEquation (14). $v_{id}^{I} = {\begin{matrix} [μ (v_{id}) + φ π (v_{id}), μ (v_{id}) + (1 + φ) π (v_{id})], φ \geq 0.5 \\ [μ (v_{id}) - φ π (v_{id}), μ (v_{id}) + (1 - φ) π (v_{id})], φ < 0.5 \end{matrix}$ (14)

3.5 Elitism

As we know, in order to maintain a better spread of non-dominated solutions from the parent and child populations, the elitism operation is used to propagate the non-dominated solutions among the parent and child populations to the next generation.

3.6 Optimal solution interval valued fuzzy cluster validity index using the non-local spatial information

To choose a particular solution from the set of non-dominated solutions produced by the final generation, an interval valued fuzzy cluster validity index is constructed by using the non-local spatial information and is defined as Equation (15). $I (C) = (\frac{1}{C} \times \frac{E_{1}}{E_{C}} \times D_{C})$ (15) where C is the number of clusters. E_C and D_C are computed by Equations (16 and 17). $E_{C} = \sum_{i = 1}^{C} \sum_{k = 1}^{n} u_{ik} (D (x_{k}^{I}, v_{i}^{I}) + β D (x_{k}^{I^{'}}, v_{i}^{I}))$ (16) $D_{C} = {max}_{p, q = 1}^{C} D (v_{p}^{I}, v_{q}^{I})$ (17) where the membership function u_ik is calculated using Equation (5), β is the spatial constrained parameter and $x_{k}^{I^{'}}$ is the non-local spatial information of the kth pixel. $D (v_{p}^{I}, v_{q}^{I}) = max {| μ (v_{p}) - μ (v_{q}) |, | (μ (v_{p}) + π (v_{p})) - (μ (v_{q})$ + π (v_q)) | } is the Hausdorff distance.

3.7 Algorithm procedure

In this section, the procedure of the proposed method is presented as follows:

Input: Image I, the maximum number of generations G, the population size P, the crossover probability p_c, the mutation probability p_m, the spatial constrained parameter β, the maximum upper bound of the cluster number C^max.

Step 1. Initialize the population. Each chromosome k encodes C^k interval cluster centers which are chosen from the gray feature of image I. Set the generation number g = 1.

Step 2. Calculate the non-local spatial information of image pixels using Equations (6 and 7).

Step 3. Decode and compute the two fitness functions for each chromosome in the initial population using Equations (9 and 11): global interval valued fuzzy compactness function C_IN and interval valued fuzzy separation function S_I.

Step 4. Perform the non-dominated sorting on the population and give the rank to each chromosome in the population.

Step 5. Generate the mating pool using the crowded binary tournament selection.

Step 6. Perform the Laplace crossover and interval valued fuzzy Poisson mutation operator by Equations (13 and 14) on chromosomes in the mating pool to create the child population.

Step 7. Perform elitism on parent and child populations to generate the next generation population. Set g = g + 1.

Step 8. Judge the iterative termination conditions. If g ≥ G, decode each chromosome of the final non-dominated solution set and compute corresponding optimal solution interval valued fuzzy cluster validity index I (C) by Equation (15). Otherwise, go toStep 3.

Output: Solutions corresponding to the chromosome with the maximum I (C) value and the cluster number C encoded in it. Then the fuzzy membership can be calculated using Equation (5) and the classification of each pixel is determined by the principle of maximum degree of membership.

4. Experimental results and analysis

To evaluate the performance of the proposed algorithm, we compare MIFCA with seven existing algorithms, namely FCM, FCM_S1, IT2FCM, IFCM [30], IVFCM [10], MOVGA [28] and MSFCA [31], and apply these methods on synthetic images, real images and MR images in this section. Moreover, the clustering accuracy (CA) [36] is adopted to evaluate the performance of algorithms. In these methods, MOVGA, MSFCA and MIFCA can automatically evolve the number of clusters. The other algorithms are performed under different number of clusters ranging from 2 to C^*, where C^* is the maximum cluster number.

For all the algorithms, the fuzziness index m is set to 2. For FCM, FCM_S1, IT2FCM, IFCM and IVFCM, the maximum iteration number T of and the stopping threshold ɛ are set to 100 and 10^–5, respectively. According to the experimental analysis in [21], the search window size r × r, the patch size s × s and the filter degree parameter h for non-local spatial information are set to 21×21, 7×7, and 30 for MSFCA and MIFCA. For FCM_S1, MSFCA and MIFCA, the spatial constrained parameter β controlling the penalty effect of the spatial constraint term in the objective function is set to 6 [37]. For MOVGA, MSFCA and MIFCA, the number of generationG and the population size P are set to 100 and 50according to the experimental analysis in [23]. The crossover probability p_c and the mutation probability p_m are set to 0.9 and 0.1 for MOVGA, MSFCA and MIFCA.

4.1 Experiments on synthetic images

In this section, a synthetic image of size 256×256 is used to test the efficiency and robustness of all the comparative algorithms. Gaussian and Salt & Pepper (S&P) noise are added to this image, respectively. Figure 2 shows the segmentation results of all the algorithms on the Gaussian noisy image. FCM, IFCM, IT2FCM, IVFCM and MOVGA cannot overcome the sensitivity to noise due to not considering any spatial information. FCM_S1 improves the segmentation result to some extent due to the introduction of local spatial information. However, there are some wrongly classified pixels in the segmentation result. MSFCA and MIFCA can remove the most noise and obtain the better performance and obtain the same CA value. Figure 3 presents the segmentation results of all the algorithms on the S&P noisy image. It is clearly illustrated in Fig. 3(b-h) that FCM, FCM_S1, IFCM, IT2FCM, IVFCM, MOVGA and MSFCA are all influenced by the S&P noise, which indicates that these methods lack enough robustness to the noise. Figure 3(i) shows that the proposed MIFCA obtains better segmentation result than other algorithms.

Fig.2

Segmentation results on the synthetic image corrupted by the Gaussian noise (0, 0.01). (a) noisy image, (b) FCM (CA = 0.9565), (c) FCM_S1 (CA = 0.9985), (d) IFCM (CA = 0.9557), (e) IT2FCM (CA = 0.9536), (f) IVFCM (CA = 0.9553), (g) MOVGA (CA = 0.9549), (h) MSFCA (CA = 0.9999), (i) MIFCA (CA = 0.9999).

Fig.3

Segmentation results on the synthetic image corrupted by the S&P noise (0.1). (a) noisy image, (b) FCM (CA = 0.9324), (c) FCM_S1 (CA = 0.9871), (d) IFCM (CA = 0.9328), (e) IT2FCM (CA = 0.9324), (f) IVFCM (CA = 0.9321), (g) MOVGA (CA = 0.9339), (h) MSFCA (CA = 0.9619), (i) MIFCA (CA = 0.9999).

4.2 Experiments on real images

To prove the performance of the proposed algorithm, FCM, FCM_S1, IFCM, IT2FCM, IVFCM, MOVGA, MSFCA and MIFCA algorithms are evaluated on seven real images selected from the Berkeley Segmentation Dataset [38]. Table 1 gives the CA values of eight algorithms on these seven images corrupted by Gaussian and S&P noise with different levels, respectively. It is clearly illustrated that the proposed MIFCA obtains the higher segmentation accuracy than other algorithms and presents more robust to different noise.

Table 1
Comparison of these eight methods on Berkeley images corrupted by Gaussian noise and S&P noise

Image Noise level FCM FCM_S1 IFCM IT2FCM IVFCM MOVGA MSFCA MIFCA

#3096 Gaussian 0.01 0.6611 0.8014 0.7355 0.6602 0.6708 0.8555 0.9347 0.9579

S&P 0.2 0.9131 0.7553 0.8669 0.8630 0.8645 0.7475 0.4538 0.9598

#101027 Gaussian 0.005 0.8461 0.8838 0.8323 0.8441 0.8342 0.8556 0.4681 0.8980

S&P 0.1 0.8386 0.8788 0.8411 0.8401 0.8409 0.8406 0.4759 0.8959

#42049 Gaussian 0.01 0.9404 0.9588 0.9458 0.9400 0.9436 0.9447 0.9625 0.9646

S&P 0.1 0.9131 0.9550 0.9109 0.9150 0.9118 0.9120 0.9215 0.9648

#24063 Gaussian 0.005 0.7949 0.8014 0.8174 0.7908 0.8491 0.3601 0.9492 0.9601

S&P 0.05 0.9163 0.7553 0.9199 0.9177 0.9241 0.7970 0.9390 0.9514

#118035 Gaussian 0.004 0.7287 0.8601 0.7176 0.7331 0.7068 0.6607 0.8604 0.9153

S&P 0.05 0.8790 0.8788 0.8729 0.8156 0.8801 0.5084 0.8512 0.8885

#12003 Gaussian 0.005 0.6625 0.6656 0.6470 0.6635 0.6360 0.2449 0.3132 0.9243

S&P 0.1 0.6762 0.6669 0.6548 0.6754 0.6406 0.3055 0.2950 0.8972

#15088 Gaussian 0.025 0.8235 0.9244 0.8783 0.8172 0.8407 0.8181 0.9232 0.9327

S&P 0.1 0.8814 0.9218 0.8847 0.8807 0.8841 0.8839 0.9104 0.9332

Image	Noise level	FCM	FCM_S1	IFCM	IT2FCM	IVFCM	MOVGA	MSFCA	MIFCA
#3096	Gaussian	0.01	0.6611	0.8014	0.7355	0.6602	0.6708	0.8555	0.9347	0.9579
	S&P	0.2	0.9131	0.7553	0.8669	0.8630	0.8645	0.7475	0.4538	0.9598
#101027	Gaussian	0.005	0.8461	0.8838	0.8323	0.8441	0.8342	0.8556	0.4681	0.8980
	S&P	0.1	0.8386	0.8788	0.8411	0.8401	0.8409	0.8406	0.4759	0.8959
#42049	Gaussian	0.01	0.9404	0.9588	0.9458	0.9400	0.9436	0.9447	0.9625	0.9646
	S&P	0.1	0.9131	0.9550	0.9109	0.9150	0.9118	0.9120	0.9215	0.9648
#24063	Gaussian	0.005	0.7949	0.8014	0.8174	0.7908	0.8491	0.3601	0.9492	0.9601
	S&P	0.05	0.9163	0.7553	0.9199	0.9177	0.9241	0.7970	0.9390	0.9514
#118035	Gaussian	0.004	0.7287	0.8601	0.7176	0.7331	0.7068	0.6607	0.8604	0.9153
	S&P	0.05	0.8790	0.8788	0.8729	0.8156	0.8801	0.5084	0.8512	0.8885
#12003	Gaussian	0.005	0.6625	0.6656	0.6470	0.6635	0.6360	0.2449	0.3132	0.9243
	S&P	0.1	0.6762	0.6669	0.6548	0.6754	0.6406	0.3055	0.2950	0.8972
#15088	Gaussian	0.025	0.8235	0.9244	0.8783	0.8172	0.8407	0.8181	0.9232	0.9327
	S&P	0.1	0.8814	0.9218	0.8847	0.8807	0.8841	0.8839	0.9104	0.9332

In order to visually compare the performance, the segmentation results of all methods on images #3096 and #101027 are presented in this section. The original images and their benchmarks are shown in Fig. 4. The segmentation results of these two images are shown in Figs. 5 –8. It can be seen from the results that FCM, FCM_S1, IFCM, IT2FCM, IVFCM and MOVGA lack enough robustness to the noise in images. Although MSFCA can obtain the betterperformance, its segmentation results still contain noise. It is clear that MIFCA provides excellent segmentation results for these images.

Fig.4

Original images and their benchmarks. (a) original image of #3096, (b) original image of #101027, (c) benchmark image of #3096, (d) benchmark image of #101027.

Fig.5

Segmentation results on the image #3096 corrupted by the Gaussian noise (0, 0.01). (a) noisy image, (b) FCM, (c) FCM_S1, (d) IFCM, (e) IT2FCM, (f) IVFCM, (g) MOVGA, (h) MSFCA, (i) MIFCA.

Fig.6

Segmentation results on the image #3096 corrupted by the S&P noise (0.1). (a) noisy image, (b) FCM, (c) FCM_S1, (d) IFCM, (e) IT2FCM, (f) IVFCM, (g) MOVGA, (h) MSFCA, (i) MIFCA.

Fig.7

Segmentation results on the image #101027 corrupted by the Gaussian noise (0, 0.025). (a) noisy image, (b) FCM, (c) FCM_S1, (d) IFCM, (e) IT2FCM, (f) IVFCM, (g) MOVGA, (h) MSFCA, (i) MIFCA.

Fig.8

Segmentation results on the image #101027 corrupted by the S&P noise (0.1). (a) noisy image, (b) FCM, (c) FCM_S1, (d) IFCM, (e) IT2FCM, (f) IVFCM, (g) MOVGA, (h) MSFCA, (i) MIFCA.

4.3 Experiments on MR images

Image segmentation plays a key role in medical image processing and analysis. To demonstrate the superiority of MIFCA, twenty brain MR images are selected from the Internet Brain Segmentation Repository (IBSR) [39] and their corresponding CA results of all methods are presented in Table 2. Except for the slice 20 of 7-8 and the slice 19 of 11-3, MIFCA obtains the highest CA values among all comparison methods. Moreover, the segmentation results of two brain images of different people (1–24 and 6–10) are selected to show the visual segmentation performance and shown in Figs. 9 and 10. Due to the number of clusters given in advance, the results of FCM, FCM_S1, IT2FCM, IFCM and IVFCM can be accepted. MOVGA obtains the incorrect number of clusters on slice 40 of 1–24. Moreover, MSFCA classifies the white matter region and gray matter region into one class on slice 12 of 6–10. For all the images, the proposed MIFCA can evolve the correct cluster number and obtain the best performance in the edge details of images.

Fig.9

Segmentation results on the slice 40 of 1–24. (a) original image, (b) benchmark image, (c) FCM, (d) FCM_S1, (e) IFCM, (f) IT2FCM, (g) IVFCM, (h) MOVGA, (i) MSFCA, (j) MIFCA.

Fig.10

Segmentation results on the slice 12 of 6–10. (a) original image, (b) benchmark image, (c) FCM, (d) FCM_S1, (e) IFCM, (f) IT2FCM, (g) IVFCM, (h) MOVGA, (i) MSFCA, (j) MIFCA.

Table 2

Comparison of these eight methods on brain images

Image	Slice	FCM	FCM_S1	IT2FCM	IFCM	IVFCM	MOVGA	MSFCA	MIFCA
1–24	6	0.9748	0.9844	0.9859	0.9747	0.9832	0.9774	0.9699	0.9889
	40	0.9718	0.9908	0.9894	0.9910	0.9900	0.9684	0.9927	0.9932
2–4	6	0.9841	0.9826	0.9841	0.9835	0.9809	0.9788	0.9791	0.9843
	41	0.9846	0.9833	0.9847	0.9849	0.9844	0.9591	0.9590	0.9857
4–8	6	0.9890	0.9859	0.9890	0.9885	0.9867	0.9809	0.9834	0.9918
	41	0.9853	0.9880	0.9898	0.9894	0.9888	0.9584	0.9653	0.9906
6–10	12	0.9833	0.9804	0.9819	0.9820	0.9772	0.9786	0.9570	0.9914
	42	0.9745	0.9689	0.9723	0.9815	0.9815	0.9656	0.9659	0.9869
7-8	20	0.9782	0.9752	0.9776	0.9772	0.9736	0.9766	0.9330	0.9702
	43	0.9734	0.9826	0.9734	0.9833	0.9930	0.9714	0.9222	0.9947
11-3	10	0.9732	0.9719	0.9732	0.9723	0.9677	0.9807	0.9527	0.9848
	19	0.9671	0.9630	0.9655	0.9641	0.9604	0.9720	0.9702	0.9687
13-3	11	0.9798	0.9769	0.9782	0.9785	0.9676	0.8961	0.9510	0.9839
	43	0.9915	0.9905	0.9915	0.9912	0.9908	0.9497	0.9914	0.9920
15-3	12	0.9720	0.9705	0.9720	0.9720	0.9720	0.9573	0.9583	0.9741
	41	0.9868	0.9860	0.9868	0.9871	0.9861	0.9631	0.9625	0.9871
17-3	9	0.9823	0.9808	0.9823	0.9812	0.9779	0.9899	0.9424	0.9895
	24	0.9738	0.9714	0.9738	0.9735	0.9718	0.9742	0.9385	0.9739
111-2	15	0.9817	0.9769	0.9810	0.9813	0.9768	0.9831	0.9782	0.9861
	23	0.9705	0.9680	0.9701	0.9705	0.9699	0.9105	0.9684	0.9713

5 Conclusion and remarks

In this article, we have proposed a multi-objective interval valued fuzzy clustering algorithm (MIFCA) to solve problems of fuzzy clustering. In order to increase the resistance to noise, MIFCA introduces the non-local spatial information derived from the image into the interval valued fuzzy fitness functions to be optimized. Moreover, interval valued fuzzy information is introduced into the new mutation operator to increase the efficiency of mutation. In order to select a solution from the non-dominated solution set, an effective interval valued fuzzy cluster validity index is constructed by utilize the non-local spatial information and the interval fuzzy information.

The construction of interval valued fuzzy sets for the image is the key procedure in the proposed method. How to construct the more robust interval valued fuzzy sets is a meaningful research. Moreover, we will discuss the construction of fitness functions incorporating the spatial information in our future work.

Footnotes

Acknowledgments

This work is supported by the National Natural Science Foundation of China (Grant Nos. 61571361, 61671377, 61202153, and 61102095), New Star Team of Xi’an University of Posts & Telecommunications (xyt2016-01), the Fundamental Research Funds for the Central Universities (Grant No. GK201903092).

References

Gonzalez

R.C.

, Woods

R.E.

, Digital Image Processing, Addison-Wesely, Massachusetts, 1992.

Rahpeyma

, Zarei

, An integrated QFD-TOPSIS approach for supplier selection under fuzzy environment: A case of detergent manufacturing industry, International Journal of Service Science, Management, Engineering, and Technology (IJSSMET) 9(3) (2018), 62–81.

Dai

, Zheng

, Han

, et al., Probability approach for interval-valued ordered decision systems in dominance-based fuzzy rough set theory, Journal of Intelligent & Fuzzy Systems 32(1) (2017), 703–710.

Zheng

, et al., Image segmentation by generalized hierarchical fuzzy C-means algorithm, Journal of Intelligent & Fuzzy Systems 28(2) (2015), 961–973.

Sowmya

, Sheela Rani

, Colour image segmentation using fuzzy clustering techniques and competitive neural network, Applied Soft Computing 11 (2011), 3170–3178.

Dunn

J.C.

, A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters, 1 (1973), 32–57.

Pal

N.R.

, Pal

S.K.

, A review on image segmentation techniques, Pattern Recognition 26(9) (1993), 1277–1294.

Bezdek

J.C.

, Ehrlich

, Full

, FCM: The fuzzy c-means clustering algorithm, Computers & Geosciences 10(2-3) (1984), 191–203.

Hwang

, Rhee

F.C.H.

, Uncertain fuzzy clustering: Interval type-2 fuzzy approach to C-means, IEEE Transactions on Fuzzy Systems 15(1) (2007), 107–120.

10.

F.A.T.

, Carvalho, Fuzzy c-means clustering methods for symbolic interval data, Pattern Recognit Letters 28(4) (2007), 423–437.

11.

D’Urso

, De Giovanni

, Massari

, et al., Exponential distance-based fuzzy clustering for interval-valued data, Fuzzy Optim Decision Making 16 (2017), 51–70.

12.

Wang

, Zhang

, Li

, Zhang

, The global fuzzy C-means clustering algorithm, Proceedings of the 6th World Congress on Intelligent Control and Automation 1, 2006, pp. 3604–3607.

13.

Bhandarkar

S.M.

, Zhang

, Image segmentation using evolutionary computation, IEEE Transactions on Evolutionary Computation 3(1) (1999), 1–21.

14.

Peter

J.M.

, Laarhoven

, Aart

E.H.L.

, Simulated Annealing: Theory and applications, Springer, Dordrecht, 1987, pp. 7–15.

15.

Chaharsooghi

S.K.

, Kermani

A.H.M.

, An effective ant colony optimization algorithm (ACO) for multi-objective resource allocation problem (MORAP), Applied Mathematics and Computation 200(1) (2008), 167–177.

16.

, Liu

, Xu

, A novel fuzzy clustering based on particle swarm optimization, pp, IEEE International Symposium on Information Technologies and Applications in Education (2007), 88–90.

17.

, Liu

, Xu

, A novel fuzzy clustering based on particle swarm optimization, pp, Information Technologies and Applications in Education (2007), 88–90.

18.

Ahmed

M.N.

, Yamany

S.M.

, Mohamed

, Faragand

A.A.

, Moriarty

, A modified fuzzy c-means algorithm for bias field estimation and segmentation of MRI data, IEEE Transactions on Medical Imaging 21(3) (2002), 193–199.

19.

Chen

, Zhang

D.Q.

, Robust image segmentation using FCM with spatial constraints based on new kernel-induced distance measure, IEEE Transactions on Systems, Man, and Cybernetics-Part B 34(4) (2004), 1907–1916.

20.

, Xia

, Chen

, Sun

, Fuzzy c-means clus-tering with weighted image patch for image segmentation, Applied Soft Computing 12(6) (2016), 1659–1667.

21.

Zhao

, Jiao

L.C.

, Liu

H.Q.

, Fuzzy c-means clustering with non-local spatial information for noisy image segmentation, Frontiers of Computer Science in China 5 (2011), 45–56.

22.

Qiu

, Xiao

, Yu

, Han

, Iqbal

M.N.

, A modified interval type-2 fuzzy C-means algorithm with application in MR image segmentation, Pattern Recognition Letters 34(12) (2013), 1329–1338.

23.

Bandyopadhyay

, Maulik

, Mukhopadhyay

, Multiobjective genetic clustering for pixel classification in remote sensing imagery, IEEE Transactions on Geoscience and Remote Sensing 45(5) (2007), 1506–1511.

24.

Bezdek

J.C.

, Pattern Recognition with Fuzzy Objective Function Algorithms,Plenum Press, New York, 1981.

25.

Xie

X.L.

, Beni

, A validity measure for fuzzy clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence 13 (1991), 841–847.

26.

Mukhopadhyay , Maulik

and Bandyopadhyay

, Multi-objective genetic clustering with ensemble among Pareto front solutions: Application to MRI brain image segmentation, in: Proceedings of the International Conference on Advances in Pattern Recognition, 2009, pp. 236–239.

27.

Pakhira

, Bandyopadhyay

, Maulik

, Validity index for crisp and fuzzy clusters, Pattern Recognition 37 (2004), 487–501.

28.

Mukhopadhyay and Maulik

, A multiobjective approach to MR brain image segmentation, Applied Soft Computing 11(1) (2011), 872–880.

29.

Maulik

, Bandyopadhyay

, Performance evaluation of some clustering algorithms and validity indices, IEEE Transactions on Pattern Analysis and Machine Intelligence 24(12) (2002), 1650–1654.

30.

Chaira

, A novel intuitionistic fuzzy C means clustering algorithm and its application to medical images, Applied Soft Computing 11 (2011), 1711–1717.

31.

Zhao

, Liu

, Fan

, A multiobjective spatial fuzzy clustering algorithm for image segmentation, Applied Soft Computing 30 (2015), 48–57.

32.

Wang

, Shen

, Shi

, Xu

, Zhang

, Iterative non-local means filter for salt and pepper noise removal, in Journal of Visual Communication and Image Representation, Elsevier 38 (2016), 440–450.

33.

Schoenauer

, A fast elitist nondominated sorting genetic algorithm for multi-objective optimization: NSGA- II, in Parallel Problem Solving from Nature (PPSN VI), Germany, Berlin: Springer, 2000, pp. 849–858 .

34.

, A new hybrid evolution genetic algorithm with Laplace crossover and power mutation, Computational Intelligence and Security 2 (2009), 88–91.

35.

Hoorfar

, Zhu

, Nelatury, Electromagnetic optimization using a mixed-parameter selt-adaptive evolutionary algorithm, Microwave and Optical Technology Letters 39(4) (2003), 267–271.

36.

, Scholkopt

, A local learning approach for clustering, in: Advances in Neural Information Processing Systems, 2007, pp. 1529–1536.

37.

Zhao

, Jiao

L.C.

, Liu

H.Q.

, Kernel generalized fuzzy c-means clustering with spatial information for image segmentation, Digital Signal Process 23(1) (2013), 184–199.

38.

Martin

, Fowlkes

, Tal

, Malik

, A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics, Proceedings Eighth IEEE International Conference 2 (2001), 416–423.

39.

Worth

, The Internet Brain Segmentation Repository (IBSR), 2009. [Online]. Available: http://www.nitrc.org/projects/ibsr.