Numpy 数组中两个 "islands"/"connected components" 之间的成对距离

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)

0 表示背景像素，1、2、3 和 4 表示属于对象的像素。您可以看到物体总是在图像中形成连续的岛或区域。我想知道每对物体之间的距离。作为距离度量，我希望对象的那些像素之间的最短直线距离彼此最接近。示例：Distance(2,3) = 1，因为它们正在接触。 Distance(1,2) = 2，因为恰好有一个背景像素将两个区域分开，或者说，物体最近的像素相隔两个像素。

谁能告诉我如何解决 Python 中的这个问题？或者 link 我要一些资源？

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 度量更改为您想要的指标。

输出：

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

对于许多斑点或更大的斑点，或者如果 performance/memory 效率是一个标准，您可能希望使用这些岛屿的轮廓。考虑到这一点，我们将使用 OpenCV's 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)}

给定样本的输出字典 -

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=...)。

Numpy 数组中两个 "islands"/"connected components" 之间的成对距离

Pairwise Distances Between Two "islands"/"connected components" in Numpy Array

python

arrays

numpy

scipy

image-segmentation