IEM-02-Seconda Parte Campionamento Quantizzazione

8/15/2019 IEM-02-Seconda Parte Campionamento Quantizzazione

1/50

Interazione & Multimedia

Una immagine è una matrice

Ogni singolo elemento della matrice è unPIXEL (picture element)

Su una immagine possono essere fatte tuttele operazioni che si possono fare sullematrici.

1


2/50


Prodotto

ATTENZIONE: per le matrici vale la regoladel prodotto riga per colonna, mentrenell’image processing si usa fare il prodotto

puntuale tra due matrici, cioè il prodottopunto a punto degli elementi corrispondenti.

2


3/50


Neighborhood N p

I vicini 4 connessi di undato pixel sono quelli allasua destra e sinistra e

quelli sopra e sotto.

I vicini 8 connessi sono

quelli 4 connessi a cui siaggiungono i 4 pixel indiagonale.

3


4/50

Interazione & Multimedia 4

Operazioni affini


5/50


Dove (u,v) è il pixel di input, (x,y) quello dioutput e T la matrice affine.

Per ottenere il valore

[x y 1] = [u w 1] * T

5


6/50


Forward mapping

In questo caso si fa scorrere l’immagine diinput e per ogni pixel (v,w) si calcola la

posizione della nuova immagine (x,y)

Inverse mapping

Visita le posizioni spaziali dei pixel di output

(x,y) e per ciascuna di esse calcola lecorrispondenti coordinate nell’immagine diinput (si ha una formula inversa)

6


7/50


Ovviamente

[u w 1] = [x y 1] * inversa(T)

7


8/50


Forward mapping A=rgb2gray(imread('lena.jpg'));

A=double(A);

figure,imshow(uint8(A)); [m,n]=size(A);

theta=-45;

B=zeros(size(A));

T=[cosd(theta) sind(theta) 0; -sind(theta) cosd(theta) 0; 0 0 1];

%scorre l'immagine di input e si stabilisce in quale punto finiranno i

%nostri pixel in output

for v=1:m

for w=1:n

vett=round([v w 1]*T);

x=vett(1);

y=vett(2);

if (x>0 & x0 & y


9/50


Inverse mapping (usato da Matlab) A=rgb2gray(imread('lena.jpg'));

A=double(A);

figure,imshow(uint8(A)); [m,n]=size(A);

theta=38;

B=zeros(size(A));

T=[cosd(theta) sind(theta) 0; -sind(theta) cosd(theta) 0; 0 0 1];

%scorre l'immagine di output

for x=1:m

for y=1:n

vett=round([x y 1]*inv(T));

v=vett(1);

w=vett(2);

if (v>0 & v0 & w


10/50


Combinazioni

Inoltre le trasformazioni affini si possonocombinare tra di loro semplicementemoltiplicando le corrispondenti matrici T.

theta=38;

tx=40;

ty=23;

cx=2;

cy=2;

Tr=[cosd(theta) sind(theta) 0; -sind(theta) cosd(theta) 0; 0 0 1];

Tt=[1 0 0; 0 1 0; tx ty 1];

Ts=[cx 0 0 ; 0 cy 0; 0 0 1];

T=Tr*Tt*Ts;

10


11/50


Valori non assegnati

Nel corso delle trasformazioni, potrebberoesserci dei valori di pixel che non sono maiindividuati dalle formule.

Per essi si applica un processo diinterpolazione.

11


12/50

Campionamento equantizzazione


13/50


Campionamento e quantizzazione

Dato un segnale continuo occorre scegliereun numero finito di “campioni” rappresentatividel segnale.

Il valore in ogni singolo punto del segnale èun numero reale, occorre scegliere dei valoridiscreti per rappresentare correttamente il

segnale.

13


14/50


Campionamento e quantizzazione

14


15/50


Campionamento


16/50


Un errore nel tasso di campionamento può

stravolgere un segnale in due modi:

a) Un campionamento troppo basso fa perdere dettagli edinformazioni; sebbene grave una tale perdita è spesso unanecessità: non possiamo conservare milioni di campioni e ciaccontentiamo di perdere informazioni pur di tenere il database

delle misure ottenute in dimensioni maneggevoli.

b) Un campionamento troppo basso può far apparire nellaimmagine dettagli NON PRESENTI nell’or iginale. Il segnaleviene “alterato” e cambiato in qualcosa di “altro”. Si parla di“aliasing”.

