Skip to content Skip to navigation Skip to collection information

OpenStax_CNX

You are here: Home » Content » Elaborazione di Media in Processing » Signal Processing in Processing: Miscellanea

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Signal Processing in Processing: Miscellanea

Module by: Davide Rocchesso, Pietro Polotti. E-mail the authors

Summary: Argomenti vari ed effetti nell'elaborazione di immagini e suoni.

Rappresentazioni economiche del colore

In Media Representation in Processing abbiamo visto come vengano riservati 8 8 bit a ciascun canale corrispondente ad un colore primario. Se a questi si aggiunge il canale alpha, abbiamo un totale di 32 32 bit per pixel. Non sempre ci possiamo permettere una così elevata occupazione di memoria per i colori, e quindi si ricorre a diverse strategie per ridurre il numero di bit per pixel.

Palette

Una prima soluzione viene dall'osservazione che in una immagine sono raramente presenti tutti i 224 2 24 colori rappresentabili. Supponendo che i colori utili per una immagine siano in numero non superiore a 256 256, si può pensare di memorizzarne le codifiche in una tabella (palette, o tavolozza), ai cui elementi si può accedere mediante un indice di soli 8 8 bit. Quindi l'immagine avrà una occupazione di memoria pari a 8 8 bit per pixel più lo spazio necessario per la palette. Per un esempio e ulteriori delucidazioni si veda color depth in Wikipedia.

Dithering

In alternativa, per mantenere basso il numero di bit per pixel, si può applicare un artificio di elaborazione, chiamato dithering. L'idea è quella di ottenere la mescolanza dei colori per via percettiva, per prossimità di piccoli punti di colore diverso. Una esauriente presentazione del fenomeno è presente alla voce dithering della Wikipedia.

Dithering di Floyd-Steinberg

L'algoritmo di Floyd-Steinberg è una delle tecniche più popolari per la distribuzione di pixel colorati a scopo di dithering. Esso minimizza gli artefatti visivi mediante un processo di errore-diffusione. L'algoritmo si può riassumere come segue:

  • Procedendo dall'alto al basso, e da sinistra a destra, per ogni pixel considerato
    • Si calcoli la differenza tra il colore che si vuole e il più vicino colore rappresentabile (errore)
    • Si diffonda l'errore sui pixel adiacenti secondo la maschera 116( 000 0X7 351 ) 1 16 0 0 0 0 X 7 3 5 1 . Cioè, al pixel alla destra di quello considerato X X si aggiungano 716 7 16 dell'errore, al pixel sotto a sinistra si aggiungano 316 3 16 dell'errore, eccetera.
Con questo algoritmo è possibile riprodurre una immagine a diversi livelli di grigio mediante un dispositivo in grado di produrre solo punti bianchi e neri. La maschera dell'algoritmo di Floyd-Steinberg è stata scelta in modo che una distribuzione uniforme di grigio di intensità 12 1 2 produce un pattern a scacchiera.

Exercise 1

Si realizzi, mediante un programma Processing che elabori il file, una versione in bianco e nero "dithered" della celebre Lena. L'immagine, elaborata solo nella metà di sinistra, dovrebbe risultare quella di Figura 1

Figura 1
Figura 1 (lena_dithered.png)

Solution



size(300, 420); 
PImage a;  // Declare variable "a" of type PImage 
a = loadImage("lena.jpg"); // Load the images into the program 
image(a, 0, 0); // Displays the image from point (0,0) 
 
int[][] output = new int[width][height]; 
for (int i=0; i<width; i++)
  for (int j=0; j<height; j++) {
    output[i][j] = (int)red(get(i, j)); 
    }
int grayVal;
float errore;
float val = 1.0/16.0;
float[][] kernel = { {0, 0, 0}, 
                     {0, -1, 7*val}, 
                     {3*val, 5*val, val }}; 

