The raster path following the algorithms

Question

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

I'm trying to write some code that follows the path to start at the end of one of the lines and trace to the other end, going through the maximum possible values ​​(that is, the whiter pixels selected in the line are better), but still gets to the other end.

I struggled with this for a while and it seems I can’t get anything that I am trying to work. So I wondered if it already has a common algorithm for this kind of problem? I searched many times, but most of the path algorithms seem to be designed to work with vectors / networks, and not with raster networks like this.

Any ideas?

Answer 1

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

Update: found a nice tutorial .

Answer 2

One way to do this:

• Filter the image to bring it closer to black and white pixels.
• Draw a line through the white pixels. To do this, start with a white pixel. Draw a line from this pixel to each other on a white pixel at a distance of 2 (or 3 or so), but ignore the pixels next to the previous line. Continue moving until you cover each pixel not close (2 or 3 pixels) from the line. You will need to make some minor adjustments to make it work well.
• Connect the end points of the lines you drew. If there are two endpoints nearby (1 or 2 pixels?) With each other, connect them. You should get a few lines consisting of many short segments, possibly with some loops and forks.
• Get rid of any small loops in the lines and split the lines on the forks, so that you have several lines of many short segments.
• Reduce points. For each row, check to see if it is nearly straightforward. If so, delete all interior points. If not, check the two halves of the line recursively until you go down to the minimum segment length.
• You can optionally plan a curve through the lines at this point.
• Profit

It will take some improvement to make it work well, but it can be done like this. Another option is to outline the white parts if they are more than 1 or 2 or 3 pixels, and then combine the double lines.

Answer 3

I don’t think you will need a genetic algorithm or something funny; good old fashion recursion and dynamic programming should be enough. I initially think that you should be able to achieve your goal by doing your first breadth first search. Starting from your starting point, you visit all neighbors with an account more than this path value - all cells start at infinity, and the costs of black cells will be infinite, and these are paths that you can turn off). Once you reach the goal, if you reach the goal, you can go back to find the way. This is greedy, but if your paths behave like this, then everything should be fine.

For paths with a grayer and swirling and rotary configuration, it might be a good idea to convert the bitmap to a graph, with the edge weight being the grayscale values ​​(or differences in grayscale values, depending on what this data actually means) . Therefore, you should be able to use any algorithm for the shortest paths based on this interpretation.

Answer 4

If you do this on a large scale or for research, you can try whit http://en.wikipedia.org/wiki/Ant_colony_optimization , but if you do it for the money just pick up something like a flood http: //en.wikipedia .org / wiki / Flood_fill