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）的凸包，必须是这些点（轮廓）的一个子集。换句话说，如果“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。至少在处理大图像时，这个方法明显更快。在没有外部解决方案的情况下，我把这个方法作为这个问题的解决方案。

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

Answer 1

如果想要更通用的解决方案，可以使用某种边缘检测的方法来只找到边缘点。我相信（可以在谷歌上查）NumPy里面有一个内置的索贝尔滤波器，它可以做到这一点。

Answer 2

这个任务看起来和你之前的两个步骤做的事情是一样的：

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

不过我不确定这样做是否更快。

Answer 3

由于没有找到合适的答案，我把我能用的最好代码发上来，作为解决方案。

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