Riempimento: Riempimento: esplorazione del terreno dinamico della visione artificiale

Di Fouad Sabry

Che cos'è il Flood Fill

Il Flood Fill, chiamato anche seed fill, è un algoritmo di Flood 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 pittura 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 chiamata riempimento del confine utilizza gli stessi algoritmi ma è definita come l'area connessa a un dato nodo che non ha un attributo particolare.

Come trarrai vantaggio

(I) Approfondimenti e convalide sui seguenti argomenti:

Capitolo 1: Riempimento

Capitolo 2: Rendering della linea di scansione

Capitolo 3: Profondità -prima ricerca

Capitolo 4: Quadtree

Capitolo 5: Attraversamento del grafico

Capitolo 6: Etichettatura dei componenti connessi

Capitolo 7: Spartiacque (elaborazione delle immagini)

Capitolo 8: Algoritmo per la risoluzione dei labirinti

Capitolo 9: Ray casting

Capitolo 10: Sfocatura del riquadro

(II) Rispondere alle principali domande del pubblico sul riempimento delle inondazioni.

(III) Esempi reali dell'utilizzo del riempimento delle inondazioni in molti campi.

A chi è rivolto questo libro

Professionisti, studenti universitari e laureati, appassionati, hobbisti e coloro che desiderano andare oltre le conoscenze o le informazioni di base per qualsiasi tipo di riempimento.

 

 

• Lingua: Italiano
• Editore: Un Miliardo Di Ben Informato [Italian]
• Data di uscita: 4 mag 2024

Anteprima del libro

Capitolo 1: Riempimento flood

Il riempimento flood, noto anche come riempimento seed, è un algoritmo flooding che sceglie e modifica l'area in una matrice multidimensionale associata a un nodo specifico con un particolare attributo. Viene utilizzato in giochi come Go e Campo minato per determinare quali pezzi vengono eliminati, nonché nello strumento di riempimento secchio delle applicazioni di vernice per riempire le aree collegate, di colore simile, con una tonalità distinta. La regione connessa a un dato nodo ma priva di un attributo specifico è ciò che si intende con la variazione nota come riempimento del bordo, che impiega le stesse tecniche.

Tenete presente che il riempimento flood mancherà alcuni pixel negli angoli più acuti, rendendolo inadatto per il disegno di poligoni pieni. Controllare invece la regola diversa da zero e la regola pari-dispari.

Tre variabili sono richieste dal classico algoritmo flood-fill: un nodo iniziale, un colore di destinazione e un colore di sostituzione. Il metodo passa al colore sostitutivo per ogni nodo della matrice connesso al nodo iniziale da un percorso che è il colore di destinazione. Al posto del colore di destinazione, viene fornito un colore del bordo per un riempimento del contorno.

Invece, due routine verranno fornite nelle seguenti descrizioni per generalizzare il metodo nel modo consueto. Tra questi ci sono Set, che riempie un pixel o un nodo, e Inside, che restituisce true per i punti non riempiti che, in base al loro colore, si troverebbero all'interno dell'area riempita. Una volta che Set è stato chiamato su un nodo, deve lasciare l'interno.

Ci sono due versioni a seconda che si contino i nodi che si toccano agli angoli come connessi o meno: rispettivamente a otto vie e a quattro vie.

Di seguito è riportata la prima implementazione nota di flood-fill a quattro vie basata implicitamente sullo stack:

Riempimento-inondazione (nodo):

1. Se il nodo non è all'interno , restituisci.

2. Impostare il nodo

3. Eseguire il riempimento di inondazione di un passaggio a sud del nodo.

4. Eseguire  il riempimento alluvionale di un passaggio a nord del nodo

5. Eseguire  il riempimento alluvionale un passaggio a ovest del nodo

6. Eseguire  il riempimento alluvionale di un passaggio a est del nodo

7. Restituzione.

Nei linguaggi e nelle situazioni in cui lo spazio dello stack è estremamente limitato, l'implementazione della tecnica utilizzata sopra è semplice da comprendere ma impraticabile (ad esempio i microcontrollori).

Un overflow dello stack viene evitato spostando la ricorsione in una struttura di dati, ad esempio uno stack o una coda. La scelta della struttura dei dati influisce sul modello di proliferazione, ma è simile al metodo ricorsivo semplice in quanto inserisce i nodi in uno stack o in una coda per l'utilizzo anziché effettuare chiamate ricorsive:

Riempimento-inondazione (nodo):

1. Impostare Q sulla coda o sulla pila vuota.

2. Aggiungi nodo alla fine di Q.

3. Mentre Q non è vuoto:

4. Porre n uguale al primo elemento di Q.

5. Rimuovere il primo elemento da Q.

