There has been an abundance of work on different approaches to the detection of one dimensional features in images. The wide interest is due to the large number of vision applications which use edges and lines as primitives, to achieve higher level goals.

Some of the earliest methods of enhancing edges in images used small convolution masks to approximate the first derivative of the image brightness function, thus enhancing edges; e.g., see [50] and [67]. These filters give very little control over smoothing and edge localization.

In [34] Marr and Hildreth proposed the use of zero crossings of the Laplacian of a Gaussian (LoG). Contours produced using the LoG filter have the property, convenient for some purposes, of being closed. However, connectivity at junctions is poor, and corners are rounded. Also, the use of non-directional derivatives means that the edge response parallel to an edge is always measured (as well as the expected response perpendicular to it), reducing the signal to noise ratio. The use of directional first and second derivatives improves on this. Finally, the LoG filter gives no indication of edge direction, which may be needed by higher level processes.

In [8] Canny described what has since become one of the most widely used edge finding algorithms. The first step taken is the definition of criteria which an edge detector must satisfy (see Section 3). These criteria are then developed quantitatively into a total error cost function. Variational calculus is applied to this cost function to find an ``optimal'' linear operator for convolution with the image. The optimal filter is shown to be a very close approximation to the first derivative of a Gaussian. Non-maximum suppression in a direction perpendicular to the edge is applied, to retain maxima in the image gradient. Finally, weak edges are removed using thresholding. The thresholding is applied with hysteresis. Edge contours are processed as complete units; two thresholds are defined, and if a contour being tracked has gradient magnitude above the higher threshold then it is still ``allowed'' to be marked as an edge at those parts where the strength falls below this threshold, as long as it does not go below the lower value. This reduces streaking in the output edges.

The Gaussian convolution can be performed quickly because it is separable and a close approximation to it can be implemented recursively. However, the hysteresis stage slows the overall algorithm down considerably. While the Canny edge finder gives stable results, edge connectivity at junctions is poor, and corners are rounded, as with the LoG filter. The scale of the Gaussian determines the amount of noise reduction; the larger the Gaussian the larger the smoothing effect. However, as expected, the larger the scale of the Gaussian, the less accurate is the localization of the edge.

Canny also investigated the synthesis of results found at different scales; in some cases the synthesis improved the final output, and in some cases it was no better than direct superposition of the results from different scales.

Finally, Canny investigated the use of ``directional operators''. Here several masks of different orientation are used with the Gaussian scale larger along the direction parallel to the edge than the scale perpendicular to it. This improves both the localization and the reliability of detection of straight edges; the idea does not work well on edges of high curvature.

In [14] and [56] similar analytical approaches to that of Canny are taken, resulting in efficient algorithms which have exact recursive implementations. These algorithms give results which are very similar to Canny's.

In [22], Haralick proposes the use of zero crossings of the second directional derivative of the image brightness function. This is theoretically the same as using maxima in the first directional derivatives, and in one dimension is the same as the LoG filter. The zero crossings are found by fitting two dimensional functions to the image brightness surface and then analyzing the resulting fit (see the following section). The functions used are ``discrete orthogonal polynomials of up to degree three''. There is a problem with ``phantom edges'' created by the second directional derivative at ``staircase structures''. Connectivity at junctions is poor. In [18] Fleck describes the use of the second directional derivative for edge finding, with various extensions to the basic use of zero crossings. The problem of phantom edges is reduced with a test using the first and third derivatives. Image noise is reduced using topological sums; smoothing is achieved at potential edge points by measuring the local support they have for their ``edge point type'' classification. The overall algorithm (and in particular the noise reduction part) is computationally expensive.

The approach of surface fitting defines a two dimensional function which should be ``flexible'' enough to provide a good approximation to the image brightness function. The best fit of the function to the image is then found at each image position, and the parameters of the fit are used either to estimate image derivatives directly or to find edges using alternative definitions. The problem with the mathematical model approach is that deviations from the surface model cannot (by definition) be accommodated by varying the model's parameters. Work taking this approach includes [28], [42] and [59].

In [43] Noble uses mathematical morphology to find image structure. Several different morphological operations are described; these are used to enhance edges and find two dimensional features. The ``erode-dilate'' operator is similar to a first order derivative, and the ``open-close'' operator is similar to a second order derivative. Good quality edges are found by tracking both sides of each edge and then stitching these ``half boundaries'' together. Connectivity at junctions is good, although spurious short ``tails'' sometimes appear at structures such as ``T'' junctions. The algorithm, including edge tracking, is fairly computationally expensive.

In [72] and [70] Venkatesh, Owens et.\ al. describe the approach of using ``local energy'' (in the frequency domain) to find features. The local energy is found from quadrature pairs of image functions, such as the image function and its Hilbert transform. Fourier transforms of the image were initially used to find the required functions, at large computational cost. In a more ``realistic'' implementation also described, processing is performed using a function pair very similar to a first and a second derivative; this is shown to be equivalent to the method proposed originally. This approach has the advantage of being able to find a wider variety of edge types than that typically found using antisymmetric linear filters, however, this is at the expense of optimizing the signal to noise ratio. (In [9] Canny makes a similar point, when discussing the symmetric and antisymmetric components of a filter.) Other work taking this approach includes [48] and [53].

In [6] Blake and Zisserman used a weak membrane model in the framework of statistical regularization. The elements of the cost functional (which is to be globally minimized) are the smoothness of the estimated surface, the quality of the fit of the estimated surface to the original data and the ``line processes'', i.e., the discontinuities in the membrane. This method does not pick up fine complicated detail very well, and is computationally expensive. This approach has been developed further, for example, in [21], [44] and [68]. Other methods of using ``global'' support for edge detection include [45] and [23].

The edge detector described in this paper uses a completely new definition of edges, and in doing so, solves many of the problems which existing algorithms have failed to overcome.

LaTeX2HTML conversion by Steve Smith (steve@fmrib.ox.ac.uk)