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

Question

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

到目前为止有两条思路:

1. 利用这个numpy.where()功能
2. 对每列和每行中的值求和,然后根据这些数字找出最大值的位置......但有一种快速有效的方法吗？这可能只是我对python相对较新的一个例子.

Answer 1

此代码将找到任何形状图像的质心.它会完全找到它rez = 1.增加rez,增加网格间距,因此可以大大提高搜索速度,但成本明显高.如果blob的大小在边界内是已知的,那么你可以rez通过高rez搜索链接低搜索,从而快速找到答案并且价格合理

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值上的图表结果:

它是一个日志图,因此它真实地说明了结合这两种方法的优势.

这是我用于测试的图像: