Python: distance from index to 1s in binary mask

user_635523 0
Viewed 393

I have a binary mask like this:

X = [[0, 0, 0, 0, 0, 1],
     [0, 0, 0, 0, 1, 1],
     [0, 0, 0, 1, 1, 1],
     [0, 0, 1, 1, 1, 1],
     [0, 0, 1, 1, 1, 1],
     [0, 0, 0, 1, 1, 1]]

I have a certain index in this array and want to compute the distance from that index to the closest 1 in the mask. If there's already a 1 at that index, the distance should be zero. Examples (assuming Manhattan distance):

distance(X, idx=(0, 5)) == 0 # already is a 1 -> distance is zero
distance(X, idx=(1, 2)) == 2 # second row, third column
distance(X, idx=(0, 0)) == 5 # upper left corner

Is there already existing functionality like this in Python/NumPy/SciPy? Both Euclidian and Manhattan distance would be fine. I'd prefer to avoid computing distances for the entire matrix (as that is pretty big in my case), and only get the distance for my one index.

scipy numpy python
3 Answers

You can use scipy.ndimage.morphology.distance_transform_cdt to compute the "taxicab" (Manhattan) distance transform:

import numpy as np
import scipy.ndimage.morphology

x = np.array([[0, 0, 0, 0, 0, 1],
              [0, 0, 0, 0, 1, 1],
              [0, 0, 0, 1, 1, 1],
              [0, 0, 1, 1, 1, 1],
              [0, 0, 1, 1, 1, 1],
              [0, 0, 0, 1, 1, 1]])
d = scipy.ndimage.morphology.distance_transform_cdt(1 - x, 'taxicab')
print(d[0, 5])
# 0
print(d[1, 2])
# 2
print(d[0, 0])
# 5
user_17827920

Here's one for manhattan distance metric for one entry -

def bwdist_manhattan_single_entry(X, idx):
    nz = np.argwhere(X==1)
    return np.abs((idx-nz).sum(1)).min()

Sample run -

In [143]: bwdist_manhattan_single_entry(X, idx=(0,5))
Out[143]: 0

In [144]: bwdist_manhattan_single_entry(X, idx=(1,2))
Out[144]: 2

In [145]: bwdist_manhattan_single_entry(X, idx=(0,0))
Out[145]: 5

Optimize further on performance by extracting the boudary elements only off the blobs of 1s -

from scipy.ndimage.morphology import binary_erosion

def bwdist_manhattan_single_entry_v2(X, idx):
    k = np.ones((3,3),dtype=int)
    nz = np.argwhere((X==1) & (~binary_erosion(X,k,border_value=1)))
    return np.abs((idx-nz).sum(1)).min()

Number of elements in nz with this method would be smaller number than the earlier one, hence it improves.

user_32938810

You can do it like this:

def Manhattan_distance(X, idx):
    dist = min([ abs(i-idx[0]) + abs(j-idx[1]) for i, row in enumerate(X) for j, val in enumerate(X[i]) if val == 1])
    return dist

Thanks.

user_129357790
Related