Reboost Image Segmentation using Genetic Algorithm

Reboost Image Segmentation using Genetic Algorithm

Shanta H Biradar

Information Science and Engineering Department

Sir M visvesvaraya Institute Of Technology Bangalore-562157.

Abstract:- This paper present a Improved Algorithm for Image Segmentation System for a RGB colour image, and presents a proposed efficient colour image segmentation algorithm based on evolutionary approach i.e. improved Genetic algorithm. The proposed technique, without any predefined parameters determines the optimum number of clusters for colour images. The optimal number of clusters is obtained by using maximum fitness value of population selection. The advantage of this method lies in the fact that no prior knowledge related to number of clusters is required to segment the color image. Proposed algorithm strongly supports the better quality of segmentation. Experiments on standard images have given the satisfactory and comparable results with other techniques.

General Terms:- Digital Image Processing, Algorithm, Image Segmentation,

Genetic Algorithm.

Keywords:- Color image segmentation, Genetic algorithm, Clustering.

1. INTRODUCTION

1. Image Segmentation

   The goal of image segmentation is to cluster pixels into salient image regions, i.e., regions corresponding to individual surfaces, objects, or natural parts of objects. Some works have applied genetic algorithms (GA) to image processing [34] and to segmentation particularly [33, 32, 30, 31]. Indeed, GA is 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. In this paper we deal with various approaches for color image segmentation using GA along with many image segmentation techniques. We have tried to describe general segmentation techniques in this paper. In next section, we illustrate M-estimators algorithm (genetic algorithm), followed by comparison of various approaches led by researchers. Finally we end our work by giving the conclusion and perspectives.

   Image		Feature Extraction		Object
   Segmentation		Process		Recognition
   Process				Process

   Image		Feature Extraction		Object
   Segmentation		Process		Recognition
   Process				Process

   Genetic Object

   Algorithm Learning Model

   Segmentatio for for new Acquisition

   n Parameter Parameter Object and

   Set Adaptation Feature Refinement

   Fig.1: Flow Chart of Image Processing System

2. 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, l length of chromosome x.

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

3. Repeat until N offsprings are created:

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

   2. 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.

Begin Optimization

Generate Random Population

Calculate Fitness (x)

Form an Offspring yi

Form an Offspring yi

Select Pair of Chromosome

N

Done

?

Y

P. Scheunders [37] proposed a genetic c-means algorithm which is an improvement to c-means clustering algorithm combining it with genetic algorithm. It is shown that this algorithm is less sensitive to the initial conditions than CMA. Furthermore GCMA is compared to several classical color image quantization algorithms, and its performance is shown to outperform the others, an effect which affects the visual image quality.

The GA-based GAHSI segmentation scheme [23] is a novel and simple approach to robustly segment an outdoor field image into plant and background regions under variable lighting conditions. The GAHSI obtained an equivalent segmentation performance to that obtained by applying cluster analysis to images acquired under specific lighting conditions. To further improve segmentation robustness, different imaging devices and color transformations as well as GA coding and operators need to be investigated in future research.

Li Zhuo et al [38] presented a mew GA based wrapper feature selection method GA-SVM for hyper-spectral data. The results showed that the GA-SVM method could significantly reduce the computation cost while improving the classification accuracy.

N END Replace Old

? Population

Y

End Optimization

Fig.2: Flow Chart of Genetic Algorithm

