Image segmentation based on super-pixel with neighborhood constrained and multi-level FCM clustering

Abstract

In order to solve the problem of noise sensitivity and low precision in image segmentation, a new image segmentation method based on super-pixel with neighborhood constrained and multi-level FCM clustering is proposed. Firstly, an improved SLIC algorithm of FCM is designed based on the local pixel region of the image to get the refined super-pixel. Then, the improved FCM clustering algorithm is combined with the spatial relationship of neighborhood super-pixel to mark the super-pixel categories. In order to verify the effectiveness of the algorithm, the artificial synthetic image with noise and natural image without noise are used for comparison experiments. The experimental result show the algorithm proposed in this paper can not only suppress the noise, but also improve the processing accuracy.

Keywords

Neighbourhood super-pixel simple linear iterative clustering fuzzy C-means image segmentation

1. Introduction

Fuzzy C-Means clustering is a nonlinear programming process with constraints. The algorithm has been successfully applied in image processing [1, 2, 3, 4] pattern recognition [5, 6], data mining [7], control decision [8] and other fields. However, in the field of image processing, due to the inherent characteristics of image data, there are still many shortcomings when using FCM algorithm for image segmentation. That are as follows: Firstly, the pixels that make up the image are many and complex, and the pixel distribution is uneven, especially the color image of “a little red in all green trees”. Secondly, traditional FCM algorithm is applied to image segmentation, it ignores the influence of pixel position, so the segmentation effect is not good and the accuracy is not high. Thirdly, FCM algorithm is an iterative algorithm based on “hill climbing”, which seek all pixels in image segmentation, so the execution time of the algorithm will increase sharply with the increase of image size and resolution, especially in processing of massive color image, its performance of real-time is even worse.

In view of the fact that the FCM algorithm ignores the influence of pixel position and noise sensitivity, scholars have proposed a series of improved algorithms [3, 4, 9, 10, 11, 12, 13, 14, 15, 16, 17]. Aiming at the spatial relationship of pixels, FCM_S1 proposed by reference 9̧ and FCM_S2 proposed by reference [10] are the early improved FCM algorithms that introduce neighborhood spatial information into image segmentation, FCM_S1 is an algorithm about robust image segmentation using FCM with spatial constraints based on new kernel-induced distance measure, and FCM_S2 is an algorithm of fast and robust fuzzy c-means clustering algorithms incorporating local information for image segmentation. After that, reference [11] defines a robust C-means clustering algorithm based on local information, its control parameters of local information influence factors proposed in this algorithm are obtained entirely from the calculation of pixel information, and no one sets other parameters for it.

Aiming at the processing of image noise and outliers, Guo et al. proposes an algorithm of Local Noise Detecting Adaptive Fuzzy C-mean Clustering (NDFCM) [2] for local noise detecting, which is effective for noise processing, but the execution time is long and the efficiency of image segmentation is not high. Tao et al. [3] proposed an improved Super-pixel Fast FCM clustering algorithm (SFFCM), based on morphological gradient reconstruction, which improves the segmentation accuracy and efficiency of color images, but the segmentation accuracy of images with a lot of noise is lower than that of NDFCM. Gu et al. [14] proposed fuzzy double C-means clustering based on sparse self-representation model, its main feature is that can process two different dimensional data sets at the same time, and has good data classification and recognition ability, high robustness on noise and data adaptability, however, data feature extraction is complex and time-consuming for it.

Zhang et al. [4] proposed a Deviation Sparse Fuzzy C-Means clustering algorithm with Neighborhood information constraints (DSFCM_N), which suppresses noise by introducing deviation tolerance distance vector $\lambda$ to achieve accurate image segmentation, but the determination of $\lambda$ is artificial and lack of theoretical foundation. In order to solve the problem of high time complexity of FCM algorithm in image segmentation, scholars have also proposed a series of improved algorithms [18, 19, 20]. Reference [18] proposed a fast robust fuzzy C-means clustering algorithm based on morphological reconstruction, its implementation of the method is simple, efficiency of execution is high, and it has a good effect on noisy image processing. The enhanced fuzzy clustering algorithm proposed in reference [19] uses filtered histogram information to complete image segmentation. Literature [20] proposes a fast general FCM algorithm combined with local neighborhood information in image segmentation. Although these algorithms reduce the time complexity of image processing and improve the efficiency of real-time in image segmentation, but image segmentation efficiency and accuracy are not satisfactory.

In view of this, based on the comprehensive analysis of the latest research progress at home and abroad, and based on the theory of SLIC (Simple Linear Iterative Clustering) [21], a neighborhood multi-level FCM clustering method for super-pixel image segmentation is proposed in this paper. The first-level FCM clustering algorithm is used to improve the SLIC super-pixel segmentation technique to obtain fine super-pixels, and the second level improves FCM clustering based on the neighborhood super-pixel constraint relationship on the basis of the first level, thus the super-pixel category marking is realized. Through two-level FCM clustering, we can further improve the segmentation accuracy and suppress noise in image segmentation.

2. Super-pixel segmentation based on FCM improved SLIC algorithm

Super-pixel is the use of image pixel color and position and other information to segment the image into a polygonal region composed of multiple adjacent pixels. SLIC is a classical super-pixel segmentation algorithm based on K-Means clustering. It uses the color and position information of the image format of CIELab to measure the similarity of pixels, CIELAB is an image colour standard formulated by CIE in 1931 the L represents image grey level, a and b are two colour channels. See relevant literature for details. And then generates super-pixel blocks with compact pixel distribution and uniform size. In each iteration, the algorithm updates the clustering center with the average of all pixels in the neighborhood block. However, due to the existence of noise pixels in the neighbourhood, not all the pixels in the neighborhood block have high similarity with the clustering center, so the clustering center is unstable.

