공의 파이썬 이미지 처리

Question

나는 알고리즘의 문제에 직면하고있다. 문제는 다음과 같습니다. 공의 이미지가 있습니다. 배열을 분석하여 수행되었습니다. 꽤 많이 이런 것 같습니다 :

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

알고리즘을 사용하여 볼의 중심 (approximativly)을 어떻게 찾을 수 있습니까? 그리고 다음과 같이 표시 :

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

나는 긴 줄의 너비와 높이와 같은 것을 사용하려고 생각하고있었습니다. 높이에 대한

:

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) 

하지만 트릭을 할해야 대중의 공의 중심을 계산

Answer 1

.. 거기에서 내가 아는하지 않습니다. 기본적으로 볼의 일부인 모든 픽셀의 좌표 평균입니다. 이것은 깔끔하게 분해되므로 x와 y의 평균을 개별적으로 계산할 수 있습니다. 이 라인을 따라 뭔가 :

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 및 j보다 명확 때문에 나는 x 여기 y를 사용하고 맛을 조정합니다..)

Answer 2

당신의 이미지가 빨간색 크고 경우 영역이 다소 작습니다. floodfill 알고리즘을 사용하면 성능이 향상됩니다. 단일 빨간색 픽셀을 발견하면 floodfill을 시작합니다. 시간 비용은 공 영역 크기에 비례합니다.

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)