在线性时间内找到二进制图像中的特定索引？

我有一个640x480的二进制图像（0s和255s）。图像中有一个白色斑点（接近圆形），我想找到斑点的质心（它总是凸起的）。基本上，我们正在处理的是一个2D布尔矩阵。如果可能，我希望运行时间线性或更好 - 这可能吗？思想在线性时间内找到二进制图像中的特定索引？

两行至今：

利用numpy.where()功能
总和的每一列和行的值，然后找到其中的最大值是基于这些数字......但有没有一种快速有效的方法来做到这一点？这可能只是我对python相对陌生的一个例子。

来源

2012-05-02 FreakinOutMan

你见过[OpenCV的]（http://opencv.willowgarage.com/wiki/）呢？ Python绑定是可用的，因为它在一些重要的地方使用，我希望现在可以合理地优化它。 – sarnold

+1对于Opencv来说，对于像这样的简单成就，你自己不会做得更好（轻松^^） – jlengrand

质心检测需要的精度是多少？并且是已知的斑点的大小？ – fraxel

此代码将查找任何形状图像的质心。它会准确找到rez = 1。增加rez，增加了网格间距，因此可以大幅度提高搜索速度，而且精确度明显降低。如果斑的大小范围内已知的，你可以链接一个低rez搜索，高rez搜索，从而找到了答案，迅速pricesely

import Image 

def find_centroid_faster(im, rez): 
    width, height = im.size 
    XX, YY, count = 0, 0, 0 
    for x in xrange(0, width, rez): 
     for y in xrange(0, height, rez): 
      if im.getpixel((x, y)) == 255: 
       XX += x 
       YY += y 
       count += 1 
    return XX/count, YY/count

例如，与下面的图片：

im = Image.open('blob.png') 
print find_centroid(im, 1) 
print find_centroid(im, 20) 
#output: 
(432, 191) 
(430, 190)

与timeit定时的第一个选项（它是线性时间，O(n)）的运行时间为1.7s，第二个为0.005s。

除非您对尺寸和形状有一些限制，否则您无法比O(n)更好地找到确切的答案。但是，你可以牺牲速度的准确性。上面的代码是O(n/(rez ** 2))，这可以是一个巨大的改进。报告结果的准确性为：± rez/2，在每个维度。

更新：

sega_sai写了一件漂亮的numpy代码（见后下）找到重心。我已经通过使用切片修改它以利用网格间距。它上面的操作相同的方式：

def find_centroid_faster_numpy(im,rez): 
        h, w = im.size 
        arr = np.array(im) 
        arr_rez = arr[::rez,::rez] 
        ygrid, xgrid  = np.mgrid[0:w:rez, 0:h:rez] 
        xcen, ycen = xgrid[arr_rez == 255].mean(), ygrid[arr_rez == 255].mean() 
        return xcen, ycen

这里作图timeit结果这两个功能在rez值跨度：

enter image description here

其日志图形，所以它确实说明结合这两种方法的优点。

这是我用于测试的图像：

enter image description here

来源

2012-05-02 08:57:15 fraxel

我会用'for'：'for xrange（0，width，rez）：'替换那些'while'循环。 –

@Mark Ransom - 非常感谢，我以为我错过了一些东西！ – fraxel

这是所有伟大的建议，非常感谢！ – FreakinOutMan

根据你的blob的大小，我会说大幅度降低图像的分辨率可能会达到你想要的。

将其降至1/10分辨率，找到一个白色像素，然后您就可以精确地了解在何处搜索质心。

来源

2012-05-02 07:50:30 jlengrand

无需对整个图像进行缩减采样，只需对其进行采样即可。例如，读取10条等距垂直线，如果没有这些线与斑点相交，则再乘10，依此类推。 –

是的，只要blob的形状不太令人毛骨悚然，你是对的。在这种情况下，我仍然会对下采样进行投票。 – jlengrand

质心的坐标是点的坐标的算术平均值。如果您想要线性解决方案，只需逐个像素，并计算每个坐标的平均值，其中像素为白色，这就是质心。

在一般情况下，你可能没有办法使它比线性更好，但是，如果你的圆形对象比图像小得多，你可以通过先搜索它来加速它（抽样一些随机数像素或像素网格，如果您知道blob足够大），然后使用BFS或DFS查找所有白点。

来源

2012-05-02 08:03:44

此代码：

import Image, numpy as np 
def getBlobCenter(imname): 
     im = Image.open(imname) 
     w, h = im.size 
     arr = np.array(im) 
     xgrid, ygrid = np.mgrid[0:w, 0:h] 
     xcen, ycen = xgrid[arr == 255].mean(), ygrid[arr == 255].mean() 
     return xcen, ycen

需要10毫秒由飞梭提供640×480的图片

来源

2012-05-02 16:59:04

+1美丽而优秀！ – fraxel

在线性时间内找到二进制图像中的特定索引？

回答

相关问题