Find the best path along raster

Question

I've just posted a question to StackOverflow about the best way to go about finding the best path on the raster below (where whiter pixels are 'better'), but have realised that it might actually be very easy to solve using some inbuilt GIS functions. To clarify, I'm trying to choose the best path down each of the lines shown in the image, staying on the bright white pixels as much as possible.

I have a feeling that the idea of Cost Surfaces and Cost Paths might help me with this, but I've had a play in ArcGIS and can't seem to get anything sensible out of it. Is this the right approach to take within a GIS? If not, are there some other inbuilt functions in a GIS that can do this kind of thing?

Answer 1

In terms of premade GIS, there's a bunch of stuff out there for travel costs on raster surfaces, e.g. r.cost, r.walk (different costs for uphill vs downhill!)

If you prefer brewing up code yourself so you know the exact algorithm:

https://stackoverflow.com/questions/2311486/how-to-calculate-the-shortest-path-between-two-points-in-a-grid

Answer 2

If you're okay with some algorithm programming then a pathfinding algorithm is a good option. A* would work if you have a desired destination, if not Dijkstra would do well. Assign lower costs to brighter pixels. If you're looking for speed, though, it might not be the best option.

Answer 3

I'd try something like this (example given in GRASS but the steps are similar for other software):

• Identify the source locations. One technique: mask the raster to the start row and filter the raster by value.
• Identify the destination points: in this case, select just the bottom row, and convert the results to vector points, then convert this 'end' raster to vector points.
• Compute the cost distance for the surface, using something like r.cost, using the computed start and end point datasets, and making the cost path raster scaled appropriately.

This does the above, skipping over the masking operations:

# identify start points, dump to raster
r.mapcalc start_rast='if(MASK && map > 100, 1, null())'

# identify the end points and convert to vector
r.mapcalc end_rast='if(END_MASK && map > 100, null())'
r.to.vect in=end_rast out=end_pts

r.cost -k in=raster_to_analyze start_rast=start_rast end_points=end_pts

Depending on what you're trying to do, this may be sufficient, or may require iteration over your start points to get multiple 'shortest cost' rasters.

Answer 4

Using ArcScan is the quickest way - http://www.esri.com/software/arcgis/extensions/arcscan/automatic-vectorization.html

Converts Raster pixels to vector lines and the length can be applied giving you the best path.

Note: You might need to inverse your image to 2 colour bitmap so the white pixels become black and vectorisation can be best applied.