Нахождение кластеров массы в матрице / растровом изображении

Question

Это продолжение вопроса, размещенного здесь: Нахождение центра масс на двумерном растровом изображении , в котором говорилось о нахождении центра масс в булевой матрице, в качестве примера.

Предположим, теперь мы расширяем матрицу до этой формы:

0 1 2 3 4 5 6 7 8 9
1 . X X . . . . . .
2 . X X X . . X . .
3 . . . . . X X X .
4 . . . . . . X . .
5 . X X . . . . . .
6 . X . . . . . . .
7 . X . . . . . . .
8 . . . . X X . . .
9 . . . . X X . . .

Как видите, теперь у нас есть 4 центра масс для 4 различных кластеров.

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

Каким может быть хороший, правильный и быстрый алгоритм для нахождения этих скоплений массы?

Answer 1

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

Вот код Python, который я собрал вместе, чтобы попытаться проиллюстрировать подход для определения массы для каждой точки. Некоторые настройки с использованием вашего примера матрицы:

matrix = [[1.0 if x == "X" else 0.0 for x in y] for y in """.XX......
.XXX..X..
.....XXX.
......X..
.XX......
.X.......
.X.......
....XX...
....XX...""".split("\n")]

HEIGHT = len(matrix)
WIDTH = len(matrix[0])
Y_RADIUS = HEIGHT / 2
X_RADIUS = WIDTH / 2

Чтобы рассчитать массу для данной точки:

def distance(x1, y1, x2, y2):
  'Manhattan distance http://en.wikipedia.org/wiki/Manhattan_distance'
  return abs(y1 - y2) + abs(x1 - x2)

def mass(m, x, y):
  _mass = m[y][x]
  for _y in range(max(0, y - Y_RADIUS), min(HEIGHT, y + Y_RADIUS)):
    for _x in range(max(0, x - X_RADIUS), min(WIDTH, x + X_RADIUS)):
      d = max(1, distance(x, y, _x, _y))
      _mass += m[_y][_x] / (d * d)
  return _mass

Примечание: я использую Манхэттен расстояния (он же Cityblock, он же Taxicab Geometry), потому что я не думаю, что дополнительная точность с использованием евклидовых расстояний стоит затрат на вызов sqrt ().

Итерация по нашей матрице и создание списка кортежей, таких как (x, y, mass (x, y)):

point_mass = []
for y in range(0, HEIGHT):
  for x in range(0, WIDTH):
    point_mass.append((x, y, mass(matrix, x, y)))

Сортировка списка по массе для каждой точки:

from operator import itemgetter
point_mass.sort(key=itemgetter(2), reverse=True)

Глядя на первые 9 пунктов в этом отсортированном списке:

(6, 2, 6.1580555555555554)
(2, 1, 5.4861111111111107)
(1, 1, 4.6736111111111107)
(1, 4, 4.5938888888888885)
(2, 0, 4.54)
(4, 7, 4.4480555555555554)
(1, 5, 4.4480555555555554)
(5, 7, 4.4059637188208614)
(4, 8, 4.3659637188208613)

Если бы мы работали от наивысшего к низшему и отфильтровали точки, которые слишком близки к уже замеченным точкам, мы получим (я делаю это вручную, так как у меня сейчас мало времени, чтобы сделать это в коде). .):

(6, 2, 6.1580555555555554)
(2, 1, 5.4861111111111107)
(1, 4, 4.5938888888888885)
(4, 7, 4.4480555555555554)

Это довольно интуитивный результат, если смотреть на вашу матрицу (обратите внимание, что при сравнении с вашим примером координаты равны нулю).

Answer 2

Вам нужен алгоритм кластеризации, это легко, поскольку у вас есть двумерная сетка, а записи граничат друг с другом. Вы можете просто использовать алгоритм заливки . После того, как у вас есть каждый кластер, вы можете найти центр, как в 2D центре массовых товаров.

Answer 3

Вот аналогичный вопрос с не очень быстрым алгоритмом и несколькими другими лучшими способами сделать это.

Answer 4

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

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

EDIT:

Непересекающиеся множества (с использованием сжатия пути и объединения по рангу) могут быть полезны здесь. Они имеют O ( & alpha; ( n )) сложность времени для объединения и поиска-набора, где

