TECNICHE DI RAPPRESENTAZIONE DI IMMAGINI · R.Cucchiara Scuola GIRPR La Visione delle Macchine 11...

TECNICHE DI RAPPRESENTAZIONE DI IMMAGINI

Prof. Rita Cucchiara

ImageLab

Dipartimento di Ingegneria dell’InformazioneUniversità di Modena e Reggio Emilia, Italy

R.Cucchiara

Scuola GIRPR La Visione delle Macchine 11 novembre 2002

2

Rappresentazione delle immagini

Rappresentazionedelle immagini

Rappresentazionedel contenuto delle immagini

Rappresentazionedel contenuto della scena rappresentata da una immagine

Iconic images:Immagini come matrici di punti

Rappresentazione disingoli punti

•Immagini a colori, a livello di grigio, di profondita’•Immagini pre-elaborate•Immagini segmentate

Rappresentazionedegli oggetti estratti

nelle immagini

Rappresentazione di•Bordi•Regioni•Forme•Proprieta’ (feature)

Rappresentazionedegli oggetti nella scena

Rappresentazione di•Scena 3D•Oggetti visuali 2D e 3D•Oggetti reali 3D•Eventi•Azioni•…

R.Cucchiara


3

Rappresentazione (del contenuto) delle immagini

FILTERING ANDINTERPOLATION

3DDataset

3DVisualization

3D VISUALIZATION


3DDataset

3DVisualization

3D VISUALIZATION

Axial images

COMPUTATION OFPANOREX CUT line

MANUAL/INTERACTIVESELECTION OFCROSS -SECTIONAL

Axial images



Volumetric

VIEWS

MULTI -VIEWVISUALIZATIONIMAGE

ANALYISIS& CLUSTERING

OBJECT

& 3D LOCATION SELECTION OFBESTCROSS -SECTIONALVIEWS

Volumetric

VIEWS



OBJECTRECOGNITION

& 3D LOCATION SELECTION OF

CROSS -SECTIONALVIEWS

slicesCT slices

Axial,panorex,

images

Axial,panorex,cross-sectionalimages


3DDataset

3DVisualization

3D VISUALIZATION


3DDataset

3DVisualization

3D VISUALIZATION


3DDataset

3DVisualization

3D VISUALIZATION


3DDataset

3DVisualization

3D VISUALIZATION


3DDataset

3DVisualization

3D VISUALIZATION


3DDataset

3DVisualization

3D VISUALIZATION

Axial images



Axial images



Axial images



Axial images



Volumetric

VIEWS



OBJECT

& 3D LOCATION SELECTION OFBESTCROSS -SECTIONALVIEWS

Volumetric

VIEWS



OBJECTRECOGNITION

& 3D LOCATION SELECTION OF

CROSS -SECTIONALVIEWS

slicesCT slicesslicesCT slices

Axial,panorex,

images


Axial,panorex,

images


R.Cucchiara


4

Rappresentazione (del contenuto) delle immagini

Agenda

Immagini elaborate e segmentate..

Curve

LabelingConnettivita’

Punti

Edge detection,Thinning..

Regioni

Filling

Insieme di regioni

Vincoli, Relazioni spazialiTemporali..

R.Cucchiara


5


Immagini (elaborate e segmentate..)

Punti Curve

Regioni Insieme di regioni


Filling

Edge detection,Thinning

..


R.Cucchiara


6

Rappresentazione di punti

Estrazione di insieme di punti significativiSegmentazione (binarizzazione..)

• Rappresentazione nello spazio immagine (coordinate x,y)

• Rappresentazione delle feature associate ai punti• colore• livello di grigio• moto

• Rappresentazione delle feature associate a insieme di punti• istogrammi

R.Cucchiara


7

Istogrammi di colore con PCA

Principal Component Analysis (PCA), o anche Karhunen-Loeve transformation (KL), e’ un metodo molto utilizzato per ridurre il numero delle dimensioni di un data set.

u Spazi colore (RGB, HSV,,,)u Spazi assolutiu Spazi multidimensionali

Perche’?u 1) lo spazio 3D e’ “ostico” da elaborare (ad es. 2D sarebbe piu’ conveniente)u 2) e’ spesso inutile perche’ in molti casi lo spazio non e’ occupato

uniformememente dai punti dell’immagine

u In molte applicazioni dove le immagini hanno una variabilita’ di colori “limitata” (ad es molti gradi di S e V con poche variazioni di tinta H..) puo’ essere conveniente ridurre lo spazio colore

R.Cucchiara


8

Esempio

PCA1

PCA2

R.Cucchiara


9


u Lo scopo e’ di proiettare lo spazio in uno spazio a dimensioni d’ con d’<d.u La nuova rappresentazione deve essere corretta nel senso dei minimi quadrati:

si cerca di minimizzare la varianza rispetto alle dimensioni considerateu Sia ogni punto x un vettore nello spazio RGB x=[xr,xg,xb]Tu siano dati M punti di una immagine

u la media e’ un vettore

u la scatter matrix e la matrice di covarianza sonou matrici 3 x 3

)(1

∑=

−=M

k

ttkk mmxxS

=

=

∑

∑

∑

=

=

=

M

kk

M

kk

M

kk

m

m

m

xbM

xgM

xrM

bgr

m

1

1

1

1

1

1

R.Cucchiara


10


u Scatter matrix

u Si calcolano gli autovalori

u dati i tre autovalori, gli autovettori sono i componenti x che annullano l’equazione

u ad esempio per λ1

−−−

−−−

−−−

=

∑∑∑

∑∑∑

∑∑∑

===

===

===

M

kmk

M

kmmkk

M

kmmkk

M

kmmkk

M

kmk

M

kmmkk

M

kmmkk

M

kmmkk

M

kmk

bxbbgxbxgbrxbxr

bgxbxggxggrxgxr

brxbxrgrxgxrrxr

S

1

22

11

11

22

1

111

22

)()()(

)()()(

)()()(

0)det( =− IS λ

=

3

2

1

λλλ

λ

0)( =− xIS λ

0321

1

1

1

=

−−

−

xxx

SSSSSSSSS

bbgbrb

gbggrg

rbrgrr

λλ

λ

R.Cucchiara


11

PCA per lo spazio RGB

u Cosi’ si trova la matrice A degli autovettoriu se λ1>λ2>λ3 ed ei sono gli autovettori corrispondentiu autovettore di λ1 sia allora A

u La KL transform trova nuovi componenti y=A(x-m)

Dato ogni punto dell’immagine x=[xr,xg,xb]T1) si calcola la media m2) si calcola S, gli autovalori gli autovettori ed A3) si calcolano i tre componenti y=[y1,y2,y3]T che sono i tre componenti della