for(int y=0; y<height; y++) { 
  for(int x=0; x<width; x++) { 
    grayVal = output[x][y];// (int)red(get(x, y));
    if (grayVal<128) errore=grayVal;
      else errore=grayVal-256;
    for(int k=-1; k<=1; k++) { 
      for(int j=-1; j<=0 /*1*/; j++) { 
        // Reflect x-j to not exceed array boundary 
        int xp = x-j; 
        int yp = y-k; 
        if (xp < 0) { 
          xp = xp + width; 
        } else if (x-j >= width) { 
          xp = xp - width;  
        } 
        // Reflect y-k to not exceed array boundary 
        if (yp < 0) { 
          yp = yp + height; 
        } else if (yp >= height) { 
          yp = yp - height; 
      }
      output[xp][yp] = (int)(output[xp][yp] + errore * kernel[-j+1][-k+1]);
      } 
    } 
  } 
} 
 
for(int i=0; i<height; i++)  
  for(int j=0; j<width; j++) 
    if (output[j][i] < 128) output[j][i] = 0;
    else output[j][i] = 255; 
    
// Display the result of dithering on half image
loadPixels(); 
for(int i=0; i<height; i++) { 
  for(int j=0; j<width/2; j++) { 
    pixels[i*width + j] = 
      color(output[j][i], output[j][i], output[j][i]);
  } 
} 
updatePixels(); 

Rappresentazioni economiche del suono

Nel caso di segnali audio, l'uso del dithering ha lo scopo di ridurre l'effetto percettivo dell'errore prodotto dai cambiamenti di quantizzazione, che normalmente si effettuano quando si registrano e poi si elaborano dei segnali audio. Per esempio, quando si registra della musica, lo si fa solitamente con una quantizzazione superiore ai 16-bit. Inoltre le eventuali operazioni matematiche (anche delle semplici variazioni di dinamica) applicate al segnale richiedono un ulteriore aumento della profondità in bit, ovvero del numero di bit impiegati. Nel momento in cui però si giunge al prodotto finale, il CD audio, il numero di bit di quantizzazione deve essere ridotto a 16. In questi processi successivi di ri-quantizzazione si introduce ogni volta un errore, che si accumula. Nel caso di una riduzione del numero di bit, si può ricorrere ad un troncamento (nel caso in cui le cifre decimali vengano trascurate e messe a zero) oppure ad un arrotondamento (nel caso in cui il numero decimale sia approssimato con la cifra intera più vicina). In entrambi i casi si introduce dell'errore. In particolare, quando si ha a che fare con segnali con un pitch (altezza) ben definito (come nel caso della musica), l'errore diventa di tipo periodico. Nell'esempio della voce dithering della Wikipedia risulta chiaro quale sia il motivo di questa aggiunta di rumore periodico, ovvero armonico. Dal punto di vista percettivo questa distorsione dà luogo ad un ronzio che "segue" il pitch del suono, che risulta piuttosto fastidioso all'ascolto.

Nel caso dell'audio, quindi, il dithering ha la funzione di trasformare questo ronzio in un rumore di fondo di tipo fruscio, meno fastidioso all'ascolto. In Figura 2 viene riportato l'esempio di alcuni periodi della forma d'onda di un clarinetto quantizzata a 16 bit. Il risultato di una riduzione del numero di bit a 8 è riportato in Figura 3. Si vede chiaramente come le riduzione dei livelli di quantizzazione determina dei tratti ad ampiezza costante. L'applicazione del dithering determina un'ulteriore trasformazione che, come si vede in Figura 4 "rompe" i tratti costanti mediante introduzione di rumore bianco. Le Figura 5, Figura 6 ed Figura 7 rappresentano le trasformate di Fourier rispettivamente dei suoni di Figura 2, Figura 3 e Figura 4. Anche nella rappresentazione in frequenza è visibile come il passaggio ad una quantizzazione a 8 bit introduca delle armoniche spurie (Figura 6) rispetto al suono a 16 bit (Figura 5), che vengono cancellate dall'effetto del dithering (Figura 7).

