Riassunto esame Elaborazione delle immagini, Prof. Placidi Giuseppe, libro consigliato Digital Image Processing, Rafael C. Gonzalez, Richard E. Woods

N L N H N

un numero di pixel non nulli maggiore rispetto a g . A questo punto, i pixel diversi da zero nelle

N H

due immagini rappresentano i pixel di edge ”forti” (high) e ”deboli” (low).

(d) Si esegue il linking degli eventuali vuoti nei pixel non nulli di g y) nel seguente modo:

(x,

N H

i. Si localizza il successivo pixel di edge p in g y).

(x,

N H

ii. Si etichettano come pixel di edge validi tutti i pixel deboli in g y) 8-connessi a p.

(x,

N L

iii. Quando tutti i pixel di g y) sono stati visitati, si impostano a 0 tutti i pixel di g y)

(x, (x,

N H N L

che non sono stati etichettati.

iv. Si inseriscono in g y) tutti i pixel diversi da 0 in g y).

(x, (x,

N H N L

L’immagine ottenuta in questo modo è il risultato dell’algoritmo di Canny.

L’algoritmo di Canny è molto preciso ma chiaramente molto più costoso computazionalmente, qundi viene usato

solo in quelle applicazioni in cui la qualità del risultato è più importante delle tempistiche di riuscita.

9.4 Edge-linking

L’individuazione degli edge è solitamente seguita da un’operazione di edge linking, poiché i punti di edge

potrebbero risultare spuri a causa di rumore o degrado. Vediamo i tre principali metodi di edge-linking utilizzati.

67

9.4.1 Elaborazione locale

Per ogni punto y) riconosciuto come punto di edge, si valuta l’intorno S in cerca di pixel con caratteristiche

(x, xy

simili. Un esempio si basa su

• intensità, ovvero due pixel t) e y) sono simili in intensità (magnitudo) se

(s, (x, t) M y)∣ E

∣M (s, − (x, ≤

dove E è un valore positivo.

• gradiente, ovvero due pixel t) e y) sono simili in direzione se

(s, (x, t) α(x, y)∣ A

∣α(s, − ≤

dove A è un valore positivo.

Il pixel t) viene quindi etichettato come edge se rispetta le due proprietà sopra. Tale formulazione è costosa

(s,

poiché deve essere applicata all’intorno di ogni pixel. Per questo motivo esiste una semplificazione adatta ad

applicazioni in tempo reale che agisce nel seguente modo:

1. Si calcolano le matrici M y)eα(x, y) dell’immagine in input f y).

(x, (x,

2. Si crea un’immagine binaria g(x, y) definita come

⎧

1 se y)∣ T e α(x, y) A T

⎪ ∣M (x, > = ±

⎪ M A

g(x, y) = ⎨

0 altrimenti

⎪

⎪

⎩

dove T è una soglia, A è una certa direzione e definisce un margine di possibili direzioni vicine ad

±T

M A

A.

3. Si impostano i vuoti (definiti come uno zero con un uno su entrambe le estremità) ad 1 per ogni riga

individualmente.

4. Si ruota l’immagine di un certo angolo per individuare i vuoti su ogni direzione.

9.4.2 Elaborazione nelle regioni

In alcuni casi i punti di una regione di interesse sono noti o determinabili. Avendo una conoscenza a priori, è

possibile utilizzare tecniche di linking basate sulle regioni. Un algoritmo in questo ambito è il seguente:

1. Sia P una sequenza di punti di valore 1 distinti e ordinati in un’immagine binaria, si specificano due punti

iniziali A e B.

2. Si specifica una soglia T e due stack vuoti Ap(Aperto) e Ch(Chiuso).

3. Se i punti in P corrispondono a una curva chiusa si pone A in Ap e B in entrambi, altrimenti si pone A

in Ap e B in Ch.

4. Si sceglie il punto V con distanza massima D dal segmento tra l’ultimo vertice in Ap e l’ultimo in

max max

Ch.

5. Se D T , si pone V sullo stack Ap, altrimenti si sposta l’ultimo vertice di Ap in Ch.

>

max max

6. Se Ap non è vuoto si torna al passo 4, altrimenti i vertici in Ch sono quelli che meglio si adattano ai punti

in P .

9.4.3 Elaborazione globale con trasformata di Hough

Spesso si ha a che fare con immagini di edge senza alcuna conoscenza sugli oggetti di interesse, in cui quindi

tutti i pixel sono potenziali candidati per il linking.

Concetto di base

Dato un punto y) nello spazio xy, attraverso esso passano infinite rette y ax+b, ma nello spazio parametrico

(x, = ′ ′

ab tale equazione corrisponde a una sola retta. Analogamente per un punto , y quindi l’intersezione tra

(x ),

tali rette nello spazio parametrico identifica una retta che collega i due punti in xy. In generale, le rette nello

spazio dei parametri che corrispondono a tutti i punti , y possono essere identificate individuando i punti

(x )

k k

nello spazio ab in cui si interseca il maggior numero di rette (punti di accumulazione).

68

Rappresentazione delle rette

Dato che per rette verticali il coefficiente angolare è infinito, si utilizza generalmente la rappresentazione normale

della retta, ovvero xcosθ y sin θ ρ

+ =

dove θ è l’angolo antiorario rispetto all’asse x e ρ la distanza perpendicolare della retta dall’origine. Scrivendo le

equazioni nello spazio dei parametri ρθ, si otterrà una serie di curve sinusoidali, una per ogni punto: se tra due

punti è possibile che vi sia una retta, allora le due curve corrispondenti ad essi nello spazio ρθ si intersecheranno

′ ′

in un certo punto , ρ ovvero i parametri della retta in forma polare.

(θ ),

Suddivisioni

Per discretizzare meglio tali intersezioni, si ricorre alla divisione del piano ρθ in piccoli quadranti detti suddi-

visioni. In questo modo, i valori di ρ che corrispondono a dei punti di accumulazione vengono arrotondati al

valore della cella più vicina.

Algoritmo

L’approccio basato sulla trasformata di Hough per l’edge linking è il seguente:

1. Si ottiene un’immagine binaria dei contorni.

2. Si individuano le suddivisioni del piano ρθ.

3. Si esaminano i contatori delle celle di accumulazione con alte concentrazioni di pixel.

4. Si esamina la relazione di continuità tra i pixel nelle celle scelte.

Riuscire a raggruppare le rette basandosi sulla direzione è un concetto globale applicabile sull’intera immagine.

Questo approccio ha una complessità lineare.

9.5 Thresholding

Tramite il thresholding è possibile eseguire una segmentazione basata sulle intensità delle regioni.

9.5.1 Sogliatura dell’intensità

In generale, l’istogramma di un’immagine potrebbe presentare diversi picchi (mode), ben separate da delle valli.

In questo caso, vuol dire che oggetti diversi si raggruppano intorno ad una certa intensità. È possibile quindi

creare una soglia all’interno di tali valli, in modo da distinguere i punti oggetto dai punti sfondo, oltre che i

diversi punti oggetto tra loro. Il successo della sogliatura dell’intensità dipende da:

• Distanza tra i picchi, che deve essere alta.

• Rumore dell’immagine, che può compromettere la distinzione tra picco e valle.

• Dimensioni degli oggetti e dello sfondo.

• Uniformità dell’illuminazione.

• Uniformità della reflettanza.

9.5.2 Uniformità dell’illuminazione

L’illuminazione non uniforme può compromettere la precisione dell’istogramma. Ci sono tre metodi per correg-

gere l’illuminazione non uniforme, ovvero:

• Moltiplicare l’immagine per l’illuminante inverso, ricavato acquisendo con lo stesso sistema una superfice

uniforme.

• Correggere il modello globale tramite pre-processing.

• Lavorare attorno alle parti non uniformi. 69

9.5.3 Sogliatura globale

Quando le distribuzioni di intensità sono sufficientemente distinte, è possibile utilizzare una soglia singola globale.

Tale soglia deve essere stimata automaticamente e viene ciò viene fatto secondo il seguente processo:

1. Si stima una soglia iniziale T .

2. Si segmenta l’immagine utilizzando T e si ottengono due gruppi di pixel G , G .

1 2

3. Si calcolano le intensità medie dei due gruppi m , m .

1 2

+m

m

4. Si calcola un nuovo valore di soglia T .

1 2

= 2

Ciò viene ripetuto finché la differenza tra T attuale e T precedente è minore di un certo intervallo ∆T .

9.5.4 Metodo di Otsu

Il metodo di Otsu si basa su uno studio probabilistico delle intensità, con lo scopo di aumentare la varianza

interclasse. Sia L il numero di livelli di intensità dell’immagine M N e n il numero di pixel di intensità i,

× i

allora la probabilità normalizzata che un pixel appartenga ad una certa intensità è

n i

p =

i MN

. Sia T k, 0 k L 1 una soglia usata per dividere i pixel in due classi C , C e sia

(k) = < < − 1 2

k

P p

(k) = ∑

1 i

i=0

la probabilità che un pixel sia assegnato alla classe C e P 1 P all’altra, allora il valore di intensità

(k) = − (k)

1 2 1

medio dei pixel assegnati alle classi è k L

1

1

m ip e m .

(k) = (k) = −1ip

∑ ∑

1 i 2 i

P P

(k) (k)

1 2

i=0 i=k+1

La media cumulativa fino al livello k è k

m(k) ip

= ∑ i

i=0

e la media dell’intera immagine è L−1 ip .

m = ∑ i

G i=0

Si può dunque stimare l’efficienza della soglia k tramite la metrica

2

σ (k)

B

η(k) = 2

σ G

dove 2

P m(k)]

[m (k) −

G 1

2

σ (k) =

B P P

(k)[1 − (k)]

1 1

e L−1

2 2

σ m p .

= (i − )

∑ G i

G i=0

∗ ∗

2

L’obiettivo è quindi quello di trovare k che massimizza σ quindi sogliare l’immagine con tale k

(k),

B

9.5.5 Smoothing e sogliatura

Il rumore può causare un malfunzionamento della sogliatura. Ciò può essere spesso facilmente risolto tramite

semplici filtri di smoothing applicati prima del thresholding.

70

9.5.6 Contorni e sogliatura

Un metodo che migliora il processo di sogliatura rendendolo indipendente dalle dimensioni degli oggetti o del

background è l’utilizzo dei contorni. Essi, tuttavia, non sono conosciuti a priori, quindi bisogna applicare uno

dei metodi come il laplaciano o il gradiente. IN particolare, tale algoritmo si svolge nei seguenti passaggi:

1. Si calcola l’immagine di edge e(x, y) di f y) tramite magnitudo del gradiente o valore assoluto del

(x,

laplaciano.

2. Si individua un valore soglia T .

3. Si applica la soglia a e(x, y) per ottenere una maschera binaria g y).

(x,

T

4. Si calcola l’istogramma dei pixel di f y) nei punti (x,y) tali che g(x, y) 1.

(x, =

5. Si utilizza tale istrogramma per segmentare f y).

(x,

9.5.7 Soglie multiple

Il metodo di Otsu può essere applicato anche quando si necessita di più soglie, generalizzando le equazioni

K

2 2

σ P m

= (m − )

∑ k k G

B k=1

dove 1 ip

P p e m

= = ∑

∑ i

k i k P k i∈C

i∈C k

k ∗ ∗