Find 'distance from the edge' of a numpy array

Question

I have a numpy array with 1s & 0s (or bools if that's easier)

I would like to find the distance from each 1 its closest 'edge' (an edge is where a 1 meets a 0).

Toy example:

Original array:

array([[0, 0, 0, 0],
       [0, 1, 1, 1],
       [0, 1, 1, 1],
       [0, 1, 1, 1]])

Result:

array([[0, 0, 0, 0],
       [0, 1, 1, 1],
       [0, 1, 2, 1],
       [0, 1, 1, 1]])

If possible, I'd like to use the 'cityblock' distance, but that's lower priority

Thanks!

Answer 1

Here's a vectorized approach using binary_erosion & cdist(..'cityblock') -

from scipy.ndimage.morphology import binary_erosion
from scipy.spatial.distance import cdist

def dist_from_edge(img):
    I = binary_erosion(img) # Interior mask
    C = img - I             # Contour mask
    out = C.astype(int)     # Setup o/p and assign cityblock distances
    out[I] = cdist(np.argwhere(C), np.argwhere(I), 'cityblock').min(0) + 1
    return out

Sample run -

In [188]: img.astype(int)
Out[188]: 
array([[0, 0, 0, 0, 1, 0, 0],
       [0, 1, 1, 1, 1, 1, 0],
       [0, 1, 1, 1, 1, 1, 1],
       [0, 1, 1, 1, 1, 1, 1],
       [0, 0, 1, 1, 1, 1, 1],
       [0, 0, 0, 1, 0, 0, 0]])

In [189]: dist_from_edge(img)
Out[189]: 
array([[0, 0, 0, 0, 1, 0, 0],
       [0, 1, 1, 1, 2, 1, 0],
       [0, 1, 2, 2, 3, 2, 1],
       [0, 1, 2, 3, 2, 2, 1],
       [0, 0, 1, 2, 1, 1, 1],
       [0, 0, 0, 1, 0, 0, 0]])

Here's an input, output on a human blob -

Answer 2

Here's one way you can do this with scipy.ndimage.distance_transform_cdt (or scipy.ndimage.distance_transform_bf):

import numpy as np
from scipy.ndimage import distance_transform_cdt


def distance_from_edge(x):
    x = np.pad(x, 1, mode='constant')
    dist = distance_transform_cdt(x, metric='taxicab')
    return dist[1:-1, 1:-1]

For example:

In [327]: a
Out[327]: 
array([[0, 0, 0, 0],
       [0, 1, 1, 1],
       [0, 1, 1, 1],
       [0, 1, 1, 1]])

In [328]: distance_from_edge(a)
Out[328]: 
array([[0, 0, 0, 0],
       [0, 1, 1, 1],
       [0, 1, 2, 1],
       [0, 1, 1, 1]], dtype=int32)

In [329]: x
Out[329]: 
array([[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
       [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0],
       [1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0],
       [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0],
       [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
       [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0],
       [0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]])

In [330]: distance_from_edge(x)
Out[330]: 
array([[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
       [1, 2, 2, 2, 2, 1, 0, 0, 0, 1, 0, 0],
       [1, 2, 3, 3, 2, 1, 0, 0, 1, 2, 1, 0],
       [1, 2, 3, 3, 2, 1, 0, 0, 0, 1, 0, 0],
       [1, 2, 3, 3, 2, 1, 0, 0, 0, 0, 0, 0],
       [1, 1, 2, 2, 2, 1, 0, 0, 0, 1, 1, 0],
       [0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 2, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]], dtype=int32)

If you don't pad the array with zeros, you get the distance to the nearest 0 in the array:

In [335]: distance_transform_cdt(a, metric='taxicab')
Out[335]: 
array([[0, 0, 0, 0],
       [0, 1, 1, 1],
       [0, 1, 2, 2],
       [0, 1, 2, 3]], dtype=int32)

In [336]: distance_transform_cdt(x, metric='taxicab')
Out[336]: 
array([[6, 5, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0],
       [5, 5, 4, 3, 2, 1, 0, 0, 0, 1, 0, 0],
       [4, 4, 4, 3, 2, 1, 0, 0, 1, 2, 1, 0],
       [3, 3, 4, 3, 2, 1, 0, 0, 0, 1, 0, 0],
       [2, 2, 3, 3, 2, 1, 0, 0, 0, 0, 0, 0],
       [1, 1, 2, 2, 2, 1, 0, 0, 0, 1, 1, 0],
       [0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 2, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2]], dtype=int32)

---

Here a different method that uses scipy.ndimage.binary_erosion. I wrote this before I discovered the distance transform function. I'm sure there are much more efficient methods, but this should work reasonably well for images that are not too big.

import numpy as np
from scipy.ndimage import binary_erosion


def distance_from_edge(x):
    dist = np.zeros_like(x, dtype=int)
    while np.count_nonzero(x) > 0:
        dist += x  # Assumes x is an array of 0s and 1s, or bools.
        x = binary_erosion(x)
    return dist

For example,

In [291]: a
Out[291]: 
array([[0, 0, 0, 0],
       [0, 1, 1, 1],
       [0, 1, 1, 1],
       [0, 1, 1, 1]])

In [292]: distance_from_edge(a)
Out[292]: 
array([[0, 0, 0, 0],
       [0, 1, 1, 1],
       [0, 1, 2, 1],
       [0, 1, 1, 1]])

In [293]: x
Out[293]: 
array([[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
       [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0],
       [1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0],
       [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0],
       [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
       [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0],
       [0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]])

In [294]: distance_from_edge(x)
Out[294]: 
array([[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
       [1, 2, 2, 2, 2, 1, 0, 0, 0, 1, 0, 0],
       [1, 2, 3, 3, 2, 1, 0, 0, 1, 2, 1, 0],
       [1, 2, 3, 3, 2, 1, 0, 0, 0, 1, 0, 0],
       [1, 2, 3, 3, 2, 1, 0, 0, 0, 0, 0, 0],
       [1, 1, 2, 2, 2, 1, 0, 0, 0, 1, 1, 0],
       [0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 2, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]])