Morfologia binaria Morfologia a toni di grigio Trasformata...

Morfologia matematica

M orfologia binariaM orfologia a toni di grigio

Trasformata distanza

Visione Artificiale 08/09 Morfologia matematica 2

Definizioni preliminari

• A ⊆ En, t ∈En • Traslazione di A rispetto ad un vettore t

At = { c∈En | c=a+t, a∈A }• Riflessione di A

Ar= { c | c=-a, a∈A }• Complemento di A

Ac = En -A

A

A(2,1)

Ar

Le operazioni e definizione sugli insiemi sono date

per note


Somma di Minkowski (Dilation)

• A⊕B = { c∈En | c=a+b, a∈A, b∈B }

• A⊕B = U Ab , b∈B– Si dimostra facilmente: A⊕B = B⊕A

A B= { (0,0), (1,0) }

A(0,0) A(1,0) A⊕B


Dilation

A B= {(-1,0), (1,0) }

A(-1,0) A(1,0) A⊕B

L’insieme B viene normalmente definito elemento strutturante


Dilation


Erosion (Differenza di Minkowski)

• AΘB = { c∈En | c+b∈A, per ogni b∈B }• AΘB = ∩ A-b b∈B

A B= { (0,0), (1,0) }

A(-1,0) A-B

Θ→O-


Erosion


Proprietà

• Se l’origine (0,0) appartiene all’elemento strutturante

– (AΘB) ⊆ A ⊆ (A⊕B)


Erosion

Erosion Dilation


Proprietà

(A+B)+C=A+(B+C) (A-B)-C=A-(B+C)(A∪B)+C=(A+C)∪(B+C) (A ∩ B)-C=(A-C) ∩(B-C)

A+B= ∪Ab A-B= ∩ A-b

A⊆B⇒(A+C)⊆ (B+C) A⊆B⇒(A-C)⊆ (B-C)(A∩B)+C⊆ (A+C)∩(B+C) (A∪ B)-C⊇ (A-C)

∪(B-C)A+(B∪C)=(A+B)∪(A+C) A-(B∪C)=(A-C)∩(B-C)

(A+B)c=Ac -Br

A+Bt=(A+B)t A-Bt=(A-B)-t

A-(B∩C)⊇(A-C)∪(B-C)

Per semplicità di notazione si è usato +e- per gli operatori Erosion e Dilation


Closing

• C(A, K) = (A+K)-K = A•K– A⊆C(A,K)=C(C(A,K),K)

K

A A+K

(A+K)-K


Closing

• C(A, K) = (A+K)-K

K

A A+K

(A+K)-K


Closing

K

A A+K

(A+K)-K


Closing


Opening

• O(A, K) = (A-K)+K = A°K– O(O(A,K),K)=O(A,K)⊆A

K

A A-K

(A-K)+K


Opening

• O(A, K) = (A-K)+K

K

A

A-K=∅=(A-K)+K


Opening

• O(A, K) = (A-K)+K

K

A

(A-K)+K

A-K


Opening


Opening e closing


Esempio


Hit or Miss

• A⊗(J,K) = (A-J)∩(Ac-K)– con il vincolo J∩K=∅

• Permette di trovare strutture regolari (template matching) – Dilation e erosion possono essere considerati come casi

particolari


Esempio

• Ricerca di punti isolati (8-connessi)– A-J=A

J

KA Ac

Ac-KRisultato

finale


Esempio

• Ricerca di punti isolati (4-connessi)

J

KA Ac

Ac-KRisultato

finale


Esempio

• J e K possono essere visti come una unica maschera con tre tipi di valori

– Punti necessariamente di immagine– Punti di background– Punti non rilevanti

M


Hit or Miss - Esempio

Pixel compatibili con lamaschera di background

Pixel compatibili con lamaschera per l’immagine


Estrazione di contorni

• Edge(A) = A – (AΘB)

A

B

Edge(A)


Estrazione di contorni


Riempimento di regioni

• Xk = (Xk-1 ⊕ B)∩AC

• X0 = p

• Il procedimento termina quando Xk == Xk-1

X0B

A

X


Componenti connesse


Convex hull


Esercizi

1) Eliminare i conduttori sottili2) Congiungere i conduttori

vicini3) Trovare le componenti

connesse4) Trovare il convex hull di ogni

componente


Umbra (estensione alle immagini gray scale)

• A ⊆ En, F⊆En-1, x∈F, y∈E• Top di un insieme A (T[A]:F→E):

T[A](x) = max { y | (x, y) ∈ A }• Umbra di f (f:F→E):

U[f] = { (x, y) ∈ F x E | y ≤ f(x) }– T[A] ⊆ A ⊆ U[A] ⊆ En

– U[U[A]] ≡ U[ A]

Insieme A Top di A Umbra di A


Umbra

