Segmentazione delle immagini

Università degli Studi di BergamoLaurea Specialistica in Ingegneria Informatica

Lezione 6.4

Corso di RoboticaProf. Davide Brugali

L6.

4: S

egm

enta

zion

e2/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Introduzione I La visione è un problema di inferenza:

abbiamo delle misure e un modello vogliamo capire cosa ha causato le misure

Caratteristiche/problemi cruciali grande quantità di dati quali dati (pixel) sono buoni e quali no? dal singolo pixel è difficile capire a che struttura appartiene

La soluzione sta nell’ottenere una rappresentazione compatta del contenuto di spicco dell’immagine che evidenzi tali caratteristiche

Segmentazione è il processo con cui si ottiene tale rappresentazione Tale rappresentazione dovrebbe

Contenere un numero di componenti gestibile Tali componenti dovrebbero essere indicativi

Segmentazione come decomposizione di un’immagine in superpixels: non interessa tanto la forma quanto la coerenza

Ambiguità del termine segmentazione Tecniche di clustering dei dati (anche edge detection lo è) Specifiche tecniche di decomposizione in super-pixels omogenei

L6.

4: S

egm

enta

zion

e3/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Introduzione IILa forma di un oggetto può essere descritta in base: Alla regione occupata

Le regioni dell’immagine di solito hanno caratteristiche omogenee

intensità, colore texture

Si basa sulla suddivisione dell’immagine in regioni significative e omogenee

Ai bordi fra gli oggetti richiede la edge detection

Gli oggetti possono essere estratti In seguito a segmentazione Dopo averne estratto i bordi

L6.

4: S

egm

enta

zion

e4/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Types

Region Growing and Shrinking

Clustering grouping K-means

Graph-Theoretic Clustering Normalized Cuts

L6.

4: S

egm

enta

zion

e5/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Growing and Shrinking I Occorre trovare regioni che rappresentano

oggetti o parti di oggetti

Il dominio X dell’immagine deve essere

segmentato in n regioni R(1),…,R(N)

La regola di segmentazione è un predicato logico con la forma P(R)

L6.

4: S

egm

enta

zion

e6/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Growing and Shrinking II La segmentazione dell’immagine partiziona

l’insieme X in sottoinsiemi R(i), i=1,…,N tali che:

1. X = i=1,..N U R(i)

2. R(i) ∩ R(j) = 0 for I ≠ j

3. P(R(i)) = TRUE for i = 1,2,…,N

4. P(R(i) U R(j)) = FALSE for i ≠ j

L6.

4: S

egm

enta

zion

e7/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Growing and Shrinking III Il risultato della segmentazione è un predicato logico

che ha la forma P(R,x,t)

x è un vettore di caratteristiche associato ad un pixel Coordinate spaziali Intensità Colore Texture

t è un insieme di parametri (di solito dei valori di soglia)

Una semplice regola di segmentazione ha la forma:P(R) : I(r,c) < T

L6.

4: S

egm

enta

zion

e8/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Growing and Shrinking IV In the case of color images the feature vector

