On the segmentation of two dimensional images using genetic algorithm

On the segmentation of two dimensional images using genetic algorithm

Aiswariya G

Dept. of Computer Applications, Bharathiar University, Coimbatore, India aisguna@gmail.com

R. Rajeswari ,

Dept. of Computer Applications, Bharathiar University, Coimbatore, India rrajeswari@rediffmail.com

Abstract Image segmentation is one of the most important stages in image processing. Lot of methods are available in the literature to segment two-dimensional (2D) images. But the success of every method is based on characteristics such as resolution and accuracy. Most of these methods require prior knowledge which is difficult to obtain. In this paper, the application of genetic algorithm for image segmentation is studied in detail. Various genetic algorithm based image segmentation techniques available in the literature are described. An implementation of genetic algorithm based image segmentation is carried out and the results are compared with other conventional techniques used for segmentation

Keywords gray scale image, segmentation, genetic algorithm.

1. INTRODUCTION

   Image segmentation is one of the important stages used in image processing applications [1]. Image segmentation is the process of dividing a digital image into sub region or set of pixels [12]. The partition represents dissimilar objects in the image based on some similarity measures such as texture and color. More specifically, it is the process of assigning a label to pixel in an image. The similar label pixels are sharing some common characteristics. The final result of image segmentation is some set of regions that group wrap the entire image. Image segmentation extracts the objects of interest and is vital for image analysis. It is one of the most important and liveliest topics of research and a huge number of image segmentation techniques have been proposed [16]. The main objective of segmentation is to make simpler and meaningful representation of an image so that it is easy to analyze the image or to locate regions and boundaries in an image [17].

   Image segmentation is a challenge and various techniques have been proposed to efficiently and automatically perform segmentation. Recently, genetic algorithms have been used for image segmentation due to their ability to identify and discriminate features of image powerfully [2].The genetic algorithm (GA) is a type of soft computing method which derives the characteristics from evolution. Genetic algorithm requires an initial population. Each Individual in the population is represented by a set of chromosomes.

   Genetic algorithms basically contain three key processes, which are selection, crossover, and mutation [8]. These stages

   are applied repeatedly to the initial population to obtain a better population for the relevant application. The steps are repeated until a best individual for the concerned application is obtained or until a maximum number of iterations.

   In this paper a review of genetic algorithm based image segmentation techniques is given. Basic genetic algorithm based image segmentation is implemented and the results obtained using this method are compared with some traditional algorithms used for image segmentation. The paper is organized as follows. Section 2 gives the description of image segmentation using genetic algorithm. Section 3 briefly describes various image segmentation techniques based on genetic algorithm available in the literature. Section 4 gives results obtained by segmenting image using genetic algorithm and compares them with the conventional segmentation results. Section 5 gives the conclusion.

2. GENETIC ALGORITHM FOR IMAGE SEGMENTATION

   Genetic algorithm is one of the methods of evolutionary algorithms which produce solutions to optimization problems using a method inspired by natural evolution based on components such as population, mutation, selection and crossover.

   The first stage of the genetic algorithm is to generate the initial population which consists of a set of individuals to give a better solution of the optimization problem. Each candidate has a set of properties. In this stage the solutions are represented either binary values are as integers. The genetic algorithm usually starts from a population of randomly generated individuals. It is an iterative process [13]. The population obtained in each iteration is called a generation. In every generation, the fitness of each individual in the population is evaluated. The fitness values are usually calculated from the current population. Based on the fitness values calculated each individual is modified using mutation to form a new generation. This new generation of candidate set is used in the next iteration of the algorithm [17]. Usually, the algorithm ends when a maximum number of iterations have been performed or when a suitable fitness level has been reached for the population.

   The candidate sets are normally represented as an array. The main advantage of using array to represent the population of the genetic algorithm is that their fixed size facilitates simple crossover operations. The fitness function is defined once. The generated initial population of the solution is

   improved using selection, crossover and mutation operators [2].

   The main stages of genetic algorithm are shown in fig 1.

   Fig. 1. main stages of genetic algorithm

   Genetic Algorithms Population

   In genetic algorithm, the population represents the number of solutions i.e. the number of segmented regions. These individuals are represented by integers which represent the label of the segmented region. Each string is a determined candidate solution. Several individuals are generated randomly which represent the initial population [15]. The fitness function is calculated for every individual during the generations to find the selection priority of individuals. Therefore the individuals who have better fitness values are preferred from the present population based on their fitness values [13]. Then the new population replaces the current population and it is given as input to the next iteration of the algorithm.

   1. Fitness Function

      The fitness function is related to the properties of the region in an image. Mainly the fitness functions have two properties, namely region size and region contrast. Fitness value is calculated for each individual separately. For image segmentation this value is usually based on the summation of every variance dissimilarity distances between the merged region [18].Fitness values is computed to evaluate the quality of each individual. Better fitness values identify better individuals.

   2. Selection Procedure

      The important step during GA generations is how to select individuals from the current population and use them to generate next population. Selection operation directly depends on the quality of an individual. The quality of each individual is measured by fitness function. Individuals with best fitness value are most selected. For image segmentation most widely used selection is Roulette-Wheel selection [19].

   3. Crossover

      Crossover produces the new child/ individual with the help of two parents/ individuals in the previous generation. Two

      individuals are selected and used as a two parents. In crossover operation the random number of genes is swapped between the parents. The main advantage of the crossover is that the generated child is better than its parents. Two widely used crossover techniques image segmentation are one point cross over and two point crossover [20].

      One point crossover to select a crossove point randomly within a chromosome of parents, and then the bits of two parents are interchanged from this point [7].

      Two point crossover to select two crossover points randomly within each parent chromosomes. Genes in the interval of two points are interchanged between two parents [5].

   4. Mutation

      Mutation operation changes the genes/ region labels in an individual. In an image segmentation method using genetic algorithm mutation can be done by merging regions. The regions are selected randomly from the individual. The selected regions are merged together [19].

      The steps involved in the genetic algorithm based image segmentation are given below:

      • An initial population is created from randomly segmented regions of the image.

      • The following steps are repeated until the maximum number of iterations are completed

        • The fitness value for the population is computed based on the dissimilarity measures between the regions.

        • Next generation is created by mating two parents, which are selected based on their fitness values.

        • The crossover function is applied to every pair of individuals of the population to create new generation.

        • The mutation function is applied for every individual in new generation. Regions are selected randomly and merged based on their dissimilarity.

      • Obtain the best individual. This individual has the labels of the segmented regions.

3. VARIOUS GENETIC ALGORITHM BASED IMAGE SEGMENTATION TECHNIQUES

   As mentioned earlier, a number of techniques are proposed for image segmentation for genetic algorithm. This section gives the summary of some of the techniques.

   Vojodi has proposed genetic programming for combining various measures and have proposed a novel measure to evaluate color image segmentation [3]. These are not suitable to estimate all images even from a particular method. These three evaluation measures are used to improve evaluation accuracy, the three evaluations measures are inter-regions disparity and an evaluation measure based on entropy t. A

   large number of data set which consisting of 300 color images is used for testing.

   Abbasgholipour et al. have proposed color image segmentation with genetic algorithm in a raisin sorting system based on machine vision in variable conditions [4].The Genetic algorithm based segmentation method described is an original and simple approach to strongly segment an image of raisin into pet, undesired and background regions under variable conditions.

   Hammouche et al. have proposed a multilevel Automatic thresholding method based on a genetic algorithm for fast image segmentation [7]. A new multilevel thresholding method based on a genetic algorithm is used.

   Manikandan has proposed multilevel thresholding for segmentation of medical brain images using real coded genetic algorithm [5]. The genetic algorithm used the optimum multilevel thresholding. It is based on maximizing the entropy. The multilevel threshold is verified using the statistical performances of the 100 independent runs.

   Lai has proposed a hierarchical evolutionary algorithm for automatic medical image segmentation [6]. It is used to classify the image into appropriate classes automatically and avoid the difficulty of searching the classes. It generates segmentation results which are continuous and smoother.

   Saraswat has proposed leukocyte segmentation in tissue images using differential evolution algorithm [9]. The mice skin sections were stained with H and E (hematoxylin and eosin) staining and were acquired at40m agnification. The

   b)

   d)

   results show that the proposed approach out performs the traditional image Segmentation techniques.

