从表示图像的数组中排除周围的零的最快方法是什么？

Question

我有一个二维数组，其中包含从.png创建的灰度图像，如下所示：

import cv2

img = cv2.imread("./images/test.png")
img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

我可以帮您翻译成中文。这段内容与编程有关，需要提取一个子数组，仅包含包含数据的矩形 - 忽略图像周围的所有零值。例如，如果输入为：

  0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0
  0   0 175   0   0   0  71   0
  0   0   0  12   8  54   0   0
  0   0   0   0 255   0   0   0
  0   0   0   2   0   0   0   0
  0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0

那么输出应该是：

175   0   0   0  71
  0  12   8  54   0
  0   0 255   0   0
  0   2   0   0   0

我可以按照正向顺序迭代行来查找第一个非零行，然后反向迭代行以查找最后一个非零行并记住索引 - 然后对列进行相同的操作，然后使用该数据提取子数组，但我肯定有更合适的方法来完成同样的任务，甚至可能有专门设计用于此目的的NumPy函数。

如果我必须在最短的代码和最快的执行之间选择，我会更加关心最快的执行。

编辑：
我没有包含最好的示例，因为中间可能有零行/零列，如下所示：

输入：

  0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0
  0   0 175   0   0   0  71   0
  0   0   0  12   8  54   0   0
  0   0   0   0 255   0   0   0
  0   0   0   0   0   0   0   0
  0   0   0   2   0   0   0   0
  0   0   0   0   0   0   0   0

输出：

175   0   0   0  71
  0  12   8  54   0
  0   0 255   0   0
  0   0   0   0   0
  0   2   0   0   0

- Chupo_cro

---

如果让我在最短的代码和最快的执行之间选择，我更感兴趣的是最快的代码。你所说的“最快的代码”是指最快的执行，对吗？ - dROOOze

你可以不用迭代来完成这个操作，首先通过掩码 >0 进行遮蔽，然后在每个轴上查找最小和最大的掩码索引，最后在该范围内进行切片。我认为在这一点上它可能不会显著提高速度或可读性，但是...值得一试。 - abarnert

@droooze：不用道歉 :-) 我看到了你的回答，感觉它是正确的。我会等你再次写出来的。 - Chupo_cro

我已经完成了！刷新页面并查看 :) - dROOOze

我已经看到了你的第一个回答，因为我截了屏 :-) 它是灰色的，因为你已经删除了回答，但它仍然可读。这是我的错误，因为我没有提供最好的示例数据，我将添加中间带有零的示例。 - Chupo_cro

Answer 1

请注意，这不是一个基于OpenCV的解决方案 - 这适用于一般的n维度NumPy或SciPy数组。

(基于Divakar的答案，扩展到n维度)

def crop_new(arr):

    mask = arr != 0
    n = mask.ndim
    dims = range(n)
    slices = [None]*n

    for i in dims:
        mask_i = mask.any(tuple(dims[:i] + dims[i+1:]))
        slices[i] = (mask_i.argmax(), len(mask_i) - mask_i[::-1].argmax())

    return arr[[slice(*s) for s in slices]]

速度测试：

In [42]: np.random.seed(0)

In [43]: a = np.zeros((30, 30, 30, 20),dtype=np.uint8)

In [44]: a[2:-2, 2:-2, 2:-2, 2:-2] = np.random.randint(0,255,(26,26,26,16),dtype
=np.uint8)

In [45]: timeit crop(a) # Old solution
1 loop, best of 3: 181 ms per loop

In [46]: timeit crop_fast(a) # modified fireant's solution for n-dimensions
100 loops, best of 3: 5 ms per loop

In [48]: timeit crop_new(a) # modified Divakar's solution for n-dimensions
100 loops, best of 3: 1.91 ms per loop

---

旧解决方案

您可以使用np.nonzero获取数组的索引。此数组的边界框完全包含在索引的最大和最小值中。

---