In addition, when the distance between the pixel and the clustering center is used to measure the similarity, it does not been taken into account the relative importance of color and position. But in fact, the similarity of color (grayscale) is more important in the image with rich details, for the image with uniform colour (grayscale) distribution, the similarity of pixel position is more important. So when the classical SLIC algorithm is used for super-pixel segmentation of images with different structures, it may produce wrong segmentation, including under-segmentation and over-segmentation. Based on this, this paper designs a SLIC super-pixel segmentation algorithm based on FCM, which achieves good results in suppressing noise, and the accuracy and efficiency of real time in image segmentation is greatly improved.

2.1 Algorithm description

Let a CIELab image have $n$ pixels, and set the number of $n_{1}$ initial super-pixel blocks to be generated, then the size of each super-pixel block $r$ is:

$\displaystyle r=\sqrt{n/n_{1}}$ (1)

Then the initial clustering center $v_{k}$ of the super-pixel block is determined according to the average value of the color (grayscale) and position information of all pixels in the super-pixel block, that is:

$\displaystyle v_{k}=(\bar{l}_{k},\bar{a}_{k},\bar{b}_{k},\bar{x}_{k},\bar{y}_{% k})$ (2)

Where $k=1,2,\ldots,n_{1},\bar{a}_{k},\bar{b}_{k},\bar{x}_{k},\bar{y}_{k}$ is the mean value of the $l, a, b$ component of all pixels in the $k$ pixel block (for grayscale images, only $l$ is considered), and $\bar{x}_{k},\bar{y}_{k}$ is the mean position (row and column coordinates) of all pixels in the pixel block. Considering the irregularity of the super-pixel, when solving the super-pixel, in the neighborhood with $v_{k}$ as the center and 2 $r$ as the side length, the super-pixel can be obtained by calculating the color and position similarity between each pixel $p$ and $v_{k}$ . At the same time, in order to facilitate the calculation, the Gaussian kernel function is used to map it to the range of [0, 1]. The specific calculation is as follows:

The color distance between pixel p and the cluster center $v_{k}$ is:

$\displaystyle d_{c}(p,v_{k})=\sqrt{(l_{p}-\bar{l}_{k})^{2}+(a_{p}-\bar{a}_{k})% ^{2}+(b_{p}-\bar{b}_{k})^{2}}$ (3)

Where $l_{p},a_{p},b_{p}$ is the colour component of pixel $p$ , and the colour similarity after Gaussian normalization is:

$\displaystyle s_{c}(p,v_{k})=\exp(-d_{c}(p,v_{k})/2)$ (4)

It can be seen from the Eq. (4) that the closer colour of the pixel $p$ is to the cluster center, the larger the sc is. When the colour of $p$ is close to the $v_{k}$ sc $\approx$ 1, when the colour of $p$ is away from the cluster center $v_{k}$ , the $s_{c}$ approaches to 0. Therefore, Eq. (4) can better express the color similarity among the pixels in the neighbourhood of 2 $r$ $\times$ 2 $r$ and the cluster center.

Similarly, the distance between pixel p and the cluster center $v_{k}$ is:

$\displaystyle d_{s}(p,v_{k})=\sqrt{(x_{p}-\bar{x}_{k})^{2}+(y_{p}-\bar{y}_{k})% ^{2}}$ (5)

The position similarity after normalization by Gaussian kernel function is:

$\displaystyle s_{s}(p,v_{k})=\exp(-d_{s}(p,v_{k})/2)$ (6)

Considering the importance of colour and position in the similarity calculation, this paper introduces the parameter $\lambda$ as the weight to adjust the relationship between the two similarity, and the similarity between the pixel p and the cluster center $v_{k}$ in the neighborhood of the fusion color and position is:

$\displaystyle s(p,v_{k})=s_{c}(p,v_{k})+\lambda\cdot s_{s}(p,v_{k})$ (7)

With the above definition, when using the FCM algorithm for super-pixel clustering segmentation, we only need to search the pixels in the 2 $r$ $\times$ 2 $r$ window of the image, and get the membership degree of each pixel to the clustering center, which avoids the global search of pixels in the whole image, and then realizes the preliminary super-pixel segmentation. The implementation steps of the algorithm are as follows:

S1: set the number of $n_{1}$ pre-segmented super-pixels, get the size $r$ of the super-pixel block according to the Eq. (1), set the weight coefficient $\lambda$ in the similarity according to the type of the image, set the maximum number of iterations $T$ , and the initial number of iterations $b=$ 1; S2: initialize the cluster center $v_{k}(k=1,2,\ldots,n1)$ for each super pixel block; S3: according to the iterative formula of FCM clustering algorithm, the membership degree of pixel p in 2 $r$ $\times$ 2 $r$ window and all clustering centers covered in this window is calculated, that is:

$\displaystyle u_{pk}=\left[\sum\nolimits_{i=1}^{c}(d_{pk}/d_{pi})^{2/m-1}% \right]^{-1}$ (8)