1. LITERATURE REVIEW

   Segmentation of a colour image composed of different kinds of texture regions can be a hard problem, namely to compute for an exact texture fields and a decision of the optimum number of segmentation areas in an image when it contains similar and/or unstationary texture fields. In this work, many researchers have proposed their algorithms for the same.

   Vitorino Ramos, Fernando Muge [22] proposed an improvement of the k-means clustering algorithm. This algorithm uses minimum distance criteria as the fitness function. The minimisation is based on the different belonging combinations, of all points in the feature space. Naturally that, such task will be simply if the number of colours in one image to segment is low; however for high number of points in this 3D colour space (i.e., the different number of colours) this minimisation is hard to compute. The respective computer time for segmentation were 14.96, 12.76 and 37.02 minutes when string lengths were 124, 64 and 468 bits long.

   ISODATA algorithm [28] proposed by Mohamad Awad, Kacem Chehdi, and Ahmad Nasri has some further refinements by splitting and merging of clusters. Clusters are merged if either the number of members (pixel) in a cluster is less than a certain threshold or if the centres of two clusters are closer than a certain threshold. Clusters are split into two different clusters if the cluster standard deviation exceeds a predefined value, and the number of members (pixels) is twice the threshold for the minimum number of members. 2) ISODATA is the only unsupervised classification method that is used with ERDAS IMAGINE.

   The number of bands used for classification was reduced from

   <>198 to 13, while the classification accuracy increased from 88.81% to 92.51%. The optimized values of the two SVM kernel parameters were 95.0297 and 0.2021, respectively, which were different from the default values as used in the ENVI software.