def _get_slice_bbox(arr):
    nonzero = np.nonzero(arr)
    return [(min(a), max(a)+1) for a in nonzero]

def crop(arr):
    slice_bbox = _get_slice_bbox(arr)
    return arr[[slice(*a) for a in slice_bbox]]

例如。

>>> img = np.array([[  0,   0,   0,   0,   0,   0,   0,   0],
                    [  0,   0,   0,   0,   0,   0,   0,   0],
                    [  0,   0, 175,   0,   0,   0,  71,   0],
                    [  0,   0,   0,  12,   8,  54,   0,   0],
                    [  0,   0,   0,   0, 255,   0,   0,   0],
                    [  0,   0,   0,   2,   0,   0,   0,   0],
                    [  0,   0,   0,   0,   0,   0,   0,   0],
                    [  0,   0,   0,   0,   0,   0,   0,   0]],  dtype='uint8')
>>> print crop(img)
[[175   0   0   0  71]
 [  0  12   8  54   0]
 [  0   0 255   0   0]
 [  0   2   0   0   0]]

- dROOOze

---

请注意，如果您想扩展此功能以支持彩色图像，则必须找出颜色通道的位置，然后适当地进行切片。目前，此解决方案不完全支持彩色图像。 - dROOOze

这正是我所需要的，谢谢！事实上，我甚至可以使用每像素1位的图像。 - Chupo_cro

我已经更新了我的答案，使用opencv方法编写了一个更简单的函数，可能比基于numpy的方法更快。 - fireant

Answer 2

我们可以使用argmax方法获取开始、结束行和列的索引，正如在此帖子中详细讨论的那样。我们还打算使用布尔数组/掩码进行高效处理。因此，使用这些工具/思想，我们将有一个向量化的解决方案，像这样 -

def remove_black_border(a): 
    # Mask of non-zeros
    mask = a!=0 # Use a >tolerance for a tolerance defining black border

    # Mask of non-zero rows and columns
    mask_row = mask.any(1)
    mask_col = mask.any(0)

    # First, last indices among the non-zero rows
    sr0,sr1 = mask_row.argmax(), len(mask_row) - mask_row[::-1].argmax()

    # First, last indices among the non-zero columns
    sc0,sc1 = mask_col.argmax(), len(mask_col) - mask_col[::-1].argmax()

    # Finally slice along the rows & cols with the start and stop indices to get 
    # cropped image. Slicing helps for an efficient operation.
    return a[sr0:sr1, sc0:sc1]

示例运行 -

In [56]: a # Input image array
Out[56]: 
array([[  0,   0,   0,   0,   0,   0,   0,   0],
       [  0,   0,   0,   0,   0,   0,   0,   0],
       [  0,   0,   0,   0,   0,   0,   0,   0],
       [  0,   0,   0, 175,   0,   0,   0,  71],
       [  0,   0,   0,   0,  12,   8,  54,   0],
       [  0,   0,   0,   0,   0, 255,   0,   0],
       [  0,   0,   0,   0,   0,   0,   0,   0],
       [  0,   0,   0,   0,   2,   0,   0,   0],
       [  0,   0,   0,   0,   0,   0,   0,   0],
       [  0,   0,   0,   0,   0,   0,   0,   0]])

In [57]: out = remove_black_border(a)

In [58]: out
Out[58]: 
array([[175,   0,   0,   0,  71],
       [  0,  12,   8,  54,   0],
       [  0,   0, 255,   0,   0],
       [  0,   0,   0,   0,   0],
       [  0,   2,   0,   0,   0]])

内存效率：

输出是对输入数组的视图，因此不需要额外的内存或复制，这有助于提高内存效率。让我们验证一下视图部分 -

In [59]: np.shares_memory(a, out)
Out[59]: True

大图上使用所有提议方法的时间

