画像処理ボールのpython

Question

私はアルゴリズムの問​​題に直面しています。ここに事がある：私はボールのイメージを持っている、それは配列を分析することによって行われた。

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

ボールの中心（アルゴリズムの略）は、どのようにして見つけられましたか？

 ....####...... 
     .##########.... 
    ...#####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アルゴリズムを使用するとパフォーマンスが向上します。 1つの赤いピクセルを見つけたら、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)