Figura 2
Figura 2 (Clarinetto.png)
Figura 3
Figura 3 (Clarinetto8.png)
Figura 4
Figura 4 (Clarinetto8dith.png)
Figura 5
Figura 5 (FT-Clarinetto.png)
Figura 6
Figura 6 (FT-Clarinetto8.png)
Figura 7
Figura 7 (FT-Clarinetto8dith.png)

Esistono inoltre dei metodi, che, sfruttando fattori percettivi quali il fatto che il nostro orecchio è più sensibile nella regione centrale della banda audio e meno nella regione acuta, permettono di rendere meno udibile l'effetto di una riquantizzazione. E' il caso del noise shaping. Come dice il nome, tale tecnica consiste nel "modellare" il rumore di quantizzazione. In Figura 8 viene riportato il suono di clarinetto riquantizzato a 8 bit a cui oltre al dithering è stato applicato un algoritmo di noise-shaping. Il risultato, apparentemente devastante sulla forma d'onda, corrisponde in realtà ad un suono il cui spettro è molto più vicino a quello del suono originale a 16 bit fatta eccezione per un notevole aumento di energia nella regione molto acuta (Figura 9). Tale rumore ad alta frequenza determina questo "arruffamento" della forma d'onda. ovvero delle intense variazioni di ampiezza ad alta frequenza. Questo rumore però non è udibile quindi il risultato finale risulta migliore dei precedenti all'ascolto.

Figura 8
Figura 8 (Clarinetto8dithNS.png)
Figura 9
Figura 9 (FT-Clarinetto8dithNS.png)
Dal punto di vista operativo, si può pensare al noise shaping come ad un analogo audio dell'algoritmo di Floyd-Steinberg per la grafica. Nel caso audio la propagazione dell'errore avviene però nel tempo anziché nello spazio. La forma più semplice di noise shaping si può ottenere mediante definizione dell'errore di quantizzazione
en=ynQyn e n y n Q y n
(1)
dove
yn=xn+en1 y n x n e n 1
(2)
e x x è il segnale non quantizzato. Ulteriori dettagli sul noise shaping si possono trovare presso la noise shaping di Wikipedia. Quanto detto è verificabile negli esempi sonori clarinetto , clarinetto a 8 bit, clarinetto a 8bit con dithering e clarinetto a 8 bit con noise shaping che contengono rispettivamente i suoni di clarinetto relativi alle Figura 2, Figura 3, Figura 4, e Figura 8.

Elaborazioni basate sull'istogramma.

Definition 1: Istogramma di una immagine
Rappresentazione grafica a barre verticali, in cui ciascuna barra rappresenta il numero di pixel presenti nell'immagine per una data intensità di grigio (o canale di colore). Definizione Wikipedia.

Tra gli esempi di Processing, si trova il codice Histogram che sovrappone ad una immagine il proprio istogramma.

L'istogramma offre una rappresentazione sintetica della immagine in cui si perde l'informazione inerente la posizione dei pixel e contano solo gli aspetti cromatici. Esso fornisce informazioni sulla gamma tonale di una immagine (quali intensità di grigio sono presenti) e sulla sua dinamica (estensione della gamma tonale). L'immagine di una scacchiera, per esempio, avrà una gamma tonale che comprende solo due intensità di grigio (bianco e nero) ma avrà gamma dinamica massima (in quanto il bianco e il nero sono le due estremità della gamma dei grigi rappresentabile).

L'istogramma costituisce il punto di partenza per quelle elaborazioni che mirano ad equilibrare o alterare il contenuto cromatico di una immagine. In generale, si tratta di costruire una mappa g o =f g i g o f g i per i livelli di grigio (o di canale-colore) da applicare per ogni pixel. L'istogramma può guidare la costruzione di tale mappa.

Traslazione ed espansione dell'istogramma

