arrays - regresion - Algoritmo vecino de matriz 2D

knn imagenes

Question

Tengo una matriz 2D como esta:

0,1,0,0,1
1,0,1,0,1
0,1,1,0,1
0,1,0,1,1
1,1,0,0,1

Si extraemos las coordenadas de todos los 1, obtenemos:

(height,width)
1,2
1,5
2,1
... 

Entonces ahora quiero encontrar las áreas creadas por los vecinos 1 (no en diagonal). Para hacer esto, necesito encontrar una manera de verificar a los vecinos de los vecinos. He estado pensando en usar dos arreglos e intercambiar los vecinos de un vecino por uno y luego por otro, pero no es una manera muy eficiente especialmente cuando se trata de procesar una gran variedad. ¿Hay una mejor solución para este problema?

Gracias

Answer 1

Hay muchos de estos métodos, se los denomina etiquetado de componentes conectados. Estos son algunos de ellos que no son tan antiguos (sin ningún orden en particular):

1. Etiquetado de velocidad de luz para arquitecturas RISC , 2009
2. Optimización de algoritmos de etiquetado de componentes conectados de dos pasos , 2009
3. Un algoritmo de etiquetado de componentes de tiempo lineal que utiliza la técnica de seguimiento de contorno , 2004

El segundo método se menciona como "Algoritmo de Wu" en la literatura (en realidad se refieren a un documento anterior, pero el algoritmo presentado allí es el mismo), y se lo considera como uno de los más rápidos para esta tarea. Usar el relleno de inundación es sin duda uno de los últimos métodos que te gustaría usar, ya que es muy lento en comparación con cualquiera de estos. Este algoritmo Wu es un etiquetado de dos pasos basado en la estructura de datos union-find con compresión de ruta, y es relativamente fácil de implementar. Como el artículo trata sobre la conectividad de 8, incluyo un código de muestra para manejar la conectividad de 4 (de lo que se trata su pregunta).

El código para la estructura union-find se toma como está del documento, pero encontrará un código similar en cada texto que lea sobre esta estructura de datos.

def set_root(e, index, root):
    # Set all nodes to point to a new root.
    while e[index] < index:
        e[index], index = root, e[index]
    e[index] = root

def find_root(e, index):
    # Find the root of the tree from node index.
    root = index
    while e[root] < root:
        root = e[root]
    return root

def union(e, i, j):
    # Combine two trees containing node i and j.
    # Return the root of the union.
    root = find_root(e, i)
    if i != j:
        root_j = find_root(e, j)
        if root > root_j:
            root = root_j
        set_root(e, j, root)
    set_root(e, i, root)
    return root

def flatten_label(e):
    # Flatten the Union-Find tree and relabel the components.
    label = 1
    for i in xrange(1, len(e)):
        if e[i] < i:
            e[i] = e[e[i]]
        else:
            e[i] = label
            label += 1

Por simplicidad, supongo que la matriz se rellena con ceros en los lados superior e izquierdo.

def scan(a, width, height): # 4-connected
    l = [[0 for _ in xrange(width)] for _ in xrange(height)]

    p = [0] # Parent array.
    label = 1
    # Assumption: ''a'' has been padded with zeroes (bottom and right parts
    # does not require padding).
    for y in xrange(1, height):
        for x in xrange(1, width):
            if a[y][x] == 0:
                continue

            # Decision tree for 4-connectivity.
            if a[y - 1][x]: # b
                if a[y][x - 1]: # d
                    l[y][x] = union(p, l[y - 1][x], l[y][x - 1])
                else:
                    l[y][x] = l[y - 1][x]
            elif a[y][x - 1]: # d
                l[y][x] = l[y][x - 1]
            else:
                # new label
                l[y][x] = label
                p.append(label)
                label += 1

    return l, p

Entonces, inicialmente tienes una matriz que pasas a este scan funciones. Este es el primer pase de etiquetado. Para resolver las etiquetas, simplemente llame a flatten_label(p) . Entonces, el segundo pase de etiquetado es trivial:

for y in xrange(height):
    for x in xrange(width):
        l[y][x] = p[l[y][x]]

Ahora sus componentes con 4 conexiones han sido etiquetados, y max(p) da cuántos de los que tiene. Si lees el documento junto con este código, no deberías tener problemas para entenderlo. La sintaxis es de Python, si tiene alguna duda sobre su significado, siéntase libre de preguntar.

Answer 2

Si mi comprensión de su pregunta es correcta, puede usar floodfill para resolver el problema.