• Si noti che data una funzione f:R2R si può facilmente definire una nuova funzione f:R3{0, 1} equivalente

– g(x, y, z) = 1 ⇔ z ≤ f(x, y) ⇔ z ∈ U[f(x, y)]– g(x, y, z) = 0 ⇔ z > f(x, y) ⇔ z ∉ U[f(x, y)]

• Posso cioè ricondurre la morfologia a toni di grigio alla morfologia matematica in uno spazio a 3 dimensioni


Gray scale dilation

• Dati: F,K⊆En-1 , f:F→E, k:K→E– F,K⊆R2 , f:F→R, k:K→R (nel caso delle immagini)

• Si definisce dilation di f tramite k (f ⊕k)(x) = max{f(x-z)+k(z) | z∈K, x-z∈F}

• Dal punto di vista computazionale la complessità è equivalente ad una convoluzione


Esempio - dilation

• (f ⊕k)(6) =max{f(6-0)+k(0), f(6-1)+k(1), f(6-2)+k(2)}=max{f(6)+k(0), f(5)+k(1), f(4)+k(2)}=max{5+0, 6+1, 5+0} = 7

fx k f⊕k10 0 131 1 352 0 533 654 565 656 7 7 6 8 5


Esempio - dilation

• (f ⊕k)(5) =max{f(5-(-1))+k(-1), f(5-0)+k(0), f(5-1)+k(1)}=max{f(6)+k(-1), f(5)+k(0), f(4)+k(1)}=max{5-1, 6+0, 5-1} = 6

fx k f⊕k

10 0 231 -1 452 533 454 565 656 5 7 4

-1 -1 0


Esempio - dilation

f U[f]

k U[k]

U[f]⊕U[k] f⊕k = T[U[f]⊕U[k]]


Esempio - dilation


Gray scale erosion

• Dati: F,K⊆En-1 , f:F→E, k:K→E• Si definisce erosion di f tramite k

(fΘk)(x) = min{f(x+z)-k(z) | z∈K, x+z∈F}• Si dimostra che una definizione equivalente è:

fΘk = T{U[f]ΘU[k]}


Esempio - erosion

• (fΘk)(5) =min{f(5-(-1))-k(-1), f(5-0)-k(0), f(5-1)-k(1)}=min{f(6)-k(-1), f(5)-k(0), f(4)-k(1)}=min{5+1, 6-0, 5+1} = 6

fx k f-k

10 0 31 -1 252 433 354 465 656 7

-1 -1


Esempio - erosion


Esempio - opening


Esempio - closing


Esempi di operatori

Ripreso da


Esempi

Erosion Dilation

Closing Opening


Esempi

• Gradiente morfologico– G = (f⊕b) – (fΘb)

• Top-hat transformation– H = f – O(f,b)

Gradiente morfologico Se bi=0 ∀i il gradiente morfologico è la differenza fra il massimo locale e il minimo locale

Visione Artificiale 08/09 Visione artificiale 48

Tassellazione quadrata

Pixel a distanza 1

Pixel a distanza 2

Pixel a distanza 3

Pixel a distanza 4


Tassellazione esagonale


Tassellazione triangolare



• La trasformata distanza è una funzione da una immagine binaria ad una gray-level

• Nella immagine prodotta i pixel di sfondo rimangono a 0, i pixel della figura vengono etichettati con la loro distanza dallo sfondo

• La distanza dipende dal tipo di connessione che si assume per la figura (4/8 connessione)



• Una possibile implementazione è tramite una successione di operazioni di erosione e di somma dell’immagine ottenuta (il risultato dipende dalla scelta dell’elemento strutturante)R = ∅while(A<>∅) do

R = R+A // + è proprio la sommaA = AΘK

done


DT - algoritmo sequenziale

• Si effettuano due scansioni dell’immagine– La prima dall’alto al basso e da sinistra a destra

• ogni pixel della figura è uguale al valore minore fra i vicini già considerati incrementato di 1

– La seconda dal basso all’alto, da destra a sinistra• ogni pixel della figura è uguale al minimo fra i vicini già considerati

incrementato di 1 ed il pixel stesso


DT - algoritmo sequenziale

1 1 1 1 11 1 2 2 2 1 11 2 2 3 2 2 1

1 1 2 3 3 3 2 1 11 2 2 3 4 3 2 21 2 3 3 4 3 3 1

1 2 3 4 4

1

1 1 1 1 11 2 2 2 2 2 11 2 3 3 3 3 2

1 2 3 4 4 4 4 2 12 3 4 5 5 5 3 21 2 3 4 5 6 4 3

1 2 3 4 5

1

1 1 1 1 11 1 2 2 2 1 11 2 2 3 2 2 1

1 1 2 3 3 3 2 1 11 2 2 2 3 2 2 11 1 1 2 2 2 1 1

