Corso di Percezione Robotica Corso di Percezione Robotica (PRo)(PRo)A.A. 99/00A.A. 99/00

B. Modulo di Percezione B. Modulo di Percezione ArtificialeArtificiale

Visione artificiale e tecniche di elaborazione delle immagini

Parte 1/2

Sommario della lezioneSommario della lezioneFormazione dell’immagine

principi di funzionamento dei dispositivi per l’acquisizione di immagini

definizioni di immagine digitalizzata, connettività e distanzapreelaborazione (early processing):

filtraggio rilevamento di bordi sogliatura

Riferimenti bibliografici:Fu, Gonzalez, Lee, “Robotica”, McGraw-HillBallard & Brown, “Computer vision”, Prentice Hall

Funzione immagine ed Funzione immagine ed immagine digitalizzataimmagine digitalizzata

f(x,y) 2x(x,y): coordinate spazialif(x,y): valore dell’intensità luminosa in quel punto

CAMPIONAMENTO DELL’IMMAGINE: digitalizzazione delle coordinate spazialiQUANTIZZAZIONE DELL’INTENSITA’ (o DEI LIVELLI DI GRIGIO): digitalizzazione in ampiezzaPIXEL: elemento dell’immagine digitalizzata

Pixel viciniPixel vicini

p = (x,y) è 4-VICINO di:(x+1,y) (x-1,y) (x,y+1) (x,y-1) N4(p)

p = (x,y) è VICINO DIAGONALE di:(x+1,y+1) (x+1,y-1) (x-1,y+1) (x-1,y-1) ND(p)

p = (x,y) è 8-VICINO di N4(p) ND(p)

ConnettivitàConnettivitàq N4(p) p e q 4-CONNESSI

q N8(p) p e q 8-CONNESSIp e q CONNESSI p e q ADIACENTIS1 e S2 sottoinsiemi di un’immagine

pS1 e qS2 t.c. p e q adiacenti

S1 e S2 adiacenti PERCORSO tra p=(x,y) e q=(s,t):{(x0,y0), (x1,y1), …, (xn,yn) t.c. (x0,y0)=p, (xn,yn)=q e i (xi,yi) è adiacente a (xi+1,yi+1)}n=lunghezza del percorso

DistanzaDistanza

p=(x,y), q=(s,t) e z=(u,v)D è una funzione della distanza o metrica se1. D(p,q) 02. D(p,q) = D(q,p)3. D(p,z) D(p,q) + D(q,z)DISTANZA EUCLIDEA: De=((x-s)2+(y-t)2)1/2

DISTANZA DEGLI ISOLATI: D4=|x-s|+|y-t|

DISTANZA A SCACCHIERA: D8=max(|x-s|,|y-t|)

Preelaborazione (early Preelaborazione (early processing): tecniche di processing): tecniche di FILTRAGGIOFILTRAGGIO

filtraggio hardwaremedia degli intornifiltraggio medianomedia dell’immaginesottrazione dello sfondo trasformazione dell’istogramma

Filtraggio hardwareFiltraggio hardware

Filtri passa-basso per l’eliminazione del rumore, tipicamente ad alta frequenzarischio di eliminare caartteristiche significative dell’immagine (es. bordi)

filtri passa-bandanei casi in cui il rumore è periodico e concentrato attorno ad una frequenza particolare

Media degli intorniMedia degli intorni

g(x,y) = 1/P f(n,m)

S: intorno di (x,y)P: numero di punti di S

n,mS

Filtraggio medianoFiltraggio mediano

g(x,y) = mediana di (x,y)

Mediana M di un insieme di valori: valore tale che metà dei valori dell’insieme sono minori di M e metà sono maggiori

Media dell’immagineMedia dell’immagine

g(x,y) = 1/K fi(x,y)K

i=1

Sottrazione dello sfondoSottrazione dello sfondo

La tecnica della sottrazione dello sfondo tenta di rimuovere le leggere variazioni dei livelli di grigio dello sfondo, approssimandole con una funzione e sottraendo tale funzione dalla funzione immaginefn(x,y) = f(x,y) - fb(x,y)

fb(x,y) = c (costante) oppure

fb(x,y)=m1x+m2y+c (lineare)

Trasformazione Trasformazione (equalizzazione) (equalizzazione) dell’istogrammadell’istogramma

ISTOGRAMMA DI UN’IMMAGINE: funzione che dà la frequenza di apparizione di ogni livello di grigio nell’immagineh(p) = numero di pixel con valore p (0pn)

EQUALIZZAZIONE DELL’ISTOGRAMMA: mappatura dei livelli di grigrio p in livelli di grigio q t.c. la loro distribuzione è uniformeg(q) dq = h(p) dpg(q) = N2/MN2: numero di pixel, M:numero dei livelli di grigio

g(p) = M/N2 h(s) dsp

0

BORDO (EDGE): area in cui i livelli di grigio variano rapidamente

OPERATORE DI BORDO (EDGE OPERATOR): operatore matematico in grado di rilevare la presenza di un bordo

