Evolutionary Algorithms for Edge Detection: A Study

Evolutionary Algorithms for Edge Detection: A Study

S. Kavitha,

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

R. Rajeswari ,

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

Abstract Edge detection in images is essential for identifying the object boundaries and hence is used in segmentation registration and object recognition. Various methods have been proposed to improve edge detection. One such category of methods use evolutionary based algorithms to detect edges. Different evolutionary optimization techniques have been recently applied to edge detection problem. This paper gives a review of various edge detection techniques based on evolutionary algorithms such as ant colony optimization, artificial bee colony optimization, particle swarm optimization, genetic algorithms, and fuzzy logic.

Keywords Edge Detection, Evolutionary Algorithm, Ant Colony Optimization, Artificial Bee Colony Optimization, Particle Swarm Optimization, Genetic Algorithm, Fuzzy Logic.

1. INTRODUCTION

   Evolutionary algorithms (EAs) are stochastic search methods that mimic the metaphor of natural biological evolution and the social behavior of species [11]. Examples include how ants find the shortest route to a source of food and how birds find their destination during migration. The behavior of such species is guided by learning, adaptation, and evolution.

   Edge detection is a basic tool in image processing and computer vision in the areas of detection and extraction [1]. The point at which the image brightness changes sharply or formally should be identified in a digital image. This deal with extracting edges in an image by identifying pixels where the intensity variation is high. Edge detection aims to focus the limits of objects in an image and is a basis for many image analysis and machine vision applications [31]. Predictable approaches such as Sobel, Prewitt, Roberts, Canny edge detection are computationally expensive because each set of operations is conducted for every pixel. Hence there is a need to develop efficient and fast algorithms detection of edges.

   Recently, evolutionary algorithms have been applied to edge detection problems. Edge detection is considered to be an optimization problem and thus can be solved using various evolutionary algorithms. Evolutionary algorithms have advantages such as efficient optimization of the problem, ability to self-learn and optimize, capability to use the knowledge available in the images and the possibility of combining these algorithms with other techniques. Various

   evolutionary algorithms used for image edge detection are as shown in figure 1.

   This paper is organized as follows. In section II common edge detection techniques are discussed. In section III ant colony optimization (ACO) algorithm based edge detection is discussed. In section IV artificial bee colony algorithm (ABC) based edge detection is discussed. In section V particle swarm optimization (PSO) based edge detection is discussed. In section VI the usage of genetic algorithm (GA) for edge detection is discussed. In section VII fuzzy logic based edge detection algorithm is discussed. In section VIII, conclusion for this paper is given.

2. EDGE DETECTION TECHNIQUES Conventional edge detection operators identify edges based

   on the nature of edges in the image. Basically there are two types of edge detection operators. The first type is first derivative-based edge detection operators which detect image edges by calculating the image gradient values. Some examples of these operators are roberts operator, sobel operator, Prewitt operator, canny operator. The second type is second derivative-based edge detection operators, which look for second derivative zero-crossing to edge detection. Some examples of these operators are laplacian of Gaussian (LOG) operator and canny operator [31]. There are various edge detection techniques available in the literature. This section describes some of them.

   1. Canny Edge Detector

      Canny edge detector uses local maxima of the gradient image to find edges. The gradient of the image gives a measure of the directional change of intensity and can be obtained using the derivative of Gaussian filter [2]. Canny differentiates edges as strong and weak based on thresholds. Weak edges are included only if they are associated with strong edges. The Canny edge detector gives the best performance both visually and quantitatively based on the measures such as mean square distance, error edge map and signal to noise ratio[1].

   2. Roberts Edge Detector

      Robertss operator is a first-order operator. It uses a partial differential operator to find the edge. Roberts operator also

      gives a gradient measure of the intensity of image. This operator takes the grayscale image as input and returns the absolute magnitude of the gradient measure at the specified point as output [1].

   3. Sobel Edge Detector

      Particle Swarm Optimization

      [20,23,24,25,26,27]

      Sobel operator is a discrete differentiation operator used to compute an approximation of the gradient of image intensity function for edge detection. At each pixel of an image, sobel operator gives either the corresponding gradient vector or normal to the vector. It convolves the input image with kernel and computes the gradient magnitude and direction [1].

      pixel to another [13]. Rai has calculated the heuristic value from the ant's weight [14]. As the ant moves farther the weight is reduced. This gives additional information about the neighborhood to calculate transition probability. Rai has proposed a method to initialize the pheromone matrix. This will allow the ants to explore other pixels that may be considered as edge pixels.

      Ant Colony Optimization [3,7,10,12,13,14,15,16,17, 18,19]

      Artificial Bee Colony Optimization

   4. Prewitt Edge Detector

   Prewitt operator also uses the first derivative to find the gradient measure of the image. The output of this operator is also the absolute value of gradient measure which is maximum [1].

   Evolutionary Algorithm for Edge Detection

   [21]

   Genetic Algorithm

   [5,8,22,28,29,30]