In Eq. (8), $d_{pk}$ is the similarity between the pixel p in the 2 $r$ $\times$ 2 $r$ window and the $k$ cluster center covered in the window, and its value is equal to the $s(p,v_{k})$ value in Eq. (7), and c is the number of cluster centers included in the window; S4: according to the membership degree $u_{pk}$ in step S3, the new cluster center is calculated according to the iterative formula of cluster center in FCM algorithm, that is:

$\displaystyle v_{k}=\left(\sum\nolimits_{i=1}^{c}(u_{pk})^{m}\cdot I_{p}\right% )\left/\sum\nolimits_{i=1}^{c}(u_{pk})^{m}\right.$ (9)

The $I_{p}=(l_{p}a_{p}b_{p}x_{p}y_{p})$ in Eq. (9) is the component value of pixel $p$ , which is the same as $v_{k}=(\bar{l}_{k},\bar{a}_{k},\bar{b}_{k},\bar{x}_{k},\bar{y}_{k})$ ; S5: update the number of iterations $b=b+1$ , and then determine whether $b\geqslant T$ is true. Yes, output the class of pixel p according to the principle of maximum membership degree, otherwise return to step S3.

2.2 Refinement of super-pixel

The above SLIC iterative method based on FCM realizes the initial division of super-pixels. FCM is a fuzzy clustering algorithm, which assigns pixels to a certain class according to the principle of maximum membership degree. However, in the process of pixel classification, some pixels, such as boundary pixels, have little difference in membership degree to several classes, which will lead to miss-division when iterating many times, especially when the initial clustering center is not selected correctly. In addition, if the neighborhood block contains noise pixels, FCM clustering will also classify them into a certain category, therefore, using the above super-pixel segmentation method will result in under-segmentation (a super-pixel block contains a number of different categories of pixels) and over-segmentation (pixels of the same nature may be divided into different super-pixel blocks), which need to be refined, and the processing flow is shown in Fig. 1.

Figure 1.

Super-pixel refinement processing method.

The analysis is as follows:

(1) Firstly, the super-pixel is divided by the improved SLIC method in this paper, and the initial super-pixel set of the image is obtained. Then, the standard deviation $\sigma_{i}$ of each super-pixel block $P_{i}$ is calculated, super-pixel standard deviation is defined as:

$\displaystyle\sigma_{i}=\frac{1}{n_{1}}\left[\sum\nolimits_{k=1}^{n_{1}}d_{c}(% x_{k},v_{i})+\lambda\cdot\sum\nolimits_{k=1}^{N}d_{s}(x_{k},v_{i})\right]$ (10)

In Eq. (10), $k=1,2,\ldots,n_{1}$ , $x_{k}$ is the pixel in the super-pixel $P_{i}$ , $n_{1}$ is the number of pixels in the super-pixel, $v_{i}$ is the clustering center of the super-pixel $P_{i}$ and $d_{c}(x_{k}$ , $v_{i})$ and $d_{s}(x_{k},v_{i})$ are the colour and position distance between the pixel $k$ and clustering center $v_{i}$ Respectively, the calculation method is shown in the Eq. (3) and the Eq. (5), $\lambda$ same as Eq. (7), which is the weight coefficient.

(2) After obtaining the standard deviation of the super-pixel, compared with the pre-given threshold $\sigma$ of the standard deviation within the super-pixel, the standard deviation within a super-pixel is the mean square deviation between all pixels of the super-pixel. If the standard deviation of the super-pixel is greater than the threshold, the minimum circumscribed rectangle of the original super-pixel block is taken, on this basis, the SLIC method proposed in this paper is used to continue segmentation until all the super-pixel blocks are segmented, thus the problem of under-segmentation is solved.

(3) After the super-pixel segmentation is completed, the standard deviation $\Psi_{i}$ between the super pixel $P_{i}$ and other super-pixel blocks in the neighborhood is calculated, and compared with the preset standard deviation threshold $\Psi$ . The standard deviation between blocks is the mean square deviation between all super-pixel blocks. If the value is too small, the super-pixel $P_{i}$ considered to be close to an adjacent super-pixel in the neighborhood and is a pixel block of the same nature. At this time, the adjacent super-pixel $P_{i}$ , with the smallest difference between the super-pixel $P_{j}$ and its block is found and $P_{i}$ and $P_{j}$ are merged. As a result, the problem of super-pixel over-segmentation is solved.

The formula for calculating the standard deviation $\Psi_{i}$ between super-pixel blocks is:

$\displaystyle\psi_{i}=\mathop{\min}\limits_{P_{j}\in\text{NP}_{i}}[d_{c}(v_{i}% ,v_{j})+\lambda\cdot d_{s}(v_{i},v_{j})]$ (11)

In Eq. (11), NP ${}_{i}$ is the adjacent super-pixel set covering the super-pixel Pi in the neighbourhood of 2 $r$ $\times$ 2 $r$ , and the super-pixel $P_{j}$ is the adjacent super-pixel of $P_{i}$ , $v_{i}$ , $v_{j}$ are the clustering center of super-pixel $P_{i}$ and $P_{j}$ , respectively. The definition of $d_{c}(v_{i},v_{j})$ , $d_{s}(v_{i},v_{j})$ is consistent with the Eq. (10).

By analyzing the above steps, we can see that in the process of solving the problem of under- segmentation, there is a large difference between the noise pixel in the image and the clustering center of any super-pixel, and the noise will be “separated” from the initial super-pixel after many iterations. Similarly, in the process of solving the over-segmented merged super-pixel, the noise pixel is not merged, so this method not only eliminates the under-segmentation and over-segmentation in the primary super-pixel segmentation. And effectively separate the noise pixels in the image.

