Edge detection using evolutionary algorithms new

 Introduction  Background  Evolutionary Algorithms  Bacteria Foraging Algorithm  Particle Swarm Optimization  Results and Conclusion  References

 Edges are significant local changes of intensity in an image. A Tulips image  Edge Detection is the process of identifying and locating sharp discontinuities in an image.  Abrupt change in pixel intensity Characterize boundary of a object Edges of the Tulips image

 A tulips Image Part of the image Edge of the part of the image Matrix generated by the Part of the image

CAUSES OF INTENSITY CHANGES 1. Geometric events Discontinuity in depth and/or surface colour and texture 2.Non-geometric events Edge formation due to Reflection of light discontinuity of surface Illumination shadows REFLECTANCE ILLUMINATION SHADOWS

IMAGE RECOGNITION SEGMENTATION IMAGE FUSION IMAGE TRACKING

The basic idea behind edge detection is to find places in an image where the intensity changes rapidly, using one of the two criterions: 1. Find places where the first derivative of the intensity is greater in magnitude than a specified threshold. (USING GRADIENT) 2. Find places where the second derivative of the intensity has a zero crossing. (USING LAPLACIAN)  Examples of the gradient based edge detectors are Prewit and Sobel operators.  An alternative method is an optimal edge detector like the Canny operator, for two dimensional images.

The IITR image Sobel Roberts Prewitt Marr Canny

INPUT IMAGE ENHANCEME FILTERING DETECTION NT EDGES OF THE IMAGE LOCALISATI LINK ON

 The quality of Edge Detection depends upon a lot of factors such as lighting conditions, the presence of objects of similar intensity,density of edges in the scene and noise.  There is no good method for automatically setting these values, so they are manually changed by an operator each time the detector is run with a different set of data.  In the presence of noise, detection of edges becomes very difficult because both edges and noise are characterized by high frequency.

1.Corners are often missed. 2.Here we have to choose Threshold values and width of the mask. Changing the size of the image complicates the setting of these values. 3.For different features we need a different operator.

 The name “EVOLUTIONARY ALGORITHM” suggests, evolution as it is observed in nature is imitated.  These algorithms are increasingly sought for finding optimum solutions for the engineering problems.  Well suited to solve complex computational problems such as optimization of objective functions , pattern recognition ,image processing, filter modelling,etc.

The word „„heuristic” is Greek and means „„to know”, „„to find”, „„to discover” or „„to guide an investigation”, Specifically, „„Heuristics are techniques which seek good (near-optimal) solutions at a reasonable computational cost without being able to guarantee either feasibility or optimality, or even in many cases to state how close to optimality a particular feasible solution is.” Heuristic algorithms mimic physical or biological processes. Some of most famous of these algorithms are ANT COLONY • MIMICS THE BEHAVIOUR OF ANTS OPTIMIZATION FORAGING FOR FOOD BACTERIA FORAGING • COMES FROM SEARCH AND THE ALGORITHM OPTIMAL FORAGING OF BACTERIA PARTICLE SWARM • SIMULATES THE BEHAVIOUR OF OPTIMIZATION FLOCK OF BIRDS GENETIC ALGORITHM • INSPIRED FROM DARWINIAN THEORY

 Given by Kelvin M. Passino (2002)  Exploits the foraging behaviour of Bacteria  Foraging can be modeled as an optimization process where bacteria seek to maximize the energy obtained per unit time spent during foraging.  An objective function is posed as the cost incurred by the bacteria in search of food.  A set of bacteria tries to reach an optimum cost. Four Stages in the life cycle of Bacteria 1. Chemo taxis 2. Swarming 3. Reproduction and 4. Elimination and Dispersal These stages in the search space generate an optimal solution to the problem of optimization.

In Chemo taxis stage, the bacteria either resort or tumble followed by a tumble or make a tumble followed by a run or swim. Movement stage of Bacteria In Swarming, each E. coli bacterium signals another bacterium via attractants to swarm together. Cell to cell signalling stage.

In the Reproduction the least healthy bacteria die and of the healthiest each bacterium splits into two bacteria, which are placed at the same location In the Elimination and Dispersal stage, any bacterium from the total set can be either eliminated or dispersed to a random location during the optimization. This stage prevents the Bacterium Reproduction stage Of Bacteria from attaining local optimum.

Start Initialization  p: Dimension Evaluation  S: Population Size Moving  Nc: Chemotactic steps Tumble / Swim  NS: Swim Length Limitation No End of Nc?  Nre: Reproduction Steps Yes  Ned: Elimination-Dispersal Steps Reproduction  Ped: Elimination Rate No End of Rep.?  dlt(i): random number on [-1,1]. Yes where i from 1 to p. Elimination  c(i): Step Size for the dimension. No End of Eli.? Yes 19 End

i J (i , j , k , l )  J (i , j , k , l ) J cc j, k , l , P j, k , l (1) i i dlt i j 1, k , l j, k , l C i T dlt i dlt i (2) i J (i, j 1, k , l ) J (i, j 1, k , l ) J cc j 1, k , l , P j 1, k , l (3) Nc 1 i J health J i, j, k , l (4) j 1

The original bacterial foraging (BF) Technique modified to make it suitable for edge detection. The nutrient concentration at each position is calculated using a derivative approach. Modifications Search Space 2-dimension search space of bacteria consists of the x and y coordinates of a pixel in an image.

