Preenchimento - Flood fill

Preenchimento de inundação recursiva com 4 direções

O preenchimento de inundação , também chamado de preenchimento de semente , é um algoritmo que determina e altera a área conectada a um determinado nó em uma matriz multidimensional com algum atributo correspondente. É usado na ferramenta de preenchimento "balde" de programas de pintura para preencher áreas conectadas de cores semelhantes com uma cor diferente, e em jogos como Go e Minesweeper para determinar quais peças são eliminadas. Uma variante chamada de preenchimento de limite usa os mesmos algoritmos, mas é definida como a área conectada a um determinado nó que não possui um atributo específico.

Observe que o preenchimento de inundação não é adequado para desenhar polígonos preenchidos, pois perderá alguns pixels em cantos mais agudos. Em vez disso, consulte Regra par ímpar e Regra diferente de zero .

Os parâmetros do algoritmo

Preenchimento de inundação recursiva com 8 direções

O algoritmo de preenchimento tradicional usa três parâmetros: um nó inicial, uma cor de destino e uma cor de substituição. O algoritmo procura todos os nós na matriz que estão conectados ao nó inicial por um caminho da cor de destino e os altera para a cor de substituição. Para um preenchimento de limite, no lugar da cor de destino, uma cor de borda seria fornecida.

Para generalizar o algoritmo da maneira comum, as seguintes descrições terão duas rotinas disponíveis. Um chamado Insideque retorna verdadeiro para pontos não preenchidos que, por sua cor, estariam dentro da área preenchida, e outro chamado Setque preenche um pixel / nó. Qualquer nó que o tenha Setchamado não deve mais ser Inside.

Dependendo se consideramos nós se tocando nos cantos conectados ou não, temos duas variações: oito vias e quatro vias, respectivamente.

Implementação recursiva baseada em pilha (quatro vias)

A implementação mais antiga conhecida, implicitamente baseada em pilha, recursiva , de preenchimento de quatro vias funciona da seguinte maneira: 

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.

Embora seja fácil de entender, a implementação do algoritmo usado acima é impraticável em linguagens e ambientes onde o espaço da pilha é severamente restrito (por exemplo, microcontroladores ).

Movendo a recursão para uma estrutura de dados

Preenchimento de quatro vias usando uma fila para armazenamento
Preenchimento de quatro vias usando uma pilha para armazenamento

Mover a recursão para uma estrutura de dados (uma pilha ou uma fila ) evita um estouro de pilha. É semelhante à solução recursiva simples, exceto que, em vez de fazer chamadas recursivas, ela empurra os nós em uma pilha ou fila para consumo, com a escolha da estrutura de dados afetando o padrão de proliferação: 

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.

Outras otimizações potenciais

  • Verifique e defina a cor de pixel de cada nó antes de adicioná-lo à pilha / fila, reduzindo o tamanho da pilha / fila.
  • Use um loop para as direções leste / oeste, enfileirando pixels acima / abaixo conforme você avança. (Tornando-o semelhante aos algoritmos de preenchimento de intervalo, abaixo.)
  • Intercalar duas ou mais cópias do código com pilhas / filas extras, para permitir que os processadores OoO tenham mais oportunidade de paralelizar
  • Use vários tópicos (de preferência com pedidos de visita ligeiramente diferentes, para que não fiquem na mesma área)

Vantagens

  • Algoritmo muito simples - fácil de fazer sem bugs.

Desvantagens

  • Usa muita memória, especialmente ao usar uma pilha.
  • Testa a maioria dos pixels preenchidos um total de quatro vezes.
  • Não é adequado para preenchimento de padrão, pois exige que os resultados do teste de pixel sejam alterados.
  • O padrão de acesso não é compatível com o cache, para a variante de enfileiramento.
  • Não é possível otimizar facilmente para palavras com vários pixels ou bitplanes.

Span Preenchimento

Preenchimento Scanline

É possível otimizar ainda mais as coisas trabalhando principalmente com spans. O primeiro exemplo completo publicado funciona com o seguinte princípio básico. Começando com um ponto de semente, você preenche à esquerda e à direita e controla as bordas. Em seguida, você escaneia a mesma parte da linha acima e a linha abaixo, procurando por novos pontos de origem para continuar. Este algoritmo é o mais popular, tanto para citações quanto para implementações, apesar de testar a maioria dos pixels preenchidos três vezes no total. Na 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

Com o tempo, as seguintes otimizações foram realizadas:

  • Quando uma nova varredura estaria inteiramente dentro do intervalo de um avô, certamente encontraria apenas pixels preenchidos e, portanto, não precisaria ser enfileirada.
  • Além disso, quando uma nova varredura se sobrepõe a um vão do avô, apenas as saliências (curvas em U e W) precisam ser examinadas.
  • É possível preencher durante a varredura de sementes

