A proposito di spazio scala e
di altre features locali...
Elisabetta Delponte
[email protected]
http://slipguru.disi.unige.it
Il mondo è fatto a scala
Il significato di un oggetto
in un’immagine è diverso
al variare della scala.
Se vogliamo descrivere
“cose” è importante
ricordarsi della scala a cui
le osserviamo.
2
3
Un esempio: le carte geografiche
4
...ancora un esempio
5
Rappresentazioni a multi-scala
Per analizzare
automaticamente
un’immagine abbiamo
bisogno di una
rappresentazione
multiscala delle
informazioni contenute in
essa.
Il tipo di informazioni che
si possono ottenere da
un’immagine dipende dal
rapporto fra le dimensioni
delle sue strutture e gli
operatori per l’analisi.
I2
I1
I0
6
Alcune difficoltà
La prospettiva crea variazioni di dimensioni
Quando si lavora con immagini digitali non
si può dimenticare di considerare il rumore
I dati, come al solito, sono bidimensionali,
mentre il nostro mondo reale è in tre
dimensioni.
Serve una teoria formale che ci permetta di
affrontare il problema del multi-scala.
7
Lo spazio-scala
Lo spazio-scala è una struttura per affrontare la
natura multiscala delle immagini [Witkin83,
Lindeberg94, Koenderink92]
Il segnale originale viene rappresentato da una
famiglia parametrica di segnali derivati nei quali le
strutture fini vengono soppresse.



I ( x , t )  I 0 ( x )  G ( x; t )
8
Idee fondamentali
L’idea base è che le strutture ai livelli a minor
risoluzione devono contenere delle semplificazioni
delle strutture dei primi livelli.
Non deve essere una soppressione accidentale dei
dettagli del segnale.
9
Segnali unidimensionali
Abbiamo ottenuto una
famiglia di segnali
unidimensionali facendo
una convoluzione del
segnale originale I0 con un
filtro gaussiano con
varianza t. (t crescente dal
basso verso l’alto)
I ( x, t )  I 0 ( x)  G( x; t )
IN
I1
I0
10
E cosa succede alle immagini?
11
Un altro esempio
12
Non solo gaussiane...
Linearità
Invarianza per traslazione spaziale
Non possono crearsi nuove strutture nel passaggio da
un livello a più alta risoluzione a uno a più bassa.
Ci sono molte formulazioni dello spazio-scala: il
filtraggio con una gaussiana ci permette di conservare
le proprietà che richiediamo.
Un altra formulazione equivalente si basa
sull’equazione di diffusione del calore:
I t  I  ( I xx  I yy )
13
Assiomi dello spazio scala
Omogeneità e isotropia:
Il filtraggio è invariante a seconda della posizione.
Causalità: non si possono creare nuovi
estremi nel passaggio da un livello a più alta
risoluzione ad uno a più bassa.
Relazioni con meccanismi della visione
biologica.
14
Causalità ovvero “Nulla si crea”
Nel passaggio da un livello a più alta risoluzione
ad uno a più bassa non si possono creare nuovi
estremi:
poiché la derivazione commuta con la convoluzione:
 x n ( g (, t )  f )  g (, t )   x n f
In altre parole: ogni feature individuata a un basso
livello di risoluzione deve avere una “causa” ad
un livello più definito.
15
La visione biologica
Gaussian
derivative
kernels fino al
quarto ordine
in 2D.
Alcuni campi
ricettivi della
retina e della
corteccia visiva
dei mammiferi
possono essere
modellati come la
sovrapposizione
di filtri gaussiani.
16
Feature detection multiscala
Analizziamo nello spazio-scala alcune feature che
conosciamo già:
Edge:

Lvv=0
Lvv e Lvvv sono derivate direzionali del
Lvvv<0
secondo e terzo ordine nella direzione v.
(v è la direzione parallela al gradiente dell’immagine)
Corner
Ridge:

Lp=0
Lpp<0
|Lpp|≥ |Lqq|
Top points
17
Edge
18
Corner
Immagine originale in cui ho
calcolato i corner (con l’algoritmo
visto insieme in laboratorio)
Immagine filtrata con una finestra
gaussiana di dimensione 11 e
varianza 2 in cui ho calcolato i corner
19
Ridge
20
Nessuno è perfetto
Esistono metodi che permettono di selezionare
automaticamente la scala a cui andare a ricercare
una feature. Altrimenti si conservano le
informazioni relative all’intero spazio scala
[Lindeberg96].
Il filtraggio fa perdere precisione nella
localizzazione della feature. Per individuarla
precisamente bisogna ricorrere a un meccanismo
inverso che è piuttosto complicato.
21
SIFT: feature invarianti per scala
Le SIFT sono features locali [Lowe04].
A partire da un’immagine possiamo estrarre
da essa alcune features che siano invarianti
per:
cambiamento di scala
rotazioni
trasformazioni affini attenzione
cambiamenti di illuminazione
cambiamenti di punto di vista
aggiunta di rumore.
22
Step principali
1. Individuazione dei massimi e minimi nello
spazio scala
2. Localizzazione dei keypoint
3. Attribuzione di una direzione ai keypoint
4. Descrizione dei keypoint.
23
La piramide nello spazio-scala
Definiamo lo spazio-scala di un immagine:
L ( x, y ,  )  G ( x , y ,  )  I ( x , y )
con:
G ( x, y ,  ) 
( x2  y 2 )
1
2
2
e
2 2
Introduciamo la differenza di Gaussiane (DoG):
D( x, y,  )  (G ( x, y, k )  G ( x, y,  ))  I ( x, y ) 
 L( x, y, k )  L( x, y,  )
24
Costruzione della piramide
I 1  G  I 0 
  D1  I 1  I 2
I 2  G  I 1 
Dopo aver calcolato la prima Dog, l’immagine
viene sottocampionata e il processo ricomincia.
25
Individuazione degli estremi
Cerchiamo i massimi e
i minimi nella piramide
D(x,y,)
Verifica su livelli
contigui: il massimo
deve esserlo anche per i
livelli di scala vicini.
26
Step principali
1. Individuazione dei massimi e minimi nello
spazio scala
2. Localizzazione dei keypoint
3. Attribuzione di una direzione ai keypoint
4. Descrizione dei keypoint.
27
Localizzazione precisa
Una volta individuato un keypoint dobbiamo:
definirne la posizione precisa nello spazio-scala e
nell’immagine originale
verificare che non sia un edge
valutarne la “forza”.
In base a queste caratteristiche possiamo selezionare
i keypoint più significativi (eliminiamo gli edge e i
punti che hanno basso contrasto)
28
Step principali
1. Individuazione dei massimi e minimi nello
spazio scala
2. Localizzazione dei keypoint
3. Attribuzione di una direzione ai keypoint
4. Descrizione dei keypoint.
29
Direzione principale
Assegnare una direzione canonica a ogni
keypoint ci permette di ottenere descrittori
invarianti per rotazione.
Possiamo calcolare modulo e direzione del
gradiente relativi al keypoint in base alla sua
posizione nello spazio scala.
Per calcolare la direzione principale
rappresentiamo le direzioni nell’intorno del
keypoint con un istogramma.
30
Istogrammi delle direzioni
31
Riassunto
1. Individuazione dei massimi e minimi nello
spazio scala
2. Localizzazione dei keypoint
k=(x,y,s)
3. Attribuzione di una direzione ai keypoint
k=(x,y,s, α)
4. Descrizione dei keypoint.
32
Descrizione dei keypoint
Cerchiamo una descrizione del keypoint che
ci permetta di ottenere invarianza per
cambiamenti di illuminazione o di cambio di
punti di vista.
i valori di grigio nell’intorno del punto di
interesse?
distribuzione delle direzioni nell’intorno.
33
Descrittori
Dati modulo e direzione del gradiente intorno al
keypoint, costruiamo il descrittore come una specie
di istogramma pesato delle direzioni.
34
Descrittori
0
345 77 0 569 25 56
0
... ...
I descrittori sono ottenuti
pesando con una gaussiana
e con il modulo del
gradiente gli istogrammi
delle direzioni nell’intorno
di ogni keypoint.
35
Esempi
36
Esempi
37
Esempi
38
Sift e applicazioni
Matching
Riconoscimento
39
Ancora un esempio
40
Esercitazione
Costruzione di uno spazio scala con filtraggi
successivi di una stessa immagine:
individuazione di edge
individuazione di corner
Calcolo di una piramide di DoG e
individuazione dei massimi e dei minimi.
Confronto con gli edge e i corner individuati
nello spazio-scala.
41