Relleno de inundación

Inundación recuperada llena de 4 direcciones

Relleno de inundación, también llamado relleno de semilla, 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 el "cubo" herramienta de relleno de los programas de pintura para rellenar áreas conectadas de colores similares con un color diferente, y en juegos como Go y Minesweeper para determinar qué piezas se eliminan. Una variante llamada relleno de límite utiliza los mismos algoritmos pero se define como el área conectada a un nodo dado que no tiene un atributo particular.

Tenga en cuenta que el relleno por inundación no es adecuado para dibujar polígonos rellenos, ya que perderá algunos píxeles en las esquinas más agudas. En su lugar, consulte la regla par-impar y la regla distinta de cero.

Los parámetros del algoritmo

Inundación recuperada llena de 8 direcciones

El algoritmo de relleno por inundación tradicional toma tres parámetros: un nodo de inicio, un color de destino y un color de reemplazo. El algoritmo busca todos los nodos en la matriz que están conectados al nodo de inicio por una ruta del color de destino y los cambia al color de reemplazo. Para un relleno de límites, en lugar del color de destino, se proporcionaría un color de borde.

Para generalizar el algoritmo de la forma habitual, las siguientes descripciones tendrán dos rutinas disponibles. Uno llamado Inside que devuelve verdadero para puntos sin rellenar que, por su color, estarían dentro del área rellena, y uno llamado Set que rellena un píxel/nodo. Cualquier nodo al que se haya llamado Set ya no debe estar Inside.

Dependiendo de si consideramos que los nodos se tocan en las esquinas conectadas o no, tenemos dos variaciones: de ocho vías y de cuatro vías respectivamente.

Implementación recursiva basada en pila (cuatro vías)

La implementación de relleno de inundación de cuatro vías recursiva implícitamente basada en pila más antigua es la siguiente:

Flood-fill (nodo):
1. Si nodos no Dentro Vuelve.
2. Set el nodos3. Realización Flood-fill un paso hacia el sur nodos.
4. Realización Flood-fill un paso hacia el norte nodos5. Realización Flood-fill un paso hacia el oeste nodos6. Realización Flood-fill un paso hacia el este nodos7. Regresa.

Aunque es fácil de entender, la implementación del algoritmo utilizado anteriormente no es práctica en lenguajes y entornos donde el espacio de pila está severamente limitado (por ejemplo, microcontroladores).

Mover la recursividad a una estructura de datos

Relleno de inundación de cuatro vías utilizando una cola para el almacenamiento

Inundación de cuatro vías llenando una pila para almacenamiento

Mover la recursividad a una estructura de datos (ya sea una pila o una cola) evita un desbordamiento de la pila. Es similar a la solución recursiva simple, excepto que en lugar de realizar llamadas recursivas, empuja los nodos a una pila o cola para su consumo, y la elección de la estructura de datos afecta el patrón de proliferación:

Flood-fill (nodo):
1. Conjunto Q a la cola vacía o apilar.
2. Add nodos hasta el final Q.
3. Mientras Q no está vacío:
4. Conjunto n igual al primer elemento Q.
5. Eliminar el primer elemento de Q.
6. Si n es Dentro:
 Set el nAñadir el nodo al oeste de n hasta el final Q.
Añadir el nodo al este de n hasta el final Q.
Añadir el nodo al norte de n hasta el final Q.
Añadir el nodo al sur n hasta el final Q.
7. Continuar la bucle hasta Q está agotado.
8. Regresa.

Posibles optimizaciones adicionales

• Compruebe y establecer el color de píxel de cada nodo antes de añadirlo a la pila / cola, reduciendo el tamaño de la pila / cola.
• Use un bucle para las direcciones este/oeste, queuing pixels arriba/bajo a medida que vaya (haciendo que sea similar a los algoritmos de llenado de lazo, abajo).
• Interlear dos o más copias del código con pilas/cuues extra, para permitir a los procesadores fuera de orden más oportunidad de paralelizar.
• Utilice varios hilos (idealmente con órdenes de visita ligeramente diferentes, por lo que no se quedan en la misma zona).

Ventajas

• algoritmo muy simple - fácil de hacer sin errores.

Desventajas

• Usa mucha memoria, especialmente cuando usa una pila.
• Pruebas más llenas de píxeles un total de cuatro veces.
• No es adecuado para el relleno de patrón, ya que requiere resultados de prueba de pixel para cambiar.
• El patrón de acceso no es fácil de caché, para la variante de búsqueda.
• No se puede optimizar fácilmente para palabras multipíxeles o bitplanes.