3. Super-pixel FCM clustering algorithm based on neighborhood constraint

In the previous section, we proposed the technique of SLIC super-pixel partition that combines FCM iterative clustering, and obtained fine super-pixels in the image. Because the super-pixels only segment the image in the neighborhood, they cannot classify the objects in the image from the angle of the whole image. In addition, it is difficult to suppress the noise far away from the local area. FCM algorithm can also achieve super-pixel classification from a global perspective. Therefore, based on the combination of super-pixel and traditional FCM clustering, this paper proposes an improved super-pixel FCM clustering algorithm based on neighborhood constraints, which aims to achieve super-pixel category marked in the whole image and suppress the influence of noise.

3.1 Location constraint of neighborhood spatial

From the super-pixel division method in Section 2, we can see that the super-pixel in the image not only has its own inherent color or gray scale characteristics, but also related to its location. For example, the super-pixels around another super-pixel is likely to constitute the same object in the image, that is, they are the same kind of super-pixel. While the super-pixel block far away from another the super-pixel is less likely to belong to the same class. Therefore, in the super-pixel classification and marking of the image, we should consider not only the information of the super-pixel itself, but also the position relationship among the super-pixels.

Let $x_{i}$ be the value of the super-pixel $P_{j}$ in a neighborhood window around the super-pixel $P_{i}$ , and $N_{i}$ is the super-pixel set in a neighborhood with the super-pixel $P_{i}$ as the center, then in the FCM clustering based on the super-pixel, the impact factor $G_{ki}$ of the neighbourhood super-pixel to the super-pixel $P_{i}$ is defined as:

$\displaystyle G_{ki}=\sum\nolimits_{r\in N_{i}}\frac{1}{d_{ir}+1}(1-u_{k_{r}})% ^{m}||x_{r}-v_{k}||^{2}$ (12)

While $d_{ir}$ is the Euclid of super-pixel $P_{r}$ and super-pixel $P_{i}$ , and its calculation method is the same as the previous distance calculation. $v_{k}$ is the $k$ -th cluster center of FCM clustering, $m$ is the fuzzy weighted index, and $u_{kr}$ is the membership degree of super-pixel $P_{r}$ and the $k$ -th cluster center.

Compared with the FCM_S1 and FCM_S2 proposed in reference [10] and the FGFCM method proposed in reference [19], Eq. (12) fuses the information of the super-pixel itself and its spatial location information. Through the use of $d_{ir}$ , the spatial location information makes the super-pixels in the neighborhood change flexibly according to their distance from the central super-pixel, that is, adaptive change, so that more local spatial information can be used. The information of super-pixel itself not only changes automatically according to the different gray difference of super-pixel in the neighborhood, but also depends on its membership value, so the value of impact factor $G_{ki}$ varies with different super-pixel.

In the improved FCM clustering (Section 3.2 will describe the FCM clustering after the introduction of factor $G_{ki}$ ), in the case of the same number of iterations, the introduction of impact factor $G_{ki}$ can retain more image detail information than using super-pixel direct clustering, the reason is that different super-pixels with different $G_{ki}$ , can also achieve a balance between suppressing noise and preserving image details through $G_{ki}$ . This balance is realized automatically by defining the fuzziness between the spatial information of each super-pixel and its own information, without using any additional parameters (the FCM_S1, FCM_S2 and FGFCM methods introduced subjective control parameters respectively), which reduces the subjectivity of the clustering process. Therefore, the introduction of factor $G_{ki}$ has great advantages in image clustering segmentation for suppress noise. Here we will analyze the implementation process of $G_{ki}$ factor in FCM clustering to suppress noise and preserve image details.

3.2 FCM clustering algorithm based on neighborhood constraints

Using the super-pixel impact factor $G_{ki}$ , we propose a new super-pixel FCM clustering algorithm based on neighborhood constraints, which combines the inherent information of the super-pixel itself and the spatial information of the neighborhood super-pixel, so that it retains more details and has high noise robustness in image segmentation. The objective function of the algorithm is defined as:

$\displaystyle J_{m}=\sum\nolimits_{i=1}^{s}{\sum\nolimits_{k=1}^{c}{u_{ki}^{m}% (||x_{i}-v_{k}||^{2}+G_{ki}}})$ (13)

Where $x_{i}$ is the information value of super-pixel $P_{i}$ itself, it consists of the values of the $l, a, b, x, y$ components, $v_{k}$ is the $k$ th clustering center, $c$ is the number of clusters, $s$ is the number of super-pixels in the image, and $u_{ki}$ is the membership degree of super-pixel $P_{i}$ relative to cluster $v_{k}$ . The Lagrange multiplier method is used to minimize the Eq. (13). After analysis and calculation, the fuzzy membership degree and clustering center are as follows:

$\displaystyle u_{ki}=\sum\nolimits_{j=1}^{c}\left(\frac{\left\|{x_{i}-v_{k}}% \right\|^{2}+G_{ki}}{\left\|{x_{i}-v_{j}}\right\|^{2}+G_{ji}}\right)^{1/1-m}$ (14) $\displaystyle v_{k}=\sum\nolimits_{i=1}^{n}{u_{ki}^{m}x_{i}}\left/\sum% \nolimits_{i=1}^{N}{u_{ki}^{m}}\right.$ (15)

The iterative execution process of the algorithm is as follows:

