El relleno por inundación , también llamado relleno semilla , es un algoritmo que determina y altera el área conectada a un nodo dado 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 Minesweeper para determinar qué piezas se eliminan. Una variante llamada relleno de límite usa los mismos algoritmos pero se define como el área conectada a un nodo dado que no tiene un atributo particular. [1]
Tenga en cuenta que el relleno de inundación no es adecuado para dibujar polígonos rellenos, ya que perderá algunos píxeles en las esquinas más agudas. [2] En su lugar, consulte Regla par impar y Regla distinta de cero .
Los parámetros del algoritmo
El algoritmo tradicional de relleno por inundación 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ímite, en lugar del color de destino, se proporcionaría un color de borde.
Para generalizar el algoritmo de la manera común, las siguientes descripciones tendrán en su lugar dos rutinas disponibles. [3] Uno llamado Inside
que devuelve verdadero para puntos sin rellenar que, por su color, estarían dentro del área llena, y uno llamado Set
que llena un píxel / nodo. Cualquier nodo que lo haya Set
llamado debe dejar de serlo Inside
.
Dependiendo de si consideramos que los nodos se tocan en las esquinas conectados o no, tenemos dos variaciones: ocho y cuatro direcciones respectivamente.
Implementación recursiva basada en pilas (cuatro vías)
La implementación más antigua conocida, implícitamente basada en pila, recursiva , de relleno de inundación de cuatro vías es la siguiente: [4] [5] [6] [7]
Relleno de inundación (nodo): 1. Si el nodo no está dentro, regrese. 2. Configure el nodo. 3. Realice el llenado por inundación un paso al sur del nodo . 4. Realice Flood-fill un paso al norte del nodo 5. Realice Flood-fill un paso al oeste del nodo 6. Realice Flood-fill un paso al este del nodo 7. Regreso.
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 la pila está muy limitado (por ejemplo, los subprogramas de Java ).
Mover la recursividad a una estructura de datos
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 hacer 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:
Relleno de inundación (nodo): 1. Ponga Q en la cola o pila vacía. 2. Añadir el nodo al final de Q . 3. Mientras Q no esté vacío: 4. Conjunto n igual al primer elemento de Q . 5. Retire primer elemento de Q . 6. Si n es el interior : Conjunto del n Añadir el nodo al oeste de n hasta el final de Q . Añadir el nodo al este de n hasta el final de Q . Añadir el nodo al norte de n hasta el final de Q . Añadir el nodo al sur de n hasta el final de Q . 7. Continúe dando vueltas hasta que Q se agote. 8. Regreso.
Posibles optimizaciones adicionales
- Verifique y establezca el color de píxel de cada nodo antes de agregarlo a la pila / cola, reduciendo el tamaño de la pila / cola.
- Utilice un bucle para las direcciones este / oeste, poniendo en cola los píxeles arriba / abajo a medida que avanza. (Haciéndolo similar a los algoritmos de llenado de tramo, a continuación).
- Intercalar dos o más copias del código con pilas / colas adicionales, para permitir que los procesadores OoO tengan más oportunidades de paralelizar
- Use varios hilos (idealmente con órdenes de visita ligeramente diferentes, para que no permanezcan en la misma área) [6]
Ventajas
- Algoritmo muy simple: fácil de hacer sin errores. [6]
Desventajas
- Utiliza mucha memoria, especialmente cuando se usa una pila. [6]
- Prueba la mayoría de los píxeles llenos un total de cuatro veces.
- No es adecuado para el relleno de patrones, ya que requiere que cambien los resultados de la prueba de píxeles.
- El patrón de acceso no es compatible con la memoria caché, para la variante de cola.
- No se puede optimizar fácilmente para palabras o planos de bits de varios píxeles. [2]
Llenado de tramo
Es posible optimizar aún más las cosas trabajando principalmente con tramos. El primer ejemplo completo publicado funciona según el siguiente principio básico. [1] Comenzando con un punto de semilla, rellena a la izquierda y a la derecha y realiza un seguimiento de los bordes. Luego, escanea la misma parte de la línea de arriba y la línea de abajo, buscando nuevos puntos de semilla para continuar. Este algoritmo es el más popular, tanto para citas como para implementaciones [ cita requerida ] , a pesar de probar la mayoría de los píxeles llenos tres veces en total. En forma de pseudocódigo:
fn relleno ( x , y ): si no es Inside ( x , y ) entonces regresa let s = nueva pila o cola vacía agregue ( x , y ) a s mientras que s no esté vacío: Quite an ( x , y ) de s, sea lx = x mientras que Inside ( lx - 1, y ): Establezca ( lx - 1, y ) lx = lx - 1 mientras que Inside ( x , y ): Establecer ( x , y ) x = x + 1 escanear ( lx , x - 1, y + 1, s ) escanear ( lx , x - 1, y - 1, s )fn scan ( lx , rx , y , s ): deje agregado = falso para x en lx .. rx : si no es Inside ( x , y ): added = false else if not added : Suma ( x , y ) as sumado = verdadero
Con el tiempo, se realizaron las siguientes optimizaciones:
- Cuando un nuevo escaneo estaría completamente dentro de un intervalo de abuelos, ciertamente solo encontraría píxeles llenos, por lo que no necesitaría hacer cola. [1] [6] [3]
- Además, cuando un nuevo escaneo se superpone a un tramo de abuelos, solo es necesario escanear los voladizos (giros en U y giros en W). [3]
- Es posible llenar mientras se escanea en busca de semillas [6]
El relleno de tramo final, combinado de escaneo y llenado se publicó en 1990 y procede de la siguiente manera (aunque la versión aquí corrige algunos errores en el original): [8]
fn relleno ( x , y ): si no es Inside ( x , y ) entonces regresa let s = nueva cola o pila vacía Suma ( x , x , y , 1) ah Suma ( x , x , y - 1, -1) ah mientras que s no esté vacío: Quite an ( x1 , x2 , y , dy ) de s sea x = x1 si Inside ( x , y ): mientras que Inside ( x - 1, y ): Establecer ( x - 1, y ) x = x - 1 si x < x1 : Añadir ( x , x1 -1, y - dy , - dy ) a s mientras x1 < x2 : mientras que Inside ( x1 , y ): Establecer ( x1 , y ) x1 = x1 + 1 Sumar ( x , x1 - 1, y + dy , dy ) a s si x1 - 1> x2 : Sumar ( x2 + 1, x1 - 1, y - dy , - dy ) mientras x1 < x2 y no Inside ( x1 , y ): x1 = x1 + 1 x = x1
Ventajas
- 2 x 8 veces más rápido que el algoritmo recursivo de píxeles.
- El patrón de acceso es compatible con la memoria caché y el plano de bits. [6]
- Puede dibujar una línea horizontal en lugar de establecer píxeles individuales. [6]
Desventajas
- Todavía visita los píxeles que ya ha llenado. (Para el algoritmo popular, 3 escaneos de la mayoría de los píxeles. Para el último, solo se realizan escaneos adicionales de píxeles donde hay huecos en el área llena). [3]
- No es adecuado para el relleno de patrones, ya que requiere que cambien los resultados de la prueba de píxeles.
Adición de compatibilidad con relleno de patrones
Dos formas comunes de hacer que los algoritmos basados en píxeles y en tramos sean compatibles con el relleno de patrones son usar un color único como relleno simple y luego reemplazarlo con un patrón o realizar un seguimiento (en una matriz booleana 2d o como regiones) de qué píxeles se han visitado, utilizándolo para indicar que los píxeles ya no se pueden rellenar. Inside debe devolver falso para dichos píxeles visitados. [3]
Relleno teórico de gráficos
Algunos teóricos aplicaron la teoría de grafos explícita 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 relleno de tramos, arriba, pero tenía una forma de detectar cuándo duplicaría el llenado de tramos. [9] Desafortunadamente, tenía errores que hicieron que no completara algunos rellenos. [10] 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 posibles bucles, lo que complica la interfaz programática. [10] Un algoritmo publicado posteriormente 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; [11] [3] también requiere un bit extra por píxel para la contabilidad. [3]
Ventajas
- Adecuado para el relleno de patrones, directamente, ya que nunca vuelve a probar los píxeles llenos. [9] [10] [11]
- Duplique la velocidad del algoritmo de tramo original, para rellenos sin complicaciones. [3]
- El patrón de acceso es compatible con la memoria caché y el plano de bits. [6] [3]
Desventajas
- Regularmente, un tramo debe compararse con cualquier otro "frente" en la cola, lo que ralentiza significativamente los rellenos complicados. [3]
- El cambio entre la teoría de gráficos y los dominios de píxeles complica la comprensión.
- El código es bastante complicado, lo que aumenta las posibilidades de errores.
Llenado basado en caminar (método de memoria fija)
Existe un método que esencialmente no usa memoria para cuatro regiones conectadas , pretendiendo ser un pintor que intenta pintar la región sin pintarse a sí mismo en una esquina. Este también es un método para resolver laberintos. Los cuatro píxeles que forman el límite principal se examinan para ver qué acción se debe tomar. El pintor podría encontrarse en una de varias condiciones:
- Se rellenan los cuatro píxeles de los límites.
- Se rellenan tres de los píxeles de los límites.
- Se rellenan dos de los píxeles de los límites.
- Se rellena un píxel de límite.
- Se rellenan los píxeles de límite cero.
Cuando se va a seguir un camino o un límite, se usa 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 (llena) el píxel sobre el que se encuentra el pintor y detiene el algoritmo.
Para el caso n. ° 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 los límites 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", entonces conservamos nuestra marca anterior y pasamos al siguiente píxel siguiendo la regla de la mano derecha.
Se utiliza 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 la marca se encuentra nuevamente 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 alguna 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 algún tipo de bucle, lo que hizo que el pintor volviera a la marca. Este bucle debe eliminarse. Se toma la marca y el pintor procede en la dirección indicada previamente por la marca utilizando una 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 límite abiertos). Aún utilizando la regla de la mano izquierda, el pintor busca ahora un pasaje simple (formado por dos píxeles de límite). Al encontrar esta ruta de límite de dos píxeles, ese píxel está pintado. Esto rompe el ciclo y permite que el algoritmo continúe.
Para el caso n. ° 4, debemos verificar las 8 esquinas conectadas opuestas para ver si están llenas o no. Si se rellena uno o ambos, esto crea una intersección de muchos caminos y no se puede rellenar. Si ambos están vacíos, entonces el píxel actual se puede pintar y el pintor puede moverse siguiendo la regla de la 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 trazar 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. [ cita requerida ] Se publicó un algoritmo de caminata en 1994. [12] 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 óptimo de relleno por inundación de memoria fija escrito en inglés estructurado:
- Las variables
cur
,mark
ymark2
cada uno contiene coordenadas de píxeles o un valor nulo- NOTA: cuando
mark
se establece en nulo, no borre su valor de coordenada anterior. Mantenga esas coordenadas disponibles para recordarlas si es necesario.
- NOTA: cuando
cur-dir
,mark-dir
ymark2-dir
cada uno tiene una dirección (izquierda, derecha, arriba o abajo)backtrack
yfindloop
cada uno tiene valores booleanoscount
es un entero
- El algoritmo
- NOTA: Todas las direcciones (frontal, posterior, izquierda, derecha) son relativas a
cur-dir
establecer cur en el píxel inicialestablecer cur-dir en la dirección predeterminadaclear mark y mark2 (establecer valores en nulo)establecer backtrack y findloop en falsomientras el píxel frontal está vacío, haz avanzarterminar mientrassaltar a INICIOBUCLE PRINCIPAL: avanzar si el píxel derecho está adentro, entonces si el retroceso es verdadero y findloop es falso y el píxel frontal o el píxel izquierdo está adentro, entonces establecer findloop en verdadero terminara si Gire a la derechaPINTURA: avanzar terminara siCOMIENZO: establezca el recuento en el número de píxeles adyacentes no diagonalmente rellenos (frontal / posterior / izquierda / derecha SOLAMENTE) si el recuento no es 4, entonces hágalo Gire a la derecha mientras que el píxel frontal está dentro, haz Gire a la izquierda mientras que el píxel frontal no está dentro del extremo si cambia el recuento caso 1 si el retroceso es cierto entonces establecer findloop en verdadero de lo contrario, si findloop es verdadero, entonces si la marca es nula, entonces marca de restauración end if else si el píxel frontal izquierdo y el píxel trasero izquierdo están dentro, entonces marca clara establecer cur saltar a PINTAR terminara si caso final caso 2 si el píxel posterior no está adentro, entonces si el píxel frontal izquierdo está adentro, entonces marca clara establecer cur saltar a PINTAR finalizar si de lo contrario si la marca no está establecida entonces establecer marca en cur establecer mark-dir en cur-dir marca clara2 establecer findloop y backtrack en falso de lo contrario, si mark2 no está configurado, entonces si cur está en mark , si cur-dir es lo mismo que mark-dir, entonces marca clara Giro de vuelta establecer cur saltar a PINTAR demás volver atrás en verdad establecer findloop en falso establecer cur-dir en mark-dir terminar si de lo contrario si findloop es verdadero entonces establecer mark2 en cur establecer mark2-dir en cur-dir terminar si de lo contrario si cur está en la marca, entonces establecer cur en mark2 establecer cur-dir en mark2-dir marca clara y mark2 establecer retroceso en falso Giro de vuelta establecer cur saltar a PINTAR de lo contrario, si está en mark2, entonces establecer marca en cur establecer cur-dir y mark-dir en mark2-dir marca clara2 terminar si terminar si terminar si caso final caso 3 marca clara establecer cur saltar a PINTAR caso final caso 4 establecer cur hecho caso final interruptor finalfinalizar BUCLE PRINCIPAL
Ventajas
- Uso constante de memoria.
Desventajas
- El patrón de acceso no es compatible con la memoria caché ni con el plano de bits.
- Puede pasar mucho tiempo dando vueltas alrededor de los bucles antes de cerrarlos.
Implementaciones vectoriales
La versión 0.46 de Inkscape incluye una herramienta de llenado de cubos, que da un resultado similar a las operaciones de mapa de bits ordinarias y, de hecho, usa una: se renderiza el lienzo, se realiza una operación de llenado de inundación en el área seleccionada y el resultado se rastrea hasta una ruta. Utiliza el concepto de condición de contorno .
Ver también
- Búsqueda en amplitud primero
- Búsqueda en profundidad
- Recorrido del gráfico
- Etiquetado de componentes conectados
- Algoritmo de Dijkstra
enlaces externos
- Implementaciones de muestra para relleno de inundación recursivo y no recursivo, clásico y de línea de exploración , por Lode Vandevenne.
- Implementación de relleno de inundación repentina, por Emanuele Feronato.
- QuickFill: un algoritmo de llenado de inundación eficiente. , por John R. Shaw.
- FloodSpill: un algoritmo de llenado de inundaciones de código abierto para C # , por Paweł Ślusarczyk
Referencias
- ↑ a b c Smith, Alvy Ray (1979). Relleno de tinte . SIGGRAPH '79: Actas de la 6ª conferencia anual sobre gráficos por ordenador y técnicas interactivas. págs. 276-283. doi : 10.1145 / 800249.807456 .
- ^ a b Ackland, Bryan D; Weste, Neil H (1981). El algoritmo de la bandera de borde: un método de relleno para pantallas de escaneo ráster . Transacciones IEEE en computadoras (Volumen: C-30, Edición: 1). págs. 41–48. doi : 10.1109 / TC.1981.6312155 .
- ^ a b c d e f g h yo j Fishkin, Kenneth P; Barsky, Brian A (1985). Un análisis y algoritmo para la propagación de relleno . Imágenes generadas por computadora: los procedimientos de vanguardia de Graphics Interface '85. págs. 56–76. doi : 10.1007 / 978-4-431-68033-8_6 .
- ^ Newman, William M; Sproull, Robert Fletcher (1979). Principios de gráficos interactivos por computadora (2ª ed.). McGraw-Hill. pag. 253. ISBN 978-0-07-046338-7.
- ^ Pavlidis, Theo (1982). Algoritmos para procesamiento de imágenes y gráficos . Springer-Verlag. pag. 181. ISBN 978-3-642-93210-6.
- ^ a b c d e f g h yo Levoy, Marc (1982). Algoritmos de inundación de área . SIGGRAPH 1981 Notas del curso de animación por computadora bidimensional.
- ^ Foley, JD; van Dam, A; Feiner, SK; Hughes, SK (1990). Gráficos por computadora: principios y práctica (2ª ed.). Addison – Wesley. págs. 979–982. ISBN 978-0-201-84840-3.
- ^ Heckbert, Paul S (1990). "IV.10: Un algoritmo de relleno de semillas". En Glassner, Andrew S (ed.). Gemas de gráficos . Prensa académica. págs. 275-277. ISBN 0122861663.
- ^ a b Lieberman, Henry (1978). Cómo colorear un libro para colorear . SIGGRAPH '78: Actas de la 5ª conferencia anual sobre gráficos por ordenador y técnicas interactivas. págs. 111-116. doi : 10.1145 / 800248.807380 .
- ^ a b c Shani, Uri (1980). Relleno de regiones en imágenes ráster binarias: un enfoque de teoría de gráficos . SIGGRAPH '80: Actas de la 7ª conferencia anual sobre gráficos por ordenador y técnicas interactivas. págs. 321–327. doi : 10.1145 / 800250.807511 .
- ^ a b Pavlidis, Theo (1981). Relleno de contorno en gráficos de trama . SIGGRAPH '81: Actas de la 8ª conferencia anual sobre gráficos por ordenador y técnicas interactivas. págs. 29–36. doi : 10.1145 / 800224.806786 .
- ^ Henrich, Dominik (1994). Relleno de regiones con uso eficiente del espacio en gráficos rasterizados . La computadora visual. págs. 205–215. doi : 10.1007 / BF01901287 .