International Journal of Innovative Research in Science, Engineering and Technology
MenuISSN ONLINE(2319-8753)PRINT(2347-6710)
ISSN ONLINE(2319-8753)PRINT(2347-6710)
| Pankaj Valand, Mayurdhvajsinh Gohil, Pragnesh Patel Assistant Professor, Electrical Engg. Dept., DJMIT, Mogar, Anand, Gujarat, India1 |
| Related article at Pubmed, Scholar Google |
Visit for more related articles at International Journal of Innovative Research in Science, Engineering and Technology
Edges of an image are considered crucial information that can be extracted by applying detectors with different methodology. Finding better algorithms for edge detection is still an active area of research. Here a novel GAACO hybrid algorithm is proposed for finding edges of an image. GA is applied to randomly generated individuals, which contain a set of randomly generated points, and before the crossover step is taken ACO is applied to the selected parents for improving the quality of the points. The developed edge detector is compared objectively to traditional edge detectors Canny, Sobel, Roberts and Perwitt using Ground Truth Estimation process. Subjective comparison is left for the readers to judge. In the proposed algorithm, GA-ACO hybrid algorithm performs in par with the traditional methods such as Canny, Sobel, Roberts or Perwitt, used for image edge detection. It was observed that the time taken by this algorithm for producing output was comparatively higher than other mentioned methods. This algorithm shows potential in dealing with dynamic input, where input image is constantly changing. A multi-processor environment can solve the time issues observed in experimentation.
Keywords |
| Genetic Algorithm, Ant Colony Algorithm, GA-ACO Hybrid |
INTRODUCTION |
| Edge Detectors are an essential part of almost all modern computer vision systems. Edge detection has varied applications. It has been realized that detecting edges reduce the amount of data to be processed once the edges are found and still preserves the structural information of the image. Different algorithms have been proposed and a few have emerged as winners in the race for designing edge detectors. Canny edge Detector [1] is one such example. Evolutionary algorithms like GA [5] have been applied for purpose of image edge detection for over a decade now. Edge Detection by Genetic Algorithm [2] was the first of its kind. GA has been used for edge patching [3], for finding active contours [4], optimization of medical images and various other purposes. GA-ACO hybrid algorithms have also been proposed for problems like text feature selection [6], sports competition scheduling [7], vehicle routing problem [8] and solving quadratic equations [9]. In this paper a hybrid GA-ACO algorithm is proposed for image edge detection and is objectively evaluated using Ground Truth Estimation process [10]. The work in this paper is basically concern to i) GA and ii) Ant Colony Optimization. GA is applied to randomly generated individuals, which contain a set of randomly generated points, and before the crossover step is taken ACO is applied to the selected parents for improving the quality of the points. In section IV we have worked out on Hybrid GA-ACO Novel Approach for Image Edge Detection that is much more efficient and effective than other methods. The results are discussed in section V by using one example of Image. |
II. GENETIC ALGORITHM |
| Genetic Algorithms is a non-deterministic stochastic search and optimization method that utilizes the theories of evolution and natural selection to solve a problem within a search space [11]. Basic steps of GA are random generation of individuals, selection, crossover, mutation and fitness calculation. Initially individuals are generated randomly or any other encoding chosen by the developer. Selection takes place depending on the fitness calculation achieved by the defined objective function. Crossover is carried out on the selected individuals and off-springs are produced which further undergo mutation. The probability of crossover and mutation are usually between 0.65-0.8 and 0.001-0.01 respectively. In crossover operation a two parent or a multi-parent [12] approach can be adopted. Mutation is an operation in which an elements value is changed randomly which causes mutation in the individual. This complete process repeats itself until the stopping criteria is satisfied or the execution of number of generations specified is completed. This is a global optimization process and it leads the complete population towards an optimum solution but eventually only a single winner emerges in accordance with the theory of survival of the fittest. |
III. ANT COLONY OPTIMIZATION |
| Ant Colony Optimization (ACO) wasintroduced by M. Dorigo and colleagues as a novel natureinspiredmeta-heuristic for the solution of hard combinatorialoptimization (CO) problems. ACO belongs to the class ofmeta-heuristics, which includes approximate algorithmsused to obtain good enough solutions to hard CO problemsin a reasonable amount of computation time. The inspiringsource of ACO is the foraging behavior of real ants [13].Basic ACO flow is as described. This complete description is ACO process as described in „Ant colony optimization theory: A surveyâÃâ¬ÃŸ [13]. A. Initialize Pheromone Values At the start of the algorithm the pheromone values are all initialized to a constant value c > 0. B. Construct Solution The basic ingredient of any ACO algorithm is a constructive heuristic for probabilistically constructing solutions. A constructive heuristic assembles solutions as sequences of elements from the finite set of solutioncomponentsC. A solution construction starts with an empty partial solutionsp =<>. Then, at each construction step the current partial solution spis extended by adding a feasible solution component from the setR sp ∈ C sp . This set is determined at each construction step by the solution construction mechanism in such a way that the problem constraints are met. The process of constructing solutions can be regarded as a walk (or a path) on the so-called construction graph Gc = C, L , which is a fully connected graph whose vertices are the solution components in C and whose edges are the elements ofL. The allowed walks on Gcare implicitly defined by the solution construction mechanism that defines the set R(sp) with respect to a partial solutionsp . The choice of a solution component ci j ∈ R(sp) is, at each construction step, done probabilistically with respect to the pheromone model. The probability for the choice of ci j is proportional to [τi j ]α . [η(ci j)]β , where η is a function that assigns to each valid solution component (possibly depending on the current construction step) a heuristic value which is also called the heuristic information. The value of parameters α and β, α > 0 and β > 0, determines the relative importance of pheromone value and heuristic information. The heuristic information is optional, but often needed for achieving a high algorithm performance. In most ACO algorithms the probabilities for choosing the next solution component (also called the transition probabilities) are defined as follows: |
 |
