Finding a specific index in a binary image in linear time?

boolean, image-processing, numpy, python, python-imaging-library

Solution

This code will find the centroid of any shaped image. It will find it exactly for `rez = 1`. Increasing `rez`, increases the grid spacing, so can massively increase the speed of the search, at the obvious cost of the accuracy. If the size of the blob is known within bounds you could chain a low `rez` search, with a high `rez` search, thus finding the answer quickly and 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

for example, with the below image:

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

Timing with `timeit` the first option (which is linear time, `O(n)`) has a run time of `1.7s`, and the second `0.005s`.

You can't do better than `O(n)` to find an exact answer, unless you have some constraints on size and shape. But, you can sacrifice accuracy for speed. The above code is `O(n/(rez ** 2))`, which can be a massive improvement. The accuracy of reported results is: `± rez / 2`, in each dimension.

Update:

`sega_sai` wrote a nice piece of `numpy` code (see post below) to find the centroid. I've modified it to take advantage of grid spacing, by using slicing. It operates in the same fashion as above:

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

Here are graphed `timeit` results for these two functions over a span of `rez` values:

Its a log graph, so it really illustrates the advantage of combining the two approaches.

This is the image I used for the tests:

Problem

I've got a 640x480 binary image (0s and 255s). There is a single white blob in the image (nearly circular) and I want to find the centroid of the blob (it's always convex). Essentially, what we're dealing with is a 2D boolean matrix. I'd like the runtime to be linear or better if possible - is this possible? Two lines of thought so far: - Make use of the `numpy.where()` function - Sum the values in each column and row, then find where the max value is based on those numbers... but is there a quick and efficient way to do this? This might just be a case of me being relatively new to python.

Original source