Python: расстояние от индекса до 1 с в двоичной маске

Question

У меня есть двоичная маска, подобная этой:

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]]

У меня есть определенный индекс в этом массиве, и я хочу вычислить расстояние от этого индекса до ближайшего 1 в маске. Если в этом индексе уже есть 1, расстояние должно быть равно нулю. Примеры (с учетом расстояния до Манхэттена):

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

Существует ли уже такая функциональность в Python / NumPy / SciPy? И евклидово, и манхэттенское расстояние вполне подойдут. Я бы предпочел избегать вычисления расстояний для всей матрицы (поскольку в моем случае это довольно большое значение) и получать только расстояние для моего единственного индекса.

Answer 1

Вот один для manhattan расстояния метри c для одной записи -

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

Образец прогона -

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

Оптимизация производительности за счет извлечения только динамических элементов BLOB-объекты 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()

Количество элементов в nz при этом методе будет меньше, чем в предыдущем, следовательно, оно улучшается.

Answer 2

Вы можете использовать scipy.ndimage.morphology.distance_transform_cdt для вычисления преобразования расстояния "такси" (Манхэттен):

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

Answer 3

Вы можете сделать это так:

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

Спасибо.