Richard Moussa

Marie Beurton-Aimar

Pascal Desbarats

On the use of social agents for image segmentation

Keywords: Image segmentation, Social spiders, Social ants, Multi-agent system, Articial life

In the literature, there are a lot of methods for image segmentation. Unfortunatelly, they are often limited in their capacity to treat image odtained by an acquisition system (Optical, X-Ray, IRM, . . .). Thus, many of them are dedicated to particular solutions and there is no generic method for solving the image segmentation problem. In this paper, we present a way to implement segmentation methods which use models coming from biology: social spiders and social ants which are implemented by a multi-agent system. After a presentation of the principles of these two methods, we will quickly present two another ones: Region Growing and Otsu thresholding methods, in the aim to compare their results. The simulation of these methods shows results that are promising. Some perspectives have been retained in order to overcome agent-based methods for having a robust segmentation technique.

I. INTRODUCTION

I MAGE SEGMENTATION consists on partitioning an im- age into a set of regions that covers it. After this process, each pixel is affected to a region and each region corresponds to a part of the image. The discontinuity between the regions constructs the contour of the object. The segmentation approaches can be divided into three major classes [START_REF] Jähne | Digital Image Processing[END_REF]. The first one corresponds to pixel-based methods which only use the gray values of the individual pixels. The second one is the edge-based methods which detect edges, for example, this can be done by computing a luminacy function. The last one, the region-based methods which analyze the gray values in larger areas for detecting regions having homogeneous characteristics, criteria or similitude. Finally, The common limitation of all these approaches is that they are based only on local information. Sometimes, only a part of the information is necessary. Pixel-based techniques do not consider the local neighborhood. Edge-based techniques look only for discontinuities, while region-based techniques only analyze homogeneous regions. Robust, automatic image segmentation requires the incorporation and efficient utilization of global contextual knowledge. However, the variability of the background, the versatility of the properties of the regions to be extracted and the presence of noise make it difficult to accomplish this task. Considering this complexity, one often applies different methods during the segmentation process according to the specifities of the images.

A MAS 1 is composed of heterogeneous unembodied agents carrying out explicitly assigned tasks, and communicating via symbols. On the contrary, many extremely competent natural Richard Moussa is a Phd student in the laboratory Labri, 351, cours de la Libération F-33405 Talence cedex e-mail: richard.moussa@labri.fr.

Marie Beurton-Aimar and Pascal Desbarats are associated professor in the laboratory Labri, 351, cours de la Libération F-33405 Talence cedex. 1 Multi-Agent System.

collective systems of multiple agents (e.g. social spiders and social ants) are not knowledge based, and are predominantly homogeneous and embodied; agents have no explicit task assignment, and do not communicate symbolically. A common method of control used in such collective systems is stigmergy, the production of a certain behavior in agents as a consequence of the effects produced in the local environment by previous behavior [START_REF] Wooldridge | An Introduction to MultiAgent Systems[END_REF]. Social insects like ants are one of the most diverse and ecologically important organisms on earth. As superorganisms, they live in intricately governed societies that rival our own in complexity and internal cohesion. For example, they are particularly well suited to post-genome biology age because they can be studied at multiple different levels of biological organization, from gene to ecosystem, and much is known about their natural history [START_REF] Theraulaz | Coordination in Distributed Building[END_REF].

Social spiders belong to spider species whose individuals form relatively long-lasting aggregations. Whereas most spiders are solitary and even aggressive toward conspecifics, hundreds of species show a tendency to live in groups and to develop collaborations between each other, often referred to as colonies. For example, spiders of 5mm in body length are capable to fix silks up to a volume of 100m 3 [2]. This technique is used to trap preys having big forms.