trasformata KL4) si fa un operazione di scaling per avere i valori y compresi tra 0 e 255

u Si ottengono tre immagini ( visivamente a livello di grigio) la prima contiene il massimo delle informazioni legate alla proiezione lungo la direzione di e1, la seconda meno e la terza puo’ spesso venire eliminata

=

321

321

321

333222111

eeeeeeeee

A

3

2

1

111

eee

R.Cucchiara


12

ESEMPIO

u Immagine spazio RGB e le tre componenti

u nel caso di immagini dermatologiche e’ stato dimostrato sperimentalmente che la prima componente KL1 contiene circa il 91% della varianza nello spazio colore (in media) la seconda circa il 6%

1

2 3

RGB

R.Cucchiara


13

Istogramma bidimensionale

PCA1

PCA2

R.Cucchiara


14

Impiego dell’istogramma 2D per clustering

u Clustering fuzzy c-means con 4 clusters nello spazio PCA[1-4]

R.Cucchiara


15

Esempio

u Immagine originale e segmentazione con FCM in PCA

R.Cucchiara


16



Punti



Filling


..


Curve

R.Cucchiara


17

Rappresentazione di curve

u Curve come edge, skeleton, parti dell’immagine dopo operazioni morfologiche, siluettes…

u Rappresentazioni numeriche (numero di punti, curvatura)

u Rappresentazioni attraverso chain à es: chain code

u Rappresentazione come formeà es: Traformate di Hough

u Rappresentazione con descrittori matematicià es: spline

R.Cucchiara


18

Chain code

u Rappresentazione degli edge: chain code[1]

u si segue il contorno in senso orario o antiorario e si tiene traccia delle direzioni che permettono di andare da un pixel del contorno al successivo. Per l’implementazione standard del chain code, si considera la regione 8-connessa di ogni punto del contorno.

R.Cucchiara


19

Rappresentazione come forme:Le trasformate di Hough

u E’ la piu’ nota classe di trasformate geometriche aventi come scopo la ricerca in immagini di pattern di forma parametricamente nota [1-5]

u Per descrivere (Localizzare e riconoscere) non tanto un oggetto, quanto “forme” che possono variare per traslazione, dimensione e rotazione.

u La classe di algoritmi basati sulla trasformata di Hough (HT) ha lo scopo di cercare forme descrivibili con parametri e di trasformare lo spazio immagine in uno spazio dei parametri dove la individuazione del pattern e’ computazionalmente piu’ semplice

y P1

P2

ρ P3

θ

x

H

P1

P2

P3ρ

θ

Spazio di HoughPer rette

ϑϑρ sencos yx +=

Trasformata di Hough per rette

R.Cucchiara


20

Rappresentazione di rette

20 40 60 80

50

100

150

Moltipl.Per 2

H r a59 -10 10466 52 4860 66 7673 74 7896 96 8086 116 82

Rette estratte con Hough

edge

R.Cucchiara


21

Rappresentazione di cerchi

r

yc

xc

xy

r

yc

xc

xy

Test 3 Test 4 Test 5Test 3 Test 4 Test 5

R.Cucchiara


22

Rette correlate: per forme allungate

H2

H1

CHCHCH

spazio di HoughGBHT

R.Cucchiara


23

Rette correlate

u Correlated Hough Transformu sullo spazio di Hough possono essere condotte post-elaborazioni per estrarre

informazioni visuali piu’ complesseu ad esempio per correlare edge opposti di oggetti allungati e rettilinei

u CH = (H1 * fc(H2));

u H1={h1:h1(ρ,α)=h(ρ,α), ρ∈[-R,R] , α∈[0,π [}u H2={h2:h2(ρ,α)=h(-ρ,α+π), ρ∈[-R,R] , α∈[0,π [}

u fc(h2(ρ,α)) =h2’(ρ,α)= spazio filtrato di h2(ρ,α) per eliminare problemi di smoothing e quindi opportunamente traslato lungo l’asse e ruotato per sovrapporre punti vicini di h1 e h2

u CH= {ch(ρ,α)=h1(ρ,α)fc(h2(ρ,α)), ρ∈[-R,R] and α∈[0,π] }

R.Cucchiara


24

VGHT vector gradient hough transform

VGHT

IVGHT

GBHT

Integrando lo spazio si riscostruisce il profilo laterale

-200 -150 -100 -50 0 50 100 150 2000

1

2

3

4

5

6

7

8

9

0 50 100 150 200-4

-2

0

2

4

6

0 50 100 150 200-5

0

5

10

15

Spazio di Hough con ro solo positivi

+ ρ- ρ

α α+πα

R.Cucchiara


25

VGHT

Se si mantengono le informazioni vettoriali sul gradiente si possono mantenere anche nello spazio di Hough informazioni sulla concordanza del segnotra u e g

)()(ˆˆ)( sjesGjyf

ixf

sgrrrr γ

∂∂

∂∂

=+=

∫ ⋅•

−⋅•−•=Γ sdgugu

uu

suuu

gun

n rrrrr

rrrrr

rr)1()()( δδ

Un punto dello spazio immagine (x,y) vota in VGHT space per un punto ro, θ1) θ e’ scelto tra θ 1=γ(x,y), θ 2= γ(x,y)+π, scegliendo quello che rende ropositivo distanza euclidea e non algebrica2) il peso e’ dato da G(x,y) cos(θ -γ) : dotato di segno

i f r r x y s i n r− + =( c o s ( ) ( ) ) /ϑ ϑ 0 . 1)rGcos( ±=−rG

γθ

u

g 0

r

G 0P(x 0 ,y 0 )

γ 0

θ

s 0

x

y

R.Cucchiara


26

TRASFORMATA DI HOUGH GENERALIZZATA

u GHT trasformata di Hough generalizzatau consente di riconoscere una qualsiasi forma parametricau concetto di moto rigido: data una forma tutte le possibili istanze di quella forma

si ottengono peru traslazione (xt,yt)u rotazione (angolo a)u fattore di scala (s)

u consideriamo ora solo la traslazioneu il modello viene definito mediante una tabella che considera un insieme di

punti interessanti del contorno del modello e li mette in corrispondenza a parametri rispetto ad un punto di riferimento RP noto

R.Cucchiara


27

TRASFORMATA GENERALIZZATA

u Rispetto ad RP si puo’ creare una tabella che indica per il punto dato la distanza r da RP e l’angolo formato a

u dato il punto x,yxref= x +r cos(a)yref= y +r sin(a)u quale r e a usare?

u Si puo’ creare una tabella di u riferimento Rtable contenente le coppie (Ri,ai) ed indirizzata dall’angolo gi (

angolo del gradiente) che indica l’orientamento del contorno in quel punto u per tutti i punti di edge accedendo all’Rtable con hashing dato da g, si calcola

xref,yref e si incrementa l’accumulatore.

u se si vuole includere l’orientazione, lo si deve ripetere per tutti gli orientamenti a0 possibili in un accumulatore 3D con

xref= x +r cos(a+a0)yref= y +r sin(a+a0)

RP (xref,yref)

r a g

R.Cucchiara


28

TRASFORMATA GENERALIZZATA

u Se si volesse includere anche tutte le possibili scale diventerebbe un array a 4dimensioni

xref=x-s r cos(a+a0)yref=y-s rsin(an+a0)

tanti piu’ punti si considerano tanto piu’ il modello e’ preciso e la trasformata e’lenta

algoritmo1)costruire la Rtable dagli edge: per tutti (o parte) i punti alla locazione indicizzata

da g inserire la coppia(r,a)2) quantizzare lo spazio di hough con i parametri xref ,yref e ao, e inizializzarlo a 03) per tutti i punti(xi,yi) di edge, noto gi, calcolare per ogni ai i corrispondenti

