Talk:Ridge detection

Edges and Ridges

Would it be possible to include a discussion on the difference/similarities between ridges and edges. Maybe an example which demonstrates the conceptual differences? --KYN 21:01, 24 September 2006 (UTC)[reply]

Well, in terms of object representation, the intention with a ridge descriptor can be to capture the axis of symmetry of the object, while the purpose of an edge is to capture the boundary of the object. This notion is particularly useful for tasks such as road extraction in aerial images and blood vessel segmentation in medical images. Tpl 18:24, 25 September 2006 (UTC)[reply]

Some authors discuss "line features" in terms of local structures which are constant in one direction and have local maximum or minimum in the orthogonal direction. How close does this come to ridges? I get the feeling that ridges relate to more global structures like objects? --KYN 19:53, 25 September 2006 (UTC)[reply]

Yes, there is a close connection between line features and ridge features. Unfortunately, a few authors also refer to line features as edge features, which complicates the matter. I have had plans to include more precise definitions of ridge features in this article. However, I'm also a bit hesitant, since it is algorithmically much harder to extract robust ridge features from images than edge, corner or blob features. There are also more alternatives to ridge extraction, and personally I'm convinced that current algorithms can be improved substantially. Tpl 05:35, 26 September 2006 (UTC)[reply]

For example the structure tensor can be used to detect lines, possibly in combination with a local phase descriptor to distinguish lines from edges. Would this qualify as a ridge detector? --KYN 22:14, 26 September 2006 (UTC)[reply]

With this terminology, the notion of ridges should include explicit extraction of one-dimensional curves that represent the ridges. Actually, there have been a number of alternative approaches to how to precisely define the notion of a ridge. With this terminology, however, I would not see just a measure of ridge strength as a ridge detector. Moreover, a ridge detector is more than an extractor thin lines. Ridges may occur at different scales and should be allow to extend to ridge widths comparable to the image size. Tpl 09:46, 27 September 2006 (UTC)[reply]

It might be worth pointing out that an image can be filters (or transformed) in such a way that edges in the original image can be identified as rigdes in the transformed image. For instance, the Canny edges are points of maximal change in the gradient magnitude along the negative gradient flow. Using the directional derivative of the gradient magnitude as a transformation, the loci of ridge points should exactly the loci of edge points in the original image.

Now, there is an explicit section on the relations between edges and ridges, including the conceptual similarities in the definitions. Tpl 19:20, 19 January 2007 (UTC)[reply]

On a note related to my contribution and to comments posted above, it seems to me that this entry is in dire need of some mathematical definitions to clarify the meaning of ridge. As TPL correctly points out, there are many definitions in use, some of which are equivalent but not obviously so. Millerj870 17:44, 17 January 2007 (UTC)[reply]

On ridge definitions and their applications in computer vision

I'm concerned about the language of the introduction. When I read it, I understand how someone could easily miss that the ridge of a function is different from the ridge of a "scale-space" function. I have revised the language to reflect the differences. I have also added references to relative critical sets (RCS) because I think the set of RCS give important geometric information about the function, and this is something that people could find useful. (Example: RCS intersect exactly at critical points of the function; they end/transition at point where operative principle curvatures of the function are equal.) I think the two different approaches to ridges in the first paragraph are owed to my approaching the question from a purely mathematical direction and TPL's approach as a computer scientists. No? It's great to have both perspectives represented in the article.

I would like to see references to the scientific literature for the statement, " 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." Can somebody supply some? Millerj870 14:07, 24 February 2007 (UTC)[reply]

Below is a set of references to the use of ridge detection for detecting roads in aerial images and for detecting blood vessels in retinal images or three-dimensional magnetic resonance images. The emphasis of these references (selected from the references of the original article) is on blood vessel detection in 3-D MR images. By following up further references to and from these articles, you should be able to find more articles on these topics:

C. Steger: An unbiased detector of curvilinear structures, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 20, No. 2, pp. 113-125, 1998.

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.

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.

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

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..

C Kirbas, F Quek: A review of vessel extraction techniques and algorithms, ACM Computing Surveys, Volume 36 , Issue 2, pages 81 - 121, 2004.

Tpl 18:27, 25 February 2007 (UTC)[reply]

Sorry to say this, but I'm quite concerned about the recently added statement "Figures or objects in a greyscale image are notoriously difficult for computers to identify, and it has been hoped that using ridge theory in the context of scale-space theory one can create a compact representation of objects (or shapes) in the image." First of all, there has been substantioal progress within the area of object recognition during the last decade. Today, there are actually several good algorithms that allow a computer to recognize a set of known objects in a scene. Hence, this problem is no longer notoriously difficult. Secondly, I do not see "ridge theory" as an established notion in the field and to say "hope" in connection with ridges today, I find as a somewhat outdated statement. Today, there are actually several working algorithms in computer that make use of ridges for various tasks that involve objects in images, please see the references in the article for examples of such works.

