Abstract- A distributed, collective, ant based approach is presented for solving the segmentation problem. The algorithm utilizes the self-organizing and autonomous brood sorting behavior observed in real ants. Ants form homogeneous clusters by simply moving pixels according to a local similarity function using simple rules. The initial knowledge of the number of clusters and initial partition are not needed during the clustering process. This novel algorithm extracts correct number of clusters with good clustering quality compared to the classical Kmeans algorithm.

Index Terms — ACO, Image segmentation, agent clustering, swarm intelligence, ants.

1. INTRODUCTION

In the field of Computer Vision, image segmentation plays a crucial role as a preliminary step for high level image processing. To understand an image, one needs to isolate the objects in it and find relation among them. The process of separation of objects is referred as image segmentation. In other words, segmentation is used to extract the meaningful objects from the image.

Image segmentation plays an essential role in the interpretation of various kinds of images. Image segmentation techniques can be grouped into several categories such as edge-based segmentation, region- oriented segmentation, histogram thresholding, and clustering algorithms. The aim of a clustering algorithm is to aggregate data into groups such that the data in each group share similar features while the data clusters are being distinct from each other. The K-means algorithm is a widely used method used for finding the structure of data. This unsupervised clustering technique has a strong tendency to get stuck into local minima when finding an optimal solution.

Therefore, clustering results are heavily dependent on the initial cluster centers distribution. Hence, the search for good initial parameters is a challenging issue and the clustering algorithms require a great deal of experimentation to determine the input parameters for the optimal or suboptimal clustering results.

Swarm intelligence approach in solving complicated optimization problems is relatively new.

The main advantage of swarm intelligence approach is that system of simple communicating agents is capable of solving complex problems.

Ant Colony Optimization (ACO) being a branch of swarm intelligence is here considered. Several papers have highlighted the efficiency of approaches inspired from the nature [2]. In particular a variety of algorithms inspired from the swarm intelligence observed from the ants‘behaviors such food hunting and nest building have been introduced for solving several combinatorial optimization problems. In this respect ant algorithms have been recently emerged. In this field we found the Ant Colony Optimization (ACO) inspired from the foraging behavior of ant colonies and the ant based clustering algorithms based on the cemetery organization and brood sorting of ants[6]. Cemetery building is obtained when ants clean their nests and form piles by collecting corpses found within the nest. Brood sorting is widespread in ant colonies. Ants gather their larvae together according to the larva’s size. The basic principle of this sorting behavior is attraction between the items transported by the ant. Small clusters of similar items grow by attracting ants to deposit more items according to their type or their size. This positive feedback leads to formation of homogeneous clusters [1].

We propose in this study a new ant-based clustering algorithm for image segmentation. In this algorithm, ants represent the simple agents that randomly move on a discrete array. Pixels that are scatted within the cells of the array can be moved from one cell to another to form clusters. The pixels’ movement is implemented indirectly through the ants’ movement. Each ant can picks up or drop a pixel according to a similarity function which measures the pixel’ similarity with other pixels in a cluster. In this way, ants dynamically cluster pixels into distinctive independent groups within which similar pixels are closely placed in the same cluster. As we will see in the following, Agent introduced new probabilistic rules for picking up or dropping pixels and also a local movement strategy is used to speed up the clustering convergence. Experimental results show that Agent algorithm gives better clustering quality compared to those obtained from Kmeans algorithm.

2. AGENT CLUSTERING ALGORITHM

This is a distributed algorithm that uses positive feedback to achieve the clustering of pixels. It is mainly based on the versions described in [4] and [1]. A number of slight modifications have been introduced that improve the quality of the clustering and to speed up of the convergence. In both LF and Agent algorithms, the ants evolve on the discrete 2D board. The size of this grid should be selected in dependence of the data collection, as it otherwise impairs convergence speed. If the size is too small, the ants carrying data items will make everlasting move since they will never find an empty case to drop down them. This will consume large amount of computational time. Otherwise, if the size of the grid is too large, ants will make idle movement when no carrying data items before encountering an item data. As far as we know these is not theoretical guideline to determine automatically the size of the board. For this reason, we replace the rectangular grid by a discrete array of N cells when N is the total number of pixels to be clustered. All cells of the array are connected to the nest of the ants’ colony in order to let the ants travel from one cell to another easily. During the algorithm ants are able to create, build or destroy existing clusters of pixels. A cluster is defined as a collection of two or more pixels. As in [2], a cluster is spatially located in a single cell, which makes the identification of clusters easily unlike in the LF algorithm where spatial patterns of objects car touch each other.