Ramos et al. have explored the idea of using a digital image as an environnement for artificial ant colonies. They observed that artificial ant colonies could react and adapt appropriately their behavior to any type of digital habitat [START_REF] Ramos | Artificial ant colonies in digital image habitats -a mass behaviour effect study on pattern recognition[END_REF]. He also investigated ant colonies based data clustering and developed an ant colony clustering algorithm which he applied to a digital image retrieval problem. By doing so, he was able to perform retrieval and classification successfully on images of marble samples [START_REF] Ramos | Self-organized data and image retrieval as a consequence of inter-dynamic synergistic relationships in artificial ant colonies[END_REF]. Liu et al. have conducted similar works and have presented an algorithm for grayscale image segmentation using behavior-based agents that self reproduce in areas of interest [START_REF] Liu | Adapive image segmentation with distributed behavior-based agents[END_REF]. Hamarneh et al. have shown how an intelligent corpus callosum agent, which takes the form of a worm, can deal with noise, incomplete edges, enormous anatomical variation, and occlusion in order to segment and label the corpus callosum in 2D mid-sagittal images slices in the brain [START_REF] Hamarneh | Deformable organisms for automatic medical image analysis[END_REF]. Bourjot et al. have explored the idea of using social spiders as a behavior to detect the regions of the image. The principle is to weave a web over the image by fixing silks between pixels [START_REF] Bourjot | A new swarm mechanism based on social spiders colonies : from web weaving to region detection[END_REF].

In this paper, two methods based on an Ant System and a Spider System are described and compared with two classical methods. The first method consists on travelling on the pixels of the image and lays down a pheromone where each pixel validates our criteria: morphologic gradient. The second is a region-based technique which tries to fix silks between homogeneous pixels to construct webs.

This paper is organized as follows. Section II describes the two types of MAS with an explanation of the usage of such systems in the image segmentation domain. Section III presents the experimentation of our implementation by using comparison criteria with two segmentation techniques: Region Growing and Otsu thresholding. Finally, our implementation is discussed and we conclude with further expected improvements and perspectives for these systems.

II. SEGMENTATION WITH SOCIAL AGENTS

A MAS is a distributed system composed of a group of agents, which interact between themselves through an environnement. Agents are classified into two categories: cognitive and reactive. Cognitive agents have a global view of the environment, they know the task for which they work. Conversely, reactive agents only know a restricted part of the environment. They react to environment stimulus and can modify this environment by adding or removing informations. Reactive agents do not know the complex task for which they work: they have a restricted set of simple features and they only apply them. Spiders or ants colonies are an example of reactive agents: each one knows locally what it has to do, but no one knows the more complex task for which they work.

Multi-agent systems are composed of an environment and a set of agents. For segmentation purpose, environment is created from a given grayscale picture: it is a matrix of gray pixels. The system and its agents have a life cycle. A cycle of the system consists in executing the life cycle of each agent. This life cycle is transposed to a step. The number of steps to be executed is given by the user. Two methods will be presented here: social ants and social spiders.

A. First MAS model: social ants

As previously mentioned, ants are social insects. They exhibit very good organization and construction abilities by colony behaviors. One of the important ones is their object searching behavior, in particular, how they can find the path to the object of interest from their nest. While walking from their nest to the object to be detected, ants leave on the way a kind of substance called pheromone whose concentration becomes weaker with time due to evaporing, forming in this way a pheromone trail. During their route, ants smell the pheromones deposited and when choosing their way, they tend to choose the most pheromoned direction. And the more the ants choose the same direction, the stronger the pheromone concentration is. Thus, this pheromone concentration helps the ants in choosing their shortest movement to the object of interest. Such algorithm is called ACO 2 algorithm [START_REF] Bertelle | Dynamic Placement Using Ants for Object Based Simulations[END_REF] [18] [START_REF] Guinaud | Problem Solving and Complex Systems[END_REF]. In image segmentation domain, lots of proposed multi-agent methods have been inspired from this concept to elaborate a robust edge-based method [START_REF] Han | An improved ant colony algorithm for fuzzy clustering in image segmentation[END_REF] or region-based method [START_REF] Saatchi | Using Ant Colony Optimization and Selforganizing Map for Image Segmentation[END_REF].

For segmentation purpose, from the behavior explained above, we have chosen to use the act of deposing pheromones to perform our image segmentation task. This segmentation uses a number of ants that are injected randomly through the environnement and guides them with a morphological 2 Ant Colony Optimization.