Llenado de tramos

Rellene Scanline usando una pila para almacenamiento

Es posible optimizar aún más las cosas trabajando principalmente con tramos, una fila con la constante y. El primer ejemplo completo publicado funciona según el siguiente principio básico.

1. Comenzando con un punto de semilla, rellenar a la izquierda y a la derecha. Realizar un seguimiento del punto más zanjado lx y el punto más ocupado rx. Esto define el lazo.
2. Escáner lx a rx arriba y debajo del punto de semilla, buscando nuevos puntos de semilla para continuar.

Como optimización, el algoritmo de exploración no necesita reiniciarse desde cada punto inicial, sino solo desde el comienzo del siguiente tramo. El uso de una pila explora primero la profundidad de los tramos, mientras que una cola explora primero la amplitud de los tramos.

Este algoritmo es el más popular, tanto para citas como para implementaciones, a pesar de probar la mayoría de los píxeles rellenos tres veces en total.

f relleno()x, Sí.):
si no Dentro()x, Sí.Entonces regresa
Deja s = nueva pila o cola vacía
Add (x, Sí.) a smientras s no está vacío:
Quitar un (x, Sí.) de sDeja lx = xmientras Dentro()lx - 1, Sí.):
 Set()lx - 1, Sí.)
 lx = lx - 1
mientras Dentro()x, Sí.):
 Set()x, Sí.)
 x = x + 1
 Escaneos()lx, x - 1, Sí. + 1, s)
 Escaneos()lx, x - 1, Sí. - 1, s)

f Escaneos()lx, rx, Sí., s):
Deja span_added = falsopara x dentro lx.. rx:
si no Dentro()x, Sí.):
 span_added = falsosi no span_added:
Add (x, Sí.) a s span_added = verdadero

Con el tiempo, se realizaron las siguientes optimizaciones:

• Cuando un nuevo escaneo estaría completamente dentro de un lapso de abuelo, sin duda sólo encontraría píxeles llenos, y así no necesitaría cola.
• Además, cuando un nuevo escaneo superpone un lazo de abuelo, sólo los overhangs (U-turns y W-turns) necesitan ser escaneados.
• Es posible rellenar mientras se escanea las semillas

En 1990 se publicó el último relleno de intervalo combinado de exploración y relleno. En forma de pseudocódigo:

f relleno()x, Sí.):
si no Dentro()x, Sí.Entonces regresa
Deja s = nueva cola o pila vacía
Add (x, x, Sí., 1) a sAdd (x, x, Sí. - 1, -1) a smientras s no está vacío:
Quitar un (x1, x2, Sí., dy) de sDeja x = x1si Dentro()x, Sí.):
mientras Dentro()x - 1, Sí.):
 Set()x - 1, Sí.)
 x = x - 1
si x. x1:
Add (x, x1-1, Sí.-dy, -dy) a smientras x1. x2:
mientras Dentro()x1, Sí.):
 Set()x1, Sí.)
 x1 = x1 + 1
 Añadir ()x, x1 - 1, Sí.+dy, dy) a ssi x1 - 1 x2:
 Añadir ()x2 + 1, x1 - 1, Sí.-dy, -dy) a s x1 = x1 + 1
mientras x1. x2 y no Dentro()x1, Sí.):
 x1 = x1 + 1
 x = x1

Ventajas

• 2x-8x más rápido que el algoritmo recursivo de pixel.
• El patrón de acceso es de caché y bitplane-friendly.
• Puede dibujar una línea horizontal en lugar de fijar píxeles individuales.

Desventajas

• Todavía visita píxeles que ya ha llenado. (Para el algoritmo popular, 3 escaneos de la mayoría de los píxeles. Para el final, sólo haciendo escaneos adicionales de píxeles donde hay agujeros en el área llenada.)
• No es adecuado para el relleno de patrón, ya que requiere resultados de prueba de pixel para cambiar.

Agregar soporte de relleno de patrones

Dos formas comunes de hacer que los algoritmos basados en píxeles y de intervalo admitan el relleno de patrones son usar un color único como un relleno simple y luego reemplazarlo con un patrón o realizar un seguimiento (en una matriz booleana 2D o como regiones). de los cuales se han visitado píxeles, utilizándolo para indicar que los píxeles ya no se pueden rellenar. Interior debe devolver falso para dichos píxeles visitados.

