Modified Ant Colony Optimization Based Approach for Edge Detection in Images

Modified Ant Colony Optimization Based Approach for Edge Detection in Images

1R. Jothilakshmi, 2R. Rajeswari

1Dept. of Physics, Vel Tech University, Chennai 62

2Dept. of Computer Applications, Bharathiar University, Coimbatore – 46

Abstract

Various methods based on Ant Colony Optimization (ACO) are used to detect edges in digital images. Such techniques generate a pheromone matrix that represents the edge information at each pixel position on the routes formed by ants dispatched on the image. In this paper a modified ACO-based approach for edge detection in images is proposed. In this paper we propose to determine the heuristic information based edge magnitude obtained using Laplacian operator. This information is used by the ants to find possible edges. Moreover, the proposed ACO-based approach takes advantage of the fuzzy clustering to determine whether a pixel is edge or not. Experimental results show the superior performance of the proposed approach.

1. Introduction

   Edge detection in images is the process of extracting edges. Edge detection helps in identifying the pixels where sharp changes in intensity occur and this helps in determining the object boundaries in images. Hence edge detection plays a very important role in pattern recognition, image analysis, computer vision and image processing. There are various approaches to detect edges in images based on gradients [1]. But there are some limitations of these conventional approaches. Firstly, the computation time of these approaches increase with the increase in the size of the image [2]. Secondly, the edges detected using these approaches are discontinuous [3].

   Ant Colony Optimization (ACO) is one of the bio- inspired algorithms [4-7], which is based on the natural foraging behavior of ant species. Ants deposit pheromone on the ground to mark some favorable path between a food source and their colony which should be followed by other members of the colony. ACO has been used to solve a number of optimization problems. Several ACO-based approaches have been proposed for edge detection [8-13,2]. The approaches given in [8-9]

   are used to enhance the edge information obtained using conventional techniques. The pure ACO-based methods proposed in [10-13,2] describe that ACO- based approaches based on Ant System [4-6] and Ant Colony System [4-5,7] can be used to directly detect edges in images. These works clearly indicate that more research work is needed to improve the quality of the edges detected using these methods and to decrease the time complexity. ACO-based approach has the potential of overcoming the limitations of conventional methods. Moreover it can be readily parallelized thus making the algorithm suitable for distributed environments.

   In this paper, we propose a modified ACO-based approach to detect edges that edge magnitude obtained using Laplacian operator and thresholding based on fuzzy c-means clustering to determine whether a pixel is an edge or not.

2. Ant Colony Optimization

   ACO is a nature-inspired technique that is designed based on ant colonies. Ant colonies have trail-laying and trail-following behavior during foraging for their food. Ants deposit pheromone on the ground to mark the path between a food source and their colony. During the course of time, the pheromone evaporates. The shorter or favorable paths are travelled by the ants faster and thus receive greater compensation for pheromone evaporation. As pheromones are laid down faster pheromone densities are high on shorter paths. It is this positive feedback mechanism that helps in finding good solutions and is the basic idea behind ACO-based algorithms.

   In an ACO algorithm, ants move through a search space, the graph, which consists of nodes and edges. The movement of an ant in the graph is determined by the transition probabilities. Heuristic information and pheromone information determine the transition probability. The construction of a solution to a problem contains a certain number of construction steps. Each ant tries to find a good solution simultaneously and individually at every construction step.

   According to the ant system [7] at the nth

   k (i, j) 1/ fk

   0

   if ant k used edge (i,j)

   construction step, the kth ant moves from node i to node j according to the transition probability

   otherwise

   —–

   – (4)

   p(n)

   ( (n1) ) (

   i, j )

   where

   fk is the tour length of the k th ant. This tour

   i, j

   i, j

   ( (n1) ) (

   i, j

   ji

   (n1)

   i, j )

   if j j ——(1)

   length depends on the nature of the problem to be solved. Its value is chosen in such a way that desirable routes have smaller tour lengths.

   where

   i, j

   is the quantity of pheromone between

   state iand

   j,i, j is the heuristic information for going

   i j

   The second update is performed after all K ants

   have moved within each construction step as [14]:

   from node

   and to node to , is the set of unvisited

   (n) (1 ). (n1) . (0)

   states and and are constants that control the influence of the pheromone and heuristic information respectively. The Ant Colony System (ACS) [7] allows for exploration by slightly modifying the rule

   where

   ————— (5)

   is the pheromone decay coefficient.

   based on equation 1 as follows:

   arg max[ (i, j)].[(i, j)]

   j J

   ifq q0 otherwise

   (2)

