Zhe Liu , Bao Xiang , Yuqing Song Hu Lu and Qingfeng Liu

Abstract: Most image segmentation methods based on clustering algorithms use singleobjective function to implement image segmentation. To avoid the defect, this paper proposes a new image segmentation method based on a multi-objective particle swarm optimization (PSO) clustering algorithm. This unsupervised algorithm not only offers a new similarity computing approach based on electromagnetic forces, but also obtains the proper number of clusters which is determined by scale-space theory. It is experimentally demonstrated that the applicability and effectiveness of the proposed multi-objective PSO clustering algorithm

Keywords: Multi-objective optimization, particle swarm optimization, electromagnetic forces, scale-space theory.

1 Introduction

Image segmentation is the division of an image into several non-overlapping areas containing pixels with identical or similar attributes [Ponttuset, Arbelaez, Barron et al(2017)]. Image segmentation is an important aspect of image processing and determines the final results and quality of image analysis. Clustering-based image segmentation methods have been widely used [Choy, Shu, Yu et al (2017); Chen, Li, Bo (2017); Yang,Chung, Wang (2009)]. A clustering method uses the feature information of the image pixels to segment the image by merging pixels with identical or similar features into one group based on the similarity measure.

Merwe et al. [Merwe and Engelbrecht (2004)] first proposed PSO for data clustering.Xiao et al. [Xiao (2003)] hybridized PSO with Self-Organizing Maps (SOM) to use SOM to cluster the data and PSO to optimize weights of the SOM. Lin et al. [Lin, Tong, Shi et al. (2014)] used the results of K-means in combination with PSO and multiclass merging to perform data clustering. Omran et al. [Omran, Salman and Engelbrecht (2006)]suggested a dynamic clustering algorithm based on PSO and K-means for image segmentation. Fornarelli [Fornarelli (2017)] used an unsupervised multi-particle clustering method for image segmentation; this method conducts a spatial search based on the minimum distance criterion and then uses the same group structure to improve the results for image segmentation. Benaichouche et al. [Benaichouche, Oulhadj and Siarry(2013)] proposed an improved method of fuzzy C-means (FCM) clustering that introduces the heuristic PSO algorithm in the initial stage to overcome local minima; the local information and Mahalanobis distance are taken into account in the classification criteria, and a greedy algorithm is used to optimize the local standard and detect potential pixel misclassification. Nanda et al. [Nanda and Panda (2013)] presented a multiobjective immune PSO algorithm according to the Pareto archive of unsupervised problems based on the recently proposed hybrid evolutionary immune PSO algorithm;this multi-objective immune PSO algorithm can perform clustering automatically and optimize two objective functions simultaneously.

This paper proposes a new two objective functions calculation methods based on different evaluations of the effectiveness of PSO clustering performance which includes the particle trajectory and speed in the global optimization. Two objective functions are used to avoid the defects of single objective function evaluation criterion in the traditional clustering algorithm. Furthermore, the optimal clustering number is determined by space-scale theory. An unsupervised image segmentation based on a multi-objective PSO clustering algorithm (UISMOPC) is proposed in this paper, and experimental data from University of California, Berkeley are applied to evaluate the algorithm.

2 Unsupervised image segmentation based on a multi-objective PSO clustering algorithm (UISMOPC)

2.1 Determination of the clustering number based on scale-space theory

UISMOPC is an unsupervised clustering algorithm, so it is of great significance that the clustering number needs to be determined in advance. So the scale-space theory [Babaud,Witkin, Baudin et al. (1986)] is applied to obtain the proper clustering number.

We define that the scale space image of a continuous signalas follows:

where * represents convolution. We take the Gaussian functionas:

Then

Figure 1: Fingerprints of a normal probability density function

2.2 Similarity measure and multi-objective function

