Znajdowanie klastrów masy w macierzy/mapie bitowej

Question

Jest to kontynuacja pytania zadanego tutaj: Finding the center of mass on a 2D bitmap, które mówiło o znalezieniu środka masy w macierzy boolowskiej, jak podano przykład.

Załóżmy teraz rozszerzamy matrycę do tego formularza:

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 . . . 

Jak widać mamy teraz 4 ośrodki masowego, dla 4 różnych klastrów.

Już wiemy, jak znaleźć środek masy, biorąc pod uwagę, że tylko jeden istnieje, jeśli uruchomimy ten algorytm na tej macierzy, otrzymamy punkt pośrodku macierzy, która nam nie pomoże.

Jaki może być dobry, prawidłowy i szybki algorytm znajdowania tych skupisk masy?

Answer 1

Myślę, że sprawdziłbym każdy punkt w macierzy i ustaliłam jej masę na podstawie jej sąsiadów. Masa za punkty spadnie z kwadratem odległości. Następnie możesz wybrać cztery najlepsze punkty w minimalnej odległości od siebie.

Oto trochę kodu Pythona, który pobiłem razem, aby zilustrować podejście do znalezienia masy dla każdego punktu. Niektóre konfiguracja za pomocą przykładową macierz:

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 

do obliczania masy dla danego punktu:

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 

Uwaga: Używam Manhattan dystansach (aka Cityblock, aka Taxicab Geometry) tutaj, bo don Uważa się, że dokładność przy użyciu odległości euklidesowych jest warta kosztu wywołania sqrt().

Iterując naszym matrycy budowy wykaz krotki jak (x, y, widmo mas (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))) 

Sortowanie listy na masę dla każdego punktu:

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

Patrząc w górę 9 punktów w tym uporządkowanym wykazie:

(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) 

Jeśli chcemy pracować od najwyższej do najniższej i filte R z dala punktów, które są zbyt blisko już widział punktów dostaniemy (robię to ręcznie odkąd zabrakło czasu, aby to zrobić w kodzie ...):

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

który jest całkiem intuicyjny wynik od samego patrzenia na twoją matrycę (zwróć uwagę, że współrzędne są zerowe w porównaniu do twojego przykładu).

Answer 2

Moja pierwsza myśl to najpierw znaleźć dowolną komórkę o niezerowej wartości. Stamtąd wykonaj algorytm wypełnienia powodzi i obliczyć środek masy znalezionych komórek. Następnie wyzeruj znalezione komórki z macierzy i rozpocznij od góry.

To oczywiście nie skaluje się tak dobrze, jak metoda z Google, która łączy się z linkiem, ale byłaby łatwiejsza do wdrożenia dla mniejszych macierzy.

EDIT:

Disjoint sets (przy użyciu kompresji ścieżki i unii-by-pozycja) może być tu przydatna. Mają O (α (n)) Złożoność unii i znaleźć osadzone, gdzie

α (n) = min {K: A _k (1) ≥ n}.

_K ( n) jest funkcją Ackerman tak α (n) będzie zasadniczo O (1) w odniesieniu do rozsądnych wartości. Jedynym problemem jest to, że zbiory rozłączne to odwzorowanie jednokierunkowe elementu do ustawienia, ale nie ma to znaczenia, jeśli przechodzisz przez wszystkie elementy.

Oto prosty skrypt Pythona do demonstracji:

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() 

wyjściowa:

. 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 

Punktem to było wykazanie rozłącznych zbiorów. Rzeczywisty algorytm w find_clusters() może zostać zaktualizowany do czegoś bardziej niezawodnego.

Referencje

• Wprowadzenie do algorytmów. 2nd ed. Cormen et.al.

Answer 3

Here's podobne pytanie z niezbyt szybkim algorytmem oraz kilka innych lepszych sposobów na zrobienie tego.

Answer 4

Potrzebujesz algorytmu grupowania, jest to łatwe, ponieważ masz tylko dwuwymiarową siatkę, a wpisy sąsiadują ze sobą. Możesz po prostu użyć floodfill algorithm. Po uzyskaniu każdego klastra można znaleźć centrum, tak jak w przypadku 2D center of mass article..