Relleno de inundación - Flood fill

Relleno de inundación recurrente con 4 direcciones

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.

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. En su lugar, consulte Regla par impar y Regla distinta de cero .

Los parámetros del algoritmo

Relleno de inundación recurrente con 8 direcciones

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. Uno llamado Insideque devuelve verdadero para puntos sin completar que, por su color, estarían dentro del área llena, y uno llamado Setque llena un píxel / nodo. Cualquier nodo que lo haya Setllamado 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 y de relleno por inundación de cuatro vías es la siguiente: 

Flood-fill (node):
 1. If node is not Inside return.
 2. Set the node
 3. Perform Flood-fill one step to the south of node.
 4. Perform Flood-fill one step to the north of node
 5. Perform Flood-fill one step to the west of node
 6. Perform Flood-fill one step to the east of node
 7. Return.

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á severamente restringido (por ejemplo, microcontroladores ).

Mover la recursividad a una estructura de datos

Relleno de inundación de cuatro vías usando una cola para almacenamiento
Relleno de inundación de cuatro vías usando 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 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: 

Flood-fill (node):
  1. Set Q to the empty queue or stack.
  2. Add node to the end of Q.
  3. While Q is not empty:
  4.   Set n equal to the first element of Q.
  5.   Remove first element from Q.
  6.   If n is Inside:
         Set the n
         Add the node to the west of n to the end of Q.
         Add the node to the east of n to the end of Q.
         Add the node to the north of n to the end of Q.
         Add the node to the south of n to the end of Q.
  7. Continue looping until Q is exhausted.
  8. Return.

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 se queden en la misma área)

Ventajas

  • Algoritmo muy simple: fácil de hacer sin errores.

Desventajas

  • Utiliza mucha memoria, especialmente cuando se usa una pila.
  • 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.

Llenado de tramo

Relleno de línea de escaneo

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. 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, a pesar de probar la mayoría de los píxeles llenos tres veces en total. En forma de pseudocódigo: 

fn fill(x, y):
  if not Inside(x, y) then return
  let s = new empty stack or queue
  add (x, y) to s
  while s is not empty:
    Remove an (x, y) from s
    let lx = x
    while Inside(lx - 1, y):
      Set(lx - 1, y)
      lx = lx - 1
    while Inside(x, y):
      Set(x, y)
      x = x + 1
    scan(lx, x - 1, y + 1, s)
    scan(lx, x - 1, y - 1, s)

fn scan(lx, rx, y, s):
  let added = false
  for x in lx .. rx:
    if not Inside(x, y):
      added = false
    else if not added:
      Add (x, y) to s
      added = true

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.
  • 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).
  • Es posible llenar mientras se escanea en busca de semillas

El relleno de tramo final combinado de escaneo y relleno se publicó en 1990 y procede de la siguiente manera (aunque la versión aquí corrige algunos errores en el original): 

fn fill(x, y):
  if not Inside(x, y) then return
  let s = new empty queue or stack
  Add (x, x, y, 1) to s
  Add (x, x, y - 1, -1) to s
  while s is not empty:
    Remove an (x1, x2, y, dy) from s
    let x = x1
    if Inside(x, y):
      while Inside(x - 1, y):
        Set(x - 1, y)
        x = x - 1
    if x < x1:
      Add (x, x1-1, y-dy, -dy) to s
    while x1 < x2:
      while Inside(x1, y):
        Set(x1, y)
        x1 = x1 + 1
      Add (x, x1 - 1, y+dy, dy) to s
      if x1 - 1 > x2:
        Add (x2 + 1, x1 - 1, y-dy, -dy)
      while x1 < x2 and not 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.
  • Puede dibujar una línea horizontal en lugar de establecer píxeles individuales.

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).
  • 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. El interior debe devolver falso para dichos píxeles visitados.

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. Desafortunadamente, tenía errores que hicieron 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 posibles bucles, lo que complica la interfaz programática. 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; también requiere un bit extra por píxel para la contabilidad.

Ventajas

  • Adecuado para el relleno de patrones, directamente, ya que nunca vuelve a probar los píxeles llenos.
  • Duplique la velocidad del algoritmo de tramo original, para rellenos sin complicaciones.
  • El patrón de acceso es compatible con la memoria caché y el plano de bits.

