4

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

到目前为止的两条思路：

  1. 使用numpy.where()功能
  2. 对每一列和每一行的值求和，然后根据这些数字找到最大值的位置......但是有没有一种快速有效的方法来做到这一点？这可能只是我对 python 比较陌生的一个例子。
4

4 回答 4

6

此代码将找到任何形状图像的质心。它会准确地找到它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：

在此处输入图像描述

它是一个日志图，因此它真正说明了结合这两种方法的优势。

这是我用于测试的图像：

在此处输入图像描述

于 2012-05-02T08:57:15.823 回答
2

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

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

于 2012-05-02T08:03:44.470 回答
2

这段代码：

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

fraxel 提供的 640x480 图片需要 10 毫秒

于 2012-05-02T16:59:04.147 回答
1

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

将其降低到 1/10 分辨率，找到一个白色像素，然后您就可以准确了解在哪里搜索质心。

于 2012-05-02T07:50:30.707 回答