Implementazione riempimento Flood

Question

Questa è la mia implementazione in C# di un algoritmo di riempimento flood basato su stack (che ho basato sulla definizione di wikipedia). Prima mentre scrivevo, volevo solo vederlo funzionare. E lo ha fatto. Quindi, volevo sapere il numero di pixel che era in realtà riempito. Quindi nel mio codice, ho cambiato il tipo restituito in int e restituito la variabile "ctr". Ma poi ctr si è rivelato essere circa il doppio del numero effettivo di pixel pieni (ho creato una funzione separata con il solo scopo di contare quei pixel - solo per sapere per certo).

Qualcuno può chiarire come e perché la variabile "ctr" viene incrementata due volte come avrebbe dovuto?

* La classe Pixel funge solo da contenitore per i valori x, ye dei colori dei pixel dalla bitmap.

public Bitmap floodfill(Bitmap image, int x, int y, Color newColor) 
{ 
    Bitmap result = new Bitmap(image.Width, image.Height); 
    Stack<Pixel> pixels = new Stack<Pixel>(); 
    Color oldColor = image.GetPixel(x, y); 
    int ctr = 0; 

    pixels.Push(new Pixel(x, y, oldColor)); 

    while (pixels.Count > 0) 
    { 
     Pixel popped = pixels.Pop(); 

     if (popped.color == oldColor) 
     { 
      ctr++; 
      result.SetPixel(popped.x, popped.y, newColor); 

      pixels.Push(new Pixel(popped.x - 1, popped.y, image.GetPixel(x - 1, y)); 
      pixels.Push(new Pixel(popped.x + 1, popped.y, image.GetPixel(x + 1, y)); 
      pixels.Push(new Pixel(popped.x, popped.y - 1, image.GetPixel(x, y - 1)); 
      pixels.Push(new Pixel(popped.x, popped.y + 1, image.GetPixel(x, y + 1)); 
     } 
    } 

    return result; 
} 

Answer 1

che fai controllare il colore del pixel qui:

if (popped.color == oldColor) 

Ma popped.color possono essere (e apperently è nel 50% dei casi) obsoleti. Poiché non controlli i duplicati quando inserisci pixel nel tuo stack, avrai duplicati. Dopo aver inserito questi duplicati, l'attributo color sarebbe stato salvato molto tempo fa.

Forse ottiene più chiaro con un disegno:

Come esempio ho preso un bitmap con 9 pixel. Sul primo riquadro hai la numerazione dei pixel e sul lato destro hai il tuo stack.

Si inizia con il pixel n. 5. e si spinge i pixel 2, 4, 6 e 8 in pila. Quindi togli il pixel 2 e premi 1 e 3. Nel passaggio successivo premi 1 e premi 2 e 4 (ancora!). Quindi puoi prendere 2 e rendersi conto che ha già ottenuto il nuovo colore quando è stato premuto. (Un po 'tardi, ma meglio tardi che mai) tuttavia: pixel no. 4 è lì due volte e ha ricordato il vecchio colore due volte. Quindi prendi il pixel n. 4 e coloralo.

Alcuni passaggi dopo l'immagine è stata riempita e alcuni elementi sono ancora presenti nello stack. Poiché il vecchio valore del colore è ancora memorizzato all'interno di questi articoli, viene nuovamente conteggiato.

Mentre posso avere un ordine errato nello stack, il punto rimane valido.

soluzione al vostro problema: rapido e sporco (perché ancora inefficiente)

if (image.GetPixel(popped.x, popped.y) == oldColor) 

conta pixel solo se il colore corrente è sbagliato, non il colore ricordato.

Consigliato: Controlla i tuoi pixel se hanno bisogno di colorare prima di spingerli in pila.

Answer 2

Se tutto il pixel è in attesa del colore passato al costruttore, non aggiornerà il colore dopo il riempimento del pixel, pertanto può incrementare ctr più di una volta per pixel.

Se si modifica Pixel per ottenere un puntatore all'immagine nel suo costruttore, è possibile rileggere il colore (cioè rendere a colori una proprietà get che legge il colore corrente) o tracciare le coordinate già riempite e non spingere quelli una seconda volta.

[Edit]

Nel caso in cui non era evidente dalla risposta accettata, GetPixel restituisce un colore - un tipo di valore. Consideralo come un int che codifica il valore RGB del pixel in quel momento.

Se si desidera eseguire un riempimento veloce, cercare un esempio di Graphics.FloodFill.

Se l'obiettivo è l'apprendimento, consiglio di copiare i dati delle immagini su un array per l'elaborazione e tornare indietro - la maggior parte degli algoritmi di immagine classici non sono molto divertenti con GetPixel().