Desventajas

  • Regularmente, un tramo debe compararse con cualquier otro "frente" en la cola, lo que ralentiza significativamente los rellenos complicados.
  • 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:

  1. Se rellenan los cuatro píxeles de los límites.
  2. Se rellenan tres de los píxeles de los límites.
  3. Se rellenan dos de los píxeles de los límites.
  4. Se rellena un píxel de límite.
  5. Se rellenan los píxeles de límite cero.

Cuando se va a seguir una ruta 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 de nuevo 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 opuestas conectadas 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, 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. 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 óptimo de relleno por inundación de memoria fija escrito en inglés estructurado:

Las variables
  • cur, marky mark2cada uno contiene coordenadas de píxeles o un valor nulo
    • NOTA: cuando markse establece en nulo, no borre su valor de coordenada anterior. Mantenga esas coordenadas disponibles para recordarlas si es necesario.
  • cur-dir, mark-diry mark2-dircada uno tiene una dirección (izquierda, derecha, arriba o abajo)
  • backtracky findloopcada uno tiene valores booleanos
  • count es un entero
El algoritmo
NOTA: Todas las direcciones (frontal, posterior, izquierda, derecha) son relativas a cur-dir 
set cur to starting pixel
set cur-dir to default direction
clear mark and mark2 (set values to null)
set backtrack and findloop to false

while front-pixel is empty do
    move forward
end while

jump to START

MAIN LOOP:
    move forward
    if right-pixel is inside then
        if backtrack is true and findloop is false and either front-pixel or left-pixel is inside then
            set findloop to true
        end if
        turn right
PAINT:
        move forward
    end if
START:
    set count to number of non-diagonally adjacent pixels filled (front/back/left/right ONLY)
    if count is not 4 then
        do
            turn right
        while front-pixel is inside
        do
            turn left
        while front-pixel is not inside
    end if
    switch count
        case 1
            if backtrack is true then
                set findloop to true
            else if findloop is true then
                if mark is null then
                    restore mark
                end if
            else if front-left-pixel and back-left-pixel are both inside then
                clear mark
                set cur
                jump to PAINT
            end if
        end case
        case 2
            if back-pixel is not inside then
                if front-left-pixel is inside then
                    clear mark
                    set cur
                    jump to PAINT
                end if
            else if mark is not set then
                set mark to cur
                set mark-dir to cur-dir
                clear mark2
                set findloop and backtrack to false
            else
                if mark2 is not set then
                    if cur is at mark then
                        if cur-dir is the same as mark-dir then
                            clear mark
                            turn around
                            set cur
                            jump to PAINT
                        else
                            set backtrack to true
                            set findloop to false
                            set cur-dir to mark-dir
                        end if
                    else if findloop is true then
                        set mark2 to cur
                        set mark2-dir to cur-dir
                    end if
                else
                    if cur is at mark then
                        set cur to mark2
                        set cur-dir to mark2-dir
                        clear mark and mark2
                        set backtrack to false
                        turn around
                        set cur
                        jump to PAINT
                    else if cur at mark2 then
                        set mark to cur
                        set cur-dir and mark-dir to mark2-dir
                        clear mark2
                    end if
                end if
            end if
        end case
        case 3
            clear mark
            set cur
            jump to PAINT
        end case
        case 4
            set cur
            done
        end case
    end switch
end MAIN LOOP

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 luego se rastrea hasta una ruta. Utiliza el concepto de condición de contorno .

Ver también

enlaces externos

Referencias

  1. ↑ 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 .
  2. ↑ 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 .
  3. ^ a b c d e f g h i 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 la interfaz gráfica '85. págs. 56–76. doi : 10.1007 / 978-4-431-68033-8_6 .
  4. ^ 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.
  5. ^ Pavlidis, Theo (1982). Algoritmos para procesamiento de imágenes y gráficos . Springer-Verlag. pag. 181. ISBN 978-3-642-93210-6.
  6. ↑ a b c d e f g h i Levoy, Marc (1982). Algoritmos de inundación de área . SIGGRAPH 1981 Notas del curso de animación por computadora bidimensional.
  7. ^ 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.
  8. ^ 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.
  9. ↑ 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 .
  10. ↑ 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 .
  11. ↑ 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 .
  12. ^ 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 .