gradient. The kernel used here to compute the gradient is a 3x3 pixels as shown in figure 1. If the pixel passes the test then an ant leaves a pheromone on it and steps to the pixel having the highest gradient in its neighborhood. The pixels in the environnement are classified into three categories: marked, visited and free. Figure 2 shows an example of the environnement having these categories and where an ant is trying to move to another pixel. Firstly, each ant computes the morphological gradient on its own pixel. Then, the pixel is classified as visited or marked depending on the condition established by the user. This ant has the capability to move on its 8-neighborhood. Thus, an ant looks to the free pixels and moves to the one having the highest gradient. If not, the ant in question passes to an impasse status. Algorithm 1 presents the description of the conditions presented above. The user has to fix three parameters: the percentage of pixels visited, the morphological gradient threshold and the number of agent. After that, the process begin trying to visit the percentage done by the user and marking pixels which passed the gradient condition. The complexity of this algorithm is O(N bagent * N bT ) where N bagent is the number of agents fixed by the user and N bT is the number of times the process passes the condition in line 2.

1) Optimization: In order to optimize the number of parameters to be delivered by the user, we have decided to fix the percentage of pixels to 100% to ensure that all the pixels were evaluated. For the morphological gradient threshold, we compute it as the minimum difference between two locals maxima of the histogram of the image having the highest distribution of pixels between them. The number of agent depends linearly from the maxima. Therefore, there is no absolute optimum value for the N bagent parameter but this problem can be bypassed by a numerical solution such as injecting one hundred times the number of local maxima.

B. Second MAS model: social spiders

Social spiders have been defined by the biologists to present stigmergic process like social insects. The characteristics of these societies and the importance of the silk in the various 1) social spiders do not present any specialization in morphology and ethology; 2) an isolated social spider presents behavioral characteristics very close to lonely species; 3) social spiders show spectacular organization and cooperation forms, in particular, the web construction and the prey capture or its transportation phenomenon. As mentioned before, Bourjot et al. have proposed a method using social spiders as a model of behavior to detect the regions of the image [START_REF] Bourjot | A new swarm mechanism based on social spiders colonies : from web weaving to region detection[END_REF]. Its principle is to weave a web over the image by fixing silks between pixels using probabilistic movement. This method has been implemented and evaluated by Bourjot et al. and Moussa et al. [START_REF] Moussa | Image segmenattion using social agents[END_REF]. It has given good results on synthetic images but failed on more complex images such as MRI3 images. Thereby, we have decided to built a new method by using some ideas from that described above.

Following the model previously described, we can design spiders as agents. Spiders are reactive agents. They are defined by an internal state composed of a set of parameters values, a current position and the last pixel where a spider has silked. These spiders have also an ability to move in the environnement, to fix a silk 4 and to come back 5 . Spiders which detect the same region can be grouped in a set called a colony. Spiders of a same colony share the same set of parameters values.

Spiders try to move through their 8-neighborhood, they prioritize the non-silked pixels and try to fix silks on them. If they fail, they move back to the last fixed silk. At the end of the process, groups of spiders are formed and are called regions. Figure 3 presents an example where a spider try to fix a silk or move back using the intensity variation as a condition. end for 12: end while 1) Optimization: In this case, only the threshold has been optimized. Its computation consists on the minimum variation of two locals maxima. But for the other two parameters, at present, we are not able to compute them automatically due to their dependency between each other.

III. METHODOLOGY USED FOR COMPARISON

In this section, we compare the social spiders method with other segmentation methods while the social ants method is interpreted separately. We do not search for counting the contours but to evaluate the result of the social ants segmentation. These comparisons allow us to determine whether the social spiders and ants methods brings something positive compared to traditional segmentation methods.

We use these comparisons on two other methods:

• a classification method by thresholding: the Otsu method [START_REF] Chen | A fast algorithm for multilevel thresholding[END_REF];

• a region-based method: the Region Growing method [START_REF] Shapiro | Computer Vision[END_REF].

To compare these methods, we need to establish criteria to be used on all test images. We compare the results on several points: 1) the number of regions; 2) correspondence between the regions of the model and the segmentation result; 3) execution time.

