如何计算三维numpy数组中的凸包图像/体积

Question

如何计算三维numpy数组中的凸包图像/体积

pythonscipycomputational-geometryscikit-imageconvex-hull

3

我想知道是否有任何基于numpy的工具可以：

在3D中给定二进制输入numpy图像，找到其凸包；
并返回在此3D凸包内的体素（3D像素）的索引列表或类似内容。

一种可能性是使用skimage.morphology.convex_hull_image()，但是~~它仅支持2D图像，因此我必须逐层调用该函数（在z轴上），这很慢。~~ [编辑：请参见下面的注释。]

我肯定更喜欢更有效的方法。例如，scipy.spatial.ConvexHull()可以获取N维空间中的点列表，并返回一个凸包对象，似乎不支持查找其凸包图像/体积。

points = np.transpose(np.where(image))
hull = scipy.spatial.ConvexHull(points)
# but now wonder an efficient way of finding the list of 3D voxels that are inside this convex hull

有什么想法吗？请注意效率对我的应用很重要。谢谢！

更新：与此同时，convex_hull_image()已经扩展支持ND图像，但对于中等大小的数据来说速度相当慢。下面接受的答案要快得多。

- galactica

1

不是我的专业领域，但scipy.spatial应该是您检查的第一个库（不是numpy，抱歉）。ConvexHull基于Qhull，如果我没记错的话，它似乎是scipy中问题最多的代码部分之一。浏览了一下您的skimage函数代码，它似乎也是基于scipy.spatial！ - sascha

谢谢！是的，scipy.spatial.ConvexHull() 似乎可以正确处理三维点，但如果 skimage.morphology.convex_hull_image() 能够处理三维图像就更好了。不确定其他库在这方面是否更完整。 - galactica

sklearn的函数基于Delaunay而不是ConvexHull。因此，也许有一些潜在的路径可以推广他们的算法。但再次强调：我在这方面并不了解太多，这只是我从查看他们的代码10秒钟后得出的第一印象（同时想知道为什么一个convex_hull函数不使用spatial.ConvexHull，而是使用Delaunay）。备注：我编辑了标签，并牺牲了3d标签来吸引专家。 - sascha

另外，这是一个非常相关的SO问题（再次使用Delaunay）：very relevant SO question (using Delaunay again)，还有其他链接1和其他链接2。编辑：哦，根据第一个链接中更新的答案，scipy可以计算您想要的内容。在此处查看可用属性here。 - sascha

谢谢你的指点，但还不太对。我正在寻找一个在凸包内的点列表，而不仅仅是体积或面积。 - galactica

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel F · Accepted Answer

你应该能够做到这一点：

def flood_fill_hull(image):    
    points = np.transpose(np.where(image))
    hull = scipy.spatial.ConvexHull(points)
    deln = scipy.spatial.Delaunay(points[hull.vertices]) 
    idx = np.stack(np.indices(image.shape), axis = -1)
    out_idx = np.nonzero(deln.find_simplex(idx) + 1)
    out_img = np.zeros(image.shape)
    out_img[out_idx] = 1
    return out_img, hull

虽然不是最快的，但如果没有现成的函数可用，它应该能够工作。

测试：

points = tuple(np.rint(10 * np.random.randn(3,100)).astype(int) + 50)
image = np.zeros((100,)*3)
image[points] = 1

%timeit flood_fill_hull(image)
10 loops, best of 3: 96.8 ms per loop

out, h = flood_fill_hull(image)

plot.imshow(out[50])

无法上传图片，但似乎已经解决了问题。