Riempimento allagamento - Flood fill

Riempimento alluvionale ricorsivo con 4 direzioni

Flood fill , chiamato anche seed fill , è un algoritmo che determina e altera l'area connessa a un dato nodo in un array multidimensionale con qualche attributo corrispondente. Viene utilizzato nello strumento di riempimento "secchio" dei programmi di disegno per riempire aree collegate di colore simile con un colore diverso e in giochi come Go e Campo minato per determinare quali pezzi vengono eliminati. Una variante denominata riempimento limite utilizza gli stessi algoritmi ma è definita come l'area connessa a un dato nodo che non ha un particolare attributo.

Nota che il riempimento allagamento non è adatto per disegnare poligoni pieni, poiché mancherà alcuni pixel negli angoli più acuti. Invece, vedi Regola pari-dispari e Regola diversa da zero .

I parametri dell'algoritmo

Riempimento alluvionale ricorsivo con 8 direzioni

Il tradizionale algoritmo di riempimento richiede tre parametri: un nodo iniziale, un colore di destinazione e un colore sostitutivo. L'algoritmo cerca tutti i nodi nell'array che sono collegati al nodo iniziale da un percorso del colore di destinazione e li cambia nel colore sostitutivo. Per un riempimento del bordo, al posto del colore di destinazione, verrebbe fornito un colore del bordo.

Per generalizzare l'algoritmo nel modo comune, le seguenti descrizioni avranno invece a disposizione due routine. Uno chiamato Insideche restituisce vero per i punti non riempiti che, per il loro colore, sarebbero all'interno dell'area piena, e uno chiamato Setche riempie un pixel/nodo. Qualsiasi nodo che lo ha Setchiamato non deve più essere Inside.

A seconda che si considerino i nodi che si toccano agli angoli collegati o meno, abbiamo due varianti: rispettivamente a otto ea quattro vie.

Implementazione ricorsiva basata su stack (a quattro vie)

La prima implementazione di riempimento a quattro vie , implicitamente basata su stack, ricorsiva , è la seguente: 

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.

Sebbene di facile comprensione, l'implementazione dell'algoritmo utilizzato sopra è poco pratica in linguaggi e ambienti in cui lo spazio dello stack è fortemente limitato (ad es. Microcontrollori ).

Spostare la ricorsione in una struttura dati

Riempimento allagamento a quattro vie utilizzando una coda per l'archiviazione
Riempimento di allagamento a quattro vie utilizzando una pila per lo stoccaggio

Lo spostamento della ricorsione in una struttura dati (uno stack o una coda ) impedisce un overflow dello stack. È simile alla semplice soluzione ricorsiva, tranne per il fatto che invece di effettuare chiamate ricorsive, spinge i nodi su uno stack o una coda per il consumo, con la scelta della struttura dei dati che influenza il modello di proliferazione: 

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.

Ulteriori potenziali ottimizzazioni

  • Controlla e imposta il colore dei pixel di ciascun nodo prima di aggiungerlo allo stack/coda, riducendo le dimensioni dello stack/coda.
  • Usa un loop per le direzioni est/ovest, accodando i pixel sopra/sotto mentre procedi. (Rendendolo simile agli algoritmi di riempimento dello span, di seguito.)
  • Interlaccia due o più copie del codice con stack/code extra, per consentire ai processori OoO maggiori opportunità di parallelizzare
  • Usa più thread (idealmente con ordini di visita leggermente diversi, in modo che non rimangano nella stessa area)

Vantaggi

  • Algoritmo molto semplice - facile da rendere privo di bug.

Svantaggi

  • Utilizza molta memoria, in particolare quando si utilizza uno stack.
  • Verifica i pixel più riempiti per un totale di quattro volte.
  • Non adatto per il riempimento del motivo, poiché richiede la modifica dei risultati del test dei pixel.
  • Il modello di accesso non è compatibile con la cache, per la variante di accodamento.
  • Non è possibile ottimizzare facilmente per parole multi-pixel o bitplane.

Riempimento della campata

Riempimento scansione

È possibile ottimizzare ulteriormente le cose lavorando principalmente con gli span. Il primo esempio completo pubblicato funziona sul seguente principio di base. Partendo da un punto seme, riempi a sinistra e a destra e tieni traccia dei bordi. Quindi, scansiona la stessa porzione della linea sopra e la linea sotto, alla ricerca di nuovi seed-point con cui continuare. Questo algoritmo è il più popolare, sia per le citazioni che per le implementazioni, nonostante abbia testato la maggior parte dei pixel pieni tre volte in totale. In forma pseudo-codice: 

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

Nel tempo sono state realizzate le seguenti ottimizzazioni:

  • Quando una nuova scansione sarebbe interamente all'interno di un intervallo nonno, sicuramente troverebbe solo pixel pieni e quindi non avrebbe bisogno di accodamento.
  • Inoltre, quando una nuova scansione si sovrappone a una campata del nonno, devono essere scansionate solo le sporgenze (inversioni a U e inversioni a W).
  • È possibile riempire durante la scansione dei semi

Il riempitivo finale dell'intervallo di scansione e riempimento combinato è stato quindi pubblicato nel 1990 e procede come segue (sebbene la versione qui corregga alcuni bug nell'originale): 

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

Vantaggi

  • 2x-8x più veloce dell'algoritmo ricorsivo in pixel.
  • Il modello di accesso è compatibile con la cache e il bitplane.
  • Può disegnare una linea orizzontale invece di impostare singoli pixel.

Svantaggi

  • Visita ancora i pixel che ha già riempito. (Per il popolare algoritmo, 3 scansioni della maggior parte dei pixel. Per l'ultimo, eseguire solo scansioni extra di pixel dove ci sono buchi nell'area piena.)
  • Non adatto per il riempimento del motivo, poiché richiede la modifica dei risultati del test dei pixel.

Aggiunta del supporto per il riempimento del motivo

Due modi comuni per fare in modo che gli algoritmi basati su span e pixel supportino il riempimento del motivo sono utilizzare un colore univoco come riempimento semplice e quindi sostituirlo con un motivo o tenere traccia (in un array booleano 2D o come regioni) di quali pixel sono stati visitati, utilizzandolo per indicare che i pixel non sono più compilabili. Inside deve quindi restituire false per tali pixel visitati.

Riempimento grafico-teorico

Alcuni teorici hanno applicato la teoria dei grafi esplicita al problema, trattando intervalli di pixel, o aggregati di questi, come nodi e studiando la loro connettività. Il primo algoritmo pubblicato sulla teoria dei grafi funzionava in modo simile al riempimento degli span, sopra, ma aveva un modo per rilevare quando avrebbe duplicato il riempimento degli span. Sfortunatamente, aveva dei bug che gli impedivano di completare alcuni riempimenti. Un algoritmo corretto è stato successivamente pubblicato con una base simile nella teoria dei grafi; tuttavia, altera l'immagine mentre procede, per bloccare temporaneamente potenziali loop, complicando l'interfaccia programmatica. Un algoritmo pubblicato in seguito dipendeva dal fatto che il confine fosse distinto da tutto il resto nell'immagine e quindi non è adatto alla maggior parte degli usi; richiede anche un bit extra per pixel per la contabilità.

Vantaggi

  • Adatto per il riempimento del motivo, direttamente, poiché non esegue mai nuovamente il test dei pixel riempiti.
  • Raddoppia la velocità dell'algoritmo di span originale, per riempimenti semplici.
  • Il modello di accesso è compatibile con la cache e il bitplane.

Svantaggi

  • Regolarmente, uno span deve essere confrontato con ogni altro "fronte" nella coda, il che rallenta notevolmente i riempimenti complicati.
  • Passare avanti e indietro tra la teoria dei grafi e i domini dei pixel complica la comprensione.
  • Il codice è abbastanza complicato, aumentando le possibilità di bug.

Riempimento a camminata (metodo a memoria fissa)

