Dithering

Il dithering, nella elaborazione numerica di segnali, è una forma di rumore con una opportuna distribuzione, che viene volontariamente aggiunto ai campioni con l'obiettivo di minimizzare la distorsione introdotta dal troncamento nel caso in cui si riquantizzino i campioni stessi. Il dithering viene usato abitualmente nell'elaborazione di segnali video e audio campionati e quantizzati. Il dithering non ha nulla a che vedere col jitter. È invece correlato con la risonanza stocastica in fisica, in cui la presenza di rumore stocastico aumenta la risposta di un segnale a perturbazioni esterne.^[1]

I primi studi teorici sulla quantizzazione delle ampiezze risalgono alla fine degli anni '50 del secolo scorso. Bernard Widrow, all'epoca al MIT e attualmente professore alla Stanford University, ha mostrato infatti che il processo di quantizzazione, dal punto di vista teorico, ha proprietà analoghe al campionamento del segnale, per cui è possibile estendere il teorema di Nyquist alla quantizzazione dei segnali.^[2]

Di fondamentale importanza per lo sviluppo delle teorie legate al dithering è un secondo lavoro in cui vengono dimostrati due teoremi che illustrano come la somma di rumore con una certa distribuzione al segnale quantizzato possa essere considerata in modo analogo al filtro antialiasing usato nel processo di campionamento temporale dei segnali.^[3]

Il concetto di dithering viene ulteriormente approfondito da Lawrence G. Roberts nella sua tesi di dottorato nel 1961, presso il MIT,^[4] nonostante egli non abbia usato il termine dither.

Il dithering viene spesso usato nei campi dell'audio e video digitali, dove serve per stimare le conversioni e (di solito in modo facoltativo) le trasformazioni di profondità di colore; viene utilizzato in molti settori differenti in cui il processo e l'analisi digitale sono necessari - specialmente nell'analisi delle forme d'onda. Tra i campi di utilizzo vi sono sistemi digitali quali audio digitale, video digitale, fotografia digitale, sismologia, radar, meteorologia ed altri ancora.

La premessa è che la quantizzazione e la ri-quantizzazione dei dati digitali genera errori (detti di quantizzazione). Se questo errore si ripete ed è correlato al segnale, se ne ottiene uno ciclico e matematicamente deterministico. In alcuni campi, soprattutto dove i recettori sono sensibili agli errori, il comportamento ciclico porta ad artefatti indesiderati. In questi ambiti, il dithering permette di avere artefatti non deterministici che quindi perdono la loro ciclicità. Il campo sonoro è un esempio primario: l'orecchio umano funziona allo stesso modo di una trasformata di Fourier, in cui individua singole frequenze. L'orecchio è particolarmente sensibile alla distorsione ovvero a frequenze addizionali che modificano il colore del suono. Questa sensibilità si può ridurre rendendo casuale il rumore su tutte le frequenze.

La versione finale di un brano audio che viene scritto digitalmente su di un compact disc, è tipicamente quantizzata a 16 bit per campione ma, grazie al processo di editing audio, i dati crescono in profondità quanto occorre. Più calcoli matematici svolgiamo, più il campione cresce in profondità: come se si trattasse di aggiungere, moltiplicare o dividere numeri decimali. Alla fine i dati digitali vengono riportati alla profondità iniziale (16 bit) per poter essere memorizzati su di un CD e distribuiti.

Esistono molti metodi che permettono di tornare ai canonici 16 bit. Ad esempio, si possono semplicemente troncare i bit in eccesso (troncamento). È anche possibile arrotondare i bit in eccesso al valore più prossimo. Ognuno di questi algoritmi, comunque, produce un imprevedibile errore nel risultato. Consideriamo, ad esempio, una forma d'onda composta dai seguenti valori:

1 2 3 4 5 6 7 8 

Se la riduciamo del 20% otteniamo questa sequenza:

0.8 1.6 2.4 3.2 4.0 4.8 5.6 6.4 

Troncando i valori otteniamo:

0 1 2 3 4 4 5 6 

Se invece li arrotondassimo avremmo:

1 2 2 3 4 5 6 6 

Se qualsiasi sequenza, compresa quella iniziale, viene processata moltiplicando i valori per 0.8 il risultato conterrà errori che saranno ovviamente ripetibili. Un'onda rappresentante la funzione di seno quantizzata al valore originario, ad esempio, comporterà lo stesso errore ogni volta che il suo valore sarà "3.4" visto che il risultato verrebbe abbassato di 0,4. Ogni volta che il valore è "5", l'errore dopo il processo sarà 0. In ogni caso, l'ammontare dell'errore cambierà continuamente al modificarsi dei valori. Il risultato ha un comportamento ciclico nell'errore, che mostra la sua frequenza addizionale sulla forma d'onda (distorsione armonica). L'orecchio è in grado di percepire questo errore sotto forma di frequenza addizionale.

