Ridge detection
Encyclopedia
The ridges of a smooth function
of two variables is 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. For a function of
variables, its ridges are a set of curves whose points are local maxima in 
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. and Miller.
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 watershed
s 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 image
s. In typical applications, ridge and valley descriptors are often used for detecting roads in aerial image
s and for detecting blood vessel
s in retinal images or three-dimensional magnetic resonance images
.
denote a two-dimensional function, and let 
be the scale-space representation of 
obtained by convolving 
with a Gaussian function
.
Furthermore, let
and 
denote the eigenvalues of the Hessian matrix
of the scale-space representation
. With a coordinate transformation (a rotation) applied to local directional derivative operators,
where p and q are coordinates of the rotated coordinate system.
It can be shown that the mixed derivative
in the transformed coordinate system is zero if we choose
,
.
Then, a formal differential geometric definition of the ridges of
at a fixed scale 
can be expressed as the set of points that satisfy
Correspondingly, the valleys of
at scale 
are the set of points
In terms of a
coordinate system with the 
direction parallel to the image gradient
where
it can be shown that this ridge and valley definition can instead be equivalently be written as
where
and the sign of
determines the polarity; 
for ridges and 
for valleys.
Let
denote a measure of ridge strength (to be specified below). Then, for a two-dimensional image, a scale-space ridge is the set of points that satisfy
where
is the scale parameter in the scale-space representation. Similarly, a scale-space valley is the set of points that satisfy
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
-normalized derivatives is essential here, since it allows the ridge and valley detector algorithms to be calibrated properly. By requiring that for a one-dimensional Gaussian ridge embedded in two (or three dimensions) the detection scale should be equal to the width of the ridge structure when measured in units of length (a requirement of a match between the size of the detection filter and the image structure it responds to), it follows that one should choose 
. Out of these three measures of ridge strength, the first entity 
is a general purpose ridge strength measure with many applications such as blood vessel detection and road extraction. Nevertheless, the entity 
has been used in applications such as fingerprint enhancement, real-time hand tracking and gesture recognition as well as for modelling local image statistics for detecting and tracking humans in images and video.
There are also other closely related ridge definitions that make use of normalized derivatives with the implicit assumption of
. Develop these approaches in further detail. When detecting ridges with 
, however, the detection scale will be twice as large as for 
, resulting in more shape distortions and a lower ability to capture ridges and valleys with nearby interfering image structures in the image domain.
pyramid
s 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
-normalized derivatives and scale-space ridges defined from local maximization of the appropriately normalized main principal curvature of the Hessian matrix (or other measures of ridge strength) over space and over scale. These notions have later been developed with application to road extraction by Steger et al. and to blood vessel segmentation by Frangi et al. as well as to the detection of curvilinear and tubular structures by Sato et al. and Krissian et al. A review of several of the classical ridge definitions at a fixed scale including relations between them has been given by Koenderink and van Doorn. A review of vessel extraction techniques has been presented by Kirbas and Quek.
in the domain of a function 
is a local maximum of the function if there is a distance 
with the property that if 
is within 
units of 
, then 
. It is well known that critical points, of which local maxima are just one type, are isolated points in a function's domain in all but the most unusual situations (i.e., the nongeneric cases).
Consider relaxing the condition that
for 
in an entire neighborhood of 
slightly to require only that this hold on an 
dimensional subset. Presumably this relaxation allows the set of points which satisfy the criteria, which we will call the ridge, to have a single degree of freedom, at least in the generic case. This means that the set of ridge points will form a 1-dimensional locus, or a ridge curve. Notice that the above can be modified to generalize the idea to local minima and result in what might call 1-dimensional valley curves.
This following ridge definition follows the book by Eberly and can be seen as a generalization of some of the abovementioned ridge definitions. Let
be open an open set, and 
be smooth. Let 
. Let 
be the gradient of 
at 
, and let 
be the 
Hessian matrix of 
at 
. Let 
be the 
ordered eigenvalues of 
and let 
be a unit eigenvector in the eigenspace for 
. (For this, one should assume that all the eigenvalues are distinct.)
The point
is a point on the 1-dimensional ridge of 
if the following conditions hold:
This makes precise the concept that
restricted to this particular 
-dimensional subspace has a local maxima at 
.
This definition naturally generalizes to the k-dimensional ridge as follows: the point
is a point on the k-dimensional ridge of 
if the following conditions hold:
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.
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
is a point on this ridge, then the value of the function at the point is maximal in the scale dimension. Let 
be a smooth differentiable function on 
. The 
is a point on the maximal scale ridge if and only if
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
-coordinate system state that the gradient magnitude of the scale-space representation, which is equal to the first-order directional derivative in the 
-direction 
, should have its first order directional derivative in the 
-direction equal to zero
while the second-order directional derivative in the
-direction of 
should be negative, i.e.,
.
Written out as an explicit expression in terms of local partial derivatives
, 
... 
, this edge definition can be expressed as the zero-crossing curves of the differential invariant
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.
Smooth function
In mathematical analysis, a differentiability class is a classification of functions according to the properties of their derivatives. Higher order differentiability classes correspond to the existence of more derivatives. Functions that have derivatives of all orders are called smooth.Most of...
of two variables is 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. For a function of
variables, its ridges are a set of curves whose points are local maxima in 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. and Miller.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
Image analysis
Image analysis is the extraction of meaningful information from images; mainly from digital images by means of digital image processing techniques...
and computer vision
Computer vision
Computer vision is a field that includes methods for acquiring, processing, analysing, and understanding images and, in general, high-dimensional data from the real world in order to produce numerical or symbolic information, e.g., in the forms of decisions...
and is to capture the interior of elongated objects in the image domain. Ridge-related representations in terms of watershed
Watershed (algorithm)
A grey-level image may be seen as a topographic relief, where the grey level of a pixel is interpreted as its altitude in the relief.A drop of water falling on a topographic relief flows along a path to finally reach a local minimum...
s 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
Interest point detection
Interest point detection is a recent terminology in computer vision that refers to the detection of interest points for subsequent processing...
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
Topological skeleton
In shape analysis, skeleton of a shape is a thin version of that shape that is equidistant to its boundaries. The skeleton usually emphasizes geometrical and topological properties of the shape, such as its connectivity, topology, length, direction, and width...
for organizing spatial constraints on local appearance, with a number of qualitative similarities to the way the Blum's medial axis transform
Medial axis
The medial axis of an object is the set of all points having more than one closest point on the object's boundary. Originally referred to as the topological skeleton, it was introduced by Blum as a tool for biological shape recognition....
provides a shape skeleton for binary image
Binary image
A binary image is a digital image that has only two possible values for each pixel. Typically the two colors used for a binary image are black and white though any two colors can be used. The color used for the object in the image is the foreground color while the rest of the image is the...
s. In typical applications, ridge and valley descriptors are often used for detecting roads in aerial image
Aerial image
An aerial image is a projected image which is "floating in air", and cannot be viewed normally. It can only be seen from one position in space, often focused by another lens....
s and for detecting blood vessel
Blood vessel
The blood vessels are the part of the circulatory system that transports blood throughout the body. There are three major types of blood vessels: the arteries, which carry the blood away from the heart; the capillaries, which enable the actual exchange of water and chemicals between the blood and...
s in retinal images or three-dimensional magnetic resonance images
Magnetic resonance imaging
Magnetic resonance imaging , nuclear magnetic resonance imaging , or magnetic resonance tomography is a medical imaging technique used in radiology to visualize detailed internal structures...
.
Differential geometric definition of ridges and valleys at a fixed scale in a two-dimensional image
Let denote a two-dimensional function, and let be the scale-space representation of obtained by convolving with a Gaussian function.Furthermore, let
and denote the eigenvalues of the Hessian matrixHessian matrix
In mathematics, the Hessian matrix is the square matrix of second-order partial derivatives of a function; that is, it describes the local curvature of a function of many variables. The Hessian matrix was developed in the 19th century by the German mathematician Ludwig Otto Hesse and later named...
of the scale-space representation
. With a coordinate transformation (a rotation) applied to local directional derivative operators,where p and q are coordinates of the rotated coordinate system.
It can be shown that the mixed derivative
in the transformed coordinate system is zero if we choose,.Then, a formal differential geometric definition of the ridges of
at a fixed scale can be expressed as the set of points that satisfyCorrespondingly, the valleys of
at scale are the set of pointsIn terms of a
coordinate system with the direction parallel to the image gradientwhere
it can be shown that this ridge and valley definition can instead be equivalently be written as
where
and the sign of
determines the polarity; for ridges and for valleys.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
denote a measure of ridge strength (to be specified below). Then, for a two-dimensional image, a scale-space ridge is the set of points that satisfywhere
is the scale parameter in the scale-space representation. Similarly, a scale-space valley is the set of points that satisfyAn 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 main principal curvature
expressed in terms of
-normalized derivatives with
.
The square of the
-normalized square eigenvalue difference
The square of the
-normalized eigenvalue difference
The notion of
-normalized derivatives is essential here, since it allows the ridge and valley detector algorithms to be calibrated properly. By requiring that for a one-dimensional Gaussian ridge embedded in two (or three dimensions) the detection scale should be equal to the width of the ridge structure when measured in units of length (a requirement of a match between the size of the detection filter and the image structure it responds to), it follows that one should choose . Out of these three measures of ridge strength, the first entity is a general purpose ridge strength measure with many applications such as blood vessel detection and road extraction. Nevertheless, the entity has been used in applications such as fingerprint enhancement, real-time hand tracking and gesture recognition as well as for modelling local image statistics for detecting and tracking humans in images and video.There are also other closely related ridge definitions that make use of normalized derivatives with the implicit assumption of
. Develop these approaches in further detail. When detecting ridges with , however, the detection scale will be twice as large as for , resulting in more shape distortions and a lower ability to capture ridges and valleys with nearby interfering image structures in the image domain.History
The notion of ridges and valleys in digital images was introduced by Haralick in 1983 and by Crowley concerning difference of GaussiansDifference of Gaussians
In computer vision, Difference of Gaussians is a grayscale image enhancement algorithm that involves the subtraction of one blurred version of an original grayscale image from another, less blurred version of the original. The blurred images are obtained by convolving the original grayscale image...
pyramid
Pyramid (image processing)
Pyramid or pyramid representation is a type of multi-scale signal representation developed by the computer vision, image processing and signal processing communities, in which a signal or an image is subject to repeated smoothing and subsampling...
s 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
-normalized derivatives and scale-space ridges defined from local maximization of the appropriately normalized main principal curvature of the Hessian matrix (or other measures of ridge strength) over space and over scale. These notions have later been developed with application to road extraction by Steger et al. and to blood vessel segmentation by Frangi et al. as well as to the detection of curvilinear and tubular structures by Sato et al. and Krissian et al. A review of several of the classical ridge definitions at a fixed scale including relations between them has been given by Koenderink and van Doorn. A review of vessel extraction techniques has been presented by Kirbas and Quek.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 in the domain of a function is a local maximum of the function if there is a distance with the property that if is within units of , then . It is well known that critical points, of which local maxima are just one type, are isolated points in a function's domain in all but the most unusual situations (i.e., the nongeneric cases).Consider relaxing the condition that
for in an entire neighborhood of slightly to require only that this hold on an dimensional subset. Presumably this relaxation allows the set of points which satisfy the criteria, which we will call the ridge, to have a single degree of freedom, at least in the generic case. This means that the set of ridge points will form a 1-dimensional locus, or a ridge curve. Notice that the above can be modified to generalize the idea to local minima and result in what might call 1-dimensional valley curves.This following ridge definition follows the book by Eberly and can be seen as a generalization of some of the abovementioned ridge definitions. Let
be open an open set, and be smooth. Let . Let be the gradient of at , and let be the Hessian matrix of at . Let be the ordered eigenvalues of and let be a unit eigenvector in the eigenspace for . (For this, one should assume that all the eigenvalues are distinct.)The point
is a point on the 1-dimensional ridge of if the following conditions hold:
, and
for 
.
This makes precise the concept that
restricted to this particular -dimensional subspace has a local maxima at .This definition naturally generalizes to the k-dimensional ridge as follows: the point
is a point on the k-dimensional ridge of if the following conditions hold:
, and
for 
.
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
is a point on this ridge, then the value of the function at the point is maximal in the scale dimension. Let be a smooth differentiable function on . The is a point on the maximal scale ridge if and only if-
and 
, and
and 
.
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 detectionEdge detection
Edge detection is a fundamental tool in image processing and computer vision, particularly in the areas of feature detection and feature extraction, which aim at identifying points in a digital image at which the image brightness changes sharply or, more formally, has discontinuities...
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
-coordinate system state that the gradient magnitude of the scale-space representation, which is equal to the first-order directional derivative in the -direction , should have its first order directional derivative in the -direction equal to zerowhile the second-order directional derivative in the
-direction of should be negative, i.e.,.Written out as an explicit expression in terms of local partial derivatives
, ... , this edge definition can be expressed as the zero-crossing curves of the differential invariantthat satisfy a sign-condition on the following differential invariant
(see the article on edge detection
Edge detection
Edge detection is a fundamental tool in image processing and computer vision, particularly in the areas of feature detection and feature extraction, which aim at identifying points in a digital image at which the image brightness changes sharply or, more formally, has discontinuities...
for more information). Notably, the edges obtained in this way are the ridges of the gradient magnitude.
See also
- Scale-space
- Edge detectionEdge detectionEdge detection is a fundamental tool in image processing and computer vision, particularly in the areas of feature detection and feature extraction, which aim at identifying points in a digital image at which the image brightness changes sharply or, more formally, has discontinuities...
- Interest point detectionInterest point detectionInterest point detection is a recent terminology in computer vision that refers to the detection of interest points for subsequent processing...
- Blob detectionBlob detectionIn the area of computer vision, blob detection refers to visual modules that are aimed at detecting points and/or regions in the image that differ in properties like brightness or color compared to the surrounding...
- Computer visionComputer visionComputer vision is a field that includes methods for acquiring, processing, analysing, and understanding images and, in general, high-dimensional data from the real world in order to produce numerical or symbolic information, e.g., in the forms of decisions...