3. ANT COLONY OPTIMIZATION FOR EDGE DETECTION Ant colonies can be used to formulate some powerful

   nature-inspired heuristics for solving the issues related to image processing. Based on ant's behavior, several edge detection methods have been proposed in the literature [12]. This section provides a brief description of these methods. The goal of image edge detection based on ACO is to use a number of ants to move on an image in order to create a pheromone matrix [19].

   Each entry of the pheromone matrix shows the edge information in each pixel location of the image. In addition, the movements of the ants are directed through the local variation of image intensity values. Some variations of ACO based edge detection techniques have also been proposed. They are modifications to Ant System (AS) [10] or Ant Colony System (ACS) algorithms [3, 7] for a digital image habitat, combined with local gray-intensity comparison for different pixel's neighborhood matrices.

   Dorigo et al. have used ant algorithms for discrete optimization which introduces the ant colony optimization (ACO) meta-heuristic [18]. In order to apply artificial ant colonies to edge detection needs to set the rules for local interactions between the ants and define the "food" that ants will searc. In the case of edge detection problem, the foods are the edge pixels in digital images.

   Tian et al. proposed an Ant Colony Optimization (ACO) based image edge detection approach [12]. To construct a pheromone matrix this approach uses a number of ants to move on a 2-D image. The edge information at each pixel location of the image will be represented by each entry. Local variation of the image's intensity values will guide the movement of the ants. The pheromone matrix is constructed by iteratively performing both the construction process and update process. This approach starts from the initialization process and then runs for N iterations. The edges are determined based on the decision process.

   Xiao et al. have explained that heuristic information is used to determine the probability using which ants move from one

   Fuzzy Logic [6,9,32,33,34]

   Fig. 1. Edge detection techniques based on evolutionary algorithms

   Nezamabadi et al. have proposed a new algorithm for ant colony search where in the problem can be specified by direct graph where the pixels of an image are denoted by the nodes of graph [15]. They have investigated various pheromone updating rules and have adapted them based on the underlying problem. Suitable values of the algorithm parameters were determined through empirical studies.

   Rahebi et al. have used ACO and Artificial Neural Networks with supervised learning to improve edge detection [16]. The experimental results show that neural networks along with ACO are very effective in edge detection.

   Lu et al. have utilized ACO to improve the conventional edge detection [17]. Traditional edge detection approach always provides a result where the edges are represented as broken pieces and this method suffers from a loss of the important image information. Lu et al. have presented an ACO based mechanism to compensate broken edges. This method focuses on four moving policies for reducing the computation load. A finite number of iterations are carried out to extract the edge information from the pheromone values.

4. ARTIFICIAL BEE COLONY ALGORITHMS FOR EDGE DETECTION

   The ABC algorithm is a stochastic, population-based evolutionary method proposed by Karaboga in the year 2005. ABC algorithm is simple and very flexible when compared to other swarm based algorithms. This method has become very popular and is widely used, because of its good convergence properties.

   Yigitbasi et al. have used ABC Optimization for edge detection of gray scale images [21]. Edges are found with masks, and dependence of masks can be removed by this improved method. The extensively used and known methods such as sobel, canny, roberts edge detection methods are compared with the results. The edge detection operators require a pre-defined mask for edge detection process. While using these masks, corner pixels and pixels of frame around the image are either ignored or taken as zero. Without this kind of loss of information, the edge information extraction was carried out with the ABC algorithm and the dependence on the mask has been removed.

