Raster path following algorithms

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开发者_Go百科 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?

---

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.

---

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.

---

I don't think you'll need a genetic algorithm or anything ridiculous; good old fashion recursion and dynamic programming should suffice. I am initially thinking, that you should be able to accomplish your goal by doing a breadth first search. From your starting point, you visit all the neighbors with scores greater then that paths value --all cells start out at infinity, and costs to black cells would be infinity, and these are the paths you can prune off). Once at your destination, if reachable, you should be able to backtrack to find the path. It's greedy, but if your paths are well behaved like these are, it should be fine.

For paths with more gray and twists and turns, it might be a good idea to convert the raster image to a graph, with the edge weight being the the gray scale values of the neighbors (or difference in gray scale values, depending on what this data actually means). So, you should be able to use any algorithm for shortest paths based on that interpretation.

---

If you are doing this on big scale or for research you might try whit http://en.wikipedia.org/wiki/Ant_colony_optimization, but if you are doing this for money just pick up something like flood fill http://en.wikipedia.org/wiki/Flood_fill