# Distance transform with variable "impedance"

The distance transform gives the distance of each pixel in a mask to the nearest zero.

E.g. lets take the Taxicab distance transform:

input       distance
1 1 0       2 1 0
1 1 1   ->  3 2 1
1 1 0       2 1 0


I'm looking for a generalized distance transform where each each element in the mask also has a "weight" or "impedance" quantifying "how much it costs to step into this square". Weight would be undefined for zeros.

input     weight      distance
1 1 0     0 2 X        2 2 0
1 1 1  ,  3 2 3   ->   4 2 3
1 1 0     1 0 X        1 0 0


My questions are:

• Is there a name for this transform?
• Can it be done in O(N) like the traditional distance transform?
• Is there a nice way to generalize this to euclidian distance?
• What do you know about the weights? Are they positive, non-negative, integers? Is there an upper bound on their value? Does it depend on $N$, how? Feb 5 at 14:02
• Found a good python implementation of this "Gray-weighted distance transform" at github.com/0mar/weighted-distance-transform - based on the pictures it seems to generalize to euclidean distance Feb 12 at 0:28

I don't know whether there is a name for the transform you want but it can be computed in time $$\tilde{O}(N)$$ where $$N$$ is the number of entries of the matrix, assuming that the weights are non-negative.
Let the dimensions of the input matrices be $$n$$ and $$m$$. Call $$A$$, $$W$$, and $$D$$ the matrix with the pixel data, the weights, and the distances in output, respectively. Assume for simplicity that $$W[i,j]=0$$ whenever $$A[i,j]=0$$.
Create a directed graph $$G = (V,E)$$ where $$V = \{s\} \cup \{1, \dots, n\} \times \{1, \dots, m\}$$ and $$E$$ contains all edges $$(s, (i,j) )$$ for which $$A[i, j]=0$$ and and edge $$( (i,j), (i',j') )$$ with weight $$W[i',j']$$ for each pair of vertices $$(i,j)$$ and $$(i', j')$$ that satisfy $$|i-i'|+|j-j'|=1$$.
The distance $$d(i,j)$$ from $$s$$ to $$(i,j)$$ in $$G$$ is exactly the distance you are looking for, i.e., $$D[i,j] = d(i,j)$$.
To compute all values $$d(i,j)$$ it suffices to run any single-source shortest-path algorithm from $$s$$ on $$G$$. Using Dijkstra's algorithm the time required is $$O(|E| + |V| \log |V|) = O(N \log N)$$. Faster algorithms might be possible if you have additional assumptions about the weights. For example, if they are bounded by a constant then $$O(N)$$ time suffices.
• Yes, sorry.$\phantom{}$ Feb 10 at 17:41