Feature detection |
---|
Edge detection |
Corner detection |
Blob detection |
Ridge detection |
Hough transform |
Structure tensor |
Affine invariant feature detection |
Feature description |
Scale space |
![]() | This article may be too technical for most readers to understand.(September 2012) |
In image processing, ridge detection is the attempt, via software, to locate ridges in an image, defined as curves whose points are local maxima of the function, akin to 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. [1] [2]
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.
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 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 [3]
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 [4] be written as
where
and the sign of determines the polarity; for ridges and for valleys.
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 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) [5] 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, [6] real-time hand tracking and gesture recognition [7] as well as for modelling local image statistics for detecting and tracking humans in images and video. [8]
There are also other closely related ridge definitions that make use of normalized derivatives with the implicit assumption of . [9] 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.
The notion of ridges and valleys in digital images was introduced by Haralick in 1983 [10] and by Crowley concerning difference of Gaussians pyramids in 1984. [11] [12] The application of ridge descriptors to medical image analysis has been extensively studied by Pizer and his co-workers [13] [14] [15] resulting in their notion of M-reps. [16] 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. [17] [18] and to blood vessel segmentation by Frangi et al. [19] as well as to the detection of curvilinear and tubular structures by Sato et al. [20] and Krissian et al. [21] 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. [22] A review of vessel extraction techniques has been presented by Kirbas and Quek. [23]
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 [24] and can be seen as a generalization of some of the abovementioned ridge definitions. Let be 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 maximum 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 [1] and Miller. [2] Their properties in one-parameter families was established by Keller. [25]
The following definition can be traced to Fritsch [26] 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
The purpose of ridge detection is usually to capture the major axis of symmetry of an elongated object,[ citation needed ] whereas the purpose of edge detection is usually to capture the boundary of the object. However, some literature on edge detection erroneously[ citation needed ] 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, [27] 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, [28] 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.
In mathematics, curvature is any of several strongly related concepts in geometry. Intuitively, the curvature is the amount by which a curve deviates from being a straight line, or a surface deviates from being a plane.
In continuum mechanics, the infinitesimal strain theory is a mathematical approach to the description of the deformation of a solid body in which the displacements of the material particles are assumed to be much smaller than any relevant dimension of the body; so that its geometry and the constitutive properties of the material at each point of space can be assumed to be unchanged by the deformation.
In vector calculus, Green's theorem relates a line integral around a simple closed curve C to a double integral over the plane region D bounded by C. It is the two-dimensional special case of Stokes' theorem.
Edge detection includes a variety of mathematical methods that aim at identifying edges, 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.
In mathematics, the covariant derivative is a way of specifying a derivative along tangent vectors of a manifold. Alternatively, the covariant derivative is a way of introducing and working with a connection on a manifold by means of a differential operator, to be contrasted with the approach given by a principal connection on the frame bundle – see affine connection. In the special case of a manifold isometrically embedded into a higher-dimensional Euclidean space, the covariant derivative can be viewed as the orthogonal projection of the Euclidean directional derivative onto the manifold's tangent space. In this case the Euclidean derivative is broken into two parts, the extrinsic normal component and the intrinsic covariant derivative component.
In differential geometry, an affine connection is a geometric object on a smooth manifold which connects nearby tangent spaces, so it permits tangent vector fields to be differentiated as if they were functions on the manifold with values in a fixed vector space. Connections are among the simplest methods of defining differentiation of the sections of vector bundles.
In geometry, curvilinear coordinates are a coordinate system for Euclidean space in which the coordinate lines may be curved. These coordinates may be derived from a set of Cartesian coordinates by using a transformation that is locally invertible at each point. This means that one can convert a point given in a Cartesian coordinate system to its curvilinear coordinates and back. The name curvilinear coordinates, coined by the French mathematician Lamé, derives from the fact that the coordinate surfaces of the curvilinear systems are curved.
In linear algebra, a rotation matrix is a transformation matrix that is used to perform a rotation in Euclidean space. For example, using the convention below, the matrix
In physics, the Hamilton–Jacobi equation, named after William Rowan Hamilton and Carl Gustav Jacob Jacobi, is an alternative formulation of classical mechanics, equivalent to other formulations such as Newton's laws of motion, Lagrangian mechanics and Hamiltonian mechanics. The Hamilton–Jacobi equation is particularly useful in identifying conserved quantities for mechanical systems, which may be possible even when the mechanical problem itself cannot be solved completely.
In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a finite-dimensional graph, the discrete Laplace operator is more commonly called the Laplacian matrix.
Scale-space theory is a framework for multi-scale signal representation developed by the computer vision, image processing and signal processing communities with complementary motivations from physics and biological vision. It is a formal theory for handling image structures at different scales, by representing an image as a one-parameter family of smoothed images, the scale-space representation, parametrized by the size of the smoothing kernel used for suppressing fine-scale structures. The parameter in this family is referred to as the scale parameter, with the interpretation that image structures of spatial size smaller than about have largely been smoothed away in the scale-space level at scale .
Corner detection is an approach used within computer vision systems to extract certain kinds of features and infer the contents of an image. Corner detection is frequently used in motion detection, image registration, video tracking, image mosaicing, panorama stitching, 3D reconstruction and object recognition. Corner detection overlaps with the topic of interest point detection.
The gradient theorem, also known as the fundamental theorem of calculus for line integrals, says that a line integral through a gradient field can be evaluated by evaluating the original scalar field at the endpoints of the curve. The theorem is a generalization of the second fundamental theorem of calculus to any curve in a plane or space rather than just the real line.
In computer vision, blob detection methods are aimed at detecting regions in a digital image that differ in properties, such as brightness or color, compared to surrounding regions. Informally, a blob is a region of an image in which some properties are constant or approximately constant; all the points in a blob can be considered in some sense to be similar to each other. The most common method for blob detection is convolution.
In probability theory and statistics, partial correlation measures the degree of association between two random variables, with the effect of a set of controlling random variables removed. When determining the numerical relationship between two variables of interest, using their correlation coefficient will give misleading results if there is another confounding variable that is numerically related to both variables of interest. This misleading information can be avoided by controlling for the confounding variable, which is done by computing the partial correlation coefficient. This is precisely the motivation for including other right-side variables in a multiple regression; but while multiple regression gives unbiased results for the effect size, it does not give a numerical value of a measure of the strength of the relationship between the two variables of interest.
The Hessian affine region detector is a feature detector used in the fields of computer vision and image analysis. Like other feature detectors, the Hessian affine detector is typically used as a preprocessing step to algorithms that rely on identifiable, characteristic interest points.
In general relativity, a point mass deflects a light ray with impact parameter by an angle approximately equal to
In physics and continuum mechanics, deformation is the transformation of a body from a reference configuration to a current configuration. A configuration is a set containing the positions of all particles of the body.
In probability theory, the family of complex normal distributions, denoted or , characterizes complex random variables whose real and imaginary parts are jointly normal. The complex normal family has three parameters: location parameter μ, covariance matrix , and the relation matrix . The standard complex normal is the univariate distribution with , , and .
Stokes' theorem, also known as the Kelvin–Stokes theorem after Lord Kelvin and George Stokes, the fundamental theorem for curls or simply the curl theorem, is a theorem in vector calculus on . Given a vector field, the theorem relates the integral of the curl of the vector field over some surface, to the line integral of the vector field around the boundary of the surface. The classical Stokes's theorem can be stated in one sentence: The line integral of a vector field over a loop is equal to the flux of its curl through the enclosed surface.
{{cite journal}}
: CS1 maint: multiple names: authors list (link){{cite journal}}
: CS1 maint: multiple names: authors list (link){{cite journal}}
: CS1 maint: multiple names: authors list (link){{cite journal}}
: CS1 maint: multiple names: authors list (link){{cite journal}}
: CS1 maint: multiple names: authors list (link){{cite journal}}
: CS1 maint: multiple names: authors list (link){{cite journal}}
: CS1 maint: multiple names: authors list (link)