Il dithering, nell'elaborazione numerica dei 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.
Storia I primi studi teorici sulla quantizzazione delle ampiezze risalgono alla fine degli anni '50 del XX secolo. 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.
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.B. Widrow, “Statistical analysis of amplitude quantized sampled-data systems” Trans. AIEE, Part. II, Vol.79, no. 52, pp.555-568, Jan. 1961
Il concetto di dithering viene ulteriormente approfondito da Lawrence G. Roberts nella sua tesi di dottorato nel 1961, presso il MIT,Lawrence G. Roberts, Picture Coding Using Pseudo-Random Noise, MIT, tesi di dottorato, 1961 online nonostante egli non abbia usato il termine dither.
Origine del termine "dither"
Il dither nel processo digitale e nell'analisi delle forme d'onda 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 e 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.
Audio digitale 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 a 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) e 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, e 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, e 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:
Quando aggiungere il dithering 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.
Differenti tipi di dithering "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.
Quale dithering usare 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.
Fotografia digitale e image processing
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.Per approfondire, vedi anche percezione del colore 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.
Esempi di dithering 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.