In [105]: # Setup for 1000x1000 2D image and 100 offsetted boundaries all across
     ...: np.random.seed(0)
     ...: a = np.zeros((1000,1000),dtype=np.uint8)
     ...: a[100:-100,100:-100] = np.random.randint(0,255,(800,800),dtype=np.uint8)

In [106]: %timeit crop_fast(a) # @fireant's soln
     ...: %timeit crop(a)      # @droooze's soln
     ...: %timeit remove_black_border(a) # from this post
100 loops, best of 3: 4.58 ms per loop
10 loops, best of 3: 127 ms per loop
10000 loops, best of 3: 155 µs per loop

- Divakar

---

感谢指出更快的方法，我根据您的方法添加了一个新的解决方案来处理n维度，应该能够处理图像堆栈。 - dROOOze

当我上次看到答案时，fireant的回答是最快的，我只想将其标记为解决方案，但现在似乎你的解决方案是最快的，而且drooze根据你的答案更新了他的答案。现在我不确定要将哪个答案标记为解决方案:-/此外，我现在才意识到如果有“提取子数组的坐标信息”，我的程序可能会受益。我不确定是否应该发布一个新问题，加入这个要求（提取子数组并返回其在原始数组中的坐标）或不:-/ - Chupo_cro

@Chupo_cro，我猜您可以发布一个新问题，详细说明“提取的子数组坐标信息”的部分。 - Divakar

Answer 3

更新 使用opencv函数的这种简单方法实际上更快，可能比其他答案中提出的方法更快。

def crop_fastest(arr):
    return cv2.boundingRect(cv2.findNonZero(arr))

这将返回边界框的x、y、宽度和高度。对于我的旧代码，在我的台式电脑上1000 loops, best of 3: 562 µs per loop，而对于这个新代码10000 loops, best of 3: 179 µs per loop。

另外，正如Chupo_cro指出的那样，简单调用cv2.boundingRect(arr)会返回相同的结果，这似乎是由于此函数中的代码在内部进行了转换。

可能有更快的方法来实现这个功能。这个更简单的函数略微更快一些。

from scipy import ndimage
def crop_fast(arr):
    slice_x, slice_y = ndimage.find_objects(arr>0)[0]
    return arr[slice_x, slice_y]

为了比较 droooze 的代码和本代码的速度，

arr = np.zeros(shape=(50000,6), dtype=np.uint8)
arr[2] = [9,8,0,0,1,1]
arr[1] = [0,3,0,0,1,1]

然后在我的笔记本电脑上，%timeit crop(arr) 返回 1000 loops, best of 3: 1.62 ms per loop，%timeit crop_fast(arr) 返回 1000 loops, best of 3: 979 µs per loop。也就是说，crop_fast() 的速度大约是 crop() 的60%。

- fireant

---

上次看到问题答案时，你的答案是最快的，我只是想将其标记为解决方案，但现在似乎Divakar的解决方案更快，并且drooze基于Divakar的答案更新了他的答案。现在我不确定该标记哪个答案为解决方案 :-/ - Chupo_cro

@Chupo_cro 我更新了我的答案，这可能是最快的代码，你可以在自己的数据上尝试一下，看看是否如此。 - fireant

我尝试使用cv2.boundingRect(arr)而不是cv2.boundingRect(cv2.findNonZero(arr))，结果也正确 - 这怎么可能？ findNonZero(arr)返回非零像素的坐标列表，用arr替换它竟然得到相同的结果 :-O cv2.boundingRect()期望一个点集，但即使传递数组而不是点集，一切都能正常工作。 - Chupo_cro

@Chupo_cro 你说得对，我刚刚检查了一下，这让我感到惊讶。我试图快速查看代码并了解为什么会这样。看起来是这个函数进行了转换。 - fireant

我刚刚使用OpenCV 2.4.12 进行了检查，发现 cv2.boundingRect(arr) 无法正常工作，这意味着后来添加了自动转换。在早期版本的OpenCV中，只有 cv2.boundingRect(cv2.findNonZero(arr)) 可以正常工作。 - Chupo_cro