Relleno de inundación: Relleno de inundación: exploración del terreno dinámico de la visión por computadora

Por Fouad Sabry

Qué es el relleno por inundación

El relleno por inundación, también llamado relleno de semillas, es un algoritmo de inundación que determina y altera el área conectada a un nodo determinado en una matriz multidimensional con algún atributo coincidente. Se utiliza en la herramienta de relleno "cubo" de los programas de pintura para rellenar áreas conectadas de colores similares con un color diferente, y en juegos como Go y Buscaminas para determinar qué piezas se limpian. Una variante llamada relleno de límites utiliza los mismos algoritmos pero se define como el área conectada a un nodo determinado que no tiene un atributo particular.

Cómo se beneficiará

(I) Información y validaciones sobre los siguientes temas:

Capítulo 1: Relleno por inundación

Capítulo 2: Representación de líneas de escaneo

Capítulo 3: Profundidad -primera búsqueda

Capítulo 4: Quadtree

Capítulo 5: Recorrido de gráficos

Capítulo 6: Etiquetado de componentes conectados

Capítulo 7: Watershed (procesamiento de imágenes)

Capítulo 8: Algoritmo de resolución de laberintos

Capítulo 9: Difusión de rayos

Capítulo 10: Desenfoque de cuadro

(II) Responder las principales preguntas del público sobre el relleno contra inundaciones.

(III) Ejemplos del mundo real sobre el uso de relleno contra inundaciones en muchos campos.

Para quién es este libro

Profesionales, estudiantes de pregrado y posgrado, entusiastas, aficionados y aquellos que quieran ir más allá del conocimiento o la información básica para cualquier tipo de Flood Fill.

 

 

• Idioma: Español
• Editorial: Mil Millones De Conocimientos [Spanish]
• Fecha de lanzamiento: 4 may 2024

Vista previa del libro

Capítulo 1: Relleno de inundación

El relleno de inundación, también conocido como relleno de semilla, es un algoritmo de inundación que elige y modifica la región en una matriz multidimensional asociada a un nodo específico con un atributo particular. Se utiliza en juegos como Go y Buscaminas para determinar qué piezas se eliminan, así como en la herramienta de relleno cubo de las aplicaciones de pintura para rellenar áreas conectadas de colores similares con un tono distintivo. La región conectada a un nodo determinado pero que carece de un atributo específico es lo que se entiende por la variación conocida como relleno de borde, que emplea las mismas técnicas.

Tenga en cuenta que el relleno de inundación perderá ciertos píxeles en las esquinas más agudas, lo que lo hace inadecuado para dibujar polígonos rellenos. En su lugar, compruebe la regla distinta de cero y la regla par-impar.

El algoritmo clásico de relleno de inundación requiere tres variables: un nodo de inicio, un color de destino y un color de reemplazo. El método cambia al color de reemplazo para cada nodo de la matriz que está conectado al nodo de inicio por una ruta de acceso que es el color de destino. En lugar del color de destino, se proporcionaría un color de borde para un relleno de límite.

En su lugar, se proporcionarán dos rutinas en las siguientes descripciones para generalizar el método de la manera habitual. Entre ellos se encuentran Set, que rellena un píxel o nodo, e Inside, que devuelve true para los puntos sin rellenar que, en función de su color, estarían dentro del área rellena. Una vez que Set ha sido llamado en un nodo, debe salir del Inside.

Hay dos versiones dependiendo de si contamos los nodos que se tocan en las esquinas como conectados o no: de ocho y de cuatro vías, respectivamente.

A continuación se muestra la implementación de relleno de inundación de cuatro vías más antigua conocida que se basa implícitamente en la pila:

Relleno de inundación (nodo):

1. Si el nodo no está dentro , devuelva.

2. Establecer el nodo

3. Realice el relleno de inundación un paso al sur del nodo.

4. Realice el relleno de inundación un paso al norte del nodo

5. Realice el relleno de inundación un paso al oeste del nodo

6. Realice el relleno de inundación un paso al este del nodo

7. Devolución.

En lenguajes y situaciones en las que el espacio de pila es extremadamente limitado, la implementación de la técnica utilizada anteriormente es fácil de entender pero inviable (por ejemplo, microcontroladores).

Se evita un desbordamiento de pila moviendo la recursividad a una estructura de datos, como una pila o una cola. La elección de la estructura de datos afecta al patrón de proliferación, pero es similar al método recursivo simple en el sentido de que empuja los nodos a una pila o cola para su consumo en lugar de realizar llamadas recursivas:

