Journal of Global Research in Computer Sciences
MenuISSN: 2229-371X
ISSN: 2229-371X
Poonam Panwar 1, Neeru Gulati2
|
| Related article at Pubmed, Scholar Google |
Visit for more related articles at Journal of Global Research in Computer Sciences
Genetic Algorithm is a search technique used in computing to find approximate solutions to optimization and search problems. As a search strategy, genetic algorithm has been applied successfully in many fields. Firstly, this paper describes the genetic algorithms evolution process .It then describes the active contours to detect the boundaries of the object whose boundaries are not defined. Then it describes the use of genetic algorithm with active contours in image segmentation.
Index Terms |
| Active Contours, Energy Minimization, Segmentation, Genetic Algorithms, Fitness Function. |
INTRODUCTION |
| Genetic algorithms (GA) are adaptive heuristic search algorithm based on the evolutionary ideas of natural selection and genetic. Genetic algorithm is a method for moving from one population of “chromosomes” to a new population by using a kind of “natural selection” together with the genetic inspired operators of crossover, mutation and inversion. Each chromosome represents a solution of the problem. In a search space, best of them are selected from the solution set available in search space. Each chromosome consists of “genes”, each gene being an instance of a particular “allele” (0 or 1) [1]. Encoding is the process of representing individual genes. The process can be performed using bits, numbers, trees, array, list or any other objects. The encoding depends mainly on solving the problem. |
| After determining the population size and manner of encoding, each solution or chromosome is evaluated. To do this fitness function is used. Fitness function depends on our problem. Based on this fitness function, fitness value is calculated for each chromosome. This fitness value tells us that how close the solution is to solve a particular problem. After the fitness function is determined for each member of the population, genetic operators should be applied on them to prevent premature convergence. These three genetic operators are as follows: |
| Selection operator: |
| Selection is a method that randomly picks chromosomes out of the population according to their evaluation function, the higher the fitness function, more the chances of an individual to be selected. Different selection methods exist for the selection of the best from the population or society. Common selection methods are: |
| a. Roulette wheel selection. |
| b. Rank selection. |
| c. Tournament selection. |
| d. Random selection. |
| e. Boltzmann selection. |
| f. Stochastic Universal sampling |
| Crossover operator |
| Crossover is the process of taking two individuals or parent solutions and producing from them two offspring’s. The reproduction or crossover operator selects a pair of two individuals for mating. A cross site is selected at random along the string length. Finally, the position values are swapped between the two strings following the cross site. It is a simple way how to choose randomly some crossover point and copy everything after the crossover point from the other parent [2]. |
| The various crossover techniques are: |
| a. Single point crossover. |
| b. Two point crossover. |
| c. Multi-point/N-point crossover. |
| d. Uniform crossover. |
| e. Three point crossover. |
| Crossover probability (Pc) is a parameter to describe how often crossover will be performed. If there is no crossover, offspring’s are exact copies of their parents. If there is crossover, the offspring’s are made from parts of both parent’s chromosome. If crossover probability is 100%, then all offspring’s are made by crossover. If it is 0%, whole new generation is made from exact copies of chromosome from all population. Crossover is made in the hope that new chromosome will contain good parts of old chromosomes and therefore the new chromosome will be better [2]. |
| Mutation operator: |
| Mutation, by changing the genes, can produce a new chromosome. Applying the mutation operator in the genetic algorithm saves valuable information of the chromosome which may otherwise be deleted during the execution of the algorithm. It is the insurance policy against the loss of genetic information. |
| The various mutation operators are: |
| a. Flipping. |
| b. Interchanging. |
| c. Reversing. |
| Mutation probability () decides how often parts of a chromosome will be mutated. If there is no mutation, offspring’s are generated immediately after crossover without any change. If mutation is performed, one or more parts of a chromosome are changed. If mutation probability is 100%, whole chromosome is changed. If it is 0%, nothing is changed. |
| To calculate the mutation rate a relation =1/L is used. Here L is the chromosome length. The process of producing a new generation and selecting the best member is repeated continuously until the algorithm’s termination condition is satisfied [2]. Given a clearly defined problem to be solved and a bit string representation for candidate solutions, a simple GA working can be described as given in fig1. |
 |
| A simple GA consists of following steps: |
| a. Start with a randomly generated population of n bit Chromosomes (candidate solution to a problem). b. Calculate the fitness f(x) of each chromosome x in the population. |
| c. Repeat the following steps until n offspring has been created. |
| (a). Select a pair of parental chromosomes from the current population, the probability of selection being an increasing function of fitness. Selection is done with replacement, meaning that the same chromosome can be selected more than once to become a parent. |
| (b). With probability, Crossover the pair at a randomly chosen point to form two offspring. If no crossover takes place, form two offspring that are exact copies of their respective parents. |
| (c). Mutate the two offspring at each locus with probability and place the resulting chromosome in new population. |
| d. Replace the current population with new population. |
| e. Go to step 2. |
| It has been claimed that via the operations of selection successive, crossover and mutation, the GA will converge. Genetic Algorithm can be widely used in the area of image segmentation with active contours. Section II and section III gives the brief introduction about Segmentation and Active Contours respectively |
IMAGE SEGMENTATION |
| Image segmentation refers to the process of partitioning a digital image into multiple segments i.e. set of pixels, pixels in a region are similar according to some homogeneity criteria such as colour, intensity or texture, so as to locate and identify objects and boundaries in an image [4]. The goal of segmentation is to simplify or change the representation of an image into something that is more meaningful and easier to analyze Practical application of image segmentation range from filtering of noisy images, medical Imaging (Locate tumours and other pathologies, Measure tissue volumes, Computer guided surgery, Diagnosis, Treatment planning, study of anatomical structure), Locate objects in satellite images (roads, forests, etc.), Iris Recognition, Fingerprint Recognition, etc. The choice of a segmentation technique over another and the level of segmentation are decided by the particular type of image and characteristics of the problem being considered. The result of image segmentation is a set of segments that collectively cover the entire image or a set of contours extracted from the image. The quality of segmentation depends upon the quality of image. The segmentation is based upon the measurement taken from the image and might be grey level, texture, colour, depth or motion. |
ACTIVE CONTOURS |
| Active contours [5] [6] or snakes or deformable models are computer generated curves that move within the image to find object boundaries under the influence of forces of curve and image itself. One may visualize the active contour as a rubber band of arbitrary shape that is deforming with time trying to get as close as possible to the object contour. It will dynamically move towards object contour by minimizing its energy iteratively and does the segmentation of an object as shown in fig 2. |
 |