3. Ant Colony based Approach for Edge

   Detection

   At the beginning of every iteration, ants are randomly placed on the image. A gray level image is considered as a two-dimensional (2-D) graph where the

   pixels are nodes. The edges of the graph connect

   where q is a random number,

   q0 is a parameter

   adjacent pixels together. The ants wander on the 2-D

   (0 q0

   1)

   and J is a random variable selected

   graph pixel by pixel in fixed number of steps (ant memory) and deposit pheromone on the graph

   according to the previous probability distribution function given in equation (1). At every step, based on the value of q generated an ant moves from state i and

   according to the quality of the path and a pheromone matrix is constructed. The path quality determines the quality of the edge.

   to state j . If

   q q0

   then the best edge is chosen

   The algorithm consists of three main steps

   (exploitation), otherwise an arbitrary edge is chosen according to equation (1) (biased exploration).

   The best-so-far solution for every construction step or for the entire algorithm is recorded. Pheromone

   deposit by ant provides a positive feedback and thus

   1. Initialization process

      Let K ants be randomly assigned on an image I whose size is RXC . The initial value of each component of the pheromone matrix (0) is set to be a

      reinforces the probability of finding new good

      constant

      init . The heuristic information

      i, j is

      solutions. Similarly evaporation of pheromone acts as a negative feedback which prevents the algorithm to stop at local optima. The pheromone is updated twice during the algorithm. The first update is performed after the movement of each ant in each construction step as [14]:

      determined based on the variation of image's intensity values in the neighborhood.

   2. Iterative Construction and Update Process

      Let the algorithm be executed for N iterations. A

      (1 p). (n1) .(k )

      if (i,j)belongs to best

      the nth iteration, one ant is randomly selected from the

      (n) i, j

      i, j

      (n1) i, j

      i, j

      otherwise

      (3)

      K ants. This ant moves on the image for L movement steps. At every step the ant moves from node (l, m) to

      its neighboring node

      (i, j)

      according to the transition

      where

      is the evaporation rate and

      probability given in equation (1). The neighborhood of

      the ant is considered to be 8-connectivity neighborhood in this implementation. An ant can move to any adjacent pixel with a condition that an ant moves only to a node that it has not recently visited to avoid ants visiting the same set of nodes repeatedly. The first update of the pheromone matrix is done after the movement of each ant in each construction step according to equation 3. The second update is done after the movement of all ants in each construction step according to equation 5. The deposited amount of

      (k )

      determined using structures of 3×3 ideal edge images based on [16, 17].

      In this paper, we have determined (i, j ) based on the edge magnitude obtained using Laplacian operator [18]. The areas in images which are smooth have the gradient value as zero. The edge regions have positive values on one side of the edge, a positive value on the other side of the edge and zero at a point between these regions. Thus the movement of the ants are steered by

      pheromone

      i, j

      is equal to the heuristic information

      the edge magnitude obtained using Laplacian operator.

      associated with the pixels that belong to the tour of the Desirable routes are the routes that pass along pixels

      k th ant if pixel (i, j)

      was visited by the k th ant in its

      with higher edge magnitude. The Laplacian function is

      given by

      current tour; 0 otherwise.

      1 x2+y2

      x 2+y 2

      In ACO-based edge detection method all the visited

      L x, y =

      2 1

      22 e

      2 2 ———— (6)

      pixels are updated. The aim of each ant is to produce only a partial edge piece in the image. The collective interaction of the ants produces a pheromone matrix from which all the edges are extracted.

   3. Decision Process

      The goal of the ant's movement is to construct a final pheromone matrix that reflects the edge information. Each element in the pheromone matrix corresponds to a pixel in the image and specifies whether that pixel is an edge or not. Finally by applying a threshold T on the final pheromone matrix

      ( N ) a binary decision is made at each pixel location to determine whether it is edge or not.

   4. Proposed Modifications to ACO based approach for Edge Detection

      1. Determination of Heuristic Information

         The movement of ants from one state to another is determined by the transition probabilities. The

         We consider a 3×3 neighborhood. The 3×3 digital filter obtained from the equation 6 is used to convolve with the 3×3 neighborhood in the image. The result

         obtained is the edge magnitude, i.e. (i, j) , obtained

         and is used as the heuristic information.

      2. Thresholding based on Fuzzy C-Means Clustering

