Edge detection
Edge detection includes a variety of mathematical methods that aim at identifying edges, defined as curves in a digital image at which the image brightness changes sharply or, more formally, has discontinuities. The same problem of finding discontinuities in one-dimensional signals is known as step detection and the problem of finding signal discontinuities over time is known as change detection. Edge detection is a fundamental tool in image processing, machine vision and computer vision, particularly in the areas of feature detection and feature extraction.
Motivations
The purpose of detecting sharp changes in image brightness is to capture important events and changes in properties of the world.It can be shown that under rather general assumptions for an image formation model, discontinuities in image brightness are likely to correspond to:
- discontinuities in depth,
- discontinuities in surface orientation,
- changes in material properties and
- variations in scene illumination.
Thus, applying an edge detection algorithm to an image may significantly reduce the amount of data to be processed and may therefore filter out information that may be regarded as less relevant, while preserving the important structural properties of an image.
If the edge detection step is successful, the subsequent task of interpreting the information contents in the original image may therefore be substantially simplified.
However, it is not always possible to obtain such ideal edges from real life images of moderate complexity.
Edges extracted from non-trivial images are often hampered by fragmentation, meaning that the edge curves are not connected, missing edge segments as well as false edges not corresponding to interesting phenomena in the image – thus complicating the subsequent task of interpreting the image data.
Edge detection is one of the fundamental steps in image processing, image analysis, image pattern recognition, and computer vision techniques.
Edge properties
The edges extracted from a two-dimensional image of a three-dimensional scene can be classified as either viewpoint dependent or viewpoint independent.A viewpoint independent edge typically reflects inherent properties of the three-dimensional objects, such as surface markings and surface shape.
A viewpoint dependent edge may change as the viewpoint changes, and typically reflects the geometry of the scene, such as objects occluding one another.
A typical edge might for instance be the border between a block of red color and a block of yellow. In contrast a line can be a small number of pixels of a different color on an otherwise unchanging background. For a line, there may therefore usually be one edge on each side of the line.
A simple edge model
Although certain literature has considered the detection of ideal step edges, the edges obtained from natural images are usually not at all ideal step edges. Instead they are normally affected by one or several of the following effects:- focal blur caused by a finite depth-of-field and finite point spread function.
- penumbral blur caused by shadows created by light sources of non-zero radius.
- shading at a smooth object
Thus, a one-dimensional image that has exactly one edge placed at may be modeled as:
At the left side of the edge, the intensity is, and right of the edge it is
. The scale parameter is called the blur scale of the edge. Ideally this scale parameter should be adjusted based on the quality of image to avoid destroying true edges of the image.
Difficulty
Outside of images with simple objects or featuring well-controlled lighting, edge detection is not a trivial task, since it can be difficult to determine what threshold should be used to define an edge between two pixels. For example, in the following one-dimensional signal, most would intuitively say there is an edge between the 4th and 5th pixels:However, if the intensity difference between the 4th and the 5th pixels were smaller, it would not be as easy to say that there should be an edge in the corresponding region. Similarly, if the intensity differences between the adjacent neighboring pixels were higher, one could argue that more than one edge should be considered to exist, or even none at all.
Approaches
There are many methods for edge detection, but most of them can be grouped into two categories, search-based and zero-crossing based.The search-based methods detect edges by first computing a measure of edge strength, usually a first-order derivative expression such as the gradient magnitude, and then searching for local directional maxima of the gradient magnitude using a computed estimate of the local orientation of the edge, usually the gradient direction.
The zero-crossing based methods search for zero crossings in a second-order derivative expression computed from the image in order to find edges, usually the zero-crossings of the Laplacian or the zero-crossings of a non-linear differential expression. As a pre-processing step to edge detection, a smoothing stage, typically Gaussian smoothing, is almost always applied.
The edge detection methods that have been published mainly differ in the types of smoothing filters that are applied and the way the measures of edge strength are computed. As many edge detection methods rely on the computation of image gradients, they also differ in the types of filters used for computing gradient estimates in the x- and y-directions.
A survey of a number of different edge detection methods can be found in ; see also the encyclopedia articles on edge detection in Encyclopedia of Mathematics and Encyclopedia of Computer Science and Engineering.
Canny
considered the mathematical problem of deriving an optimal smoothing filter, given the criteria of detection, localization and minimizing multiple responses to a single edge. He showed that the optimal filter, given these assumptions, is a sum of four exponential terms. He also showed that this filter can be well approximated by first-order derivatives of Gaussians.Canny also introduced the notion of non-maximum suppression, which means that, given the presmoothing filters, edge points are defined as points where the gradient magnitude assumes a local maximum in the gradient direction.
Looking for the zero crossing of the 2nd derivative along the gradient direction was first proposed by Haralick.
It took less than two decades to find a modern geometric variational meaning for that operator, that links it to the Marr–Hildreth edge detector.
That observation was presented by Ron Kimmel and Alfred Bruckstein.
Although his work was done in the early days of computer vision, the Canny edge detector is still a state-of-the-art edge detector. Edge detectors that perform better than the Canny usually require longer computation times or a greater number of parameters.
Kovalevsky
has suggested a quite different approach. He uses a preprocessing of the image with the Sigma filter and with a special filter for the dilution of the ramps. This method uses no brightness of the image but only the intensities of the color channels which is important for detecting an edge between two adjacent pixels of equal brightness but different colors. The method scans the image two times: first along the horizontal lines and second along the vertical columns. In each horizontal line six consequent adjacent pixels are considered and five color difference between each two adjacent pixels are calculated. Each color difference is the sum of absolute differences of the intensities of the color channels Red, Green, and Blue of the corresponding adjacent pixels. If this sum is greater than a given threshold, then the sign of the color difference is set equal to the sign of the difference of the green intensities. If the green difference is zero, then the sign of the color difference is set equal to the sign of the difference of the red intensities. If, however, both the green and the red differences are zero, then the sign of the color difference is set equal to the sign of the blue difference which in this case cannot be zero since the sum is greater than the threshold.Certain conditions for the values and signs of the five color differences are specified in such way that if the conditions are fulfilled, then a short vertical stroke is put between the third and the fourth of the six pixels as the label of the edge.
Similar calculations are performed for the vertical columns. In this case a short horizontal stroke is put between the third and the fourth of the six subsequent pixels. The vertical and horizontal strokes mostly compose a connected sequence representing the edge.
This method is robust and very fast and, what is more important, it can detect edges between adjacent pixels of equal brightness’s if the color difference between these pixels is greater than the threshold.
The Canny–Deriche detector was derived from similar mathematical criteria as the Canny edge detector, although starting from a discrete viewpoint and then leading to a set of recursive filters for image smoothing instead of exponential filters or Gaussian filters.
The differential edge detector described below can be seen as a reformulation of Canny's method from the viewpoint of differential invariants computed from a scale space representation leading to a number of advantages in terms of both theoretical analysis and sub-pixel implementation. In that aspect, Log Gabor filter have been shown to be a good choice to extract boundaries in natural scenes.