Considering the similarity measures discussed above, we present two different objective functions based on the criteria of minimizing the within-class similarity and maximizing the similarity between clusters. The first objective functionconcerning the intra-class precision and the second objective functionconcerning the inter-class incoherence is defined as follows,is the sum of the similarity betweenand the cluster to which it belongs. A smaller value ofindicates superior clustering results.is sum of the similarity betweenand other clusters, excluding the one to which it belongs. A smaller value ofindicates better clustering results. It is obvious that we need to minimizeandsimultaneously. It is apparent that the sum ofandequals the sum of the similarity of eachto all clusters, and thus the equationis true. Then,the clustering problem is transformed to a multi-objective optimization of calculating

2.3 Multi-objective optimization based on Pareto optimal

The multi-objective clustering method is the unsupervised division of the dataset based on the constraints of multiple objective functions simultaneously. The multi-objective particle swarm guides the particles’ velocity and position by multiple objective functions,and thus the best particles eventually fall within the scope of the Pareto set. This method uses the idea of external archive of Pareto Optimal introduced in the MOPSO algorithm[Coello, Pulido, Lechuga et al. (2004)]. A multi-objective optimization problem optimizes two or more target objects simultaneously and can be illustrated as follows:

Table 1: Flowchart of UISMOPC

In the UISMOPC algorithm, f1 and f2 are the itness functions of Multi-objective PSO algorithm, and they can be calculated by formula (5) and (6), ggbest is a global search variable that ensures information exchange between each particle and the other particles in the swarm. ggbest drives the particle to the best position in the whole swarm based on social knowledge and overcomes the traditional drawbacks of the clustering algorithm,which is sensitive to the initial values and can easily fall into local optima. The linear transformation of w along with the change in the iteration adjusts the overall ability of the algorithm and avoids its premature convergence.

3 Experimental results and analysis

To evaluate the unsupervised image segmentation algorithm based on multi-objective PSO (UISMOPC), a comparison analysis using K-means [Niknam (2010)], FCM[Kannan, Ramathilagam and Chung (2012)], PSO-K-means [Niknam and Amiri (2010)]and PSO-FCM [Liu, Pei, Zhou et al. (2008)] methods was performed. We used a graphic dedicated workstation by Dell with an Intel Core i5 processor CPU, 1.6 GHz speed, 4 Gb memory, 500 Gb hard disk, and matlab2010 as the experimental software. The performance of the proposed algorithm was evaluated using 300 images from the Berkeley Segmentation Dataset and Benchmark (BSDB) [Fowlkes, Martin, and Malik(2013)]. The clustering numbers are obtained based on scale-space theory. Some selected results are presented here.

3.1 Evaluation method

Both supervised and unsupervised objective evaluation methods can be used to describe the results of image segmentation quantitatively. The supervised evaluation method requires the standard image as a precondition; this image is not easy to obtain, and thus the unsupervised evaluation method is accepted [Zhang, Jason, Fritts et al. (2008)]. The unsupervised evaluation method is the measure of the segmentation results by a set of parameter measurements and does not require a standard image in the evaluation process.We used intra-region uniformity metrics and inter-region disparity metrics to demonstrate the effectiveness and rationality of the method proposed in this paper.

Intra-region uniformity metrics are an intuitive and effective way to evaluate segmentation performance by measuring intra-region uniformity. The image segmentation quality evaluation criterion [Zhang, Jason, Fritts et al. (2008)] is as follows:

where I is the segmentation results of the image;is the size of the image; R is the number of categories in the image segmentation; Aiis the area of the i-th region, that is,the total number of pixels; and eiis the average color error number of the i-th region, A smaller F value indicates improved segmentation.

3.2 Experimental results using real data

The experimental data were obtained from the University of California, Berkeley, BSDB standard test image database. We compare the K-means, FCM, PSO-K-means, PSO-FCM and UISMOPC image segmentation in this paper. The clustering numbers of the original images shown in Fig. 2 are obtained by scale-space theory discussed in Chapter 2.1, the clustering number can be obtained, it can be shown that the number is 3,3,4,4,6,5,4,4 respectively. The 8 original test images are shown in the first line of Fig. 3, the results using the K-means, FCM, PSO-K-means, PSO-FCM-means and the proposed UISMOPC method are shown in the 2-6 line respectively.

