·
Cihan
Topal cihant
[at] anadolu [dot] edu
[dot] tr
·
Cuneyt
Akinlar cakinlar [at] anadolu [dot] edu [dot] tr
Edge Drawing (ED) is a novel and unorthodox
edgedetection algorithm that runs realtime and produces high quality edge
maps. Unlike traditional reactive edge detectors, which work by eliminating
nonedge pixels, ED is proactive: ED first computes a set of pixels (called the
anchors), which have a very high likelihood of being edge pixels. ED then uses
a smart routing algorithm to link the anchors (hence the name Edge Drawing), and
obtain the final edge map. The whole process is similar to children’s dottodot
boundary completion puzzles, where a child is given a dotted boundary of an
object, and s/he is asked to draw the boundary by connecting the dots. Not only
ED runs in blazing realtime speed, it also produces clean, wellconnected,
1pixel wide edge segments, each of which is a set of pixel chains in vector
form.
Video
A
good edge detector must produce high quality edge maps, and it must run very
fast. The speed of the detector is especially important for realtime computer
vision and image processing applications. Among the existing edge detectors,
Canny is generally considered to produce the best results, and is assumed to be
the defacto edge detector by the computer vision and image processing
community. OpenCV implementation of Canny (cvCanny function) is the fastest known implementation of
this famous edge detector, and is used by many realtime computer vision and
image processing applications.
Figure 1 shows the edge map for the famous Lena image obtained by OpenCV Canny, where some of the low quality edge patches
have been highlighted. Clearly, the edge map itself is of low quality
consisting of edge segments with ragged, discontinuous, unattended, multipixel
wide edges. This is because the conventional edge detectors including Canny
evaluate pixels in an isolated and individual manner and generally ignore
interpixel relations, which leads to such discontinuities, individual and
unattended edge segment formations.
Evaluation
of the existing edge detectors for realtime applications has clearly shown the
need for a new edge detector that satisfies the following requirements: (1)
runs very fast, i.e., realtime, (2) produces high quality edge maps consisting
of coherent, contiguous, welllocalized, 1pixel wide edges. Below, we propose
Edge Drawing (ED) [1] as a novel and unorthodox edge or boundary detection
algorithm that satisfies both of these requirements. ED further distinguishes
itself from other edge detectors by not only producing a traditional binary
edge map, but by outputting the edge map in vector form as a set of edge
segments, each consisting of a contiguous chain of pixels.
Edge
Drawing (ED) works on grayscale images and is comprised of 4 steps:
(1)
Suppression of noise by Gaussian filtering,
(2)
Computation of the gradient magnitude and edge direction maps,
(3) Extraction of the anchors (peaks of the gradient map),
(4) Linking of the anchors by smart routing to compute the final
edge map.
The
very first step of ED is similar to most image processing methods: We process
the image with a Gaussian kernel to suppress noise and smooth out the image.
Any of the wellknown Gauss filters can be used at this step. For all results
given below, a 5x5 Gaussian kernel with is used. Depending on
the structure and strength of noise, other types of smoothing filters can be
used.
The
next step of ED is to compute the gradient magnitude and edge direction maps.
Figure
2: Computation of the
gradient magnitude and edge direction maps.
Figure 2 depicts the computation
of the gradient magnitude and edge direction maps. Using the smoothed image, we
compute the horizontal and vertical gradients, Gx and
Gy, respectively. Any of the wellknown gradient
operators, e.g., Prewitt, Sobel, Scharr,
etc., can be used at this step. The gradient magnitude G at a pixel is then
obtained by simply adding Gx and Gy,
i.e., G = Gx + Gy.
Simultaneously with the gradient magnitude map, the edge direction map is also
computed by simply comparing the horizontal and vertical gradients at each
pixel. If the horizontal gradient is bigger, i.e., Gx
>= Gy, a vertical edge is assumed to pass
through the pixel. Otherwise, a horizontal edge is assumed to pass through the
pixel. So, the gradient angle at a pixel is assumed to be either 0 or 90
degrees. Our experiments have shown that using two gradient angles were enough
to smartly route the anchor linking process. Increasing the number of gradient
angles simply increases the computational time without aiding the linking
process.
(a) (b)
Figure 3:
(a) Input image Lena, (b)Thresholded
image with respect to gradient magnitudes. The Sobel
operator and a threshold of 36 were used to obtain this image.
To
help us ignore nonedge pixels and speed up the computation, we threshold the
gradient map and eliminate the so called “weak” pixels. This is very similar to
Canny’s elimination of weak pixels by a low threshold
[3]: Recall that after the computation of the gradient map, Canny eliminates
those pixels where the gradient magnitude is smaller than a userdefined low
threshold. These are pixels that may not contain an edge element (edgel). We use the same idea, and eliminate those pixels
where the gradient magnitude is smaller than a certain userdefined threshold.
Figure 3(a) shows the Lena image, and Figure 3(b) shows the corresponding thresholded gradient map. To obtain this gradient map, we
used the Sobel operator and a gradient threshold of
36. Black pixels are those where the Sobel operator
produces a gradient value smaller than 36, and all other pixels are marked as
white. We call this the “edge areas” image. All edgels
of the image must reside within the boundaries of the edge areas. None of the
eliminated black pixels may contain an edgel.
The
first two steps of ED (gauss filtering and gradient map computation) are
similar to most edge detection algorithms. After the computation of the edge
areas image however, ED follows a very unorthodox approach: Instead of testing
individual pixels within the edge areas for being edgels,
ED first spots a subset of pixels (called the anchors) and then links these
anchors by a heuristic smart routing algorithm. Intuitively, anchors correspond
to peaks (maximas) of the gradient map. If you
visualize the gradient map in 3D, anchors would be the peaks of the mountains.
Figure 4:
Part of the gradient map from Lena’s hat (left), and the corresponding 3D view.
Two sample anchors are marked with red circles, Arrows
indicate the anchor linking directions.
Figure
4 shows the 3D view of the gradient map of part of Lena’s hat. Clearly, the
gradient operator produces maximum values at edge/boundary crossings. That is, edgels are located on top of the gradient mountain. Anchors
(marked with red circles) are the peaks of this mountain. ED would first
identify these peaks (anchors) and then link them with a smart routing
procedure.
Symbols used in the algorithm: (x, y): Pixel being processed G: Gradient map D: Direction map IsAnchor(x, y, G, D, ANCHOR_THRESH){ if (D[x, y] == HORIZONTAL){ // Compare with up & down if (G[x, y] – G[x, y1]
>= ANCHOR_THRESH && G[x, y] – G[x, y+1] >= ANCHOR_THRESH)
return true; } else { //
VERTICAL EDGE. Compare with left & right. if (G[x, y] – G[x1, y]
>= ANCHOR_THRESH && G[x, y] – G[x+1, y] >= ANCHOR_THRESH)
return true; } //endelse return false; //
Not an anchor } //endIsAnchor 
Table 1: Algorithm to test for an anchor at (x, y)
Table
1 shows our algorithm to check a pixel (x, y) for being an anchor. Since an
anchor must be a peak of the gradient map, we simply compare the pixel’s
gradient value with its neighbors. For a horizontal edge, the up and down
neighbors are compared; for a vertical edge, left and right neighbors are
compared. If the pixel’s gradient value is bigger than both of its neighbors by
a certain threshold (ANCHOR_THRESH), the pixel is marked to be an anchor. By
changing the anchor threshold, the number of anchors can be adjusted.
Furthermore, anchor testing can be performed at different scan intervals, i.e.,
every row/column, every second row/column etc. Increasing the number of anchors
would increase the details of the edge map, and vice versa. We also note that
anchor extraction is a generic procedure, and other anchor extraction methods
can be used instead of the one given in Table 1.
(a)
(b)
Figure
5: (a) Anchors, (b) Final
edge map produced by ED.
Figure
5(a) shows a set of anchors for the Lena image for an anchor threshold of 8,
and a scan interval of 4; that is, every 4th row or column has been scanned to
test for anchors. Scanning every row and column would produce more anchors.
Increasing the scan interval would decrease the number of anchors. General rule
of thumb is the following: If all details of the image are requested, a scan
interval of 1 should be used. If only the long edges are requested (i.e., a
skeleton of the object boundaries), a larger scan interval can be used. Thus,
the amount of detail in the final edge map can easily be adjusted by changing
this parameter.
The
final step of ED is the linking of anchors by drawing edges between them.
Recall that anchors correspond to the peaks of the gradient map. To link
consecutive anchors, we simply go from one peak (anchor) to the next by walking
over the cordillera of the gradient map. This process is guided by the gradient
magnitude and direction maps computed in step 2 of the algorithm.
Figure
6: (a) Horizontal, (b)
Vertical walks in smart routing.
The
smart routing process works as follows: Starting at an anchor, we look at the
direction of the edge passing through the anchor. If a horizontal edge passes
through the anchor, we start the linking process by walking to the left and to
the right (refer to Figure 6(a)). If a vertical edge passes through the anchor,
we start the linking process by walking up and down (refer to Figure 6(b)).
During a walk, only 3 immediate neighbors are considered, and the one having
the maximum gradient value is picked. The walk stops under 2 conditions:
Symbols used in the algorithm: (x, y): Starting pixel G: Gradient map D: Direction map E: Edge map GoLeft(x, y, G, D, E){ while (G[x, y] > 0
&& D[x, y] == HORIZONTAL && E[x, y] != EDGE){ E[x, y] = EDGE; //
Mark this pixel as an edgel // Look at 3 neighbors to the left & pick the one with the max.
gradient value if (G[x1, y1] > G[x1, y]
&& G[x1, y1] > G[x1, y+1]){ x = x1; y =
y1; // UpLeft } else if (G[x1, y+1]
> G[x1, y] && G[x1, y+1] > G[x1, y1]){ x = x1; y =
y+1; // DownLeft } else { x = x1; //
StraightLeft } //endelse } //endwhile } //endGoLeft 
Table
2: Algorithm to walk left of
an anchor at (x, y)
The
algorithm in Table 2 describes smart routing starting at an anchor (x, y). We
assume that a horizontal edge passes through this anchor and we give the
algorithm to walk left of the anchor. Going right, up or down would be very
similar, and are not elaborated. Starting at an anchor (x, y), we continue
walking left for as long as the 3 conditions listed above are satisfied. At
each iteration of the loop, we simply look at the 3 immediate neighbors to the
left, i.e., (x1, y1), (x1, y) and (x1, y+1), and pick the one having the
greatest gradient value. If we were to walk right, we would have considered 3
immediate neighbors to the right, i.e., (x+1, y1), (x+1, y) and (x+1, y+1).
(a)
(b)
Figure
7: (a) An illustration of
the smart routing procedure, (b) Detected edge segments for Lena.
A
detailed illustration of the smart routing procedure is given in Figure 7(a) on
a magnified region of a thresholded gradient map.
Numbers inside the pixels are the gradient magnitudes; the black pixels
represent the thresholded pixels. Anchors are marked
with red circles and the pixels collected during the linking process are labeled
with yellow circles. Assume that the pixel at (8, 4) is the starting anchor.
Since a horizontal edge is passing through this anchor, a horizontal walk
(first to the left and then to the right) is initiated. Small arrows show the
pixels being considered during the routing process, and the blue arrows
indicate the selected pixels. As seen, 3 immediate neighbors are checked at each iteration with respect to the edge direction, and
the pixel having the greatest gradient value is always selected.
Figure
5(b) shows the edge map produced by ED for the Lena image. Clearly, this is a
very high quality edge map with all details detected, consisting of coherent,
contiguous, 1pixel wide edges. ED not only produces this binary edge map, it
also generates the output as a set of edge segments each made up of a pixel
chain in vector form. Each such chain is thus a contour and can used for
further processing to perform object detection, tracking, registration etc.
Figure 7(b) shows the edge segments detected for Lena. There are 432 segments
in this edge map, with each color representing a different edge segment.
In
this section, we compare the performance of ED to OpenCV
implementation of the famous Canny edge detector. We
use Canny for comparison because it is considered to produce the best results
on a variety of images, and OpenCV implementation of
Canny (cvCanny function) is used as the defacto edge
detector by many realtime computer vision and image processing applications.
We first present edge map results on some of the most challenging images. We
then compare the running time of ED and OpenCV Canny
on these images.
(a) (b) (c)
Figure 8: (a) Original image (512x512), (b) OpenCV
Canny edge map for low threshold = 60 and high threshold = 100, (c) ED edge map
with Sobel operator, gradient threshold = 36 and
anchor threshold = 8.
Figure 8 shows the edge maps
produced by OpenCV Canny (cvCanny)
and ED for 4 challenging images. To obtain these results, we used a Canny low threshold of 60, and a high threshold of 100. For
ED, we used the Sobel operator with a gradient
threshold of 36 and an anchor threshold of 8. Looking at the resulting edge maps,
we see that Canny’s edge maps contain a lot of
disjoint, unattended noisy edgels. On the other hand,
ED’s edge maps are very clean consisting of coherent, contiguous,
welllocalized and 1pixel wide edgels. Additionally,
ED’s result is returned as a set of edge segments each consisting of a
contiguous chain of pixels as depicted in Figure 7(b).
Figure 9: (Toptobottom, Lefttoright) ED’s edge map for scan intervals
of 8, 16, 32 and 64 respectively. Sobel operator and
a gradient threshold of 36 were used to obtain all edge maps.
Figure 9 shows the effects of the
number of anchors on the final edge map. As we stated before, more anchors in
the linking step lead to more detailed edge maps and vice versa. In Figure 9,
the scan interval for anchor computation is changed from 8 to 64. Specifically,
to obtain the topleft edge map, we scan every 8th row or column during the
anchor computation step. Continuing right and down we respectively scan every
16th, 32nd and 64th row or column. As the number of anchors decrease, so are
the details in the final edge maps. Notice that the general skeleton of the
objects in the image is always extracted. It is only the small details that get
lost. This is due to the fact that a single anchor on a long boundary is enough
to extract the entire boundary. Therefore, even if we have a few anchors on the
long boundaries of the objects, ED would be able to extract these long
boundaries during the anchor linking process.
Image 

Edge Drawing (ms) 
OpenCV Canny (ms) 

Gauss Filtering 
Gradient Computation 
Anchor Extraction 
Anchor Linking 
Total (ms) 

lena 
512x512 
1.56 
2.80 
2.07 
2.30 
8.73 
8.44 

peppers 
512x512 
1.56 
2.80 
1.91 
2.05 
8.32 
8.14 

mandrill 
512x512 
1.56 
2.80 
4.74 
7.16 
16.26 
13.03 

chairs 
512x512 
1.56 
2.80 
2.00 
2.60 
8.96 
8.38 

Table 2: Dissection of the running times of ED and OpenCV
Canny on four images given in figure 8. The running times were obtained in a PC
with a 3Ghz P4 processor and 1 GB RAM.
Table 2 shows the dissection of
the running times of ED and OpenCV Canny on four
images given in Figure 8. The processing times were obtained in a PC with a 3 Ghz Intel P4 processor and 1 GB RAM. Clearly, ED runs
realtime and is almost as fast as OpenCV Canny. But
recall that ED not only generates better binary edge maps, but it also
generates edge maps as edge segments, each consisting of a pixel chain in
vector form. To generate edge segments as pixels chains from OpenCV Canny’s binary edge map
would not only require extra processing, but it would also produce inferior
results due to the noisy structure of Canny’s edge
map. ED however, produces these contour chains by default without the need for
extra processing.