L’aliasing è un fenomeno sottile ma poiché esso è imprevedibilerichiede attenzione.


17/50


Come scegliere il giusto

campionamento?

Per scegliere il giusto valore dicampionamento si ricorre ad un teorema

fondamentale: il teorema di Shannon. Tale teorema si basa sulla misura della

frequenza di Nyquist.

Ma cos’è?

17


18/50


Nyquist rate (Harry Nyquist, 1928)

Si definisce Nyquist rate la più alta frequenzain un segnale continuo e limitato.

18


19/50


Non daremo una definizione rigorosa ma una “operativa” in 1D.La generalizzazione a 2d è immediata.

Si osservi un fenomeno che si svolge in un intervallo a…b

• Se il fenomeno è (approx) costante durante tutto l’intervallo, la frequenza di

Nyquist è 1: il fenomeno si svolge in un unico ciclo.• Altrimenti si divide l’intervallo in 2 parti e si controlla per ciascun intervallino ilfenomeno si mantiene (approx) costante (esso può però variare da intervallinoad intervallino).• Si procede in tal modo dividendo l’intervallo in 3, 4, … parti fino a trovare unasuddivisione tale che entro ciascun intervallino il fenomeno sia in pratica

costante.

Sia tale suddivisione in N parti. N si dice frequenza di Nyquist del fenomenosull’intervallo osservato.

Nyquist rate (in pratica)


20/50


Teorema del campionamento di

Shannon (Claude E. Shannon, 1949)

Se si raccolgono campioni con frequenzaalmeno doppia della frequenza di Nyquist (2Nnel nostro caso) il segnale può esserericostruito FEDELMENTE in ogni suo punto!

20


21/50


21

Diametro tratto: 4 pixel

Diametro tratto: 6 pixel

Applicazione alle immagini


22/50


Usiamo i tratti fini. La nostra “freq. di Nyquist” è allora: dimensione quadro 720 pixel, dettaglio massimo 4 pixel, possiamo dividere

l’intervallo in 720/4=180 tratti.

Il doppio della frequenza di Nyquist è 360. Prenderemo allora solo 360 campioni ericostruiremo con l’interpolazione binomiale l’immagine.

Ricostruita da 360 campioniOriginale

campionamento


23/50


Decidiamo di volere trascurare i tratti fini. La nostra ipotetica “freq. di Nyquist” è allora: dimensione quadro 720 pixel, dettaglio massimo 6 pixel, possiamo dividere

l’intervallo in 720/6=120 tratti.

Il doppio della frequenza di Nyquist è 240. Prenderemo allora solo 240 campioni ericostruiremo con l’interpolazione binomiale l’immagine.


campionamento


24/50


campionamento

Campioniamo NON al doppio della frequenzadi Nyquist

24



25/50


720 campioni 360 campioni

240 campioni 120 campioni


26/50


Esempio di campionamento usandoPhotoshop.

26


27/50


Sottocampionamento

Ma cosa succede se si campiona ad unafrequenza inferiore a quella di Nyquist?

Si perdono dei dettagli significativi e spesso

si introducono nuovi dettagli che non sonopresenti nella realtà.

27


28/50


Aliasing

Questo fenomeno è detto frequency aliasingo semplicemente aliasing

Con l’aliasing le alte frequenze sono

“mascherate” da basse frequenze e trattatecome tali nella fase di campionamento.

Aliasing proviene da Alias cioè falsa identità!

28


29/50


Segnale reale.

Campionamento “rado”

Ricostruzione per interpolazione (si perdono dettagli = alte frequenze)

Perdita di dettagli


30/50


CampionamentoUn pixel ogni 256

Ricostruzione coninterpolazione

bicubica

Si perdono dettagli, graffi e disegni sulle rocce sono divenutiindistinguibili e sono apparsi NUOVI dettagli!