Operatori basati sul gradiente: operatore di differenza, operatore incrociato di Roberts, operatori di Prewitt e Sobel, metodo dei crack edge, metodo del laplacianoTecniche di confronto con un modello (template matching): operatori di KirschTecniche basate su modelli parametrici: operatore di Hueckel

Preelaborazione (early Preelaborazione (early processing): tecniche di processing): tecniche di RILEVAMENTO DEI BORDIRILEVAMENTO DEI BORDI

Rilevamento di bordi basato sul Rilevamento di bordi basato sul gradiente - definizionigradiente - definizioni

GRADIENTE: misura della discontinuità in un punto dell’immagineDIREZIONE DEL GRADIENTE (s(x,y)): direzione della massima variazione dei livelli di grigioINTENSITA’ DEL GRADIENTE ((x,y)): intensità della variazione dei livelli di grigio

Rilevamento di bordi basato sul Rilevamento di bordi basato sul gradientegradiente

s(x,y) = (12 + 2

2)1/2 (x,y) = tan-1 (2/1)OPERATORE DI DIFFERENZA:1= f(x+a,y) - f(x,y) 2= f(x,y+a) - f(x,y)OPERATORE INCROCIATO DI ROBERTS:1= f(x,y+a) - f(x+a,y) 2= f(x,y) - f(x+a,y+a)PREWITT:1= f(x-1,y+1) + f(x,y+1) + f(x+1,y+1) - f(x-1,y-1) - f(x,y-1) - f(x+1,y-1) 2= f(x-1,y-1) + f(x-1,y) + f(x-1, y+1) - f(x+1,y-1) - f(x+1)y) - f(x+1,y+1)SOBEL:1= f(x-1,y+1) + 2f(x,y+1) + f(x+1,y+1) - f(x-1,y-1) - 2f(x,y-1) - f(x+1,y-1) 2= f(x-1,y-1) + 2f(x-1,y) + f(x-1, y+1) - f(x+1,y-1) - 2f(x+1)y) - f(x+1,y+1)

Rilevamento dei crack edge Rilevamento dei crack edge

CRACK EDGE: bordo considerato tra 2 pixel

Ogni pixel ha 4 crack edge:(x,y) = k /2s(x,y) = |f(x,y) - f(x+k,y-k)|

0 k 4

Metodo del LaplacianoMetodo del Laplaciano

Approssimazione della derivata del secondo ordine

L(x,y) = f(x,y) - 1/4 [f(x,y+1) + f(x,y-1) + f(x-1,y) + f(x+1,y)]

Operatore di KirschOperatore di Kirsch

S(x) = max[1, max |f(xk) - f(x)|]K+1

k k-1

Modello di HueckelModello di Hueckel

Modello di un bordo ideale, rappresentato attraverso parametri che vengono variati per trovare il miglior matching sull’immagine

SogliaturaSogliatura

Trasformazione dell’immagine in IMMAGINE BINARIA, attraverso il confronto con una soglia T:

g(x,y) = 1 se f(x,y) > T= 0 se f(x,y) T

T può essere costante o variabile rispetto a x, y, f(x,y) o altre proprietà localiT può essere determinata empiricamente o con tecniche statistiche

Algoritmo di rilassamento di Algoritmo di rilassamento di PragerPrager

Migliora l’immagine dei bordi (crack edge), rafforzando quelli più plausibili ed indebolendo quelli più dubbi, rispetto al

valore dei bordi vicini0. Calcola il valore di fiducia iniziale di ogni bordo C0(e) come il gradiente normalizzato rispetto al massimo gradiente1. k=12. Calcola il tipo di ogni bordo in base alla fiducia dei vicini3. Modifica la fiducia di ogni bordo Ck(e) sulla base del tipo e del valore di fiducia precedente Ck-1(e)4. Verifica se c’è stata la convergenza di tutti i Ck(e) a 0 o 1. Se sì allora stop, altrimenti incrementa k e vai al passo 2

Algoritmo di rilassamento di Algoritmo di rilassamento di PragerPragerUn vertice è di tipo i se i massimizza conf(i)conf(0) = (m-a)(m-b)(m-c)conf(1) = a(m-b)(m-c) conf(2) = ab(m-c)conf(3) = abc

m=max(a,b,c,q)a,b,c gradienti normalizzati con abcq costante (es: q=0.1)

Algoritmo di rilassamento di Algoritmo di rilassamento di PragerPragerUn bordo è di tipo i-j se i suoi vertici sono di tipo i e di tipo j, rispettivamente

INCREMENTA i bordi di tipo: 1-1, 1-2, 1-3DECREMENTA i bordi di tipo: 0-0, 0-2, 0-3INVARIATI i bordi di tipo: 0-1, 2-2, 2-3, 3-3

INCREMENTO: CK+1(e)=min(1,Ck(e)+)DECREMENTO: CK+1(e)=max(0,Ck(e)-)NO VARIAZIONE: CK+1(e)=Ck(e)

costante (tipicamente 0.1 0.3)