Page 234 -

4.2 Edges 213

Once we have computed the sign function S(x), we must find its zero crossings and
convert these into edge elements (edgels). An easy way to detect and represent zero crossings
is to look for adjacent pixel locations x i and x j where the sign changes value, i.e., [S(x i ) >
0] =[S(x j ) > 0].
The sub-pixel location of this crossing can be obtained by computing the “x-intercept” of
the “line” connecting S(x i ) and S(x j ),

x i S(x j ) − x j S(x i )
x z = . (4.25)
S(x j ) − S(x i )
The orientation and strength of such edgels can be obtained by linearly interpolating the
gradient values computed on the original pixel grid.
An alternative edgel representation can be obtained by linking adjacent edgels on the
dual grid to form edgels that live inside each square formed by four adjacent pixels in the
5
original pixel grid. The (potential) advantage of this representation is that the edgels now
live on a grid offset by half a pixel from the original pixel grid and are thus easier to store
and access. As before, the orientations and strengths of the edges can be computed by
interpolating the gradient field or estimating these values from the difference of Gaussian
image (see Exercise 4.7).
In applications where the accuracy of the edge orientation is more important, higher-order
steerable filters can be used (Freeman and Adelson 1991) (see Section 3.2.3). Such filters are
more selective for more elongated edges and also have the possibility of better modeling curve
intersections because they can represent multiple orientations at the same pixel (Figure 3.16).
Their disadvantage is that they are more expensive to compute and the directional derivative
of the edge strength does not have a simple closed form solution. 6

Scale selection and blur estimation
As we mentioned before, the derivative, Laplacian, and Difference of Gaussian filters (4.20–
4.23) all require the selection of a spatial scale parameter σ. If we are only interested in
detecting sharp edges, the width of the filter can be determined from image noise characteris-
tics (Canny 1986; Elder and Zucker 1998). However, if we want to detect edges that occur at
different resolutions (Figures 4.32b–c), a scale-space approach that detects and then selects
edges at different scales may be necessary (Witkin 1983; Lindeberg 1994, 1998a; Nielsen,
Florack, and Deriche 1997).
Elder and Zucker (1998) present a principled approach to solving this problem. Given
a known image noise level, their technique computes, for every pixel, the minimum scale
at which an edge can be reliably detected (Figure 4.32d). Their approach first computes
gradients densely over an image by selecting among gradient estimates computed at different
scales, based on their gradient magnitudes. It then performs a similar estimate of minimum
scale for directed second derivatives and uses zero crossings of this latter quantity to robustly
select edges (Figures 4.32e–f). As an optional final step, the blur width of each edge can
be computed from the distance between extrema in the second derivative response minus the
width of the Gaussian filter.
5
This algorithm is a 2D version of the 3D marching cubes isosurface extraction algorithm (Lorensen and Cline
1987).
6 In fact, the edge orientation can have a 180 ambiguity for “bar edges”, which makes the computation of zero
◦
crossings in the derivative more tricky.