Relleno de inundación (nodo):

1. Establezca Q en la cola o pila vacía.

2. Agregue el nodo al final de Q.

3. Mientras Q no esté vacío:

4. Iguale n al primer elemento de Q.

5. Elimine el primer elemento de Q.

6. Si n está dentro:

Establezca el parámetro n

Agregue el nodo al oeste de n al final de Q.

Agregue el nodo al este de n al final de Q.

Agregue el nodo al norte de n al final de Q.

Agregue el nodo al sur de n al final de Q.

7. Continúe haciendo un bucle hasta que se agote Q.

8. Devolución.

Antes de agregar un nodo a la pila o cola, determine y establezca su color de píxel para minimizar el tamaño de la pila o cola.

Utilice un bucle para moverse en una dirección este-oeste mientras pone en cola los píxeles por encima y por debajo (lo que lo hace similar a los algoritmos de llenado de intervalos, a continuación).

Para proporcionar a los procesadores desordenados más oportunidades de paralelizar, intercala dos o más copias del código con pilas y colas adicionales.

Use varios hilos, idealmente con horarios de visita ligeramente diferentes para que no se congreguen en un solo lugar.

Método sencillo que es fácil de crear sin errores.

Uso intensivo de memoria, especialmente cuando se usa una pila.

Prueba los píxeles más rellenos cuatro veces en total.

El relleno de patrones no es posible ya que necesita que cambien los resultados de las pruebas de píxeles.

El patrón de acceso para la variación de cola no es compatible con la memoria caché.

Difícil de optimizar para planos de bits o palabras de varios píxeles.

Trabajar en gran medida con intervalos, una fila con y constante, permite una mayor optimización. El primer ejemplo completo publicado opera de acuerdo con el siguiente principio fundamental:

Rellene a la izquierda y a la derecha después de un punto semilla. Realice un seguimiento de los puntos rellenos más a la izquierda y más a la derecha, lx y rx, respectivamente. Esto establece el rango.

Busque más puntos de inicialización escaneando de lx a rx por encima y por debajo del punto de inicialización actual.

El proceso de análisis se optimiza para que solo se deban reiniciar los puntos de inicialización al principio del siguiente intervalo. Una cola explora primero los intervalos, mientras que una pila investiga primero los intervalos en términos de profundidad.

A pesar de comprobar los píxeles más llenos tres veces en total, este enfoque es el más común en términos de implementaciones y citas.

fn relleno (x, y):

si no es Inside(x, y) entonces return

let s = nueva pila o cola vacía

Suma (x, y) a s

while s no está vacío:

Eliminar un (x, y) de s

Sea lx = x

mientras que Inside(lx - 1, y):

Conjunto (lx - 1, y)

lx = lx - 1

mientras que Inside(x, y):

Conjunto (x, y)

x = x + 1

Escaneo (Lx, X - 1, Y + 1, S)

Escaneo (Lx, X - 1, Y - 1, S)

Escaneo FN (LX, RX, Y, S):

let span_added = falso

para x en lx .. Rx:

si no es Inside(x, y):

span_added = falso

De lo contrario, si no span_added:

Suma (x, y) a s

span_added = verdadero

Con el tiempo, se realizaron las siguientes mejoras:

No sería necesario poner en cola un nuevo análisis si estuviera totalmente dentro de un intervalo de abuelos, ya que solo detectaría píxeles rellenos.

Además, solo se deben escanear los voladizos (giros en U y giros en W) cuando un nuevo escaneo cruza un tramo de abuelos.

Puedes llenarte mientras buscas semillas.

fn relleno (x, y):

si no es Inside(x, y) entonces return

let s = nueva cola o pila vacía

Suma (x, x, y, 1) a s

Suma (x, x, y - 1, -1) a s

while s no está vacío:

Elimine an (x1, x2, y, dy) de s

Sea x = x1

si está dentro(x, y):

mientras que Inside(x - 1, y):

Conjunto (x - 1, y)

x = x - 1

Si x < x1:

Suma (x, x1-1, y-dy, -dy) a s

mientras que x1 <= x2:

mientras que Inside(x1, y):

Conjunto (x1, y)

x1 = x1 + 1

Suma (x, x1 - 1, y+dy, dy) a s

Si x1 - 1 > x2:

Suma (x2 + 1, x1 - 1, y-dy, -dy) a s

x1 = x1 + 1

mientras que x1 < x2 y no Inside(x1, y):

x1 = x1 +