Spectral-Spatial Clustering with a Local Weight Parameter Determination Method for Remote Sensing Imagery

Abstract

Remote sensing image clustering is a challenging task considering its intrinsic complexity. Recently, by combining the spectral and spatial information of the remote sensing data, the clustering performance can be dramatically enhanced, termed as Spectral-Spatial Clustering (SSC). However, it has always been difficult to determine the weight parameter for balancing the spectral term and spatial term of the clustering objective function. In this paper, spectral-spatial clustering with a local weight parameter determination method for remote sensing image was proposed, i.e., L-SSC. In L-SSC, considering the large scale of remote sensing images, the weight parameter can be determined locally in a patch image instead of the whole image. Afterwards, the local weight parameter was used in constructing the objective function of L-SSC. Thus, the remote sensing image clustering problem was transformed into an optimization problem. Finally, in order to achieve a better optimization performance, a variant of differential evolution (i.e., jDE) was used as the optimizer due to its powerful optimization capability. Experimental results on three remote sensing images, including a Wuhan TM image, a Fancun Quickbird image, and an Indian Pine AVIRIS image, demonstrated that the proposed L-SSC can acquire higher clustering accuracy in comparison to other spectral-spatial clustering methods.

1. Introduction

Clustering is one of the most important techniques in remote sensing image processing. The aim of remote sensing clustering is to partition a given image into groups such that pixels in the same group are as similar to each other as possible while those assigned to different groups are dissimilar [1,2]. With the development of satellite sensors, the spatial resolution of remote sensing images increases, resulting in the fact that pixels of the same land use/cover class may not have a similar spectral property [3,4]. Thus, isolated pixels, namely “salt and pepper” effects, may emerge in remote sensing image clustering results. Furthermore, due to the existence of noise and outliers, these effects are aggravated.

Fortunately, the spatial information embedded in a remote sensing image can take the homogeneity of neighbor pixels into consideration [5], which has been used in remote sensing image processing, such as classification [6], semi-supervised classification [7], segmentation [8], and hyperspectral unmixing [9]. Especially, coupled with spectral information, the spatial information can also be utilized in remote sensing image clustering, termed as Spectral-Spatial Clustering (i.e., SSC). Firstly, the spatial features (i.e., GLCM, Morphological Profile) can be extracted and stacked with the spectral feature [10]. An accurate spatial feature extraction method can be effective in SSC. However, the selection of the appropriate spatial feature is not an easy task because of different class distributions with regard to different regions. Secondly, object-based techniques can be used for introducing the spatial information in SSC, which can be implemented by combining the traditional pixel-wise unsupervised classification method with segmentation [11].

Both the spatial feature stacking technique and the object-based technique can be thought of as pre- and post-processing techniques, which can be easily combined with other spectral-spatial clustering methods. Among these methods, the FCM-based spectral-spatial clustering method is our focus because of its easy implementation and cheaper computational complexity compared with others such as spectral clustering [12,13]. In the literature, Ahmed et al. proposed FCM_S [14] aiming at incorporating spatial constraints by modifying objective function of FCM [15]. However, FCM_S is time-consuming because of the computation of spatial neighborhood term in each iteration step. Chen and Zhang [16] reduced the computational complexity of FCM_S by introducing the mean-filtered image, termed as FCM_S1. One common drawback of the above methods is that they both need a weight parameter to control the trade-off between being robust to outliers and the effectiveness of preserving the derails. The weight parameter is often selected empirically, which is time-consuming and unreasonable. Hence, KADESFC was proposed for remote sensing image clustering, in which the weight parameter was determined adaptively by introducing the concept of entropy [17]. However, the weight parameter in KADESFC is not accurate because of the fact that it is determined based on the whole image and it cannot take the local spatial information of each pixel into consideration to calculate the weight parameter. Meanwhile, the above methods for remote sensing clustering were transformed into the optimization of clustering objective functions. However, the optimization methods of these objective functions mainly, in essence, belong to mountain-climbing algorithms [18]. Hence, it is easy for them to get stuck in local optima, especially considering the complexity the remote sensing image processing.

In order to resolve the above problems and enhance the generalization capability in remote sensing image clustering, spectral-spatial clustering with a local weight parameter determination method for remote sensing image (termed as L-SSC) is proposed, the contributions of which are listed below:

(1)

FCIDE-based local weight parameter calculation method. In order to achieve a balance between the spectral term and the spatial term of objective functions for SSC, a local weight parameter calculation method is proposed. This new weight parameter determination method is based on the motivation that patch images instead of the whole image, can be used as the local spatial information in determining the weight parameter. The utilization of local spatial information can preserve more detail, which alleviates over-smoothing resulting from the aggressive weight parameter brought by the large scale of the remote sensing image. Thus, this weight parameter determination method is more in line with the real situation. Due to the fact that the cluster number of each patch image is unknown, in this paper, an automatic clustering method named FCIDE [19] was used, which can determine the number of clusters and acquire the clustering result simultaneously. Then, the local weight parameter was determined based on the clustering result of each patch image.

(2)

jDE-based optimization method. The FCIDE-based local weight parameter was used to achieve a trade-off between the spectral term and spatial term, and construct the clustering objective function, termed as Jm_E. In order to acquire more satisfying clustering results, a kernelized version of Jm_E was also constructed as the clustering objective function, termed as Jm_K. Thus, the task of remote sensing image clustering was transformed into an optimization problem. A differential evolution algorithm (DE) [20], as one of the recently growing areas of research in evolution algorithm, is used to optimize two above constructed objective functions. DE has been proved to have a powerful global search capability in many applications [21,22] including remote sensing image processing, such as clustering [17,23,24,25], sub-pixel mapping [26], feature selection [27], and endmember extraction [28]. In the mechanism of classical DE, two parameters F and CR need to be tuned manually [29]. In order to simplify the whole process (e.g., parameter selection) in this work, a variant of DE, namely jDE [30], is used, which can determine both parameters adaptively.

Experiments were conducted on three remote sensing datasets (i.e., a WuhanTM image, a Fancun QuickBird image, and an Indian Pine AVIRIS image) to demonstrate the effectiveness of the local weight parameter and the superiority of the proposed clustering methods (L-SSC_E, and L-SSC_K) over other novel methods, such as K-means, FCM, GMM, FCM_S1, KWFLICM [31], and KADESFC [17].

The rest of this paper is organized as follows: Section 2 describes two strategies (manual and adaptive ones) that determine the weight parameter between the spectral term and spatial term. Section 3 describes the proposed spectral-spatial clustering with a local weight parameter determination method for a remote sensing image. Section 4 presents experimental clustering results. Section 5 makes an analysis about the local weight parameters visually and quantitatively. Section 6 gives our conclusions.

2. Background

Before describing the proposed method, the notations used throughout this paper are defined (Figure 1).

Figure 1. The defined notations.

Figure 1. The defined notations.

During the task of remote sensing image classification, the pixels nearby tend to be labelled with the same class. The homogeneity of neighbor pixels can be used to enhance the clustering performance by combining the spectral term and the spatial term in the objective functions for remote sensing image clustering. However, it is still a problem to control the trade-off between the spectral term and spatial term, which can be determined by a weight parameter. Recently, researchers working in the determination of the weight parameter have started taking some interest on two approaches, namely the manual determination [14,16] and the adaptive determination [17].

2.1. The Manual Determination of the Weight Parameter

FCM_S is introduced [14] as a modification of the standard FCM by introducing a term that allows the labelling of a pixel to be influenced by labels in its neighborhood. The neighborhood acts as a regularizer and biases the solution towards piecewise-homogeneous labelling. The objective function of FCM_S is defined as Equation (1):

$$Jm\_S={\displaystyle \sum _{i=1}^C{\displaystyle \sum _{k=1}^N{u}_{ik}^m||x_k-v_i|{|}^2}}+\frac{\alpha }{N_R}{\displaystyle \sum _{i=1}^C{\displaystyle \sum _{k=1}^N{u}_{ik}^m{\displaystyle \sum _{\mathrm{r}\in N_k}\left|\right|x_r-v_i|{|}^2}}}$$

