4

我想计算二进制 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. 至少对于大图像，这要快得多。在明显没有外部解决方案的情况下，我将其定位为该问题的解决方案。

不过，如果有人知道更快的方法，请说出来:)

4

3 回答 3

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
于 2009-11-12T11:41:43.227 回答
0

对于更通用的解决方案，您可以使用某种边缘检测方法来仅找到边缘点。我相信（Google..）NumPy 有内置的 sobel 过滤器，可以做到这一点。

于 2009-10-21T21:24:00.980 回答
0

这个任务似乎完成了与你最后两个步骤相同的事情：

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

不过，不知道会不会更快。

于 2009-10-21T17:22:54.977 回答