4. EXPERIMENTAL RESULTS

   The general steps associated with image segmentation using genetic algorithm, as described in section 2, is implemented. It is applied for four images which as stored in .jpg format. The images are building, building1 and Lena. The result obtained from genetic algorithm based segmentation is compared with gray level thresholding [2], watershed segmentation [19], and k-means based segmentation [1]. The results obtained for building and building1 images are shown in figures 2, 3 and 4 respectively.

   a)

   c)

   e)

   Fig. 2. a) original image segmentation results obtained using b) gray-level thresholding c) watershed segmentation d) k-means based segmentation and e) genetic algorithm based segmentation

   1. b)

      c) d)

      e)

      Fig. 3. a) original image segmentation results obtained using b) gray-level thresholding c) watershed segmentation d) k-means based segmentation and e) genetic algorithm based segmentation

      b)

      a)

      c) d)

      e)

      Fig. 4. a) original image segmentation results obtained using b) gray-level thresholding c) watershed segmentation d) k-means based segmentation and e) genetic algorithm based segmentation

5. CONCLUSION

This paper gives a detailed study of the image segmentation using genetic algorithm. The general stages involved in the image segmentation using genetic algorithm are described. Various image segmentation techniques using genetic algorithm available in the literature are also described. A general genetic algorithm based image segmentation is implemented and the results are given.

ACKNOWLEDGMENT

The authors are thankful to Bharathiar University for valuable support.

REFERENCES

1. R.C.Gonzalez and R.E. woods,Digital image processing, Pearson Education 2005.

2. L.A.Zadeh Fuzzy Logic, Neural network and soft computing,

   university of California 1992.

3. Hakime Vojodi , Ali Fakhari, Amir Masoud Eftekhari Moghadam A new evaluation measure for color image segmentation based on genetic programming approach Image and Vision Computing 877886 2013.

4. M. Abbasgholipour , M. Omid, A. Keyhani, S.S. Mohtasebi Color

   image segmentation with genetic algorithm in a raisin sorting system

   based on machine vision in variable conditions Expert Systems with

   Applications 36713678 2011.

5. S. Manikandan, K. Ramar, M. Willjuice Iruthayarajan, K.G. Srinivasagan Multilevel thresholding for segmentation of medical brain images using real coded genetic algorithm Measurement 558568 2014.

6. Chih-Chin Lai a, Chuan-Yu ChangA hierarchical evolutionary algorithm for automatic medical image segmentation Expert Systems with Applications 248259 2009.

7. Kamal Hammouche, Moussa Diaf, Patrick Siarry A multilevel automatic thresholding method based on a genetic algorithm for a fast image segmentation Computer Vision and Image Understanding 163175 2008.

8. Motohide Yoshimura, Shunichiro OeEvolutionary segmentation of texture image using genetic algorithms towards automatic decision of optimum number of segmentation areas Pattern Recognition 2041-2054 1999.

9. Mukesh Saraswat n, K.V.Arya,HarishSharma Leukocyte segmentation in tissue images using differential evolution algorithm Swarm and Evolutionary Computation 4654 2013.

10. Erik Cuevas, Daniel Zaldivar, Marco Prez-CisnerosA novel multithreshold segmentation approach based on differential evolution optimization Expert Systems with Applications 52655271 2010.

11. Swagatam Das, Amit KonarAutomatic image pixel clustering with an improved differential evolution Applied Soft Computing 226236 2009.

12. Lo Bosco, G. A genetic algorithm for image segmentation Image Analysis and Processing 262 266 2001

13. Huynh Thi Thanh Binh Improving Image Segmentation Using Genetic Algorithm Machine Learning and Applications 18 23 2012 Maulik U Medical image segmentation using genetic algorithms IEEE Trans Inf Technol Biomed. 166-173

14. Poonam Panwar, Neeru Gulati genetic algorithms for image segmentation using active contours Jurnal of Global Research in Computer Science Volume 4, No. 1 2013

15. Bir bhanu Adaptive image segmentation using genetic algorithm IEEE

    transaction on systems, man, and cybernetics vol 25 no.12 1995.

16. Mantas Paulinas, Andrius Usinskas A survey of genetic algorithms applications for image enhancement and segmentation information technology and control vol.36 No.3 2007

17. Eun Yi Kim , Se Hyun Park Automatic video segmentation using genetic algorithms Pattern Recognition Letters 27 12521265 2006

18. Maryam Gholami Doborjeh Genetic Optimization for Image

    Segmentation

19. Wen-Bing Tao Jin-Wen Tian, Jian Liuimage segmentation by three- level thresholding based on maximum fuzzy entropy and genetic algorithm Pattern Recognition Letters 24 30693078 2003