Se la mappa è del tipo g o = g i +k g o g i k l'istogramma risulta traslato verso una maggiore o minore brillantezza a seconda del segno di k k. Invece, se la mappa è del tipo g o =k g i g o k g i l'istogramma risulterà espanso o compresso, per valori di k k rispettivamente minori o maggiori di 1 1.

Tra questo tipo di operazioni di scaling lineare rientra il contrast stretching, il quale cerca di estendere la gamma dinamica di una immagine. L'intervallo di valori sul quale basare lo scalamento viene scelto sulla base dell'istogramma, ad esempio lasciando fuori le code della distribuzione corrispondenti al 10 % 10% dei pixel più chiari e più scuri.

Scaling non lineare

Più in generale, la mappa g o =f g i g o f g i può essere non-lineare, e ciò consente una maggiore flessibilità nella manipolazione dell'istogramma. Un utile strumento è quello che consente di manipolare interattivamente la mappa di scaling e di vedere subito i risultati sull'immagine e/o sull'istogramma. Lo strumento Color Tools/Curvesdel programma di elaborazione di immagini Gimp fa proprio questo, usando una spline interpolante. In Processing è possibile costruire uno strumento simile, come riportato in Esempio 1

Equalizzazione dell'istogramma

Lo scaling non lineare è il mezzo per equalizzare l'istogramma, cioè per fargli assumere una forma desiderabile. Una immagine ha una gamma tonale equilibrata se tutti i livelli di grigio sono rappresentati e se la distribuzione è grossomodo uniforme. Cioè, si aspira ad avere un istogramma piatto. Senza entrare troppo a fondo nei dettagli matematici si può dire che la mappa nonlineare da usarsi per l'equalizzazione è ottenuta dalla distribuzione cumulata dell'istogramma dell'immagine f g i = k =0 g i hk f g i k 0 g i h k , dove hk h k è la frequenza, opportunamente scalata per una costante di normalizzazione, con cui compare il k k-esimo livello di grigio.

Exercise 2

Si modifichi il codice Processing del Esempio 1 per aggiungere la operazione di equalizzazione dell'istogramma.

Solution



int grayValues = 256;
int[] hist = new int[grayValues]; 
int[] histc = new int[grayValues];
PImage a; 

void setup() {
  background(255);
  stroke(0,0,0);
  size(300, 420); 
  colorMode(RGB, width); 
  framerate(5);
  a = loadImage("lena.jpg"); 
  image(a, 0, 0);
}

void draw() {
    // calculate the histogram 
  for (int i=0; i<width; i++) { 
    for (int j=0; j<height; j++) { 
      int c = constrain(int(red(get(i,j))), 0, grayValues-1);
      hist[c]++;
    } 
  } 

  // Find the largest value in the histogram 
  float maxval = 0; 
  for (int i=0; i<grayValues; i++) { 
    if(hist[i] > maxval) { 
      maxval = hist[i]; 
    }  
  } 

  // Accumulate the histogram
  histc[0] = hist[0];
  for (int i=1; i<grayValues; i++) { 
    histc[i] = histc[i-1] + hist[i];    
  } 
  
  // Normalize the histogram to values between 0 and "height" 
  for (int i=0; i<grayValues; i++) { 
    hist[i] = int(hist[i]/maxval * height); 
  } 

  if (mousePressed == true) { //equalization
    for (int i=1; i<grayValues; i++) { 
    println(float(histc[i])/histc[grayValues-1]*256);
    } 
    loadPixels();
    println("click");
    for (int i=0; i<width; i++)
      for (int j=0; j<height; j++) {
        //normalized cumulated histogram mapping
        pixels[i+j*width] = color(
          int(
          float(histc[constrain(int(red(a.get(i,j))), 0, grayValues-1)])/
            histc[grayValues-1]*256)); 
      }
    updatePixels();
     }
 
  // Draw half of the histogram 
  stroke(50, 250, 0); 
  strokeWeight(2);
  for (int i=0; i<grayValues; i++) { 
    line(i, height, i, height-hist[i]); 
  } 
}

