Python 二维矩阵二值化轮廓

Question

我希望能在一个二进制的NxM矩阵中计算出形状的凸包。凸包算法需要一个坐标列表，因此我使用numpy.argwhere(im)获取所有形状点的坐标。然而，大多数这些点并没有对凸包产生贡献（它们位于形状内部）。由于凸包计算时间至少与输入的点数成比例，所以我想到了一个过滤无用点的方法，并且只传递那些跨越轮廓的点。这个想法非常简单，对于二进制NxM矩阵中的每一行，我只取最小和最大的索引。例如：

im = np.array([[1,1,1,0],
              [1,0,1,1],
              [1,1,0,1],
              [0,0,0,0],
              [0,1,1,1]], dtype=np.bool)
outline = somefunc(im)

然后大纲应该以元组或5x2的numpy数组形式呈现（我不介意）：

[(0,0),(0,2),(1,0),(1,3),(2,0),(2,3),(4,1),(4,3)]

任何紧贴在这个形状 (im) 上的凸包，必须是这些点 (outline) 的子集。换句话说，如果 "somefunc()" 能有效地过滤内部点，则可以节省凸包计算时间。

我已经有了实现上述技巧的代码，但我希望有人能提供更聪明（即更快）的方法，因为我需要多次运行它。我拥有的代码如下：

# I have a 2D binary field. random for the purpose of demonstration.
import numpy as np
im = np.random.random((320,360)) > 0.9

# This is my algorithm so far. Notice that coords is sorted.
coords = np.argwhere(im)
left = np.roll(coords[:,0], 1, axis=0) != coords[:,0]
outline = np.vstack([coords[left], coords[left[1:]], coords[-1]])

我有一个想法是使用Python的reduce()函数，这样我只需要遍历一次坐标列表。但我很难找到一个好的缩减函数。

非常感谢您的任何帮助！

编辑

与此同时，我已经找到了一种更快的方法，可以直接从im转换到outline。至少对于大图片来说，这种方法显著更快。在没有外部解决方案的情况下，我将其作为该问题的解决方案。

如果有人知道更快的方法，请告诉我 :)

- Paul

---

"fast" 不是一个非常有用的标签。 - SilentGhost

叹气 我在寻找答案，聪明的家伙。 - Paul

@Paul：抱怨可能是一个好的方法，因为你的问题有些不清楚和无用。如果我们不能理解你的问题（包括标签），我们基本上无法提供帮助。 - S.Lott

到达这里的任何人，请查看此答案：https://dev59.com/m2zXa4cB1Zd3GeqPWbAJ#14223101 - Anoyz

Answer 1

如果没有可接受的答案，我会发布我最好的工作代码作为解决方案。

def outline(im):
    ''' Input binary 2D (NxM) image. Ouput array (2xK) of K (y,x) coordinates
        where 0 <= K <= 2*M.
    '''
    topbottom = np.empty((1,2*im.shape[1]), dtype=np.uint16)
    topbottom[0,0:im.shape[1]] = np.argmax(im, axis=0)
    topbottom[0,im.shape[1]:] = (im.shape[0]-1)-np.argmax(np.flipud(im), axis=0)
    mask      = np.tile(np.any(im, axis=0), (2,))
    xvalues   = np.tile(np.arange(im.shape[1]), (1,2))
    return np.vstack([topbottom,xvalues])[:,mask].T

- Paul

Answer 2

这个任务似乎完成了与您的前两个步骤相同的事情：

outline = np.array(dict(reversed(coords)).items() + dict(coords).items())

不知道它是否更快。

- Skyhawker

---

太糟糕了，它慢了10倍(!)。 - Paul

Answer 3

对于更一般的解决方案，您可以使用某种边缘检测方法来仅查找边缘点。我相信（谷歌..）NumPy具有内置的Sobel滤波器，可以实现这一点。

- Harriv

---

是的，我知道Sobel滤波器，它非常出色。事实上，正是通过它我得到了这些二进制图像。但是该滤波器并不提供索引。 - Paul

该过滤器会为您提供位图/矩阵，您可以在其中找到与您的代码中类似的所有索引。 - Harriv

哦，等等，你得到了带有Sobel算子的示例图像，但它有太多点了？ - Harriv

你说得对。我想在（阈值化的）Sobel周围拟合一个多边形。因此，首先我想要减少点的数量。这最后一部分是我试图寻找快速代码的地方。 - Paul

在我使用的机器视觉应用程序中，Blob工具有轮廓输出，但不幸的是，在OpenCV中我没有发现这样的功能。那本来会是一个优雅的解决方案... - Harriv