Corso di Percezione Robotica (PRo)

C. Modulo di Percezione Attiva

Visione robotica

Cecilia Laschi

ARTS Lab, Scuola Superiore Sant’Anna

cecilia.laschi@sssup.it

050-883486

Sommario della lezione (1/2)

Immagini digitali formazione dell’immagine

definizioni di immagine digitalizzata, connettività e distanza

operatori puntuali, locali e globali

Pre-elaborazione (early processing): filtraggio

rilevamento di bordi

sogliatura

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

Sommario della lezione (2/2)

Segmentazione dell’immagine

Rilevamento dei contorni

Rappresentazione dei contorni

Visione stereoscopica

Principi fondamentali

L’algoritmo di Marr & Poggio

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

Principali classi di tecniche di elaborazione delle immagini digitali

SEGMENTAZIONE

Rilevamento delle parti che costituiscono una scena

Elaborazione dell’immagine a livello globale

Es:

RILEVAMENTO CONTORNI: elementi basati sulla discontinuità

RILEVAMENTO REGIONI: elementi basati sulla uniformità

PRE-ELABORAZIONE (EARLY PROCESSING)

Elaborazione dei valori dei pixel dell’immagine a livello puntuale o locale

Es:

FILTRAGGIO

RILEVAMENTO DEI BORDI

Formazione dell’immagine nell’occhio

Formazione dell’immagine nella macchina fotografica

Sensori CCD - Charge-Coupled-Device

1969 Bill Boyle e George Smith

Funzione immagine

f(x,y) 2x

(x,y): coordinate spaziali

f(x,y): valore dell’intensità luminosa

Un esempio di immagine digitale

Immagine digitale

CAMPIONAMENTO DELL’IMMAGINE: discretizzazione delle coordinate spaziali

QUANTIZZAZIONE DELL’INTENSITA’ (o DEI LIVELLI DI GRIGIO): discretizzazione in ampiezza

PIXEL: elemento dell’immagine digitale

Risoluzione spaziale

Profondità di colore

Binario – 1 bit

Livelli di grigio – 8 bit

True color – 24 bit

Geometria delle immagini

Pixel 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)

Punti 4-vicini

Un punto P=(x,y) appartenente ad un’immagine digitale ha 4 punti vicini in orizzontale e in verticale

L’insieme dei punti 4-vicini di P si indica con N4(P)

Punti vicini diagonali

Un punto P=(x,y) appartenente ad un’immagine digitale ha 4 punti vicini diagonali

L’insieme dei punti vicini diagonali di P si indica con ND(P)

Punti 8-vicini

Un punto P=(x,y) appartenente ad un’immagine digitale ha 8 punti 8-vicini

N8(P) = N4(P) ND(P)

L’insieme dei punti 8-vicini di P si indica con N8(P)

Distanza

p=(x,y), q=(s,t) e z=(u,v)

D è una funzione della distanza o metrica se

1. D(p,q) 0

2. D(p,q) = D(q,p)

3. D(p,z) D(p,q) + D(q,z)

DISTANZA EUCLIDEA: De(p,q)=((x-s)2+(y-t)2)1/2

Distanza sulle immagini digitali

La distanza euclidea tra due punti P(x,y) e Q(u,v) è definita come:

Sulle immagini digitali sono definite anche altre distanze, “più semplici”: distanza city block (a blocchi)

distanza chessboard (a scacchiera)

Distanza city block

E’ definita come:

“Cerchio” identificato dai punti X tali che d4 (P,X)≤2

I punti a distanza 1 da P sono

proprio i 4-vicini di P.

d4(P,Q) è uguale alla lunghezza del più breve 4-percorso da P a Q.

Distanza chessboard

E’ definita come:

“Cerchio” identificato dai punti X tali che d8 (P,X)≤2

I punti a distanza 1 da P sono

proprio i 8-vicini di P.

d8(P,Q) è uguale alla lunghezza del più breve 8-percorso da P a Q.

Proprietà metriche