I am also concerned about talking about graph representations already in the introduction of this article. While there is a clear conceptual link between ridges, valleys, critical points and graphs, few if any purely graph-based approaches have developed into actually working and useful algorithms. In Wikipedia, I think that it is better to have the emphasis on concepts that work and have been demonstrated to give useful results in practice. Tpl 18:42, 25 February 2007 (UTC)[reply]

Thanks for the references. I think it's important in an encyclopedia entry to have references to the primary literature when it makes a claim about impact or usefulness.

On my "notorious" comment, I think you must agree that teaching computers to "see" figures in greyscale 2D, 3D, or 4D images is a very difficult problem to solve. At least it's been historically difficult. This is the genesis of my comment. Just because this problem has been solved is some special cases at the fronteirs of computer science doesn't mean that the wikipedia entry shouldn't communicate to a general audience that the problem is challenging. This makes the progress that has been acheived all the more remarkable! From the perspective of the non-computer scientists, the popular media (television and movies) makes it seems like computers can easily drive a car or identify a person standing in a crowd of other people. Don't we, as scientists, have some obligation to communicate to the non-scientists that this problem, which is of great social interest, is a difficult problem to solve. That's all I'm trying to convey in the entry.

On your opinion that ridge theory not being an established notion in the field, I must say I agree. Ridge theory is not established. The work in computer vision and image analysis that uses "ridges" does so in a Wild West fashion. That is to say, ridges are being used to advance the frontiers in image analysis and a very fruitful and generous way. But just like Newton and Leibniz made unsubstantiated claims about properties about their calculus, often scientistis make claims about ridges that aren't substantiated by anything more than intuition and inductive understanding. The only work (to my knowledge) that has been done to put ridge theory on a firm mathematical foundation has been done by Pizer, Damon, and their students. All other work that has been done has been experimental and computational. That is the work that advances understanding, and its impportance cannot be overestimates. But a true scientific theory is strongest when it is supported by mathematical proof.

On the existence of algorithms that will detect the ridges (in sclae space or Euclidean space) of a function, one find in the literature all sorts of exposition on ridge finding, but there is very little (open source) code that is accessible to the scientific community to help people implement ridge-theoretic techniques. Furthermore, there are very few people publishing on ridges. If we want to share with the scientific and mathematical community the importance of ridges, we need to talk about ridges in a way that makes them understand that there are cool scientific and mathematical questions that can be answered with ridges.