| Active contours were first described by Kass [8] in 1988. In this method, first a primary contour is defined close to the edge of the object in mind, and then in order to detect the edge, an energy function is specified for contour through various arithmetic techniques, the edge detection and segmentation process is complete. Unlike most other techniques for finding image features, snakes are always minimising their energy. Since the publication of Snakes, deformable models have grown to be one of the most active research areas in the boundary mapping community. The position (V(s) = (x(s), y(s))) of a snake can be represented parametrically by following equation. |
| V(s)=(x(s),y(s)) with s[0,1], its energy can be written as[8] |
 |
| here represents the internal energy of the snake due to bending.It is used to control the rate of stretch and to prevent the discontinuity in the contour. |
| Eimage represents the energy which depends upon the image and it gives rise to the image forces. |
| E con gives rise to the external constraint forces introduced by the user. |
| and together are called (External energy). |
| The final shape of the contour correspond to the minimum of this energy i.e. when this energy is minimum, the snake finds the boundary of the image as shown in fig.3. In the original technique of Kass [8] et al, the internal energy is defined as |
 |
| The snake energy of the snake is composed of a first-order term controlled by Ãâ°Ãâ(s and a second-order term controlled by (s The first-order term makes the snake act like a membrane and a second-order terms makes it act like a thin plate. Adjusting the weights Ãâ°Ãâ(s and (scontrols the relative importance of the membrane and thin plate terms. Ãâ°Ãâ(s controls the tension of the contour and (s) controls its rigidity. |
| Further, have three components or energy functions: |
| a. Lines |
| b. Edges |
| c. Terminations |
| The total image energy can be expressed as weighted combination of these three energy functions as: |
 |
| Adjusting the weights in the image will determine salient features in the image which will be considered by the snake. Some systems, including the original snake’s implementation, allowed for user interaction to guide the snakes, not only in initial placement but also in their energy terms. Such constraint energy can be used to interactively guide the snakes towards or away from particular features. |
 |
GENETIC ALGORITHM AND ACTIVE CONTOURS |
| The active contour method has been one of the widely used techniques for image segmentation. The basic idea of active contour is to evolve a curve, subject to constraint from a given image, in order to detect objects in that image [9]. But sometimes images are very noisy. So it is very difficult to accurately define their boundaries. Segmentation of Medical images is challenging due to poor image contrast and artifacts that result in missing or diffuse organ/tissue boundaries [10].The ultrasound images have low level of contrast and are very noisy. The Genetic Algorithm with active contour helps to overcome these problems. This reduces the time required for segmentation. Sensitivity to the initial position of the contour and the entrapment within local minima are among the problems inflicted on the active contour model used for image segmentation. To resolve this issue, Mohammad Talebi et. al in [7] combined genetic algorithm with active contour and apply it for the segmentation of ultrasound images. In this situation, this specific region under study can be considered as concentric circles, where each of these circle act like a contour as shown in fig. 4. Each of these points can contain the points from the tissue’s edge. So if we are able to separate these points from each contour and connect them together, we can reveal the tissue’s edge. The population of the chromosome is considered as the initial population to generate these circles. Once the initial contours are formed and the contour points are determined, each of these points should be evaluated and best ones be selected according to fitness function. The fitness function is defined based upon the energy minimization concept of active contours. So we can define the fitness function as: |
| Ffitness=1/(1+(Einternal+ Eexternal)) |
| =1/(1+(aEContinuity + ECurvaure + Eimage )) (4) |
| where |
| Einternal = energy of the curve. |
| Eexternal =energy of the image. |
| α= ability of the snake to stretch. |
| =rigidity of curve. |
| =weight factor for image. |
| After calculating the overall fitness functions, contours having highest value of fitness functions has been selected as the best solutions. At this stage, considering the rate of selection, selection, crossover and mutation has been applied. This process is repeated until a set of best contour is finally acquired. After the algorithm runs its course, the best point for each contour is selected. The final contour is obtained by connecting those points. |
| The genetic algorithm combined with active contour solves the optimization problem of active contour. One of the largest drawbacks of active contours is that the snakes often get stuck in local minima states. This has been overcome by use of genetic algorithm. |
 |
CONCLUSION |
| Genetic Algorithm [11] is a search technique to find approximate solutions to optimization and search problems by using the genetics as its model of problem solving. Its usefulness and gracefulness of solving problems has made it the more favorite choice among the traditional methods, namely gradient search, random search and others. GAs is very helpful when the developer does not have precise domain expertise, GAs possesses the ability to explore and learn from their domain. |
References |
|