Si noti come tutte queste distanze siano metriche

Infatti, per tutte valgono le seguenti proprietà:

d(P,Q) ≥ 0; d(P,Q) = 0 P = Q

d(P,Q) = d(Q,P)

d(P,R) ≤ d(P,Q) + d(Q,R)

Connettività

Siano P e Q due punti dell’immagine digitale allora:

P e Q sono 4-CONNESSI se Q N4(P)

P e Q sono 8-CONNESSI se Q N8(P)

P e Q sono m-CONNESSI se:

Q N4(P) oppure

Q ND(P) N4(P) N4(Q) =

0 2 0

0 0 1

0 1 1

0 2 0

0 0 1

0 1 1

0 2 0

0 0 1

0 1 1

Connettività

Un percorso (path) di lunghezza n da P a Q è una sequenza di punti P=P1, P2, …, Pn=Q tale che Pi è un k-vicino di Pi-1 i=1,…n

A seconda del valore di k, si parla di 4-percorso o di 8-percorso

P si dice k-connesso a Q se esiste un k-percorso da P a Q formato interamente da punti appartenenti ad S.

Esempio

Se P è 4-connesso a Q allora è anche 8-connesso a Q

P è 8-connesso a Q P è 4-connesso a Q

Elaborazione delle immagini digitali

I tipi di operazioni che si possono realizzare per trasformare un’immagine in ingresso a[M,N] in un’immagine di uscita b[M,N] possono essere classificate in tre categorie:

Operatori puntuali

Operatori locali

Operatori globali

Operazioni su immagini digitali

Operatori puntuali

il valore di uscita nel punto (i,j) dipende solo dal valore di ingresso nel punto (i,j)

Operatori locali

il valore di uscita nel punto (i,j) dipende solo dai valori di ingresso in un intorno del punto (i,j)

Operatori globali

il valore di uscita nel punto (i,j) dipende da tutti i valori dell’immagine di ingresso

Operazioni puntuali

Trasformazioni puntuali

Sono trasformazioni tipicamente orientate al miglioramento della qualità dell’immagine (image enhancement).

Generalmente si realizzano tramite una funzioney=f(x), che ad un livello di grigio x dell’immaginein ingresso, fa corrispondere il valore y per l’immagine in uscita.

La trasformazione si può realizzare tramite delleLook-up Table (LUT) che permettonoun’implementazione hardware efficiente dellatrasformazione.

Binarizzazione - sogliatura

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

T può essere determinata empiricamente o con tecniche statistiche

Esempio

Inversione dei livelli di grigio

Semplice trasformazione del tipo:

g(x,y)=255- f(x,y)

Fornisce la “negativa” dell’immagine originale

Compressione di potenza

Trasformazione del tipo:

g(x,y)=c f(x,y)

Esempio

Espansione di contrasto

Si realizza per aumentare la dinamica di un’immagine il cui istogramma è concentrato in un intervallo limitato dei valori possibili

Esempio – clipping a 150

0 per ( , ) 150

( , ) 255*[ ( , ) 150] per ( , ) 150

105

f x y

g x y f x yf x y

Pre-elaborazione (early processing): tecniche di FILTRAGGIO

Media degli intorni

Filtraggio mediano

Media dell’immagine

Sottrazione dello sfondo

Trasformazione dell’istogramma

Metodi del dominio spaziale

g(x,y)= h[f(x,y)]

Maschere di Convoluzione

w1 w2 w3

w4 w5 w6

w7 w8 w9

Correlazione di immagini

Misure di similitudine, per confrontare una funzione immagine f(x) con un template t(x)

Rft(y) = xf(x)t(x-y)

1 1 1

1 1 1

1 1 1

Template Immagine Correlazione

1 1 0 0 0

1 1 1 0 0

1 0 1 0 0

0 0 0 0 0

0 0 0 0 8

7 4 2 x x

5 3 2 x x

2 1 9 x x

x x x x x

x x x x x

Filtri di smoothing

Sono filtri per il miglioramento della qualità dell’immagine

