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

Question

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:

1. Make use of the numpy.where() function
2. 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.

Answer 1

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:

Answer 2

The centroid's coordinates are arithmetic means of coordinates of the points. If you want the linear solution, just go pixel by pixel, and count means of each coordinates, where the pixels are white, and that's the centroid.

There is probably no way you can make it better than linear in general case, however, if your circular object is much smaller than the image, you can speed it up, by searching for it first (sampling a number of random pixels, or a grid of pixels, if you know the blob is big enough) and then using BFS or DFS to find all the white points.