Попарные расстояния между двумя «островами» / «связанными компонентами» в массиве Numpy

Question

Рассмотрим следующее изображение, сохраненное как массив numpy:

a = [[0,0,0,0,0,1,1,0,0,0],
     [0,0,0,0,1,1,1,1,0,0],
     [0,0,0,0,0,1,1,0,0,0],
     [0,0,0,0,0,0,0,0,0,0],
     [0,0,0,0,0,2,0,0,0,0],
     [0,0,0,0,0,2,2,0,0,0],
     [0,0,0,0,0,2,0,0,0,0],
     [0,0,0,0,3,3,3,0,0,0],
     [4,0,0,0,0,0,0,0,0,0],
     [4,4,0,0,0,0,0,0,0,0],
     [4,4,4,0,0,0,0,0,0,0]]

a = np.array(a)

Нули представляют пиксели фона, 1,2,3 и 4 представляют пиксели, принадлежащие объектам. Вы можете видеть, что объекты всегда образуют непрерывные острова или области на изображении. Я хотел бы знать расстояние между каждой парой объектов. В качестве меры расстояния я хотел бы иметь кратчайшее прямолинейное расстояние между пикселями объекта, которые находятся ближе всего друг к другу. Пример: Distance(2,3) = 1, потому что они касаются друг друга. Distance(1,2) = 2, потому что существует ровно один пиксель фона, разделяющий две области, или, другими словами, ближайшие пиксели объектов находятся на расстоянии двух пикселей друг от друга.

Кто-нибудь может сказать мне, как можно было бы решить эту проблему в Python? Или связать меня с какими-то ресурсами?

Answer 1

Это то, что вам понадобится:

from scipy.spatial.distance import cdist
def Distance(a, m, n):
  return cdist(np.argwhere(a==m),np.argwhere(a==n),'minkowski',p=1.).min()

или аналогично в комментарии @MaxPowers (утверждение: cityblock быстрее):

  return cdist(np.argwhere(a==m),np.argwhere(a==n),'cityblock').min()

Найдите местоположения островов и вычислить попарное расстояние локаций и получить минимум. Я не уверен на 100% в желаемой вами дистанции, но думаю, что вы ищете l1 норму. Если нет, вы можете изменить размер cdist на желаемый c.

вывод:

Distance(a,2,3)
1.0
Distance(a,2,1)
2.0
Distance(a,3,1)
5.0
Distance(a,4,3)
5.0

Answer 2

Для многих BLOB-объектов или больших BLOB-объектов или если критерием является производительность / эффективность использования памяти, вы можете захотеть работать с контурами этих островов. Имея это в виду, мы будем использовать OpenCV findContours, чтобы получить контуры, затем выполнить попарное вычисление расстояния и получить min в качестве окончательного результата. Реализация будет выглядеть примерно так, которая получает все возможные попарные расстояния -

from scipy.spatial.distance import cdist
import cv2

ids = np.arange(1, a.max()+1) #np.unique(a)[1:] if not in ranged sequence

idxs = []
for id_ in ids:
    im = (a == id_).astype(np.uint8)
    contours,_ = cv2.findContours(im, cv2.RETR_TREE, cv2.CHAIN_APPROX_NONE)
    idx = contours[0][:, 0]
    idxs.append(idx)

# Get pairwise indices and then distances
r,c = np.triu_indices(len(ids), 1)
pdists = {(ids[i],ids[j]):cdist(idxs[i], idxs[j]).min() for (i, j) in zip(r, c)}

Выходной dict для данного образца -

In [225]: pdists
Out[225]: 
{(1, 2): 2.0,
 (1, 3): 5.0,
 (1, 4): 7.810249675906654,
 (2, 3): 1.0,
 (2, 4): 5.0,
 (3, 4): 3.605551275463989}

По умолчанию cdist использует евклидово расстояние как metric. В зависимости от вашего определения прямой линии между островами, вы можете попробовать другие метрики, а именно 'minkowski' и 'cityblock' для расстояний Minkowski и Manhattan соответственно.

Итак, cdist(idxs[i], idxs[j]) будет изменить на cdist(idxs[i], idxs[j], metric=...).