Color image segmentation: a state of the art survey.

Introduction

segmentation refers to the process of partitioning a digital image into multiple segments or set of pixels, also known as superpixels. Image segmentation is typically used to locate objects and boundaries (lines, curves, etc.) in images. Image segmentation can be used in various fields like medical (for locating tumors and other computer guided surgery), satellite imaging, remote sensing and many more areas. Genetic Algorithms (GAs) were invented by John Holland and developed by him and his students and colleagues.

[ILLUSTRATION OMITTED]

Genetic algorithm

Genetic algorithms are based on natural selection discovered by Charles Darwin [40]. They employ natural selection of fittest individuals as optimization problem solver. Optimization is performed through natural exchange of genetic material between parents. Offsprings are formed from parent genes. Fitness of offsprings is evaluated. The fittest individuals are allowed to breed only. In computer world, genetic material is replaced by strings of bits and natural selection replaced by fitness function. Matting of parents is represented by cross-over and mutation operations.

A simple GA (Figure 1) consists of five steps [29]

1. Start with a randomly generated population of N chromosomes, where N is the size of population, 1--length of chromosome x.

2. Calculate the fitness value of function [phi](x) of each chromosome x in the population.

3. Repeat until N offsprings are created:

a. Probabilistically select a pair of chromosomes from current population using value of fitness function.

b. Produce an offspring yi using crossover and mutation operators, where i = 1, 2, N.

4. Replace current population with newly created one.

5. Go to step 2.

[ILLUSTRATION OMITTED]

Various Segmentation technique Edge detection Technique

One of the most fundamental segmentation technique is edge detection. It usually involves two stages. The first one is edge enhancement process that requires the evaluation of derivatives of the image and usage of gradient or Laplacian operators. The second stage involves selection and combination of edge map pixels using boundary detection, edge linking and grouping of local edges. This stage can be viewed as a search for optimal con-figuration of pixels that better approximate edges. Several approaches applied GA-based search for optimal configuration of edge pixels.

In, possible edge configuration S is encoded as chromosome. Each chromosome consists of a K2 bits string, where K represents the dimension of an image I. Each bit shows the presence of an edge pixel in the image I. Algorithm evaluates each chromosome by using a cost function. The form of the point cost function is a linear combination of five weighted point factors [12]. It includes fragmentation, thickness, local length, region similarity and curvature. These factors are evaluated for each pixel in its local neighbourhood of MxM window.

Fragmentation describes local edge discontinuities. Penalty for fragmentation is assigned to define the endpoints of the edge. Pixel is considered as an endpoint if it has only one neighbour or is isolated at all. Image fragmentation into small portions makes the algorithm to be more robust. As small portions of image are evaluated separately, they can converge quicker than others. In such a way, converged portions are not changed by global crossover or mutation. Predefined mutations allow to drive a portion of edge map more directly to the goal than random changes.

Thresholding Technique

The simplest method of image segmentation is called the thresholding method. This method is based on a clip-level (or a threshold value) to turn a gray-scale image into a binary image. The key of this method is to select the threshold value (or values when multiple-levels are selected). Several popular methods are used in industry including the maximum entropy method, k-means clustering can also be used.

During the thresholding process, individual pixels in an image are marked as "object" pixels if their value is greater than some threshold value (assuming an object to be brighter than the background) and as "background" pixels otherwise. This convention is known as threshold above. Variants include threshold below, which is opposite of threshold above; threshold inside, where a pixel is labelled "object" if its value is between two thresholds; and threshold outside, which is the opposite of threshold inside (Shapiro, et al. 2001:83). Typically, an object pixel is given a value of "1" while a background pixel is given a value of "0." Finally, a binary image is created by coloring each pixel white or black, depending on a pixel's labels.

Histogram based Segmentation

Histogram-based methods are very efficient when compared to other image segmentation methods because they typically require only one pass through the pixels. In this technique, a histogram is computed from all of the pixels in the image, and the peaks and valleys in the histogram are used to locate the clusters in the image.[1] Color or intensity can be used as the measure.

Graph Partitioning Method

Graph partitioning is a fairly new and promising approach to perceptual grouping or image segmentation. It treats image segmentation as a graph partitioning problem. The basic scheme is to construct a graph with edge weights from the information contained in the individual pixels of a digital image. That graph is then partitioned following a global criterion. It thus partitions or segments an image from a global point of view.

Region Growing Methods

This technique adopts segmentation by finding coherent regions (pixel similarities). It is guaranteed (by definition) to produce coherent regions. Linking edges, gaps produced by missing edge pixels, etc. are not an issue. It works from the inside out, instead of the outside in. The question of which object a pixel belongs to is immediate, not the result of point-in-contour tests. Suppose that we start with a single pixel p and wish to expand from that seed pixel to fill a coherent region.

Let's define a similarity measure S(i, j) such that it produces a high result if pixels i and j are similar and a low one otherwise. First, consider a pixel q adjacent to pixel p. We can add pixel q to pixel p's region iff S(p, q) > T for some threshold T. We can then proceed to the other neighbors of p and do likewise. Suppose that S(p, q) > T and we added pixel q to pixel p's region. We can now similarly consider the neighbours of q and add them likewise if they are similar enough. If we continue this recursively, we have an algorithm analogous to a "flood fill" but which works not on binary data but on similar greyscale data.