Initially the N pixels {P1,…Pn} to be clustered are

placed on the array such that each array cell can only occupied by one pixel. Each ant ai from a colony of K

ants { a 1,....,a k} picks up a randomly chosen pixel

from its cell and returns to his nest. After this initialization phase, the clustering phase starts. During an iterative process, one ant is selected randomly; it performs a number of movements between its nest and the array and decides with a probabilistic rule whether or not to drop its pixel. If the ant becomes free, it searches for a new pixel to pick up. The ant has knowledge of a list of the locations of all pixels not being carried by other ants. The ant randomly selects a pixel from this list of “free” pixels and probabilistically decides whether or not to pick up that pixel. This process is repeated for all ants. The stopping criterion of the algorithm is the number of iteration fixed by the user at the beginning. The algorithm works as follows: On the array, each ant ai may possibly picks up a pixel pi from a cell ck or drop it in the cell ck according to the similarity function f, which represents the average distance between the pixel pi and others pixels pj in the cell ck. It is used to determine when pixel pi should leave from others pixels. The similarity function is defined by:

Where d (Pi, Pj) is determined by the contrast between two pixels pi and pj in terms of gray level and is defined

NG is the number of the gray levels in the image. a represents the mean distance between all pixels and is defined by:

The value of a can be calculated before the clustering process. The function f (.) gives its maximum response when d (pi, pj) tends to 0.

In the following, we will explain in detail the heuristic and the exact mechanism for picking and dropping a pixel.

2.1 Picking up a pixel:

When the ant is not carrying any pixel, it searches for a possible pixel to pick up. This search is guide by an index table that contains all free pixels (not transported by the ants). This index table is function of the similarity between the gray level of the pixel and the center of the cluster where it is located, such that the most dissimilar pixels, which are the most farthest from the center of theirs clusters, are in the top of the index table. Three cases have to be considered: if the considered pixel pi is alone in its cell ck , if it has one pixel with it in the same cell and if there is some others pixels with it in the cell. In the first case, the ant picks up it automatically. In the second case, we have an invalid cluster with only two pixels; the ant will destroy this cluster by picking up the considered pixel with a probability q. In the third case, the ant has a high probability to pick up the pixel if its similarity with all the pixels in the cluster is too low (tend to 0). For picking decision the following probability Ppickup (Pi, Ck) is used:

2.2 Dropping a pixel:

Once an ant has picks up a pixel pi, it returns with it to the nest then it looks for an interesting new cell where it will drop it. For this purpose a modified version of the short-term memory introduced in[4] and[1] is used. Ants remember a small number of pixels that it has picked up and the cells where it has successfully dropped them. And so, when the ant is carrying a pixel, its memory is consulted in order to select a cell on which it could drop the pixel. It then evaluates locally the suitability of each of the memorized cells as dropping cell for the current carried pixel. For this, the similarity function f is applied

to each cell and the best interesting cell ck is the one, at which the similarity function yields the higher value. Instead of just biasing the ants’ random walk as in [8] and [2], the ant directly moves from the nest to this cell. The decision whether to drop the pixel is taken probabilistically. The probability Pdrop (Pi, Ck) for dropping the pixel is given by:

Pdrop (Pi, Ck) = 1 – cos2 [ ∏/2 f (Pi, Ck) ]

3. EXPERIMENTAL RESULTS

The Agent Clustering algorithm was tested on synthetic and real images presented in Fig. 1 and 2. Synthetic images are used because the correct classification and the exact number of classes are known in advance. We can evaluate the ability of the ant-clustering algorithm to find the correct number of clusters. Moreover, we can evaluate the partition computed by Agent with the known correct partition.

