25-08-2017, 09:32 PM
Ant Colony Optimization for Image Edge Detection
[attachment=65673]
Introduction
Ant colony optimization (ACO) is a nature-inspired
optimization algorithm [1], [2], that is motivated by the
natural foraging behavior of ant species. Ants deposit
pheromone on the ground to mark paths between a food
source and their colony, which should be followed by
other members of the colony. Over time, pheromone
trails evaporate. The longer it takes for an ant to travel
down the path and back again, the more time the
pheromones have to evaporate. Shorter – and thus,
favorable – paths get marched over faster and receive
greater compensation for pheromone evaporation.
Pheromone densities remain high on shorter paths
because pheromone is laid down faster. This positive
feedback mechanism eventually leads the ants to follow
the shorter paths. It is this natural phenomenon that
inspired the development of the ACO metaheuristic.
Dorigo et al. [3] proposed the first ACO algorithm, ant
system (AS) [1]-[3]. Since then, extensions to AS have
been developed, such as ant colony system (ACS) [1],
[2] and MAX-MIN ant system (MMAS) [1], [2]. ACO
has been used to solve a wide variety of optimization
problems.
In this paper, an ACO-based method for image edge
detection is proposed. Edge detection aims to localize
the boundaries of objects in an image and is a basis for
image analysis and machine vision. In the proposed
ACO-based approach, artificial ants are distributed over
an image and moved based on the local variation of the
image’s intensity values. The movement of ants
establishes a pheromone matrix that represents the edge
information at each pixel location in the image. The
method makes use of the improvements introduced in
ACS, a variant ACO which is based on the original AS.
2 Image Edge Detection
Image edge detection refers to the extraction of the
edges in a digital image. It is a process whose aim is to
identify points in an image where discontinuities or
sharp changes in intensity occur. This process is crucial
to understanding the content of an image and has its
applications in image analysis and machine vision. It is
usually applied in initial stages of computer vision
applications.
The purpose of detecting sharp changes in image
intensity is to capture significant events and changes in
the physical properties of the world. Under general
assumptions about the image formation process,
discontinuities in intensity usually correspond to
discontinuities in depth, discontinuities in surface
orientation, changes in material properties, and
variations in scene illumination. A representation of an
image in terms of its edges is compact because it uses a
set of one-dimensional curves instead of a twodimensional
pattern. Hence, edges have been used as
main features in many computer vision algorithms.
Conventional approaches to edge detection are
computationally expensive because each set of
operations is conducted for each pixel. In conventional
approaches, the computation time quickly increases with
the size of the image. An ACO-based approach has the
potential of overcoming the limitations of conventional
methods. Furthermore, it can readily be parallelized,
which makes the algorithm easily adaptable for
distributed systems.
Several ACO-based approaches to the edge detection
problem have been proposed [4]-[7]. Previously reported
ACO-based approaches to image edge detection, to the
best of the author’s knowledge, all use a decision rule
that is based on AS. AS is the first ACO algorithm.
Since its development, a number of extensions have
emerged. One of the successful ones is ACS. This paper
presents a technique derived from distinguishing
features of ACS. One of the significant aspects of ACS
is the form of decision rule used, the pseudorandom
proportional rule. The approach presented in this paper
uses such rule in the tour construction process.
Proposed Edge Detection Method
This section provides a theoretical discussion on the ant
colony optimization metaheuristic and ant colony
system, one of the main extensions to AS. The
theoretical discussion is followed by a discussion on the
proposed ACO-based image edge detection technique.
3.1 Ant Colony Optimization
ACO is a probabilistic technique for finding optimal
paths in fully connected graphs through a guided search,
by making use of the pheromone information. This
technique can be used to solve any computational
problem that can be reduced to finding good paths on a
weighted graph. In an ACO algorithm, ants move
through a search space, the graph, which consists of
nodes and edges. The movement of the ants is
probabilistically dictated by the transition probabilities.
The transition probability reflects the likelihood that an
ant will move from a given node to another. This value
is influenced by the heuristic information and the
pheromone information. The heuristic information is
solely dependent on the instance of the problem.
Pheromone values are used and updated during the
search. Fig. 1 shows a pseudocode of the general
procedure in an ACO metaheuristic.
Conclusion
An ACO-based image edge detection method that takes
advantage of the improvements introduced in ACS has
been successfully implemented. The proposed method
produced acceptable results within reasonable amounts
of time.
[attachment=65673]
Introduction
Ant colony optimization (ACO) is a nature-inspired
optimization algorithm [1], [2], that is motivated by the
natural foraging behavior of ant species. Ants deposit
pheromone on the ground to mark paths between a food
source and their colony, which should be followed by
other members of the colony. Over time, pheromone
trails evaporate. The longer it takes for an ant to travel
down the path and back again, the more time the
pheromones have to evaporate. Shorter – and thus,
favorable – paths get marched over faster and receive
greater compensation for pheromone evaporation.
Pheromone densities remain high on shorter paths
because pheromone is laid down faster. This positive
feedback mechanism eventually leads the ants to follow
the shorter paths. It is this natural phenomenon that
inspired the development of the ACO metaheuristic.
Dorigo et al. [3] proposed the first ACO algorithm, ant
system (AS) [1]-[3]. Since then, extensions to AS have
been developed, such as ant colony system (ACS) [1],
[2] and MAX-MIN ant system (MMAS) [1], [2]. ACO
has been used to solve a wide variety of optimization
problems.
In this paper, an ACO-based method for image edge
detection is proposed. Edge detection aims to localize
the boundaries of objects in an image and is a basis for
image analysis and machine vision. In the proposed
ACO-based approach, artificial ants are distributed over
an image and moved based on the local variation of the
image’s intensity values. The movement of ants
establishes a pheromone matrix that represents the edge
information at each pixel location in the image. The
method makes use of the improvements introduced in
ACS, a variant ACO which is based on the original AS.
2 Image Edge Detection
Image edge detection refers to the extraction of the
edges in a digital image. It is a process whose aim is to
identify points in an image where discontinuities or
sharp changes in intensity occur. This process is crucial
to understanding the content of an image and has its
applications in image analysis and machine vision. It is
usually applied in initial stages of computer vision
applications.
The purpose of detecting sharp changes in image
intensity is to capture significant events and changes in
the physical properties of the world. Under general
assumptions about the image formation process,
discontinuities in intensity usually correspond to
discontinuities in depth, discontinuities in surface
orientation, changes in material properties, and
variations in scene illumination. A representation of an
image in terms of its edges is compact because it uses a
set of one-dimensional curves instead of a twodimensional
pattern. Hence, edges have been used as
main features in many computer vision algorithms.
Conventional approaches to edge detection are
computationally expensive because each set of
operations is conducted for each pixel. In conventional
approaches, the computation time quickly increases with
the size of the image. An ACO-based approach has the
potential of overcoming the limitations of conventional
methods. Furthermore, it can readily be parallelized,
which makes the algorithm easily adaptable for
distributed systems.
Several ACO-based approaches to the edge detection
problem have been proposed [4]-[7]. Previously reported
ACO-based approaches to image edge detection, to the
best of the author’s knowledge, all use a decision rule
that is based on AS. AS is the first ACO algorithm.
Since its development, a number of extensions have
emerged. One of the successful ones is ACS. This paper
presents a technique derived from distinguishing
features of ACS. One of the significant aspects of ACS
is the form of decision rule used, the pseudorandom
proportional rule. The approach presented in this paper
uses such rule in the tour construction process.
Proposed Edge Detection Method
This section provides a theoretical discussion on the ant
colony optimization metaheuristic and ant colony
system, one of the main extensions to AS. The
theoretical discussion is followed by a discussion on the
proposed ACO-based image edge detection technique.
3.1 Ant Colony Optimization
ACO is a probabilistic technique for finding optimal
paths in fully connected graphs through a guided search,
by making use of the pheromone information. This
technique can be used to solve any computational
problem that can be reduced to finding good paths on a
weighted graph. In an ACO algorithm, ants move
through a search space, the graph, which consists of
nodes and edges. The movement of the ants is
probabilistically dictated by the transition probabilities.
The transition probability reflects the likelihood that an
ant will move from a given node to another. This value
is influenced by the heuristic information and the
pheromone information. The heuristic information is
solely dependent on the instance of the problem.
Pheromone values are used and updated during the
search. Fig. 1 shows a pseudocode of the general
procedure in an ACO metaheuristic.
Conclusion
An ACO-based image edge detection method that takes
advantage of the improvements introduced in ACS has
been successfully implemented. The proposed method
produced acceptable results within reasonable amounts
of time.