O preenchimento final combinado de varredura e preenchimento foi então publicado em 1990 e procede da seguinte forma (embora a versão aqui corrija alguns bugs no 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

Vantagens

  • 2x-8x mais rápido do que o algoritmo recursivo de pixel.
  • O padrão de acesso é compatível com cache e plano de bits.
  • Pode desenhar uma linha horizontal em vez de definir pixels individuais.

Desvantagens

  • Ainda visita os pixels que já foram preenchidos. (Para o algoritmo popular, três varreduras da maioria dos pixels. Para o último, apenas fazer varreduras extras de pixels onde houver buracos na área preenchida.)
  • Não é adequado para preenchimento de padrão, pois exige que os resultados do teste de pixel sejam alterados.

Adicionando Suporte de Preenchimento de Padrão

Duas maneiras comuns de fazer com que o span e os algoritmos baseados em pixels suportem o preenchimento de padrão são usar uma cor única como preenchimento simples e, em seguida, substituí-la por um padrão ou manter o controle (em uma matriz booleana 2d ou como regiões) de quais pixels foram visitados, usando-o para indicar que os pixels não podem mais ser preenchidos. Inside deve então retornar false para esses pixels visitados.

Preenchimento teórico de grafos

Alguns teóricos aplicaram a teoria dos grafos explícita ao problema, tratando vãos de pixels, ou agregados de tais como nós, e estudando sua conectividade. O primeiro algoritmo de teoria de grafos publicado funcionou de maneira semelhante ao preenchimento de span, acima, mas tinha uma maneira de detectar quando duplicaria o preenchimento de vãos. Infelizmente, ele tinha bugs que o impediam de completar alguns preenchimentos. Um algoritmo corrigido foi publicado posteriormente com uma base semelhante na teoria dos grafos; no entanto, ele altera a imagem à medida que avança, para bloquear temporariamente os loops em potencial, complicando a interface programática. Um algoritmo publicado posteriormente dependia do limite ser distinto de tudo o mais na imagem e, portanto, não é adequado para a maioria dos usos; também requer um bit extra por pixel para contabilidade.

Vantagens

  • Adequado para preenchimento de padrão, diretamente, uma vez que nunca retesta pixels preenchidos.
  • Dobre a velocidade do algoritmo de amplitude original, para preenchimentos descomplicados.
  • O padrão de acesso é compatível com cache e plano de bits.

Desvantagens

  • Regularmente, um intervalo deve ser comparado a todos os outros 'frontais' na fila, o que retarda significativamente os preenchimentos complicados.
  • Alternar entre a teoria dos gráficos e os domínios dos pixels complica o entendimento.
  • O código é bastante complicado, aumentando as chances de bugs.

Preenchimento baseado em caminhada (método de memória fixa)

Existe um método que usa essencialmente nenhuma memória para quatro regiões conectadas , fingindo ser um pintor tentando pintar a região sem pintar a si mesmo em um canto. Este também é um método para resolver labirintos. Os quatro pixels que formam o limite primário são examinados para ver qual ação deve ser tomada. O pintor pode se encontrar em uma das várias condições:

  1. Todos os quatro pixels de limite são preenchidos.
  2. Três dos pixels de limite são preenchidos.
  3. Dois dos pixels de limite são preenchidos.
  4. Um pixel de limite é preenchido.
  5. Pixels de limite zero são preenchidos.

Onde um caminho ou limite deve ser seguido, a regra da mão direita é usada. O pintor segue a região colocando a mão direita na parede (o limite da região) e progredindo em torno da borda da região sem retirar a mão.

Para o caso # 1, o pintor pinta (preenche) o pixel em que o pintor está e interrompe o algoritmo.

Para o caso # 2, existe um caminho que conduz para fora da área. Pinte o pixel em que o pintor está e mova-se na direção do caminho aberto.

Para o caso # 3, os dois pixels de limite definem um caminho que, se pintarmos o pixel atual, pode nos impedir de voltar para o outro lado do caminho. Precisamos de uma "marca" para definir onde estamos e em que direção estamos indo para ver se algum dia voltaremos exatamente ao mesmo pixel. Se já tivermos criado essa "marca", preservamos nossa marca anterior e passamos para o próximo pixel seguindo a regra da mão direita.

Uma marca é usada para o primeiro limite de 2 pixels que é encontrado para lembrar onde a passagem começou e em que direção o pintor estava se movendo. Se a marca for encontrada novamente e o pintor estiver viajando na mesma direção, o pintor sabe que é seguro pintar o quadrado com a marca e continuar na mesma direção. Isso ocorre porque (por meio de algum caminho desconhecido) os pixels do outro lado da marca podem ser alcançados e pintados no futuro. A marca é removida para uso futuro.

Se o pintor encontra a marca, mas está indo em uma direção diferente, então algum tipo de laço ocorreu, que fez com que o pintor voltasse para a marca. Este loop deve ser eliminado. A marca é apanhada e o pintor então prossegue na direção indicada anteriormente pela marca usando uma regra da mão esquerda para o limite (semelhante à regra da mão direita, mas usando a mão esquerda do pintor). Isso continua até que uma interseção seja encontrada (com três ou mais pixels de limite aberto). Ainda usando a regra da mão esquerda, o pintor agora procura uma passagem simples (feita por dois pixels de limite). Ao encontrar esse caminho de limite de dois pixels, esse pixel é pintado. Isso interrompe o loop e permite que o algoritmo continue.

Para o caso # 4, precisamos verificar os cantos 8-conectados opostos para ver se eles estão preenchidos ou não. Se um ou ambos forem preenchidos, isso criará uma interseção de muitos caminhos e não poderá ser preenchido. Se ambos estiverem vazios, o pixel atual pode ser pintado e o pintor pode se mover seguindo a regra da mão direita.

O algoritmo troca tempo por memória. Para formas simples, é muito eficiente. No entanto, se a forma é complexa com muitos recursos, o algoritmo gasta uma grande quantidade de tempo traçando as bordas da região tentando garantir que tudo possa ser pintado.

Este algoritmo foi disponibilizado comercialmente pela primeira vez em 1981 em um sistema de processamento de imagem Vicom fabricado pela Vicom Systems, Inc. Um algoritmo de caminhada foi publicado em 1994. O algoritmo de preenchimento de inundação recursivo clássico também estava disponível no sistema Vicom.

Pseudo-código

Esta é uma implementação em pseudocódigo de um algoritmo ideal de inundação de memória fixa escrito em inglês estruturado:

As variáveis
  • cur, markE mark2cada uma, quer de pixel coordenadas ou um valor nulo
    • NOTA: quando marké definido como nulo, não apaga seu valor de coordenada anterior. Mantenha essas coordenadas disponíveis para serem recuperadas, se necessário.
  • cur-dir, mark-dire mark2-dircada um mantém uma direção (esquerda, direita, para cima ou para baixo)
  • backtracke findloopcada um contém valores booleanos
  • count é um inteiro
O algoritmo
NOTA: Todas as direções (frente, trás, esquerda, direita) são 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

Vantagens

  • Uso constante de memória.

Desvantagens

  • O padrão de acesso não é compatível com cache ou plano de bits.
  • Pode passar muito tempo percorrendo os loops antes de fechá-los.

Implementações de vetor

A versão 0.46 do Inkscape inclui uma ferramenta de preenchimento de balde, fornecendo saída semelhante às operações de bitmap comuns e, na verdade, usando uma: a tela é renderizada, uma operação de preenchimento é realizada na área selecionada e o resultado é então rastreado de volta a um caminho. Ele usa o conceito de uma condição de limite .

Veja também

links externos

Referências

  1. ^ a b c Smith, Alvy Ray (1979). Preenchimento de tonalidade . SIGGRAPH '79: Anais da 6ª conferência anual sobre computação gráfica e técnicas interativas. pp. 276–283. doi : 10.1145 / 800249.807456 .
  2. ^ a b Ackland, Bryan D; Weste, Neil H (1981). O algoritmo de sinalizador de borda - um método de preenchimento para telas de varredura raster . Transações IEEE em computadores (Volume: C-30, Edição: 1). pp. 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). Uma Análise e Algoritmo para Propagação de Preenchimento . Imagens geradas por computador: The State of the Art Proceedings of Graphics Interface '85. pp. 56-76. doi : 10.1007 / 978-4-431-68033-8_6 .
  4. ^ Newman, William M; Sproull, Robert Fletcher (1979). Principles of Interactive Computer Graphics (2ª ed.). McGraw-Hill. p. 253. ISBN 978-0-07-046338-7.
  5. ^ Pavlidis, Theo (1982). Algoritmos para processamento de imagens e gráficos . Springer-Verlag. p. 181. ISBN 978-3-642-93210-6.
  6. ^ a b c d e f g h i Levoy, Marc (1982). Algoritmos de inundação de área . SIGGRAPH 1981 Notas do curso de Animação Computadorizada Bi-Dimensional.
  7. ^ Foley, JD; van Dam, A; Feiner, SK; Hughes, SK (1990). Computação Gráfica: Princípios e Prática (2ª ed.). Addison – Wesley. pp. 979–982. ISBN 978-0-201-84840-3.
  8. ^ Heckbert, Paul S (1990). "IV.10: Um algoritmo de preenchimento de sementes". Em Glassner, Andrew S (ed.). Gemas gráficas . Academic Press. pp. 275–277. ISBN 0122861663.
  9. ^ a b Lieberman, Henry (1978). Como colorir um livro para colorir . SIGGRAPH '78: Anais da 5ª conferência anual sobre computação gráfica e técnicas interativas. pp. 111–116. doi : 10.1145 / 800248.807380 .
  10. ^ a b c Shani, Uri (1980). Preenchendo regiões em imagens binárias raster: Uma abordagem da teoria dos gráficos . SIGGRAPH '80: Anais da 7ª conferência anual sobre computação gráfica e técnicas interativas. pp. 321–327. doi : 10.1145 / 800250.807511 .
  11. ^ a b Pavlidis, Theo (1981). Preenchimento de contorno em gráficos raster . SIGGRAPH '81: Anais da 8ª conferência anual sobre computação gráfica e técnicas interativas. pp. 29–36. doi : 10.1145 / 800224.806786 .
  12. ^ Henrich, Dominik (1994). Preenchimento de região com espaço eficiente em gráficos raster . O computador visual. pp. 205–215. doi : 10.1007 / BF01901287 .