Watershed Transformation Method

The watershed transformation considers the gradient magnitude of an image as a topographic surface. Pixels having the highest gradient magnitude intensities (GMIs) correspond to watershed lines, which represent the region boundaries. Water placed on any pixel enclosed by a common watershed line flows downhill to a common local intensity minimum (LIM). Pixels draining to a common minimum form a catch basin, which represents a segment.

Compression Based Methods

Compression based methods postulate that the optimal segmentation is the one that minimizes, over all possible segmentations, the coding length of the data. [3][4] The connection between these two concepts is that segmentation tries to find patterns in an image and any regularity in the image can be used to compress it. The method describes each segment by its texture and boundary shape. Each of these components is modeled by a probability distribution function and its coding length is computed as follows:

1. The boundary encoding leverages the fact that regions in natural images tend to have a smooth contour. This prior is used by huffman coding to encode the difference chain code of the contours in an image. Thus, the smoother a boundary is, the shorter coding length it attains.

2. Texture is encoded by lossy compression in a way similar to minimum description length (MDL) principle, but here the length of the data given the model is approximated by the number of samples times the entropy of the model. The texture in each region is modeled by a multivariate normal distribution whose entropy has closed form expression. An interesting property of this model is that the estimated entropy bounds the true entropy of the data from above. This is because among all distributions with a given mean and covariance, normal distribution has the largest entropy. Thus, the true coding length cannot be more than what the algorithm tries to minimize.

For any given segmentation of an image, this scheme yields the number of bits required to encode that image based on the given segmentation. Thus, among all possible segmentations of an image, the goal is to find the segmentation which produces the shortest coding length. This can be achieved by a simple agglomerative clustering method. The distortion in the lossy compression determines the coarseness of the segmentation and its optimal value may differ for each image. This parameter can be estimated heuristically from the contrast of textures in an image

According to the scholars TIANZI ZIANG, FAGUO YANG in their research paper conclude that (A Parallel Genetic Algorithm For Cell Image Segmentation [1]), Parallel Genetic Algorithm has demonstrated to be more successful in the optimization than classical genetic algorithm in there work for blood cell image segmentation under severe noise.

The basic algorithm for parallel genetic algorithm can be described as below:

1. Define a suitable representation and genetic operators, generate randomly a population of candidate solutions and partition it into several subpopulations; decide a migration strategy for share individuals between the subpopulations.

2. Each subpopulation executes the step 3 and 4.

3. Self-evolve based on the chosen genetic operators: selection, crossover, mutation, local hill-climbing.

4. Send the best individuals to the neighbouring subpopulations based on the migration strategy, receive their best ones and replace the worst ones of the subpopulation.

5. Determine whether the stopping criteria are satisfied. If satisfied, stop the iteration; otherwise go step 2.

In this paper, they have proposed a novel approach to cell image segmentation under severe noise conditions by combining kernel-based dynamic clustering and a parallel genetic algorithm. In there algorithm, they make use of not only the edge information but also the shape information of the cell contour that the cell boundary has an ellipse-like shape.

By using parallel genetic algorithm as optimizer, they achieved not only a more accurate solution but also a speedup because of several processors sharing the population evaluations. The results indicate a promising direction for further research into automatic initialization, which is especially important for designing automatic algorithm in biomedical applications.

Kanchan deshmukh and Ganesh shinde used fuzzy min-max clustering approach [2] and Concluded that the segments in images are found automatically based on adaptive multilevel threshold approach and FMMN clustering algorithm. The neural network with multisigmoid function tries to label the objects with its original color even after segmentation. This system does not require a prior information about number of objects in the image.

Furtado, Cai1 & Xiaobo at China University of Geosciences [3], performed supervised classification using genetic algorithm and inferred that the use of different number of classes to classify an image is not that effective once we can note that the pixels in some of the images--same image and different classes--were not classified.

S. Chabrier, C. Rosenberger, B. Emile [4] proposed optimization based imaged segmentation through genetic algorithms, they show 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, they show that this approach can either be applied for grey-levels or multi-components images in a supervised context or in an unsupervised one.

[FIGURE OMITTED]

L. Tang, L. F. Tian, B.L. Steward [5] (Color Image Segmentation with Genetic Algorithm for In-Field Weed Sensing) worked to develop machine vision-based weed detection technology for outdoor natural lighting conditions. Supervised color image segmentation using a binary-coded genetic algorithm (GA) identifying a region in Hue-Saturation-Intensity (HSI) color space (GAHSI) for outdoor field weed sensing was successfully implemented. Images from two extreme intensity lighting conditions, those under sunny and cloudy sky conditions, were mosaicked to explore the possibility of using GAHSI to locate a plant region in color space when these two extremes were presented simultaneously. The GAHSI result provided evidence for the existence and separability of such a region. In their experiment, GAHSI performance was measured by comparing the GAHSI segmented image with a corresponding hand-segmented reference image. When compared with cluster analysis-based segmentation results, the GAHSI achieved equivalent performance.