(1)

$$U\in \{u_{ik}\in [0,1]|{\displaystyle \sum _{i=1}^C{u}_{ik}=1and}0<{\displaystyle \sum _{k=1}^N{u}_{ik}}<N\}$$

(2)

$$u_{ik}=\frac{{(||x_k-v_i|{|}^2+\frac{\alpha }{N_R}{\displaystyle \sum _{\mathrm{r}\in N_k}||x_r-v_i|{|}^2})}^{\raisebox{1ex}{$-1$}\!\left/ \!\raisebox{-1ex}{$(m-1)$}\right.}}{{\displaystyle \sum _{j=1}^C{(||x_k-v_j|{|}^2+\frac{\alpha }{N_R}{\displaystyle \sum _{\mathrm{r}\in N_k}\left|\right|x_r-v_j|{|}^2})}^{\raisebox{1ex}{$-1$}\!\left/ \!\raisebox{-1ex}{$(m-1)$}\right.}}}$$

(3)

$$v_i=\frac{{\displaystyle \sum _{k=1}^N{u}_{ik}^m(x_k+\frac{\alpha }{N_R}{\displaystyle \sum _{\mathrm{r}\in N_k}{x}_r})}}{(1+\alpha ){\displaystyle \sum _{k=1}^N{u}_{ik}^m}}$$

(4)

where x_r represents the neighbor of x_k, N_k stands for the set of neighbor pixels falling into a window around pixel x_k, and N_R is its cardinality. The weight parameter α is used to control the balance between the data term and the smoothing term. Jm_S can be minimized by calculating Equations (3) and (4) iteratively. The array U = [u_ik] in Equation (2) is a fuzzy membership matrix.

For FCM_S, the minimization of Equation (1) is time-consuming due to the fact that the neighbor term $\sum _{r\in N_k}||{\mathrm{x}}_r-{\mathrm{v}}_i|{|}^2$ needs to be calculated in each iteration step. In order to resolve the above problem, FCM_S1 [16] is proposed as a variant of FCM_S. The objective function of FCM_S1 is written in Equation (5):

$$Jm\_S1={\displaystyle \sum _{i=1}^C{\displaystyle \sum _{k=1}^N{u}_{ik}^m||x_k-v_i|{|}^2}}+\alpha {\displaystyle \sum _{i=1}^C{\displaystyle \sum _{k=1}^N{u}_{ik}^m||\overline{x_k}-v_i|{|}^2}}$$

(5)

$$u_{ik}=\frac{{(||x_k-v_i|{|}^2+\left|\right|\overline{x_k}-v_i|{|}^2)}^{\raisebox{1ex}{$-1$}\!\left/ \!\raisebox{-1ex}{$(m-1)$}\right.}}{{\displaystyle \sum _{j=1}^C{(||x_k-v_j|{|}^2+\left|\right|\overline{x_k}-v_j|{|}^2)}^{\raisebox{1ex}{$-1$}\!\left/ \!\raisebox{-1ex}{$(m-1)$}\right.}}}$$

(6)

$$v_i=\frac{{\displaystyle \sum _{k=1}^N{u}_{ik}^m(x_k+\overline{x_k})}}{(1+\alpha ){\displaystyle \sum _{k=1}^N{u}_{ik}^m}}$$

(7)

where $\overline{{\mathrm{x}}_k}$ is a means of neighboring pixels lying within a window around x_k. Jm_S1 can be minimized by calculating Equations (6) and (7) iteratively. Unlike FCM_S, $\overline{{\mathrm{x}}_k}$ can be calculated in advance, reducing the whole calculation time.

The appropriate weight parameter α in Jm_S and Jm_S1 can achieve a balance between the spectral term and spatial term, making a trade-off between being robust to outliers and the effectiveness of preserving the derails. Thus, two above methods (FCM_S, FCM_S1) performs well on most remote sensing images. However, the weight parameter α is often selected manually, which is time-consuming. Hence, adaptive determination of the weight parameter is much more preferred.

2.2. The Adaptive Determination of Weight Parameter

In KADESFC [17], the weight parameter α_k of each pixel can be calculated adaptively based on its corresponding entropy (see Equation (8)). The weight parameter α_k of each pixel can be calculated in the following process (Figure 2)

$$Jm\_aS1={\displaystyle \sum _{i=1}^C{\displaystyle \sum _{k=1}^N{u}_{ik}^m(1-{\alpha }_k)[1-K({\mathit{x}}_{\mathit{k}},{\mathit{v}}_{\mathit{i}})]}}+{\displaystyle \sum _{i=1}^C{\displaystyle \sum _{k=1}^N{u}_{ik}^m{\alpha }_k[1-K(\overline{{\mathit{x}}_{\mathit{k}}},{\mathit{v}}_{\mathit{i}})]}}$$

(8)

Figure 2. The flowchart of adaptive weight parameter determination in KADESFC.

Figure 2. The flowchart of adaptive weight parameter determination in KADESFC.

(1)

The calculation of the membership matrix based on FCM. Fuzzy C means clustering (FCM) is firstly used to cluster the whole remote sensing image. Then, the membership matrix U = [u_ik] can then be acquired, in which the membership u_ik represents the membership of the k-th pixel with respect to i-th cluster center.

(2)

The calculation of the entropy for each pixel. The entropy of each pixel is calculated using the following Equation (9):

$$E_{\mathrm{k}}=-{\displaystyle \sum _{i=1}^C{u}_{ik}{\log }_2}{u}_{ik}$$

(9)

where E_k is the entropy of the k-th pixel. The physical meaning of entropy can be explained by uncertainty of the k-th pixel. As can be seen from Equation (9), the larger the entropy of the pixel, the more uncertain the pixel is. In most cases, these uncertain pixels can be thought of as isolated pixels (e.g., noise or outliers) due to the fact that their belonging to each cluster center is comparable. Hence, the weight parameter α_k with a large value should be put onto these pixels, meaning that more spatial information should be taken into consideration to determine its label.

(3)

The calculation of the weight parameter α_k. Since the range of the entropy is not equal to the range of α_k (i.e., 0–1), E_k needs to be mapped linearly to 0–1 as Equation (10):

$${\alpha }_k=\frac{E_k-E_{\text{min}}}{E_{\text{max}}-E_{\text{min}}}$$

(10)

where E_max and E_min are the maximum and minimum entropy of all the pixels, respectively, and α_k is set as the weight parameter of the k-th pixel.

Based on the above methods to determine weight parameter in the traditional spectral-spatial clustering methods, several problems need to be resolved.

(1)

By directly applying FCM on the whole remote sensing image, the adaptive determination method in KADESFC does not take the local information of each pixel into consideration. It does not consider the situation that there are different distributions of objects in different regions of the remote sensing images with large scale. Thus, the membership matrix based on FCM may be unsatisfying when the remote sensing image with large scale is to be processed. Then, the inaccurate membership u_ik cannot be used to accurately estimate the entropy E_k and the weight parameter α_k. Figure 3 shows the weight parameter image α_k of two remote sensing images with a size of 400 × 400, which are acquired using the above adaptive determination method in KADESFC. It should be noted that the darker the pixel is, the smaller the weight parameter is, and vice versa. As can be seen from Figure 3c,d, some detailed pixels (building and roads labelled with circles and lines) are assigned with large value of the weight parameter, resulting in the fact that these detailed pixels may be smoothed in the final clustering results.

(2)

The objective functions of FCM_S and FCM_S1, namely Jm_S and Jm_S1, are both minimized by calculating the membership and cluster center iteratively, whose performance are often affected by the initial values. That is, their performance is limited by optimization of the clustering objective function.

Figure 3. The weight parameter images of adaptive determination method (KADESFC) (circles and lines representing building and roads). (a) Wuhan TM image; (b) Fancun image; (c) the weight parameter image of Wuhan TM image; and (d) the weight parameter image of Fancun image.