x can be three RGB image components {IR(r,c),IG(r,c),IB(r,c)

A simple segmentation rule may have the form:

P(R,x,t) : (IR(r,c) <T(R)) && (IG(r,c)<T(G))&&

(IB(r,c) < T(B))

L6.

4: S

egm

enta

zion

e9/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Region Growing I

Un semplice approccio alla segmentazione: partire da alcuni pixels (seeds) che rappresentano

regioni distinte dell’immagine (istogramma!) accrescerli fino a che tutta l’immagine risulta coperta

Servono una regola che descrive il meccanismo di crescita una regola che

controlla l’omogeneità della regione dopo ciascuna fase

verifica se è possibile unire due regioni distinte

L6.

4: S

egm

enta

zion

e10/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Region Growing II

Meccanismo di crescita: ad ogni fase k e per ciascuna regione Ri(k), i = 1,…,N, si controlla se ci sono pixel non classificati nell’intorno 8-connesso di ciascun pixel del bordo della regione

Prima di assegnare tale pixel a una regione Ri(k), si controlla se la regione è ancora omogenea :

P(Ri(k) U {x}) = TRUE

L6.

4: S

egm

enta

zion

e11/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Region Growing III

Esempio di test di omogeneità: se l’intensità del pixel è vicina al valore medio della regione

|I(r,c) – M(i)| <= T(i)

La soglia Ti varia a seconda della regione Rn e dell’intensità del pixel I(r,c). Può essere data da:

T(i) = { 1 – [s.d(i)/M(i)] } T

L6.

4: S

egm

enta

zion

e12/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Region Growing IV: Merging

Date la media e la deviazione standard dalla media di una regione Ri con n pixel:

M = (1/n)(r,c)€Ri ∑ I(r,c)

s.d = Square root((1/n)(r,c)€Ri ∑[I(r,c)-M]2)

Can be used to decide if the merging of the two regions R1,R2 is allowed, if

|M1 – M2| < (k)s.d(i) , i = 1, 2 , two regions are merged

L6.

4: S

egm

enta

zion

e13/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Split I L’approccio opposto al region growing è il

region shrinking (splitting)

E’ un approccio top-down e incomincia con l’ipotesi che l’immagine sia omogenea

Se non è vero, l’immagine viene suddivisa in 4 sotto-immagini

Questa procedura di splitting viene ripetuta ricordivamente fino a che restano solo regioni omogenee

L6.

4: S

egm

enta

zion

e14/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Split II Supponiamo che l’immagine originale sia un

quadrato N x N, con N potenza di 2(N = 2n): Tutte le regioni prodotte dall’algoritmo di

splitting sono quadrati di dimensione M x M , dove M è pure una potenza di 2 (M=2m,m<=n).

Poiché la procedura è ricorsiva, produce una rappresentazione che può essere descritta da un albero i cui nodi hanno quattro figli ciascuno

L6.

4: S

egm

enta

zion

e15/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Split III

Quadtree

R0 R1

R2R3

R0

R1

R00 R01 R02 R04

L6.

4: S

egm

enta

zion

e16/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Split / Merge I

Svantaggio delle tecniche di splitting: Creano regioni adiacenti e omogenee che

risultano distinte

Metodo Split and Merge– Ad ogni iterazione

lo splitting è seguito da un merging

L6.

4: S

egm

enta

zion

e17/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Split / Merge II Se una regione R non è omogenea (P(R)=

False) viene suddivisa in 4 sotto regioni Se due regioni adiacenti Ri,Rj sono

omogenee (P(Ri U Rj) = TRUE), esse vengono unite

L’algoritmo si ferma quando non è possibile operare alcuno splitting o merging successivo

L’algoritmo di split e merge produce regioni più compatte del algoritmo di solo splitting

L6.

4: S

egm

enta

zion

e18/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Results – Region grow

L6.

4: S

egm

enta

zion

e19/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Results – Region Split

L6.

4: S

egm

enta

zion

e20/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Results – Region Split and Merge

L6.

4: S

egm

enta

zion

e21/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Results – Region growing

L6.

4: S

egm

enta

zion

e22/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Results – Region Split

L6.

4: S

egm

enta

zion

e23/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Results – Region Split and Merge

L6.

4: S

egm

enta

zion

e24/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering I

La CLUSTER ANALYSIS viene usata per determinare gruppi di dati/oggetti simili Gli oggetti sono descritti da

coordinate/features

Viene usata in molti campi Visione artificiale Analisi socio-economiche Ovunque si debbano individuare gruppi distinti

di dati

L6.

4: S

egm

enta

zion

e25/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering II Cluster (gruppo) – Insieme di oggetti simili La somiglianza fra una coppia di oggetti dello

stesso gruppo è maggiore della somiglianza fra oggetti di gruppi diversi

I cluster sono disgiunti – gli oggetti appartengono ad uno solo di essi

L6.

4: S

egm

enta

zion

e26/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering e distanza Distanza – la distanza euclidea può essere usata x

calcolare la distanza/somiglianza Oggetti distanti sono poco simili Le coordinate usate per il calcolo sono I valori dei

feature di ciascun pixel

Xij – il valore della j-esimo feature dell’i-esimo pixelp – numero di features

2

1

)(),( kjij

p

jikki xxdxxd

L6.

4: S

egm

enta

zion

e27/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering e distanza fra cluster

L6.

4: S

egm

enta

zion

e28/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering e centro di gravità Il centro di gravità è il punto con coordinate uguali

alla media delle variabili dei pixel appartenenti al cluster

L6.

4: S

egm

enta

zion

e29/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering - Metodi

Gerarchici – gli oggetti vengono raggruppati, creando una gerarchia di cluster basata sulle distanze tra gli oggetti e gli oggetti e i cluster Raggruppamento o agglomerative clustering

Grouping Suddivisione o divisive clustering

Non-gerarchici – gli oggetti vengono spostati da un cluster all’altro con qualche criterio (ad esempio la variabilità più bassa) K-means

L6.

4: S

egm

enta

zion

e30/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering – Grouping I Si ha una matrice di n oggetti e p variabili Si costruisce la matrice delle distanze tra gli

oggetti Troviamo due oggetti simili (vicini) e li uniamo

in un cluster. I due oggetti sono sostituiti con uno che ha le

coordinate del centro di gravità

ikdD Dove i,k=1,2,..,n

dik – distanza tra due oggetti

L6.

4: S

egm

enta

zion

e31/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering – Grouping II La dimensione della matrice D viene ridotta di

1 (due oggetti sono rimpiazzati dal centro di gravità).

Si calcolano le distanze tra il nuovo cluster e I restanti oggetti

Gli step precedenti devono essere ripetuti fino a che rimane solo un cluster

L6.

4: S

egm

enta

zion

e32/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering – Grouping example

L6.

4: S

egm

enta

zion

e33/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering – Grouping example Standardizziamo i dati (poiché corrispondono

a grandezze diverse):

j

jijij S

xxz

L6.

4: S

egm

enta

zion

e34/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering – Grouping example Determiniamo la matrice delle distanze La distanza minima è quella fra i pixels 5 e 8 – il

primo cluster! Si calcola il loro centro di gravità

2

1

)(),( kjij

p

jikki xxdxxd

L6.

4: S

egm

enta

zion

e35/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering – Grouping example 5 e 8 sono sostituiti– X1, X2, e X3 sono le

medie relative a questi 2 oggetti e danno il centro di gravità;

Nella prima colonna ci sono I numeri dei pixels, nella seconda quelli dei cluster

L6.

4: S

egm

enta

zion

e36/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering – Grouping example La distanza minima è tra i pixels 2 and 4: il

nuovo cluster di cui va calcolato il centro che sostituisce i dati dei pixels 2 e 4

L6.

4: S

egm

enta

zion

e37/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering – Grouping example Restano 8 clusters. Eseguiamo I restanti 7 step L’ultimo step mostra cluster irregolari; rimane il pixel

9 rimane e l’uòtima matrice D Alla fine tutti gli oggetti stanno in un cluster

L6.

4: S

egm

enta

zion

e38/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering – Grouping example Come scegliamo i

cluster? Consideriamo la minima

distanza tra clusters. Il dendrogramma illustra gli oggetti e le distanze minime tra di essi secondo la procedura di grouping

Tagliamo le braccia del dendrogramma in qualche punto e otteniamo cluster diversi (è una nostra scelta)

L6.

4: S

egm

enta

zion

e39/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering – Grouping example Gli oggetti all’interno dei cluster sono simili?

Rispetto a che cosa? Per rispondere, usiamo la media e la media

globale

L6.

4: S

egm

enta

zion

e40/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering – K-means Lo scopo è creare k cluster situati il più lontano

possibile, mentre i cluster contengono pixel simili1. Vengono scelti k pixel, come se fossero i centri di

gravità (ad esempio, quelli più lontani tra di loro o basandosi sull’istogramma)

2. Ciascun pixel viene associato al centro più vicino, assicurandosi che non vi siano cluster vuoti

3. Vengono calcolati i centri di gravità dei cluster così creati

4. Le fasi 2 e 3 devono essere ripetute finché1. non si hanno più spostamenti dei pixel fra cluster o

dei centri di gravità

2. Tali spostamenti sono sotto una soglia prestabilita

L6.

4: S

egm

enta

zion

e41/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering – Esempio K-means A and E sono scelti a caso come centri C è più vicino ad A che ad E, così il cluster 1

consiste di A, B, e C mentre il 2 consiste di D e E. I punti rossi sono i centri di gravità C è più vicino al centro del cluster 2. Pertanto sarà

spostato dal cluster 1 al 2

L6.

4: S

egm

enta

zion

e42/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Clustering by K-means Il risultato di tale algoritmo è trovare un

minimo locale della seguente funzione detta objective function

Dove x indica il vettore di caratteristiche del pixel e c quello del centro di un cluster

I segmenti possono non essere connessi e sparpagliati bisogna introdurre le corodinate spaziali nel vettore delle caratteristiche

L6.

4: S

egm

enta

zion

e43/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Graph Image Segmentation I L’immagine è rappresentata da un grafo G =

(V,E) I veritici sono punti dello spazio dei features Il grafo è completamente connesso Ad ogni lato è associato un peso w(i,j) che è

funzione della similarità fra i vertici i and j.

Obiettivo: Partizionare l’insieme V negli insiemi disgiunti V1,..,Vn, dove la similarità tra i vertici di Vi è alta e quella tra I vertici di Vi e Vj è bassa

L6.

4: S

egm

enta

zion

e44/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Graph Image Segmentation II

V: nodi/vertici del grafoE: lati/archi che connettono i vertici

G = {V,E}

PixelsSimilarità fra Pixel

Slides from Jianbo Shi

L6.

4: S

egm

enta

zion

e45/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Graph Image Segmentation III I pesi/affinità più comuni (Wij) sono

Luminosità

Colore

Coordinate spaziali

Texture

L6.

4: S

egm

enta

zion

e46/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Normalized Cuts I Decomponiamo il grafo in 2 due insiemi disgiunti A e B

Cut(A,B) è una misura della similarità tra i due gruppi Minimizzare Cut(A,B) dà una partizione col massimo di

disassociazione Esistono algoritmi efficienti e “veloci”

Tuttavia

BvAu

vuwBACut,

),(),(

L6.

4: S

egm

enta

zion

e47/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Normalized Cuts II Data una partizione (A,B) di V, definiamo

Ncut(A,B) misura la similarità tra due gruppi, normalizzandola sul “volume” occupato dai due gruppi all’interno del grafo

Ncut(A,B) ha un valore minimo se A e B condividono lati con pesi bassi al proprio interno hanno lati con pesi alti

VtAu

tuwVAassoc

VBassoc

BAcut

VAassoc

BAcutBANcut

,

),(),(

),(

),(

),(

),(),(

L6.

4: S

egm

enta

zion

e48/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Normalized Cuts III: Matrix Form D is an n x n diagonal matrix with entries

W is an n x n symmetrical matrix

j

jiwiiD ),(),(

),(),( jiwjiW

Dyy

yWDyGMinNcut

t

t

y

)(min)(

Subject to the constraints:y(i) ε {1,-b} dove 1 indica l’appartenenza del vertice ad

un insieme e –b all’altro• ytD1=0

L6.

4: S

egm

enta

zion

e49/47

Dav

ide

Bru

ga l

i –

Un

iBG

- R

ob

ot i

ca

Normalized Cuts IV Permettendo agli elementi di y di assumere valori

reali, MinNcut(G) può essere risolto trovando l’autovettore relativo al secondo più piccolo autovalore

Si stabilisce una soglia T tale che Se yi<T appartiene ad un insieme Se yi>=T appartiene all’altro insieme

Come scegliere la soglia? Costante, ad esempio (0, or 0.5). Il valore mediano Cercare il valore di soglia cui corrisponde il valore minimo di Ncut:

Scegliere n soglie possibili Calcolare Ncut Scegliere la soglia che dà il valore minimo di Ncut

DyyWD )(