07. Keypoint e Descrittori Locali

Keypoint e Descrittori Locali

Slide

Indice

• Requisiti per Feature Invarianti
• Harris Corner Detector
  • Formulazione Matematica
  • Cornerness e Classificazione dei Pixel
  • Algoritmo e Proprietà
• Scale Space e Laplacian of Gaussian
  • LoG Normalizzato
  • Localizzatori Invarianti per Scala
• SIFT (Scale-Invariant Feature Transform)
  • DoG: Localizzazione dei Keypoint
  • Orientazione dei Keypoint
  • Descrittore SIFT
• SURF (Speeded-Up Robust Features)
  • Box Filters e Immagine Integrale
  • Localizzazione SURF
  • Orientazione e Descrittore SURF
• FAST Keypoints
  • Algoritmo FAST
  • Proprietà e Varianti
• BRIEF: Descrittore Binario
• ORB
• Feature Matching
  • Selezione dei Match Presunti
• RANSAC
  • Algoritmo e Parametri
  • Applicazione ai Keypoint

---

Requisiti per Feature Invarianti

Un localizzatore di keypoint deve garantire ripetibilità: lo stesso punto fisico deve essere rilevato in immagini diverse della stessa scena, anche in presenza di trasformazioni geometriche e fotometriche.

Le invarianze richieste sono:

Trasformazione	Descrizione
Traslazione	La posizione nella scena non cambia il punto fisico
Rotazione	La scena può essere ruotata planare
Scala	L’oggetto può essere più vicino o lontano dalla camera
Illuminazione	Variazioni lineari e non lineari di intensità

---

Harris Corner Detector

Definizione

Il Harris Corner Detector rileva punti di interesse (corner) analizzando come varia l’intensità dell’immagine spostandosi in ogni direzione. Un corner è un punto in cui lo spostamento in qualsiasi direzione produce una variazione significativa.

Formulazione Matematica

La variazione di intensità per uno spostamento $(u,v)$ attorno al pixel $(x,y)$ è:

$E(u,v)={\sum }_{x,y}w(x,y){\left[I(x+u,y+v)-I(x,y)\right]}^2$

dove $w(x,y)$ è una funzione peso (gaussiana o finestra uniforme). Tramite l’approssimazione di Taylor al primo ordine si ottiene:

$E(u,v)\approx \left[\begin{array}{cc}u& v\end{array}\right]M\left[\begin{array}{c}u\\ v\end{array}\right]$

dove $M$ è la matrice di struttura (structure tensor):

$M={\sum }_{x,y}w(x,y)\left[\begin{array}{cc}{I}_x^2& I_x{I}_y\\ I_x{I}_y& I_y^2\end{array}\right]$

Gli autovalori ${\lambda }_1,{\lambda }_2$ di $M$ descrivono le variazioni principali di intensità nelle due direzioni ortogonali.

Cornerness e Classificazione dei Pixel

Per evitare il calcolo esplicito degli autovalori (costoso), si usa la funzione di cornerness $R$:

$R=\det (M)-\alpha \cdot \text{trace}(M{)}^2={\lambda }_1{\lambda }_2-\alpha ({\lambda }_1+{\lambda }_2{)}^2$

con $\alpha \in [0.04,0.06]$. La classificazione dei pixel in base a $R$:

Caso	Autovalori	$R$	Tipo
Corner	${\lambda }_1\gg 0$, ${\lambda }_2\gg 0$	$R>0$ (grande)	Variazione in tutte le direzioni
Edge	${\lambda }_1\gg {\lambda }_2\approx 0$	$R<0$	Variazione in una sola direzione
Flat	${\lambda }_1\approx {\lambda }_2\approx 0$	$\Vert R\Vert$ piccolo	Nessuna variazione

Algoritmo e Proprietà

Algoritmo:

1. Calcola i gradienti $I_x$, $I_y$ (es. con Sobel)
2. Calcola $M$ per ogni pixel (con pesatura gaussiana)
3. Calcola $R$ per ogni pixel
4. Applica una soglia su $R$
5. Sopprimi i non-massimi locali (non-maximum suppression)

Proprietà di invarianza:

Trasformazione	Invariante?	Nota
Rotazione	Sì	Gli autovalori di $M$ non cambiano con la rotazione
Traslazione di intensità ($I\to I+c$)	Sì	Le derivate non cambiano
Scala moltiplicativa di intensità ($I\to cI$)	Parziale	$R$ scala come $c^2$; con soglia adattiva è ok
Scala geometrica	No	Un corner a scala diversa può non essere rilevato

La mancanza di invarianza alla scala geometrica è il limite principale di Harris.

---

Scale Space e Laplacian of Gaussian

Definizione

Lo scale space è una famiglia di immagini ottenute convolvendo l’immagine originale con gaussiane a $\sigma$ crescente. Rappresenta la struttura dell’immagine a diverse scale di dettaglio.

La gaussiana a scala $\sigma$:

$G(x,y,\sigma )=\frac{1}{2\pi {\sigma }^2}\exp \left(-\frac{x^2+y^2}{2{\sigma }^2}\right)$

Il Laplacian of Gaussian (LoG) misura la variazione locale a una data scala:

$\text{LoG}(x,y,\sigma )=\frac{{\partial }^{2}G}{\partial x^2}+\frac{{\partial }^{2}G}{\partial y^2}$

LoG Normalizzato

Per rendere il rilevatore invariante alla scala, il LoG deve essere normalizzato rispetto a $\sigma$:

${\text{LoG}}_{\text{norm}}(x,y,\sigma )={\sigma }^2\left(\frac{{\partial }^{2}G}{\partial x^2}+\frac{{\partial }^{2}G}{\partial y^2}\right)$

La normalizzazione garantisce che blob di dimensioni diverse producano risposte comparabili. La scala caratteristica di un blob è il $\sigma$ che massimizza $|{\text{LoG}}_{\text{norm}}|$.

Localizzatori Invarianti per Scala

Metodo	Localizzazione spaziale	Localizzazione in scala
Laplacian detector	Qualsiasi localizzatore 2D	Massimo del LoG nello scale space
Harris-Laplace	Harris corner in 2D	Massimo del LoG in scala
DoG (SIFT)	Massimo del DoG in 3D	Integrata nella struttura DoG

---

SIFT (Scale-Invariant Feature Transform)

Definizione

SIFT (Lowe, 1999) è il descrittore locale più noto. Combina un localizzatore basato su DoG (Difference of Gaussians) con un descrittore robusto basato su istogrammi di gradienti orientati. È invariante a scala, rotazione e variazioni di illuminazione.

DoG: Localizzazione dei Keypoint

Il Difference of Gaussians approssima il LoG normalizzato in modo efficiente:

$D(x,y,\sigma )=L(x,y,k\sigma )-L(x,y,\sigma )$

dove $L(x,y,\sigma )=G(x,y,\sigma )\ast I(x,y)$ è l’immagine smoothed alla scala $\sigma$.

Struttura piramidale:

• L’immagine è analizzata in ottave (ogni ottava raddoppia $\sigma$, da $\sigma$ a $2\sigma$)
• Ogni ottava contiene $s$ intervalli, con $k=2^{1/s}$
• Per coprire un’intera ottava servono $s+3$ livelli di convoluzione gaussiana (e quindi $s+2$ immagini DoG)
• Tipicamente $s=3$, quindi $k=2^{1/3}$

Localizzazione approssimata: i keypoint sono i massimi e minimi della DoG nello spazio 3D $(x,y,\sigma )$. Un pixel è candidato estremo se è maggiore o minore di tutti i suoi $8+9+9=26$ vicini (8 nella stessa scala, 9 nella scala superiore, 9 nella scala inferiore).

Localizzazione accurata: i massimi discreti non coincidono esattamente con i massimi continui. Si effettua un’interpolazione (sviluppo di Taylor del secondo ordine) per localizzare il keypoint con precisione sub-pixel.

Filtraggio dei candidati:

• Si eliminano i punti con contrasto basso (sensibili al rumore) — soglia sul valore di DoG
• Si eliminano i punti su edge (sfruttando il rapporto degli autovalori della Hessiana, come in Harris)