6. Se n è all'interno:

Impostare il n

Aggiungi il nodo a ovest di n alla fine di Q.

Aggiungi il nodo a est di n alla fine di Q.

Aggiungi il nodo a nord di n alla fine di Q.

Aggiungi il nodo a sud di n alla fine di Q.

7. Continuare il ciclo fino a quando Q non è esaurito.

8. Restituzione.

Prima di aggiungere un nodo allo stack o alla coda, determinare e impostare il colore dei pixel per ridurre al minimo le dimensioni dello stack o della coda.

Utilizza un loop per spostarti in direzione est-ovest mentre accodi i pixel sopra e sotto (rendendolo simile agli algoritmi di riempimento dell'intervallo, di seguito).

Per offrire ai processori out-of-order maggiori opportunità di parallelizzare, interfoliare due o più copie del codice con stack e code aggiuntivi.

Usa diversi thread, idealmente con orari di visita leggermente diversi, in modo che non si riuniscano in un unico posto.

Metodo semplice da creare e privo di bug.

Richiede molta memoria, soprattutto quando si utilizza uno stack.

Verifica i pixel più pieni quattro volte in totale.

Il riempimento del modello non è possibile poiché richiede la modifica dei risultati dei test dei pixel.

Il modello di accesso per la variante di accodamento non è compatibile con la cache.

Difficile da ottimizzare per bitplane o parole multi-pixel.

Lavorando in gran parte con le campate, una riga con y costante consente un'ulteriore ottimizzazione. Il primo esempio completo pubblicato opera secondo il seguente principio fondamentale:.

Riempite a sinistra e a destra dopo un punto di partenza. Tenere traccia dei punti riempiti più a sinistra e più a destra, rispettivamente lx e rx. In questo modo si stabilisce l'intervallo.

Cerca altri punti di partenza eseguendo la scansione da lx a rx sopra e sotto il punto di partenza corrente.

Il processo di analisi è ottimizzato in modo che solo i punti di partenza all'inizio dell'intervallo successivo debbano essere riavviati. Una coda esplora prima gli intervalli, mentre uno stack analizza prima gli intervalli in termini di profondità.

Nonostante controlli i pixel più pieni tre volte in totale, questo approccio è il più comune in termini di implementazioni e citazioni.

Riempimento FN (X, Y):

se non Inside(x, y) allora ritorna

let s = nuovo stack o coda vuota

Aggiungi (x, y) a s

mentre s non è vuoto:

Rimuovi un (x, y) da s

Sia lx = x

mentre all'interno (lx - 1, y):

Insieme(lx - 1, y)

lx = lx - 1

mentre all'interno(x, y):

Impostare(x, y)

x = x + 1

Scansione(LX, X - 1, Y + 1, S)

Scansione(LX, X - 1, Y - 1, S)

Scansione FN (LX, RX, Y, S):

let span_added = falso

per x in lx .. RX:

se non all'interno (x, y):

span_added = falso

altrimenti se non span_added:

Aggiungi (x, y) a s

span_added = vero

Nel corso del tempo sono stati apportati i seguenti miglioramenti:

Una nuova scansione non avrebbe bisogno di essere accodata se si trovasse interamente all'interno di un intervallo nonno perché rileverebbe solo i pixel pieni.

Inoltre, solo le sporgenze (inversioni a U e inversioni a W) devono essere scansionate quando una nuova scansione attraversa una campata nonna.

Puoi fare il pieno mentre cerchi i semi.

Riempimento FN (X, Y):

se non Inside(x, y) allora ritorna

let s = nuova coda o pila vuota

Aggiungi (x, x, y, 1) a s

Aggiungi (x, x, y - 1, -1) a s

mentre s non è vuoto:

Rimuovere un (x1, x2, y, dy) da s

Sia x = x1

se Interno(x, y):

mentre Interno(x - 1, y):

Insieme(x - 1, y)

x = x - 1

se x < x1:

Aggiungi (x, x1-1, y-dy, -dy) a s

mentre x1 <= x2:

mentre all'interno (x1, y):

Impostare(x1, y)

x1 = x1 + 1

Aggiungi (x, x1 - 1, y+dy, dy) a s

se x1 - 1 > x2:

Aggiungi (x2 + 1, x1 - 1, y-dy, -dy) a s

x1 = x1 + 1

mentre x1 < x2 e non Inside(x1, y):

x1 = x1 + 1

x = x1

più veloce della tecnica pixel-ricorsiva di 2-8 volte.

Compatibile con i modelli di accesso alla cache e al bitplane.

Invece di impostare i singoli pixel, è possibile disegnare una linea orizzontale.

fa ancora viaggi verso pixel già pieni. (L'algoritmo più comune