Relleno teórico de grafos

Algunos teóricos aplicaron la teoría de gráficos explícitos al problema, tratando tramos de píxeles, o agregados de los mismos, como nodos y estudiando su conectividad. El primer algoritmo de teoría de grafos publicado funcionó de manera similar al llenado de tramos, pero tenía una forma de detectar cuándo duplicaría el llenado de tramos. Desafortunadamente, tenía errores que hacían que no completara algunos rellenos. Posteriormente se publicó un algoritmo corregido con una base similar en la teoría de grafos; sin embargo, altera la imagen a medida que avanza, para bloquear temporalmente los posibles bucles, lo que complica la interfaz programática. Un algoritmo publicado más tarde dependía de que el límite fuera distinto de todo lo demás en la imagen y, por lo tanto, no es adecuado para la mayoría de los usos; también requiere un bit adicional por píxel para la contabilidad.

Ventajas

• Adecuado para relleno de patrón, directamente, ya que nunca retesta píxeles llenos.
• Doblar la velocidad del algoritmo de lapso original, para rellenos sin complicaciones.
• El patrón de acceso es de caché y bitplane-friendly.

Desventajas

• Regularmente, un lazo tiene que ser comparado con cada otro 'front' en la cola, que disminuye significativamente los rellenos complicados.
• Cambiar de ida y vuelta entre los dominios teoréticos gráficos y pixel complica la comprensión.
• El código es bastante complicado, aumentando las posibilidades de errores.

Llenado basado en caminata (método de memoria fija)

Existe un método que esencialmente no usa memoria para las regiones conectadas por cuatro al pretender ser un pintor que intenta pintar la región sin pintarse a sí mismos en una esquina. Este es también un método para resolver laberintos. Los cuatro píxeles que forman el límite primario se examinan para ver qué acción se debe tomar. El pintor podría encontrarse en una de varias condiciones:

1. Los cuatro píxeles límite están llenos.
2. Tres de los píxeles del límite están llenos.
3. Dos de los píxeles del límite están llenos.
4. Un píxel de límite está lleno.
5. Los píxeles de límite cero están llenos.

Cuando se debe seguir un camino o un límite, se utiliza la regla de la mano derecha. El pintor sigue la región colocando su mano derecha en la pared (el límite de la región) y avanzando alrededor del borde de la región sin quitar la mano.

Para el caso n.º 1, el pintor pinta (rellena) el píxel sobre el que se encuentra y detiene el algoritmo.

Para el caso #2, existe un camino que sale del área. Pinte el píxel sobre el que está parado el pintor y muévase en la dirección del camino abierto.

Para el caso n.º 3, los dos píxeles de contorno definen una ruta que, si pintamos el píxel actual, puede impedirnos volver al otro lado de la ruta. Necesitamos una "marca" para definir dónde estamos y en qué dirección nos dirigimos para ver si alguna vez volvemos exactamente al mismo píxel. Si ya creamos tal "marca", conservamos nuestra marca anterior y pasamos al siguiente píxel siguiendo la regla de la mano derecha.

Se usa una marca para el primer límite de 2 píxeles que se encuentra para recordar dónde comenzó el pasaje y en qué dirección se movía el pintor. Si se vuelve a encontrar la marca y el pintor viaja en la misma dirección, entonces el pintor sabe que es seguro pintar el cuadrado con la marca y continuar en la misma dirección. Esto se debe a que (a través de una ruta desconocida) los píxeles del otro lado de la marca se pueden alcanzar y pintar en el futuro. La marca se elimina para uso futuro.

Si el pintor encuentra la marca pero va en una dirección diferente, entonces se ha producido una especie de bucle que hizo que el pintor volviera a la marca. Este bucle debe ser eliminado. Se levanta la marca y el pintor procede en la dirección indicada previamente por la marca usando la regla de la mano izquierda para el límite (similar a la regla de la mano derecha pero usando la mano izquierda del pintor). Esto continúa hasta que se encuentra una intersección (con tres o más píxeles de contorno abiertos). Todavía usando la regla de la mano izquierda, el pintor ahora busca un pasaje simple (compuesto por dos píxeles de contorno). Al encontrar esta ruta límite de dos píxeles, ese píxel se pinta. Esto rompe el ciclo y permite que el algoritmo continúe.

Para el caso #4, necesitamos verificar las esquinas opuestas conectadas en 8 para ver si están llenas o no. Si uno o ambos están llenos, esto crea una intersección de muchas rutas y no se puede llenar. Si ambos están vacíos, se puede pintar el píxel actual y el pintor puede moverse siguiendo la regla de la mano derecha.