Definition Let Γ be an image and ∆ its segmentation result. We call Γ i the region i of the image and ∆ j the region j of the result.

The number of regions allows us to determine whether the method considered detects a number of regions close to reality. In the case of noisy images, it is possible that some methods detect regions with insignificant size. That is why we add to the total number of regions, the number of regions having insignificant size. For our output segmentation, we consider a region as insignificant if its size is less than 10 pixels.

The computation of the number of regions is done on the method result on which a labeling is added to the connected components to consider the regions connected.

The correspondence between initial image and its result enables us to determine if the regions identified by the method correspond to the regions defined in the initial image. This is only possible in the case of synthetic images.

To compute the accuracy, it is necessary to determine which region ∆ j matches the most the region Γ i . This region is determined by:

n i =
the total number of pixels the pixels of Γ i n j = the total number of pixels the pixels of ∆ j (1)

n i j =
the total number of pixels the common pixels between ∆ j and Γ i Thus, it is possible to compute δ i,j = n i j n i and γ i,j = n i j nj representing respectively the proportion of pixels of Γ i belonging to ∆ j and the proportion of pixels of ∆ j belonging to Γ i . We have two ways to choose the region that corresponds to ∆ j corresponding the most to Γ i :

1) ∆ k as the value of δ i,k is maximum: in this case, we prefer the fact that Γ i and ∆ j have a maximum of pixels in common; 2) ∆ k as δ i,k + γ i,k is maximum: same as above, but we add the requirement that ∆ k must have a minimum of pixels in other regions than Γ i . In our results, we indicate two points, accuracy δ and accuracy δ+γ , which corresponds respectively to the two choices of ∆ k described above. In both cases, the accuracy will be the average values for all regions of the model.

A. Region Growing

The Region Growing method consists on building a region from one chosen pixel and then adding recursively neighbors whose grayscale difference with the original pixel is below a threshold [START_REF] Shapiro | Computer Vision[END_REF].

This method tries to grow an initial region by adding to this region the connected pixels that do not belong to any region. These pixels are the neighborhood pixels already in the region and whose grayscale is sufficiently close to the area. When it is not possible to add pixels, we create a new region with a pixel that has not been selected yet, then we grow the region.

The method ends when all the pixels were chosen by a region.

B. Otsu

Otsu has developed a multi-level thresholding method [START_REF] Otsu | A threshold selection method from gray level histograms[END_REF]. Its aim is to determine, for a given number of regions, the optimum values of different thresholds based on the variance of subdivisions created.

The basic method consists on separating the foreground from the background. In this case, we search the optimal threshold to split the pixels in two regions. For a threshold t, it is possible to compute the between-class variance σ 2 (t). This measure is derived from the average intensity µ 1 , µ 2 and µ of classes [0; t], [t + 1; L] and [0; L] where L is the maximum intensity.

The Equation 2introduce the computation of σ 2 , where w 1 and w 2 represent the proportion of pixels in the class [0; t] and [t + 1; L] compared to the total number of pixels.

σ 2 (t) = w 1 (t)(µ 1 (t) -µ) 2 + w 2 (t)(µ 2 (t) -µ) 2 (2)
The Otsu method shows that the optimal threshold t * is obtained for a between-class variance. The method consists on computing the variance for all possible thresholds (t ∈ {1; . . .; L -1}) and determining its maximal value. This method could be extended easily to the computation of M classes with M -1 thresholds {t 1 ; t 2 ; . . .; T M -1 -1} (t 1 < t 2 < . . . < t M -1 ). The between-class variance is defined then as follows:

σ 2 (t 1 , . . . , t M -1 ) = M M -1 w k (µ k -µ) 2 (3)
where w k represent the proportion of pixels in the class [t k-1 ; t k ]6 , µ k the intensity average of this same class and µ the intensity average of the class [0; L].

For each M-1-uplet, we compute thresholds of the betweenclass variance. The optimal thresholds, (t * , . . ., t * M -1 ), correspond to the maximum value of the between-class variance.

Chen et al. propose an algorithm that minimizes the number of necessary computation to obtain a faster algorithm [START_REF] Chen | A fast algorithm for multilevel thresholding[END_REF]. This method had been implemented for our evaluations tests.

