image processing python of a ball

Question

I'm facing a problem of algorithm. Here's the thing : I've got an image of a ball, it was done by analysing a array. It's pretty much something like this :

      ....####......
      .##########....
   ...############.....
      .##########....
      ....####......

How do i found the center of the ball (approximativly) with an algorithm ? And displaying something like this :

      ....####......
      .##########....
   ...#####0######.....
      .##########....
      ....####......

I was thinking of using something like the width of the longer line of # and the height.

for the height :

k = 0
for i in range (0, 10) :
for j in range (0, 20) :
# if one line contain a # then k = k+1 
center = (k/2)

but i don't know from there ..

Answer 1

Computing the ball's centre of mass should do the trick. Basically, it's the average of the coordinates of all pixels that are part of the ball. This neatly decomposes so you can compute the average for x and y separately. Something along these lines:

sum_x = 0
sum_y = 0
count = 0
for x in range(0, 10):
  for y in range(0, 20):
    if image[x][y] == '#':
      sum_x += x
      sum_y += y
      count += 1
centre_x = sum_x / count # this will truncate; round or use float if you want
centre_y = sum_y / count

(I'm using x and y here because their meaning is clearer than i and j. Adjust to taste.)

Answer 2

If your image is large and the red area is rather small, using floodfill algorithm will have better performance. Once you found a single red pixel, you start floodfill, it's time cost will just porportional to the ball area size.

from collections import deque
def floodfill(x0, y0,  is_red):
    # here is_red is a function to judge if is_red(x, y)
    que = deque()
    inque = set()
    que.append((x0, y0))
    D = ((-1, 0), (1, 0), (0, -1), (0, 1))
    sumx, sumy = 0, 0
    cnt = 0
    while que:
        x, y = que.popleft()
        sumx += x
        sumy += y
        cnt += 1
        for dx, dy in D:
            x1 = x + dx
            y1 = y + dy
            if is_red(x1, y1) and (x1, y1) not in inque:
                que.append((x1, y1))
                inque.add((x1, y1))
    return sumx/cnt, sumy/cnt

def find_center(img):
    size = img.size()
    def is_red(x, y):
        # you may change the judge condition by your self
        return img[x, y] == '#'
    for x in xrange(size[0]):
        for y in xrange(size[1]):
            if is_red(x, y):
                return floodfill(x, y, is_red)