S1: set clustering number $c$ , fuzzy weighted index value $m$ (usually 2), iteration termination threshold $\theta$ , number of iterative execution cycles $t=$ 0. S2: randomly initialize the fuzzy partition matrix $U^{(t)}$ . S3: calculate the cluster center $v_{k}(t)$ according to the Eq. (15). S4: calculate the fuzzy membership degree $u_{ki}(t+1)$ according to the Eq. (14). S5: if $\left\|{U^{(t+1)}-U^{{}^{(t)}}}\right\|<\theta$ , stop the iteration, otherwise $t=t+1$ , return to S3 to continue execution. S6: after the iteration of the algorithm is terminated, classify of the super-pixel $P_{i}$ belongs is marked according to the principle of maximum membership degree.

Algorithm analysis:

It can be seen from the above algorithm description, the robustness of the algorithm to noise is mainly reflected in the neighborhood constraint impact factor $G_{ki}$ . As can be seen from Eq. (12), the size is automatically determined without introducing any new adjustment control parameters, so the calculation is simple. Even in the absence of any prior knowledge of noise, the noise super-pixels in the neighbourhood can be balanced, that is, after a certain number of adaptive iterations, in the neighbourhood center on the super-pixel $P_{i}$ , The membership degree of a noisy super-pixel to a cluster center is basically the same as that of a non- noisy super pixel to a cluster center. So as to restrain the influence of noise on clustering and realize the insensitivity of the algorithm to noise.

It specifically includes two cases. Firstly, suppose that in a neighborhood, the central super-pixel $P_{i}$ is non-noise super-pixel, and a certain other super-pixel $P_{r}$ in the neighborhood is a noise super-pixel. Because the gray value of the noise super-pixel is different from the central super-pixel $P_{i}$ , and the membership degree is small, according to the Eq. (12), it can be known that the $G_{ki}$ value of the super-pixel $P_{i}$ is small, and the membership degree $u_{ki}$ obtained by repeated iteration of the Eq. (14) is also small. Similarly, because the neighbourhood window where other super-pixels are located overlaps with the neighbourhood window, the membership values of other super-pixels in the neighbourhood window calculated by Eq. (14) are also decreasing, so that the membership degrees of all super pixels (including noise super pixels) in the neighbourhood are basically the same. Secondly, if the central super-pixel $P_{i}$ in neighborhood is noise, and the other super-pixel $P_{r}$ is non-noise super-pixel, it can be known from Eq. (12) that $u_{kr}$ is larger and $\left\|{x_{r}-v_{k}}\right\|$ value is smaller, so the value of $G_{ki}$ becomes smaller.

After repeated iterative calculation of Eq. (14), the membership degree $u_{ki}$ is also getting smaller, and because other super-pixel neighborhood window in the region are cross-covered, we can know from the first case, the membership $u_{kr}$ of these non-noise super-pixels is also decreasing in the iterative calculation process, and finally the balance is reached, that is, all the super-pixel $u_{ki}$ in the neighbourhood of the super-pixel $P_{i}$ is basically the same size. Through the above analysis, it can be concluded that the introduction of neighborhood super-pixel impact factor can effectively balance the noise in the image and improve the robustness of the clustering algorithm to noise.

4. Analysis of experimental results

In order to verify the effectiveness of the algorithm proposed in this paper, we use the Super-pixel Fast FCM clustering algorithm (SFFCM) based on morphological gradient reconstruction proposed in reference [3], the improved FCM algorithm based on local spatial information FCM_S1 and FCM_S2 proposed in reference [9] and literature [10], and the Deviation Sparse Fuzzy C-means clustering algorithm under Neighborhood(DSFCM_N) information constraints proposed in reference [4]. Among them, FCM_S1 and FCM_S2 first introduced neighborhood spatial information, which is a classical clustering and segmentation algorithm based on neighborhood information. SFFCM algorithm is a new algorithm based on super-pixel processing published on IEEE Transaction on Fuzzy System, the algorithm has sufficient theory and good application effect. DSFCM_N algorithm proposes to identify noise and outliers by applying sparsity to the deviation between measured values and theoretical values under the constraint of neighborhood information and the clustering accuracy is improved, the design of the algorithm is novel, and it has a great correlation with the algorithm proposed. So it is feasible to use these algorithms for experimental comparison. For the convenience of description, the super-pixel image segmentation algorithm based on neighborhood multi-level FCM clustering proposed in this paper is referred to as SN_FCM.

Experimental environment: CPU Intel(R) Core™ i7-6700@3.4GHZ, RAM 16G, Operating system: Windows 10, Programming environment: Matlab 2012a.

The parameters setting in the experiment are: FCM clustering fuzzy weighted index $m=$ 2, iteration termination threshold (the difference of membership between two adjacent iterations) $\theta=$ 10 ${}^{-5}$ , maximum number of iterations $T=$ 100, in SN_FCM algorithm, the threshold of standard deviation within and between super-pixel blocks given in Fig. 1 is $\sigma=$ 0.01, $\Psi=$ 0.1, weight parameter $\lambda$ is taken according to the actual situation, and in SFFCM algorithm, $\eta=$ 10 ${}^{-4}$ , it is used to determine the largest structural element $r_{2}$ and the value of minimum structural element $r_{1}$ is set 2. In algorithm FCM_S1 and FCM_S2 neighborhood influence control parameter $\alpha=$ 3, algorithm DSFCM_N, regularization vector $\beta=(\beta_{1},\beta_{2},\ldots,\beta_{l})$ is a very important parameter vector, which determines the deviation tolerance distance of each channel of the image, and its value should be determined according to different experimental image objects. The specific determination method refers to the formula (30) in reference [4], which is limited in space, there will not go into detail here.