The final pheromone matrix is used to determine whether each pixel is an edge or not. The decision is made by applying a threshold on the final pheromone matrix (N). In [12, 2], the thresholding is done based on the method developed in [19].

In this paper, the threshold T is computed based on fuzzy c-means clustering method developed in [20].

Let x denote the 1-D representation of the final

pheromone matrix p . The algorithm is based on the

minimization of the following objective function:

RxC L

J um || x c ||2

transition probability depends on the combination of a)

m ij

i 1 j 1

i j

——————– (7)

the heuristic information or the attractiveness

(i, j )

where m is any integer value greater than or equal

which is problem specific and is calculated a priori and

to 1, uij is the degree of membership of xi

in cluster j,

b) the trail level (i, j) which indicates how proficient it has been in the past to make such a move and this

value is updated by the ants depending on the quality of

xi is the i-th pheromone element, cj is the center of the cluster j , L is the maximum number of clusters i.e.

the path.

(2

j L)

and

|| * || is any norm representing the

In [12], (i, j ) is a function of local group of pixels called clique. Its value depends on the variation of the image's intensity values on the clique. In [15], (i, j ) is

similarity between data and the center. In our problem the number of clusters, L 2 . The algorithm consists of the following steps:

ij U k 1

U [u ] (0)

1. Initialize matrix, , .

2. Calculate the centers

   RxC

   ij

   i

   um .x

   C(k ) [c ]

   using

   the images is 128×128. The results are compared with Sobel, Prewitt, Canny and ACO-based edge detection technique given in [12]. Figures 1, 2, 3 and 4 present the results of test images camera, boat, house and

   j

   c j

   i 1

   u

   RxC

   m

   ij

   i 1

   ——————– (8)

   polygons respectively. As seen from the figures, the proposed approach gives better results compared to other methods except Canny's method, in terms of visual quality of the extracted edge information.

3. Calculate U (k 1) using

   L

   uij

   1

   || x c

   || 2

   ( i j )m1

   k 1

   || xi ck ||

   ——————– (9)

4. If

   || U (k 1) U (k ) ||

   then stop; otherwise set

   k k 1and return to step 2.

   After the completion of the iterative process, the threshold is calculated as

   T c1 c2

   1. (b)

      2 ——————– (10)

      where ci is the center of cluster i .

5. Results and Discussion

   The various parameters of the proposed algorithm are determined by experiments. A suitable set of parameters are given in table 1.

   Table 1. Suitable parameters of the proposed algorithm

   Parameter	Value
   (evaporation rate)	0.85
   init (initial value of each element of pheromone matrix)	0.001
   (weighting factor of pheromone information)	1
   (weighting factor of heuristic information)	0.1
   L (total number of ants movement-steps within each construction step)	40
   (pheromone decay coefficient)	0.05
   N (total number of construction steps)	4

   Experiments are conducted based on four test images, camera, boat, house and polygons. The size of

   (c) (d)

   1. (f)

      Figure 1. Extracted edges for the test image camera a) original image b) Sobel operator c) Prewitt operator d) Cannys method e) Method proposed in [12] without thinning and f) Proposed method (without thinning)

      1. (b)

   (c) (d)

   (c) (d)

   (e)

   (f)

   (e) (f)

   Figure 2. Extracted edges for the test image boat a) original image b) Sobel operator c) Prewitt operator d) Cannys method e) Method proposed in [12] without thinning and f) Proposed method (without thinning)

   (a) (b)

   Figure 3. Extracted edges for the test image house a) original image b) Sobel operator c) Prewitt operator d) Cannys method e) Method proposed in [12] without tinning and f) Proposed method (without thinning)

   (a) (b)

   (c) (d)

   (e)

   (f)

   1. D. S. Lu, C. C. Chen, "Edge Detection Improvement by Ant Colony Optimization", Pattern Recognition Letters, vol. 29(4), pp. 416-425, 2008.

   2. H. Nezamabadi-pour, S. Saryazdi and E. Rashedi, "Edge Detection using Ant Algorithms", Soft Computing, vol. 10, pp. 63-68, 2006.

   3. A. Rezaee, "Extracting Edges of Images with Ant Colony", Journal of Electrical Engineering, vol. 59(1), pp. 57- 59, 2008.

   4. J. Tian, W. Yu, S. Xie, "An Ant Colony Optimization Algorithm for Image Edge Detection", IEEE Congress on Evolutionary Computation, 2008.

   5. J. Tian, W. Yu, L. Chen, L. Ma, "Image Edge Detection using Variation-Adaptive Ant Colony Optimization", Transactions on Computational Collective Intelligence V,

   Figure 4. Extracted edges for the test image polygons a) original image b) Sobel operator c) Prewitt operator d) Cannys method e) Method proposed in [12] without thinning and f) Proposed method (without thinning)

