Raster path following algorithms

Question

I've got a raster grid of values that looks something like the image below (white is high values, the black background value is zero).

I'm trying to write some kind of path-following code to start at the end of one of the lines and trace to the other end, going via the highest possible values (that is, the whiter the pixels chosen to be in the line the better) but still getting to the other end.

I've been struggling with this for a while, and can't seem to get anything I try to work. So I wondered, has a generic algorithm already been developed for this sort of problem? I've done a lot of searching, but most path algorithms seem to be designed to work on vectors/networks, not raster grids like this.

Any ideas?

Answer 1

The simplest idea probably is to use the A* algorithm, where each pixel is a node, and the cost of the node is the pixel darkness.

Update: Found a nice tutorial.

Answer 2

One way to do this:

1. Filter the image to get it closer to black and white only pixels.
2. Draw a line through the white pixels. To do this, start at a white pixel. Draw a line from that pixel to each other white pixel a distance of 2 (or 3 or so) away, but ignore pixels near a previous line. Keep going until you've covered every pixel not close (2 or 3 pixels) from a line. You'll have to do some minor adjustments here to get it to work well.
3. Connect the endpoints of the lines you've drawn. If there are two endpoints near (1 or 2 pixels?) one another, connect them. You should end up with a few lines made up of a lot of short segments, possibly with some loops and forks.
4. Get rid of any small loops in the lines, and seperate the lines at forks, so you have a few lines made of a lot of short segments.
5. Reduce points. For each line, check to see if it is nearly straight. If so, remove all the interior points. If not, check the two halves of the line recursively until you get down to the minimum segment lengths.
6. You can optionally fit a spline curve through the lines at this point.
7. Profit.

It will take some tweaking to get it to work well, but it is possible to do it this way. One other variant is to outline the white sections, if they are wider than 1 or 2 or 3 pixels, and combine the double lines afterward.