Ridge detection is the attempt, via software, to locate ridges (or edges) in an image.
Contents
- Differential geometric definition of ridges and valleys at a fixed scale in a two dimensional image
- Computation of variable scale ridges from two dimensional images
- History
- Definition of ridges and valleys in N dimensions
- Maximal Scale Ridge
- Relations between edge detection and ridge detection
- References
In mathematics and computer vision, the ridges (or the ridge set) of a smooth function of two variables are a set of curves whose points are, in one or more ways to be made precise below, local maxima of the function in at least one dimension. This notion captures the intuition of geographical ridges. For a function of N variables, its ridges are a set of curves whose points are local maxima in N − 1 dimensions. In this respect, the notion of ridge points extends the concept of a local maximum. Correspondingly, the notion of valleys for a function can be defined by replacing the condition of a local maximum with the condition of a local minimum. The union of ridge sets and valley sets, together with a related set of points called the connector set form a connected set of curves that partition, intersect, or meet at the critical points of the function. This union of sets together is called the function's relative critical set.
Ridge sets, valley sets, and relative critical sets represent important geometric information intrinsic to a function. In a way, they provide a compact representation of important features of the function, but the extent to which they can be used to determine global features of the function is an open question. The primary motivation for the creation of ridge detection and valley detection procedures has come from image analysis and computer vision and is to capture the interior of elongated objects in the image domain. Ridge-related representations in terms of watersheds have been used for image segmentation. There have also been attempts to capture the shapes of objects by graph-based representations that reflect ridges, valleys and critical points in the image domain. Such representations may, however, be highly noise sensitive if computed at a single scale only. Because scale-space theoretic computations involve convolution with the Gaussian (smoothing) kernel, it has been hoped that use of multi-scale ridges, valleys and critical points in the context of scale space theory should allow for more a robust representation of objects (or shapes) in the image.
In this respect, ridges and valleys can be seen as a complement to natural interest points or local extremal points. With appropriately defined concepts, ridges and valleys in the intensity landscape (or in some other representation derived from the intensity landscape) may form a scale invariant skeleton for organizing spatial constraints on local appearance, with a number of qualitative similarities to the way the Blum's medial axis transform provides a shape skeleton for binary images. In typical applications, ridge and valley descriptors are often used for detecting roads in aerial images and for detecting blood vessels in retinal images or three-dimensional magnetic resonance images.
Differential geometric definition of ridges and valleys at a fixed scale in a two-dimensional image
Let
Furthermore, let
of the scale-space representation
where p and q are coordinates of the rotated coordinate system.
It can be shown that the mixed derivative
Then, a formal differential geometric definition of the ridges of
Correspondingly, the valleys of
In terms of a
where
it can be shown that this ridge and valley definition can instead be equivalently be written as
where
and the sign of
Computation of variable scale ridges from two-dimensional images
A main problem with the fixed scale ridge definition presented above is that it can be very sensitive to the choice of the scale level. Experiments show that the scale parameter of the Gaussian pre-smoothing kernel must be carefully tuned to the width of the ridge structure in the image domain, in order for the ridge detector to produce a connected curve reflecting the underlying image structures. To handle this problem in the absence of prior information, the notion of scale-space ridges has been introduced, which treats the scale parameter as an inherent property of the ridge definition and allows the scale levels to vary along a scale-space ridge. Moreover, the concept of a scale-space ridge also allows the scale parameter to be automatically tuned to the width of the ridge structures in the image domain, in fact as a consequence of a well-stated definition. In the literature, a number of different approaches have been proposed based on this idea.
Let
where
An immediate consequence of this definition is that for a two-dimensional image the concept of scale-space ridges sweeps out a set of one-dimensional curves in the three-dimensional scale-space, where the scale parameter is allowed to vary along the scale-space ridge (or the scale-space valley). The ridge descriptor in the image domain will then be a projection of this three-dimensional curve into the two-dimensional image plane, where the attribute scale information at every ridge point can be used as a natural estimate of the width of the ridge structure in the image domain in a neighbourhood of that point.
In the literature, various measures of ridge strength have been proposed. When Lindeberg (1996, 1998) coined the term scale-space ridge, he considered three measures of ridge strength:
The notion of
There are also other closely related ridge definitions that make use of normalized derivatives with the implicit assumption of
History
The notion of ridges and valleys in digital images was introduced by Haralick in 1983 and by Crowley concerning difference of Gaussians pyramids in 1984. The application of ridge descriptors to medical image analysis has been extensively studied by Pizer and his co-workers resulting in their notion of M-reps. Ridge detection has also been furthered by Lindeberg with the introduction of
Definition of ridges and valleys in N dimensions
In its broadest sense, the notion of ridge generalizes the idea of a local maximum of a real-valued function. A point
Consider relaxing the condition that
This following ridge definition follows the book by Eberly and can be seen as a generalization of some of the abovementioned ridge definitions. Let
The point
-
λ n − 1 < 0 , and -
∇ x 0 f ⋅ e i = 0 fori = 1 , 2 , … , n − 1 .
This makes precise the concept that
This definition naturally generalizes to the k-dimensional ridge as follows: the point
-
λ n − k < 0 , and -
∇ x 0 f ⋅ e i = 0 fori = 1 , 2 , … , n − k .
In many ways, these definitions naturally generalize that of a local maximum of a function. Properties of maximal convexity ridges are put on a solid mathematical footing by Damon and Miller. Their properties in one-parameter families was established by Keller.
Maximal Scale Ridge
The following definition can be traced to Fritsch who was interested in extracting geometric information about figures in two dimensional greyscale images. Fritsch filtered his image with a "medialness" filter that gave him information analogous to "distant to the boundary" data in scale-space. Ridges of this image, once projected to the original image, were to be analogous to a shape skeleton (e.g., the Blum Medial Axis) of the original image.
What follows is a definition for the maximal scale ridge of a function of three variables, one of which is a "scale" parameter. One thing that we want to be true in this definition is, if
-
∂ f ∂ σ = 0 and∂ 2 f ∂ σ 2 < 0 , and -
∇ f ⋅ e 1 = 0 ande 1 t H ( f ) e 1 < 0 .
Relations between edge detection and ridge detection
The purpose of ridge detection is usually to capture the major axis of symmetry of an elongated object, whereas the purpose of edge detection is usually to capture the boundary of the object. However, some literature on edge detection erroneously includes the notion of ridges into the concept of edges, which confuses the situation.
In terms of definitions, there is a close connection between edge detectors and ridge detectors. With the formulation of non-maximum as given by Canny, it holds that edges are defined as the points where the gradient magnitude assumes a local maximum in the gradient direction. Following a differential geometric way of expressing this definition, we can in the above-mentioned
while the second-order directional derivative in the
Written out as an explicit expression in terms of local partial derivatives
that satisfy a sign-condition on the following differential invariant
(see the article on edge detection for more information). Notably, the edges obtained in this way are the ridges of the gradient magnitude.