Estrazione di contorni e segmentazione

Contorni

Gli oggetti che popolano una scena rappresentata in una immagine sono usualmente individuabili dai loro contorni: profili filiformi che corrispondono ad una rapida variazione di colore o di intensità di grigio. L'estrazione dei contorni è una delle operazioni tipiche dell'elaborazione di immagini. In analisi matematica, una rapida variazione di una funzione corrisponde ad un picco della funzione derivata. In elaborazione del segnale a tempo (e spazio) discreto, la derivata si può approssimare come operazione alle differenze, cioè come un filtro. I filtri che lasciano passare le variazioni repentine ed eliminano le variazioni lente sono di tipo passa-alto. Non stupisce quindi che per l'estrazione di contorni si usino maschere di convoluzione simili a quella vista in Elementary Filters per l'edge crispening. Più correttamente, si può dire che in 2D si cercano i punti di massima ampiezza del gradiente, che necessariamente sono punti in cui si annulla il laplaciano della immagine, cioè la derivata seconda spaziale. Il laplaciano può essere approssimato (a spazio discreto) mediante la maschera di convoluzione ( 010 1-41 010 ) 0 1 0 1 -4 1 0 1 0 . L'applicazione diretta del laplaciano è spesso non soddisfacente, in quanto il risultato è troppo sensibile al rumore e ai piccoli dettagli. E' quindi consigliabile combinare la maschera laplaciana con quella di un filtro passa-basso. La combinazione di laplaciano e filtro gaussiano (LoG) produce, nel caso 5 5 per 5 5, la maschera ( 00-100 0-1-2-10 -1-216-2-1 0-1-2-10 00-100 ) 0 0 -1 0 0 0 -1 -2 -1 0 -1 -2 16 -2 -1 0 -1 -2 -1 0 0 0 -1 0 0 Nel programma Gimp è anche reallizzato un evidenziatore di contorni basato sulla differenza tra due filtraggi gaussiani, basati su due gaussiane di ampiezza diversa, che fa in modo che intervenga un effetto di inibizione al di fuori dai contorni principali, in modo simile a quanto sembra avvenire nel nostro sistema sensoriale.

Regioni

In molte applicazioni è necessario isolare i diversi oggetti che popolano una scena, a partire dalle loro rappresentazioni come collezioni di pixel in una immagine. Ad esempio, può essere interessante isolare un oggetto in primo piano (foreground) dallo sfondo (background). In questo caso si parla di segmentazione o di estrazione di regioni. La maniera più semplice per isolare delle regioni è quella di farlo sulla base del colore, o dell'intensità di grigio. Anche in questo caso, l'operazione può essere guidata dall'istogramma, che può aiutarci a stabilire una soglia (threshold) di grigio. Tutti i pixel più scuri della soglia saranno mappati sul nero, e tutti i più chiari saranno mappati sul bianco. Ad esempio, se l'istogramma presenta due gobbe evidenti, ed è possibile attribuire una gobba al foreground (perché, per esempio, più chiaro) e l'altra gobba al background (perché, per esempio, più scuro), la soglia andrà scelta a metà tra le due gobbe. Talvolta è necessario stabilire una molteplicità di soglie, in modo da isolare regioni con diverse gamme di grigio. Per le immagini a colori, le soglie possono essere diverse nei diversi canali RGB.

Exercise 3

Si applichi il filtro laplaciano e il filtro LoG all'immagine di Lena.

Exercise 4

Si mostri come l'estrazione di figura da sfondo mediante threshold possa essere realizzata mediante una mappa non lineare g o =f g i g o f g i . Che forma deve avere questa mappa?

Solution

E' una mappa a gradino, con transizione da 0 0 a 255 255 collocata in corrispondenza della soglia scelta.

Exercise 5

Si utilizzi un programma per l'elaborazione di immagini (es., Gimp) per isolare (mediante soglia) le fratture nella immagine del vetro rotto.