xref,yref ed incrementarne il valore

R.Cucchiara


29

Rappresentazione con Spline

u Rappresentazione di una curva tramite formulazione matematica

u Interpolazioni

u B-spline vengono definiti punti di controllo per rappresentare una curva con un polinomio del terzo grado o superiore

u Catmull Rom Spline viene cercata la curva che meglio interpola i punti con un polinomio del terzo grado

R.Cucchiara


30

Rappresentazione con B-spline

thresholding withhisteresis

INTENSITY SLICINGthresholding with

histeresisMORPHOLOGYclosing, opening,

filling..

THINNINGSampled

(chain coded)B-SPLINE

R.Cucchiara


31

Catmull-Rom spline

u Vengono definiti un insieme N di punti di controllo sottocampionando i numeri di edge di k N=E/k. Le Catmull-Rom splines sono definite in un intervallo continuo t Î [0,1] ,

u p(i) p(i+1)

u Questa equazione del terz’ordine definisce una funzione continua da p(i) ap(i+1), Le cui tangenti in p(i) p(i+1) hanno la direzione e sono parallele a (p(i+1)- p(i-1))/2 e (p(i+2)- p(i))/2

u Per disegnare la curva poi possono essere indicati piu’ punti per t=0 a 1 ad es. k punti.

R.Cucchiara


32

Esempio k=10

R.Cucchiara


33

Esempio k=40

R.Cucchiara


34

Esempio k=100

R.Cucchiara


35



Punti Curve



Filling


..


R.Cucchiara


36

Descrittori di regioni

u Descrittori di feature associate alle regioni

u Feature geometriche relative a tutta la forma

u Feature topologiche relative alla forma

u Colore relative ai punti della regione

u Tessitura relative a parti o tutta la regione

u Movimento relative a parti o tutta la regione

………….

R.Cucchiara


37

Rappresentazione di oggetti 2D

u Dopo la segmentazione di una immagine 2Du Vengono estratte REGIONI, FORME, OGGETTI 2Du Definiamo con il simbolo l’insieme di pixel 8-connessi al punto (i,j).

u è una regione connessa

se

Una regione connessa puo’ essere descritta attraverso la lista dei suoi punti

8( , )i jN

( ){ }8( , ) , : 1 1i jN l m I l i m j= ∈ − ≤ ∧ − ≤

R I⊂ ( )1, , : ,..., nx y R X I X x x∀ ∈ ∃ ⊂ =

1

81ii x nx N x x x y

+∈ ∧ = ∧ =

R.Cucchiara


38

MOMENTI SPAZIALI

u L’analisi dei momenti spaziali si opera sia sull’immagine binaria che a livelli di grigio.

u Una regione a livelli di grigio puo’essere vista come una densita’ di probabilita’di una variabile 2D random, che puo’ essere descritta con sue informaizonistatistiche come i momenti [1-4]

u Un momento di ordine (r+s) e’ dipendente dalla rotazione dalla traslazione e dalla scala ed e’ dato da

u che discretizzato

u dove r e s sono interi non negativi il parametro r+s e’ l’ordine del momentou le combinazioni di r ed s generano un infinito numero di momenti che puo’

essere impiegato per specificare f(x,y)