Experimental data: we use two kinds of image data for experiments, the first is the artificial synthetic image with 40% salt and pepper noise, the second is the natural colour image set without noise. Because the first data set is a synthetic image set with simple colour and a large amount of noise, and the second natural image data set is not only rich in colour but also free of noise, these two data sets reflect the composition of image data from different sides. Experiments are carried out on these two data sets to verify the processing of noisy images by the proposed method It can better illustrate the effectiveness of the method proposed in this paper. Experimental evaluation indicators: there are three evaluation indicators in this experiment, segmentation accuracy (SA), similarity score (CS) and execution timeSA represents the percentage between the correct pixel obtained after segmentation and the real correct pixel; CS represents the percentage of pixels obtained after segmentation and total classified pixels (including correct and wrong). SA and CS are defined as follows:

$\displaystyle\text{SA}=\frac{\sum\nolimits_{i=1}^{c}{{|A}_{i}\cap{C}_{i}|}}{% \sum\nolimits_{j=1}^{c}{{|C}_{j}|}}$ (16) $\displaystyle\text{CS}=\sum\nolimits_{i=1}^{c}{\frac{|{A}_{i}\cap{C}_{i}|}{|{A% }_{i}\cup{C}_{i}|}}$ (17)

In the formula, $c$ is the number of clusters, $A_{i}$ represents the set of pixels belonging to class $i$ in the clustering experimental results, $C_{i}$ represents the set of pixels belonging to class $i$ in the standard segmentation results, and $\left|\ldots\right|$ represents the number of pixels in the set. It can be seen from the above formula that the higher the values of SA and CS, the better the clustering results.

Figure 2.

Super-pixel blocks of the synthetic color image.

4.1 Experiment 1. Synthetic color image

The synthetic color image is shown in Fig. 2a. The size of the image is 135 $\times$ 135 pixels and consists of five parts. After adding 40% salt and pepper noise (S-P noise), as shown in Fig. 2b, the pixels in the local area of the image are evenly distributed in this experiment, so the similarity calculation (Eq. (7)) weight parameter $\lambda=$ 1 is proposed in this paper. The super-pixel blocks obtained by using the super-pixel segmentation method proposed in Section 2.2 are shown in Fig. 2c and d, in which Fig. 2c are the super-pixel blocks corresponding to Fig. 2a, and Fig. 2d are the super-pixel blocks corresponding to Fig. 2b. Compared with Fig. 2c and Fig. 2d, it can be seen that the super-pixel blocks obtained from the noisy image except that the boundary division of the super-pixel blocks is not accurate, Other super-pixel blocks are almost consistent with those obtained from noise free images, which shows that the super-pixel partition algorithm proposed in this paper can suppress noise well. In addition, According to the above experimental environment and parameters, FCM_S1, FCM_S2, SFFCM, DSFCM_N and the SN_FCM five algorithm proposed in this paper are used to segment Fig. 2b and reconstruct it, and the images of reconstructed are shown in Fig. 3a–e. In order to quantitatively evaluate the performance of the algorithm, the average values of the evaluation indexes SA, CS and Time, are tested for 10 times, and the results are shown in Table 1.

Table 1
Evaluation index of 5 algorithms for synthetic image

	SA (%)	CS (%)	Time (s)
FCM_S1	72.1	60.5	1.60
FCM_S2	80.6	77.3	3.41
SFFCM	89.6	90.5	0.23
DSFCM_N	93.2	94.1	5.76
SN_FCM	93.4	94.4	1.64

Figure 3.

Synthetic color image.

From Fig. 3, we can see that among the five algorithms, the segmentation effect of FCM_S1 is the worst, DSFCM_N and SN_FCM are the best, there are little difference between them, they are close to the original Fig. 2a, and SN_FCM is more prominent to the details of image reconstruction, and the boundary of each component object is smoother. At the same time, by analyzing the evaluation indexes in Table 1, it can be concluded that SN_FCM has the largest segmentation SA and CS, followed by DSFCM_N, and has little difference from the SN_FCM, and FCM_S1 is the worst. This is because although FCM_S1 has introduced the spatial influence adjustment parameter “a”, but the parameter value is given subjectively, and FCM_S2 has improved on the basis of FCM_S1, so the segmentation effect of FCM_S2 is better than that of FCM_S1. SFFCM combines super-pixel information and morphological techniques, so it has high segmentation accuracy in image segmentation.

However, in the morphology-based MMGR-WT algorithm, the minimum value of structural elements $r_{1}$ needs to be given through experiments, which has no theoretical basis, and its maximum value $r_{2}$ is given by threshold $\eta$ , so the algorithm still has some shortcomings. The DSFCM_N is considered that under the condition of neighborhood information constraints, clustering is carried out by introducing a deviation matrix E between the measured values and theoretical values of the data, that is, not only the data itself but also the measured data deviation has be taken into account in the clustering process, so that the clustering result is more accurate. The SN_FCM in this paper uses two-level FCM clustering when segmenting the image, which is to refine the super-pixel of the image, and it also takes into account the interaction between super-pixels, so not only the details are prominent, but also the segmentation effect is good and the accuracy is high.

