 Open Access
 Total Downloads : 335
 Authors : R. Jothilakshmi, R. Rajeswari
 Paper ID : IJERTV3IS11145
 Volume & Issue : Volume 03, Issue 01 (January 2014)
 Published (First Online): 01022014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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 ACObased 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 ACObased 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.

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 [47], 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 ACObased approaches have been proposed for edge detection [813,2]. The approaches given in [89]
are used to enhance the edge information obtained using conventional techniques. The pure ACObased methods proposed in [1013,2] describe that ACO based approaches based on Ant System [46] and Ant Colony System [45,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. ACObased 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 ACObased approach to detect edges that edge magnitude obtained using Laplacian operator and thresholding based on fuzzy cmeans clustering to determine whether a pixel is an edge or not.

Ant Colony Optimization
ACO is a natureinspired technique that is designed based on ant colonies. Ant colonies have traillaying and trailfollowing 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 ACObased 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)

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 twodimensional (2D) 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 2D
(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 bestsofar solution for every construction step or for the entire algorithm is recorded. Pheromone
deposit by ant provides a positive feedback and thus

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.

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 8connectivity 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 ACObased 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.

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.

Proposed Modifications to ACO based approach for Edge Detection

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.

Thresholding based on Fuzzy CMeans 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 cmeans clustering method developed in [20].
Let x denote the 1D 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 ith 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)

Initialize matrix, , .

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 ACObased 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.

Calculate U (k 1) using
L
uij
1
 x c
 2
( i j )m1
k 1
 xi ck 
——————– (9)

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

(b)
2 ——————– (10)
where ci is the center of cluster i .


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
movementsteps 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)

(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)

(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)

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

H. Nezamabadipour, S. Saryazdi and E. Rashedi, "Edge Detection using Ant Algorithms", Soft Computing, vol. 10, pp. 6368, 2006.

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

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

J. Tian, W. Yu, L. Chen, L. Ma, "Image Edge Detection using VariationAdaptive 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)


Conclusion
This paper presents a modified ACObased edge detection technique. Heuristic function is determined based on the edge magnitude obtained using Laplacian operator. Fuzzy cmeans 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.

References

L. S. Davis, "Edge Detection Techniques", Computer Graphics and Image Processing, vol. 4, pp. 248270, 1995.

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. 2533, 2010.

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.

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

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

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. 2941, February 1996.

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. 5366, 1997.

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. 197202, 2008.
Lectures Notes in Computer Science, 6910, pp. 2740, 2011.

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

D. Aydin, "A Modified AntBased Approach to Edge Detection", N. T. Nguyen, R. Kowalezyk and S. M. Chen Eds. ICCCI 2009, LNAI, vol. 5796, pp. 620628, Springer Verlag Berlin Heidelberg 2009.

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

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

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

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

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