Figure 3. The weight parameter images of adaptive determination method (KADESFC) (circles and lines representing building and roads). (a) Wuhan TM image; (b) Fancun image; (c) the weight parameter image of Wuhan TM image; and (d) the weight parameter image of Fancun image.

3. The Proposed Method

In this paper, spectral-spatial clustering with a local weight parameter determination method for remote sensing image (i.e., L-SSC) was proposed. The flowchart of L-SSC is as Figure 4, which includes two processes: FCIDE-based local weight parameter determination, and the jDE-based optimization method.

Figure 4. Flowchart of the proposed method L-SSC.

Figure 4. Flowchart of the proposed method L-SSC.

3.1. FCIDE-Based Local Weight Parameter Determination Method

The local information, i.e., there are different distributions of objects in different regions, motivates us to determine the weight parameter based on patch image instead of the whole remote sensing image. Thus, the workflow of the proposed FCIDE-based local weight parameter determination method is listed as Figure 5 and will be described in detail below.

Figure 5. The flowchart of FCIDE-based local weight parameter determination method. (a) Whole image; (b) Patch image; (c) Parch weight; and (d) Whole weight.

Figure 5. The flowchart of FCIDE-based local weight parameter determination method. (a) Whole image; (b) Patch image; (c) Parch weight; and (d) Whole weight.

Step 1. The original image (see Figure 5a) with a large scale is divided into patch and patch image with small scale (see Figure 5b).

Step 2. Due to the fact that the cluster number of each patch image is unknown, the automatic clustering strategy in FCIDE [19] is used to cluster each patch of the remote sensing image and calculate the membership u_ik, which can be briefly described below.

(1)

Initialization of the population.

For a remote sensing image with C clusters and D spectral bands, the individual encoding strategy of FCIDE is as Figure 6, in which Cp cluster centers a are encoded (Cp > C) and D bands are encoded for each cluster center. At the same time, each individual have Cp masker corresponding to the Cp cluster centers. If the masker number is 1, the corresponding cluster center is selected to calculate the objective function, namely XB index Equation (11). If the masker number is 0, the corresponding cluster center is not selected to calculate the objective function. The task of FCIDE is to evolve C cluster centers, which possess the minimum value of XB.

Figure 6. The encoding strategy in automatic clustering.

Figure 6. The encoding strategy in automatic clustering.

(2)

Calculation of the fitness of each individual using the objective function Equation (11):

$$\mathrm{X}B=\frac{J_m/N}{Sep(v)}=\frac{{\displaystyle \sum _{i=1}^C{\displaystyle \sum _{k=1}^N{u}_{ik}^m{\Vert x_k-v_i\Vert }^2}}}{N{\text{min}}_{i\ne j}{\Vert v_i-v_j\Vert }^2}$$

(11)

In the FCIDE-based patch weight parameter calculation method, the clustering validity index XB [32] (see Equation (11)) was selected as the fitness function for the automatic clustering method FCIDE. It has been proved that the minimum of XB cannot only indicate the appropriate partition of remote sensing data, but also indicate the correct number of clusters.

(3)

Mutation and crossover. In DE, the mutation operator amounts to creating a donor vector V_i(t)=[v_i,1(t), v_i,2(t),…, v_i,C×D(t)]^T for changing each individual of the population. The mutation process can be expressed as Equation (12):

$${\mathit{V}}_{\mathit{i}}(t)={\mathit{X}}_{r_1^i}(t)+F({\mathit{X}}_{r_2^i}(t)-{\mathit{X}}_{r_3^i}(t))$$

(12)

where ${\mathit{X}}_{r1}^i$, ${\mathit{X}}_{r2}^i$, ${\mathit{X}}_{r3}^i$ are picked up randomly from the population.

After the mutation operator, crossover is operated between the donor vector V_i(t) and the target vector X_i(t), generating a trial vector U_i(t) = [u_i,1(t), u_i,2(t),…, u_i,C×D(t)]^T. The crossover operator can be implemented as Equation (13):