2. GENETIC ALGORITHM BASED CLUSTERING

   The searching capability of GAs can be used for the purpose of appropriately clustering a set of unlabeled points in N-dimension into K clusters [1]. In our proposed scheme, the same idea can be applied on image data. We consider a colour image of size mxn and every pixel has Red, Green and Blue components. The basic steps of the GA-clustering algorithm for clustering image data are as follows:

   1. Encoding

      Each chromosome represents a solution which is a sequence of K cluster centres. For an N dimensional space, each cluster centre is mapped to N consecutive genes in the chromosome. For image datasets each gene is an integer representing an intensity value of the three components Red, Green and Blue.

   2. Population initialization

      Population is initialized in various rounds randomly and in each round the best chromosome survives for the next round processing.

   3. Fitness computation

      The fitness computation is accomplished in two steps. First, the pixel dataset is clustered according to the centres encoded in the chromosome under consideration, such that each intensity value

      xi(r,g,b) of colour image combined with three component red, green and blue (24 bit), i = 1, 2, …, mxn is assigned to cluster

      with centre zj(r,g,b), j = 1, 2, …, K,

      If

      The next step involves adjusting the values of the cluster centres encoded in the chromosome, replacing them by the mean points of

      the respective clusters. The new centre Zi(r,g,b) for the cluster Ci is given by

      Now the fitness metric is computed by calculating the sum of intra cluster spread, i.e. finding the sum of Euclidean distance between the pixels and their respective cluster, given by

      The fitness evaluation of a chromosome is given by –

      f = 1/M ..(1), thus our aim is to minimise the value of f.

   4. Selection

      Initially the fittest chromosome in every round of random population generation is moved to next generation, in the subsequent processing the fittest chromosome directly holds the 40% of the entire population and the rest of the population is hold by the chromosomes in the decreasing order of there fitness value.

   5. Termination Criterion

   We perform the population generation, fitness computation, crossover and selection for a predetermined number of generations, thus the algorithm is computed for the fixed number of generations and the best solution seen in the entire generation proceeds to final result.

   Table 1. Analysis of Various Algorithms

   	Population size	Selection	Crossover		Mutation	Fitness criteria	Stopping criteria	Coding	Characteris- tics	Future work
   [22] Parallel	100	Fitness	One point	Substitutio		Distributio	Threshold	Integer	Using a	Automatic
   Genetic Algorithm		proportio nal Model	crossover- Random selection of the	n of a randomly generate integer		n function	technique based on entropy of distributed	(Chromoso me length =5)	region based energy function, the active	Initialization
   			point Crossover probabilit	Mutation probability = 0.1			function		surface converges quickly
   			y=0.5
   [23] GAHSI	48	Local	Single	Insertion		Weighted	Threshold	Binary	Use of	Adaptive
   Algorithm		tourname nt selection over roulette wheel	point crossover Crossover probabilit y=0.8	Mutation probability = 0.03		average function	technique based on UTOPIA parameter, if it failed for		different imaging devices and color transformati ons	adjustment of mutation rate
   		method					consecutive
   							5 times
   [24]	6	Normaliz	Arithmeti	Non		Supervised	Stability of	Based on	Special	Implementati
   Optimizatio		ed	c	uniform		evaluation	standard	genotype	focus on	on of priori
   n Algorithm		geometri	crossover,	mutation,		function	deviation		evaluation	knowledge
   		c ranking	Crossover	Mutation		involving	of the		metrics
   		selection	probabilit	probability		classificatio	evaluation
   		method,	y=0.6	=0.05		n rate	criterion
   		Selection
   		probabili
   		ty = 0.08

   [25, 26]	31	Expected	Unordere	Remove	Linear	Threshold	GA+SA+H	Distributed	Removal of
   Hybrid Genetic Algorithm		value plan and Elitist plan are two selection strategies	d Subseque nce Exchange Crossover (USXX) and Ordered Crossover , Crossover	and Reinsert, Mutation Probabilit y=0.03	Scaling function	Technique based on hybrid function	GAPSA (Genetic Algorithm, Sequential Algorithm, Hybrid Genetic Algorithm with Parallel Simulated	environment with Remote Method Invocation concept	ambiguity in the population size. And more than two meta- heuristic algorithms may be interpreted to
   			Probabilit y=0.6				Annealing		improve the solution
   									space.
   [27]	100	Proportio	Crossover	Mutation	average	Sub-	Based on	GA	To reolve
   Adaptive		nal	Probabilit	Probabilit	fitness	averaging	Schema	repeatedly	the problem
   Genetic		selection	y, 0.5 < pc	y, 0.001 <	value f –	the fitness	Theorem	converges to	of getting
   Algorithm		method	< 1.0	pm < 0.05	maximum fitness value (fmax f)	value	i.e. Binary Coding	almost same fitness values	stuck in the local optimum when the population is
   									scattered.
   [28]	90	Roulette	Cluster	Random	Objective	Stability of	Bit level	Usage of	Parallel
   ISODATA		wheel	centre	substitutio	Function	fitness	coding	multicompo	cooperation
   Algorithm		method	replaceme	n		values for		nent	with more
   			nt method	Mutation		20		features	segmentation
   			Crossover	probability		iterations			methods,
   			probabilit	= 0.1					such as FCM
   			y = 0.6
   [36]	30	Roulette	Single	Substitutio	Cluster	Fixed no.	Integer	No prior	Work on
   Dynamic		Wheel	point	n	validity	of		knowledge	generation of
   GA		selection	crossover	Mutation	criteria	iterations		required	optimal no.
   Based Clustering (GADCIS)			Crossover probabilit y=0.9	probability =0.01	based on Gaussian distribution				of cluster centres
   [37] Genetic	No.	Roulette	One point	Insertion	Inverse of	Stability of	Binary or	Develops a	Data
   c-means	Of	wheel	crossover	of single	MSE	MSE	other	hybrid	clustering
   Clustering (GCMA)	Clu ster S	selection	Crossover probabilit y-=0.8	bit Mutation probability =0.05				algorithm combining CMA and GA	methods
   [38] GA	20	Stochasti	Single	Scale=1.0	Rank	Fixed no.	Binary	Classifies	Improvement
   (based on SVM)		c uniform	point crossover Crossover probabilit y=0.8	Shrink=1. 0	(fitness normalizati on)	of iterations		the given input data based on a set of training examples	in classification accuracy
   			scattered
   [39] Elastic	200	3 level	One point	Substitutio	Normalized	Fitness	Integer	GA	Deviation of
   Contour		contour	crossover	n	histogram	value		repeatedly	no. of
   Method		function	Crossover probabilit y=0.6	Mutation probability =0.0001	function	ranging around 500-570		converges to almost same fitness values	variants

3. PROPOSED WORK

The proposed new segmentation algorithm can produce a better result according to the segments created by optimal number of dynamic clusters. We consider a colour image f of size m x n. The proposed algorithm is:

1. Repeat step 2 to 4 till fixed no. of generations.

2. Randomly generate the cluster set using the randperm function.

3. Each pixel of the image is associated with the cluster number using min distance function which uses Euclidean formula as criteria.

4. We calculate fitness value of the chromosome by adding the distances of each pixel.

5. The chromosome with maximum fitness value is considered as the solution.

   1. RESULT

      Testing of proposed algorithm with standard color images, it has given satisfactory results, a tabular comparison between different clustering techniques are presented below. Column 2 of table gives the optimal range of clusters as proposed by [12]. Assumptions for segmenting the images are as follows: 20 rounds are processed for generating the initial population each generating random cluster from range 2 to 8 in RGB space, from each round cluster with maximum fitness value is passed to next generation and at each next iteration fitness value is being compared with fitness value of next cluster set. Each next generation contains the maximum fitness value, cluster set and also the cluster numbers. An iteration to 20 generations has been done to create the final results.

      Original Lena image Lena image by proposed Segmentation method

      Original Mandril image Mandril image by proposed

      Segmentation method

      Fig.3: Original Image and Segmented Image of Lena & Mandril

      Table 2. Comparison of different Image Segmentation Algorithm

      Image	Optimal range	Proposed method	DCPSO using v	SNOB
      Mandril	5 to 10	5.32	6	39
      Lena	5 to 10	4.47	6.85	31
      Peppers	6 to 10	6.13	6.25	42
      Jet	5 to 7	4.39	5.3	22

   2. FUTURE WORK

      The preceding sections provide an overview of the field of image segmentation, the review shows that many current algorithms are able to produce reasonable results on images of moderate complexity; several of these algorithms are efficient enough that they can be used as a pre-processing stage for higher level vision tasks such as recognition and tracking. The GAHSI algorithm

      [23] has its own characteristics; still it has scope of improvement in adaptive adjustment of mutation rate. Elastic contour method
      [39] can be improved by automatic deviaton of no. of variants. In ISODATA algorithm [28], a parallel cooperation with various segmentation algorithms like FCM is required for further improvement. Still, there is some scope of improvement. Reviewing the existing algorithms, we conclude that absence of prior knowledge about the images contents, it is in general not possible to determine how many regions are required for a reasonable segmentation. This problem manifests in two forms, Under-segmentation, which occurs when parts of the image that actually correspond to different objects, or to an object and the background, are assigned to the same region; and over- segmentation, which occurs when parts of the image corresponding to a single object are split apart.

   3. CONCLUSION

      Genetic Algorithm has many advantages in obtaining the optimized solution. It was proved to be the most powerful optimization technique in a large space. Genetic algorithm allows performing robust search for finding the global optimum. The result of the optimization depends on the chromosome encoding scheme and involvement of genetic operators as well as on the fitness function. However the quality of image segmentation can be improved by selecting the parameters in an optimized way. The desire for improvement after the GA reached a near optimal stage, led the authors to put some efforts on implementation of prior knowledge applications of GAs in clustering and grouping problems are intensively described in [29]. 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.. In present scenario, various fast algorithms for speeding up the process of template matching are being implemented such as M-estimators for dealing with outliers. This fast algorithm ensures finding the global minimum of the robust template

      matching problem in which a non-decreasing M-estimator serves as an error measure.

   4. REFERENCES

1. W. Frei and C. Chen, "Fast Boundary Detection: A Generalization and New Algorithm," IEEE Trans. Computers, vol. C-26, no. 10, pp. 988-998, Oct. 1977.

2. J. Canny, A computational approach to edge detection,

   IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 8, No. 6, pp. 679-698, Nov. 1986.

3. R. C. Gonzalez and R. E. Woods, Digital Image Processing. Upper Saddle River, NJ: Prentice-Hall, 2001, pp. 572-585.

4. W. K. Pratt, Digital Image Processing. New York, NY: Wiley- Interscience, 1991, pp. 491-556.

5. Suryakant, Neetu Kushwaha, Edge Detection using Fuzzy Logic in Matlab, ISSN: 2277 128X, Volume 2,

   Issue 4, April 2012.

6. Gonzalez and Woods, "Digital image processing", 2nd Edition,

Computational Intelligence Research ISSN 0973-1873 Volume 8, Number 1 (2012), pp. 17-25 © Research India Publications.

1. Utkarsh Kumar Shah and Prof. A. Mukherjee, BTP REPORT Image segmentation by region growing, April

   15, 2010.

2. Shilpa Kamdi1, R.K.Krishna2,1,2-Rajiv Gandhi College of Engineering,Research and Technology, Image Segmentation and Region Growing Algorithm , feb 1,

   2012,

3. S.Beucher, F.Meyer,The morphological approach to segmentation: The watershed transform, in

   Mathematical Morphology Image Processing, E. R. Dougherty, Ed. New York Marcel Dekker, 1993, vol. 12, pp. 433481.

4. A. N. Moga, M. Gabbouj, "Parallel image component labeling with watershed transformation, IEEE Trans.

   Pattern Anal. MachineIntell. vol. 19, pp. 441450. J. M

   Gauch, Image segmentation and analysis via multi-scale gradient watershed hierarchies, IEEE Trans Image

   Processing, vol. 8, pp. 6979, 2000

5. O. F. Olsen, M. Nielsen, Multi-scale gradient magnitude watershed

prentice hall, 2002.

1. Kenneth R. Castelman Press, 2003.

   , "Digital image processing", Tsinghua Univ

   segmentation, in ICIAP 979th Int Conference on Image Analysis and Processing, ser. Lecture Notesin Computer Science. Berlin,

2. Du Gen-yuan,Miao Fang,Tian Sheng-li,Guo Xi-rong.,"Remote Sensing Image Sequence Segmentation Based on the Modified Fuzzy C-means", Journal of Software, Vol. 5, No. 1, PP.28-35, 2009.

3. N. Senthilkumaran and R. Rajesh, Edge Detection

   Techniques for Image Segmentation – A Survey, Proceedings of the International Conference on Managing Next Generation Software Applications (MNGSA-08), 2008, pp.749-760.

4. Sharmishtha Mitra, Amit Mitra and Debasis Kundu, Genetic algorithm and M-estimator based robust sequential estimation of parameters of nonlinear sinusoidal signals, Commun Nonlinear Sci Numer

   Simulat, October 2010.

5. Jiun-Hung Chen, Chu-Song Chen, and Yong-Sheng

   Chen, Fast Algorithm for Robust Template Matching With M- Estimators, IEEE TRANSACTIONS ON

   SIGNAL PROCESSING, VOL. 51, NO. 1, JANUARY 2003.

6. Jun Zhang, Kitakyushu Jinglu Hu. Image Segmentation

   Based on 2D Otsu Method with Histogram Analysis Computer Science and Software Engineering, 2008 International Conference

7. Leo Grady and Eric L. Schwartz Isoperimetric Graph Partitioning for Image SegmentationPattern Analysis and Machine Intelligence, IEEE Transactions.

8. Pateek Gupta, Sargam Saxena, Sonali Singh, Saumya Dhami and Vijai Singh, Color Image Segmentation: A State of the Art Survey, International Journal of

Germany: Springer-Verlag, 2001, vol. 1310, pp. 613.

1. JL. Vincent, Morphological gray scale reconstruction in image analysis: Applications and efficient algorithms,

   IEEE Trans. Image Processing, vol. 2, 1993.

2. Mandeep Kaur, Gagandeep Jindal, Medical Image Segmentation using Marker Controlled Watershed

   Transformation, IJCST Vol. 2, Issue 4, Oct . – Dec. 2011.

3. Faguo Yang 3, Tianzi Jiang and Yong Fan , A Parallel Genetic Algorithm for Cell Image Segmentation 1;2, 4 National Laboratory of Pattern Recognition, Institute of Automation Chinese Academy of Sciences, Beijing 100080, P. R. China David J. Evans 5 Department of Computing, Nottingham Trent University Nottingham, NG1 4BU, UK.

4. L. Tang, L. Tian, B. L. Steward , COLOR IMAGE

   SEGMENTATION WITH GENETIC ALGORITHM FOR IN- FIELD WEED SENSING.

5. S. Chabrier, C. Rosenberger, B. Emile Laboratoire Terre-Oc´ean Universit´e de la Polyn´esie francaise B.P. 6570 98702 FAAA, 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.

6. Thamilselvan Rakkiannan and Balasubramanie Palanisamy, Hybridization of Genetic Algorithm with Parallel Implementation of Simulated Annealing for Job Shop Scheduling American Journal of Applied Sciences 9 (10): 1694-1705, 2012.

7. Kikuo Fujita, Shinsuke Akagi and Noriyasu Hirokawa,

   Hybrid Approach for Optimal Nesting Using a Genetic Algorithm and a Local Minimization Algorithm Osaka University Suita, Osaka, JAPAN.

8. M. Srinivas, and L. M. Patnaik, Fellow, Adaptive Probabilities of Crossover and Mutation in Genetic

   Algorithms IEEE TRANSACTIONS ON SYSTEMS, MAN AND CYBERNETICS, VOL. 24, NO. 4, APRIL 1994.

9. Mohamad Awad, Kacem Chehdi, and Ahmad Nasri , Multicomponent Image Segmentation Using a Genetic

   Algorithm and Artificial Neural Network, IEEE GEOSCIENCE AND REMOTE SENSING LETTERS, VOL. 4, NO. 4, OCTOBER 2007.

10. Falkenauer, E., Genetic Algorithms and Grouping Problems, John Wiley & Sons, Boston, 1998.

11. Peng-Yeng Yin, A fast scheme for optimal thresholding using genetic algorithms Signal Processing, (72):8595, 1999

12. Minglun Gong and Yee-Hong Yang, Genetic-based multiresolution color image segmentation Vision

    Interface, pages 141148, 2001.

13. D.N. Chun and H.S. Yang, Robust image segmentation using genetic algorithm with a fuzzy measure Pattern

    Recognition, 7(29):11951211, 1996.

14. B. Bhanu and S. Lee, Genetic Learning for Adaptive Image Segmentation Kluwer Academic Press, 1994.

15. Y. Delignon A. Marzouki and W. Pieczynski,

    Estimation of generalized mixtures and its application in image segmentation IEEE Transactions on Image

    Processing, 6(10):13641375, October 1997.

16. Zhenyu Wu and Richard Leahy, An Optimal Graph theoretic approach to data clustering: Theory and its

    Application to Image Segmentation, IEEE Transactions on pattern analysis and machine intelligence, Vol. 15 No. 11, Nov. 1993.

17. Amiya Halder and Nilavra Pathak, An Evolutionary

    Dynamic Clustering Based Colour Image Segmentation, International Journal of Image Processing (IJIP), Volume (4): Issue (6).

18. P. Scheunders, A GENETIC C-MEANS CLUSTERING ALGORITHM APPLIED TO COLOR IMAGE QUANTIZATION, Vision Lab, Dept. of Physics,

    RUCA University of Antwerp, Groenenborgerlaan 171, 2020 Antwerpen, Belgium.

19. Li Zhuo, Jing Zheng, Fang Wang, Xia Li, Bin Ai and Junping Qian, A GENETIC ALGORITHM BASED

    WRAPPER FEATURE SELECTION METHOD FOR CLASSIFICATION OF HYPERSPECTRAL IMAGES

    USING SUPPORT VECTOR MACHINE, School of

    Geographical sciences, Guangzhou University, Guangzhou 510006, China) Commission VII, WG VII/3.

20. S.Cagnoni, A.B. Dobrezeneicki, R.Pauli, J.C. Yanch, Genetic algorithm based interactive segmentation of 3D medical images.