NumPy数组中“岛屿”/“连通组件”之间的成对距离

Question

NumPy数组中“岛屿”/“连通组件”之间的成对距离

pythonarraysnumpyscipyimage-segmentation

9

考虑以下图像，存储为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中解决这个问题吗？或者给我一些资源链接吗？

- r0f1

这回答您的问题吗？Python中最快的成对距离度量 - norok2

1

不好意思，不是的。您发布的链接只考虑了一维情况，并且解决的问题也略有不同。 - r0f1

我认为解决你的问题的方法基本上是相同的。我会开始尝试适应其中的内容，看看是否会在某个地方卡住。 - norok2

@yatu 我很好奇，是比较两个岛屿的所有点需要更长时间，还是只需按照下面的帖子进行比较？ - Ehsan

1

我认为如果这些岛屿已经被“标记”，下面的方法应该可以很好地工作。如果它们没有被明确标记，那么连接组件就会更多。 - yatu

1

@r0f1 请问第三个和第四个岛屿之间的直线距离是多少？我不确定这种情况下距离的定义是否清晰。请详细说明一下。谢谢。 - Ehsan

2个回答

6

对于许多大型的或更大的 blob，或者如果性能/内存效率是一个标准，您可能希望使用这些岛的轮廓。考虑到这一点，我们将使用OpenCV 的 findContours来获取轮廓，然后执行成对距离计算，并将最小值作为最终输出结果。实现将类似于以下内容，以获取所有可能的成对距离 -

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和Manhattan距离的'minkowski'和'cityblock'。

因此，cdist(idxs[i], idxs[j])将变更为cdist(idxs[i], idxs[j], metric=...)。

- Divakar

请注意：此假设每个岛屿（连通组件）都具有唯一的值。如果多个连通组件具有相同的值，则“idx = [c [0] for contour in contours for c in contour]”将更准确。 - smttsp

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ehsan · Accepted Answer

以下是您需要的内容：

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()

查找岛屿的位置，计算位置之间的两两距离并获得最小值。我不确定您想要的距离是否准确，但我认为您正在寻找 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