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
Visione Artificiale 08/09 Morfologia matematica 3
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
Visione Artificiale 08/09 Morfologia matematica 4
Dilation
A B= {(-1,0), (1,0) }
A(-1,0) A(1,0) A⊕B
L’insieme B viene normalmente definito elemento strutturante
Visione Artificiale 08/09 Morfologia matematica 5
Dilation
Visione Artificiale 08/09 Morfologia matematica 6
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-
Visione Artificiale 08/09 Morfologia matematica 7
Erosion
Visione Artificiale 08/09 Morfologia matematica 8
Proprietà
• Se l’origine (0,0) appartiene all’elemento strutturante
– (AΘB) ⊆ A ⊆ (A⊕B)
Visione Artificiale 08/09 Morfologia matematica 9
Erosion
Erosion Dilation
Visione Artificiale 08/09 Morfologia matematica 10
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
Visione Artificiale 08/09 Morfologia matematica 11
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
Visione Artificiale 08/09 Morfologia matematica 12
Closing
• C(A, K) = (A+K)-K
K
A A+K
(A+K)-K
Visione Artificiale 08/09 Morfologia matematica 13
Closing
• C(A, K) = (A+K)-K
K
A A+K
(A+K)-K
Visione Artificiale 08/09 Morfologia matematica 14
Closing
K
A A+K
(A+K)-K
Visione Artificiale 08/09 Morfologia matematica 15
Closing
Visione Artificiale 08/09 Morfologia matematica 16
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
Visione Artificiale 08/09 Morfologia matematica 17
Opening
• O(A, K) = (A-K)+K
K
A
A-K=∅=(A-K)+K
Visione Artificiale 08/09 Morfologia matematica 18
Opening
• O(A, K) = (A-K)+K
K
A
(A-K)+K
A-K
Visione Artificiale 08/09 Morfologia matematica 19
Opening
Visione Artificiale 08/09 Morfologia matematica 20
Opening e closing
Visione Artificiale 08/09 Morfologia matematica 21
Esempio
Visione Artificiale 08/09 Morfologia matematica 22
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
Visione Artificiale 08/09 Morfologia matematica 23
Esempio
• Ricerca di punti isolati (8-connessi)– A-J=A
J
KA Ac
Ac-KRisultato
finale
Visione Artificiale 08/09 Morfologia matematica 24
Esempio
• Ricerca di punti isolati (4-connessi)
J
KA Ac
Ac-KRisultato
finale
Visione Artificiale 08/09 Morfologia matematica 25
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
Visione Artificiale 08/09 Morfologia matematica 26
Hit or Miss - Esempio
Pixel compatibili con lamaschera di background
Pixel compatibili con lamaschera per l’immagine
Visione Artificiale 08/09 Morfologia matematica 27
Estrazione di contorni
• Edge(A) = A – (AΘB)
A
B
Edge(A)
Visione Artificiale 08/09 Morfologia matematica 28
Estrazione di contorni
Visione Artificiale 08/09 Morfologia matematica 29
Riempimento di regioni
• Xk = (Xk-1 ⊕ B)∩AC
• X0 = p
• Il procedimento termina quando Xk == Xk-1
X0B
A
X
Visione Artificiale 08/09 Morfologia matematica 30
Componenti connesse
Visione Artificiale 08/09 Morfologia matematica 31
Convex hull
Visione Artificiale 08/09 Morfologia matematica 32
Esercizi
1) Eliminare i conduttori sottili2) Congiungere i conduttori
vicini3) Trovare le componenti
connesse4) Trovare il convex hull di ogni
componente
Visione Artificiale 08/09 Morfologia matematica 33
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
Visione Artificiale 08/09 Morfologia matematica 34
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
Visione Artificiale 08/09 Morfologia matematica 35
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
Visione Artificiale 08/09 Morfologia matematica 36
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
Visione Artificiale 08/09 Morfologia matematica 37
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
Visione Artificiale 08/09 Morfologia matematica 38
Esempio - dilation
f U[f]
k U[k]
U[f]⊕U[k] f⊕k = T[U[f]⊕U[k]]
Visione Artificiale 08/09 Morfologia matematica 39
Esempio - dilation
Visione Artificiale 08/09 Morfologia matematica 40
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]}
Visione Artificiale 08/09 Morfologia matematica 41
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
Visione Artificiale 08/09 Morfologia matematica 42
Esempio - erosion
Visione Artificiale 08/09 Morfologia matematica 43
Esempio - opening
Visione Artificiale 08/09 Morfologia matematica 44
Esempio - closing
Visione Artificiale 08/09 Morfologia matematica 45
Esempi di operatori
Ripreso da
Visione Artificiale 08/09 Morfologia matematica 46
Esempi
Erosion Dilation
Closing Opening
Visione Artificiale 08/09 Morfologia matematica 47
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
Visione Artificiale 08/09 Visione artificiale 49
Tassellazione esagonale
Visione Artificiale 08/09 Visione artificiale 50
Tassellazione triangolare
Visione Artificiale 08/09 Morfologia matematica 51
Trasformata distanza
• 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)
Visione Artificiale 08/09 Morfologia matematica 52
Trasformata distanza
• 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
Visione Artificiale 08/09 Morfologia matematica 53
Trasformata distanza
Visione Artificiale 08/09 Morfologia matematica 54
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
Visione Artificiale 08/09 Morfologia matematica 55
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
Visione Artificiale 08/09 Morfologia matematica 56
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
Visione Artificiale 08/09 Morfologia matematica 57
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
Visione Artificiale 08/09 Morfologia matematica 58
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
Visione Artificiale 08/09 Morfologia matematica 59
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)
Visione Artificiale 08/09 Morfologia matematica 60
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
Visione Artificiale 08/09 Morfologia matematica 61
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|)
Visione Artificiale 08/09 Morfologia matematica 62
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
Visione Artificiale 08/09 Morfologia matematica 63
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
Visione Artificiale 08/09 Morfologia matematica 64
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
Visione Artificiale 08/09 Morfologia matematica 65
Paradossi topologici
• 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
Visione Artificiale 08/09 Morfologia matematica 66
Paradossi topologici
• Si noti che una tassellazione esagonale non provoca paradossi
Visione Artificiale 08/09 Morfologia matematica 67
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