Chemo taxis  Goal of this stage is to let the bacterium search for the edge pixels of the image.  Another goal is to keep the bacterium away from the noisy pixels.  Probabilistic derivative approach is used to find the edge pixels. Swarming  A bacterium relies on other bacteria  The bacterium that has searched an optimum path, signals other bacteria so that they can reach the desired optimum path swiftly.  That optimum path is the best edge detected.  Bacterium releases both attractant and repellant.  Bactreia congregate in to groups and move in a concentric manner. Reproduction  The population is sorted in the ascending order of the accumulated cost  Half of the least healthy bacteria dies and each of the other healthiest bacteria splits up into two. Elimination-Dispersal  Each bacterium in the population is subjected to elimination-dispersal with some Probablity.

RESULT OF BACTERIA FORAGING ALGORITHM A Cameraman Image Edge Detected using BFOA With split ratio 4 Edge detected using BFOA With split ratio 12

 Edges are accurately detected  The result of this algorithm may show disconnected edges as shown in Fig  Thick edges can be seen due to bacteria moving parallel to an edge.  Since BFOA has been devised with the aim of global extremes, this error is expected.

 Proposed by Kenedy and Eberhert (1995)  Global optimization method  Population based Evolutionary Algorithm based on social- psychological principles  Simulates a social model such as flocking of birds, schooling of fish etc.  PSO algorithm attempt to maximize or minimize a given set of data by generating a random set of particles which move with randomly changing velocity throughout the search space.  The Particle with the best position is selected and other particle will swarm towards it.  Successfully applied to training neural networks, optimizing power system,fuzzy control systems, robotics, antenna design and computer games.

The velocity update equation is given by The next position of the particle will be

 Best Edge is nothing but a COLLECTION OF PIXELS WHICH ARE ON CURVES.  PSO based algorithm can be used to detect those curves.  To Apply PSO based algorithm in edge detection “Each Particle represents a CURVE”

The movement directions from a pixel to one of eight neighbours An example for a curve passing through pixel A 5 5 5 4 3 3 4 4 5 0 0 0 0 0 ...... Particle encoding for the curve above The dimension of the vector representing a particle depends on image size. Each Curve can be encoded using the direction of movement from a pixel to the next pixel on the curve. The Best fitting Curve is selected which passes through a pixel. All other neighbour curves (Particles) swarm towards the Best fitting Curve.

 Homogeneity and  Uniformity factors  The first one measures the homogeneity of the pixels on a curve and the second one measures the intensity similarity of these pixels.  The homogeneity operator can be formulated as below: (5) Homogeneity factor of a curve: This factor shows the average of homogeneity of the pixels on a curve where the homogeneity of each pixel on the curve is calculated based on equation (5). This factor is defined as below: (6) Uniformity factor of a curve: The pixels on a curve often have similar values of intensities; hence we introduce a new concept that we call the uniformity factor of a curve. This factor can be computed for any curve as below: (7)

 Objective function is needed to calculate the fitness of the particle at each point. In case of edge detection the objective function is calculated with the help of homogeneity factor and uniformity factor. Here, we search the curves which pass through a pixel. We expect to make the homogeneity factor bigger, the uniformity factor smaller, and the length of the curves bigger. So heuristically this function is defined as below: (8)

Flow chart depicting the General PSO Algorithm: Start Initialize particles with random position and velocity vectors. particles exhaust For each particle’s position (p) Loop until all evaluate fitness Loop until max iter If fitness(p) better than fitness(pbest) then pbest= p Set best of pBests as gBest Update particles velocity (eq. 1) and position (eq. 3) Stop: giving gBest, optimal solution.

RESULTS OF PSO Edge Detected Using Sobel Operator A Test Image Edge Detected using PSO

A A noisy Image Output Using Sobel Operator Output Using PSO

 Ease of implementation  High rate of convergence  Fewer operators  A limited memory for each particle to save its previous state  High capability to optimise noisy functions

 Bacteria Foraging method finds robust edges even in the complex and noisy images. This work opens a new domain of research in the field of edge detection using bio-inspired algorithms. This method performs better than many other standard methods.  Particle Swarm Optimization (PSO) is a computational intelligence method. Here the results of PSO are compared with the Sobel operator and this algorithm outperforms the Sobel operator.  A main advantage of these algorithms is detection of edges in one step and there is no need for smoothing, enhancement and localization as pre-processing steps.  The PSO algorithm used here gives the output only for predefined shapes (e.g. Circle, Triangle etc). An improvement can be made so that this algorithm can be applied for the complex images also.

1. R afael C. Gonzalez, Richard E.Woods and Steven l. Eddins “Digital Image Processing using MATLAB” Second Edition 2. Om Prakash Verma, Madasu Hanmandlu, Puneet Kumar , Sidharth Chhabra, and Akhil Jindal, “A Novel Bacterial Foraging Technique for Edge detection ”, 2011 IEEE 3. Kelvin M. Passino , “Biomimicry of Bacteria Foraging and Control for Distributed Optimization and Control”, JUNE 2002 IEEE, pp 52- 67 4. Mahdi Setayesh1, Mengjie Zhang1 and Mark Johnston2,” A new homogeneity-based approach to edge detection using PSO, 24th International Conference Image and Vision Computing New Zealand (IVCNZ 2009)”, 2009 IEEE 5. Mahdi Setayesh, Mengjie Zhang and Mark Johnston, “Improving Edge Detection Using Particle Swarm Optimisation”,2010,IEEE

Edge detection using evolutionary algorithms new

Edge detection using evolutionary algorithms new

More Related Content

What's hot

Viewers also liked

Similar to Edge detection using evolutionary algorithms new

Recently uploaded

Edge detection using evolutionary algorithms new

Editor's Notes