Non possiamo evitare il riprodursi degli errori in questo procedimento. Prendere un numero a due cifre (4.8) e trasformarlo in uno ad una cifra (5) produce un errore, e questo è inevitabile. Quello che vogliamo fare è creare un sistema in cui l'errore non si ripeta al ripetersi dei valori.

Una plausibile soluzione potrebbe essere di prendere un numero a due cifre (4.8) ed arrotondarlo in una delle due direzioni. Ad esempio, lo arrotondiamo la prima volta a 5, la seconda a 4, e così via. In questo modo la media a lungo termine sarà 4.5, invece di 4, ed il valore sarà più simile a quello di partenza, 4.8. Questo metodo produce ancora un errore deterministico (nonostante sia più complicato). Ogni volta che troviamo il valore 4.8 l'errore sarà 0.2 o -0.8. Quindi il problema non è risolto.

Un'altra soluzione consiste nell'arrotondare il 4.8 in modo che quattro volte su cinque diventi 5, e l'altra diventi 4. In questo caso la media è esattamente 4.8 ma, sfortunatamente, l'errore è ancora deterministico, ed ancora l'orecchio lo percepisce (nonostante il sovracampionamento possa limitare il disturbo).

Questo ragionamento porta al dithering. Invece di arrotondare con una ciclicità predicibile, che succederebbe se lavorassimo in modo casuale? Possiamo arrotondare casualmente vincolando il totale in modo che l'80% delle volte venga arrotondato a 5, lasciando così la media a 4.8 ma generando un errore irriproducibile. Proprio questo è il cuore del dithering.

Calcoliamo una serie di numeri casuali compresi tra 0 e 0.9 (ad esempio: 0.6, 0.4, 0.5, 0.3, 0.7, etc.) e li aggiungiamo al risultato della nostra equazione. Due volte su dieci il risultato verrà troncato a 4 (se 0 o 0.1 vengono aggiunti a 4.8), mentre nei restanti casi il valore diverrà 5; ognuna di queste situazioni ha una possibilità del 20% di diventare 4 e dell'80% di diventare 5. A lungo andare la media sarà 4.8 e la quantizzazione dell'errore diverrà casuale. Il rumore così ottenuto è percepito meno dall'orecchio.

Per far comprendere al meglio la funzione del dithering, vengono messi a disposizione i seguenti file audio:

• 16-bit originale^ⓘ
• troncato a 6 bit^ⓘ
• dithering a 6 bit^ⓘ

Il dithering va aggiunto prima di qualsiasi quantizzazione o ri-quantizzazione al fine di prevenire comportamenti non lineari (distorsione); più bassa è la profondità di bit, più grande deve essere il dither. Il risultato sarà ancora distorto, ma la distorsione, essendo di natura casuale, viene ridotta a rumore. Qualsiasi processo di riduzione di bit dovrebbe aggiungere il dither alla forma d'onda prima di applicare la riduzione.

RPDF sta per "Rectangular Probability Density Function" (Funzione rettangolare di densità della probabilità), ed è equivalente al lancio di un dado. Ogni numero ha la stessa probabilità di uscire.

TPDF sta per "Triangular Probability Density Function" (Funzione triangolare di densità della probabilità), equivalente al lancio di due dadi. La somma dei dadi ha differenti probabilità d'uscita:

1/1 = 2

1/2 2/1 = 3

1/3 2/2 3/1 = 4

1/4 2/3 3/2 4/1 = 5

1/5 2/4 3/3 4/2 5/1 = 6

1/6 2/5 3/4 4/3 5/2 6/1 = 7

2/6 3/5 4/4 5/3 6/2 = 8

3/6 4/5 5/4 6/3 = 9

4/6 5/5 6/4 = 10

5/6 6/5 = 11

6/6 = 12

il 7 uscirà molto più spesso del 2 o del 12, e la relazione tra queste probabilità viene detta triangolare.

La PDF Gaussiana è equivalente al lancio di infiniti dadi. La relazione tra le probabilità dei risultati ha una forma a campana detta curva Gaussiana. Il dithering prodotto dalla PDF Gaussiana è quasi coincidente al rumore atmosferico naturale, il fruscio delle musicassette, ecc.

Il dithering colorato viene a volte descritto come quel dithering che è stato filtrato per differenziarsi dal rumore bianco. Alcuni algoritmi di dithering usano un rumore che possiede più energia nelle alte frequenze, e meno nella banda audio critica.

Il noise shaping non è in realtà un dithering, poiché consiste nel "modellare" il rumore, come dice il suo nome, spostandolo in zone dello spettro audio in cui è meno udibile. Normalmente viene associato al dithering, e quindi sposta appunto questo rumore. È tuttavia possibile anche usarlo senza dithering. In tal caso il rumore di ri-quantizzazione rimane distorto, ma viene spostato in zone dello spettro audio in cui è meno udibile.

