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

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.

## Answers

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:

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.

This code:

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

takes 10 ms for 640x480 picture provided by fraxel

Depending on the size of your blob, I would say that dramatically reducing the resolution of your image may achieve what you want.

Reduce it to a 1/10 resolution, find the one white pixel, and then you have a precise idea of where to search for the centroid.