1 RAPPRESENTAZIONE E DESCRIZIONE DELLE FORME. 2 Il processo di segmentazione conduce alla partizione...

1

RAPPRESENTAZIONE E DESCRIZIONE DELLE FORME

2

Il processo di segmentazione conduce alla partizione di una immagine in regioni omogenee

Tali regioni sono date in input al processo di riconoscimento per l’identificazione e la localizzazione degli oggetti della scena

Per tale scopo è necessario definire le modalità di rappresentazione e descrizione della forma delle regioni omogenee ottenute dal processo di segmentazione.

3

Una regione omogenea può essere rappresentata

•considerando l’insieme dei pixel che costituiscono il contorno della regione (rappresentazione mediante il contorno)

•oppure considerando i pixel, come aggregati, che costituiscono l’insieme omogeneo dei pixel della regione stessa (rappresentazione mediante aggregazione di pixel)

Per semplicità, una regione rappresentata dal contorno è chiamata anche esterna, mentre una regione rappresentata come aggregazione di pixel è detta interna.

4

• Una volta scelto lo schema di rappresentazione interna o esterna di una regione, necessita definire le modalità di descrizione della regione stessa, per caratterizzare in caratterizzare in modo oggettivomodo oggettivo la sua forma

• Per esempio, se è scelto un modello di rappresentazione esterna, è importante definire le caratteristiche del contorno estraendo le informazioni topologiche più significativeinformazioni topologiche più significative quali Perimetro, Centro di massa, Area, Numero di concavità, ecc..

• Il ruolo della descrizione di una regione risulta strategico, per il passo successivo, nel processo di riconoscimentoprocesso di riconoscimento degli oggettidegli oggetti, che, partendo dalle misure di forma delle regioni dovrà produrre un risultato non soggettivo.

5

• Ricordiamo che le forme da analizzare sono proiezioni bidimensionali di oggetti 3D che possono apparire diversi in relazione alle diverse condizioni di osservazione (cambiamento della posizione ed orientamento tra oggetto e osservatore)

• Questo genera forme diverse 2D nel piano immagine per uno stesso oggetto

• Da ciò emerge l’esigenza di sviluppare metodi di rappresentazione e descrizione delle forme che idealmente dovrebbero essere invariantiinvarianti rispetto al cambiamento di scalascala, la posizioneposizione ed orientazioneorientazione degli oggetti osservati.

6

• Purtroppo non esistono metodi di descrizione delle forme che operano perfettamente

• Tuttavia sono disponibili diversi metodi di rappresentazione e descrizione che offrono buoni risultati per descrivere oggetti 3D, partendo da una o più delle loro proiezioni 2D, sulla base di alcune proprietà geometriche e topologicheproprietà geometriche e topologiche derivate dalle forme osservate.

7

RAPPRESENTAZIONE ESTERNA DELLE REGIONI

CHAIN CODE

La rappresentazione del contorno può essere realizzata con il metodo di Freeman, chiamato anche chain coding, che consiste di una sequenza di codici numerici rappresentanti una sequenza di segmenti lineari di lunghezza unitaria ed una determinata direzione

In figura è evidenziato come sono codificati i pixel del contorno in un reticolo quadrato sulla base della 4-vicinanza ed 8-vicinanza.

Dal Gonzalez Digital Image Processing cap.11Ma ancheNixon, Aguado:Feature ExtractionAnd Image Processing

8

La descrizione del contorno comprende le coordinate della posizione (x,y) del pixel iniziale del contorno e da un 4-percorso oppure 8-percorso che costituisce rispettivamente la sequenza ordinata dei codici di direzione da 0 a 3 oppure da 0 a 7

La sequenza dei codici di un contorno cambia con il variare del pixel di partenza del contorno

Questo costituirebbe un grosso problema per l’analisi delle forme quando basato sul confronto della sequenza dei codici.

000

1

2

2

3

2

3

S2

S1

1000332212

12212100033

9

Tale inconveniente può essere risolto normalizzando la sequenza dei codici del contorno come segue:

Si considera la sequenza dei codici come una sequenza circolare (costituita dai numeri che indicano i codici di direzione), che può essere riconfigurata mediante operazioni elementari di rotazione circolare (spostamento e inserimento) dei numeri di direzione, (il codice che esce da un estremo della sequenza rientra dall’estremo opposto) fino a quando la sequenza dei numeri forma un intero con valore minimo.

000

1

2

2

3

2

3

S

S’

S’=1×90°=3323211100

1

2212100033

00

1

3

3

2

3

1

2

1

0

1

2

3

10

Rispetto alla rotazione, il codice della sequenza è normalizzato con la derivata prima della codifica

La derivata prima è calcolata dal conteggio del numero di direzioni (in senso antiorario) che separano due codici adiacenti della sequenza

Per esempio, se consideriamo il contorno 10103322 la sua derivata prima rispetto ad un 4-percorso risulterebbe 3133030

Se il codice è considerato come una sequenza circolare, il primo elemento del codice normalizzato si ottiene considerando la distanza direzionale tra l’ultimo (nell’esempio 0) ed il primo codice (nell’esempio 3) della sequenza di input. Dall’esempio considerato il codice normalizzato diventa 33133030

0

1

2

3

11

Un vantaggio del chain code rispetto alla rappresentazione matriciale, specialmente per oggetti binari, è dato dalla compattezza di tale codifica

Per esempio, per un oggetto circolare con diametro di D pixel, nella rappresentazione matriciale occorrerebbero circa D2 locazioni di memoria per memorizzare tutti i pixel dell’oggetto, mentre con il chain code con 8-direzioni, l’oggetto sarebbe codificato in circa D bit (in pratica 3 bit per ogni pixel del contorno)

Per D molto grande, il vantaggio della compattezza risulta più evidente

Un altro vantaggio di questa codifica si riscontra quando necessita calcolare il perimetro e l’area della forma.

12

Impronta (signature)

L’impronta è definita come una funzione monodimensionale per rappresentare un contorno

Considera come funzione impronta la distanza r di ciascun pixel del contorno dal centro di massa del contorno stesso definita in relazione all’angolo compreso tra l’asse delle x ed il vettore distanza r.In pratica, si passa da una rappresentazione bidimensionale del contorno ad una rappresentazione monodimensionale r() che risulta semplificata.

L’impronta dipende dalle dimensioni della forma e dal pixel di partenza del contorno

Si normalizza rapportando la funzione r() rispetto ad un valore massimo predefinito.

13

Impronta (signature)

Varianti della funzione impronta•Angolo formato tra la tangente del contorno con una linea orizzontale di riferimento•Funzione densità delle pendenze

1 2

0

45

90

-90

-45

45°

-45°

+15°

A B

C

D

E

EDC

B

A

14

Rappresentazione mediante scheletrizzazione

In molte applicazioni si hanno immagini che rappresentano particolari oggetti con una dominanza di strutture lineari a spessore variabile e con forme complesse di ramificazioni

Pensiamo per esempio, alle immagini per la ispezione di circuiti stampati, oppure alle immagini provenienti dalla digitalizzazione di mappe di curve di livello (pendenza) del territorio, oppure a quelle ottenute dalla digitalizzazione dei disegni tecnici

In questi casi, per la rappresentazione della forma degli oggetti (curve di livello, piste dei circuiti stampati, tratti del disegno) è conveniente usare il cosiddetto scheletro (skeleton)

15

Rappresentazione mediante scheletrizzazione (MAT - Medial Axis Transformation)

Una spiegazione intuitiva della MAT è data immaginando di voler bruciare due prati uno a forma cilindrica ed uno rettangolare

Nel caso del prato rettangolare si riscontrano dei punti, dove si intersecano le linee di fuoco orizzontale e verticale, che si trovano alla minima equidistanza da almeno due punti del contornoL’insieme dei punti di fuoco con questa caratteristica costituiscono l’asse mediano dello scheletro

Asse medianodello scheletro

Confine di fuoco

Contorno

Contorno rettangolare

Linee di fuoco

Asse medianodello scheletro

16


Più in generale possiamo definire la MAT di una regione R con contorno C come segue:

Ogni pixel di R appartiene all’asse mediano se esso è contemporaneamente equidistante da almeno due punti del contorno C. Nel caso delle immagini digitali, il valore f(P) dei pixel appartenenti all’asse mediano, corrisponde alla distanza di P dal contorno C

17


Una semplice scheletrizzazione è ottenuta applicando la trasformata asse mediano misurando la distanza d(P,C) di ogni pixel P dell’oggetto R dal contorno C.

Le distanze d sono massimi locali se d(P,C) d(Q,C) per ogni pixel Q nelle vicinanze di P.

Il valore della distanza è calcolato operando con una finestra 3×3. Posizionando la finestra in ogni pixel dell’immagine binaria di input f(P), la distanza g(P) del pixel centrale è calcolato aggiungendo al valore del pixel corrente f(P) il valore minimo dei pixel 4-vicinanza (sono i pixel Nord, Sud, Est, Ovest)

g0(i,j) = f(i,j)gk(i,j) = g0(i,j)+min[gk-1(u,v)] k=1,2.......

18


g0(i,j) = f(i,j)gk(i,j) = g0(i,j)+min[gk-1(u,v)] k=1,2.......

19

Immagine RGB diun pattern vascolare

Banda Green Equalizzazione semplice dell’istogramma

Equalizzazione adattiva CLAHE

Sistema automatico di localizzazione dei vasi sanguigni

Esempio di scheletrizzazione in campo medico - preprocessing

20Sistema automatico di localizzazione dei vasi sanguigni

SEGMENTAZIONE

21

Esempio di scheletrizzazione in campo medico

Sistema automatico di localizzazione dei vasi sanguigni

22

Descrizione delle forme

Il passo successivo alla segmentazione riguarda il processo di riconoscimento degli oggetti ossia la loro identificazione partendo dalle regioni omogenee ottenute con la segmentazione

Il processo di riconoscimento utilizza gli schemi di rappresentazione delle regioni discussi in precedenza

Vediamo ora come è possibile estrarre misure misure quantitativequantitative che caratterizzano le forme delle regioni per semplificare il processo di riconoscimento degli oggetti

Le misure delle forme possono essere estratte analizzando i pixel del contorno oppure tutti i pixel delle regioni stesse

23

Descrizione delle forme

Ricordiamo inoltre che necessita definire misure di misure di forme invariantiforme invarianti rispetto alla posizione dell’oggetto proiettato nel piano immagine ed alle diverse possibili proiezioni dello stesso oggetto

Questo porta alla scelta di descrittori di forme invarianti rispetto alla rotazione, traslazione e distanza tra oggetto e osservatore

24

PERIMETRO

Misura geometrica che può essere calcolata partendo dalla rappresentazione del contorno di un oggetto

Esprime la somma delle distanze tra centro e centro della sequenza dei pixel che costituiscono il contorno dell’oggetto

Con una codifica del contorno a 8-direzioni la distanza è espressa dal contributo dei pixel in direzione verticale oppure orizzontale codificati con numeri pari, e dal contributo dei pixel in direzione diagonale (a 45o rispetto agli assi principali) codificati con numeri dispari

Assumendo il pixel con dimensioni quadrate (rapporto tra larghezza ed altezza 1:1), il perimetro dell’oggetto con codifica 8-vicinanza è data da

P n nP D 20

1

2

3

4

5

6

7

DispariPari

dove nP ed nD rappresentano rispettivamente il numero dei pixel con codice pari e dispari del contorno.

25

PERIMETRO

Molto sensibile al rumore presente nell’immagine ed è influenzato dagli algoritmi di segmentazione utilizzati per l’estrazione di regioni omogenee

Molta attenzione si deve prestare quando si vuole usare il perimetro come descrittore di forma valutato da differenti immagini

Il perimetro non è sempre invariante rispetto alla rotazione dell’oggetto. Se il contorno è codificato con 4-direzioni, la misura del perimetro deriva direttamente dal numero dei pixel del contorno (non esiste più il fattore )

2

26

AREAL’Area di un oggetto costituisce una misura geometrica di forma poco significativa.

La misura dell’Area è ottenuta direttamente contando il numero di pixel della regione nel caso di una sua rappresentazione matriciale

Se invece l’oggetto è rappresentato dalla codifica del contorno chain code, la misura dell’Area risulta più semplice rispetto al conteggio dei pixel nella rappresentazione matriciale

Questo deriva dalla compattezza della codifica del contorno

La procedura che calcola l’Area partendo dalla codifica del contorno opera in modo simile all’integrazione numerica.

27

AREA

0+

1+

2

3-

4 -

5-

6

7+

Starty

x1 2 3 4 5 6 7 8 9 10 11

La procedura inizia ad elaborare ogni codice della sequenza del contorno e per il corrispondente pixel deve essere nota l’ordinata y.

La misura dell’Area è calcolata sommando il contributo positivo o negativo dell’Area dei rettangoli, generati in corrispondenza di ogni codice della sequenza, che hanno la larghezza di base uguale ad un pixel e l’altezza uguale all’ordinata y corrispondente.

12

3

4

5

6

7

28

AREAIndicando con A l’area, con S1, S2 ... Sn il codice della sequenza del contorno, l’area è calcolata come segue:1) A=02) Per ciascun elemento del codice Si esegue:

Switch (Si) {case 0:case 1:case 7:

A=A+Y(Si);Break;

case 3:case 4:case 5:

A=A-Y(Si);Break;

case 2:case 6:

Break;};

3) A rappresenta la misura dell’Area stimata della sequenza S1.... Sn.

Y(Si) rappresenta l’ordinata del pixel associato al codice Si del contorno.

29

COMPATTEZZA

Le misure geometriche perimetro ed Area sono entrambe poco significative quando un oggetto è osservato da distanze diverse

In questo caso è necessario definire misure di forme invarianti al cambiamento di scala dell’oggetto nel piano immagine

La compattezza C è una semplice misura (non dimensionale) di forma definita come:

dove P ed A sono rispettivamente il perimetro e l’Area della regione.Il cerchio è la figura geometrica più compatta nello spazio Euclideo con valore minino della compattezza uguale a 4 12.57.Per il quadrato la compattezza è 16 e per un triangolo equilatero è

CP

A

2

36 3/

Forma compatta

Forma non compatta

30

RETTANGOLARITÀ

Questa misura geometrica è data dal rapporto tra l’Area A0 dell’oggetto e l’Area AR del rettangolo minimo che include l’oggetto:

Se l’oggetto ha forma rettangolare R assume valore 1, per un oggetto circolare la rettangolarità è /4 e diventa con valori minori per oggetti con forma complessa.

RA

AR

0

31

ASSE MAGGIORE

Si definisce asse maggiore di un oggetto la corda di massima lunghezza tracciata tra due punti estremi del contorno dell’oggetto stesso

Se indichiamo con Pi e Pj due pixel del contorno C e con d(Pi,Pj) la distanza tra Pi e Pj, la lunghezza dell’asse maggiore D1 è dato da:

D1

Pi

Pj

Asse maggiore

22

),(

1 )()()],(max[ ijij

CPP

yyxxjiD PPdji

)]()arctan[( ijij xxyy

La lunghezza dell’asse maggiore D1 e l’angolo di orientazione dell’asse maggiore rispetto all’asse x costituiscono due parametri utili di descrizione del contorno

32

ASSE MINOREL’asse minore di un oggetto è definito come la corda di massima lunghezza che può essere tracciata in direzione perpendicolare all’asse maggiore. La lunghezza dell’asse minore è calcolata analogamente a quella dell’asse maggiore considerando in questo caso i pixel Pl e Pk del contorno corrispondenti all’estremità dell’asse minore

RETTANGOLO DI BASEIl parallelogramma con lati paralleli a D1 e D2 che include completamente l’oggetto è chiamato rettangolo di base.Il rettangolo di base corrisponde al più piccolo rettangolo che include completamente l’oggetto e presenta una orientazione coincidente con quella dell’oggetto stesso.Il rettangolo di base può essere calcolato se è noto l’angolo di orientazione dell’oggetto.

Asse minore

Pl

Pk

Rettangolo di base

D2

33

ECCENTRICITÀ

La più semplice misura di eccentricità di un oggetto è ottenuta dal rapporto D2/D1 tra le lunghezze dell’asse maggiore e quella dell’asse minore.

ALLUNGAMENTO

Una misura dell’allungamento di un oggetto è ottenuta dal rapporto tra l’altezza e la base del rettangolo di base associato allo stesso oggetto.

Numero di Eulero (visto in precedenza)

34

MOMENTI SPAZIALI

I momenti spaziali possono essere considerati come un approccio statistico per la caratterizzazione della forma di un oggetto

Il livello di grigio associato ad un pixel non è caratterizzato da un valore univoco bensì da una funzione di densità di probabilità p(z) che indica quanto frequentemente osserviamo il livello di grigio z dell’immagine

In precedenza, considerando l’immagine come processo stocastico, abbiamo ricavato alcune caratteristiche derivate dalla statistica del primo ordine

Ricordiamo che

p zH z

H zz

( )( )

( )

0

255 0 1 0 255 10

255

p z z e p zz

( ) , ( )

35

MOMENTI SPAZIALI

Dall’istogramma H sono derivabili alcune caratteristiche statistiche come i momenti di ordine n, con n intero positivo:

m p z znn

z

( ) ( )

0

255

255

0

)(z

zpz

Per definizione il momento di ordine 1 è zero mentre quello di ordine 2 risulta:

255

0

222 ))((

z

zzpm

dove è il valore di grigio medio definito come:

36

MOMENTI SPAZIALI

Possiamo ora estendere i risultati dell’approccio statistico ad immagini bidimensionali allo scopo di definire i momenti spaziali di un oggetto rappresentato con i livelli di grigio f(x,y)

In questo caso f(x,y) rappresenta la funzione densità di probabilità congiunta ed il momento M di ordine (m+n) è dato da:

Al variare degli interi positivi m ed n si genera un insieme indefinito di momenti {Mm,n} in corrispondenza dell’immagine f(x,y) e viceversa.

M x y f x ym nm n

yx, ( , )

37

MOMENTI SPAZIALI

Per caratterizzare la forma di un oggetto in modo univoco è importante definire un insieme ristretto di momenti e possibilmente invarianti rispetto alla posizione, orientazione e scala dell’oggetto

I momenti di ordine zero e del primo ordine sono definiti dalle equazioni:

Per le immagini binarie il momento di ordine zero M0,0 coincide con l’area dell’oggetto.

x yx y

x yx y

x yx y

yxfyMyxyfM

yxfxMyxxfM

yxxyfMyxfM

),(),(

),(),(

),(),(

22,01,0

20,20,1

1,10,0

38

MOMENTI SPAZIALI - INVARIANZA ALLA TRASLAZIONE

Per ottenere l’invarianza dei momenti rispetto alla traslazione,si può calcolare il momento centrale momento centrale di ordine (m+n) che è dato da:

m n cm

cn

yxx x y y f x y, ( ) ( ) ( , )

0,0

1,0

0,0

0,1

),(

),(

),(

),(

M

M

yxf

yxyf

y

M

M

yxf

yxxf

x

x y

x yc

x y

x yc

Area dell’oggetto

Momenti spaziali del primo ordine

39

MOMENTI SPAZIALI - INVARIANZA ALLA TRASLAZIONE

Nel caso di immagini binarie:•f(x,y)=1 per pixel appartenente all’oggetto •f(x,y)=0 altrimenti

pertanto riflette solo la forma dell’oggetto e conseguentemente un insieme di momenti sono unicamente determinati

Per le immagini binarie il calcolo del momento centrale spaziale si riduce a

m n cm

cn

yxx x y y, ( ) ( )

40

MOMENTI SPAZIALI - INVARIANZA AL CAMBIAMENTO DI SCALA

In diverse applicazioni si presenta la necessità di osservare gli oggetti da distanze diverse.

Questo condiziona le misure di forma che devono essere invarianti rispetto al cambiamento di scala dell’oggetto osservato

In queste condizioni possiamo considerare che le coordinate dell’oggetto sono trasformate in x’=x ed y’=y e conseguentemente l’oggetto è trasformato da un fattore di scala con i momenti centrali spaziali modificati da:

m nm n

m n,' , 2

41

MOMENTI SPAZIALI - INVARIANZA AL CAMBIAMENTO DI SCALA

I momenti centrali spaziali possono essere normalizzati rispetto al momento di ordine zero μ00 come segue:

m n

m n,

,'

,'( )

0 0

( )m n 22

dove ηmn sono i momenti centrali spaziali (normalizzati) invarianti rispetto al cambiamento di scala.

Nel caso di immagini binarie, poiché il momento centrale di ordine zero coincide con l’area dell’oggetto, i momenti centrali sono tutti normalizzati rispetto all’area dell’oggetto.

00

42

MOMENTI SPAZIALI - INVARIANZA ALL’ORIENTAZIONE DELL’OGGETTO

I momenti centrali del primo ordine 01 ed 10 sono per definizione zero, infatti

1 01 0

, ( ) ( ) ( , ) x x y y f x yc cyx

xf(x, y) - x

= 0

cx

f x y MM

MM

yyx( , ) ,

,

,,1 0

1 0

0 00 0

0 10 1

, ( ) ( ) ( , ) x x y y f x yc cyx

yf(x, y) - y

= 0

cx

f x y MM

MM

yyx( , ) ,

,

,,0 1

0 1

0 00 0

43


Analizziamo ora il significato dei tre momenti centrali del secondo ordine:

2 02

0 22

1 11 1

,

,

,

( ) ( , )

( ) ( , )

( ) ( ) ( , )

x x f x y

y y f x y

x x y y f x y

cyx

cyx

c cyx

il valore del livello di grigio dei pixel f(x,y) (che in analogia alla meccanica classica rappresenta la densità dell’oggetto) è moltiplicato per il quadrato della distanza dal centro di massa (xc,yc).

44


I momenti 2,0 e 0,2 rappresentano i momenti di inerzia dell’oggetto rispetto all’asse x ed y. Se l’oggetto ha una forma allungata con un asse principale ben definito è possibile calcolare l’angolo di orientazione dell’oggetto come l’inclinazione dell’asse minimo di inerzia rispetto all’asse delle x.

x

yx

),( cc yx

I momenti 2,0 e 0,2 rappresentano i momenti di inerzia dell’oggetto rispetto all’asse x ed y.

Se l’oggetto ha una forma allungata con un asse principale ben definito è possibile calcolare l’angolo di l’angolo di orientazione orientazione dell’oggetto dell’oggetto come l’inclinazione dell’asse minimo di inerzia rispetto all’asse delle x.

2,00,2

1,12arctan

2

1

45


I momenti centrali del secondo ordine sono invarianti rispetto alla rotazione sia che sono calcolati dopo che l’oggetto è ruotato di un angolo sia che sono calcolati rispetto agli assi principali

Una seconda misura di eccentricità può essere espressa in termini dei momenti centrali del secondo ordine come:

dove assume valori da 0 ad 1. Per oggetti a forma circolare tende a

zero mentre per oggetti con forma poligonale tende a 1.

( )

( ), , ,

, ,

2 0 0 22

1 12

2 0 0 22

4

46

MOMENTI SPAZIALI -

47

1 2 3 4 5 6 7

48

Riconoscimento Loghi

49

Esperiemento – Estrazione Momenti di Hu

50


1 2 3 4 5 6 7-0.5

0

0.5

1

1.5

2

2.5

3

3.5

4

Normal

-45

-90-135

Resized 50%

51


1 2 3 4 5 6 70

0.1

0.2

0.3

0.4

0.5

0.6

0.7

Normal

-45

-90-135

Resized 50%

52


53


1 2 3 4 5 6 7-2

0

2

4

6

8

10

Serafino

Brand SiteAirliquide

Ecc

1 RAPPRESENTAZIONE E DESCRIZIONE DELLE FORME. 2 Il processo di segmentazione conduce alla partizione...

Documents

Transcript of 1 RAPPRESENTAZIONE E DESCRIZIONE DELLE FORME. 2 Il processo di segmentazione conduce alla partizione...