Python中从二进制掩模快速提取轮廓掩模的方法

Question

Python中从二进制掩模快速提取轮廓掩模的方法

3

我希望制作一个实时应用程序，其中涉及到找到二进制掩模的边缘。如果可能的话，我需要一些快速的东西，没有GPU，每张图像运行时间希望低于0.0005秒，大小为（1000,1000）。我将使用以下示例二进制图像，大小为（1000,1000）。

（复制代码：）

import numpy as np
im=np.zeros((1000,1000),dtype=np.uint8)
im[400:600,400:600]=255

图片

快速处理事务的第一种逻辑方式是使用OpenCV库：

import cv2
timeit.timeit(lambda:cv2.Laplacian(im,cv2.CV_8U),number=100)/100
0.0011617112159729003

如预期所示，结果如下：拉普拉斯

我发现这种方法非常耗时。之后我尝试使用findContours：

 def usingcontours(im):
    points=np.transpose(cv2.findContours(im,cv2.RETR_TREE,cv2.CHAIN_APPROX_NONE)[1][0])
    tmp=np.zeros_like(im)
    tmp[tuple(points)]=255
    return tmp 
timeit.timeit(lambda:usingcontours(im),number=100)/100
0.0009052801132202148

这次的结果与之前相同。虽然这已经比之前好了，但仍不如我所希望的那样好。我转而使用numpy来近似拉普拉斯算子，使用梯度作为最后的手段，尽管我知道这样的效果会更差：

def usinggradient(im):
    tmp=np.gradient(im)
    return ((tmp[0]+tmp[1])>0).astype(np.uint8)
timeit.timeit(lambda:usinggradient(im),number=100)/100
0.018681130409240722

那么，有没有人对如何加速我的算法有进一步的想法？我强调我希望这个算法用于二进制图像，所以我猜肯定有更好的实现方法。

- Vasilis Lemonidis

你可以使用一些NumPy和Scipy形态学腐蚀和位运算来完成这个任务。请查看scipy.ndimage.morphology.binary_dilation和np.logical_*函数。 - YXD

1000 x 1000 / 0.0005秒 = 每秒2 x 10^9像素 -- 这意味着每个像素只能使用1-2个时钟周期，即使进行向量化和并行化也没有太多可操作的余地。 - Dan Mašek

@DanMašek 2 x 10^9像素/秒意味着对于一个位图图像，是2x10^9比特/秒。假设一个良好的程序利用了所有核心，我相信这是可能的，在一个8核2GHz的CPU中，每个核心有4个线程，我可以在每个时钟周期处理32像素（位），因此64*10^9像素/秒= 1000 x 1000 / 0.00016秒。因此，我正在寻找任何具有低于O(3 * n)复杂度的现成实现，在二进制图像中我相信这是可能的。 - Vasilis Lemonidis

timeit.timeit(lambda:im+1,number=100)/100 给出了 8.358001708984375e-05 秒，所以比我想象的要好，我需要一个复杂度小于 O(4*n) 的算法。 - Vasilis Lemonidis

1个回答

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

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

- Divakar · Accepted Answer

我选择了最快的方法cv2.findContours来提高速度。在它里面，我们可以用简单的切片代替那些昂贵的transpose和转换为元组的部分，像这样 -

idx = cv2.findContours(im,cv2.RETR_TREE,cv2.CHAIN_APPROX_NONE)[1][0]
out = np.zeros_like(im)
out[idx[:,0,0],idx[:,0,1]] = 255

运行时测试 -

In [114]: # Inputs
     ...: im=np.zeros((1000,1000),dtype=np.uint8)
     ...: im[400:600,400:600]=255
     ...: idx = cv2.findContours(im,cv2.RETR_TREE,cv2.CHAIN_APPROX_NONE)[1][0]
     ...: 

In [115]: def original_app(im, idx):
     ...:     points=np.transpose(idx)
     ...:     tmp=np.zeros_like(im)
     ...:     tmp[tuple(points)]=255
     ...:     return tmp
     ...: 
     ...: def proposed_app(im, idx):
     ...:     out = np.zeros_like(im)
     ...:     out[idx[:,0,0],idx[:,0,1]] = 255
     ...:     return out
     ...: 

In [120]: %timeit original_app(im, idx)
10000 loops, best of 3: 108 µs per loop

In [121]: %timeit proposed_app(im, idx)
10000 loops, best of 3: 101 µs per loop

In [122]: %timeit cv2.findContours(im,cv2.RETR_TREE,cv2.CHAIN_APPROX_NONE)
1000 loops, best of 3: 1.55 ms per loop

所以，提议的方法有一些边角改进，但与轮廓发现本身相比似乎微不足道。

我研究了scikit-image版本，并进行了快速测试，看起来比OpenCV版本慢得多。