Regarding the concern about "relative critical set", there are few algorithms that make these concepts useful because few people know about them. A wikipedia entry is a perfect place for saying _something_ about relative critical sets, especially since a relative critical set of dimesion (k+1) self-intersects at the relative critical set of dimension k. (This means that the critical points of a function and precisely the self intersection points of the relative critical curves of the function. Isn't this beautiful?) Millerj870 00:00, 26 February 2007 (UTC)[reply]

Concerning the problem of object recogntion, I could agree with the statement that if one starts by computing a graph representation from a grey-level image and without further thoughts aims at using this graph for object recognition, one may end up with a problem that is very likely to be notoriously difficult, or even intractable. The view-based approaches to object recognition that have been developed over the last 10 years or so, however, show that the problem of recognizing a set of known objects in a complex scene can be quite managable, and may even be addressed in real time if the set of objects to be recognized is sufficiently small.

The area of computer vision is according to my viewpoint very much a problem of doing an appropriate modelling. If useful concepts are approprietely defined, subsequent algorithms may in many cases be rather straightforward. If one, on the other hand starts from unsuitable definitions, then the subsequent task of solving the actual original problem may in practice be untractable. Of course, I agree that a proper mathemathical foundation is in many cases necessary. There are however some areas of computer vision where quite complicated proofs have been presented where one can question if the model they study are appropriate at all.

The best solution is of course if appropriate modelling and a well-founded theory go hand in hand. To say that all other works on ridge detection except Pizers, Damon lack a mathematical foundation, however, is a mere insult to all others who have provided valuable contributions to the problem. Contrary to your statement, I find "computational" as a very valuable attribute of research in computer vision. A large part of the problem is to state operational definitions that can be implemented robustly on real-world noisy data. According to my viewpoint, this is one important aspect "computational", and in no way "computational" excludes mathematical proofs. For example, the commonly used notion of "scale-space ridges" to a very large extent boils down to the application of a well-stated and operational definition to image data in 2-D or 3-D. From the way the definition has been stated, it straightforwardly follows that scale invariance holds. The way that this notion has been successfully applied to different types of problems shows that it works in practice.

Concerning the intrinsic difficulties of the computer vision problem, I agree that the popular literature seems to be almost fully unaware of how complex the vision problem is (or can be). From a pedagogical viewpoint, however, I would find it more appropriate to describe these difficulties in some of the general pages on computer vision. If one start on this page on ridge detection by describing purely graph-based approaches, which may lead to notoriously difficult subsequent problems unless handled with an extreme degree of special care, I'm afraid that one may put the reader of this article on a wrong track. Therefore, I have now modified the text in the introduction to have a much lower emphasis on graphs. Tpl 12:42, 27 February 2007 (UTC)[reply]

The first paragraph

In a 2-D function, a ridge is a connected set of points that are maximal in at least one dimension. In 2D, "maximal in at least one dimension" would include singular point maximas are ridges. Is this correct? When extended to N dimensions, a ridge is a connected sequence of points that are maximal in N-1 dimensions. In both sentences the word "maximal" is used, but I would guess that "minimal" may also be applicable? Or is the concept of ridges restricted to bright structures on dark background? --KYN 07:54, 27 September 2006 (UTC)[reply]

Of course the important word "bright" is missing here. I have corrected that. Tpl 09:47, 27 September 2006 (UTC)[reply]

"In a 2-D function, a (bright) ridge is a connected set of points that are maximal in at least one dimension". This definition includes also isolated point maximas. Is this correct? --KYN 16:08, 28 September 2006 (UTC)[reply]

The addition of "bright" is not necessary, as a ridge of function values (e.g., intensity) can extend through a region of low values in a continuous and unbroken fashion. Millerj870 17:53, 17 January 2007 (UTC)[reply]

Some of the ridge points will also be local maxima. Whether to include or exclude them is to me a matter of definition. Tpl 05:46, 29 September 2006 (UTC)[reply]

This could then be mentioned as a possible distinction between ridges and lines. --KYN 18:33, 30 September 2006 (UTC)[reply]

According to the definition tendered, critical points that are local maxima will be ridge points because they are maximal in at least one direction (they are maximal in all directions). Millerj870 17:53, 17 January 2007 (UTC)[reply]

Second paragraph

In the scale space of an image, ridges provide an invariant description of elongated structures invariant relative to what? , and thus provide a complement to natural interest points (local extremal points) I take it that local extremal points are an example of what here is called natural interest points. There are other natural interest points in the form of corners or crossings. Are ridges complements also of these interest points? . In image scale space, a ridge is a connected set of points that are maximal in one of the spatial dimensions as well as in the scale dimension. 1) Is this an alternative definition relative to the one provided in the first paragraph, or a more precise formulation? 2) This definition is interesting since it suggests that a ridge can be a curve in the 3D scale space of a 2D image. Is this correct? Is the resulting ridge then the projection of this curve onto the 2D image? Ridges occur along the center of elongated structures since "elongated structures" is a rather vaguely defined concept maybe "in general occur along..." is better since it promises less? , and thus provide a form of scale invariant skeleton for organizing spatial constraints on local appearance. These three concepts need to be explained, perhaps in terms of examples: 1) Scale invariant skeleton 2) spatial constraints (which constraints?) 3) Local appearance --KYN 18:33, 30 September 2006 (UTC)[reply]

I'm not the first author of the text in this paragraph. Since I may have modified the text somewhat and know about the field, I'll answer your questions.

Concerning invariance, the invariance properties depend a bit upon precisely which ridge definition you use, but as a general statement a reasonable ridge definition should be covariant with respect to translations, rotations and rescalings in the image domain as well as affine stretchnings of the intensity domain. In addition, some definitions are also covariant with monotone intensity transformations, but the latter property is hard to maintain on noisy data.
Concerning complement to interest point, the word "natural" is not essential here. Ridge features in the form of curves serve as a complement to interest points in terms of corners, blobs and local maxima and minima. Also point-like features that respond to ridges have been defined and been used in simplified systems for tracking and recognition.
For ridges defined in a scale-space representation, a reasonable definition of a scale-space ridge will for a two-dimensional image be a one-dimensional curve embedded in the three-dimensional scale-space, which in turn can be projected onto the two-dimensional image domain. This is really an important aspect of the definition and can be seen as an extension of the way in which certain interest point features are defined from scale-space extrema, which are local maxima in the 3-D scale-space of a 2-D image, and then projected down to 2-D image space.
Concerning elongated structures, the underlying motivation for extracting ridge features is in most cases to capture the axes of symmetry of an elongated object.
Concerning the sentence "[ridges] thus provide a form of scale invariant skeleton for organizing spatial constraints on local appearance", I agree that this sentence is somewhat condensed. However, it is not at all incorrect, and agrees with the intention of ridge descriptors by a few authors in the area. To develop this notion in more detail in Wikipedia, however, there is more work that one could do in terms of research articles first. (Some people may have some work to do here :-)

