Более быстрый способ найти центроиды областей пикселей - PullRequest
Новая
       12

Более быстрый способ найти центроиды областей пикселей

1 голос
/ 23 апреля 2019

Для игры я создал карту территорий, состоящую из пикселей, причем каждая территория имела свой цвет.Оттуда я хочу добавить имена на каждой территории.

Для наглядности я хочу поместить имена в центр тяжести области.Поэтому я использовал PIL для преобразования изображения в одну большую матрицу.Я построил класс для записи данных центроидов каждой территории, собранных в словаре.Затем я перебираю пиксели для обработки центроида.Этот метод очень медленный и занимает около минуты для карты 2400 x 1100. 

territory_map = numpy.array([
    [0, 0, 0, 1, 0, 0, 0],
    [0, 2, 2, 1, 0, 0, 0],
    [2, 2, 1, 1, 3, 3, 3],
    [2, 0, 0, 1, 3, 0, 0],
])

centroid_data = {}

class CentroidRecord(object):
    def __init__(self, x, y):
        super(CentroidRecord, self).__init__()
        self.x = float(x)
        self.y = float(y)
        self.volume = 1

    def add_mass(self, x, y):
        #           new_x = (old_x * old_volume + x) / (old_volume + 1),
        # therefore new_x = old_x + (x - old_x) / v,
        # for v = volume + 1.
        self.volume += 1
        self.x += (x - self.x) / self.volume
        self.y += (y - self.y) / self.volume


for y in range(territory_map.shape[0]):
    for x in range(territory_map.shape[1]):
        cell = territory_map[y][x]
        if cell == 0:
            continue
        if cell not in centroid_data:
            centroid_data[cell] = CentroidRecord(x, y)
        else:
            centroid_data[cell].add_mass(x, y)

for area in centroid_data:
    data = centroid_data[area]
    print(f"{area}: ({data.x}, {data.y})")

Это должно напечатать следующее: 

1: (2.8, 1.6)
2: (0.8, 1.8)
3: (4.75, 2.25)

Есть ли более быстрый способ сделать это?

1 Ответ

0 голосов
/ 23 апреля 2019

Каждая координата центроида для цвета является просто средним значением всех координат точек этого цвета. Соответственно, мы можем использовать dict понимание: 

import numpy as np

n_colours = territory_map.max()

{i: tuple(c.mean() for c in np.where(territory_map.T == i)) 
 for i in range(1, n_colours + 1)}

Выход: 

{1: (2.8, 1.6), 
 2: (0.8, 1.8), 
 3: (4.75, 2.25)}

Обратите внимание, что нам нужно взять транспозицию, потому что строки (координата y) идут перед столбцами (координата x) в numpy.

Время, затраченное на случайно сгенерированные данные: 

81.6 ms ± 5.36 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
...