6. Conclusion

   This paper presents a modified ACO-based edge detection technique. Heuristic function is determined based on the edge magnitude obtained using Laplacian operator. Fuzzy c-means clustering based thresholding is used to determine whether a pixel is edge pixel or not. Experimental results show that the proposed technique gives better results.

7. References

1. L. S. Davis, "Edge Detection Techniques", Computer Graphics and Image Processing, vol. 4, pp. 248-270, 1995.

2. V. B. Anna and O. Carlos, "Image Edge Detection using Ant Colony Optimization", International Journal of Circuits, Systems and Signal Processing, vol. 4(2), pp. 25-33, 2010.

3. O. P. Verma, M. Hanmandlu, A. K. Sultania, Dhruv, "A Novel Fuzzy Ant System for Edge Detection", Proceedings of 2010 IEEE/ACIS 9th International Conference on Computer and Information Science, IEEE Computer Society Washington, DC, USA, 2010.

4. M. Dorigo and T. Stutzle, Ant Colony Optimization, Cambridge: MIT Press, 2004.

5. H. B. Duan, Ant Colony Algorithms: Theory and Applications, Beijing: Science Press, 2005.

6. M. Dorigo, V. Maniezzo and A. Colorni, "Ant System: Optimization by a Colony of Cooperating Agents", IEEE Transactions on Systems, Man and Cybernetics, Part B, vol. 26, pp. 29-41, February 1996.

7. M. Dorigo and L. M. Gambardella, "Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem", IEEE Transactions on Evolutionary Computation, vol. 1, pp. 53-66, 1997.

8. Y. P. Wong, V. C. M. Soh, K. W. Ban, Y. T. Bau, "Improved Canny Edges using Ant Colony Optimization", Proceedings of 5th International Conference on Computer Graphics, Imaging and Visualization, pp. 197-202, 2008.

Lectures Notes in Computer Science, 6910, pp. 27-40, 2011.

1. M. Dorigo, M. Birattari and T. Stutzle, "Ant Colony Optimization", IEEE Computational Intelligence Magazine, vol. 1, pp. 28-39, November 2006.

2. D. Aydin, "A Modified Ant-Based Approach to Edge Detection", N. T. Nguyen, R. Kowalezyk and S. M. Chen Eds. ICCCI 2009, LNAI, vol. 5796, pp. 620-628, Springer- Verlag Berlin Heidelberg 2009.

3. D. Kim, W. Lee, I. Kweon, "Automatic Edge Detection using 3×3 Ideal Binary Pixel Patterns and Fuzzy-based Edge Thresholding", Pattern Recognition Letters, vol. 25, no. 1, pp. 101-106, 2004.

4. C. C. Kanga, W. J. Wang, "A Novel Edge Detection Method based on the Maximizing Objective Function", Pattern Recognition, vol. 40, no. 2, pp. 609-618, 2007.

5. D. Gilbarg, N. Trudinger, Elliptic Partial Differential Equations of Second Order, Springer, 2001.

6. N. Otsu, "A Threshold Selection Method from Gray Level Histograms", IEEE Transactions on Systems, Man and Cybernetics, vol. 9, pp. 62-66, January 1979.

7. J. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Plenum, New York, 1981.