Ridge detection


Ridge detection

The ridges (or the ridge set) of a smooth function of two variables is a set of curves whose points are, loosely speaking, local maxima in at least one dimension. For a function of N variables, its ridges are a set of curves whose points are local maxima in N-1 dimensions. (A more precise definition is given below). In this respect, the notion of ridge points can be seen as an extension of 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, and 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 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 f(x, y) denote a two-dimensional function, and let L be the scale-space representation of f(x, y) obtained by convolving f(x, y) with a Gaussian function :g(x, y, t) = frac{1}{2 pi t} e^{-(x^2+y^2)/2t}. Furthermore, let L_{pp} and L_{qq} denote the eigenvalues of the Hessian matrix:H = egin{bmatrix}L_{xx} & L_{xy} \ L_{xy} & L_{yy}end{bmatrix}of the scale-space representation L. With a coordinate transformation (a rotation) applied to local directional derivative operators,:partial_p = sin eta partial_x - cos eta partial_y, partial_q = cos eta partial_x + sin eta partial_y it can be shown that the mixed derivative L_{pq} in the transformed coordinate system is zero if we choose :cos eta = sqrt{frac{1}{2} left( 1 + frac{L_{xx}-L_{yy{sqrt{(L_{xx}-L_{yy})^2 + 4 L_{xy}^2 ight)}, sin eta = sgn(Lxy) sqrt{frac{1}{2} left( 1 - frac{L_{xx}-L_{yy{sqrt{(L_{xx}-L_{yy})^2 + 4 L_{xy}^2 ight)} .Then, a formal differential geometric definition of the ridges of f(x, y) at a fixed scale t can be expressed as the set of points that satisfy:L_{p} = 0, L_{pp} leq 0, |L_{pp}| geq |L_{qq}|.Correspondingly, the valleys of f(x, y) at scale t are the set of points:L_{q} = 0, L_{qq} geq 0, |L_{qq}| geq |L_{pp}|.In terms of a (u, v) coordinate system with the v direction parallel to the image gradient:partial_u = sin alpha partial_x - cos alpha partial_y, partial_v = cos alpha partial_x + sin alpha partial_y where:cos alpha = frac{L_x}{sqrt{L_x^2 + L_y^2, sin alpha = frac{L_y}{sqrt{L_x^2 + L_y^2 it can be shown that this ridge and valley definition can instead be equivalently [ [http://www.nada.kth.se/~tony/abstracts/Lin94-SI-abstract.html T. Lindeberg: Scale-space theory: A basic tool for analysing structures at different scales, in J. of Applied Statistics, 21(2), pp. 224–270, 1994] ] be written as: L_{uv} = 0, L_{uu}^2 - L_{vv}^2 geq 0 where :L_v^2 L_{uu} = L_x^2 L_{yy} - 2 L_x L_y L_{xy} + L_y^2 L_{xx},:L_v^2 L_{uv} = L_x L_y (L_{xx} - L_{yy}) - (L_x^2 - L_y^2) L_{xy}, :L_v^2 L_{vv} = L_x^2 L_{xx} + 2 L_x L_y L_{xy} + L_y^2 L_{yy} and the sign of L_{uu} determines the polarity; L_{uu}<0 for ridges and L_{uu}>0 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 R(x, y, t) 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:L_{p} = 0, L_{pp} leq 0, partial_t(R) = 0, partial_{tt}(R) leq 0,where t is the scale parameter in the scale-space representation. Similarly, a "scale-space valley" is the set of points that satisfy:L_{q} = 0, L_{qq} geq 0, partial_t(R) = 0, partial_{tt}(R) leq 0.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) [ [http://www.nada.kth.se/cvap/abstracts/cvap191.html T. Lindeberg: "Edge detection and ridge detection with automatic scale selection", International Journal of Computer Vision, vol 30, number 2, pp. 117--154, 1998. Earlier version presented at IEEE Conference on Pattern Recognition and Computer Vision, CVPR'96, San Francisco, California, pages 465--470, june 1996] ] coined the term scale-space ridge, he considered three measures of ridge strength:

  • The main principal curvature :L_{pp, gamma-norm} = frac{t^{gamma{2} left( L_{xx}+L_{yy} - sqrt{(L_{xx}-L_{yy})^2 + 4 L_{xy}^2} ight)expressed in terms of "gamma-normalized derivatives" with:partial_{xi} = t^{gamma/2} partial_x, partial_{eta} = t^{gamma/2} partial_y.
  • The square of the gamma-normalized square eigenvalue difference:N_{gamma-norm} = left( L_{pp, gamma-norm}^2 - L_{qq, gamma-norm}^2 ight)^2 = t^{4 gamma} (L_{xx}+L_{yy})^2 left( (L_{xx}-L_{yy})^2 + 4 L_{xy}^2 ight).
  • The square of the gamma-normalized eigenvalue difference:A_{gamma-norm} = left( L_{pp, gamma-norm} - L_{qq, gamma-norm} ight)^2 = t^{2 gamma} left( (L_{xx}-L_{yy})^2 + 4 L_{xy}^2 ight).
The notion of gamma-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 gamma = 3/4. Out of these three measures of ridge strength, the first entity L_{pp, gamma-norm} is a general purpose ridge strength measure with many applications such as blood vessel detection and road extraction. Nevertheless, the entity A_{gamma-norm} has been used in applications such as fingerprint enhancement [ [http://www.nada.kth.se/cvap/abstracts/cvap226.html A. Almansa and T. Lindeberg: Fingerprint Enhancement by Shape Adaptation of Scale-Space Operators with Automatic Scale-Selection, IEEE Transactions on Image Processing, volume 9, number 12, pp 2027-2042, 2000.] ] , real-time hand tracking and gesture recognition [ [http://www.nada.kth.se/cvap/abstracts/BreLapLin-FG02.html L. Bretzner, I. Laptev and T. Lindeberg: Hand Gesture Recognition using Multi-Scale Colour Features, Hierarchical Models and Particle Filtering, Proc. IEEE Conference on Face and Gesture 2002, Washington DC, 423--428.] ] as well as for modelling local image statistics for detecting and tracking humans in images and video. [ [http://www.csc.kth.se/~hedvig/publications/ijcv_03.pdf H. Sidenbladh and M. Black: Learning the statistics of people in images and video. International Journal of Computer Vision, volume 54, numbers 1-2, pages 183-209, 2003.] ]

There are also other closely related ridge definitions that make use of normalized derivatives with the implicit assumption of gamma = 1. [J. Furst and J. Miller, "The Maximal Scale Ridge: Incorporating Scale in the Ridge Definition", "Scale Space Theory in Computer Vision: Proceedings of the First International Conference on, Scale Space '97," pp. 93-104. Springer Lecture Notes in Computer Science, vol. 1682.] "Develop these approaches in further detail." When detecting ridges with gamma = 1, however, it should be noted that the detection scale will be twice as large as for gamma = 3/4, 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 [R. Haralick, "Ridges and Valleys on Digital Images," Computer Vision, Graphics, and Image Processing vol. 22, no. 10, pp. 28-38, Apr. 1983] and by Crowley concerning difference of Gaussians pyramids in 1984 [ [http://www-prima.inrialpes.fr/Prima/Homepages/jlc/papers/Crowley-Parker84.pdf J. L. Crowley and A. C. Parker, "A Representation for Shape Based on Peaks and Ridges in the Difference of Low Pass Transform", IEEE Transactions on PAMI, PAMI 6 (2), pp 156-170, March 1984.] ] [ [http://www-prima.inrialpes.fr/Prima/Homepages/jlc/papers/Crowley-Sanderson-PAMI87.pdf J. L. Crowley and A. Sanderson,"Multiple Resolution Representation and Probabilistic Matching of 2-D Gray-Scale Shape", IEEE Transactions on PAMI, PAMI 9(1), pp 113-121, January 1987.] ] . The application of ridge descriptors to medical image analysis has been extensively studied by Pizer and his co-workers [ J. M. Gauch , S. M. Pizer, Multiresolution Analysis of Ridges and Valleys in Grey-Scale Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.6, p.635-646, June 1993] [D. Eberly , R. Gardner , B. Morse , S. Pizer , C. Scharlach, Ridges for image analysis, Journal of Mathematical Imaging and Vision, v.4 n.4, p.353-373, Dec. 1994.] [Stephen M. Pizer , David Eberly , Daniel S. Fritsch, Zoom-invariant vision of figural shape: the mathematics of cores, Computer Vision and Image Understanding, v.69 n.1, p.55-71, Jan. 1998] resulting in their notion of M-reps [ [http://citeseer.ist.psu.edu/pizer01segmentation.html S. Pizer, S. Joshi, T. Fletcher, M. Styner, G. Tracton, J. Chen (2001) "Segmentation of Single-Figure Objects by Deformable M-reps", Proceedings of the 4th International Conference on Medical Image Computing and Computer-Assisted Intervention, Springer Lecture Notes In Computer Science; Vol. 2208, pp. 862 - 871] ] . Ridge detection has also been furthered by Lindeberg with the introduction of gamma-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 [ [http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/trans/tp/&toc=comp/trans/tp/1998/02/i2toc.xml&DOI=10.1109/34.659930 C. Steger: An unbiased detector of curvilinear structures, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 20, No. 2, pp. 113-125, 1998.] ] [ [http://www.irisa.fr/vista/Papers/2000_mva_laptev.pdf I. Laptev, H. Mayer, T. Lindeberg, W. Eckstein, C. Steger, and A. Baumgartner: Automatic extraction of roads from aerial images based on scale-space and snakes, Machine Vision and Applications 12(1):23, 2000.] ] and to blood vessel segmentation by Frangi et al [ [http://www.ncbi.nlm.nih.gov/entrez/query.fcgi?cmd=Retrieve&db=PubMed&list_uids=10628954&dopt=Citation A. Frangi, W. Niessen, R. Hoogeveen, T. van Walsum and M. Viergever (1999) "Model-based quantitation of 3-D magnetic resonance angiographic images", IEEE Trans Med Imaging. 1999 Oct;18(10):946-56.] ] as well as to the detection of curvilinear and tubular structures by Sato et al [ [http://www.image.med.osaka-u.ac.jp/member/yoshi/paper/linefilter.pdf Y Sato, S Nakajima, N Shiraga, H Atsumi, S Yoshida ...: Three-dimensional multi-scale line filter for segmentation and visualization of curvilinear structures in medical images, Medical Image Analysis, volume 2, number 2, pp 143–168, 1998 ] ] and Krissian et al [ [http://portal.acm.org/citation.cfm?id=363419.363423 K. Krissian, G. Malandain, N. Ayache, R. Vaillan and Y. Trousset (2000) "Model-based detection of tubular structures in 3D images" Computer Vision and Image Understanding, Volume 80 , Issue 2, 130 - 171.] .] . 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 [Jan J. Koenderink and Andrea J. van Doorn. 2+1-D differential geometry. Pattern. Recognition Letters, 15:439–443, May 1994.] . A review of vessel extraction techniques has been presented by Kirbas and Quek [ [ftp://cmp.felk.cvut.cz/pub/cmp/articles/matas/ps/Curvilinear/blood-vessel_review.pdf C Kirbas, F Quek: A review of vessel extraction techniques and algorithms, ACM Computing Surveys, Volume 36 , Issue 2, pages 81 - 121, 2004.] ] .

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 mathbf{x}_0 in the domain of a function f:mathbb{R}^n ightarrow mathbb{R}is a local maximum of the function if there is a distance delta>0 with the property that if mathbf{x} is within delta units of mathbf{x}_0, then f(mathbf{x}) < f(mathbf{x}_0). 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 f(mathbf{x}) < f(mathbf{x}_0) for mathbf{x} in an entire neighborhood of mathbf{x}_0 slightly to require only that this hold on an n-1 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 [ [http://www.amazon.com/dp/0792342682/ Eberly, D. "Ridges in Image and Data Analysis." Kluwer, 1996.] ] and can be seen as a generalization of some of the abovementioned ridge definitions. Let U subset mathbb{R}^n be open an open set, and f:U ightarrow mathbb{R} be smooth. Let mathbf{x}_0 in U. Let abla_{mathbf{x}_0}f be the gradient of f at mathbf{x}_0, and let H_{mathbf{x}_0}(f) be the n imes n Hessian matrix of fat mathbf{x}_0. Let lambda_1 leq lambda_2 leq cdots leq lambda_n be the n ordered eigenvalues of H_{mathbf{x}_0}(f) and let mathbf{e}_i be a unit eigenvector in the eigenspace for lambda_i. (For this, one should assume that all the eigenvalues are distinct.)

The point mathbf{x}_0 is a point on the 1-dimensional ridge of f if the following conditions hold:

  1. lambda_{n-1}<0, and
  2. abla_{mathbf{x}_0} f cdot mathbf{e}_i=0 for i=1, 2, ldots, n-1.
This makes precise the concept that f restricted to "this particular" n-1-dimensional subspace has a local maxima at mathbf{x}_0.

This definition naturally generalizes to the "k"-dimensional ridge as follows: the point mathbf{x}_0 is a point on the "k"-dimensional ridge of f if the following conditions hold:

  1. lambda_{n-k}<0, and
  2. abla_{mathbf{x}_0} f cdot mathbf{e}_i=0 for i=1, 2, ldots, 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 [Damon, J. "Properties of Ridges and Cores in Two-Dimensional Images." Journal of Mathematical Imaging and Vision. pp.163-174. 1999.] and Miller [Miller, J. "Relative Critical Sets in mathbb{R}^n and Applications to Image Analysis." Ph.D. Dissertation. University of North Carolina. 1998.] . Their properties in one-parameter families was established by Keller [Kerrel, R. "Generic Transitions of Relative Critical Sets in Parameterized Families with Applications to Image Analysis." University of North Carolina. 1999.] .

Maximal Scale Ridge

The following definition can be traced to Fritsch [ Fritsch, DS, Eberly,D., Pizer, SM, and McAuliffe, MJ. "Stimulated cores and their applications in medical imaging." Information Processing in Medical Imaging, Y. Bizais, C Barillot, R DiPaola, eds., Kluwer Series in Computational Imaging and Vision, pp. 365-368.] 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 (mathbf{x},sigma) is a point on this ridge, then the value of the function at the point is maximal in the scale dimension. Let f(mathbf{x},sigma) be a smooth differentiable function on U subset mathbb{R}^2 imes mathbb{R}_{+}. The (mathbf{x},sigma) is a point on the maximal scale ridge if and only if

  1. frac{partial f}{partial sigma}=0 and frac{partial^2 f}{partial sigma^2}<0, and
  2. abla f cdot mathbf{e}_1=0 and mathbf{v}_1^t H(f) mathbf{v}_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 objectFact|date=July 2008, whereas the purpose of edge detection is usually to capture the boundary of the object. However, some literature on edge detection erroneouslyFact|date=July 2008 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 [ [http://portal.acm.org/citation.cfm?id=11275 J. Canny: A computational approach to edge detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 8, issue 6, pages 679 - 698, 1986] ] , 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 [ [http://www.nada.kth.se/~tony/abstracts/Lin93-JMIV.html T. Lindeberg: Discrete Derivative Approximations with Scale-Space Properties: A Basis for Low-Level Feature Extraction, J. of Mathematical Imaging and Vision, 3(4), pp. 349--376, 1993.] ] , we can in the above-mentioned (u, v)-coordinate system state that the gradient magnitude of the scale-space representation, which is equal to the first-order directional derivative in the v-direction L_v, should have its first order directional derivative in the v-direction equal to zero :partial_v(L_v) = 0 while the second-order directional derivative in the v-direction of L_v should be negative, i.e., :partial_{vv}(L_v) leq 0. Written out as an explicit expression in terms of local partial derivatives L_x, L_y ... L_{yyy}, this edge definition can be expressed as the zero-crossing curves of the differential invariant:L_v^2 L_{vv} = L_x^2 , L_{xx} + 2 , L_x , L_y , L_{xy} + L_y^2 , L_{yy} = 0,that satisfy a sign-condition on the following differential invariant:L_v^3 L_{vvv} = L_x^3 , L_{xxx} + 3 , L_x^2 , L_y , L_{xxy} + 3 , L_x , L_y^2 , L_{xyy} + L_y^3 , L_{yyy} leq 0(see the article on edge detection for more information). Notably, the edges obtained in this way are the ridges of the gradient magnitude.

See also

*Scale-space
*Edge detection
*Interest point detection
*Blob detection
*Computer vision

References

External links

* [http://operaomnia.interfree.it/thesis/thesis_italy_XX_ciclo_andrea_anzalone.html Multiscale analysis for optimized vessel segmentation of fundus retina images] Ph.D Thesis


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Détection de zones d'intérêt — En vision par ordinateur et en traitement d images, la détection de zones d intérêt d une image numérique (feature detection en anglais) consiste à mettre en évidence des zones de cette image jugées « intéressantes » pour l analyse, c… …   Wikipédia en Français

  • Ridge (differential geometry) — For a smooth surface in three dimensions a ridge point occurs when a line of curvature has a local maximum or minimum of principal curvature. The set of ridge points form curves on the surface called ridges.Ridges fall into two types typically… …   Wikipedia

  • Feature detection (computer vision) — In computer vision and image processing the concept of feature detection refers to methods that aim at computing abstractions of image information and making local decisions at every image point whether there is an image feature of a given type… …   Wikipedia

  • Edge detection — is a terminology in image processing and computer vision, particularly in the areas of feature detection and feature extraction, to refer to algorithms which aim at identifying points in a digital image at which the image brightness changes… …   Wikipedia

  • Corner detection — Feature detection Output of a typical corner detection algorithm …   Wikipedia

  • Blob detection — Feature detection Output of a typical corner detection algorithm …   Wikipedia

  • Interest point detection — is a recent terminology in computer vision that refers to the detection of interest points for subsequent processing. An interest point is a point in the image which in general can be characterized as follows:* it has a clear, preferably… …   Wikipedia

  • Neutron detection — is the effective detection of neutrons entering a well positioned detector. There are two key aspects to effective neutron detection: hardware and software. Detection hardware refers to the kind of neutron detector used (the most common today is… …   Wikipedia

  • Hickory Ridge, Virginia — Hickory Ridge is an extinct unincorporated town in Prince William County, Virginia. The town was located on land that is now part of Prince William Forest Park, a National Park Service property located adjacent to Marine Corps Base Quantico. The… …   Wikipedia

  • 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 …   Wikipedia


We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.