Signal Processing in Processing: Miscellanea
Summary: Argomenti vari ed effetti nell'elaborazione di immagini e suoni.
- Links
-
Supplemental links
Rappresentazioni economiche del colore
In Media Representation in
Processing abbiamo visto come vengano riservati
8
8 32
32
Palette
Una prima soluzione viene dall'osservazione che in una immagine sono raramente presenti tutti i
2 24
2
24
256 256
8 8 8
8
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:
1 2
1
2
- 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
X
Problem 1
Solution 1
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 detrmina 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 3 |
 Figura 4 |
 Figura 5 |
 Figura 6 |
 Figura 7 |
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.
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
e n = y n - Q y n
e
n
y
n
Q
y
n
y n = x n + e n - 1
y
n
x
n
e
n
1
x x
 Figura 8 |
 Figura 9 |
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
Traslazione ed espansione dell'istogramma
Se la mappa è del tipo
g
o
=
g
i
+ k
g
o
g
i
k
k k
g
o
= k
g
i
g
o
k
g
i
k k
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 %
Scaling non lineare
Più in generale, la mappa
g
o
= f
g
i
g
o
f
g
i
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, descritti nella guida
alla equalizzazione dell'istogramma insieme ad utili
informazioni pratiche, 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
h k
f
g
i
k
0
g
i
h
k
h k
h
k
k k
Problem 2
Si modifichi il codice Processing del Esempio 1 per aggiungere la operazione di
equalizzazione dell'istogramma.
Solution 2
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
0 1 0 1 -4 1 0 1 0
0
1
0
1
-4
1
0
1
0
5 5 5
5
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
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
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. Per un approfondimento e suggerimenti pratici si veda
la guida
al thresholding.
Problem 3
Si applichi il filtro laplaciano e il filtro LoG all'immagine di Lena.
Problem 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
Solution 4
E' una mappa a gradino, con transizione da
0 0 255
255
Problem 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 gamma 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 |
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 |
Comments, questions, feedback, criticisms?
Discussion forum
Send feedback
More about this content: Metadata | Version History | Cite This Content
This work is licensed by Davide Rocchesso e Pietro Polotti. See the Creative Commons License about permission to reuse this material.
Last edited by Davide Rocchesso on Jul 4, 2006 4:18 am GMT-5.