Orientazione dei Keypoint

Per ottenere invarianza alla rotazione, a ogni keypoint viene assegnata un’orientazione dominante. Per ogni punto dell’intorno (nell’immagine smoothed $L$ alla scala più vicina) si calcola magnitudo e orientazione del gradiente:

$m(x,y)=\sqrt{{\left(L(x+1,y)-L(x-1,y)\right)}^2+{\left(L(x,y+1)-L(x,y-1)\right)}^2}$

$\theta (x,y)={\tan }^{-1}\frac{L(x,y+1)-L(x,y-1)}{L(x+1,y)-L(x-1,y)}$

Viene costruito un istogramma delle orientazioni a 36 bin (10° ciascuno). I contributi sono pesati per la magnitudo e per una gaussiana con $\sigma =1.5\times$ scala del punto. L’orientazione assegnata è il picco assoluto dell’istogramma.

Keypoint multipli

Se esistono picchi locali che superano l’80% del massimo assoluto, vengono generati ulteriori keypoint con stessa posizione e scala ma orientazione diversa.

Descrittore SIFT

Il descrittore è costruito a partire da una finestra orientata attorno al keypoint (ruotata secondo l’orientazione assegnata). Le magnitudo dei gradienti sono pesate con una gaussiana con $\sigma$ pari a metà della larghezza della finestra.

Struttura del descrittore:

1. La regione attorno al keypoint viene partizionata in $4\times 4$ sottoregioni
2. Per ogni sottoregione si costruisce un istogramma di 8 bin delle orientazioni (pesate per la magnitudo)
3. I valori vengono distribuiti nei bin adiacenti tramite interpolazione trilineare (robustezza)
4. I $4\times 4\times 8=128$ valori concatenati formano il vettore descrittore

Normalizzazione (per invarianza all’illuminazione):

1. Normalizza il vettore a norma unitaria → gestisce variazioni lineari di intensità
2. Applica una soglia a 0.2 (scarta valori > 0.2) → gestisce saturazione della camera
3. Rinormalizza a norma unitaria

---

SURF (Speeded-Up Robust Features)

Definizione

SURF (Bay et al., 2008) è una versione computazionalmente efficiente di SIFT. Sostituisce i filtri LoG con box filters calcolabili in tempo costante tramite l’immagine integrale. È invariante a rotazione, scala e illuminazione.

Box Filters e Immagine Integrale

L’immagine integrale $II(r,c)$ è la somma di tutti i pixel nella regione in alto a sinistra di $(r,c)$:

$II(r,c)={\sum }_{r^{\prime }\le r,c^{\prime }\le c}I(r^{\prime },c^{\prime })$

Calcolata in un’unica passata con le formule ricorsive:

$S(r,c)=S(r,c-1)+I(r,c)II(r,c)=II(r-1,c)+S(r,c)$

Grazie all’immagine integrale, la somma dei pixel in un rettangolo qualsiasi si calcola con 4 accessi in memoria: $II(4)+II(1)-II(2)-II(3)$ (angoli del rettangolo). I box filters $D_{xx}$, $D_{yy}$, $D_{xy}$ approssimano le derivate seconde della gaussiana con filtri rettangolari di valori interi. Il filtro base approssima una gaussiana con $\sigma =1.2$.

Localizzazione SURF

La localizzazione si basa sul determinante della matrice Hessiana approssimata:

$H=\left[\begin{array}{cc}{L}_{xx}& L_{xy}\\ L_{xy}& L_{yy}\end{array}\right]\Rightarrow \det (H_{\text{approx}})=D_{xx}{D}_{yy}-(w{D}_{xy}{)}^2$

dove $w=0.9$ è un fattore correttivo. I keypoint corrispondono ai massimi locali di questa mappa.

Vantaggio rispetto a SIFT: non serve ridimensionare l’immagine. Si aumentano le dimensioni dei box filter per analizzare scale diverse, con complessità costante su ogni livello. La localizzazione finale usa non-maximum suppression in un intorno $3\times 3\times 3$ e interpolazione.

Orientazione e Descrittore SURF

Orientazione: risposta ai filtri Haar-like in $x$ e $y$ nell’intorno circolare di raggio $6s$. Le risposte $(d_x,d_y)$ vengono sommate vettorialmente su finestre angolari di $\pi /3$; l’orientazione dominante è la direzione della somma massima.

Descrittore:

1. Regione quadrata $20s\times 20s$ centrata e orientata sul keypoint
2. Divisa in $4\times 4$ sottoregioni
3. Per ogni sottoregione, risposte Haar pesate con gaussiana:

$\mathbf{v}=\left(\sum d_x,\sum d_y,\sum |d_x|,\sum |d_y|\right)$

4. Concatenazione di tutte le sottoregioni → dimensione 64
5. Normalizzazione a vettore unitario (invarianza al contrasto)

Versione estesa a 128

Si separano le somme di $d_x$ e $|d_x|$ per $d_y<0$ e $d_y>0$, e analogamente per $d_y$. Più discriminativa ma doppiamente costosa.

---

FAST Keypoints

Definizione

FAST (Features from Accelerated Segment Test) è un rilevatore di corner estremamente veloce, basato sul confronto di intensità tra un pixel candidato e i suoi vicini su un cerchio discreto di raggio 3.

Algoritmo FAST

1. Considera il pixel $p$ con intensità $I_p$ e soglia $T$ (tipicamente $T=0.2\times I_p$)
2. Seleziona i 16 pixel sull’anello circolare di raggio 3
3. $p$ è un corner se esistono $N$ pixel consecutivi sull’anello tutti con intensità $>I_p+T$ oppure tutti $<I_p-T$
   • $N=12$ → FAST-12, $N=11$ → FAST-11, $N=9$ → FAST-9
4. Accelerazione: si controllano i pixel 1, 5, 9, 13. Se meno di 3 soddisfano la condizione, $p$ non è un corner (scartato subito)
5. Dopo la detection si applica non-maximum suppression

Proprietà e Varianti

Proprietà	Valore
Efficienza	Molto alta
Ripetibilità	Bassa (solo luminosità)
Invarianza rotazione	No (nessuna info direzionale)
Invarianza scala	No (raggio fisso = 3)

Variante per rotazione — orientazione tramite centroide di intensità:

$m_{pq}={\sum }_{x,y\in B}{x}^p{y}^{q}I(x,y)C=\left(\frac{m_{10}}{m_{00}},\frac{m_{01}}{m_{00}}\right)\theta =\arctan \left(\frac{m_{01}}{m_{10}}\right)$

Variante per scala — ricerca dei corner su una image pyramid (immagini riscalate progressivamente).

---

BRIEF: Descrittore Binario

Definizione

BRIEF (Binary Robust Independent Elementary Features) costruisce un descrittore come stringa binaria confrontando l’intensità di coppie di pixel nell’intorno del keypoint. Compatto ed efficiente da confrontare (distanza di Hamming).

Il test binario su una coppia $(\mathbf{x},\mathbf{y})$ nella patch $\mathbf{p}$ (pre-smoothed con box filter):