Hanno l’effetto di diminuire il contrasto locale dell’immagine

Sono usati per:

eliminare i dettagli inutili (blurring)

ridurre alcuni tipi di rumore (noise cleaning)

Filtri di smoothing

Tipicamente, calcolano la media dei valori dei pixel in un intorno simmetrico (3x3, 5x5, 7x7,…)

Media degli intorni

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

S: intorno di (x,y)

P: numero di punti di S

n,mS1/9 1/9 1/9

1/9 1/9 1/9

1/9 1/9 1/9

Esempio: Blurring

Esempio: Blurring

Filtri di smoothing

Sono utilizzate anche altre maschere che realizzano una media pesata (es. filtro gaussiano)

Discretizzazione su una maschera 3x3 di una gaussiana con media nulla e varianza paria a 0.5

Noise cleaning rumore impulsivo,

detto anche “sale e pepe” (salt & pepper)

Viene caratterizzato dalla frazione (in %) dell’immagine modificata

rumore gaussiano biancoViene caratterizzato dalla media e dalla varianza

Rumore impulsivo e filtri di media

Filtraggio 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

Applicazione filtro mediano

Effetti di una media su un intorno 5x5

Effetti di un filtraggio mediano su un intorno 5x5

Esempi di applicazione di un filtro mediano

Immagine con rumore Immagine con rumore

Media o mediana?

Il filtro di media tende a creare nuovi livelli di grigio prima non esistenti

Inoltre, attenua non solo il rumore, ma anche tutte le alte frequenze spaziali in maniera indiscriminata, causando così sfocatura, perdita di dettaglio fine e smussatura dei fronti di salita nelle transizioni chiaro/scuro

Il filtro mediano non deteriora i fronti di salita, ma elimina i picchi con base sufficientemente piccola rispetto all’ampiezza della maschera

Sottrazione 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 immagine

fn(x,y) = f(x,y) - fb(x,y)

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

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

Istogramma di un’immagine

I pixel di una immagine sono una “popolazione” sulla quale possiamo calcolare tutte le quantità statistiche descrittive che si usano normalmente:

Media, mediana, varianza, deviazione standard, quartili, percentili, ecc.

Particolarmente importante è la conoscenza della distribuzione delle frequenze dei toni di grigio:

l’istogramma

Istogramma

Per ogni livello di grigio, riporta il numero di pixel di quel valore

Per una immagine I[m,n] si ha:

H(k) = numero di pixel di valore k

La somma di tutti gli H è esattamente mxn

L’istogramma è utile a comprendere in maniera immediata le caratteristiche dell’immagine

Caratteristiche dell’istogramma

Immagine “chiara” più denso a destra

Immagine “scura” più denso a sinistra

Limite dell’istogramma

Non tiene conto della distribuzione spaziale

Equalizzazione istogramma

E’ una tecnica che mira a modificare la forma dell’istogramma redistribuendo i valori dei livelli di grigio in modo che l’istogramma sia quanto più uniforme possibile

L’obiettivo è quello di migliorare immagini a debole contrasto

L’equalizzazione non porta necessariamente ad un miglioramento dell’immagine (Es. immagine con istogramma bimodale)

Trasformazione (equalizzazione) dell’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 grigio 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

Equalizzazione istogramma

Supponiamo inizialmente di lavorare nel continuo e sia h(x) l’istogramma dell’immagine di partenza

Per realizzare l’equalizzazione è necessaria una trasformazione monotona

y=y(x)

tale che l’istogramma g(y) dell’immagine trasformata sia costante

g(y)=C

Si impone che aree elementari dell’istogramma originale si trasformano in aree corrispondenti dell’istogramma modificato, si ha:

Equalizzazione istogramma

0

1 1( ) ( ) ( )

xdy

h x y x h x dxdx C C

0 0

1( ) ( ) ( )

x x

k k

ly x H k H k

C n m

Ricavo y(x):

2550 0

0

1 256( ) ( ) ( )

( )

x x