Se il segnale da processare deve subire un ulteriore lavoro, dovrebbe essere usato il TPDF che ha l'ampiezza di due passi di quantizzazione (in modo che i valori calcolati varino tra -1 e +1 o, se vogliamo, tra 0 e 2). Se il dithering colorato viene usato come processo intermedio, la gamma di frequenze può sfumarsi in un'altra e diventare vagamente udibile.

Se il segnale da lavorare non deve essere ulteriormente processato (ovvero accettiamo direttamente il risultato del dithering) è conveniente usare il dithering colorato o il noise shaping, in grado di diminuire enormemente il livello del rumore udibile spostandone buona parte nell'area non critica.

Il dithering viene usato in computer grafica per creare l'illusione della profondità di colore in immagini dotate di una tavolozza limitata (quantizzazione del colore). In un'immagine sottoposta a dithering, i colori non disponibili vengono approssimati dalla distribuzione dei pixel colorati con le tinte disponibili. L'occhio umano percepisce la diffusione come un amalgama dei colori.^[7] Il dithering è simile alla tecnica chiamata halftone nella stampa in cui si usava un retino stocastico. Le immagini trattate con il dithering, particolarmente quelle in cui vengono usati pochi colori, possono spesso apparire granulari, o composte da puntini.

Ridurre la profondità del colore di un'immagine spesso causa effetti collaterali indesiderati. Se l'immagine originale è una fotografia, probabilmente i colori saranno migliaia, o addirittura milioni. Limitarne il numero fa, ovviamente, perdere qualità all'immagine.

Molti fattori possono modificare la qualità risultante, probabilmente il più significativo di questi è la "larghezza" della tavolozza usata. Ad esempio, un'immagine di alta qualità (Figura 1) può essere ridotta con una tavolozza a 256 colori (Web-safe colors). Se i colori dei pixel originali venissero semplicemente spostati nel colore "più vicino" tra quelli disponibili, non avremmo applicazione del dithering (Figura 2). Normalmente, questo approccio causa aree di colore uniforme e perdita di dettaglio, generando macchie di colore molto diverse dall'originale. Le aree sfumate appaiono a strisce (effetto banding). L'applicazione del dithering può aiutare a limitare questi artefatti visivi e, di solito, crea un'immagine più simile all'originale (Figura 3). Il dithering permette di ridurre il banding e la "piattezza" dei colori.

Uno dei problemi legati all'uso di tavolozze preimpostate è dato dal fatto che molti dei colori necessari non sono presenti, e molti di quelli presenti non sono necessari; una tavolozza che contenga molte sfumature di verde è controindicata se non usiamo il verde nell'immagine, ad esempio. In questi casi è indicato l'uso di tavolozze ottimizzate. In queste tavolozze i colori vengono scelti basandosi sulla loro frequenza nell'immagine originale. L'immagine ottenuta presenta ulteriori miglioramenti rispetto alla precedente (Figura 4).

Il numero di colori disponibili nella tavolozza è un dato importante. Se, ad esempio, è composta di soli 16 colori, l'immagine perderà altri dettagli, oltre ad un incremento dell'effetto banding (Figura 5). Ancora una volta, il dithering ci aiuta ad aggirare il problema (Figura 6).

• 
  Figura 1. Fotografia originale; notare la sfumatura del colore nel dettaglio.
• 
  Figura 2. Immagine originale a cui è stata applicata una tavolozza limitata (web-safe color palette) senza l'applicazione del dithering. Notare le ampie aree con colore uniforme e la perdita di dettagli.
• 
  Figura 3. Immagine originale con web-safe color palette e l'applicazione dell'algoritmo di Floyd-Steinberg. Anche se usiamo la stessa tavolozza, l'applicazione del dithering genera un'immagine più simile all'originale.
• 
  Figura 4. In questo caso, l'originale è stato ridotto ad una tavolozza ottimizzata a 256 colori, ed è stato applicato l'algoritmo di Floyd-Steinberg. L'uso di una tavolozza ottimizzata, piuttosto che di una preimpostata, permette di migliorare ulteriormente l'immagine.
• 
  Figura 5. Profondità ridotta a 16 colori (ottimizzati) e niente dithering. Il colore appare a strisce.
• 
  Figura 6. Stessa immagine, 16 colori ottimizzati, ma viene applicato il dithering per ridurre il banding (effetto a strisce).