5. PARTICLE SWARM OPTIMIZATION FOR EDGE DETECTION

   PSO was developed by Kennedy and Eberhart [23]. The PSO is inspired by the social behavior of a flock of migrating birds trying to reach an unknown destination. In PSO, each solution is a 'bird' in the flock and is referred to as a 'particle'. A particle is analogous to a chromosome (population member) in GAs. As opposed to GAs, the evolutionary process in the PSO does not create new birds from parent ones. Rather, the birds in the population only evolve their social behavior and accordingly their movement towards a destination [24].

   Zhen gang et al. have proposed a novel new medical image edge-detection technique based on PSO Algorithm [25]. It is difficult for detecting the medical image borders accurately. A new fitness function is formulated as the objective function. PSO algorithm is adopted to find the optimal filter mask to enhance the accuracy of the inspection system. The results denote that the accuracy of the proposed edge detection method is higher level than the conventional edge detection methods for medical images.

   Zhang et al. have proposed a PSO based edge detection technique which improves edge detection by extracting continuous edges [26]. The method works well in noisy images which often result in broken edges. A new objective and encoding function is used to concentrate on noise and broken edges of image. This algorithm is more suitable for edge detection than the canny and sobel algorithms in the images.

   Alipoor et al. have also proposed a novel edge detection method based on PSO [27]. They have proposed a new filter based on evolutionary computation. Artificial training is carried out on the edge map and the best edge filter is found. The benefit of this method is that the edge detection filter can be developed in an effective manner and it provides the better results than other edge detection algorithms.

   Mahdi Setayesh has proposed a novel constrained optimization model for detecting continuous edges in noisy images [20]. Two PSO-based algorithms are developed to find good solutions for detecting edges. These two algorithms use two different constraint handling methods penalizing and preservation. The above two constraints are compared with revised version of Canny based edge detector and the robust rank order (RRO)-based algorithm as a statistical-based edge detector on two different type of images that contains the various level of noise.

6. GENETIC ALGORITHMS FOR EDGE DETECTION

   GAs are inspired by biological systems improved fitness through evolution. A solution to a given problem is represented in the form of a string, called 'chromosome', consisting of a set of elements, called 'genes', that hold a set of values for the optimization variables [28].

   Basic steps of GA are random generation of individuals, selection, crossover, mutation and fitness calculation. Initially individuals are generated randomly or by any other encoding method 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 [29] approach can be adopted. Mutation is an operation in which an elements value is changed randomly which causes mutation in the individual.

   Li et al. have proposed adaptive immune genetic algorithm (AIGA) based on cost minimization technique for edge detection [8]. The immune genetic algorithm is a novel evolutionary algorithm which combines the immune mechanism and evolutionary mechanism. The edge detection problem was the same as minimizing the cost of an edge image, and the desired edge image was found to be one that corresponds to the global minimum of the cost function. The AIGA used the adaptive probabilities of crossover, mutation and immune operation, and a geometric annealing schedule in the immune operator.

   Branch et al. have used GA to reduce false edges detected by gradients [5]. Their aim is to find a well defined edge map to lead the image segmentation. The method is based on three stages: first, the depth gradients and orientation gradients are calculated. In the next stage genetic algorithm is used to find an edge map from the obtained gradients. In the last stage fast labeling is carried out. The main limitation of this method is the presence of noise in images. The noise in the images made the gradient calculation difficult and, consequently, the edge extraction. The genetic algorithm implemented in the method found thin and closed edges, and considerably reduced the false edges detected by gradients.

   Senthilkumaran et al. have studied edge detection method for Dental X-ray image segmentation based on a GA approach [22]. They have shown that the GA based edge detection provides higher performance for edge detection. GA flexible edge detection on shady segments is used to recognize the problems in mouth such as tooth decay, damage of the supporting teeth and their bones, tooth injuries. Dental X-rays are quietly used to analyze the problems earlier that the symptoms are occurred in mouth.

   Pankaj Valand et al. have proposed to find an edge of an image based on a novel GA-ACO algorithm [30]. The algorithm is applied to randomly generated individuals before the crossover step is taken. And it contains randomly generated points. The main purpose of applying ACO to the selected parents is to improve the quality of the points. The conventional edge detectors canny, sobel, Roberts and perwitt operators are used in ground truth estimation process. In the proposed algorithm, GA-ACO hybrid algorithm performs

   much better than the conventional methods. When compared, the time taken by this algorithm in order to produce the output was higher than the other methods. This is potential in dealing with dynamic input, where input image is constantly changing.

7. FUZZY LOGIC FOR EDGE DETECTION

   The term fuzzy logic was proposed in 1965 by Lotfi Zadeh. Fuzzy logic is a structure of many valued logic. It is applied to many fields such as control theory and artificial intelligence. The mathematical concepts related to fuzzy reasoning are very easy. Fuzzy logic is a more perceptive approach without the far achieving complexity.

   Khaire et al. have explained about fuzzy set approach based on edge detection. The image is judged as a fuzzy set and pixels are taken as elements [32]. The color images are changed to a partially segmented image using fuzzy approach. Later an edge detector is convolved over the partially segmented image to obtain edged image. The double edges are treated appropriately and the method works well blurred images. The real images contain equally strong and weak edges. The fuzzy approach provides both strong and weak edges having different edge strength using higher and lower thresholds.

   Yadav et al. have proposed a fuzzy inference system (FIS) used to detect edges. FIS is very simple and capable method to recognize the edges without determing a threshold value [33]. FIS presents single output value corresponding to multiple input values and identifies whether a pixel is an edge pixel or not. FIS is a striking solution to improve the quality of edge as much as possible. These algorithms provide better results compared to the other edge detection algorithms.

   Aborisade has proposed effective fuzzy based edge detection algorithm [9]. This method uses the edge strength information derived using three masks to avoid detection of fake edges corresponding to noise. Three linear spatial filters are used which are low-pass, high-pass and edge enhancement sobel filters during spatial convolution process. Edge strength values derived from the three masks form three sets of edges. These are given as input to the, fuzzy system and fuzzy rules determine whether the pixel is an edge or non edge pixel. The pixel arrangement of a given image is generated using Mamdani defuzzifier method.

   Rahman khan et al. have presented a fuzzy rule based algorithm [34]. This is able to detect edges from the gray scale images. They have compared the results with the results from sobel and prewitt edge detectors. The edge detection algorithm is better than sobel and prewitt operators in finding dissimilar edges from the image and hence it is able to give better visual look of edges which is not possible in case of sobel and prewitt operators. The input pixels are separated into two fuzzy sets Black and White and the output is divided into three sets Black, Edge and White.

8. CONCLUSION

Edge detection in images is very important for identification of object boundaries. Various evolutionary algorithms have been used to improve the performance of edge detection techniques. This paper presents a survey of the

evolutionary algorithms based edge detection techniques. This review has highlighted on the advantages and limitations of these methods.

ACKNOWLEDGEMENT

The authors are thankful to Bharathiar University for valuable support.

REFERENCES

1. R. C. Gonzalez and R. E. Woods. "Digital Image Processing". 2nd ed, 2002.

2. S. Price "The Canny Edge Detector", July4, 1996.

3. A.A.Alshennawy, A.Aly, "Edge Detection in Digital Images Using Fuzzy Logic Technique", International Journal of Electrical and Engineering, page no 4:7 2009.

4. Rashmi, Mukesh Kumar, and Rohini Saxena "Algorithm and Technique on Various Edge Detection: A Survey", an International Journal (Sipij) Vol.4, No.3, June 2013.

5. Diaz, J. Branch, and P. Boulanger, "A Genetic Algorithm to Segment Range Image by Edge Detection". IEEE, 0-7803-94 19-4/05 2005.

6. KiranjeetKaur, Sheenam Malhotra,"A Survey on Edge Detection Using Different Techniques", International Journal of Application Vol 2, issue 4, April 2013.

7. Baterina, A. V. Oppus, C. "Image edge detection using ant colony optimization", WSEAS Transactions on Signal Processing 6(2): 58-67, 2010.

8. Ying Li, Bendu Bai, "An Adaptive Immune Genetic Algorithm for Edge Detection", ICIC, LNAI 4682, pp. 565-571, 2007.

9. Aborisade, D.O Fuzzy Logic Based Digital Image Edge Detection Global journals of computer science and technology, page no: 79- 83Vol.10 Issue 14 (Ver.1.0) November 2010.

10. Khajehpour, Lucas, Araabi, "Hierarchical image segmentation using Ant colony and chemical computing approach", Advances in Natural Computation, Vol. 3611, 2005.

11. Somya Jain "Edge Detection using Evolutionary Algorithms", A thesis submitted to the Delhi Technological University, Delhi. 2009 – 2011.

12. Jing Tian, Weiyu Yu, and Shengli Xie, "An Ant Colony Optimization Algorithm for Image Edge Detection", IEEE Congress on Evolutionary Computation, 978-1-4244-1823-7/08 IEEE 2008.