| (0,1)is called an evaporation rate. It is defined as the rate at which the pheromone deposited by ants is evaporated as observed in nature. It implements a useful form of forgetting, favouring the exploration of new areas in the search space is commonly called the quality function. It decides how the pheromone update is going to be achieved. |
IV. PROPOSED GA-ACO HYBRID TO IMAGE EDGE DETECTION |
| In the proposed algorithm an attempt has been made to hybridize GA and ACO to achieve image edge detection. GA executes according to its basic algorithm. As mentioned earlier, before the selected parents go through the process of crossover they are passed on to the ACO algorithm for improving the quality of edge points present in the selected parents thus resulting in better parents and ultimately better off-springs. |
 |
| A. Initial Population Each individual is defined as a set of points on the image indicating their location. Decimal encoding is used for the purpose of chromosome encoding. The winner individual will have all or most of these points on the edge of the image. B. Fitness Function/Objective Function Fitness function is defined as the total sum of fitness of all the points present in an individual. Fitness of each point is calculated singularly by comparing its intensity value to its neighbouring cells. Greater the difference between their intensities more fit that point is. C. Selection Selection is achieved by N-percent selection method. Other selection methods can also be adopted. Elitism is also used in order to enable the best solution so far to survive for the next generation as a result increasing the performance of GA. |
| D. Passing selected individuals to ACO The individuals selected for crossover are passed on to the ACO algorithm. Each individual is handled separately here. The number of points in an individual becomes the number of ants in ACO and the point location becomes the starting position for the ants in ACO. The movement of ants isbased on transitionprobability matrix. α is taken as 0.8 and β is taken as 0.2 which are the values determining importance of pheromone and heuristic information. Global and local pheromone matrices are initially assigned some constant value. Heuristic function is similar to the fitness function where the probability of an ant to move to the neighbouring cell is determined by the difference in the intensity value of the cell (point) in consideration and neighbouring cells. The ACO executes for defined iterations and the ant’s positions change through the process. As a result the new ant locations are obtained. These new ant locations are passed back to the GA algorithm as the points in parent individuals. As a result the quality of points present in the parent itself gets improved resulting in better results from crossover. E. Crossover Single point crossover is considered for this experiment. The points in the parent individuals get exchanged at the crossover point and off-springs are produced. Point at which the crossover takes place is randomly generated. F. Mutation Mutation has a very low probability of occurrence. A random single point in a random individual changes its values in the mutation operation. |
 |
V. RESULTS AND DISCUSSIONS |
| Certain benchmark test images were considered for the testing of this algorithm like cameraman, Leena, monkey, etc. Subjective and Objective evaluation was considered. Objective evaluation was calculated with the Ground Truth Estimation Method [10]. Edge images are shown for subjectiveevaluations while the Table-I indicate the objective evaluation results of GA-ACO Hybrid Edge Detector. |
 |
 |
| In this paper GA-ACO Hybrid algorithm is proposed for image edge detection. Observing the results it can be concluded that GA-ACO hybrid algorithm performs in par with the traditional methods, method such as canny, sobel, roberts or perwitt, used for image edge detection. It was observed during experimentation that the time taken by this algorithm for producing output was comparatively higher than other mentioned methods. This algorithm shows potential in dealing with dynamic input, where input image is constantly changing, because the search space always remains constant. A multi-processor environment can solve the time issues observed in experimentation. This is a novel approach to image edge detection. |
References |
|