k k

k

y x H k H kC

H k

Nel dominio discreto diventa:

Per un’immagine a livelli di grigio (8-bit):

Algoritmo equalizzazione

1. Valutare istogramma H(k)

2. Calcolare la

3. Eseguire la trasformazione tramite la y(x)

0

( ) ( )x

k

ly x H k

n m

Esempio di equalizzazione dell’istogramma

Esempio di equalizzazione dell’istogramma

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 laplaciano

Tecniche di confronto con un modello (template matching): operatori di Kirsch

Tecniche basate su modelli parametrici: operatore di Hueckel

Pre-elaborazione (early processing): tecniche di RILEVAMENTO DEI BORDI

Rilevamento di bordi basato sul gradiente - definizioni

GRADIENTE: misura della discontinuità in un punto dell’immagine

DIREZIONE DEL GRADIENTE ((x,y)): direzione della massima variazione dei livelli di grigio

INTENSITA’ DEL GRADIENTE (s(x,y)): intensità della variazione dei livelli di grigio

Rilevamento di bordi basato sul gradiente

Filtri derivativi del primo ordine

Per implementare le derivate del primo ordine, un operatore utilizzato di frequente è il gradiente che rappresenta la derivata di una f(x,y) nella direzione di massima variazione

Il gradiente è definito come un vettore colonna:

DIREZIONE DEL GRADIENTE (x,y):

direzione della massima variazione dei

livelli di grigio

INTENSITA’ DEL GRADIENTE (s(x,y)):

intensità della variazione dei livelli di grigio

Implementazione filtri derivativi

Di fatto, non si usa il gradiente così come è definito, in quanto le derivate parziali non sono isotrope.

Si considera invece il modulo del gradiente, anche se l’operatore risultante non è lineare

La valutazione del modulo del gradiente comporta un’elevata complessità computazionale.

Per ridurre la complessità, si può approssimare il modulo con la somma dei valori assoluti delle componenti, anche se, a rigore, si perde l’isotropia dell’operatore

Rilevamento di bordi basato sul gradiente

s(x,y) = (12 + 2

2)1/2

(x,y) = tan-1(2 / 1)

fx

fy

1

2

G[f(x,y)] = =

Rilevamento di bordi basato sul gradiente e sogliatura

g(x,y)=G[f(x,y)]

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

0 se g[f(x,y)] <= T

Rilevamento dei bordi e sogliatura

OPERATORE DI DIFFERENZA:

1= f(x+a,y) - f(x,y)

2= f(x,y+a) - f(x,y)

Si,j 12

22

1 = Ii-a,j - Ii,j

2 = Ii,j+a - Ii,j

a

a

j+i,ji,

j,-i

II

I

sogliaS se 1

sogliaS se 0E

ji,

ji,

ji,

2

ji,

2

ji,

ji,

2

2

2

1ji,

sogliaS se 1

sogliaS se 0E

S

Approssimazione derivata prima

A = 1

Rilevamento dei bordi e sogliatura

A = 2

Rilevamento di bordi basato sul gradiente

OPERATORE INCROCIATO DI ROBERTS:1= f(x,y+a) - f(x+a,y) 2= f(x,y) - f(x+a,y+a)

OPERATORE DI 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)

0 1

-1 0

1

-121

-1 -1 -1

0 0 0

1 1 1

1 0 -1

1 0 -1

1 0 -1

1 2

Operatori di PrewitOPERATORI DI 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)

Rilevamento di bordi basato sul gradiente

OPERATORE DI 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)

-1 -2 -1

0 0 0

1 2 1

-1 0 1

-2 0 2

-1 0 1

1 2

Approssimazione derivata seconda

Implementazione del Laplaciano

Filtro di sharpening mediante Laplaciano

Per ottenere l’immagine migliorata, è necessario combinare l’immagine originale con il laplaciano

Operatore di Kirsch

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

Xk N8(x)

K+1

k k-1

-1 0 1

-1 0 1

-1 0 1

1 1 1