Esiste un metodo che essenzialmente non utilizza alcuna memoria per le quattro regioni collegate fingendo di essere un pittore che cerca di dipingere la regione senza dipingersi in un angolo. Questo è anche un metodo per risolvere i labirinti. I quattro pixel che costituiscono il confine principale vengono esaminati per vedere quale azione dovrebbe essere intrapresa. Il pittore potrebbe trovarsi in una delle diverse condizioni:

  1. Tutti e quattro i pixel di contorno sono riempiti.
  2. Tre dei pixel di confine sono riempiti.
  3. Due dei pixel di confine sono riempiti.
  4. Un pixel di confine è riempito.
  5. I pixel del limite zero vengono riempiti.

Quando si deve seguire un percorso o un confine, viene utilizzata la regola della mano destra. Il pittore segue la regione appoggiando la mano destra sul muro (il confine della regione) e avanzando lungo il bordo della regione senza togliere la mano.

Per il caso n. 1, il pittore dipinge (riempie) il pixel su cui si trova il pittore e interrompe l'algoritmo.

Per il caso n. 2 esiste un percorso che porta fuori dall'area. Dipingi il pixel su cui si trova il pittore e muoviti nella direzione del percorso aperto.

Per il caso n. 3, i due pixel di confine definiscono un percorso che, se abbiamo dipinto il pixel corrente, potrebbe impedirci di tornare dall'altra parte del percorso. Abbiamo bisogno di un "segno" per definire dove siamo e in quale direzione stiamo andando per vedere se torniamo mai esattamente allo stesso pixel. Se abbiamo già creato un tale "segno", conserviamo il nostro segno precedente e ci spostiamo al pixel successivo seguendo la regola della mano destra.

Viene utilizzato un segno per il primo confine di 2 pixel che si incontra per ricordare dove è iniziato il passaggio e in quale direzione si stava muovendo il pittore. Se si incontra di nuovo il segno e il pittore sta viaggiando nella stessa direzione, allora il pittore sa che è sicuro dipingere il quadrato con il segno e continuare nella stessa direzione. Questo perché (attraverso un percorso sconosciuto) i pixel dall'altra parte del segno possono essere raggiunti e dipinti in futuro. Il marchio viene rimosso per un uso futuro.

Se il pittore incontra il segno ma sta andando in una direzione diversa, si è verificata una sorta di loop che ha fatto sì che il pittore tornasse al segno. Questo ciclo deve essere eliminato. Il segno viene prelevato, e il pittore procede quindi nella direzione indicata in precedenza dal segno utilizzando un regolo sinistro per il confine (simile al regolo destro ma usando la mano sinistra del pittore). Questo continua finché non viene trovata un'intersezione (con tre o più pixel di confine aperti). Sempre usando la regola della mano sinistra il pittore ora cerca un passaggio semplice (composto da due pixel di confine). Dopo aver trovato questo percorso di confine di due pixel, quel pixel viene dipinto. Questo interrompe il ciclo e consente all'algoritmo di continuare.

Per il caso n. 4, dobbiamo controllare gli 8 angoli collegati opposti per vedere se sono pieni o meno. Se uno o entrambi sono riempiti, questo crea un'intersezione a molti percorsi e non può essere riempito. Se entrambi sono vuoti, il pixel corrente può essere dipinto e il pittore può muoversi seguendo la regola della mano destra.

L'algoritmo scambia il tempo per la memoria. Per le forme semplici è molto efficiente. Tuttavia, se la forma è complessa con molte caratteristiche, l'algoritmo impiega molto tempo a tracciare i bordi della regione cercando di assicurarsi che tutto possa essere dipinto.

Questo algoritmo è stato disponibile per la prima volta in commercio nel 1981 su un sistema di elaborazione delle immagini Vicom prodotto da Vicom Systems, Inc. Un algoritmo di camminata è stato pubblicato nel 1994. Il classico algoritmo di riempimento ricorsivo era disponibile anche sul sistema Vicom.

Pseudocodice

Questa è un'implementazione in pseudocodice di un algoritmo di riempimento del flusso a memoria fissa ottimale scritto in inglese strutturato:

Le variabili
  • cur, mark, e mark2ciascuno contiene coordinate in pixel o un valore nullo
    • NOTA: quando markè impostato su null, non cancellare il suo precedente valore della coordinata. Tieni a disposizione quelle coordinate per essere richiamate se necessario.
  • cur-dir, mark-dir, e mark2-dirognuno tiene una direzione (sinistra, destra, su o giù)
  • backtracke findloopciascuno contiene valori booleani
  • count è un intero
L'algoritmo
NOTA: tutte le direzioni (anteriore, posteriore, sinistra, destra) sono relative 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

Vantaggi

  • Utilizzo costante della memoria.

Svantaggi

  • Il modello di accesso non è compatibile con la cache o il bitplane.
  • Può passare molto tempo a girare intorno ai loop prima di chiuderli.

Implementazioni vettoriali

La versione 0.46 di Inkscape include uno strumento di riempimento del secchio, che fornisce un output simile alle normali operazioni bitmap e in effetti ne utilizza uno: viene eseguito il rendering del canvas, viene eseguita un'operazione di riempimento dell'area selezionata e il risultato viene quindi ricondotto a un tracciato. Utilizza il concetto di condizione al contorno .

Guarda anche

link esterno

Riferimenti

  1. ^ a b c Smith, Alvy Ray (1979). Riempimento tinta . SIGGRAPH '79: Atti del VI Convegno annuale su Computer grafica e tecniche interattive. pp. 276-283. doi : 10.1145/800249.807456 .
  2. ^ a b Ackland, Bryan D; Weste, Neil H (1981). L'algoritmo edge flag — Un metodo di riempimento per le visualizzazioni di scansione raster . Transazioni IEEE sui computer (Volume: C-30, Numero: 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). Un'analisi e un algoritmo per la propagazione del riempimento . Immagini generate al computer: lo stato dell'arte degli atti dell'interfaccia grafica '85. pp. 56-76. doi : 10.1007/978-4-431-68033-8_6 .
  4. ^ Newman, William M; Sproull, Robert Fletcher (1979). Principi di computer grafica interattiva (2a ed.). McGraw Hill. P. 253. ISBN 978-0-07-046338-7.
  5. ^ Pavlidis, Theo (1982). Algoritmi per la grafica e l'elaborazione delle immagini . Springer-Verlag. P. 181. ISBN 978-3-642-93210-6.
  6. ^ a b c d e f g h i Levoy, Marc (1982). Algoritmi di inondazione dell'area . SIGGRAPH 1981 Appunti del corso di animazione computerizzata bidimensionale.
  7. ^ Foley, JD; van Dam, A; Feiner, SK; Hughes, SK (1990). Computer grafica: principi e pratica (2a ed.). Addison-Wesley. pp. 979–982. ISBN 978-0-201-84840-3.
  8. ^ Heckbert, Paul S (1990). "IV.10: Un algoritmo di riempimento del seme". In Glassner, Andrew S (ed.). Gemme grafiche . stampa accademica. pp. 275-277. ISBN 0122861663.
  9. ^ a b Lieberman, Henry (1978). Come colorare in un libro da colorare . SIGGRAPH '78: Atti del V Convegno annuale su Computer grafica e tecniche interattive. pp. 111-116. doi : 10.1145/800248.807380 .
  10. ^ a b c Shani, Uri (1980). Regioni di riempimento in immagini raster binarie: un approccio teorico dei grafi . SIGGRAPH '80: Atti del VII convegno annuale su Computer grafica e tecniche interattive. pp. 321-327. doi : 10.1145/800250.807511 .
  11. ^ a b Pavlidis, Theo (1981). Riempimento del contorno in grafica raster . SIGGRAPH '81: Atti dell'VIII convegno annuale su Computer grafica e tecniche interattive. pp. 29-36. doi : 10.1145/800224.806786 .
  12. ^ Henrich, Dominik (1994). Riempimento di aree efficienti in termini di spazio nella grafica raster . Il computer visivo. pp. 205-215. doi : 10.1007/BF01901287 .