In addition, in terms of execution time, DSFCM_N not only calculates the membership degree and clustering center, but also repeatedly calculates the deviation of the data $e_{jq}$ . The calculation of deviation takes a lot of time, so the algorithm takes a long time to execute. The adjustment of spatial parameter in FCM_S2 needs repeated calculation to get the best value, and the iterative time of clustering is long. The SN_FCM which proposed in this paper has to decompose and merge repeatedly when dividing super-pixels, but in the process of clustering, the number of super-pixel blocks is much less than the real pixels of the image, so the execution time is less than DSFCM_N and FCM_S2, but a little more than SFFCM and FCM_S1.

4.2 Experiment 2. Pascal VOC 2012 natural image dataset

In order to further verify the effectiveness of the algorithm, this experiment selects the Pascal VOC 2012 natural image dataset, which is commonly used to test the classification in the field of artificial intelligence. It contains 4 categories and 20 kinds of natural and scene images without artificial noise, such as airplane, bicycle, bird, bus, bed, cat, chair, cow, dog, sheep, etc. At present, the capacity of the Pascal VOC 2012 dataset has exceeded 12000 images. And it is being updated and expanded every year. Pascal VOC 2012 dataset has become a standard dataset for measuring the performance of computer vision algorithm [21]. The scene images of some Pascal VOC 2012 dataset are shown in Fig. 4.

Figure 4.

Pascal VOC 2012 dataset partial scene images.

Figure 5.

Super pixel blocks of the image corresponding to Fig. 4.

In the experiment, we select seven images (cat, horse, plane, car, motorcycle, TV, living room) from the Pascal VOC 2012 dataset. In this experiment, considering that the color information of pixels is a little more important than the position information, so colour weight parameter $\lambda=$ 0.75 of similarity calculation in SN_FCM. Firstly, we use the super-pixel segmentation method proposed in Section 2.2 to segment the images in Fig. 4 to obtain the corresponding super-pixel blocks, as shown in Fig. 5. For further comparison, the results of 7 images based on SN_FCM proposed in this paper are shown in Fig. 6, with a total of 7 groups of images. The first image of each group is the original image, the pixel block of the second image is the target object block obtained after standard segmentation, and the pixel block of the third image is the super-pixel block segmented by SN_FCM algorithm proposed in this paper. From the segmentation results, we can find that the algorithm proposed in this paper can better realize image segmentation At the same time, in order to further verify the experimental effect, same as the previous experiment, we use FCM_S1, FCM_S2, SFFCM, DSFCM and SN_FCM for image segmentation and reconstruction experiments.in order to make the experimental result more objective and to facilitate comparison, for each algorithm, the experimental result of each of the 7 images are averaged after 10 experiments, and then the average values of the experimental results of the 7 images are calculated as the final experimental data, and the average SA, CS and time values of each algorithm for the 7 images are obtained, as shown in Table 2. The actual intuitive effect images after each image segmentation and reconstruction by each algorithm is no longer listed here because of the space.

Table 2

The evaluation index values of 5 algorithms in natural image

	SA (%)	CS (%)	Time (s)
FCM_S1	87.1	87.6	0.43
FCM_S2	94.2	94.1	0.82
SFFCM	94.5	94.3	0.34
DSFCM_N	95.1	94.5	2.68
SN_FCM	95.0	94.4	0.90

Figure 6.

Image segmentation comparison of the SN_FCM algorithm proposed in this paper.

The analysis of the data in Table 2 shows that for the natural color image processing without noise, except for the algorithm FCM_S1, the other four algorithms have high accuracy and similarity. Although the SN_FCM has achieved better accuracy and similarity, but comparing with other algorithms, such as DSFCM_N, its value of SA and CS is not significantly improved, and even slightly lower than the DSFCM_N. It shows that this algorithm has no obvious advantage in dealing with images without noise, but compared with experiment 1, this algorithm has great advantage in image processing with noise, so as to further verify the robustness of the algorithm to noise. Similarly, in the comparison of the execution time of the five algorithms, the execution time of the DSFCM_N algorithm is much longer than that of the other four algorithms. The execution time of the SN_FCM is relatively long, but within the tolerable range, and much shorter than that of the DSFCM_N algorithm.

5. Conclusion

In this paper, an image super-pixel partition algorithm is given based on SLIC and FCM iterative clustering, and then a neighborhood constrained super-pixel FCM clustering impact factor is designed by combining the information of super-pixel itself and the spatial information of neighborhood super-pixel. Over this, an improved super-pixel FCM clustering algorithm based on neighborhood constraint is proposed. Theoretical analysis and experiments show that the algorithm proposed in this paper achieves good result in image clustering segmentation. Especially for the processing of images with a lot of noise, it has high accuracy and similarity.

The main contributions of this paper are as follows: one is to design a SLIC super-pixel fine partition method based on FCM, and the other is to propose a super-pixel FCM clustering algorithm based on neighborhood spatial impact factor $G_{ir}$ , which further improves the accuracy of image segmentation. However, because this algorithm needs a large number of intra-block decomposition and inter-block merging calculations when obtaining super-pixels, and repeated iteration in clustering segmentation, the execution time of the algorithm is relatively long. How to further improve the time efficiency of the algorithm without changing the execution environment of the algorithm will be the research goal of the next step.

Footnotes

Acknowledgments