Compressione di dinamica audio

Così come nel caso delle immagini, anche nell'audio si pone il problema della riduzione dei dati necessari per rappresentare un suono, pur mantenendo una qualità accettabile dal punto di vista percettivo. Cosa si intenda per "qualità accettabile" quando si riducono o, meglio, si comprimono i dati è cosa da stabilire. In genere i parametri di valutazione qualitativa degli standard di compressione audio sono di tipo statistico, basati sui risultati di test di ascolto fatti su di un campionario di ascoltatori, rappresentativi di una vasta gamma di utenti. Gli standard di compressione audio in genere si basano sull'ottimizzazione della dinamica del segnale, ovvero sull'ottimizzazione del numero di bit impiegati per la quantizzazione. Un ben noto esempio di standard di compressione è quello dell'mp3, nel quale vengono sfruttati fenomeni di psicoacustica, quali il fatto che i suoni forti mascherano (rendono inudibili) i suoni deboli. Nella riproduzione di suoni digitalizzati, quello che si vuole mascherare è il rumore di quantizzazione. Quindi, detto in modo molto semplificato, se il suono ha dinamica ampia (è forte) si può usare un passo di quantizzazione maggiore, in quanto il più intenso rumore di quantizzazione prodotto dalla suddivisione più grossolana dei livelli di quantizzazione è comunque mascherato dal suono riprodotto. Sempre semplificando in modo radicale le cose, si può dire che l'mp3 varia il passo di quantizzazione seguendo l'andamento della dinamica del segnale e in modo diverso in diverse bande di frequenza, permettendo così una riduzione anche di 20 volte il numero di dati rispetto ad una rappresentazione a dinamica fissa a 16 bit. Un'altra tecnica di compressione è data dalla mu-law (μ-law). Questo standard è utilizzato soprattutto nei sistemi audio e di comunicazione digitale in America del nord e in Giappone. In questo caso l'idea di base è di modificare il range dinamico di un segnale audio analogico prima della quantizzazione. Anche in questo caso ciò che giustifica questa tecnica di compressione è un fenomeno di psicoacustica, ovvero il fatto che la nostra percezione dell'intensità non è lineare ma di tipo logaritmico, il che significa che segue approssimativamente un andamento come quello mostrato in Figura 10.

Figura 10
Figura 10 (Loudness.png)

Ciò che fa la mu-law è dunque ridurre il range dinamico del segnale mediante un'operazione di riscalamento delle ampiezza secondo la mappa descritta in Figura 11. Come si vede, l'effetto è quello di amplificare le ampiezze basse, riducendo il range di valori assunti dal segnale (prevalentemente valori alti di ampiezza) e incrementando pertanto il rapporto (la differenza di ampiezza) tra il suono che vogliamo riprodurre e il rumore di quantizzazione. Successivamente si effettua una quantizzazione lineare del segnale che è stato preliminarmente distorto in modo non lineare. Nel momento in cui si vuole riprodurre il segnale digitale, questo viene prima normalmente convertito in segnale analogico e poi trasformato mediante una curva di distorsione delle ampiezze che controbilanci la distorsione pre-quantizzazione di Figura 11. Il risultato globale, entro certi limiti, è vicino a quello di una quantizzazione del segnale non distorto. Cambiando punto di vista, si può pensare all'intero processo come ad una quantizzazione di tipo non lineare del suono, ovvero una quantizzazione dove il passo è maggiore (più grossolano) per le ampiezze maggiori e minore (più dettagliato) per le ampiezze minori. Il che, almeno da un punto di vista qualitativo, corrisponde esattamente a come funziona il nostro sistema percettivo. Siamo più sensibili alle differenze di intensità tra suoni deboli e meno sensibili alle differenze tra suoni forti e molto forti. Molto simile alla mu-law è la A-law usata invece nei sistemi digitali in Europa.

Figura 11
Figura 11 (mu-law.png)

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks