Numpy Array 中两个“孤岛”/“连接组件”之间的成对距离

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度量更改为所需的度量。

输出：

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，或者如果性能/内存效率是一个标准，您可能希望使用这些岛的轮廓。考虑到这一点，我们将使用OpenCVfindContours来获取轮廓，然后执行成对距离计算并将其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'and 'cityblock'forMinkowski和Manhattandistances。

所以，cdist(idxs[i], idxs[j])会改为cdist(idxs[i], idxs[j], metric=...).