dxdyyxfyxsrm sr ),(),( ∫∫+∞

∞−

+∞

∞−

=

∑ ∑= =

=Ii Jj

sr jifjisrM..1 ..1

),(),(

R.Cucchiara


39

MOMENTI

u Il momento di ordine 0 e’ l’area della sagoma se binarizzata ( o la somma del valore dei pixel)

u e’ detta image surface

u ci sono due momenti del primo ordine

u le coordinate del baricentro si definiscono dal rapporto

u i0=M(1,0)/M(0,0)u j0=M(0,1)/M(0,0)

∑ ∑= =

=Ii Jj

jifM..1 ..1

),()0,0(

∑ ∑= =

=Ii Jj

jijfM..1 ..1

),()1,0(

∑ ∑= =

=Ii Jj

jiifM..1 ..1

),()0,1(

R.Cucchiara


40

MOMENTI CENTRALI NORMALIZZATIu Noto il baricentro e’ possibile ricostruire i momenti centrali, con il nuovo

riferimento centrale all’oggetto

i0,j0i

j jc

ic

∑ ∑= =

−−=Ii Jj

srsr jifjjiiJIsrMc..1 ..1

),()0()0()/(1),(

Mc(1,0) e Mc(0,1) sono =0

I momenti centrali sono invarianti alla traslazione

i0,j0

i

j jc

ican

u i momenti centrali opportunamente scalati sono stati impiegati per definire degli invariantidell’ oggetto

Mc(r,s)V(r,s)=

M[0,0]a dove a=(r+s)/2 +1 per r+s=2,3….

R.Cucchiara


41

CIRCOLARITA’

u Secondo una definizione di Haralick (1974) CIRCOLARITA’ puo’ essere definita come il rapporto tra il valor medio e la varianza

u C=1 cerchio, 0.7854 quadrato, 0.539 triangolo isoscele...u CIRCOLARITA’ rileva quanto piu’ i punti sono vicini a baricentrou se K e’ il n. di pixel di bordo

u gode delle proprieta’u 1) man mano che cresce la forma circolare, C cresce monotonicamenteu 2) il valore di C per forme digitali e continue/simili e’ simileu 3) e’ indipendente dall’area e dall’orientazione

20

20

1..0

)()()/1( jjiiK mmKm

−+−= ∑−=

µ

220

20

1..0

2 ))()(()/1( µσ −−+−= ∑−=

jjiiK mmKm

µσ /=C

R.Cucchiara


42

RETTANGOLARITA’

u Rettangolarita’R=A/Aeu dove Ae e’ l’area dell’extent ossia del minimo rettangolo che contiene l’oggetto

u imin, imax,jmin, jmax sono le 4 coordinate minime massime dell’oggettoAe=(jmax-jmin)(imax-imin)

u dipende dall’orientamento dell’oggetto:

R.Cucchiara


43

PUNTI ESTREMI

u Orientamento: angolo tra la direzione dell’asse maggiore dell’oggetto e il verso positivo dell’asse orizzontale (j)

u Extent orientato come l’oggetto (Exto)

1) Si calcola l’asse maggiore2) si calcola l’asse minore (passante per il baricentro)3) si calcolano i 4 punti di massima distanza dagli assi C1,C2,C3,C44) si calcolano gli assi paralleli agli assi maggiori e minori passanti per C1,,C4 (l1,l2,w1,w2)5) si calcolano i vertici dell’exto V1,V2,V3 e V4 come intersezione di tali assi

C1

C2C4

C3B

V1

V3

V2

V4

l1

l2w2

w1

R.Cucchiara


44

Descrittori geometrici

Minimorettangolo

R.Cucchiara


45

DESCRITTORI

u Descrittori legati all’oggetto orientato e all’exto

u Lunghezza(L) estensione massima nella direzione dell’asse maggiore

u Larghezza(W) estensione massima nella direzione dell’asse minore

u Rettangolarita’ rapporto tra l’area e l’area dell’extoR=A/LW

u Elliticita’ rapporto tra l’area e l’area dell’ellissi orientata

E=A/( (π/4)LW)

u Eccentricita’ quanto e’ allungato E=L/W