Tpl 17:40, 3 October 2006 (UTC)[reply]

Now the material on scale-space ridges has been extended with explicit definitions as well as an explicit discussion of the projection of curves in the 3-D scale-space onto the 2-D image domain. Tpl 19:23, 19 January 2007 (UTC)[reply]

I have some concerns about this second parpagraph. What it says is misleading. A ridge of an elongated figure in a greyscale digial image need NOT represent its center. That is, the ridge curve that appears in such a figure need not run down its center. If there paragraph were to be revised to say something like, "The original motivation for ridge-theory in the context of image analysis was to extent to greyscale images the concept of medial skeleton" then the paragraph would be ok. As it is, the paragraph is incorrect. It's easy to imagine the case of a very simple figure in a greyscale image whose ridge is not a medial curve. Take, for example, the greyscale image of a black background with a white rugby ball in the foreground that is illuminated from a direction to the left of the camera. The ball will appear as an ellipse in the 2D image with it's left side more bright (higher in intensity) than it's right, which is at least slightly shadowed. When we regard the image as the graph of an intensity function, the ridge of that function lies closer to the left edge of the rugby ball than the right - the greater the contrast between light and shadow, the further from the ball's center will the ridge run.

Let's see if we can come to some agreement about revising this paragraph. Ridges are too cool to not get this entry right! Millerj870 21:09, 4 February 2007 (UTC)[reply]

In the previous formulation there was a qualifier "in principle" in the statement. Now, I've made this more explicit by the additional qualifier "for a roughly symmetric intensity profile". Tpl 10:27, 6 February 2007 (UTC)[reply]

Second restructuring of the article

After the restructuring of this article by user Millerj870, I made a second restructuring trying to accomplish a better compromise between the best aspects of the previous outline and the new suggestion. For an encyclopedia article, I think that it is better to start with a verbal description of the most important information rather than starting with a set of formulae. Therefore I reinsrted a general overview introduction which aims at accomplishing this. Since the two-dimensional case is much easier to handle in terms of closed-form expressions for the formulae, I also developed the two-dimensional theory for the cases of fixed scale ridge detection and variable scale ridge detection. My view is that this material could be presented before proceeding to the more general N-dimensional case, which may be harder to grasp for unfamiliar readers. I have also added a number of more references concerning main topics of the theory as well as applications. I have, however, tried as much as possible not to touch the material that Miller870 seems to indicate that he may work further upon. My only suggestion in this respect is to merge the generalization of the concept of local maxima to ridges in arbitrary dimension to a section that describes N-dimensional ridge definitions in more detail. In the new outline of the article, there is a specific section about the N-dimensional case. Tpl 16:39, 19 January 2007 (UTC)[reply]

The article is moving in the right direction, but I worry about the increasing level of technical detail. TPL is right to keep the introduction as verbal or expository as possible; this is the best way to get people to appreciate the ideas that are to follow. I wonder if there were a way for us to add images that would help the reader visualize what we're talking about. If my suspicions are correct, I think TPL is more likely to have access to such images than I am, but I think I can come up with a few. Millerj870 21:12, 4 February 2007 (UTC)[reply]

Center of Luminance Ridge Detection

This is a fast algorithm that has been used to acquire cell outlines and by surface profile 3-D laser scanners. It has also been called the Center of Mass Algorithm since the calculation for one point is the same. I think it would be good to include a short description of it on this page, along with references. The reason I haven't just dived in and started doing it is because the page is so well written and so cohesive I first want to discuss what would be the best way to make this change. Zen-in (talk) 17:08, 12 September 2010 (UTC)[reply]

I have not previously heard about the method you mention. The intention with this article is that it should describe the most important and widely used methods for ridge detection that are of wide interest. A possible suggestion for you to handle the method you mention could be by first writing a standalone article on that topic. Such an article could also describe the corresponding application of the method to edge detection as you mention in the discussion page on that topic. Then, you could insert links to your new article from these pages and also other authors could express their opinion. Tpl (talk) 14:24, 13 September 2010 (UTC)[reply]

Height ridge

The stub on height ridge appears to (want to) treat the same topic. The main references seem to be the same: Lindeberg, Haralick, Eberly etc. Tijfo098 (talk) 12:46, 2 September 2012 (UTC)[reply]

requires more generic summary

this article jumps right into the technical specifications. it does not provide a basic, generic statement saying what ridge detection actually is. its way too focussed on maths and does not provide any way for someone to find out what ridge detection is unless they already knew what ridge detection was. — Preceding unsigned comment added by 111.69.192.23 (talk) 14:19, 2 February 2013 (UTC)[reply]