Table 1 resumes the characteristic of each image like the number of clusters (K), the number of the gray levels (NG). The optimal range of the number of clusters for real images are taken from [5].

Table2 summarized all ants setting used in our experimentations for all test images. Theses setting were selected because they gave good results in preliminary tests.

Synthetic Image1

Synthetic Image 2

Fig. 1: Synthetic test images

Lenna

Peppers

Fig. 2: Real test images

TABLE 1: CHARACTERISTICS OF TEST IMAGES

Images	K	NG
Synthetic Image 1	3	46
Synthetic Image 2	6	117
Lenna	[5,10]	52
Peppers	[6,10]	54

TABLE 2: VALUES OF THE PARAMETERS OF AGENT

Parameter	Value
Number of ants K	20
q	0.7

The quality of the clustering obtained by Agent is compared to a classical clustering algorithm; the well- known Kmeans Algorithm. For this purpose, we initialize k means with N (number of pixels), 20 and 100 clusters. Starting from a random partitioning, the algorithm repeatedly computed the centers of the clusters and reassigns each pixel to the cluster, which the center is closer to it in term of gray levels.

Figure 1 shows the synthetic images. In Synthetic image 1, it is clearly visible that there are 3 objects. Table of synthetic image 1, clearly illustrates the capability of Agent (indicating value 3.08), correctly identify these objects.

Similarly for synthetic image 2 , it is visible that there are 6 objects. Agent (indicating value 6 ), correctly identifies these objects.

In order to formally evaluate the quality of the clustering obtained from the two algorithms Agent and Kmeans on the test images. We used the Rand index [6] and the Rosenberger’s measure [6]. The first of the two measures make use of the correct clustering which is known only for synthetic images. They are defined as follows:

3.1 The rand index R:
It determines the degree of pixels (in term of pair wise co-assignments) that are correctly classified according to a segmented image Seg and the reference image Re. as:

where a,b,c and d are parameters computed for each couples of pixels pi and pj as following: if C ref (i), C ref (j),

C seg (i)and C seg (j)are the labels of clusters of Pi and Pj in reference image and the segmented one, we have

R takes its value in the interval [0,1] and is to be maximized.

3.2 The Rosenberger’s measure:

It combined intra-cluster and inter-cluster disparities. It is defined by the following equation:

The global intra-region disparity D’ quantifies the homogeneity of each class in the segmented image (seg) is defined as:

Where NC is the number of clusters, ng(pi) is the gray level of the pixel pi Similarly, the global inter-classes disparity D measures the disparity between the classes.

It is given by:

Where qk is the number of clusters cj that are neighborhood of the cluster ck . The disparity between two clusters is defined by the following equation:

Where Ci is the centroid of cluster Ci and NG is the total gray levels present in the image to be segmented. A good clustering minimized the Rosenberger’s measure.

Tables 3 gives the means and standard deviation over 50 runs obtained for each of the two measures from the two clustering algorithms on synthetic and real images. Additionally, it gives the average number of clusters. The

Agent algorithm was simulated during 4500 iterations and the number of iterations of the Kmeans algorithm was set to 10. As can be seen, Agent algorithm outperforms the three versions of the Kmeans algorithm; both in terms of correct number of clusters, of Rand index and of Rosenberg’s measure. In general the kmeans algorithm over estimated the number of clusters which tends to be equal to the number of the gray levels present in the image to be segmented when the number of clusters gives to the algorithm is two high.

Table 3: Results for k-means and Agent algorithms on synthetic and real

Synthetic	N-	20-	100-	Agent
Image1	Kmeans	Kmeans	Kmeans
No.of	46	6	22	3.08
clusters
	(0)	(0)	(0)	(0.284)
R	0.7342	0,9580	0,7754	0,9897
	(0)	(0)	(0)	(0,433)
Ros	0.4888	0.3400	0,.4663	0.05082
	(0)	(0)	(0)	(1.729)