Mohamad Awad, Kacem Chehdi, and Ahmad Nasri developed a new multi-component image segmentation method using a nonparametric unsupervised artificial neural network called Kohonen's self organizing map (SOM) and hybrid genetic algorithm (HGA).SOM is used to detect the main features that are present in the image; then, HGA is used to cluster the image into homogeneous regions without any a priori knowledge.The multi component features of an image were extracted by using SOM-HGA algorithm and were compared to those obtained by ISODATA algorithm. It was observed that the results obtained by applying SOM and HGA method to satellite imaging are more robust and efficient than those obtained with ISODATA. SOM-HGA efficiency increases slightly with image resolution; the overall average efficiency of SOM-HGA is greater than 90%. However, the efficiency of ISODATA degrades slightly with the increase of image resolution. [6]

Segmentation of medical images is challenging due to poor image contrast and artifacts that result in missing or diffuse organ/tissue boundaries. Payel Ghosh and Melanie Mitchell used a level set function to represent the segmenting curve, which is evolved using a genetic algorithm (GA). Shape and textural priors derived from manually segmented images are used to constrain the evolution of the segmenting curve over successive generations. The algorithm developed here evolves a segmenting contour by incorporating both texture and shape information to extract objects without prominent edges. [7]

Conclusion

The use of genetic algorithms in image segmentation provides us the better way to deal with the color images for their study and analysis. Genetic algorithms are a commonly used approach which aims to minimize the complexity in dealing with the color pixel to separation and also to optimise the parameters of existing image segmentation algorithms. The major concept that helps succeding this technique deals with the minutely distinguished segments or extracting boundary values to provide with an easy identifiable image. Basically decisions are choosing a method of segmentation to which genetic algorithms will be applied, finding a fitness function and optimized threshold value which lies between the reliable range and also that is a good measure of the quality of image segmentation and finding a meaningful way to represent the chromosomes. The desire for improvement after the GA reached a near optimal stage, led the authors to put some efforts on adaptively adjusting the mutation rate. Applications of GAs in clustering and grouping problems are intensively described in [8]. In the present approach, grey level intensities of RGB image channels are considered as feature vectors, and the k-mean clustering model (J.MacQueen, 1967) is then applied as a quantitative criterion (or GA objective fitness function), for guiding the evolutionary algorithm in his appropriate search. Since the k-mean clustering model allows to minimize the internal feature variance of each colour cluster (or the maximisation of the variances between different colour clusters [9]), natural and homogeneous clusters can emerge if the GA is properly coded.

References

[1] A Parallel Genetic Algorithm for Cell Image Segmentation Tianzi Jiang, Faguo Yang, and Yong Fan. National Laboratory of Pattern Recognition, Institute of Automation Chinese Academy of Sciences, Beijing 100080, P. R. China

[2] Adaptive Color Image Segmentation Using Fuzzy Min-Max Clustering Kanchan Deshmukh, Member IAENG, Ganesh Shinde.

[3] Digital image processing:supervised classification using genetic algorithm in MATLAB toolbox:Joaquim Jose Furtado1*, Zhihua Cai1 & Liu Xiaobo1 China University of Geosciences, 388 LuMo road, Wuhan, Hubei, P.R. China. Zip code 430074

[4] S. Chabrier, C. Rosenberger, B. Emile Laboratoire Terre-Oc'ean Universit e de la Polyn'esie francaise B.P. 6570 98702 FAA'A, Tahiti--Polyn'esie Franaise, Laboratoire GREYC ENSICAEN--Universit'e de Caen--CNRS 6 Boulevard Mar'echal Juin, 14000 Caen cedex, France EURASIP journal on Video and Image processing (2008) 1-23

[5] Color Image Segmentation with Genetic Algorithm for In-Field Weed Sensing

[6] Multicomponent Image Segmentation Using a Genetic Algorithm and Artificial Neural Network Mohamad Awad, Kacem Chehdi, and Ahmad Nasri

[7] Segmentation of Medical Images Using a Genetic Algorithm Payel Ghosh Dept. of ECE Portland State University Portland, OR 97207 payel@pdx.edu Melanie Mitchell Dept. of Computer Science Portland State University Portland, OR 97207 mm@cs.pdx.edu

[8] Falkenauer, E., 1998, Genetic Algorithms and Grouping Problems, John Wiley & Sons, Boston.

[9] Ramos, V., 1997, Evolution and Cognition in Image Analysis, MSc Thesis (in Portuguese), 230 pp., Instituto Superior Tecnico--IST, Lisbon, December 1997.

Prateek Gupta, Sargam Saxena, Sonali Singh, Saumya Dhami and Vijai Singh

Computer Science Department, IMS Engineering College, Ghaziabad, U.P., India E-mail: prateekguptacs@yahoo.com, saxenasargam143@gmail.com, sonali_singh050@yahoo.com, sd.0041.g3@gmail.com, vijai.cs@gmail.com