Yu Yang (1986.3-), Female, Master, Deputy senior engineer, Maoming Guangdong, Major in Big data technology and Application; Corresponding author: Zhicheng Wen(1972-), male, Dong’an county, Hunan province, Han, Ph.D., professor, China, E-mail: zcwen@mail.shu.edu.cn.

This paper supported by the Industrial Support Project of Xinyu Science and Technology Bureau, Jiangxi Province: Research on Reliability Control Technology for Train Communication Network Transmission System (2019).

References

Tao

Xiao

Xiaohong

, et al. Research progress on image segmentation based on fuzzy clustering. Acta Electronica Sinica. 2019; 47(8): 1776-1791. doi: 10.3969/j.issn.0372-2112.2019.08.023.

Guo

Wang

Shen

. Adaptive fuzzy c-means algorithm based on local noise detecting for image segmentation. IET Image Process. 2016; 10(4): 272-279. doi: 10.1049/iet-ipr.2015.0236.

Tao

Xiaohong

Yanning

, et al. Super-pixel based fast fuzzy c-means clustering for colour image segmentation. IEEE Transaction on Fuzzy Systems. 2019; 27(9): 1753-1766. doi: 10.1109/TFUZZ.2018.2889018.

Yuxuan

Xiangzhi

Ruirui

, et al. Deviation sparse fuzzy c-means with neighbour information constraint, IEEE Transactions on Fuzzy systems. 2019; 27(1): 185-199. doi: 10.1109/TFUZZ.2018.2883033.

Weifeng

Jinbao

Ying

. A novel fuzzy clustering algorithm based on similarity of attribute space. Journal of Electronics and Information Technology. 2019; 41(11): 2722-2728.

Hang

Zehua

Lyu

, et al. A global optimization fuzzy clustering algorithm based on tabu search. Acta Electronica Sinica. 2019; 47(2): 289-295.

Chaturvedi

Patel

Swami

. Fuzzy c-means based inference mechanism for association rule mining. International Journal of Advanced Computer Science and Applications. 2015; 6(6): 103-110. doi: 10.14569/IJACSA.

Yukihiro

Yasunori

. On semi-supervised fuzzy c-means clustering for data with cluster wise tolerance by opposite criteria. Soft Computing-A Fusion of Foundations, Methodologies & Applications. 2013; 17(1): 71-81.

Songcan

Daoqiang

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

10.

Weiling

Songcan

Daoqiang

. Fast and robust fuzzy c-means clustering algorithms incorporating local information for image segmentation. Pattern Recognition. 2007; 40(3): 825-838. doi: 10.1016/j.patcog.2006.07.011.

11.

Krinidis

Chatzis

. A robust fuzzy local information C-means clustering algorithm. IEEE Transaction on Image Process. 2010; 19(5): 1328-1337. doi: 10.1109/TIP.2010.2040763.

12.

Gong

Liang

Shi

, et al. Fuzzy c-means clustering with local information and kernel metric for image segmentation. IEEE Transaction on Image Process. 2013; 22(2): 573-584.

13.

Zhang

Wang

Shi

Hao

. A novel adaptive fuzzy local information c-means clustering algorithm for remotely sensed imagery classification. IEEE Transaction on Geoscience Remote Sense. 2017; 55(9): 5057-5068. doi: 10.1109/TGRS.2017.2702061.

14.

Jiao

Yang

, et al. Fuzzy double c-means clustering based on sparse self-representation. IEEE Transactions on Fuzzy Systems. 2018; 26(2): 612-626. doi: 10.1109/TFUZZ.2017.2686804.

15.

Mansheng

Zhe

Zhicheng

, et al. Improved FCM clustering algorithm based on spatial correlation and membership smoothing. Journal of Electronics and Information Technology. 2017; 39(5): 1123-1129. doi: 10.11999/JEIT160710.

16.

Memon

Lee

. Generalised kernel weighted fuzzy c-means clustering algorithm with local information. IET Image Processing. 2017; 11(1): 1-12.

17.

Tao

Xiaohong

Yanning

, et al. Significantly fast and robust fuzzy c-means clustering algorithm based on morphological reconstruction and membership filtering. IEEE Transaction on Fuzzy Systems. 2018; 26(5): 3027-3041. doi: 10.1109/TFUZZ.2018.2796074.

18.

Szilagyil

Benyo

Szilagyi

, et al. MR brain image segmentation using an enhanced fuzzy c-means algorithm, 25th Proceedings of the Annual International Conference of the IEEE Engineering in Medicine and Biology SocietyMX. IEEE, 2003.

19.

Weiling

, SongeanC, DaoqiangZ. Fast and robust fuzzy c-means clustering algorithms incorporating local information for image segmentation. Pattern Recognition. 2007; 40(3): 825-838.

20.

Achanta

Shaji

Smith

, et al. SLIC super-pixels compared to state-of-the-art super-pixel methods. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2012; 34(11): 2274-2282.

21.

Everingham

Eslami

Vangool

Williams

Winn

Zisserman

. The Pascal Visual Object Classes Challenge. International Journal of Computer Vision. 2015; 111(1): 98-136.

Image segmentation based on super-pixel with neighborhood constrained and multi-level FCM clustering

Abstract

Keywords

1. Introduction

2. Super-pixel segmentation based on FCM improved SLIC algorithm

2.1 Algorithm description

3.1 Location constraint of neighborhood spatial

Table 1 Evaluation index of 5 algorithms for synthetic image

Footnotes

Acknowledgments

References

Table 1
Evaluation index of 5 algorithms for synthetic image