0 0 0

-1 -1 -1

0 1 1

-1 0 1

-1 -1 0

1 1 0

1 0 -1

0 -1 -1

Modello di Hueckel

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

Rilevamento dei crack edge

CRACK EDGE: bordo considerato tra 2 pixel

Ogni pixel ha 4 crack edge:

(x,y) = k /2

0 k < 4

s(x,y) = |f(x,y) - f(x+h,y-h)|

h = 1, -1

Algoritmo di rilassamento di Prager

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

al valore dei bordi vicini

0. Calcola il valore di fiducia iniziale di ogni bordo C0(e) come il gradiente normalizzato rispetto al massimo gradiente

1. k=1

2. Calcola il tipo di ogni bordo in base alla fiducia dei vicini

3. 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 Prager

Un bordo è di tipo i-j se i suoi vertici sono di tipo i e di tipo j, rispettivamente

Un 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 Prager

Un 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)

Sogliatura

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à locali

T può essere determinata empiricamente o con tecniche statistiche

Segmentazione

Individuazione delle parti costituenti una scena

CONTORNI: elementi di un’immagine segmentata basati sulla discontinuità

REGIONI: elementi di un’immagine segmentata basati sulla uniformità

Rilevamento dei contorni

Ricerca di un contorno noto verifica del bordo sulle normali

verifica del bordo sul contorno

divide et impera

confronto con un modello

confronto con un esempio

inseguimento scansione e inseguimento

metodo del punto finale

analisi locale

metodo di Hough

ricerca sul grafo

Verifica del bordo sulle normali

Verifica del bordo sul contorno

Divide et impera

Confronto con un modello

Modello di Hueckel

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

Confronto con un esempio (template)

0 0 1 0 0

0 0 1 0 0

0 0 1 0 0

0 0 1 0 0

0 0 1 0 0

0 0 0 0 0

0 0 0 0 0

1 1 1 1 1

0 0 0 0 0

0 0 0 0 0

0 0 0 0 1

0 0 0 1 0

0 0 1 0 0

0 1 0 0 0

1 0 0 0 0

Contorno verticale Contorno orizzontale Contorno diagonale

Scansione e inseguimento

1.Scandisci l’immagine da sinistra a destra dall’alto verso il basso fino a trovare un edge

2.Collegalo al precedente e ricerca altri edge in un suo intorno

3. (a) se c’è un solo edge: vai a 2.

(b) se ce ne sono 2 o più: scegline uno e vai a 2; memorizza gli altri

(c) se non ce ne sono, l’edge considerato è un terminale di contorno. Se ci sono edge memorizzati scegline uno e vai a 2, altrimenti vai a 1.

Un esempio di rilevamento dei contorni con una tecnica di inseguimento

(a)

(b) (c)

Analisi locale

Il metodo consiste nel collegare gli edge di un intorno che hanno caratteristiche simili

|S(x,y) - S(x’,y’)| < T (soglia)

|(x,y) - (x’,y’)| < A (soglia)

Metodo di Hough

Rileva ogni contorno che possa essere espresso da una curva parametrica, confrontando l’immagine dei bordi con tutte le curve ottenute variando i valori dei parametri

Trasformata di Hough

E’ una tecnica che permette di riconoscere particolari configurazioni di punti presenti nell’immagine, come segmenti, curve o altre forme prefissate.

E’ un tipico operatore globale.

Il principio fondamentale è che la forma cercata può essere espressa tramite una funzione nota che fa uso di un insieme di parametri.

Una particolare istanza della forma cercata è quindi completamente precisata dal valore assunto dall’insieme di parametri.

Trasformata di Hough – Caso della retta

Per esempio, assumendo come rappresentazione della retta la forma:

y=ax+b qualunque retta è completamente specificata

dal valore dei parametri (a,b).

Se si assume un tipo di rappresentazione diversa, quale la forma normale di Hesse

ρ = x cosϑ + y sin ϑ la retta è completamente specificata dalla

coppia (ρ,ϑ).

