Edge Drawing – A Combined Real-Time Edge/Edge Segment Detector

Text Box: Demonstration Text Box: Download
 

 

 


Authors

·         Cihan Topal         cihant [at] anadolu [dot] edu [dot] tr

·         Cuneyt Akinlar     cakinlar [at] anadolu [dot] edu [dot] tr

 

Summary

 

Edge Drawing (ED) is a novel and unorthodox edge-detection algorithm that runs real-time and produces high quality edge maps. Unlike traditional reactive edge detectors, which work by eliminating non-edge 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 dot-to-dot 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 real-time speed, it also produces clean, well-connected, 1-pixel wide edge segments, each of which is a set of pixel chains in vector form.

 

References

  1. C. Topal, C. Akinlar, Edge Drawing: A Combined Real-Time Edge and Segment Detector,” Journal of Visual Communication and Image Representation, 23(6), 862-872, 2012.
  2. C. Topal, C. Akinlar, and Y. Genc, Edge Drawing: A Heuristic Approach to Robust Real-Time Edge Detection, Proceedings of the ICPR, pp. 2424-2427, August 2010.



 

Video

 

The need for a new Edge Detector

 

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 real-time 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 de-facto 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 real-time 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, multi-pixel wide edges. This is because the conventional edge detectors including Canny evaluate pixels in an isolated and individual manner and generally ignore inter-pixel relations, which leads to such discontinuities, individual and unattended edge segment formations.

 

Evaluation of the existing edge detectors for real-time applications has clearly shown the need for a new edge detector that satisfies the following requirements: (1) runs very fast, i.e., real-time, (2) produces high quality edge maps consisting of coherent, contiguous, well-localized, 1-pixel 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.

 

Overview of Edge Drawing (ED)

 

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.                                   

 

Step1: Gaussian Filtering

 

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 well-known 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.

 

Step2: Computation of the Gradient Magnitude and Edge Direction Maps

 

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 well-known 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.

 

Description: InputImage Description: GradImgBW

(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 non-edge 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 user-defined 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 user-defined 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.

 

Step3: Extraction of the Anchors

 

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, y-1] >= 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[x-1, y] >= ANCHOR_THRESH &&

             G[x, y] – G[x+1, y] >= ANCHOR_THRESH) return true;

    } //end-else

 

    return false;    // Not an anchor

}  //end-IsAnchor

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.

 

Description: AnchorsImg4 Description: EdgeDrawing

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

 

Step4: Linking of the Anchors by Smart Routing

 

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:

  1. We move out of the edge areas, i.e., the thresholded gradient value of the current pixel is 0.
  2. We encounter a previously detected edgel.

 

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[x-1, y-1] > G[x-1, y] && G[x-1, y-1] > G[x-1, y+1]){

            x = x-1; y = y-1;    // Up-Left

 

        } else if (G[x-1, y+1] > G[x-1, y] && G[x-1, y+1] > G[x-1, y-1]){

            x = x-1; y = y+1;  // Down-Left

 

      } else {

          x = x-1;                 // Straight-Left

      } //end-else

    } //end-while

}  //end-GoLeft

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., (x-1, y-1), (x-1, y) and (x-1, 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, y-1), (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, 1-pixel 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.

 

Experiments

 

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 de-facto edge detector by many real-time 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.

 

Description: Lena Description: C:\cygwin\home\cakinlar\NewPapers\EdgeDrawing-WebSite\Figs\Lena-Canny.bmp Description: C:\cygwin\home\cakinlar\NewPapers\EdgeDrawing-WebSite\Figs\Lena-ED.bmp

Description: Peppers Description: C:\cygwin\home\cakinlar\NewPapers\EdgeDrawing-WebSite\Figs\peppers-Canny.bmp Description: C:\cygwin\home\cakinlar\NewPapers\EdgeDrawing-WebSite\Figs\Peppers-ED8.bmp

Description: Mandril Description: C:\cygwin\home\cakinlar\NewPapers\EdgeDrawing-WebSite\Figs\Mandril-Canny.bmp Description: C:\cygwin\home\cakinlar\NewPapers\EdgeDrawing-WebSite\Figs\Mandril-ED.bmp

Description: Chairs Description: C:\cygwin\home\cakinlar\NewPapers\EdgeDrawing-WebSite\Figs\Chairs-Canny.bmp Description: C:\cygwin\home\cakinlar\NewPapers\EdgeDrawing-WebSite\Figs\Chairs-ED.bmp

(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, well-localized and 1-pixel 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).

 

Description: C:\cygwin\home\cakinlar\NewPapers\EdgeDrawing-WebSite\Figs\Peppers-ED8.bmp Description: C:\cygwin\home\cakinlar\NewPapers\EdgeDrawing-WebSite\Figs\Peppers-ED16.bmp

 Description: C:\cygwin\home\cakinlar\NewPapers\EdgeDrawing-WebSite\Figs\Peppers-ED32.bmp Description: C:\cygwin\home\cakinlar\NewPapers\EdgeDrawing-WebSite\Figs\Peppers-ED64.bmp

Figure 9: (Top-to-bottom, Left-to-right) 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 top-left 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 real-time 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.

 

Description: Description: Locations of visitors to this page