13. Peng Xiao, Jun Li and Jian-Ping Li , "An improved Ant colony Optimization Algorithm for Image Extracting", International Conference on Apperceiving Computing and Intelligence Analysis (ICACIA), p. 248

    – 252 , 17-19 Dec. 2010.

14. Puneet Rai Image Edge Detection using Modified Ant Colony Optimization Algorithm based on Weighted Heuristics ", International Journal of Computer Applications p 0975 8887 Volume 68- No.15, April 2013.

15. H. Nezamabadi-Pour, S. Saryazdi, and E. Rashedi, "Edge detection using ant algorithms", Soft Computing,vol. 10, pp. 623-628, May 2006.

16. JavadRahebi, Hamid Reza Tajik, "Biomedical Image Edge Detection using an Ant Colony Optimization Based on Artificial Neural Networks", International Journal of Engineering Science and Technology (IJEST), vol. 3, 12 Dec 2011.

17. De-Sian Lu, Chien-Chang Chen "Edge detection improvement by ant colony optimization", Pattern Recognition Letters, vol. 29, pp. 416-425, March 2008.

18. M. Dorigo, L. M. Gambardella, M. Middendorf and T. Stutzle, "Special Issue on Ant Colony Optimization", IEEE Transactions on Evolutionary Computation, vol. 6, Jul. 2002.

19. Etemad, S. A. White T, "An ant-inspired algorithm for detection of image edge Features", Applied Soft Computing 11(8): 4883-4893 .2011.

20. Mahdi Setayesh "Particle Swarm Optimization for Edge Detection in Noisy Images" A thesis submitted to the Victoria University of Wellington 2013.

21. Elif Deniz Yigitbasi, Nurdan Akhan Baykan "Edge Detection using Artificial Bee Colony Algorithm", International Journal of Information and Electronics Engineering, Vol. 3, No. 6, November 2013.

22. Senthilkumarn, "Genetic Algorithm Approach to Edge Detection for Dental X-ray Image Segmentation", International Journal of Advanced Research in Computer Science and Electronic Engineering (IJARCSEE) Volume 1, Issue 7, September 2012.

23. Kennedy J, Eberhart R. "Particle swarm optimization", IEEE international conference on neural networks, 1942-1948, 1995.

24. Shi Y, Eberhart R. "A modified particle swarm optimizer", IEEE International conference on evolutionary computation. Piscataway, NJ IEEE p. 69-73, 1998.

25. Shi Zhen-gang, "Edge Detection for Medical Image Based on PSO Algorithm", Intelligent Networks and Intelligent Systems (ICINIS),p. 84

    871-3-2010.

26. Mengjie Zhang, Johnston M, "Improving edge detection using particle swarm optimization", Image and Vision Computing New Zealand (IVCNZ),p. 1 – 8 , 2010.

27. Alipoor M, Imandoost S, Haddadnia J Designing edge detection filters using Particle Swarm Optimization", Electrical Engineering (ICEE), p. 548 – 552, 2010.

28. Goldberg DE, "Genetic algorithms in search, optimization and machine learning", Reading, MA: Addison-Wesley Publishing, 1989.

29. Daoxiong Gong, Xiao gang Roan, "A new Multi-parent Recombination Genetic Algorithm Intelligent Control and Automation", WCICA Fifth World Congress on Vol 3, 2004.

30. Pankaj Valand, Mayurdhvajsinh Gohil, PragneshPatel Novel Approach for Image Edge Detection, International Journal of Innovative Research in Science, Engineering and Technology Vol. 2, Issue 12, December 2013.

31. Li Bin, Mehdi Samiei yeganeh "Comparison for Image Edge Detection Algorithms" IOSR Journal of Computer Engineering Vol 2, PP 01-04, July-Aug. 2012.

32. Pushpajit Khaire, Nileshsingh V. Thakur A Fuzzy Set Approach for Edge Detection International Journal of Image Processing, Vol 6 2012.

33. Meenakshi Yadav, Kalpna Kashyap Edge Detection through Fuzzy Inference System International Journal Of Engineering And Computer Science Vol 2 Issue 6 Page No. 1855-1860, June, 2013.

34. Aijaz Ur Rahman khan, Kavita Thakur An Efficient Fuzzy Logic Based Edge Detection Algorithm for Gray Scale Image International Journal of Emerging Technology and Advanced Engineering, Vol 2, August 2012.