22 )41()41(3241 jVjViViVVdVVdVL −+−===

22 )31()31(4231 jVjViViVVdVVdVW −+−===

R.Cucchiara


46

Descrittori geometrici e di colore

R.Cucchiara


47

DESCRITTORI TOPOLOGICI

u Numero di Eulerou E=C-HC n. di componenti connessi dell’immagine (non è la circolarità)u H numero di lacune

u C=2 H=4 E=-2

u il n. di Eulero e’ una proprieta’ topologica invariante a trasformazioni rubber sheet

u e’ una proprieta’ dell’immagine ma se l’immagine contiene un solo oggetto puo’ essere usata come caratteristica visuale

R.Cucchiara


48

BIT QUAD

u Con i bit quad molto accurata si dimostra (Duda 1973)

A= 1/4 n(Q1) + 1/2n(Q2) +7/8n(Q3)+n(Q4)+3/4n(QD)E4=1/4 [ n(Q1) + 2n(QD) -n(Q3)]E8=1/4 [ n(Q1) - 2n(QD) +n(Q3)]u se un’immagine contiene molti oggetti ma poche lacune si puo’ pensare ad E

come il n. approssimato di oggettiu tanto che si puo’ pensare ad una area media A1=A/E

0 000

1 100

1 000 1

0 00 1

000

100

0

1 111

11 0

0

1 100 1

100

1 010

1 110 1

1 10 11

1 0 111

0

101 0

Q0

Q1

Q2

Q3

QD

Q4

R.Cucchiara


49

ESEMPIOO g g e t t o E u l e r o A r e a

1 0 1 3 3 . 7 58 0 1 3 9 . 8 7 59 0 1 4 0 . 7 5

1 1 0 1 3 5 . 8 7 51 9 0 1 4 1 . 6 2 5

6 1 2 5 2 . 1 2 57 1 2 5 5 . 8 7 5

1 2 1 2 4 51 7 1 2 5 21 8 1 2 4 7 . 3 7 5

2 1 8 6 . 1 2 54 1 8 6 . 5

1 0 1 8 31 3 1 8 2 . 3 7 51 5 1 8 22 0 1 8 7 . 5

3 - 1 2 7 4 . 3 7 55 - 1 2 7 6 . 5

1 4 - 1 2 8 8 . 8 7 51 6 - 1 2 8 1 . 1 2 5

050

100150200250300350

-2 -1 0 1 2NUMERO DI EULERO

AR

EA

CORONE QUADRATI CERCHI ELLISSI

R.Cucchiara


50

Rappresentazione del movimento di regioni

u Estrazione del movimento in video:

Calcolo e rappresentazione del movimento di

tutti i punti (motionfield)

Segmentazione inoggetti

Calcolo e rappresentazione delMovimento dell’oggetto

Calcolo e rappresentazione del movimento dei punti dell’oggetto

Individuazione dei punti in movimento

Calcolo e rappresentazione del movimento dei

punti (motionfield)

Aggregazione dei punti in oggetto

Featuretracking

R.Cucchiara


51

Individuazione dei punti

u I punti vengono individuati come in movimento con tecniche

u Frame difference- single differenceu Frame difference- double differenceu Background suppression

u Vengono rappresentati– Come template --à poi aggregati in blob b/n– Come punti a colori


R.Cucchiara


52

Single Frame difference

u Hp: Un’apprezzabile variazione della luminosità di un pixel indica la presenza di un moto relativo tra la scena e la sorgente di acquisizione.

u Data una sequenza di immagini {In}, l’immagine differenza tra due frames Dn è definita dalla differenza tra i valori di luminosità dei pixel corrispondenti nei due frames successivi In e In-1 della sequenza.

u Dn(i , j) = | In(i , j) - In-1(i , j) |u Stationary Region Sn = {p(i , j) ∈ In | Dn(i , j) = 0} -à > Th♦ Moving Region Mn = {p(i , j) ∈ In | Dn(i , j) ≠ 0}

♦ Problemi♦ Delocalizzazione♦ Presenza di ghost Frame n

Dn

Frame n-1

R.Cucchiara


53

Double-difference

u Corretta se i frame sono disgiuntiu Il Delta-frame dipende dalla

velocita’ degli oggetti [2]

Framen-1

Frame n

Dn

Frame n+1

Dn+1

DDn

R.Cucchiara


54

Double-difference con edge closure

Punti ad alto gradiente +Punti con double difference

Punti di edge ad elevato movimento

Closure and filling

Oggetto in movimento (extent)

MotionGradient

R.Cucchiara


55

Background suppression

u Come calcolare il background (background modeling)– Modelli statistici (gaussiane, mediane, moda..) Grimson 99,Davis 99– Modelli adattativi– Modelli selettivi

– Come eseguire la background suppression– Livello di grigio– Livelli di colore

BackgroundSuppression

BackgroundUpdate

Segmentation

It

MVOt

DBt

Bt

R.Cucchiara


56

Approcci al background suppression

Feature Systems

Statistics Minimum and maximum values [16], • Median [5,6],

Single Gaussian [18, 4, 22] K Gaussians [23, 3, 24]

Eigenbackgrounds approximation [19, 17]

Minimization of Gaussian differences [20]Adaptivity [5,6,16, 17, 18, 10, 11, 21]

Selectivity [3, 5,6,21, 10, 16]

Background suppressionDifference between image and background [10, 11, 2,5,6]

Difference with eigenbackgrounds [19]

Average probability of current pixel value in K Gaussian backgrounds [2]

Mahalanobis distance [18],[17]

Smallest generalized eigenvalue greater threshold [20]

Shadow[3,4,5,6]

Ghost [16,6]

High-frequency illumination changes Temporal filtering [23, 19, 17]

Size filtering [5,6]Sudden global illumination changes [16,5,6]

R.Cucchiara


57

SaKBot

u SaKBot Statistical and knowledge based objecttracking

TrackingObjectsHistory

t

Scene undestanding

BackgroundSuppression

BackgroundUpdate

Segmentation

It

MVOMVO shadow

DBt

Bt

Object validation

Shadow detection

GhostGhost shadow

Image

Background Foreground

Object

Ghost

MVO

Backgroundsuppression

Shadow

Ghostshadow

MVOShadow

Shadowdetection

R.Cucchiara


58

Sakbot

∉∀

= +

++

otherwisepBkOpKO in O ifpBs

pBt

ttt

)(:)(

)(1

11

≤−∧

≤−∧≤≤

=

otherwise

SpBSpI

HpBHpIVpBVpI

if

pSP S

Ht

tt

ttt

t

0

).().(

).().().().(

1

)( τ

τβα

Bst+1=Median(Ht+1∪ wb[Bt])

{ } { }{ } { }

∪∈∪∈

= ++

ttt

tttt

wghostshadoghost in O O,p ifpBsMVOshadowMVO in O O,p ifpB

pBk)(

)()( 1

1

R.Cucchiara


59



Calcolo e rappresentazione del movimento dei

punti (motionfield)


Rappresentazione

Background suppressionFrame difference….

Optical flowBlock matchingRegion matching

Tracking

R.Cucchiara


60

Rappresentazione di oggetti

R.Cucchiara


61

Movimento e optical flow

u Movimento come motion fieldu Calcolo dell’optical flow

(+smoothed constraint) Horn Schunck Artificial Intelligence 1981(+first order least squares technique) Baindsbridge-Smith, Lane Image and Vision Conmputing 1997

0IvIuI tyx =++

∂∂

∂∂

∂∂

∂∂

∂∂

∂∂

=

yI

xI

yI

xI

yI

xI

A

2525

22

11

MM

∂∂

∂∂∂∂

=

tI

tItI

B

25

2

1

M

( ) BAAAvu TT 1−

=

Molto sensibile al rumore

Optical flow medioDescrive direzioneVersoIntensita’

R.Cucchiara


62

Rappresentazione

Solo oggetti in movimentoCon aOF>th

Background suppression

R.Cucchiara


63

Rappresentazione del movimento degli oggetti

4

3

21

2

3

1

4

5

150

200

250

120 170

ground truth

with shadow suppression

without shadow suppression

Frame #1302

Frame #1302

Frame #1314

Frame #1325

Rappresentazione dellatraiettoria Confronto con ground truth

R.Cucchiara


64

Modelli probabilistici di apparenza

u Gli oggetti possono essere rappresentati per l’individuazione del movimento attraverso [25-28] modelli di apparenza

u L’oggetto non e’ rappresentato dal punto presente solo nel frame corrente mau Modelli di apparenza: ogni punto dell’oggetto e’ rappresentato dalla sua

apparenza in uno spazio colore in un intervallo di tempou Modelli probabilistici: il modello dell’oggetto non e’ cio’ che e’

deterministicamente nell’ultimo frame ma cio’ che puo’ essere stimato o desunto in un intervallo di tempo Blob mod prob. Mod. app.

R.Cucchiara


65

Modello di apparenza

u Temporal template (Davis BobickCVPR97)

u View-specific representation of the action

u Motion-energy image MEIu D binary image : punti in moto

u E(x,y,t)=U i=1..(T-1) D(x,y,t-i)

u T e’ l’intervalllo di osservazione di un’azione

u Motion-history image

H(x,y,t)= T i f D(x,y,t)=1max(0, H(x,y,t-1)-1) otherwise

R.Cucchiara


66


u Apparenza se la probabilita’ e ‘ maggiore di 0.3

Se (x,y) VOP(x,y,n) = P(x,y,n-1)ß

Se (x,y) VOModello di probabilita’( A.Senior PETS2002)P(x,y,n) = P(x,y,n-1)ß +(1- ß)

Se (x,y) VOMRGB(x,y,n) = MRGB(x,y,n-1)

Se (x,y) VOModello di apparenzaMRGB(x,y,n) = MRGB(x,y,n-1)a + I(x,y,n)(1-a)

P(x,y,n,T)= ß T P(x,y,n-T)+Σ j=1..T ß T (1- ß )m(x,y,n-j)

R.Cucchiara


67


Impiego:Affinare il posizionamento dei track sul frame corrente Ottenere informazioni visuali sull’oggetto:Ü SilhoutteÜ Variazioni non rigide

Gestire le sovrapposizioni Gestire le sottosegmentazioni

R.Cucchiara


68

Gestione delle sovrapposizioni

u Tramite il modello dell’apparenza si puo’ definire quanto probabilisticamente un punto appartiene ad un track e quindi associare un ordine di profondita’

R.Cucchiara


69

Esempio

u Video rappresentazione con modello probabilistico

R.Cucchiara


70

Rappresentazione dello sfondo

u Operazioni di mosaicatura…

u esempio

R.Cucchiara


71

Motion con Feature Tracking

u Algoritmi tratti dalle tecniche di Lucas (Tomasi) Kanade



Featuretracking

Selezione di featureDi basso livello (es. punti angolosi) Tracking delle feature

aggregazione delle feature con moto uniforme

R.Cucchiara


72

Esempio feature angolari

u Algoritmo di Lucas Kanadeu 1) selezione di feature salienti (autovalori)u 2) block matching per ottenere un dato di optical flow

u Selezione di n feature Fpi(t) i=1…n n< Nmax

Condizioni di filtraggio:Una feature Fpi(t) viene eliminata se, data la sua corrispondente Fpi(t+1), seu Fpi(t), Fpi(t+1) in steering wheels zoneu Fpi(t), Fpi(t+1) in modello ellisse centrata nel steering wheels central pointu Angolo (Fpi(t), Fpi(t+1)) <ThMinAngleu Angolo (Fpi(t), Fpi(t+1)) >ThMaxAngle

R.Cucchiara


73



Punti Curve



Filling


..


R.Cucchiara


74

Rappresentazione delle relazioni spaziali

u Segmentazioni di immagini in regioni (o oggetti)u Calcolo di attributi associati ad ogni regioneu Calcolo delle relazioni tra regioni

– Relazioni spaziali– Relazioni topologiche

u Rappresentazione delle relazioni– Metodi dichiarativi- regole– Metodi basati sui grafi

t Grafi, alberi..

u Impiego delle relazioni e delle rappresentazioni– Graph matching– Information retrieval– Model matching per riconoscimento e classificazione– localizzazione

R.Cucchiara


75

Grafi

u Un grafo G è una coppia ordinata G=(V,E) dove V è un insieme non vuoto detto insieme dei vertici del grafo ed è detto l’insieme dei lati o archi

u Un grafo diretto D è una coppia D=(V,E) dove è una relazionebinaria su V.

u Siano G=(V,E) e G'=(V',E') due grafi. Una funzione f : V → V’ è detta un morfismo di grafi se ∀ v1,v2 ∈ V, {v1,v2} ∈ E ⇒ {f(v1), f(v2)} ∈ E’.

u un morfismo sarà denotato anche con f : (V,E) → (V’,E’).

u Un morfismo f : G → G’ si dice un isomorfismo se u - f è bigettiva (biettiva)u - f--1 è a sua volta un morfismo.

u Si dice albero un grafo connesso e senza cicli.

⊆

2V

E

E V V⊂ ×

R.Cucchiara


76

ARG

u ARG Attributed relational graph [1] Esempio

u Individual regions are represented by size (s), computed as the size of the area it occupies,perimeter (p) computed as the length of its bounding contour, roundness (r), computed asthe ratio of the smallest to the largest second moment and orientation (o), defined to be the angle between the horizontal direction and the axis of elongation. This is the axis of least second moment.

u Spatial relationships between regions are described by the following set of features: relative distance (rd), computed as the minimum distance between their surrounding contours, relativeorientation (ro) defined as the angle with the horizontal direction of the line connecting the centers of mass of their regions and relative position (rp) taking values corresponding to regions which are the first one inside the other (-1), outside each other (0) or, the second inside the first one (1) respectively.

R.Cucchiara


77

ARG

u Si puo’ utilizzare un ARG per definire il grafo delle adiacenze

A

B

C

DE

F

R.Cucchiara


78

Arg Attributed relational graph

u Spesso la relazione a grafi viene usata per ricerca di similarita’u A volte anche in ausilio alla segmentazione es Markof Random Field per

Region Merging [3]

R.Cucchiara


79

Rappresentazione del movimento

Segmentazione inoggetti


Calcolo e rappresentazione del movimento dei punti dell’oggetto

Segmentazione frame by frame sul colore

Spatial Adjacency graph

Region matching à motion vector

Markov Fandom Field

R.Cucchiara


80

Impiego di ARG per motion detection

R.Cucchiara


81

Proprieta’ di Inclusione

R0

Def2: Ra è inclusa in Rb ⇔ ∀ punto x∈Ra ⇒ x∈Convex Hull(Rb)

Esempio:

segmentazione immagine dermatologica

Def1: R0 regione dummy rappresentante il bordo esterno dell’immagine.[2]Ra è inclusa in Rb se non ∃ un percorso di punti che porta da Ra a R0 senza passare da Rb

R.Cucchiara


82

Grafo e albero topologico (di inclusione)

A

B

C

DE

F

A

B

C

DE

FL’inclusione gode della proprieta’Anti-simmetrica Transitiva --->

R.Cucchiara


83

Topological Tree

Def: Il Topological Tree (TT) è un albero i cui nodi sono regioni di una immagine e gli archi rappresentano la proprietà di inclusione.

• Possibile soluzione:

Segmentazionecolore

CostruzioneTT

Immagine{ }iR R= TT

Svantaggio: Come fare la segmentazione??

Altra soluzione: costruire l’albero durante la segmentazione dell’immagine. Vantaggio: privilegio la segmentazione di aree rispetto altre

R.Cucchiara


84

Recursive FCMRecursiveFCM(RK,PK)

Condizionipartizionamento

Fine

RichiamoRecursiveFCM(Ri,Pi)

Organizzazione per corretto richiamo ricorsivo

Inserimentonell’albero

regione “esterna”

Partizionamento

{ }iR=R

Sì

Inserimentonell’albero

No

Eliminazione regioni“non significative”

GARBAGECOLLECTOR

R.Cucchiara


85

Recursive FCM

u Partizionamento:

LABELING

{ }iR=RFCM con PCA

PCA1

PCA2

PCA3

ISTOGRAMMI

Cluster1

Cluster2

• Recupero delle regioni eliminate:

RecursiveFCM

R.Cucchiara


86

Esempi di risultati

R.Cucchiara


87

Tree matchingTipo di alberi Non ordinati

Parametrizzati

Metodo:

2. Valutare la distanza fra i due alberi in base alle caratteristiche assegnate ai nodi

1. Eliminare nodi per ottenere 2 alberi isomorfi

Distanza fra gli alberi T e T’

( )

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

( ( ), ( '))

costErase T n costErase T mT T

KTD K T K Tδ

+ + = +

∑ ∑T T'

T T'

n S m SK = S ,S

∈ ∈

marking

Costo della cancellazione di un nodo Distanza fra i due alberi potati

e isomorfi

Albero potato

R.Cucchiara


88

Esempio

Area cancellata

Nodi cancellati

KTD(T,T’)

Segmentazione SegmentazioneTT TT

Immagini confrontate Immagini

confrontate

R.Cucchiara


89

Conclusioni

u Per informazioni:Prof. Rita Cucchiara E.mail [email protected]. Dipartimento di Ingegneria dell'Informazione

Università di Modena e Reggio Emiliahttp//www.ing.unimo.it/ Imagelab http//imagelab.ing.unimo.itvia Vignolese 905, 41100 Modena, Italia Tel. +39-059-2056136 Fax. +39-059-2056129

R.Cucchiara


90

Bibliografiau Istogramma colore1. Scott E Umbaugh, Yansheng Wei, Mark Zuke,“Feature Extraction in Image Analysis”,IEEE

Engineering in Medicine and Biology Magazine , Volume 16, Number 4, July/August 1997, pp. 62-73.2. Philippe Schmid,“Segmentation of Digitized Dermatoscopic Images by Two-Dimensional Color

Clustering”, IEEE Transactions on Medical Imaging, 18(2):164-171, February 1999.3. R. Cucchiara, C. Grana, A. Prati, S. Seidenari, G. Pellacani, “Exploiting Color and Topological

Features for Region Segmentation with Recursive Fuzzy c-means”,In press on Machine GRAPHICS & VISION

4. Majid Mirmehdi, Maria Petrou “Segmentation of color textures”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 22 , February 2000.

u CURVE1. Freeman. ``On the encoding of arbitrary geometric configurations''. IRE Trans. on Electronic Computers, Vol. EC-10, pp. 260--268,

1961.

u HOUGH1. J. Illingworth, J. Kittler, " A Survey of the Hough transform" CVGIP vol 43, pp. 221-238, 19882. V.F. Leaves “ Shape detection in computer vision using Hough Transform” Springer Verlag Ed., 19923. D. C. W. Pao, H.F. Li “Shape recognition using the straight line Hough Transform: Theory and Generalization” IEEE

Trans. on PAMI vol 14 n. 11 pp 1076-1089, 19924. R.Cucchiara, F. Filicori “The Vector-Gradient Hough Transform” IEEE Transactions on PAMI 20 n.7 jul 1998 pp 746-

7515. E. R. Davies, “Image space transforms for detecting straight edges in industrial images” Pattern Recognition Letters n.

4 pp 185-192, 1986

R.Cucchiara


91

Bibliografia

u Spline1. E. Catmull, and R. Rom, "A Class of Local Interpolationg Splines,"in Computer Aided Geometric

Design, R. E. Barnhill and R. F.Riesened, Eds. New York: Academic Press, 1974.2. http://www.mvps.org/directx/articles/catmull/3. C GRANA, G PELLACANI, R CUCCHIARA, and S SEIDENARI A New Algorithm for Border

Description of Polarized Light Surface Microscopic Images ofPigmented Skin Lesions submitted toTransactions on medical imaging

u Regioni1. Haralick Robert M., Shapiro Linda G.: Computer and Robot Vision, Vol I e II, Addison-Wesley Pub.

Co., Mass., USA, 1992 e nuova versione2. C.-H. Teh and R. T. Chin, "On Image Analysis by the Methods of Moments", IEEE Transactions on

Pattern Analysis and Machine Intelligence, vol. 10, no. 4, July 1988, pp. 496—5133. L. Yang and F. Albregtsen. Fast computation of invariant geometric moments: A new method giving

correct results. In Proceeding of the International Conference on Pattern Recognition (ICPR) 94, pages A:201-204, 1994

4. Dyer, C.R., C omputing the Euler Number of an Image from its Quadtree,CGIP(13), No. 3, July 1980, pp. 270-276

R.Cucchiara


92

Bibliografia

u Movimento1. Y. Kameda, M. Minoh, A Human Motion Estimation Method using 3-successive video frames, Proceedings of

International Conference on Virtual Systems and Multimedia'96, pp.135-140, 1996.2. Cucchiara, R., Piccardi, M., and Mello, P., “Image analysis and rule-based reasoning for a traffic monitoring

system”, IEEE Trans. on Intelligent Transportation Systems, vol. 1, no.2, June 2000, pp. 119-1303. Elgammal, A., Harwood, D., and Davis, L.S., “Non-parametric Model for Background Subtraction”, Proc. of ICCV

'99 FRAME-RATE Workshop, 1999.4. McKenna, S.J., Jabri, S., Duric, Z., and Rosenfeld, A. and Wechsler, H., “Tracking groups of people”, CVGIP, 2000,

vol. 80, pp. 42-56.5. Cucchiara, R. Grana, C., Piccardi, M., and Prati A., “Statistic and knowledge-based moving object detection in traffic

scenes”, Proc. of ITSC’00, 2000, pp. 27-32.6. R. Cucchiara, C. Grana, A. Prati, "Detecting Moving Objects and their Shadows: an evaluation with the PETS2002

dataset," in Proceedings of Third IEEE International Workshop on Performance Evaluation of Tracking and Surveillance (PETS 2002) in conj. with ECCV 2002, Copenhagen, Denmark, May 31, 2002

7. Yoshinari, K., and Michihito, M., “A human motion estimation method using 3-successive video frames”, Proc. of Intl. Conf. on Virtual Systems and Multimedia, 1996, pp. 135-140.

8. Dagless, E.L., Ali, A.T., and Bulas Cruz, J., “Visual road traffic monitoring and data collection”, Proc. of IEEE-IEE VNIS'93, 1993, pp. 146-149.

9. Shio, A. and Sklansky, J., “Segmentation of People in Motion”, Proc. of IEEE Workshop on Visual Motion, 1991, pp. 325-332.

10. Koller, D., Weber, J., Huang, T., Malik, J., Ogasawara, G., Rao, B., and Russell, S., “Towards Robust Automatic Traffic Scene Analysis in Real-time”, Proc. ICPR’94, November 1994, pp. 126-131

11. Rota, N. and Thonnat, M., “Video sequence interpretation for visual surveillance”, Proc. of Third IEEE Int. Workshop on Visual Surveillance 2000, 2000, pp. 59-68.

12. Karmann, K.P., and von Brant, A., “Moving object recognition using an adaptive background memory” in Time varying Image Processing and Moving Object Recognition, Elsevier Science B.V., 1990.

R.Cucchiara


93

Bibliografia[13] Jiang,, C., and Ward, M.O., “Shadow identification”, Proc. of CVPR'92, pp. 606-612, 1992.[14]Kilger, M., “A shadow handler in a video-based real-time traffic monitoring system”, Proc. of

WACV'92, pp. 11-18, 1992.[15] Stauder, J. and Mech, R. and Ostermann, J., “Detection of moving cast shadows for object

segmentation”, IEEE Trans. on Multimedia, vol. 1 , n. 1, pp. 65-76, March 1999.[16] Haritaoglu, I., Harwoord, D., and Davis, L.S., “W4: Real-time surveillance of people and their

activities”, IEEE Trans. on Patt. Anal. and Machine Intell., vol. 22, no. 8, pp. 809-830, 2000.[[17] M. Seki, H. Fujiwara, K. Sumi, “A robust background subtraction method for changing

background”, 2000.[18] C. Wren, A. Azarbayejani, T. Darrell, and A. Pentland, “Pfinder: Real-time Tracking of the

Human Body,” IEEE Trans. on Patt. Anal. and Machine Intell., vol. 19, no. 7, pp. 780-785, 1997.[19] N. M. Oliver, B. Rosario, and A. P. Pentland, “A Bayesian Computer Vision System for Modeling

Human Interactions,” IEEE Trans. on Patt. Anal. and Machine Intell., vol. 22, no. 8, pp. 831-843, 2000.

[20] N. Ohta, “A statiscal approach to background suppression for surveillance systems,” 2001.[121 N. Amamoto, A. Fujii, “Detecting obstructions and tracking moving objects by image processing

technique”, Electronics and Communications in Japan, Part 3, vol. 82, no. 11, 1999, pp. 28-37.[22] S. Jabri, Z. Duric, H. Wechsler, A. Rosenfeld, “Detection and location of people in video images

using adaptive fusion of color and edge information”, 2000.[23] C. Stauffer, W.E.L. Grimson, “Adaptive background mixture models for real-time tracking”, Proc.

of CVPR 1999, pp. 246-252.[24] C. Stauffer, W.E.L. Grimson, “Learning patterns of activity using real-ime tracking”, IEEE Trans.

on Patt. Anal. and Machine Intell., vol. 22, no. 8, pp. 747-757, 2000.

R.Cucchiara


94

Bibliografiau [25] P. Perez1, C. Hue2, J. Vermaak1, and M. Gangnet1Color-Based Probabilistic Tracking ECCV 2002, LNCS 2350,

pp. 661–675, 2002.u [26] Allan D. Jepson David J. Fleety Thomas F. El-MaraghiRobust Online Appearance Models for Visual TrackingIEEE

Conference on Computer Vision and and Pattern Recognition, Kauai, 2001, Vol. I, pp. 415–422u [26] Andrew Senior Tracking people with probabilistic appearance models PETS2002-ECCV 2002u [28]Stefano Morselli Un sistema di tracking basato su modelli probabilistici per analisi in tempo reale Tesi di Laurea

Universita’ di Modena 2002

u GRAPHu [1] E. Petrakis Fast Retrieval by Spatial Structure in Image Databases

http://citeseer.nj.nec.com/cache/papers/cs/25784/http:zSzzSzwww.ced.tuc.grzSz~petrakiszSzpublicationszSzpetr02.pdf/petrakis02fast.pdf

u [2] R. Cucchiara, C. Grana, S. Seidenari, G. Pellacani, "Exploiting Color and Topological Features for Region Segmentation with Recursive Fuzzy c-means," in press on Machine Graphics and Vision, 2003

u [3] M. Gelgon, P. Bouthemy, A region-level motion-based graph representation and labeling for tracking a spatial image partition, Pattern Recognition 33 (2000) 725-740.

TECNICHE DI RAPPRESENTAZIONE DI IMMAGINI · R.Cucchiara Scuola GIRPR La Visione delle Macchine 11...

Documents

Transcript of TECNICHE DI RAPPRESENTAZIONE DI IMMAGINI · R.Cucchiara Scuola GIRPR La Visione delle Macchine 11...