images. The table shows means and standard deviations (in brackets) for

Synthetic	N-	20-	100-	Agent
Image2	Kmeans	Kmeans	Kmeans
No.of	117	10	99	6
clusters
	(0)	(0)	(0)	(1.05)
R	0,6199	0,6843	0,6266	0,8984
	(0)	(0)	(0)	(1.323))
Ros	0,4981	0,4864	0,4979	0,04500
	(0)	(0)	(0)	(1.06)

50 independent runs

Lenna	N-Kmeans	20-	100-	Agent
		Kmeans	Kmeans
No.of	52	19	52	10.09
clusters
	(0)	(0)	(0)	(1.789)
Ros	0,4882	0,4652	0,4882	0,3313
	(0)	(0)	(0)	(0.456)

A new Swarm-based algorithm for image segmentation is presented by simulating the behavior of brood sorting of ants. In Agent, each pixel is placed in a cell on a discrete array, which represents the environment of the ants. Each ant may pickup a pixel or drops a pixel according to a similarity function that measures the degree of the similarity of a pixel with others pixels in the cluster. In Agent, we proposed new probabilistic rules for picking and dropping pixels moving and a local moving strategy that have salient effect in fastening the clustering process. Experimental results on synthetic and real images demonstrated the ability of Agent to extract the correct number of clusters and to give better clustering quality compared to those obtained from a classical clustering algorithm like Kmeans.

REFERENCES

[1]Monmarché, N., 1999. On Data Clustering with Artificial Ants. In: Freitas AA, (ed.), Data Mining with Evolutionary Algorithms: Research Directions– Papers from the AAAI Workshop, 23-26. AAAI Press.

[2]Bonabeau, E. and E. Theraulaz, 2000. L’intelligence en essaim. Pour la Science, 282: 66-73.

[3]Handl, J., 2003. Ant_based methods for tasks of clustering and topograpgoc mapping: Extensions, analysis and comparison with alternative methods. Master Thesis Germany.

[4]Lumer, E.D. and B. Faieta, 1994. Diversity and Adaptation in Populations of Clustering Ants. In: D. Cli®, P. Husbands, J. Meyer and S. Wilson (Eds.), From Animals to Animats 3, Proceedings of the 3rd International Conference on the Simulation of Adaptive Behavior, The MIT press/Bradford Books.

[5]Turi, R.H., 2001. Clustering-based color image segmentation. Ph.D Thesis. Monash University, Australia.

[6]Rosenberger, C., 1999. Mise en oeuvre d’un système adaptatif de

segmentation d’images Thèse de Doctorat de l’université de Rennes I

[7] Dorigo, M.; Maniezzo, V. & Colorni, A. (1996). Ant system:

optimization by a colony of cooperating agents, In: IEEE Transactions on Systems, Man and cybernetics, Part B,Vol.

26, 1996, pp. 29-41

[8]Gonzalez, R.C. & Woods, R.E. (1992). Digital Image Processing. Addison-Wesley, 1992

[9]Omran, M.; Salman, A. & Engelbrecht, A.P. (2002). Image Classification Using Particle Swarm Optimization, 2002

[10]Langham, A.E. and P.W. Grant, 1999. Using Competing Ant Colonies to Solve k-way Partitioning Problems with Foraging and Raiding Strategies. In: D. Floreano et al. (Eds.), Advances in Artificial Life, Lecture Notes in Computer Science, 1674, Springer, pp: 621–625.

[11]Hertz, J.; Krogh, A. & Palmer R.G. (1991). Introduction to the theory of neural computation, Addison-Wesley, Redwood City, 1991

[12]Earl Gose , Richard Johnsonbaugh, Steve Jost. .Pattern Recognition & Image Analysis.

[13]Zheng, H.; Zheng, Z. & Xiang Y. (2003). The application of ant colony system to image textute classification [textute read texture], In: Proceedings of the 2nd International Conference on Machine Learning and Cybernetics, vol. 3, pp. 1491-1495, Xi'an, China Nov. 2003