a) Ovvie scalettature sui bordi dei sassi.

b) Fori che non erano presenti nell’originale!

Aliasing


31/50


originale

ricostruito

Se si fosse trattato di una onda sonora un suono acuto sarebbe

stato sostituito da un suono grave!Quanti campioni prendere per riprodurre un suono con fedeltàaccettabile? (passo essenziale per fare un CD!)

Aliasing


32/50


originale ricostruitoAppaiano nuovi inesistenti

dettagli (“artifacts”)

Aliasing


33/50

33

Animazione costruitacon tutti i campioni disponibili Animazione costruita

Usando un campione ogni 4

Animazione costruitaUsando un campione ogni 25

Essa viene percepita come retrograda!(Alias temporale: un movimento vienesostituito ad un altro!)


34/50


Aliasing

Nella realtà l’aliasing è sempre presenteanche se in condizioni minime.

Esso viene introdotto quando si impone che il

segnale sia limitato per essere campionato. L’aliasing può essere ridotto applicando una

funzione di smussamento sul segnale

originario prima del campionamento (anti-aliasing).

34


35/50


Aliasing

35


36/50


Moirè

36


37/50


Immagini reali da Facebook

37


38/50


Wagon wheel

Cercate i video su YouTube inserendo“wagon wheel aliasing”…

38


39/50

La quantizzazione


40/50


Quantizzazione

I sensori sono apparecchiatureanalogiche: forniscono misure diluminosità come numeri REALI.

È utile arrotondare tali valori.

Tale processo si chiamaQUANTIZZAZIONE

40


41/50


Quantizzazione

• In più le misure sono sempre soggette aERRORE a causa di difetti nel sensore odi perturbazioni termiche (“ rumore” ).

• Nei CCD anche a obiettivo chiuso ci sonocorrenti parassite che inducono rumoredentro i l dispositivo elettronico dette

“ dark current” .

41


42/50


Quantizzazione: procedura generale

Se i valori da quantizzare sono numeri reali nel range[a, b] e si vuole quantizzare su n livelli:

Si fissano n+1 numeri in [a, b]:

t0=a < t

1< t

2< … < t

n< t

n+1=b

Il numero x in [a,b] verrà assegnato al livello diquantizzazione k se risulta:

tk


43/50


Quantizzazione: diagramma

Livello 3: Q3

Livello 2: Q2

Livello 1: Q1

Livello 0: Q0

t0

t4

t3

t1

t2

Fissato il numero di livelli diquantizzazione si pone il problemadi come rappresentare in memoriatali livelli. Ovviamente ut ilizzeremodelle etichette numeriche.

Quanti b it sono necessari per

ricordare quale livello di luminositàsi misura in un punto?

Nell ’esempio ne bastano 2 = log(4)

In generale se ci sono N livellioccorre rappresentare N etichettenumeriche e avremo bisogno di un

numero di bit pari a:B = log (N)


44/50


Tipi di quantizzazione

l i v e l l i

a b

l i v e l l i

a b

uniforme

Non uniforme


45/50


La quantizzazione

La quantizzazione effettuata dagli scanner commerciali e dallafotocamere digitali è non uniforme e logaritmica:ciò permette di assegnare più livelli nella area dei toni scuri emeno livelli nella area dei toni chiari.

Questo è particolarmente importante quando si elaborano datimedici (es.radiografie)

Quantizzazioneuniforme

Quantizzazionelogaritmica


46/50



47/50



48/50


Quantizzazione: effetti sulle immagini

2 livell i1 bit

4 livelli2 bit

8 livelli3 bit

256

livelli8 bit


49/50


Quantizzazione

Quantizzazione uniforme: - range in ingresso 0…N-1,- range in uscita 0…K-1 con K


50/50

Quantizzazione

Quantizzazione non uniforme: - range in ingresso 0…N-1,- range in uscita 0…K-1 con K

IEM-02-Seconda Parte Campionamento Quantizzazione

Documents

Transcript of IEM-02-Seconda Parte Campionamento Quantizzazione