1 1 1 1 1

1

1 1 1 1 11 2 2 2 2 2 11 2 3 3 3 2 1

1 2 3 4 4 4 3 2 12 2 3 3 3 3 2 11 1 2 2 2 2 2 1

1 1 1 1 1

1


DT - massimi locali

33 3 3 1

2 31

2 2

2 4 4 42 3

2

• I massimi locali sono una rappresentazione compatta della figura

• Possono essere utilizzati per ricostruire la figura: è l’unione dei dischi aventi per dimensione il valore del massimo


Dischi massimi

• La forma dei dischi dipende dall’elemento strutturante• Si ottiene iterando una operazione di dilation tramite

l’elemento strutturante

32

122

2 2222 3

2

222

1 1 1 1

1 1 1 1 1

111

111

11

11

1

111

33 3 3 1

2 3111


Calcolo distanza

• Distanza fra due punti (X, Y )A = { X }; D = Awhile(Y∉A) do

A = (A ⊕ K)∩FD = D + A

done• Seguendo la direzione del

massimo gradiente si ottiene anche il percorso più breve (non è detto sia unico)

Y

X

4 4 4 1

5 8

4 4 4 3 2 15 5 4 3 2 1 1

6 6 6 5 3 1 17 7 28 4 3 2 19 8 7 6 5 4 3 2 18 8 7 6 5 4

67

88


Calcolo distanza

• Se A ≡(A ⊕ K)∩F– allora Y non è raggiungibile da X– F non è connesso

• Il metodo può essere pesante computazionalmente (si pensi ad una spirale)


Trasformata distanza pesata

• La distanza di ogni vicino non è unitaria ma pesata (w)• Algoritmo sequenziale

– Scansione diretta• val = mini {pi+wi} (i vicini precedenti)

– Scansione inversa• new-val = mink {pk+wk} (k il pixel corrente e vicini successivi)

• Esempio (per una migliore approssimazione della distanza euclidea, si ottiene circa il doppio)

2 30 22 3

323


Immagini binarie - definizioni

• Vicini: i vicini di un pixel sono i pixel a distanza unitaria secondo il tipo di connessione scelto

• normalmente si usano due tipi di connessione– 4 connessione e– 8 connessione

• Dati due punti (p,q) di coordinate (i,j) e (h,k) la distanza è calcolata rispettivamente:

– d(p,q) = |i-h|+|j-k|– d(p,q) = max(|i-h|,|j-k|)


Immagini binarie - definizioni

• Percorso: un percorso di lunghezza n da p a q è una sequenza di pixelp=p0 , p1 , .. pi, … pn=qdove pi è un vicino di pi-1

• Componente connesso: un insieme è connesso se esiste un percorso fra due qualunque suoi punti

• Contorno: il contorno di una figura è l’insieme dei punti a distanza unitaria dallo sfondo


Scheletro

• Lo scheletro di F è un sottoinsieme di F con le seguenti proprietà

– è connesso se F è connesso ed ha lo stesso ordine di molteplicità di F

– ha spessore unitario– è centrato in F– include i massimi locali di F


Paradossi topologici

• Il contorno di una figura secondo la 4 connessione è solo 8 connesso

• Il contorno di una figura secondo la 8 connessione è 4 connesso

1 1 1 1 11 1 2 2 2 1 11 2 2 3 2 2 1

1 1 2 3 3 3 2 1 11 2 2 2 3 2 2 11 1 1 2 2 2 1 1

1 1 1 1 1

1

1 1 1 1 11 2 2 2 2 2 11 2 3 3 3 2 1

1 2 3 4 4 4 3 2 12 2 3 3 3 3 2 11 1 2 2 2 2 2 1

1 1 1 1 1

1



• Se considero una 8 connessione interno ed esterno dell’oggetto sono connessi

• Se considero una 4 connessione il contorno non è chiuso (connesso)

1 1 1 1 11 2 2 2 2 2 11 2 3 3 3 2 1

1 2 3 4 4 4 3 2 12 2 3 3 3 3 2 11 1 2 2 2 2 2 1

1 1 1 1 1

1



• Si noti che una tassellazione esagonale non provoca paradossi


Implementazione ricorsiva

1. void etichetta(matrice, i, j, label) {2. if(matrice[i][j]!=non_etichettato) return;3. matrice[i][j] = label;4. etichetta(matrice, i+1, j, label);5. etichetta(matrice, i, j+1, label);6. etichetta(matrice, i-1, j, label);7. etichetta(matrice, i, j-1, label);8. // eventuali pixel diagonali: 8 connessione9. }

♦ Possibili problemi:• Stack overflow• Pixel di bordo

Morfologia binaria Morfologia a toni di grigio Trasformata...

Documents

Transcript of Morfologia binaria Morfologia a toni di grigio Trasformata...