{'fraction_non_alphanumeric': 0.025815879201169022, 'fraction_numerical': 0.009343311340388788, 'mean_word_length': 4.771530794786608, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Image Segmentation Based on Genetic Algorithms Combination

Many works in the literature focus on the definition of evaluation metrics and criteria that enable to quantify the performance of an image processing algorithm. These evaluation criteria can be used to define new image processing algorithms by optimizing them. In this paper, we propose a general scheme to segment images by a genetic algorithm. The developed method uses an evaluation criterion which quantifies the quality of an image segmentation result. The proposed segmentation method can integrate a local ground truth when it is available in order to set the desired level of precision of the final result. A genetic algorithm is then used in order to determine the best combination of information extracted by the selected criterion. Then, we show that this approach can either be applied for gray-levels or multicomponents images in a supervised context or in an unsupervised one. Last, we show the efficiency of the proposed method through some experimental results on several gray-levels and multicomponents images.


Introduction
Segmentation is an essential step in image processing since it conditions the quality of the resulting interpretation. Lots of approaches have been proposed and a dense literature is available [19,14,10,31].
In order to extract as much information as possible from an environment, multi-components images can be used. In the last decade, multi-components images segmentation has received a great deal of attention for remote sensing and industrial applications because it significantly improves the discrimination and the recognition capabilities compared with gray-levels images segmentation methods. To process these images, there are two types of segmentation methods: the scalar and the vectorial approaches. The first one consists in merging the segmentation result of each band [13,24,14]. The second one tries to generalize the classical segmentation process of one-component images [27].
Some works have applied genetic algorithms (GA) to image processing [1] and to segmentation particularly [4,8,28,11]. As segmentation can be seen as a process which finds out the optimal regions partition of an image according to a criterion, GA are well adapted to achieve this goal. Indeed, GA are particularly efficient when the search space is really important and when the criterion to optimize is numerically complicated which is always the case in image processing. The main advantages of using GA for segmentation lie in their ability to determine the optimal number of regions of a segmentation result or to choose some features such as the size of the analysis window or some heuristic thresholds.
The GA proposed by Holland [12] are a general-purpose global optimization technique based on randomized search. They incorporate some aspects of iterative algorithm. A genetic algorithm is based on the idea that natural evolution is a search process that optimizes the structures it generates. An 2 interesting characteristic of GA is their high efficiency for difficult search problems without being stuck in local extremum. In a GA, a population of individuals, described by some chromosomes, is iteratively updated by applying operators of selection, mutation and crossover to solve the problem. Each individual is evaluated by a fitness function that controls the population evolution in order to optimize it.
Bhanu and al [4] used GA to optimize the parameters of a segmentation method under various conditions of image acquisition. Another illustration of the interest of GA for image segmentation is given by Yoshimura and al [29]. They combined GA and Kohonen's self-organizing map for the clustering of textured images. The fuzzy C-means algorithm was used to generate a fine segmentation result. Andrey [2] suggested an original approach as no objective fitness function is needed to evaluate segmentation results. Li and Chiao [16] proposed a genetic algorithm dedicated to texture images where the fitness function is based on texture features similarity. Melkemi et al. [17] use genetic algorithms to combine different segmentation results obtained by different agents. A recent work proposed by Lai et Chang uses a fitness function that can be considered as an evaluation criterion in a hierarchical process [15]. None study of the used fitness function has been done in order to quantify its reliability.
The most important components of the proposed methods concern both the modelling of the problem with GA and the definition of the fitness function. GA can be used to find out the optimal label of each pixel, to determine the optimal parameters of a segmentation method (number of regions for example), or to merge regions of a fine segmentation result. Concerning the fitness function, it can be an unsupervised quantitative measure of a segmentation result or a supervised one using some a priori knowledge.
In this paper, we deal with a general scheme for grey-levels and multi-components image segmentation that involves a GA. GA is used here as an optimization method for the optimal combination of segmentation results whose quality is quantified through an evaluation criterion. We define a general scheme to define segmentation methods by optimization. Note that we try in this paper to evaluate the reliability of the fitness functions we used in our method.
We illustrate the proposed method by defining different types of fitness functions in section 2. The 3 first one uses the value of an unsupervised evaluation criterion computed on a segmentation result. The second one uses a semi-supervised evaluation criterion by taking into account a local ground truth when it is available. The last one shows the generalization for multi-components images. In section 3, we describe the optimization process with GA. We show the efficiency of the proposed method through experimental results on gray-levels and multi-components images in section 4. In section 5, we conclude and give some perspectives.

Developed method
The developed method consists in looking for the optimal combination of segmentation results by taking into account an evaluation criterion and by using a genetic algorithm. We define in the following subsections some evaluation criteria for different purposes concerning the segmentation process.

Evaluation principles
Numerous works deal with the problem of the evaluation of a segmentation result [20,22]. Zhang [32] presents a possible classification of the evaluation criteria in three groups: • the "analytical methods" which permit to characterize an algorithm in terms of principles, needs, complexity, convergency, stability,... without any reference to a concrete implementation of the algorithm or testing data, • the "empirical goodness methods" also called unsupervised criteria which compute a fitness metric on a segmentation result. They do not necessitate any knowledge on the segmented images to assess and their principles consist in an estimation of the quality of a segmentation result according to some statistics computed on each region, class, texture, fuzzy set... detected, mostly often by using a statistical point of view (see Figure 1), • the "empirical discrepancy methods" also called supervised criteria which compute some measures of dissimilarity between a segmentation result and the desired segmentation result (see Figure   2). They thus assess the quality of a segmentation result by using an a priori knowledge. This knowledge can be a segmentation result used as a reference which is called ground truth (GT ) or  Our center of interest is to evaluate the quality of a segmentation result, thus the analytical criteria are not studied in this paper. Moreover, we have chosen for this study to focus on criteria which assess region segmentation results because it is a complex problem. In the next section, we study some unsupervised evaluation criteria.

Unsupervised evaluation
Unsupervised evaluation criteria give an information on the coherence of a segmentation result quality.
The main objective of a previous work presented in [6] was to determine the supervised evaluation crite-rion, within a selection of criteria from the literature, having the best behavior in comparison with human experts judgement. To achieve this goal, two main steps have been realized. The first one concerns the ranking of segmentation results of some images by human experts. The second one concerns the creation of a similarity measure able to compare the evaluation behavior of the experts and of a criterion to study.
Thus, a Similarity Rate of Correct Comparison criterion (SRCC) has been defined [6]. It computes the similary of judgment given by an evaluation criterion and an expert. From this study, the Vinet's criterion has been determined as the one with the best behavior according to the human experts.
In the following part of this paper, we briefly present the results of a comparative study of unsupervised evaluation criteria [7] by using the Vinet's criterion as a reference in the case of synthetic images for which the ground truth is well known.
A set of synthetic images including 14 subsets of images having respectively from 2 to 15 classes was created. The Figure 3 presents some examples of the ground truths used to create the images. Thus, each subset has a fixed number of classes and is made up of 600 images with a proportion of textures going from 0 to 100% by step of 25%. The Figure 4 presents some examples of synthetic images created by using this process. We used three segmentation methods: the Fuzzy C Means method (FCM) [3], a relaxation of this segmentation result and the mean shift algorithm (EDISON) [9]. In addition to these three segmentation results, an obvious synthetic segmentation result was added: the ground truth used to create the subset of synthetic images. This result is the best possible one. The Figure 5 presents an example of segmentation results obtained by using these methods on an image (the number of classes is supposed to be known for We selected, from the state of art [32,21] six unsupervised evaluation criteria of gray level image segmentation results into regions or classes: • Zeboudj's contrast (Zeboudj) [30]: this measure takes into account the internal and external contrasts of the regions measured in the neighborhood of each pixel.
• Levine and Nazif's inter-class contrast (Inter) [18]: this criterion computes the sum of contrasts of the regions balanced by their surfaces.
• Levine and Nazif's intra-class uniformity (Intra) [18]: this criterion computes the sum of the normalized standard deviation of each region.
• Combination of intra-class and inter-class disparities (Intra-inter) [18]: this indicator combines similar versions of the Levine and Nazif inter-class and intra-class measures.
• Borsotti's criterion (Borsotti) [5]: this measure is based on the number, the surface and the variance of the regions.
• Rosenberger's criterion (Rosenberger) [21]: the originality of this criterion lies in its adaptive computation according to the type of region (uniform or textured). In the textured case, the dispersion of some textured parameters is used and in the uniform case, gray levels parameters are computed.
The Vinet's criterion [25] proved to be the closest one to the human judgement with a similarity rate of correct comparison (SRCC) of 86% in the supervised case [6]. This criterion was thus selected as our reference and was computed on the whole set of segmentation results obtained on the images set (the as- In the case of completely uniform images, the Zeboudj's criterion proves to be the most efficient with a SRCC V inet superior to 88%. The Inter criterion is recommended in the case of mixed images and for most textured ones. It has a mean SRCC V inet of more than 71% on the images sets corresponding to these cases. Finally, the Rosenberger's criterion is the only discriminating criterion for the study of segmentation results of images having textured classes with the same average of gray levels with a SRCC V inet of more than 61%. If one takes into account the whole images set, the Inter criterion appears to be the most efficient but presents a SRCC V inet of only 66%.

Supervised evaluation
In order to define the level of precision of the segmentation result, we can use a local ground truth. A local ground truth is defined as a small set of pixels with a known class. It is used in the optimization process by computing the correct classification rate (Vinet's measure) on each cluster of the local ground truth. An example of a local ground truth is given in figure 6. In this case, we set some examples of regions in an image.  We call GT the local ground truth used in our method. Given a segmentation result, we can compute the correct classification rate for each cluster of GT . We define the following criterion: where N bGT is the number of pixels in GT . The value Rate(C i ) is the correct classification rate for the cluster C i . The correct classification rate for each pixel of GT is integrated into this criterion. The higher this value is, the more the result corresponds to the needed level of precision. If N bclass equals to zero, the segmentation process will be unsupervised. The local ground truth can be seen as local constraints set by an user. The R(I s , GT ) term evaluates the adequation of the segmentation result to GT (that means that all the clusters of GT in the final segmentation result must be as homogeneous as possible).
A new criterion can be defined by taking into account some constraints on the level of precision of the segmentation result: where CR(I s , GT ) is one of the unsupervised criteria detailed in the section 2.2. The SCR(I s , GT ) criterion is a semi-supervised one.

Generalization to the multi-components case
We define in this section the generalization of an unsupervised evaluation criterion for multi-components  Table 2 shows that there is no fundamental difference between the three fusion operators (mean, minimum, maximum). The best evaluation criterion in the multi-components case, in sense of our approach, is the Rosenberger's criterion with the fusion method based on the mean.  We applied this criterion in the multi-components case.

Optimization method: a Genetic Algorithm
Genetic algorithms determine the optimal value of a criterion by simulating the evolution of a population until survival of best fitted individuals [26]. The survivors are individuals obtained by crossing-over, mutation and selection of individuals from the previous generation. We think that GA is a good candidate to find out the optimal combination of segmentation results for two main reasons. The first one is due to the fact an evaluation criterion is not very easy to differentiate. GA is an optimization method that does not necessitate to differentiate the fitness function but only to evaluate it. Second, if the population  • individual mutation: individual's genes are modified in order to be better adapted to the environment. We use the non-uniform mutation process which randomly selects one chromosome x i , and sets it as equal to a non-uniform random number: • selection of an individual: individuals that are not adapted to the environment do not survive to the next generation. We used the normalized geometric ranking selection method which defines a probability P i for each individual i to be selected as following: where q : the probability of selecting the best individual r : the rank of individual, where 1 is the best n : the size of the population • crossing-over: two individuals can reproduce by combining their genes. We use the arithmetic crossover which produces two complementary linear combinations of the parents: where X, Y : genotype of parents a : a number in the interval [0, 1] X ′ , Y ′ : genotype of the linear combinations of the parents

Experimental results
In this paper, we show the results of two types of experiments. First, we use the previously presented method to segment gray levels images by combining several segmentation results. Second, we present some genetic segmentation results of multi-spectral images. These images were acquired with a CASI (Compact Airborne Spectrographic Imager).
For all the following experimental results, we set the value of the selection probability to 8%, the crossing-over probability to 60% and the mutation probability to 5%. The unsupervised evaluation criterion we use in this paper is the Rosenberger's one because of the presence of textures in test images.

Genetic segmentation of gray levels images
First of all, we show the unsupervised genetic segmentation results of one gray levels image called CAR (see Figure 8). This image was segmented using the K-means algorithm with mean and variance as attributes with different numbers of clusters N C (5, 10, 12, 15) which constitutes the initial population for the GA. In this case, the genotype of an individual is a vector of size 262144 (the size of each image is 512 × 512 pixels). A gene corresponds to the label of each pixel in the considered segmentation result.
Final result shows the efficiency of the proposed method. If we look at the tree in left of the CAR image, we see that this textured region is not over-segmented like in the segmentation results we used in 14 the initial population. An important point is that we did not specify in this experiment the number of clusters we wanted. It has been automatically determined (NC=6).  Table 3 gives some statistics about the GA for the previous segmentation result. We show here the ability of the GA to determine the best individual with a few iterations. The value of the evaluation criterion of the best segmentation result significantly increases. Note that we obtain a good stability of the results for different executions of this algorithm after 100 iterations.  We also present the supervised segmentation results of two images by using the developed method (see figure 9). We define, for each original image, a local ground truth in order to obtain a precise segmentation result. The local ground truth defines some regions which must be present in the final result.
As for example, we define three regions in the figure 9 (a) and two in the figure 9 (c), so we want in the final result that pixels in these regions belong to the same class. As we can see in the segmentation result ( figure 9 (b)), the sky is represented by a single cluster as the roof of the house and the major part of the grass. For the image (c) of figure 9, we select some fields in order to make the interpretation of the culture inside each field easier.
The initial population is composed of segmentation results obtained by using the K-means algorithm with mean and variance as attributes with different numbers of clusters (5,10,12,15). Segmentation results are visually correct. Table 4 gives the values of several optimized criteria. The D and D correspond to intermediate values used to compute the Rosenberger's criterion [21]. The D computes the global intra-region disparity and has to be close to zero (computation of the disparity of statistics inside a region). The second one computes the global inter-region disparity D and must have as high value as possible. Value CR corresponds   Table 4: Values of the evaluation criterion for results of figure 9 We compared the supervised approach and the unsupervised one by segmenting the same image AERIAL. The evaluation results are detailed in Table 5. These results show that the evaluation criterion CR is higher in the unsupervised case. This reveals the ability of the unsupervised approach to determine the optimal value of CR. The use of a ground truth allows us to match the level of precision of the

Genetic segmentation of multi-spectral images
In this section, we present the unsupervised segmentation result of a multi-spectral image composed of 9 bands (wavelength in nm: 551.1, 571.5, 600.9, 636.5, 677.7, 696.5, 715.4, 749.5, 799.9) using the proposed method (see in figure 10). Each component of this image was also segmented using the K-means algorithm with mean and variance as attributes. The final result is correct and combine well information from each component. The application for this image was to compute the bio-mass of algae lying on the beach.
The use of multi-spectral data provides us a better discrimination of algae by taking account visible and also near infra-red information. As for example, the white square detected in the segmentation result in the figure 10 (c) on the top right is present in the final result while it was not really visible in figure 10 (d).
We present also the supervised segmentation result of two multi-spectral images with a similar protocol. We show the two most different components of these images (which correspond to components 1 and 9). We define for each original image a local ground truth in order to obtain a precise segmentation result. For the figure 11 (a), the local ground truth corresponds to figure 11 (c). We select 2 types of field and an area corresponding to some hedges. Each component brings an additional piece of information, the problem for these images is to take them into account in the final result. As we can see in figures 11 (d) and (h), the segmentation results are visually correct and correctly integrate addi-

Conclusion and perspectives
Many works in the literature focus on the definition of evaluation metrics that enable to quantify the performance of an image processing algorithm. These evaluation criteria can be used to define new image processing algorithms by optimizing them. Genetic algorithms can be used for this application.
In this paper, we focused on the interest of genetic algorithms for image segmentation. We showed that this kind of approach can be applied either for grey-levels and multi-components images. The developed method uses the ability of GA to solve optimization problems with a large search space (label of each pixel of an image). The developed method can also integrate some a priori knowledge (such as a local ground truth) if it is available. Its efficiency was illustrated through some experimental results on several CASI multi-spectral images.
Prospects for this work concern first of all the definition of some new fitness functions in order to define edge segmentation methods. Second, some a priori knowledge such as the shape of objects to detect could be used in order to localize some particular objects in an image. 20