$\tau (\mathbf{p};\mathbf{x},\mathbf{y}):=\{\begin{array}{ll}1& \text{se }\mathbf{p}(\mathbf{x})<\mathbf{p}(\mathbf{y})\\ 0& \text{altrimenti}\end{array}$

Il descrittore composto da $n_d$ test:

$f_{n_d}(\mathbf{p}):={\sum }_{1\le i\le n_d}{2}^{i-1}\tau (\mathbf{p};{\mathbf{x}}_i,{\mathbf{y}}_i)$

con $n_d\in \{128,256,512\}$. Le coppie di pixel possono essere scelte con diverse distribuzioni (uniforme, gaussiana, griglia polare). Il pre-smoothing con box filter (non gaussiana, per efficienza) riduce la sensibilità al rumore.

---

ORB

Definizione

ORB (Oriented FAST and Rotated BRIEF) combina Oriented FAST e Rotated BRIEF. È libero da brevetti, efficiente e robusto — la principale alternativa a SIFT/SURF.

$\text{ORB}=\underset{\text{keypoint + scala + orientazione}}{\underbrace{\text{Oriented FAST}}}+\underset{\text{descrittore orientato}}{\underbrace{\text{Rotated BRIEF}}}$

• Oriented FAST: keypoint FAST con orientazione (centroide di intensità) e scala (image pyramid)
• Rotated BRIEF: le coppie di pixel vengono ruotate secondo l’orientazione del keypoint → invarianza alla rotazione

---

Feature Matching

Il feature matching trova corrispondenze tra keypoint di due immagini della stessa scena.

Pipeline:

1. Rileva i keypoint e calcola i descrittori (SIFT, SURF, ORB, …)
2. Determina un set di match presunti tramite nearest neighbor search
3. Stima la trasformazione ottimale con RANSAC

Selezione dei Match Presunti

Il match di un keypoint è il suo nearest neighbor (distanza euclidea minima per float, Hamming per binari).

Problema: una soglia globale sulla distanza non funziona bene — le distribuzioni di distanze corrette e errate si sovrappongono.

Soluzione — ratio test: si confronta la distanza 1-NN con la distanza 2-NN:

$\frac{d_{1\text{-NN}}}{d_{2\text{-NN}}}<\text{soglia}$

Se il rapporto è basso, il match è netto (il 1-NN è molto più vicino del 2-NN). Match ambigui vengono scartati.

Approcci per la ricerca efficiente:

• Ricerca esaustiva: $O(n^2)$, accurata ma lenta
• Hashing: funzione hash organizza i descrittori in bucket di oggetti simili
• KD-Tree: struttura dati per nearest neighbor search efficiente in alta dimensione

---

RANSAC

Definizione

RANSAC (RAndom SAmple Consensus) è un algoritmo iterativo per stimare i parametri di un modello in presenza di outlier. Nel feature matching, stima la trasformazione geometrica ottimale (es. omografia) tra due immagini da un insieme di match presunti che include inevitabilmente match errati.

I dati si dividono in inlier (compatibili con il modello) e outlier (non rappresentati dal modello).

Algoritmo e Parametri

Algoritmo — ripeti $K$ volte:

1. Scegli $n$ campioni casuali (il minimal set — numero minimo per determinare il modello)
2. Adatta i parametri $\Theta$ agli $n$ campioni
3. Conta gli inlier $c$: punti con distanza dal modello $<t$

Output: il modello $\Theta$ con $c$ più elevato.

Parametri:

Soglia $t$ (per definire gli inlier): assumendo rumore gaussiano con deviazione standard $\sigma$:

$t^2=3.84{\sigma }^2$

Con questa scelta, il 95% degli inlier ha distanza $d<t$.

Numero di iterazioni $K$: si vuole che con probabilità $p$ (es. $p=0.99$) almeno un sample set sia privo di outlier. Detto $e$ la frazione di outlier e $s$ la dimensione del minimal set:

$K>\frac{\log (1-p)}{\log \left(1-(1-e{)}^s\right)}$

$K$ non dipende dal numero totale di punti $N$.

Esempio — minimal set $s=4$ (omografia), $p=0.99$:

$e$	10%	20%	30%	40%	50%
$K$	5	9	17	34	72

Applicazione ai Keypoint

Per stimare l’omografia $H$ che allinea due immagini:

$H=\left[\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& 1\end{array}\right]$

Il minimal set è 4 coppie di punti corrispondenti. Algoritmo per ogni iterazione:

1. Seleziona 4 coppie di match presunti casuali
2. Calcola $H$ da queste 4 coppie
3. Conta gli inlier per cui $\text{SSD}(p_i^{\prime },H(p_i))<ϵ$
4. Seleziona la $H$ con il massimo numero di inlier (opzionalmente ricalcolata su tutti gli inlier)

Vantaggi e svantaggi:

Vantaggi	Svantaggi
Semplice e generale	Complessità cresce con il numero di parametri
Robusto anche con molti outlier	Non ottimale per stimare modelli multipli
Più scalabile della Hough transform	Non ottimale per modelli approssimati

---

Prossimi Argomenti

Continueremo con:

• Trasformazioni 2D e Image Stitching - omografie e composizione di immagini panoramiche