Esempio

La retta in figura è identificata dalla coppia:

(a,b)=(-0.5,0.5)

o dalla coppia:

(ρ ,ϑ)=(0.447,1.107)

Il piano trasformato

Domande

Nell’immagine in analisi, l’unica informazione disponibile è costituita dall’insieme di punti che appartiene al foreground.

1. Come poter sfruttare questa trasformata ai fini della individuazione di segmenti in un’immagine ?

2. Qual è la trasformata di un punto nell’immagine ?

Trasformata di un punto

Nel piano dell’immagine, un punto è identificato dall’intersezione di più rette.

Quindi, ad ogni punto P corrisponde, nel piano dei parametri, la curva formata dai punti immagine delle rette passanti per P.

Trasformata del punto

Domanda

Che cosa succede se nell’immagine ci sono dei punti allineati su una stessa retta ?

Sul piano dei parametri, le curve che corrispondono alle trasformazioni dei vari punti si intersecano in un punto del piano trasformato che è l’immagine della retta su cui giacciono i punti.

Individuazione della retta sul piano trasformato

Implementazione trasformata di Hough – caso della retta

Si consideri una discretizzazione del piano dei parametri (ρ,ϑ).

Ciò permette di rappresentare tale piano su una matrice H(m,n) i cui indici di riga e di colonna corrispondono ai valori quantizzati di ρ e ϑ.

Gli intervalli di variazione di ρ e ϑ sono fissati sulla base delle caratteristiche dell’immagine originale. Tipicamente -ρmax≤ ρ ≤ ρmax, -π/2 ≤ ϑ ≤ π/2, dove ρmax=0.5*(NR2+NC2)1/2 e (NR,NC ) sono le dimensioni

dell’immagine originale. Il numero dei livelli di quantizzazione va poi scelto in base

all’accuratezza desiderata. Una scelta quasi sempre soddisfacente è max(NR,NC).

Metodo di Hough: rappresentazione polare di una retta

= x cos + y sin

Algoritmo di Hough

1.Quantizza lo spazio dei parametri tra valori appropriati di massimo e minimo

2.Crea una matrice di accumulazione di dimensioni pari al numero dei parametri, inizializzata a 0

3.Per ogni punto di edge dell’immagine, incrementa tutti i punti della matrice di accumulazione corrispondenti ai valori dei parametri delle curve su cui l’edge giace

4.I massimi locali nella matrice rappresentano i valori dei parametri che individuano le curve che meglio approssimano il contorno

Algoritmo

1. Si azzeri la matrice H(.,.);2. Per ogni punto PF, P=(x,y)

1. per ϑn che varia tra -π/2 e π/2 con passo dϑ1. si valuta ρ(n)=x*cos(ϑn)+y*sin(ϑn)2. si ricava l’indice m corrispondente a ρ(n)3. si incrementi H(m,n)

2. end

3. End

4. Si individuino i massimi locali su H(.,.) corrispondenti ai parametri dei segmenti individuati

Esempio: figura piana

Esempio: matrice accumulazione

Algoritmo di Hough

Algoritmo di Hough

Sogliatura immagini reali

Conclusioni

E’ possibile – ma molto oneroso - utilizzare la trasformata di Hough per individuare cerchi, tenendo conto dell’equazione (x-a)2+(y-b)2=c2

In questo caso è possibile lavorare su: un piano dei parametri (a,b), fissando il raggio c dei cerchi da

individuare uno spazio dei parametri (a,b,c), facendo variare c in un

intervallo finito.

E’ stata inoltre proposta (Ballard) una generalizzazione della trasformata di Hough che permette di individuare oggetti di forma qualunque.

Non è adatta a applicazioni real-time

Metodo della ricerca su grafo

NODI: crack edge (p,q)

con p,q pixel di intensità f(p) e f(q)

ARCHI: collegamenti tra crack edge che in sequenza possono far parte di un contorno

COSTO (associato all’arco entrante in (p,q)): c(p,q) = H - [f(p) - f(q)]

