Encontrar cúmulos de masa en una matriz/mapa de bits

Question

Esto es en continuación con la pregunta publicada aquí: Finding the center of mass on a 2D bitmap que hablaba de encontrar el centro de masa en una matriz booleana, como se muestra en el ejemplo.

Supongamos ahora que ampliar la matriz a esta forma:

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

Como se puede ver que ahora tienen 4 centros de masa, por 4 grupos diferentes.

Ya sabemos cómo encontrar un centro de masa dado que solo existe uno, si ejecutamos ese algoritmo en esta matriz obtendremos un punto en el medio de la matriz que no nos sirve.

¿Cuál puede ser un algoritmo bueno, correcto y rápido para encontrar estos grupos de masa?

Answer 1

Creo que verificaría cada punto de la matriz y descubriría su masa en función de sus vecinos. La masa de los puntos caería con decir el cuadrado de la distancia. A continuación, puede elegir los cuatro puntos superiores con una distancia mínima el uno del otro.

Aquí hay un código de Python que mezclé para intentar ilustrar el enfoque para descubrir la masa de cada punto. Algunos de configuración usando el ejemplo de la matriz:

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 

para calcular la masa de un punto dado:

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 

Nota: Estoy usando Manhattan distancias (aka Cityblock, también conocido como Taxi geometría) aquí porque Don No creo que la precisión añadida usando distancias Euclidianas valga el costo de llamar a sqrt().

Iterar a través de nuestra matriz y la construcción de una lista de tuplas como (x, y, la masa (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))) 

Clasificación de la lista de la masa para cada punto:

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

en cuanto a los 9 puntos superiores en esa lista ordenada:

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

Si hemos de trabajar de mayor a menor y filtrante r distancia puntos que están demasiado cerca de los puntos de visto ya vamos a llegar (lo estoy haciendo manualmente desde que he quedado sin tiempo ahora para hacerlo en código ...):

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

que es un resultado bastante intuitivo al solo mirar su matriz (tenga en cuenta que las coordenadas son cero cuando se compara con su ejemplo).

Answer 2

Mi primer pensamiento sería encontrar primero una celda con un valor distinto de cero. A partir de ahí, realice un algoritmo de llenado de inundación y calcule el centro de masa de las células encontradas. Luego, ponga a cero las celdas encontradas de la matriz y comience nuevamente desde arriba.

Esto, por supuesto, no se escalaría tan bien como el método de Google, que tuinstoel vinculado, pero sería más fácil de implementar para matrices más pequeñas.

EDIT:

Disjoint sets (usando compresión de caminos y la unión por rango) podría ser útil aquí. Tienen O (α (n)) complejidad del tiempo para la unión y encontrar-set, donde

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

A _k (n) es la función de Ackerman, por lo α (n) será esencialmente O (1) para cualquier valor razonables. El único problema es que los conjuntos disjuntos son un mapeo unidireccional del elemento a establecer, pero esto no importará si vas a atravesar todos los elementos.

Aquí es un simple script en Python para la demostración:

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

Salida:

. 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 

El punto de esto era demostrar conjuntos disjuntos. El algoritmo real en find_clusters() podría actualizarse a algo más robusto.

Referencias

• Introducción a los algoritmos. 2nd ed. Cormen et.al.

Answer 3

Here's una pregunta similar con un algoritmo no tan rápido, y varias otras formas mejores de hacerlo.

Answer 4

Necesita un algoritmo de agrupamiento, esto es fácil ya que solo tiene una cuadrícula bidimensional, y las entradas están bordeando entre sí. Solo puede usar un floodfill algorithm. Una vez que tenga cada clúster, puede encontrar el centro como en el 2D center of mass article..