Algorithm for following the path of ridges on a 3D image

I'm trying to find an algorithm (or algorithm ideas) for following a ridge on a 3D image, derived from a digital elevation model (DEM). I've managed to get very basic program working which just iterates across each row of the image marking a ridge line wherever it finds a large change in aspect (ie. from < 180 degrees to > 180 degrees).

However, the lines this produces aren't brilliant, there are often gaps and various strange artefacts. I'm hoping to try and extend this by using some sort of algorithm to follow the ridge lines, thus producing lines that are complete (that is, no gaps) and more accurate.

A number of people have mentioned snake algorithms to me, but they don't seem to be quite what I'm looking for. I've also done a lot of searching about path-finding algorithms, but again, they don't seem to be quite the right thing.

Does anyone have any suggestions for types or algorithms or specific algorithms I should look at?

Update: I've been asked to add some more detail on the exact area I'll be applying this to. It's working with gridded elevation data of sand dunes. I'm trying to extract the crests if these sand dunes, which look similar to the boundaries between drainage basins, but can be far more complex (for example, there can be multiple sand dunes very close to each other with gradually merging crests)

---

You can get a good estimate of the ridges using sign changes of the curvature. Note that the curvature will be near infinity at flat regions. Hence possible psuedo-code for a ridge detection algorithm could be:

for each face in the mesh
   compute 1/curvature
   if abs(1/curvature) != zeroTolerance 
     flag face as ridge
   else
     continue

(zeroTolerance is a number near but not equal to zero eg 0.003 etc)

Also Meshlab provides a module for normal & curvature estimation on most formats. You can test the idea using it, before you code it up.

---

I don't know how what your data is like or how much automation you need. This won't work if if consists of peaks without clear ridges (but then you probably wouldn't be asking the question.)

startPoint = highest point in DEM (or on ridge)
curPoint = startPoint;
line += curPoint;
Loop
    curPoint = highest point adjacent to curPoint not in line; // (Don't backtrack)
    line += point;
Repeat

Curious what the real solution turns out to be.

Edited to add: depending on the coarseness of your data set, 'point' can be a single point or a smoothed average of a local region of points.

---

http://en.wikipedia.org/wiki/Ridge_detection

链接地址: http://www.djcxy.com/p/79656.html

上一篇: 无论如何去除航空影像的算法变色

下一篇: 用于跟踪3D图像上脊的路径的算法