Distance map filter with speed image? Computing the minimal path to boundary with obstacles.


(Andrew Wilson) #1

I’m looking for an operation (hopefully an itk filter) that computes the minimal distance to a boundary/surface with obstacles (like how the speed function is used in fast marching).

Basically I have two polygons. I want to compute the shortest path from all the points on the surface of the polygon to the points on another separate polygon. However, I want to enforce a “no travel zone” (binary speed image). I know this would be computed in volumes so I already have binary masks of my polygons (I use them for other things) and I have binary masks for the “no travel zones.”

What I’m describing is very much like a distance map filter. But I need a distance map filter that can use a speed function/“no travel zone” and I’m not aware of one in ITK that would do it. Essentially I would supply it with 3 input images, in my case binary. The two images to compute distances between (input0 would be where it starts and input1 would be where it should end), then a speed image to specify how fast to go in those areas (by setting to 0 it would have to go around).

Alternatively fast marching could certainly do this. But the calculation would take quite awhile and be highly inefficient. It would work like so: Fast march for every point on poly1 with binary speed image essentially finding the shortest path to all other points. Then just compare the distances of all the points on poly2 and chose the smallest. But like I said this would take very long.

Any help would be much appreciated.


(Dženan Zukić) #2

This could be done using breadth first search algorithm. Input: speed image. Have a temporary image which indicates which pixels have their distance calculated. And the output distance image. Set the “no travel zone” to have +inf distance (or PixelType's maximum value) and mark it as calculated or treat it specially in some other way.

Mark the pixels in one polygon as having distance 0. In each iteration, calculate distance for each pixel which has at least one neighbor with known distance. And its distance would be the neighbor with lowest distance +1 (or +1.41 if it is a diagonal neighbor). Keep iterating until you reach all pixels of the other polygon or fill the whole image.

While you could scan the entire image in each iteration to find the pixels on the current front, it is almost certainly more efficient to keep a set of the indices on the front. And once a pixel has its distance calculated, add its neighbors to the set.

To make this work with arbitrary “speed image” instead of “go/no go” one, the algorithm would have to be more complicated.


(Bradley Lowekamp) #3

I think the ColidingFrontsImageFilter may be similar to what you are looking for.


(Andras Lasso) #4

If there is no ITK class that directly implements this and your application also uses VTK then you may consider using vtkDijkstraImageGeodesicPath.