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   -&gt;  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 &quot;weight&quot; or &quot;impedance&quot; quantifying &quot;how much it costs to step into this square&quot;.  Weight would be undefined for zeros.
input     weight      distance
1 1 0     0 2 X        2 2 0
1 1 1  ,  3 2 3   -&gt;   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?
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.