Tutti i display hardware, comprese le vecchie schede video dei primi computer o i moderni schermi LCD fino alle fotocamere digitali, sono in grado di mostrare un limitato numero di colori rispetto alle periferiche più avanzate. Uno degli usi del dithering permette di mostrare immagini di qualità su schermi che non lo sono. Ad esempio, possiamo visualizzare immagini in truecolor su schermi in grado di mostrare solo 256 colori alla volta. I colori disponibili verranno usati per generare "un'approssimazione" dell'immagine originale. Il dithering sfrutta i vantaggi dell'occhio umano, che tende a miscelare due colori se sono posti troppo vicini (acutezza visiva).

Questo uso del dithering, in cui gli schermi dei computer sono la principale limitazione, viene fatto nel campo del software come i web browser. Dal momento che il browser raccoglie immagini da fonti esterne, può essere necessario operare il dithering su quelle troppo "profonde". A causa di questo problema, venne definita una tavolozza standard chiamata Web-safe palette, che raggruppa i colori visualizzabili su tutti gli schermi, a prescindere dal sistema operativo o dal browser utilizzati.

Un altro utile impiego del dithering è in quelle situazioni in cui il formato dei file grafici è il fattore limitante. In particolare, il comunissimo GIF utilizza al massimo 256 colori in molti software di editing. Le immagini in altri formati, come il PNG, possono avere restrizioni imposte dalla volontà di limitare la dimensione del file. Questo genere di immagini ha una tavolozza predefinita contenente i colori utilizzabili all'interno dell'immagine. In questi casi, i programmi di editing possono sobbarcarsi il compito di applicare il dithering prima di salvare le immagini nel loro formato.

Esistono molti algoritmi creati per l'applicazione del dithering. Uno dei primi, ed ancora tra i più popolari, è l'algoritmo di Floyd-Steinberg, sviluppato nel 1975. Uno dei punti di forza di questo algoritmo è la sua capacità di minimizzare gli artefatti visivi attraverso un processo di diffusione dell'errore; solitamente produce immagini più simili all'originale rispetto a quanto fatto da altri algoritmi similari.

Gli altri metodi comprendono:

• Dithering ponderato (Average dithering): una delle tecniche più semplici, è basata sulla selezione di un colore "medio" e sull'assegnazione di colore ai pixel in base a quanto sono "distanti" da lui
• Dithering ordinato (Ordered dithering): produce un risultato simile a quello ottenuto nella stampa delle riviste attraverso l'uso dell'halftone
• Dithering casuale (Random dithering): aggiunge un elemento casuale ad ogni pixel, creando l'immagine
• Dithering di Albie (Albie dithering): metodo simile al Floyd-Steinberg, ma ottimizzato per la visualizzazione su schermi interlacciati
• Dithering di Jarvis (Jarvis dithering): vedi l'immagine a lato per un esempio

Lo Stimulated Brillouin Scattering (SBS) è un effetto ottico non lineare che limita la potenza ottica utilizzata nei sistemi in fibra ottica. Il segnale trasmesso può essere manipolato con il dithering al fine di limitare il "rumore" trasmesso.

Il termine dithering è usato in fotografia astronomica digitale con un significato molto diverso. Quando si eseguono riprese a posa molto lunga (foto di galassie, nebulose, ammassi stellari, ecc.) è pratica comune suddividere la posa in sequenze di scatti, che vengono poi "fusi" nell'immagine finale mediante software appositi. Per esempio, 12 scatti da 10 minuti generano un'immagine simile a quella che si otterrebbe con 120 minuti di posa continua (suddividere la posa in più scatti brevi porta una serie di vantaggi, tanto che questa metodologia è standard). Il dithering consiste nello spostare leggermente lo strumento tra uno scatto e il successivo, in modo che eventuali difetti del sensore non si presentino in tutti i singoli scatti nello stesso punto dell'immagine. Ciò permette di cancellare questi difetti dall'immagine finale, mediante l'elaborazione che si esegue dopo le riprese. Di norma il sistema di controllo del telescopio si occupa in automatico di questa operazione, spostando di pochissimo lo strumento (in una direzione casuale) tra uno scatto e l'altro, ovviamente prima di riaprire l'otturatore per lo scatto successivo.

• (EN) Aldrich, Nika. "Dither Explained (pdf)"
• (EN) Aldrich, Nika. "Digital Audio Explained"
• (EN) Katz, Bob. The Secrets of Dither"
• (EN) Katz, Bob, Mastering Audio, su digido.com. URL consultato il 6 agosto 2021 (archiviato dall'url originale l'8 ottobre 2006).

• Audio digitale
• Video digitale
• Algoritmo di Floyd-Steinberg
• Comando di valvole proporzionali in Pulse-width modulation
• Risonanza stocastica

• Wikimedia Commons contiene immagini o altri file sul dithering

• (EN) DHALF.TXT (1991) analizza vari filtri basati sul Floyd-Steinberg.
• (EN) Cos'è il Dither? Articolo pubblicato su Australian HI-FI contenente esempi grafici di come il dithering audio riduca le distorsioni.

Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica