I dispositivi elettronici negli ultimi anni hanno aumentato la capacità di elaborazione in modo esponenziale; proprio come aveva predetto la Legge di Moore. Questo ha permesso di realizzare circuiti integrati sempre più complessi, più veloci e meno dispendiosi a livello energetico. Il risultato è stato il passaggio di tutte le comunicazioni da analogiche a digitali.

Nella vita reale ogni misurazione “analogica” può avere qualsiasi valore, cioè, possiamo aumentare a piacere il range di misura (nei limiti tecnologici). Nei sistemi binari (es: computer, smartphone, fotocamere…) invece, i valori che qualsiasi dato può assumere sono 2N, con N sono i bit usati per descrivere un valore.

Nel passaggio dal mondo analogico a quello digitale si ha una perdita di informazione con aggiunta di rumore. Per diminuire questo rumore (o errore) si continua ad aumentare i bit per descrive ogni dato.

 

quantizzazione

Quantizzazione a 4 valori, cioè a 22  (N=2)

Aumentando il numero di bit sarà necessario aumentare i dati da immagazzinare, alzando i costi in termini di risorse del sistema. Una soluzione efficace (e usata) è quella di quantizzare il segnale ad una risoluzione maggiore (con più bit), con sistemi professionali, per poi passare, con alcuni algoritmo appositi, ad una più bassa per poterlo memorizzare e/o trasmettere.

Quantizzare ad alta risoluzione sembra uno spreco di risorse in questo caso, ma è qui che gli algoritmi che coinvolgono il Dithering entrano in gioco.

Nel passaggio da un maggior risoluzione ad una minore, bisogna eliminare i bit meno significativi (es. passaggio da 16 bit a 10 bit).

 

1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 1
← bit più significativi  bit meno significativi →

 

Sia nel troncamento dei bit meno significativi che nell’arrotondamento, la quantizzazione aggiunge un rumore che può essere correlato con il segnale. Questo introduce una distorsione che dipendono molto dal segnale originale soprattutto in caso di segnali continui ad ampiezza piccola. [1]

Prime applicazioni: Seconda Guerra Mondiale.

Gli algoritmi di Dithering aggiungono un rumore causale e statisticamente non correlato con il segnale in ingresso, questo permette di diminuire le distorsioni causate dalla quantizzazione e/o dal troncamento perché elimina la correlazione nella decisione presa. Il prezzo è quello di inserire del rumore casuale più distribuito.

La prima applicazione la cito direttamente da wikipedia perché secondo me è molto carina:

…uno dei primi [usi] del dithering avvenne durante la Seconda Guerra Mondiale. I bombardieri usarono i computer meccanici per orientarsi e calcolare la traiettoria delle bombe.

Curiosamente, questi computer (scatole riempite con centinaia d’ingranaggi e ruote dentate) funzionavano più accuratamente quando erano impiegati a bordo degli aerei, e meno al suolo.

Gli ingegneri capirono che la vibrazione prodotta dall’aereo riduceva l’errore causato dai componenti viscosi in movimento. Invece di muoversi a scatti, si muovevano con maggiore continuità.

Vennero inseriti piccoli motorini all’interno dei computer, con l’intenzione di farli vibrare, e queste vibrazioni vennero chiamate ‘dither’, termine preso dal verbo anglosassone “didderen”, che significava ‘tremare’.

Oggi, quando si dà un colpetto ad un contatore meccanico per aumentarne l’accuratezza, si sta applicando del dithering, ed i moderni dizionari inglesi definiscono “dither” come ‘stato di elevato nervosismo, confusione o agitazione’. In seguito il dithering rese i sistemi digitali leggermente più analogici, nel senso buono del termine.

Cit. (Ken Pohlmann, Principles of Digital Audio, quarta edizione, pagina 46)

 

Campo audio: noise shaping.

Nel campo audio, in sala di registrazione, i segnali vengono campionati con risoluzione di 32bit ad altre frequenze di campionamento (es. 192 KHz), questo permette di avere un master di qualità molto alta.

Questo master, viene poi ridotto alla qualità CD-audio (risoluzione 16 bit, frequenza di campionamento 44,10 KHz) utilizzando il Noise shaping.

Cito wikipedia perché lo descrive molto bene:

Il noise shaping può essere sfruttato per manipolare la distribuzione dell’errore di quantizzazione, in modo tale che si concentri maggiormente al di fuori dello spettro dell’udibile.

Il risultato è una notevole riduzione dell’errore di quantizzazione sulle bande critiche, per effetto della maggiore concentrazione del rumore sulle bande alle quali l’orecchio è meno sensibile… [2]

Qui sotto trovate un video preso da You Tube, in cui viene convertito un segnale audio con solo 4 bit, la versione con il dither risulta più rumorosa, ma allo stesso tempo più vicino all’originale.

 

 

Nella parte finale di questo articolo trovare alcuni audio che vengono trattati con il noise shaping, in cui si sente molto meno il rumore di fondo.

 

Image processing: algoritmo di Floyd-Steinberg.

Nelle immagini per limitare l’occupazione, soprattutto quando vengono usate per siti web, il numero di colori utilizzabili risulta essere limitato. Questo porta alla perdita della qualità nell’immagine. Applicando il dithering si limita questa perdita.

In questo campo l’algoritmo dithering più famoso è l’algoritmo di Floyd-Steinberg [3]. Una della più importanti implementazioni risiede nel formato GIF. Quando nel formato viene limitato il numero di colori, per ridurre il rumore prodotto da questa limitazione, l’errore di quantizzazione viene diffuso sui pixel più vicini. Più specificamente 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.

 

1 2 3

 

Nelle precedenti tre immagini, (prese da wikipedia), la prima è la foto originale, nella secondo è stata applicata una tavolozza limitata (web-safe color palette), mentre la terza è stata creata applicando l’algoritmo di Floyd-Steinberg con lo stesso numero limitato di colori della seconda rimanendo comunque più fedele all’originale

Se il numero di colori viene alzato a 256, con l’algoritmo di Floyd-Steinberg otteniamo questo risultato:

 

4

 

Un possibile sviluppo risulta applicare lo stesso metodo anche nel campo temporale, come descritto in questa pubblicazione:

 

5

Ho trovato anche questa implementazione in JavaScript dell’algoritmo ad un video in cui si può limitare il numero di colori a 8, con risultati a dir poco sorprendenti pensando cosa si può fare con questi pochi colori.

Il dithering si applica anche a campi non audiovisivi come:

  • Inverter: dispositivi elettronici usati per le conversioni DC/AC (essenziali per i pannelli solari), riducendo le emissioni elettromagnetiche prodotte. [4]
  • Fibre ottiche: utilizzato per limitare gli effetti ottici non lineari.

Curosità: l’immagine della Playmate Lenna (la foto principale), diventata uno “standard” nei test di compressione delle immagine, fu pubblicata per le prima volta nella tesi di master all’MIT, in cui veniva discusso applicazione del dithering. [5]