C. Experimentations

Now, we will present the results of the experimentation on 2D images with and without noise. Firstly, we will see the results of segmentation obtained with a non-noisy image to ensure the functioning of the different methods, then we will see the results on a noisy-image to determine the noiseresistance of the spiders and ants methods. For the spiders method, the non-detected pixels are colored. Therefore, they will be seen as a noise in the image segmentation results.

The execution time to be given comes from the simulation of the methods on a machine equipped with an Intel Quad Q9550 (4 cores having 2.83GHz) and 4GB of RAM. The operating system of this machine is a Linux kernel 2.6.21 x86 64. The synthetic and the brain images are respectively composed of 10 and 94 regions. The size of the test images is 256x256 pixels.

Figure 4 and 5 presents respectively the results of the different image segmentation techniques applied on a non-noisy synthetic and brain image. Their informations are explored in table I and II. For the synthetic image, the results of Region Growing (threshold = 25) and Otsu (thresholds = 60, 127, 178 and 204) methods have a maximum accuracy with a number of regions that corresponds to the image. The spiders method (iterations = 100000, spiders = 10000 and threshold = 25) has a region that corresponds to the extra pixels that have been detected by any spider. This region is not connected, the pixels that compose it are scattered throughout the image. These pixels are merged with the most likely region. The processing time is bigger than the other methods with less accurate results. The ants method (ants = 10000, gradient = 51) has delivered a good accuracy for the detection of the contours with the same number of contours for the original image. The supplement region discussed above on the segmentation image obtained by social spiders is composed of scattered contours. These contours are found by the social ants segmentation with a good precision and a fast computation time.

Social spiders

Social spiders

In the case of the brain image, the Region Growing method (threshold = 13) has the lowest accuracy and the biggest number of regions. Otsu method (thresholds = 15, 44, 76 and 95) produced the highest number of insignificant regions which leads an oversegmentation of the image. Same as above, The social spiders method (iterations = 100000, spiders = 10000 and threshold = 25) has pixels not selected by any spider (ie. they are colored by black in the image and spreaded like noise). It is therefore possible to perform a post-treatment that would link these pixels to the colony that have a strong presence in their neighborhoods. Its accuracy is better the the other methods. As for the social ants method (ants = 10000, gradient = 26), it has approximatively recovered all the contours with good accuracy.

Despite the fact that the difference between region-based segmentation methods is small, the accuracy of the results of the spiders and the ants methods are worse than the other methods for the synthetic image case and better for the brain case. However, as the spiders and the ants methods are stochastic methods, we do not expect to get maximum accuracy. Let us test that this accuracy will remain stable when adding noise.

For that, we added noise to the original images (20%). The results of the different image segmentation techniques applied on the synthetic and brain noisy images are respectively presented in figure 6 and7 . Their statistics are mentioned in table III and IV. In the case of synthetic noisy image, adding noise caused a decrease in the accuracy of the results of all methods except Region Growing (threshold = 50) which presents a robustness to noise. The result of the spiders method (iterations = 100000, spiders = 10000 and threshold = 50) has decreased in term of accuracy. Furthermore, the difference between the accuracy of the non-noisy image and the noisy one is minimal for the spiders method. These two points allow us to say that the spiders method is less sensitive when adding noise to the image. The number of regions has increased for the three methods compared to the non-noisy image segmentation. However, a number of regions rather high can be explained by a number of pixels non-detected more important, leading to disconnection of the regions. We note that the Otsu method (thresholds = 15, 64, 134 and 200) produces the most regions. This method, unlike Region Growing and social spiders method, have produced an important number of insignificant regions which implies oversegmentation of the image. As for the social ants method (gradient = 102), the accuracy has decreased due to noise effect.

Social spiders

Social spiders

For the noisy brain image, the Region Growing (threshold = 25) and the Otsu (thresholds = 17, 52, 90 and 117) have oversegmentated the image despite the fact that the Region Growing method obtained a number of significant region closer to the reality. The accuracy of the social spiders method (iterations = 100000, spiders = 10000 and threshold = 25) has decreased the less and became the best one in term of performance. The accuracy of the social ants method (gradient = 84) has made an important decrease due to noise effect.

