SURF

L'algoritmo Speeded Up Robust Features (BETVG08) prende spunto dall'algoritmo SIFT e dalla teoria delle rappresentazioni scala-spazio per proporne una versione ottimizzata dove si sfruttano hessiane approssimate utilizzando l'immagine integrale, sia per individuare i punti caratteristici che per estrarne i descrittori.

SURF è invariante alla traslazione, scala e rotazione ma esiste una variante semplificata, indicata con “U-SURF”, che è solo invariante a variazioni di traslazione e scala: in questo caso l'area intorno al punto individuato non viene normalizzata rispetto alla rotazione nel momento in cui viene estratto il descrittore.

In SURF i punti caratteristici vengono rilevati calcolando massimi locali sul determinante dell'immagine Hessiana definita come:

$$\mathcal{H}(x,y; t)=\begin{bmatrix} \frac{\partial}{\par... ...matrix}D_{xx} & D_{xy} \\ D_{xy} & D_{yy} \end{bmatrix}$$ (5.13)

immagine formata dalle convoluzioni tra le derivate di secondo ordine della gaussiana di varianza $t=\sigma^2$ e l'immagine nel punto $(x,y)$. Per motivi di prestazioni le derivate delle gaussiane vengono quantizzate a numeri interi e approssimate a regioni rettangolari (box filters), ovvero alcune zone rettangolari intorno al punto vengono pesate positivamente, altre negativamente e la loro somma forma l'elemento della matrice $\mathcal{H}$.

La banda di questi filtri approssimati si può stimare come

$$\sigma = \frac{1.2}{9} l$$ (5.14)

con $l$ della dimensione del filtro. Il filtro $9 \times 9$, il più piccolo possibile, per esempio approssima le derivate della gaussiana di varianza $\sigma=1.2$.

L'immagine determinante viene calcolata come

$$\det(\mathcal{H}) = D_{xx} D_{yy} - \left(w D_{xy} \right)^{2}$$ (5.15)

dove $w$ è un fattore che tiene conto della quantizzazione, cerca di compensare i vari errori di arrotondamento, e normalmente viene posto $w=0.912$ costante. Il determinante infine viene normalizzato rispetto alla dimensione della scala coinvolta, in modo da poterlo confrontare a scale differenti.

L'immagine viene analizzata per più ottave (ogni ottava ha un fattore di scala doppio rispetto all'ottava precedente). Ogni ottava è divisa in un ugual numero di livelli di scala. Il numero di scale per ottava è limitato dalla natura strettamente quantizzata del filtro e le gaussiane approssimate non sono ben equispaziate come nel caso di SIFT. Di fatto 4 intervalli per ottava è l'unico numero di suddivisioni possibile.

All'interno di ogni ottava, al variare della scala $s$ e della posizione, viene eseguita una Non-Maxima Suppression $3\times 3\times 3$ sull'immagine del determinante di $\mathcal{H}$. I minimi/massimi locali, interpolati attraverso una quadrica tridimensionale come per SIFT, sono i punti interessanti individuati da SURF. La scala è posta uguale alla varianza del filtro associato $s=\sigma$.

Dai punti di massimo cosı trovati, usando sempre l'immagine integrale, viene estratta l'orientazione dominante nell'intorno del punto (intorno di raggio $6s$ e campionato a passo $s$). Anche questo caso vengono usate feature di Haar di lato $4s$ e pesate con una gaussiana di distribuzione $\sigma=2s$.

Attraverso l'informazione sull'orientazione viene generato un descrittore basato sulle direzioni dei gradienti campionando l'area in un intorno di $20s$, divisa in $4 \times 4$ regioni e pesando i punti con una gaussiana $\sigma=3.3s$. All'interno di ogni regione vengono calcolati $d_x$, $d_y$, $\vert d_x\vert$ e $\vert d_y\vert$. Sia l'orientazione che l'istogramma dei gradienti sono estratti alla scala di rilevamento della feature.