con H massima intensità nell’immagine

Metodo della ricerca su grafo

c(p,q) = H - [f(p) - f(q)]

Metodo della ricerca su grafo

c(p,q) = H - [f(p) - f(q)]

Rappresentazione dei contorni

Codici a catena e numeri di forma

Forme caratteristiche

Codici a catena e numeri di forma

1

3

02

Codici a catena e numeri di forma

Normalizzazione rispetto alla rotazione:utilizzare la differenza del codice a catena contando in senso antiorario il numero delle direzioni che separano due elementi adiacenti

Es: 10103322

3133030

33133030

Codici a catena e numeri di forma

Calcolo dell’area con i codici a catena

1. Area=0;

2. y=0;

3. per ogni elemento del codice a catena

case direzione

0: area+=y;

1: y++;

2: area-=y;

3: y--; x

y

1

3

02

Forme caratteristiche

Problema fondamentale della visione stereoscopica

La proiezione operata da una telecamera comporta un'inevitabile perdita d'informazione: infatti il passaggio da un punto dello spazio tridimensionale ad un punto dell'immagine bidimensionale, prevede la perdita di una coordinata, quella che tiene conto della profondità

in un ipotetico passaggio inverso si ha il problema di recuperare l'informazione relativa a questa coordinata "smarrita"

Questo problema viene superato da una tecnica nota come stereopsi.

trasformazione inversa, dalla proiezione 2D sul piano di un'immagine, ai punti corrispondenti nello spazio 3D

Visione stereoscopicaprincipi di base

Proiezione di un punto del mondo sul piano dell'immagine

Sistema binoculare non convergente

xx d f

f z

xx d f

f z

1

2

( )

( )fdxxzf

fdxxzf

)()(

)()(

2

1

( )( )f z x x df 2 1 2

[Tratta da: Ballard e Brown, 1982]z f

df

x x

2

2 1Disparità

Visione stereoscopica

Passi fondamentali:

Acquisire due immagini distinte, conoscendo la distanza tra le telecamere

Ricavare le linee su cui i punti tridimensionali reali giacciono

Intersecare le linee

2 Telecamere: problema del matching

Date due telecamere trovare la corrispondenza di punti omologhi su due diverse immagini

Mappa delle disparità

Algoritmo di Marr & Poggio Selezionare un punto su una superficie della scena in

una delle due immagini Identificare lo stesso punto nell’altra immagine Misurare la disparità tra le due posizioni del punto

Algoritmo di Marr & PoggioVincoli: Compatibilità: i punti neri possono corrispondere solo a punti neri Unicità: quasi sempre un punto nero di un’immagine può corrispondere a non

più di un punto nero dell’altra immagine Continuità: la disparità varia linearmente quasi ovunque nell’immagine,

eccetto ai bordiDisparitàR

L

x

x

(a)

-

-

--

+

+

-

-

--

+

+

(b) (c)

+

+

In (a) Lx e Rx rappresentano le posizioni degli elementi nelle immagini sinistra e destra rispettivamente. Le linee continue orizzontali e verticali rappresentano le linee di visione dell'occhio sinistro e destro. Le intersezioni di queste linee corrispondono a possibili valori di disparità. Le linee tratteggiate diagonali sono linee di disparità costante. Le linee tratteggiate rappresentano le interazioni eccitatorie, mentre le altre (orizzontali e verticali) quelle inibitorie. (b) mostra la struttura locale della rete ad ogni nodo. (c) mostra la struttura locale della rete corrispondente applicata ad immagini bidimensionali. [Tratta da: Marr, 1982]

Algoritmo di Marr & Poggio

CCCC0

,,),,(',','

',','),,(',','

',','

1

,, dyxdyxOdyx

t

dyxdyxSdyx

t

dyx

t

dyx

: stato della cella (x,y) con disparità d al tempo t

S(x,y,z): intorno locale eccitatorio

O(x,y,z): intorno locale inibitorio

: costante di inibizione: funzione di soglia