The execution time of all methods remained stable. Therefore, it appears that the social spiders segmentation is robust to noise effect. This robustness has however led to a light oversegmentation of the image without influencing the time process.

IV. CONCLUSION AND PERSPECTIVES

In this paper, we have presented two methods of segmentation. The first corresponds to a contour-based technique, the social ants, which has produced a good segmentation where the method has recovered the contours of the non-noisy images. As for the noisy ones, the contours are scattered for an accuracy less important. On the contrary, the social spiders method, a region-based method, has produced a non neligeable time processing in the case of non-noised image with a result less important than the others. And when noise is added, the processing time remained stable but with a better accuracy than for the other region-based methods. Note that the results of social spiders method are influenced by the repartition of the agents on the matrix and the number of step to do.

We have made comparisons between the results of the social spiders, social ants, Region Growing and the Otsu methods. These comparisons focused on the accuracy, the number of regions produced and the time processing of the methods. They are not exhaustive comparisons where all aspects of segmentation are not taken into account.

Through these comparisons, we have put forward some drawbacks on the social spiders method. Particularly, we have seen that this method produced a significant number of areas and that the execution time was particularly long as discussed above.

As we can see from the results in table I, the social spiders method produces a new region constructed by pixels non-silked. These pixels are composed of scattered contours. Therefore, the social spiders and the social ants have complementary roles and merging the two methods will produce a new segmentation having accurate contours on the resulting images.

Fig. 1 .

 1 Fig. 1. Gradient computation kernel.

Fig. 2 .

 2 Fig. 2. Ants movement.

Algorithm 1 G 1 ←

 11 Ants method Require: Pixels: Matrix of pixels ∈ N 2 , PerV: Percentage of pixels visited and Grad: Morphological gradient threshold ∈ R and Nbagent: number of agents ∈ N. 1: NbVisited ← 0. 2: while PerV > Per(NbVisited) do 3: for Each agent s do 4: ComputeGrad(Pixel(s)).

5 :

 5 if G 1 ≥ Grad then 6:Mark(Pixel(s)).

G 2 ←

 2 ComputeGrad(Neighborhood(Pixel(s))).

9 :

 9 Move(s, Position(Max(G 2 ))).

  end while behavior have created a different model from the social insects one. During their cycle, social spiders have the abilities to fix silks, move forward and move back. This model have characteristics which sufficiently distinguishes the levels of the realized spots, the society organization and the communication supports. Indeed, social spiders correspond to an interest model for three reasons [9]:

Fig. 3 .Algorithm 2 2 :

 322 Fig. 3. Spiders movement.

  (Pixel(a)), Position(Pixel(T))). 7: LastFixedSilk(a) ← Pixel(a).

Fig. 4 .

 4 Fig. 4. 2D segmentation of synthetic a) Original image b) Social spiders, c) Social ants, d) Region Growing, e) Otsu.

Fig. 5 .

 5 Fig. 5. 2D segmentation of Brain image: a) Original image b) Social spiders, c) Social ants, d) Region Growing, e) Otsu.

Fig. 6 .

 6 Fig. 6. 2D segmentation of synthetic image with noise: a) Original image b) Social spiders, c) Social ants, d) Region Growing, e) Otsu.

Fig. 7 .

 7 Fig. 7. 2D segmentation of Brain image with noise: a) Original image b) Social spiders, c) Social ants, d) Region Growing, e) Otsu.

TABLE III 2D

 III RESULTS: SYNTHETIC IMAGE WITH NOISE.

			Social ants	Region Growing	Otsu
	Region	425	x	89	3096
	Region > 10px	51	x	10	580
	Accuracyσ	84.6 %	75.2 %	99.9 %	50.1 %
	Accuracyσ+γ	81.5 %	73.3 %	99.9 %	34.6 %
	Time	327 s	0.2 s	0.5 s	18 s

Magnetic Resonance Imaging.

Weave a dragline between two pixels.

Return to the last fixed pixel.

t 0 = 0 and t M = L.