8
$\begingroup$

I would like to find the shortest path in an image from one pixel to another. If the image is grayscale, the distance between two pixels could be Abs[p1 - p2], otherwise for multichannel images it could be EuclideanDistance / ManhattanDistance or whatever. For example, here's the shortest path from {1,1} to {32,32} in an RGB image using the ManhattanDistance between pixel colours:

input image $\rightarrow$ image with path overlay

My first attempt is abysmally slow. It uses a temporary GridGraph to construct a 4-connected grid (8-connected is also desired in future!) and extracts the edge pairs. It then builds a second GridGraph of identical size from these edges but fills in the edge weights. I had to do this because I couldn't find how to update graph weights on an existing graph in Mathematica. Finally it calls FindShortestPath on this graph and the rest is just turning the path vertices back into row-column coordinates so I can highlight the pixels in the image. It's a lot of work to do something that could be simpler.

vtx2rc[id_, rows_] := Module[{r = 1 + Mod[(id - 1), rows]}, {r, (id - r)/rows + 1}]
weightfn[dat_, v1_, v2_] := ManhattanDistance[
 Extract[dat, vtx2rc[v1, Length@dat]],
 Extract[dat, vtx2rc[v2, Length@dat]]
]
makegr[dat_, dims_] := Module[{rows = dims[[1]], gr = GridGraph[dims]},
  Return[GridGraph[dims, 
    EdgeWeight -> ((# -> weightfn[dat, #[[1]], #[[2]]]) & /@ 
       EdgeList[gr])]]
  ]
rc2node[rc_, rows_] := (rc[[2]] - 1)*rows + rc[[1]]
genpath[gr_, rows_, p1_, p2_] := 
 vtx2rc[#, rows] & /@ 
  FindShortestPath[gr, rc2node[p1, rows], rc2node[p2, rows]]
makemask[path_, dims_] := Module[{c = ConstantArray[0, dims]},
  For[i = 1, i <= Length[path], ++i,
   c[[path[[i, 1]], path[[i, 2]]]] = 1;
   ];
  Return[Image[c] // ImageAdjust]
]

Usage looks like this:

img = img = ImageResize[<<<your image here>>>,64]
dat = ImageData[img];
dims = Most@Dimensions@dat;
gr = makegr[dat, dims];
startpoint = {1, 1};
endpoint = Reverse@ImageDimensions@img;
Show[ImageAdd[img,
  makemask[genpath[gr, dims[[1]], startpoint, endpoint], dims]]]

For images size > 128 it's too slow and I really need it closer to realtime. Ideally I want something fast enough that I can have two Locator points in a manipulate and draw the path over the image on the fly.

I'm fine with suboptimal short paths if they're quick to find on large images in under 2s.

$\endgroup$
6
  • 1
    $\begingroup$ I don't understand how you defined the "shortest path in an image from one pixel to another". Could you clarify that point? Would that not always be the line connecting those two points, rasterized at the same resolution of your image? $\endgroup$
    – MarcoB
    May 13, 2020 at 19:37
  • 2
    $\begingroup$ Each pixel is connected to its immediate neighbours either in a 4-connected way, or 8-connected if you choose to include the diagonals. For 4-connected this is a GridGraph. Give each edge in this graph a weight that represents some choice of colour distance between the two connected pixels. If you had an 8 x 5 image for example, its graph is GridGraph[{5,8}]. The shortest path is a valid path on the GridGraph connecting start and end points that minimizes the total colour distance along the chosen edges. $\endgroup$
    – flinty
    May 13, 2020 at 20:14
  • 1
    $\begingroup$ A suggestion: Your algorithm is slow because it does global optimization (which scales poorly). Instead, start with the straight-line path between $A$ and $B$ and calculate the "distance" between neighboring pixels on this path. Then perturb segments of the path and accept if it yields shorter distance. Continue within interactive time constraints. This may not give the shortest route, but it may give a good route given your interactive time constraints. $\endgroup$ May 15, 2020 at 17:43
  • $\begingroup$ Did you check which part is slow ? Graph generation or Optimization ? $\endgroup$
    – A.G.
    May 15, 2020 at 17:45
  • 3
    $\begingroup$ I would implement A* in C, to operate directly on images. A lot of work? Yes. $\endgroup$
    – Szabolcs
    May 16, 2020 at 9:18

1 Answer 1

9
+300
$\begingroup$

The problem appears to be that constructing a weighted graph using this syntax:

EdgeWeight -> ((# -> weightfn[dat, #[[1]], #[[2]]]) & /@ 
       EdgeList[gr])]]

is incredibly slow. If I replace it with the following:

EdgeWeight -> ((weightfn[dat, #[[1]], #[[2]]]) & /@ EdgeList[gr])

it brings the total computation time down from 21.7 seconds to 0.436 seconds, using a 128x128 image. The same graph will be constructed regardless of which syntax you choose.

$\endgroup$
5
  • $\begingroup$ It's still a bit choppy but now good even at 512x512. I've accepted as it solves my first problem with performance. My other problems are how to get it to scale to 1920x1080 and is there something I can replace GridGraph with to get an 8-connected graph? $\endgroup$
    – flinty
    May 16, 2020 at 1:29
  • $\begingroup$ @flinty I looked at how to construct the 8-connected graph but I didn’t find any solution with satisfactory performance. I’ll let you known if I figure it out. $\endgroup$
    – C. E.
    May 16, 2020 at 16:11
  • $\begingroup$ @flinty This solution, GridGraph with diagonal edges, works for m-by-n grids, but it's slow for when m x n is large. $\endgroup$
    – creidhne
    May 19, 2020 at 12:40
  • 1
    $\begingroup$ @flinty Well, your question disappeared, but consider the answers to mathematica.stackexchange.com/a/165561/41569 for m-by-n grids. I'm still working on a speedier method. $\endgroup$
    – creidhne
    May 19, 2020 at 13:01
  • $\begingroup$ @creidhne Yes I deleted it - you could post your method to the existing question you found. I have chosen to implement A* search over images as a C++ DLL library I can load and control from Mathematica to get better performance. $\endgroup$
    – flinty
    May 19, 2020 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.