title: Algoritmo di Floyd-Steinberg
text: # Algoritmo 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}}$
  
  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 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:
  
  