$$u_{i,j}(t)=\{\begin{array}{l}{v}_{i,j}(t),if(ran{d}_{i,j}(0,1)\le CRorj=j_{rand})\\ x_{i,j}(t),otherwise\end{array}$$

(13)

There are two main parameters including F and CR in DE. In FCIDE, this scale factor F is varied in a random manner in the range (0.5–1) by using Equation (14). In addition, the crossover rate CR was linearly decreased with time from maximum to minimum of CR, which can be formulated as Equation (15):

$$F=0.5(1+\text{rand}(0,1))$$

(14)

$$CR=C{R}_{\text{max}}-(C{R}_{\text{max}}-C{R}_{\text{min}})\times \frac{iter}{MAXITER}$$

(15)

where CR_max and CR_min are the maximum and minimum values of the crossover rate CR, iter is the current iteration number, and MAXITER is the maximum number of allowable iterations.

(4)

Recalculation of the fitness of offspring U_i(t) using the objective function Equation (11).

(5)

Selection. The selection operator is to decide who is the winner between the target vector X_i(t) and the trial vector U_i(t). The vector with better fitness can be selected to the next generation. The target vector of next generation can be generated by selection operator as Equation (16):

$${\mathit{X}}_i(t+1)=\{\begin{array}{l}{\mathit{U}}_i(t),iff({\mathit{U}}_i(t))\le f({\mathit{X}}_i(t))\\ {\mathit{X}}_i(t),otherwise\end{array}$$

(16)

(6)

Elite strategy. In order to speed the coverage of iteration and enhance the efficiency of optimization, elite strategy is applied, which preserves the individual with the best fitness found so far.

(7)

Terminal condition. Repeat Step (3) to Step (6) until the terminal condition is met. The terminal condition is to reach the max number of iterations.

Step 3. After applying FCIDE to each patch (Figure 5b) of remote sensing image, the membership matrix U = [u_ik] can be acquired based on the cluster centers encoded in the individuals. Afterwards, the patch weight parameter (Figure 5c) can be calculated using Equations (9) and (10). Then the weight parameters of the whole image (Figure 5d) can also be obtained by combining these patch weight images.

3.2. jDE-Based Clustering Method (Optimization of the Proposed Kernelized Objective Function)

Based on the above local weight parameter α_k, the first objective function Jm_E can be formulated as Equation (17), in which the Euclidian distance is used as the similarity metrics:

$$Jm\_E={\displaystyle \sum _{i=1}^C{\displaystyle \sum _{k=1}^N{u}_{ik}^m(1-{\alpha }_k)||{\mathit{x}}_{\mathit{k}}-{\mathit{v}}_{\mathit{i}}||}}+{\displaystyle \sum _{i=1}^C{\displaystyle \sum _{k=1}^N{u}_{ik}^m{\alpha }_k||\overline{{\mathit{x}}_{\mathit{k}}}-{\mathit{v}}_{\mathit{i}}||}}$$

(17)

where the weight parameter α_k is used to control the effect of the neighbor term of k-th pixel, which has been calculated by the FCIDE-based local weight parameter determination method described in Section 3.1.

Considering the complex distribution of remote sensing data, the second objective function Jm_K, a kernelized version of Jm_E, was also constructed as Equation (18), in which the kernel distance was used as the similarity metric:

$$Jm\_K={\displaystyle \sum _{i=1}^C{\displaystyle \sum _{k=1}^N{u}_{ik}^m(1-{\alpha }_k)[1-K({\mathit{x}}_{\mathit{k}},{\mathit{v}}_{\mathit{i}})]}}+{\displaystyle \sum _{i=1}^C{\displaystyle \sum _{k=1}^N{u}_{ik}^m{\alpha }_k[1-K(\overline{{\mathit{x}}_{\mathit{k}}},{\mathit{v}}_{\mathit{i}})]}}$$

(18)

where K(x_k, v_i) is the kernel metric distance between x_k and v_i based on Radial Basis Function (RBF) kernel [33], the formula of which is shown in Equation (19):

$$K({\mathit{x}}_{\mathit{k}},{\mathit{v}}_{\mathit{i}})=\exp (-\frac{\left|\right|{\mathit{x}}_{\mathit{k}}-{\mathit{v}}_{\mathit{i}}|{|}^2}{2\times {\delta }^2})$$

(19)

where δ is bandwidth, which has an effect on the performance of the kernel metric. In the paper, the bandwidth is empirically selected as the number of spectral bands.

In this paper, a variant of DE, namely jDE [30], is used to optimize the objective function Equation (17), or Equation (18), respectively. The whole optimization process of jDE can be implemented according to the following steps:

Step 1. Initialization of the population. For a remote sensing image with C clusters and D spectral bands, the individual encoding strategy of FCIDE is as Figure 7, in which C cluster centers are encoded and D bands are encoded for each cluster center. Considering the adaptive mutation and crossover in Step 3, the mutation scale factor F, and the crossover constant CR are also encoded into the individual.

Figure 7. The example of individual encoding in jDE (e.g., K cluster centers and two bands).

Figure 7. The example of individual encoding in jDE (e.g., K cluster centers and two bands).

Step 2. Calculation of the fitness of each individual using the objective function Equation (17) or Equation (18).

Step 3. Adaptive mutation and crossover. In DE, the mutation operator amounts to creating a donor vector V_i(t) = [v_i,1(t), v_i,2(t),…, v_i,C×D(t)]^T for changing each individual of the population. The mutation process can be expressed as Equation (20):

$${\mathit{V}}_{\mathit{i}}(t)={\mathit{X}}_{r_1^i}(t)+F_i({\mathit{X}}_{r_2^i}(t)-{\mathit{X}}_{r_3^i}(t))$$

(20)

where $X_{r1}^i$, $X_{r2}^i$, $X_{r3}^i$ are picked up randomly from the population.

After mutation operator, crossover is operated between the donor vector V_i(t) and the target vector X_i(t), generating a trial vector U_i(t) = [u_i,1(t), u_i,2(t),…, u_i,C×D(t)]^T. The crossover operator can be implemented as Equation (21):

$$u_{i,j}(t)=\{\begin{array}{l}{v}_{i,j}(t),if(ran{d}_{i,j}(0,1)\le C{R}_{i}orj=j_{rand})\\ x_{i,j}(t),otherwise\end{array}$$

(21)

There are two main parameters including F and CR in DE. As is shown in Figure 6, each individual not only encodes the cluster centers but also the parameters CR and F enabling their update in the process of evolution. The F_i and CR_i can be updated according to Equation (22) and Equation (23):

$$F_i^{\text{'}}=\{\begin{array}{l}0.1+0.9\times rand(0,1),ifrand(0,1)<0.1\\ F_i,otherwise\end{array}$$

(22)

$$C{R}_i^{\text{'}}=\{\begin{array}{l}rand(0,1),ifrand(0,1)\le 0.1\\ C{R}_i,otherwise\end{array}$$

(23)

Step 4. Recalculation of the fitness of offspring U_i(t) using the objective function Equation (17) or (18).

Step 5. Selection. The selection operator is to decide who is the winner between the target vector X_i(t) and the trial vector U_i(t). The vector with better fitness can be selected to the next generation. The target vector of next generation can be generated by selection operator as Equation (24):

$${\mathit{X}}_i(t+1)=\{\begin{array}{l}{\mathit{U}}_i(t),iff({\mathit{U}}_i(t))\le f({\mathit{X}}_i(t))\\ {\mathit{X}}_i(t),otherwise\end{array}$$

(24)

Step 6. Elite strategy. In order to speed the coverage of iteration and enhance the efficiency of optimization, elite strategy is applied, which preserves the individual with the best fitness found so far.

Step 7. Terminal condition. Repeat Steps 3 to step 6 until the terminal condition is met. The terminal condition is to either reach the max number of iterations or begin to stagnate in order to update the best individual.

Step 8. Clustering. The membership matrix U = [u_ik] corresponding to the best individual is calculated based on the cluster center encoded in the best individual. Each pixel is then assigned to the cluster center with the largest membership u_ik using Equation (25):

$$y_k=\underset{1\le i\le C}{\text{arg max}}{u}_{ik}$$

(25)

where y_k is the cluster label of the k-th pixel, C is the number of clusters.

4. Experimental Data and Results

4.1. The Comparison Methods and Parameter Setting

The proposed methods (i.e., L-SSC_E, and L-SSC_K) were compared with other clustering methods, including classical clustering methods (i.e., K-means, FCM [14], Gaussian Mixture Model (GMM)) and spectral-spatial clustering methods (i.e., FCM_S1 [16], KWFLICM [31], KADESFC [17]). It should be noted that L-SSC_E, and L-SSC_K are the methods that use Equations (17) and (18) as the objective function, respectively. In addition, principal component analysis (PCA) was applied to the remote sensing image before GMM was conducted in order to remove the correlation between different spectral bands and to better approximate the inverse of the covariance matrix in GMM. For KADESFC, L-SSC_E, and L-SSC_K, the size of the population is 5 × D [34] for Wuhan TM and Fancun Quickbird image, where D is the number of the spectral bands for the remote sensing image. In order to reduce the computational complexity, the size of population is set as 50 for the Indian Pine AVIRIS image. The max generation for KADESFC, L-SSC_E, and L-SSC_K is 100. For L-SSC and the comparison methods, the cluster number was set to be the class number in the ground truth

4.2. Experiment 1—Wuhan TM Image

In order to test the validity of proposed algorithm, a Wuhan TM image is used, which is a 30 m resolution multi-spectral Landsat TM image of Wuhan City, China with a size of 400 pixel × 400 pixel, in six bands. This region in the Wuhan TM image was expected to contain five classes, which are listed in Table 1. It also reports the details of the samples for the Wuhan TM image. The Wuhan TM image and ground truth image are shown in Figure 8a,b.

Figure 8c–j illustrates the clustering results using K-means, FCM, PCA+GMM, FCM_S1, KWFLICM, KADESFC, L-SSC_E, and L-SSC_K, respectively. As can be seen from Figure 8, these clustering methods, except K-means, achieve similar clustering results on the river and lake classes due to their simple characteristics. For the FCM method, the vegetation and building classes are classified incorrectly and the bare soil class is classified into two classes. In addition, for GMM, some pixels are misclassified into the building class. In addition, compared with the clustering results of K-means, FCM, and PCA+GMM with more isolated pixels, the other clustering methods give better visual results due to the utilization of spatial information. Compared with KADESFC, the clustering results of L-SSC_E and L-SSC_K perform better, especially in the building class in the left part of the image, resulting from that the weight parameter calculated by the patch image which takes the local information into consideration and can be more accurate.

Figure 8. Wuhan TM image and the clustering results. (a) WuhanTM image; (b) Groundtruth; (c) K-means; (d) FCM; (e) PCA+GMM; (f) FCM_S1; (g) KWFLICM; (h) KADESFC (i) L-SSC_E and (j) L-SSC_K.

Figure 8. Wuhan TM image and the clustering results. (a) WuhanTM image; (b) Groundtruth; (c) K-means; (d) FCM; (e) PCA+GMM; (f) FCM_S1; (g) KWFLICM; (h) KADESFC (i) L-SSC_E and (j) L-SSC_K.

Table 1. Details of the samples for the Wuhan TM image.

Class Name	River	Vegetation	Lake	Bare	Building
Test Samples	2557	4102	1737	1849	3037

Table 1. Details of the samples for the Wuhan TM image.

Class Name	River	Vegetation	Lake	Bare	Building
Test Samples	2557	4102	1737	1849	3037

To compare the algorithms above quantitatively, overall accuracy (OA) and kappa coefficient [35,36] for the image are listed in Table 2. L-SSC_K obtains the best OA, 92.41%, with the gain of 20.41%, 10.89%, 0.31%, 6.3%, 1.92%, 4.84%, and 0.38% over K-means, FCM, PCA+GMM, FCM_S1, KWFLICM, KADESFC, and L-SSC_E, respectively. In most cases, the SSC clustering methods (i.e., FCM_S1, KWFLICM, KADESFC, and L-SSC_E) can achieve higher clustering accuracy due to the utilization of spatial information. We can also see that PCA+GMM get relative high clustering accuracy on about 92%. This is because that the PCA was firstly applied, resulting in a distinctive data structure compared with the original one. In addition, compared with KADESFC (OA = 87.57%), the clustering results of L-SSC_E (OA = 92.03%) and L-SSC_K (OA = 92.41%) achieve higher clustering accuracy, which also demonstrate the effectiveness of the local weight parameter determination method and its capability of better balancing the trade-off between the spectral term and spatial term. Although KWFLICM was designed to determine the weight parameter based on the local window, it cannot get higher clustering accuracy on the Wuhan TM image. This is because KWFLICM was originally designed for the natural image segmentation, in which there only exists one spectral band and the adaptive determination strategy of weight parameter and bandwidth in KWFLICM do not take the multi-spectral bands into consideration. Compared with L-SSC_E, the clustering result of L-SSC_K performs a little better, which demonstrates the effectiveness of kernel technique for kernelizing the objective function. The quantitative comparison of these algorithms is consistent with the visual finding. Based on the above analysis, L-SSC_E and L-SSC_K outperform other clustering methods.

Table 2. Comparison of clustering accuracy for Wuhan TM image.

Class	K-Means	FCM	PCA+GMM	FCM_S1	KWFLICM	KADESFC	L-SSC_E	L-SSC_K
--	Producer’s Accuracy (%)
River	100.00	100.00	100.00	100.00	100.00	100.00	100.00	100.00
Vegetation	85.31	82.31	93.83	88.99	91.17	89.78	93.46	93.29
Lake	0	99.81	95.00	100.00	99.94	99.94	100.00	100.00
Bare soil	78.43	60.88	94.76	71.09	86.80	75.24	88.34	94.93
Building	49.58	71.72	68.13	72.09	72.15	73.95	75.51	66.87
--	User’s Accuracy (%)
River	62.03	99.96	100.00	100.00	100.00	100.00	100.00	100.00
Vegetation	92.12	74.96	98.51	81.94	92.04	84.44	96.29	96.59
Lake	0	91.85	100.00	95.82	99.94	85.32	82.49	86.51
Bare soil	75.50	67.09	80.98	75.60	79.66	83.27	87.53	85.45
Building	96.83	85.17	79.82	84.22	83.88	85.97	88.54	90.86
OA (%)	71.70	81.52	92.10	86.11	90.49	87.57	92.03	92.41
Kappa	0.6317	0.7600	0.8976	0.8196	0.8769	0.8390	0.8971	0.9095

Table 2. Comparison of clustering accuracy for Wuhan TM image.

Class	K-Means	FCM	PCA+GMM	FCM_S1	KWFLICM	KADESFC	L-SSC_E	L-SSC_K
--	Producer’s Accuracy (%)
River	100.00	100.00	100.00	100.00	100.00	100.00	100.00	100.00
Vegetation	85.31	82.31	93.83	88.99	91.17	89.78	93.46	93.29
Lake	0	99.81	95.00	100.00	99.94	99.94	100.00	100.00
Bare soil	78.43	60.88	94.76	71.09	86.80	75.24	88.34	94.93
Building	49.58	71.72	68.13	72.09	72.15	73.95	75.51	66.87
--	User’s Accuracy (%)
River	62.03	99.96	100.00	100.00	100.00	100.00	100.00	100.00
Vegetation	92.12	74.96	98.51	81.94	92.04	84.44	96.29	96.59
Lake	0	91.85	100.00	95.82	99.94	85.32	82.49	86.51
Bare soil	75.50	67.09	80.98	75.60	79.66	83.27	87.53	85.45
Building	96.83	85.17	79.82	84.22	83.88	85.97	88.54	90.86
OA (%)	71.70	81.52	92.10	86.11	90.49	87.57	92.03	92.41
Kappa	0.6317	0.7600	0.8976	0.8196	0.8769	0.8390	0.8971	0.9095

4.3. Experiment 2—Fancun QuickBird Image

The second experiment dataset (Fancun QuickBird dataset) [37] was a 2.4-m spatial resolution QuickBird (QB) image (400 × 400) over the Fancun area in Hainan province, China, which was acquired in January 2010. This remote sensing dataset has been used for testing a remote sensing image supervised classification method in [37]. However, the ground truth in [37] is not appropriate for remote sensing image clustering because of the fact that the number of shadow pixels is so small that it is difficult to distinguish the shadow class and water class in the process of clustering. Hence, in this paper, for the task of remote sensing image clustering, the shadow class and water class are merged into one class in the ground truth for testing the clustering performance. In addition, a new concrete class is added into the ground truth due to its large amount. Figure 9a,b show the Fancun image and its corresponding ground truth. Table 3 reports the number of test samples.

Figure 9. Fancun image and its clustering results. (a) WuhanTM image; (b) Groundtruth; (c) K-means; (d) FCM; (e) PCA+GMM; (f) FCM_S1; (g) KWFLICM; (h) KADESFC; (i) L-SSC_E and (j) L-SSC_K.

Figure 9. Fancun image and its clustering results. (a) WuhanTM image; (b) Groundtruth; (c) K-means; (d) FCM; (e) PCA+GMM; (f) FCM_S1; (g) KWFLICM; (h) KADESFC; (i) L-SSC_E and (j) L-SSC_K.

Table 3. Details of the samples for the Fancun image.

Class Name	Water + Shadow	Tree	Bare	Grass	Building	Road	Concrete
Test Samples	10,986	25,242	4465	4052	8233	3931	1951

Table 3. Details of the samples for the Fancun image.

Class Name	Water + Shadow	Tree	Bare	Grass	Building	Road	Concrete
Test Samples	10,986	25,242	4465	4052	8233	3931	1951

Figure 9c–j illustrates the clustering results using K-means, FCM, PCA+GMM, FCM_S1, KWFLICM, KADESFC, L-SSC_E, and L-SSC_K, respectively. As can be seen from Figure 9, compared with FCM, KWFLICM, and FCM_S1, the five other algorithms can distinguish the road class (labelled 2) better, especially for KADESFC, L-SSC_E and L-SSC_K. As for the tree class (labelled 1), some pixels in K-means, KWFLICMand FCM_S1 are misclassified into grass class. The results of L-SSC_E, L-SSC_K, and KADESFC look better. As for the grass class (labelled 3), some pixels in KADESFC are misclassified into the tree class while L-SSC_E, L-SSC_K can achieve better visual result, demonstrating the efficiency of the local weight parameter calculated by the patch image. The above comparisons can demonstrate that the proposed SSC method can not only incorporate the spatial information into the clustering result, it can also preserve the details of the image with the local weight parameter.

The Overall Accuracy (OA) and kappa coefficient for the image are also listed in Table 4. L-SSC_K obtains the best OA, 76.18%, with the gain of 10.15%, 12.58%, 9.74%, 9.07%, 7.06%, 3.38%, and 0.88% over K-means, FCM, PCA+GMM, FCM_S1, KWFLICM, KADESFC, and L-SSC_E, respectively. Compared with KADESFC with the clustering accuracy at 72.80%, the clustering results of L-SSC_E and L-SSC_K can get clustering accuracy at 75.30%, and 76.18%, which demonstrate the effectiveness of the local weight parameter calculated by the patch image. In addition, the clustering result of L-SSC_K can achieves slightly higher clustering accuracy than L-SSC_E, which demonstrates the effectiveness of the kernel technique. Especially for tree, grass, and road classes, L-SSC_E (78.05%, 96.13%, 77.94%) and L-SSC_K (84.72%, 97.33%, 77.44%) both achieve comparative Producer’s Accuracy (PA), which are consistent with the above visual result. The quantitative comparison of these algorithms is consistent with the visual finding.

Table 4. Comparison of clustering accuracy for the Fancun image.

Class	K-Means	FCM	PCA + GMM	FCM_S1	KWFLICM	KADESFC	L-SSC_E	L-SSC_K
--	Producer’s Accuracy (%)
Water and shadow	99.20	99.38	81.62	99.33	99.52	99.51	99.70	99.60
Tree	58.84	55.51	58.59	58.84	66.92	85.93	78.05	84.72
Grass	98.01	96.22	97.98	97.25	98.50	22.51	96.13	97.33
Bare	46.87	62.49	98.10	61.23	72.75	61.62	44.89	67.87
Building	26.04	36.21	43.50	35.20	43.48	20.87	32.24	26.28
Road	74.31	20.22	86.92	53.42	0.00	78.17	77.94	77.44
Concrete	90.88	97.44	0	98.15	99.18	99.08	99.74	95.23
--	User’s Accuracy (%)
Water and shadow	78.45	79.02	99.99	86.07	87.22	77.14	80.99	83.99
Tree	99.44	99.18	99.62	99.35	99.39	86.39	99.46	99.47
Grass	34.35	51.68	48.70	48.26	36.06	50.76	73.58	62.18
Bare	43.79	49.20	67.87	49.75	50.07	53.81	50.12	49.30
Building	51.30	55.25	79.79	59.76	49.74	60.94	61.42	32.93
Road	52.75	9.83	48.32	24.96	0.00	51.01	50.87	46.59
Concrete	54.77	48.08	0	48.07	47.79	46.93	44.17	50.72
OA (%)	66.03	63.60	66.44	67.11	69.12	72.80	0.7530	76.18
Kappa	0.5793	0.5518	0.5914	0.5940	0.6113	0.6365	0.6843	0.6920

Table 4. Comparison of clustering accuracy for the Fancun image.

Class	K-Means	FCM	PCA + GMM	FCM_S1	KWFLICM	KADESFC	L-SSC_E	L-SSC_K
--	Producer’s Accuracy (%)
Water and shadow	99.20	99.38	81.62	99.33	99.52	99.51	99.70	99.60
Tree	58.84	55.51	58.59	58.84	66.92	85.93	78.05	84.72
Grass	98.01	96.22	97.98	97.25	98.50	22.51	96.13	97.33
Bare	46.87	62.49	98.10	61.23	72.75	61.62	44.89	67.87
Building	26.04	36.21	43.50	35.20	43.48	20.87	32.24	26.28
Road	74.31	20.22	86.92	53.42	0.00	78.17	77.94	77.44
Concrete	90.88	97.44	0	98.15	99.18	99.08	99.74	95.23
--	User’s Accuracy (%)
Water and shadow	78.45	79.02	99.99	86.07	87.22	77.14	80.99	83.99
Tree	99.44	99.18	99.62	99.35	99.39	86.39	99.46	99.47
Grass	34.35	51.68	48.70	48.26	36.06	50.76	73.58	62.18
Bare	43.79	49.20	67.87	49.75	50.07	53.81	50.12	49.30
Building	51.30	55.25	79.79	59.76	49.74	60.94	61.42	32.93
Road	52.75	9.83	48.32	24.96	0.00	51.01	50.87	46.59
Concrete	54.77	48.08	0	48.07	47.79	46.93	44.17	50.72
OA (%)	66.03	63.60	66.44	67.11	69.12	72.80	0.7530	76.18
Kappa	0.5793	0.5518	0.5914	0.5940	0.6113	0.6365	0.6843	0.6920

4.4. Experiment 3—Indian Pine AVIRIS Image

Experiment 3 was conducted using an Airborne Visible/Infrared Imaging Spectrometer (AVIRIS) dataset from over the Northwest India Indian Pine test site by the Jet Propulsion Laboratory and NASA/Ames in June 1992, which was captured from six miles in the western area of Northwest Tippecanoe County (NTC). This AVIRIS image with a size of 145 pixels by 145 pixels represents a 2 mile × 2 mile area at 20 m spatial resolution. A total of 20 channels from the water absorption and noisy bands (104–108, 150–163, 220) were removed from the original 220 spectral channels, leaving 200 spectral features for the experiments. For the indication of clustering task, we referred to the strategy in [38] to merge the land cover classes to get the ground truth composed of five classes including wood, corn, hay, soybean, and grass. Figure 10a,b show the Indian Pine AVIRIS image and its corresponding ground truth. Table 5 reports the number of test samples for the five classes.

Table 5. The number of the test samples used for the Indian Pine image.

Class Name	Wood	Corn	Hay	Soybean	Grass
Test Samples	2495	2134	478	4020	963

Table 5. The number of the test samples used for the Indian Pine image.

Class Name	Wood	Corn	Hay	Soybean	Grass
Test Samples	2495	2134	478	4020	963

Figure 10. Indian Pine AVIRIS image and its clustering results. (a) WuhanTM image; (b) Groundtruth, (c) K-means; (d) FCM; (e) PCA+GMM; (f) FCM_S1; (g) KWFLICM; (h) KADESFC; (i) L-SSC_E and (j) L-SSC_K.

Figure 10. Indian Pine AVIRIS image and its clustering results. (a) WuhanTM image; (b) Groundtruth, (c) K-means; (d) FCM; (e) PCA+GMM; (f) FCM_S1; (g) KWFLICM; (h) KADESFC; (i) L-SSC_E and (j) L-SSC_K.

Figure 10c–j illustrates the clustering results using K-means, FCM, PCA+GMM, FCM_S1, KWFLICM, KADESFC, L-SSC_E, and L-SSC_K, respectively. As can be seen from Figure 10, in the region labelled 1, K-means, PCA+GMM, and KWFLICM misclassify the hay class into the grass class. The results of other methods, especially for L-SSC_E and L-SSC_K, look better. In the region labelled 2, some pixels in the results of FCM, FCM_S1, KWFLICM, KADESFC, and L-SSC_E misclassify the soybean class into the corn class. Totally, the proposed method L-SSC_K can acquire comparative visual result on both regions labelled 1 and 2. The Overall Accuracy (OA) and kappa coefficient for the image are also listed in Table 6. L-SSC_K obtains the best OA, 63.49%, with the gain of 12.67%, 9.65%, 6.94%, 9.52% 6.51% and 2.16% over K-means, FCM, PCA+GMM, FCM_S1, KWFLICM, KADESFC, and L-SSC_E, respectively. Especially, L-SSC_K achieves the comparative producer’s accuracy on both soybean and corn classes, which is consistent with the above visual results. Compared with KADESFC (OA = 57.98%), the clustering results of L-SSC_E (OA = 62.33%) and L-SSC_K (OA = 64.49%) perform better due to the fact that the local weight parameter calculated by the patch image can better describe the relation between different pixels. In addition, Compared with L-SSC_E, the clustering result of L-SSC_K get higher clustering accuracy, which demonstrates the effectiveness of the kernel technique. The quantitative comparison of these algorithms is consistent with the visual finding. As can be seen from the above analysis, the comparisons of these algorithms for the Indian Pine AVIRIS image also agree with the Wuhan TM and Fancun Quickbird image. The same conclusion can be made that L-SSC_E and L-SSC_K outperform other clustering methods.

Table 6. Comparison of clustering accuracy for Indian Pine AVIRIS image.

Class	K-Means	FCM	PCA+GMM	FCM_S1	KWFLICM	KADESFC	L-SSC_E	L-SSC_K
--	Producer’s Accuracy (%)
Wood	20.04	53.19	26.97	53.59	50.46	50.26	60.52	32.02
Corn	50.80	63.59	65.32	68.14	48.59	76.62	79.9	76.01
Hay	0	79.71	10.46	88.28	0.00	92.05	94.98	90.38
Soybean	72.66	53.23	67.14	54.63	60.05	46.79	46.02	76.29
Grass	75.18	34.06	95.02	41.33	86.81	66.46	79.96	60.96
--	User’s Accuracy (%)
Wood	32.20	42.60	35.27	43.06	44.39	39.34	41.62	51.05
Corn	97.13	96.86	100.00	97.06	98.95	99.33	94.77	98.30
Hay	0	25.08	14.01	29.87	0.00	34.46	60.78	32.24
Soybean	58.78	66.69	63.43	67.47	66.28	61.61	66.12	65.86
Grass	46.77	38.77	42.05	48.60	47.96	69.11	68.87	66.86
OA (%)	51.82	54.84	56.80	57.55	54.97	57.98	62.33	64.49
Kappa	0.3341	0.3998	0.4112	0.4337	0.3950	0.4412	0.4969	0.5126

Table 6. Comparison of clustering accuracy for Indian Pine AVIRIS image.

Class	K-Means	FCM	PCA+GMM	FCM_S1	KWFLICM	KADESFC	L-SSC_E	L-SSC_K
--	Producer’s Accuracy (%)
Wood	20.04	53.19	26.97	53.59	50.46	50.26	60.52	32.02
Corn	50.80	63.59	65.32	68.14	48.59	76.62	79.9	76.01
Hay	0	79.71	10.46	88.28	0.00	92.05	94.98	90.38
Soybean	72.66	53.23	67.14	54.63	60.05	46.79	46.02	76.29
Grass	75.18	34.06	95.02	41.33	86.81	66.46	79.96	60.96
--	User’s Accuracy (%)
Wood	32.20	42.60	35.27	43.06	44.39	39.34	41.62	51.05
Corn	97.13	96.86	100.00	97.06	98.95	99.33	94.77	98.30
Hay	0	25.08	14.01	29.87	0.00	34.46	60.78	32.24
Soybean	58.78	66.69	63.43	67.47	66.28	61.61	66.12	65.86
Grass	46.77	38.77	42.05	48.60	47.96	69.11	68.87	66.86
OA (%)	51.82	54.84	56.80	57.55	54.97	57.98	62.33	64.49
Kappa	0.3341	0.3998	0.4112	0.4337	0.3950	0.4412	0.4969	0.5126

5. Discussion

5.1. Discussion on Selection of Patch Size

The patch size has an impact on the performance of the proposed method L-SSC. Therefore, we discuss the selection of patch size visually and quantitatively based on the weight parameter image and clustering accuracy of different patch sizes.

(1)

Visual Comparison (Weight Parameter Image) of Different Patch Sizes

For Wuhan TM, Fancun Quickbird, and Indian Pine AVIRIS images, Figure 11, Figure 12 and Figure 13 list the weight parameter images based on different patch sizes including 25 × 25, 50 × 50, 75 × 75, 100 × 100, 145 × 145, 150 × 150, 200 × 200, 300 × 300, and 400 × 400. In Figure 11, Figure 12 and Figure 13, the darker the pixel is, the smaller the local weight parameter value is, and vice versa. It should be noted that the patch size of 400 × 400 for Wuhan TM or Fancun Quickbird, and 145 × 145 for Indian Pine AVIRIS image is equal to the size of the corresponding whole image. Thus, the comparison between 400 × 400 for Wuhan TM or Fancun Quickbird and 145 × 145 for Indian Pine AVIRIS image with other patch sizes can be used to demonstrate the effectiveness of FCIDE-based local weight parameter determination method.

Figure 11. The weight parameter image of the Wuhan TM image for different patch sizes (refer to the text for a detailed description of the markup).

Figure 11. The weight parameter image of the Wuhan TM image for different patch sizes (refer to the text for a detailed description of the markup).

Figure 12. The weight parameter image of the Fancun image for different patch sizes (refer to the text for a detailed description of the markup).

Figure 12. The weight parameter image of the Fancun image for different patch sizes (refer to the text for a detailed description of the markup).

Figure 13. The weight parameter image of the Indian Pine image for different patch sizes.

Figure 13. The weight parameter image of the Indian Pine image for different patch sizes.

For the Wuhan TM image in Figure 11, the pixels in the region (labelled red circle) belong to town, which has a variety of objects. However, when the patch size is 400 × 400, these pixels are assigned excessive weight parameter values, which can result in over-smoothing. That is, the complex distribution of objects in this region may be smoothed due to the excessive weight parameter value calculated by whole image. When the patch size is smaller than 200 × 200, the weight parameter value in these regions become small, which can prevent over-smoothing. We also can see that when the patch size is equal to 25 × 25, or 50 × 50 (labelled red rectangle), mosaic appearance will emerge, which are not in line with the real situation. Therefore, based on visual comparison of different patch sizes, the patch size (75 × 75–200 × 200) is much preferred for the Wuhan TM image. For the Fancun image in Figure 12, when the patch size is 400 × 400, the building class (labelled red circle) is assigned an excessive weight parameter value, compared with the weight parameter calculated by a patch image with 100 × 100. Moreover, as for the road class (labelled red lines), the weight parameter value is relatively small (i.e., dark) when patch size is equal to 100 × 100, compared with weight parameter calculated by the whole image (400 × 400), in which the weight parameter value of these pixels is excessive and unacceptable, resulting in the smoothing of the road class. Furthermore, like the Wuhan TM image, when the patch size is too small, a mosaic appearance (labelled red rectangle) will also emerge. For the Indian Pine AVIRIS image in Figure 13, due to the fact the shapes of the different farmlands is regular (e.g., rectangle) and with small area, it weakens the impact of the mosaic.

(2)

Quantitative Comparison (Clustering Accuracy) of Different Patch Sizes

Table 7, Table 8 and Table 9 show the clustering accuracy of L-SSC_E and L-SSC_K for different patch sizes, namely 25 × 25, 50 × 50, 75 × 75, 100 × 100, 145 × 145, 150 × 150, 200 × 200, 300 × 300 and 400 × 400.

Table 7. The clustering accuracy of different patch sizes for the Wuhan TM image.

Patch Size	25 × 25	50 × 50	75 × 75	100 × 100	150 × 150	200 × 200	300 × 300	400 × 400
--	L-SSC_E
OA (%)	82.14	71.80	79.79	87.46	92.00	92.03	82.78	88.29
Kappa	0.7687	0.6407	0.7370	0.8399	0.8969	0.8971	0.7772	0.8483
--	L-SSC_K
OA (%)	78.79	81.44	89.49	91.50	90.58	91.73	92.41	87.48
Kappa	0.7246	0.7587	0.8648	0.8901	0.8789	0.8926	0.9018	0.8379

Table 7. The clustering accuracy of different patch sizes for the Wuhan TM image.

Patch Size	25 × 25	50 × 50	75 × 75	100 × 100	150 × 150	200 × 200	300 × 300	400 × 400
--	L-SSC_E
OA (%)	82.14	71.80	79.79	87.46	92.00	92.03	82.78	88.29
Kappa	0.7687	0.6407	0.7370	0.8399	0.8969	0.8971	0.7772	0.8483
--	L-SSC_K
OA (%)	78.79	81.44	89.49	91.50	90.58	91.73	92.41	87.48
Kappa	0.7246	0.7587	0.8648	0.8901	0.8789	0.8926	0.9018	0.8379

Table 8. The clustering accuracy of different patch sizes for the Fancun image.

Patch Size	25 × 25	50 × 50	75 × 75	100 × 100	150 × 150	200 × 200	300 × 300	400 × 400
--	L-SSC_E
OA (%)	61.82	71.28	75.36	70.48	65.54	75.30	64.68	67.4
Kappa	0.5272	0.6371	0.6794	0.6307	0.5718	0.6843	0.5342	0.5922
--	L-SSC_K
OA (%)	63.68	65.69	76.18	75.56	67.06	66.62	64.84	66.10
Kappa	0.5494	0.5735	0.6920	0.6820	0.5939	0.5810	0.5648	0.5835

Table 8. The clustering accuracy of different patch sizes for the Fancun image.

Patch Size	25 × 25	50 × 50	75 × 75	100 × 100	150 × 150	200 × 200	300 × 300	400 × 400
--	L-SSC_E
OA (%)	61.82	71.28	75.36	70.48	65.54	75.30	64.68	67.4
Kappa	0.5272	0.6371	0.6794	0.6307	0.5718	0.6843	0.5342	0.5922
--	L-SSC_K
OA (%)	63.68	65.69	76.18	75.56	67.06	66.62	64.84	66.10
Kappa	0.5494	0.5735	0.6920	0.6820	0.5939	0.5810	0.5648	0.5835

Table 9. The clustering accuracy of different patch sizes for the Indian Pine AVIRIS image.

Patch Size	25 × 25	50 × 50	75 × 75	100 × 100	150 × 150
--	L-SSC_E
OA (%)	61.47	62.33	58.14	57.36	57.41
Kappa	0.4814	0.4969	0.4307	0.4332	0.4322
--	L-SSC_K
OA (%)	61.02	64.49	60.37	60.29	63.63
Kappa	0.4828	0.5126	0.4567	0.4734	0.4985

Table 9. The clustering accuracy of different patch sizes for the Indian Pine AVIRIS image.

Patch Size	25 × 25	50 × 50	75 × 75	100 × 100	150 × 150
--	L-SSC_E
OA (%)	61.47	62.33	58.14	57.36	57.41
Kappa	0.4814	0.4969	0.4307	0.4332	0.4322
--	L-SSC_K
OA (%)	61.02	64.49	60.37	60.29	63.63
Kappa	0.4828	0.5126	0.4567	0.4734	0.4985

In Table 7, for the Wuhan TM image, it can be seen that L-SSC_E can acquire higher clustering accuracy when the patch size is 150 × 150–200 × 200, and L-SSC_K can perform better when the patch size is 75 × 75–300 × 300. In both above situations, they can achieve better clustering performance than the clustering result when the patch size is 400 × 400 (i.e., the whole image), validating the effectiveness of local weight parameter. On the other hand, when the patch size is small (e.g., 25 × 25, 50 × 50), their clustering accuracy is not so satisfying. To some extent, this is consistent with the visual comparison in Figure 11. Therefore, based on the visual and quantitative comparison, the optimal patch size for the Wuhan TM image can be 150 × 150–200 × 200. In Table 8, for the Fancun Quickbird image, the same conclusion can be made that the optimal patch size for the Fancun Quickbird image can be 75 × 75–200 × 200. It should be specified that, in Table 9, for the Indian Pine AVIRIS image, the optimal patch size is smaller (i.e., 50 × 50) due to the fact the regular shape and small size of farm land in the region decreases the impact of the mosaic, which is also consistent with the conclusion made in the visual comparison of different patch sizes in Figure 13.

Based on the visual and quantitative comparison of L-SSC for different patch sizes, it can be seen that L-SSC with the local weight parameter can achieve higher clustering accuracy than the method with the weight parameter calculated by the whole image (e.g., 400 × 400 for the Wuhan TM and Fancun Quickbird images, or 145 × 145 for the Indian Pine AVIRIS image). Especially, visual comparison shows that it can also preserve the detail of some classes, such as road and building. However, it is not so easy to select one optimal patch size for all remote sensing images due to the different characteristics of different images (e.g., the shape and size of objects). Firstly, when the patch is smaller, the more accurate local weight parameter can be acquired. However, more patch images mean that huge amounts of clustering results with different degrees of detail may emerge, resulting in the mosaic appearance (e.g., for Wuhan TM and Fancun Quickbird images). Therefore, in this situation, a middle-size (150 × 150–200 × 200) can be selected. Secondly, when the shape of the objects is regular (e.g., a rectangle for the Indian Pine AVIRIS image), the degree of detail of clustering results with different patch size is similar, weakening the impact of mosaic. Thus, for the Indian Pine AVIRIS image, a small patch size will be preferred (50 × 50).

5.2. Computational Complexity Analysis

The computational complexity of L-SSC is analyzed, which includes the parts: the FCIDE-based local weight parameter determination method, and the jDE-based clustering method.

Part 1: FCIDE-based local weight parameter determination method:

• Initialization. The computational complexity of initialization is $\mathrm{O}\left(N{P}_1\times C_{max}\right)$, where $N{P}_1$ represents the number of individuals, $C_{max}$ is the maximum number of cluster numbers.
• Fitness calculation. (a) Supposing there are $N_1$ pixels in each patch image, the computational complexity of this step is $\mathrm{O}\left(N_1\times C_{max}\right)$. (b) The time for updating the clusters is $\mathrm{O}\left(C_{max}\right)$. Thus, the total time that is spent on fitness calculation is $\mathrm{O}\left(N{P}_1\times N_1\times C_{max}\right)$.
• Mutation and crossover operation. In this step, the time consumed is $\mathrm{O}\left(N_1\times C_{max}\right)$.
• Selection. The selection operation’s time is $\mathrm{O}\left(N{P}_1\right)$.

The computational complexity for the FCIDE-based local weight parameter determination method is $\mathrm{O}\left(N{P}_1\times N_1\times C_{max}\times \text{iP}\times G_1\right)$, namely $\mathrm{O}\left(N{P}_1\times N\times C_{max}\times G_1\right)$, where $\mathrm{iP}$ is the number of patch images, and $G_1$ is the maximum generation for the FCIDE-based local weight parameter determination method, $N$ is the number of pixels in the whole image.

Part 2: jDE-based clustering method:

• Initialization. The time which this step needs is $\mathrm{O}\left(NP\times C\right)$, where $NP$ represents the number of individuals, $C$ is the number of cluster numbers.
• Fitness calculation. (a) Supposing there are $N$ pixels in the whole image, the computational complexity of this step is $\mathrm{O}\left(N\times C\right)$. (b) The time for updating the clusters is $\mathrm{O}\left(C\right)$. Thus, the total time that is spent on fitness calculation is $\mathrm{O}\left(NP\times N\times C\right)$.
• Mutation and crossover operation. In this step, the time consumed is $\mathrm{O}\left(NP\times C\right)$.
• Selection. The selection operation’s time is $\mathrm{O}\left(NP\right)$.

The computational complexity for the jDE-based clustering method is $\mathrm{O}\left(NP\times N\times C\times G_2\right)$, where $G_2$ is the maximum generation for the jDE-based clustering method.

Based on the above analysis, the computational complexity of L-SSC is $\mathrm{O}\left(N{P}_1\times N\times C_{max}\times G_1\right)$ or $\mathrm{O}\left(NP\times N\times C\times G_2\right)$. The time consumed by each algorithm is shown in Figure 14. Although the computation cost of L-SSC is slightly more than KADESFC, it can be acceptable with regard to the clustering accuracy improvement.

Figure 14. Comparison of computational time for (a) Wuhan TM; (b) Fancun IKONOS; and (c) Indian Pine AVIRIS.

Figure 14. Comparison of computational time for (a) Wuhan TM; (b) Fancun IKONOS; and (c) Indian Pine AVIRIS.

6. Conclusions

This paper proposed spectral-spatial clustering with a local weight parameter determination method for remote sensing image, namely L-SSC. L-SSC can adaptively determine the local weight parameter using patch images and take the local spatial information into consideration, resolving the problem brought by the large scale of remote sensing image. The experimental results show that the FCIDE-based local weight parameter can not only incorporate the spatial information, smoothing the isolated pixels in the clustering result, it can also preserve the details of some classes. Furthermore, the global optimization method, jDE, was used to optimize the proposed clustering objective function, Jm_K, and Jm_E, further improving the clustering accuracy. As a result, the proposed clustering methods, L-SSC_E and L-SSC_K, consistently outperform other clustering algorithms visually and quantitatively.

Although two DE-based methods are utilized, they function differently in L-SSC_E, or L-SSC_K. For example, in the process of local weight parameter determination, due to the unknown cluster number of each patch image, automatic clustering methods should be used (such as FCIDE), which can determine the cluster number automatically. At the same time, in order to acquire a more satisfying optimization result, clustering methods, such as jDE, were utilized because of their powerful global optimization capability. This work provides an effective way for integrating two DE-based methods in the task of remote sensing image clustering.

The discussion on the selection of patch size demonstrated the effectiveness of the proposed FCIDE-based local weight parameter determination method. However, due to different characteristics of different images (e.g., the shape and size of objects), it is not easy to select one exact optimal patch size for all remote sensing images. Our future work may focus on the adaptive determination of patch size and new shapes of patch may also be introduced based on the segmentation results.