0
$\begingroup$

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?
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Steven
    Feb 5 at 14:02
  • $\begingroup$ 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 $\endgroup$
    – Peter
    Feb 12 at 0:28
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Should "B" be "W" above? $\endgroup$
    – Peter
    Feb 10 at 16:52
  • $\begingroup$ Yes, sorry.$\phantom{}$ $\endgroup$
    – Steven
    Feb 10 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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