& alpha; ( n ) = min { k : A _k (1) & ge; n }.

A _k ( n ) - это функция Аккермана, поэтому & alpha; ( n ) будет по существу, будет O (1) для любых разумных значений. Единственная проблема заключается в том, что непересекающиеся наборы являются односторонним отображением элемента для установки, но это не имеет значения, если вы собираетесь использовать все элементы.

Вот простой скрипт на python для демонстрации:

from collections import defaultdict

class DisjointSets(object):
    def __init__(self):
        self.item_map = defaultdict(DisjointNode)

    def add(self,item):
        """Add item to the forest."""
        # It's gets initialized to a new node when
        # trying to access a non-existant item.
        return self.item_map[item]

    def __contains__(self,item):
        return (item in self.item_map)

    def __getitem__(self,item):
        if item not in self:
            raise KeyError
        return self.item_map[item]

    def __delitem__(self,item):
        del self.item_map[item]

    def __iter__(self):
        # sort all items into real sets
        all_sets = defaultdict(set)
        for item,node in self.item_map.iteritems():
            all_sets[node.find_set()].add(item)
        return all_sets.itervalues()

class DisjointNode(object):
    def __init__(self,parent=None,rank=0):
        if parent is None:
            self.parent = self
        else:
            self.parent = parent
        self.rank = rank

    def union(self,other):
        """Join two sets."""
        node1 = self.find_set()
        node2 = other.find_set()
        # union by rank
        if node1.rank > node2.rank:
            node2.parent = node1
        else:
            node1.parent = node2
            if node1.rank == node2.rank:
                node2.rank += 1
        return node1

    def find_set(self):
        """Finds the root node of this set."""
        node = self
        while node is not node.parent:
            node = node.parent
        # path compression
        root, node = node, self
        while node is not node.parent:
            node, node.parent = node.parent, root
        return root

def find_clusters(grid):
    disj = DisjointSets()
    for y,row in enumerate(grid):
        for x,cell in enumerate(row):
            if cell:
                node = disj.add((x,y))
                for dx,dy in ((-1,0),(-1,-1),(0,-1),(1,-1)):
                    if (x+dx,y+dy) in disj:
                        node.union(disj[x+dx,y+dy])
    for index,set_ in enumerate(disj):
        sum_x, sum_y, count = 0, 0, 0
        for x,y in set_:
            sum_x += x
            sum_y += y
            count += 1
        yield 1.0 * sum_x / count, 1.0 * sum_y / count

def main():
    grid = [[('.' != cell) for cell in row if not cell.isspace()] for row in (
        ". X X . . . . . .",
        ". X X X . . X . .",
        ". . . . . X X X .",
        ". . . . . . X . .",
        ". X X . . . . . .",
        ". X . . . . . . .",
        ". X . . . . . . .",
        ". . . . X X . . .",
        ". . . . X X . . .",
    )]
    coordinates = list(find_clusters(grid))
    centers = dict(((round(x),round(y)),i) for i,(x,y) in enumerate(coordinates))
    for y,row in enumerate(grid):
        for x,cell in enumerate(row):
            if (x,y) in centers:
                print centers[x,y]+1,
            elif cell:
                print 'X',
            else:
                print '.',
        print
    print
    print '%4s | %7s %7s' % ('i','x','y')
    print '-'*22
    for i,(x,y) in enumerate(coordinates):
        print '%4d | %7.4f %7.4f' % (i+1,x,y)

if __name__ == '__main__':
    main()

Выход:

. X X . . . . . .
. X 3 X . . X . .
. . . . . X 4 X .
. . . . . . X . .
. X X . . . . . .
. 2 . . . . . . .
. X . . . . . . .
. . . . X X . . .
. . . . X 1 . . .

   i |       x       y
----------------------
   1 |  4.5000  7.5000
   2 |  1.2500  4.7500
   3 |  1.8000  0.6000
   4 |  6.0000  2.0000

Смысл этого состоял в том, чтобы продемонстрировать непересекающиеся множества. Фактический алгоритм в find_clusters() может быть обновлен до более надежного.

Ссылки

• Введение в алгоритмы. 2-е изд. Cormen et.al.