To quantitatively evaluate the segmentation results of the algorithms, we used the F value and FRCas the evaluating indicators to compare the segmentation results of several classic clustering methods and the proposed segmentation method. Tab. 2 presents the FRCvalues of eight different images using five segmentation methods. The abscissa represents the images, and the ordinate represents the evaluation criteria of the segmentation quality.

Figure 2: Fingerprints of gray level density

Figure 3: Segmentation results of 8 test images

The results in Tab. 2 indicate that the image segmentation results of the PSO-K-means and PSO-FCM methods are superior to those of the K-means and FCM methods. The FRCvalue is higher for the proposed UISMOPC algorithm than the other four segmentation methods. The segmentation result of the proposed method is superior to those of the other image segmentation methods from the perspective of regional coherence.

Table 2: values of the segmentation results

Table 2: values of the segmentation results

#A(0) #B(0) #C(0) #D(0) #E(0) #F(0) #G(0) #H(0)K-means 0.7071 1.193 1.1176 1.8623 2.0787 1.3647 1.4584 1.5371 FCM 0.6008 1.1396 0.9219 1.7785 2.0964 1.1684 1.6282 1.0197 PSO-K-means 0.8196 1.2161 1.101 2.2772 2.3625 1.8108 1.9622 1.8412 PSO-FCM 0.7283 1.2144 1.0595 2.2255 2.0889 1.3836 1.6484 1.546 UISMOPC 0.8913 1.2756 1.2319 2.3104 2.5387 1.8975 2.1223 1.9174

Figure 4: Comparison of the F values of our UISMOPC method and the other four algorithms

Fig. 4 presents the different F values of the different segmentation methods. We selected formula (9) as the indicator to evaluate image segmentation results. Fig. 4 presents the F values of several images using the five segmentation methods. The abscissa represents different images, and the ordinate represents the F value evaluation criterion. As shown in Fig. 4, the F values of the PSO-K-means algorithm and PSO-FCM segmentation methods are smaller than those of the K-means and FCM methods; the latter two methods are over-dependent on the initial value in the image segmentation. The PSO-K-means and PSO-FCM methods incorporate the PSO algorithm to obtain more accurate clustering centers and, consequently, superior segmentation quality compared to the traditional division of the K-means and FCM methods. The F value of the proposed UISMOPC algorithm is smaller than those of the other methods because the PSO-K-means and PSOFCM segmentation methods divide the image data using one objective function, whereas the UISMOPC image segmentation method is based on multiple objective functions and consequently produces superior segmentation quality

Using the two evaluation indexes, we appraised the results in terms of intra-class precision and inter-class incoherence. The proposed image segmentation method based on the UISMOPC algorithm is superior to the traditional K-means, FCM segmentation and clustering algorithms based on single objective functions.

4 Conclusions

In this paper, we proposed an unsupervised image segmentation method based on a multiobjective PSO clustering algorithm by defining two different objective functions. The experimental results demonstrated that the clustering effectiveness was further improved by multi-objective optimization compared to other methods. As an unsupervised algorithm, UISMOPC not only proposes new fitness functions which illustrates the similarities between each cluster but also uses the idea of external archive of Pareto Optimal, so that the best particles can be obtained within a scope to make the algorithm much more robust. Furthermore, the determination of clustering number proposed by scale-space theory can help us to obtain more accurate number for those clustering-based methods. We will focus on transforming the clustering problem and multi-objective optimization more reasonably in the future.

Acknowledgement:This work was supported by the National Natural Science Foundation of China (Nos. 61772242, 61402204, 61572239), Research Fund for Advanced Talents of Jiangsu University (No. 14JDG141), Science and Technology Project of Zhenjiang City (No. SH20140110); Special Software Development Foundation of Zhenjiang City (No. 201322); Science and Technology Support Foundation of Zhenjiang City (Industrial) (No. GY2014013).