El algoritmo intercambia tiempo por memoria. Para formas simples es muy eficiente. Sin embargo, si la forma es compleja con muchas características, el algoritmo dedica una gran cantidad de tiempo a rastrear los bordes de la región para asegurarse de que todo se pueda pintar.

Este algoritmo estuvo disponible comercialmente por primera vez en 1981 en un sistema de procesamiento de imágenes Vicom fabricado por Vicom Systems, Inc. En 1994 se publicó un algoritmo de desplazamiento. El algoritmo clásico de relleno de inundación recursivo también estaba disponible en el sistema Vicom.

Pseudocódigo

Esta es una implementación de pseudocódigo de un algoritmo de llenado de inundación de memoria fija óptimo escrito en inglés estructurado:

Las variables

• cur, mark, y mark2 cada sujetar coordenadas pixel o un valor nulo
  • NOTA: cuando mark se establece para anular, no borrar su valor de coordenadas anterior. Mantenga las coordenadas disponibles para ser recordadas si es necesario.
• cur-dir, mark-dir, y mark2-dir cada uno tiene una dirección (izquierda, derecha, arriba o abajo)
• backtrack y findloop cada uno de los valores booleanos
• count es un entero

El algoritmo

NOTA: Todas las direcciones (frontera, espalda, izquierda, derecha) son relativas a cur-dir

set cur to starting pixel
establecer cur-dir a dirección predeterminada
marca clara y marca2 (valores fijos a null)
set backtrack and findloop to false

mientras front-pixel está vacío doavance
terminar mientrassaltar a START

MAIN LOOP:
avance
 si El pixel derecho está dentro entonces si backtrack es verdad y encontrarloop es falso y o frontal-pixel o El pixel izquierdo está dentro entoncesset findloop to true
 terminar sigire a la derecha
PAINT:
avance
 terminar siSTART:
 set Cuenta to number of non-diagonally adjacent pixels filled (front/back/left/right ONLY)
 si Cuenta no 4 entonces dogire a la derecha
 mientras el pixel delantero está dentro
 dogire a la izquierda
 mientras front-pixel no está dentro
 terminar si interruptor CuentaCaso 1
 si backtrack es verdad entoncesset findloop to true
 si encontrarloop es verdad entonces si La marca es nula entoncesrestaurar marca
 terminar si si frontal-izquierda-pixel y retro-izquierda-pixel están ambos dentro entoncesmarca clara
curtidor
saltar a PAINT
 terminar siCaso final
Caso 2
 si atrás-pixel no está dentro entonces si front-left-pixel está dentro entoncesmarca clara
curtidor
saltar a PAINT
 terminar si si marca no se establece entoncesmarcar para frenar
set mark-dir to cur-dir
marca clara2
set findloop y backtrack a false
 más si Mark2 no está fijado entonces si Cur está en la marca entonces si cur-dir es lo mismo que Mark-dir entoncesmarca clara
Date la vuelta
curtidor
saltar a PAINT
 másretroceder a la verdad
set findloop to false
set cur-dir to mark-dir
 terminar si si encontrarloop es verdad entoncesmarca2 para curar
set mark2-dir to cur-dir
 terminar si más si Cur está en la marca entoncesestablecer la curva a la marca2
set cur-dir to mark2-dir
marca clara y marca2
de nuevo a falso
Date la vuelta
curtidor
saltar a PAINT
 más si se cura en la marca2 entoncesmarcar para frenar
set cur-dir y mark-dir a mark2-dir
marca clara2
 terminar si terminar si terminar siCaso final
Caso 3
marca clara
curtidor
saltar a PAINT
Caso final
Caso 4
curtidor
hecho
Caso final
 interruptor de extremofinal MAIN LOOP

Ventajas

• Uso constante de memoria.

Desventajas

• El patrón de acceso no es fácil de caché o bitplane.
• Puede pasar mucho tiempo caminando por los bucles antes de cerrarlos.

Implementaciones de vectores

La versión 0.46 de Inkscape incluye una herramienta de relleno de cubeta, que brinda resultados similares a las operaciones de mapa de bits ordinarias y, de hecho, usa una: se procesa el lienzo, se realiza una operación de relleno de inundación en el área seleccionada y luego se rastrea el resultado hasta una ruta. Utiliza el concepto de una condición de contorno.