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 `e invariante alla traslazione, scala e rotazione ma esiste una variante semplificata, indicata con “U-SURF”, che `e 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:
H(x, y; t) =
" ∂
∂x2G(t) ∗ I ∂xy∂ G(t) ∗ I
∂
∂yxG(t) ∗ I ∂y∂2G(t) ∗ I
#
=Dxx Dxy
Dxy Dyy
(5.13)
immagine formata dalle convoluzioni tra le derivate di secondo ordine della gaussiana di varianza t = σ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 H.
La banda di questi filtri approssimati si pu`o stimare come σ = 1.2
9 l (5.14)
con l della dimensione del filtro. Il filtro 9 × 9, il pi`u piccolo possibile, per esempio approssima le derivate della gaussiana di varianza σ = 1.2.
L’immagine determinante viene calcolata come
det(H) = DxxDyy− (wDxy)2 (5.15)
dove w `e 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`u ottave (ogni ottava ha un fattore di scala doppio rispetto all’ottava precedente).
Ogni ottava `e divisa in un ugual numero di livelli di scala. Il numero di scale per ottava `e 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 `e 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 × 3 × 3 sull’immagine del determinante di H. I minimi/massimi locali, interpolati attraverso una quadrica tridimensionale come per SIFT, sono i punti interessanti individuati da SURF. La scala `e posta uguale alla varianza del filtro associato s = σ.
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 σ = 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 × 4 regioni e pesando i punti con una gaussiana σ = 3.3s. All’interno di ogni regione vengono calcolati dx, dy, |dx| e |dy|. Sia l’orientazione che l’istogramma dei gradienti sono estratti alla scala di rilevamento della feature.
5.5 AST
L’ultima classe di estrattori di punti caratteristici cade sotto il nome di Accelerated Segment Test sviluppate da Rosten. DI questo algoritmo esistono al momento tre versioni leggermente differenti.
p 16 1 2
3 4 5 6 7 9 8 10 11 12 13 14
15
Figura 5.5: FAST: i 16 pixel sulla circonferenza di raggio 3 su cui eseguire il test di consecutivit`a.
La prima versione di Features from Accelerated Segment Test FAST [RD05] `e probabilmente quella pi`u intuitiva: in questo caso sono indicati come caratteristici quei punti che hanno una sequenza continua di n pixel, lungo a una circonferenza di raggio dato, tutti pi`u (o meno) luminosi del pixel centrale usato come riferimento per il tono di grigio. Nel caso, per esempio, di FAST-9 vengono analizzati i 16 pixels sulla circonferenza di raggio 3 e si verifica se sussistono 9 pixel contigui tutti sopra o tutti sotto una certa soglia rispetto al pixel centrale. Nelle versioni successive [RD06] ottimizza l’estrazione attraverso l’uso di alberi di decisione addestrati per individuare punti caratteristici che massimizzano la quantit`a locale di informazione. Tali alberi processano sempre i pixel sulla circonferenza.
Questo approccio `e tipico degli ultimi anni quando, grazie all’abbondare di dataset pubblici, `e stato fatto largo utilizzo di classificatori per costruire individuatori di punti caratteristici stabili. Di fatto, date delle primitive che descrivono l’intorno di un punto, l’utilizzo di una tecnica di ottimizzazione permette di individuare quelle che mostrano maggiore stabilit`a nel particolare compito. L’articolo di Rosten fra l’altro produce un ottimo survey sulle tecniche di estrazione di punti caratteristici precedenti.
Nell’ultima variante (FAST-ER) viene infine estesa l’area da analizzare non solo ai punti di una circonferenza, ma a tutti i pixel nell’intorno del punto centrale.
Capitolo 6
Descrittori
Un altro concetto che ha una collocazione trasversale tra le tematiche di visione artificiale `e quello di descrittore (Visual Descriptor ). Il descrittore infatti viene usato in diverse tematiche: viene usato per eseguire il confronto tra punti caratteristici o per generare la mappa di disparit`a nella visione stereoscopia, per fornire una rappresentazione compatta di una porzione dell’immagine per velocizzare la sua individuazione o ricerca, e grazie a questa soluzione compatta che per`o preserva gran parte dell’informazione, viene usata per generare lo spazio delle caratteristiche negli algoritmi di classificazione.
A seconda della trasformazione che subisce l’immagine da cui si vogliono caratterizzare i punti, il descrittore deve soddisfare alcuni principi di invarianza
traslazione ´E quella pi`u facile e viene automaticamente risolta dall’estrattore di punti caratteristici;
scala ´E un’altra trasformazione che normalmente viene risolta dall’estrattore di punti caratteristici;
luminosit`a Le immagini possono subire una variazione di luminosit`a;
rotazione Le immagini possono rappresentare la stessa scena ruotata;
prospettiva I cambi di prospettiva deformano in maniera complessa la porzione di mondo osservata.
Prima che venisse introdotto il concetto di descrittore compatto, il modo universalmente diffuso per confrontare due punti caratteristici era la correlazione tra le aree intorno al punto:
d(p1, p2) =X
δ∈Ω
wδ(I1(p1+ δ) − ¯I1)(I2(p2+ δ) − ¯I2) (6.1)
con Ω una finestra di dimensione fissa centrata nel punto delle due immagini e ¯In il valor medio dell’immagine all’interno della finestra Ω. wδ `e un peso opzionale (ad esempio una gaussiana) per assegnare contributi diversi ai pixel vicini e lontani dal punto. La correlazione `e invariante ai cambiamenti di luminosit`a ma richiede un elevato peso computazionale. In questo caso il descrittore `e esattamente la porzione di immagine intorno al punto individuato [Mor80].
Un approccio simile alla correlazione, non invariante alla luminosit`a ma pi`u performante dal punto di vista computazionale,
`
e la SAD (Sum of Absolute Differences):
d(p1, p2) =X
δ∈Ω
|I1(p1+ δ) − I2(p2+ δ)| (6.2)
Per rendere la SAD invariante alla luminosit`a vengono normalmente eseguiti i confronti non sull’immagine originale, ma sulle immagini derivata orizzontale e derivata verticale. Questo ragionamento sembra molto semplice ma pu`o essere ulteriormente generalizzato nel concetto di eseguire il confronto non sull’immagine originale, ma tra una o pi`u immagini estratte attraverso l’ausilio di differenti kernel, kernel che provvedono a fornire al descrittore alcuni livelli di invarianza.
E altres`ı da notare che il confronto tra i pixel tra le immagini `´ e comunque un algoritmo di tipo O(n2): eseguire questi confronti per punto richiede comunque un elevato peso computazionale e molteplici accessi in memoria. Soluzioni moderne vogliono superare questo limite prevedendo l’estrazione di un descrittore dall’intorno del punto di dimensione inferiore alla quantit`a di pixel rappresentati che per`o massimizzi l’informazione contenuta in essa.
Sia SIFT (sezione 5.3) che SURF (sezione5.4) estraggono i loro descrittori sfruttando le informazioni sulla scala e sulla rotazione estratti dall’immagine (´e possibile estrarre queste informazioni in maniera comunque indipendete e pertanto si possono applicare a qualunque classe di descrittori per renderli invarianti a scala e rotazione). I descrittori ottenuti da SIFT e SURF, sono differenti versioni del medesimo concetto, ovvero dell’istogramma dell’orientazione del gradiente (sezione6.2), esempio di come comprimere in uno spazio di dimensioni ridotte la variabilit`a intorno al punto.
Tutti i descrittori usati attualmente non usano direttamente i punti dell’immagine come descrittore, ma `e facile vedere che basta un sottoinsieme abbastanza ben distribuito dei punti per realizzare comunque una descrizione accurata del punto.
90
In [RD05] viene creato un descrittore con i 16 pixel presenti lungo la circonferenza discreta di raggio 3. Tale descrizione pu`o essere resa ancora pi`u compatta passando alla forma binaria dei Local Binary Pattern descritti in seguito o non vincolata alla circonferenza, come in Census o in BRIEF. Un altro approccio `e campionare in maniera opportuna lo spazio dei kernel [GZS11], estraendo da m coordinate intorno al punto chiave, i valori che assumono convoluzioni dell’immagine originale (Sobel orizzontale e verticale), in modo da creare un descrittore di appena 2m valori.
E da notare che, per motivi prettamente computazionali di riutilizzo di risorse, spesso ad ogni particolare estrattore di´ punti caratteristici viene associato uno specifico estrattore di descrittori.
Da questa introduzione si capisce che descrivere un punto chiave con un insieme di dati inferiore ma allo stesso tempo sufficientemente descrittivo `e un discorso che torna utile anche quando si parla di classificazione. Il concetto di descrittore nasce nel tentativo di estrarre informazioni locali dell’immagine che ne permettano di conservare buona parte dell’informa-zione. In questo modo `e possibile eseguire confronti (relativamente) veloci tra punti tra immagini, o usare tali descrittori come caratteristiche su cui addestrare classificatori.