Algoritmo di Floyd-Steinberg

Esempio di un'immagine a 24 bit RGB (a sinistra) convertita in una a 3 bit RGB (a destra) usando l'algoritmo di dithering di Floyd-Steinberg

L'algoritmo di Floyd-Steinberg è un algoritmo di dithering pubblicato nel 1976 da Robert W. Floyd e Louis Steinberg. Viene usato nei programmi di manipolazione delle immagini grafiche, ad esempio quando si converte un'immagine nel formato GIF, limitata a 256 tonalità di colore.

Descrizione

Questo algoritmo compie il dithering diffondendo l'errore di quantizzazione di un pixel ai pixel vicini. Più specificamente, nell'algoritmo da essi proposto, l'errore di un pixel viene diffuso ai pixel circostanti in queste proporzioni: $7/16$ dell'errore viene sommato al pixel a destra, $3/16$ al pixel in basso a sinistra, $5/16$ al pixel sottostante, e $1/16$ al pixel in basso a destra.

${\begin{bmatrix}0&0&0\\0&0&{7 \over 16}\\{3 \over 16}&{5 \over 16}&{1 \over 16}\end{bmatrix}}$

Consideriamo ad esempio una matrice con i seguenti valori di pixel:

${\begin{bmatrix}0.00&0.00&0.00\\0.00&1.00&0.00\\0.00&0.00&0.00\end{bmatrix}}$

Se il valore centrale è quantizzato a zero e l'errore viene diffuso secondo l'algoritmo di Floyd-Steinberg, questo sarà il risultato:

${\begin{bmatrix}0.00&0.00&0.00\\0.00&0&0.44\\0.19&0.31&0.06\end{bmatrix}}$

Altro esempio di dithering di Floyd-Steinberg eseguito su un'immagine in bianco e nero di un particolare del David di Michelangelo

L'algoritmo esamina l'immagine da sinistra a destra e dall'alto verso il basso, quantizzando i valori dei pixel uno ad uno, trasferendo l'errore di quantizzazione di ogni pixel a quelli adiacenti, senza però coinvolgere quelli già quantizzati. Quindi se un certo numero di pixel è già stato arrotondato per difetto, è lecito attendersi che il prossimo pixel sia arrotondato verso l'alto, per cui la media della quantizzazione dell'errore è vicina a zero.

In alcune implementazioni la direzione orizzontale dell'analisi si alterna fra le righe (una riga verso destra, poi una verso sinistra e così via): questo modo è noto come "serpentine scanning" ("scansione a serpentina") o "dithering bustrofedico".

I coefficienti di diffusione hanno la proprietà che se i valori dei colori di partenza della tonalità del pixel sono esattamente uguali il risultato del dithering sarà un motivo a scacchiera. Ad esempio, il grigio 50% può generare un motivo a scacchiera bianco e nero.

Si noti che l'intero algoritmo può essere eseguito "in-place", invece di accumulare l'errore in un buffer separato.

Esempio di codice

Quello che segue è un esempio in pseudocode dell'algoritmo:

per ogni y dall'alto in basso
   per ogni x da sinistra a destra
      vecchio_pixel := pixel[x][y]
      nuovo_pixel := trova_il_colore_della_tavolozza_più_vicino(vecchio_pixel)
      pixel[x][y] := nuovo_pixel
      quant_errore := vecchio_pixel - nuovo_pixel
      pixel[x+1][y] := pixel[x+1][y] + 7/16 * quant_errore
      pixel[x-1][y+1] := pixel[x-1][y+1] + 3/16 * quant_errore
      pixel[x][y+1] := pixel[x][y+1] + 5/16 * quant_errore
      pixel[x+1][y+1] := pixel[x+1][y+1] + 1/16 * quant_errore

Per ottenere un buon risultato la quantizzazione degli errori dovrebbe avere un'accuratezza sufficiente a prevenire eventuali errori di arrotondamento che potrebbero influenzare l'immagine finale. Ad esempio, per convertire un'immagine a 16 bit in una ad 8 bit la funzione trova_il_colore_della_tavolozza_più_vicino() potrebbe eseguire una semplice operazione:

trova_il_colore_della_tavolozza_più_vicino(vecchio_pixel) = (vecchio_pixel + 128) / 256

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su Algoritmo di Floyd-Steinberg

Collegamenti esterni

• (EN) Image Quantization, Halftoning, and Dithering - Lezione passo-passo per l'apprendimento di Quantization, Halftoning, e Dithering
• (EN) Floyd-Steinberg Dithering - Descrizione ed immagini esemplificative