在标签图中获取分段边界框的最快方法

Question

一个3D标签图是一个矩阵，其中每个像素（体素）都有一个整数标签。这些值应该是连续的，也就是说，标签为k的部分不会被打散。

给定这样的标签图（分割），在Python中获取每个部分周围最小边界框的坐标最快的方法是什么？

我尝试了以下方法：

• 使用多索引迭代器（来自numpy.nditer）遍历矩阵，并构建一个反向索引字典。这意味着对于每个标签，你可以得到每个体素的3个坐标。
• 对于每个标签，获取每个坐标的最大值和最小值。

好处是你可以在一次O(N)的遍历中获取所有位置信息。坏处是我并不需要这么详细的信息。我只需要极值，所以可能有更快的方法来做到这一点，使用一些比不断添加到列表中更快的numpy函数。有什么建议吗？

在我的机器上，遍历矩阵大约需要8秒，所以如果能减少这个时间就太好了。为了让你了解数据情况，标签图中有几百个标签。标签图的大小可以是700x300x30，或者300x300x200，或者类似的尺寸。

编辑：现在只存储每个标签在每个坐标上的更新最大值和最小值。这消除了维护和存储这些大列表（添加）的需要。

Answer 1

如果我理解你的问题没错的话，你有一些体素（可以理解为三维空间中的小块），你想要找出每个组在每个轴上的最小值和最大值。

我们来定义一下：

• arr：一个三维的整数标签数组

• labels：一个标签列表（整数从0到最大标签值）

下面是代码：

import numpy as np

# number of highest label:
labmax = np.max(labels)

# maximum and minimum positions along each axis (initialized to very low and high values)
b_first = np.iinfo('int32').min * np.ones((3, labmax + 1), dtype='int32')
b_last = np.iinfo('int32').max * np.ones((3, labmax + 1), dtype='int32')

# run through all of the dimensions making 2D slices and marking all existing labels to b
for dim in range(3):
    # create a generic slice object to make the slices
    sl = [slice(None), slice(None), slice(None)]

    bf = b_first[dim]
    bl = b_last[dim]

    # go through all slices in this dimension
    for k in range(arr.shape[dim]):
        # create the slice object
        sl[dim] = k
        # update the last "seen" vector
        bl[arr[sl].flatten()] = k

        # if we have smaller values in "last" than in "first", update
        bf[:] = np.clip(bf, None, bl)

经过这个操作后，我们会得到六个向量，分别给出每个轴上最小和最大的索引。例如，标签 13 在第二个轴上的边界值是 b_first[1][13] 和 b_last[1][13]。如果某个标签缺失，那么所有对应的 b_first 和 b_last 的值都会是最大的 int32 值。

我在我的电脑上试过，对于一个 (300,300,200) 的数组，找到这些值大约需要1秒钟。