Come si è visto nelle sezioni precedenti, gli algoritmi di analisi visuale possono utilizzare due diversi tipi di descrittori: i descrittori non binari (SIFT [16], SURF [18]), e i descrittori binari (BRIEF [21], ORB [26], BRISK [11], FREAK [27]). I descrittori binari, di cui verrà fatto uso in questa tesi, sono intrinsecamente differenti dai descrittori a valori reali. Ogni elemento del descrittore è infatti già quantizzato a un bit per definizione. Di conseguenza l’applicazione degli schemi di codifica tradizionali risulta difficoltosa. Tuttavia, anche se una codifica senza per- dite può comunque essere applicata in modo convenzionale, esiste la possibilità di regolare la dimensione dei descrittori binari, variando il numero di confronti delle coppie a seconda della disponibilità di bit. Nel seguito viene descritto un metodo di codifica senza perdite per descrittori binari seguito da uno studio sull’efficacia dei descrittori in funzione della loro dimensione, quando si varia la strategia di scelta dei confronti da effettuare [28].
Ogni elemento di un descrittore binario è quindi un bit, che rappresenta il risultato di un test binario valutato sulla sulla base del contenuto dell’intorno di ciascun keypoint. Se si considerano in particolare due descrittori allo stato dell’arte, BRISK e FREAK, che adottano un metodo simile di costruzione del descrittore, si vede che in entrambi i casi ogni test binario effettua il confronto tra due valori di intensità smussata di una coppia di pixel. La posizione di questi pixel
Figura 2.9: Schemi di campionamento nel caso di (a) BRISK e nel caso di (b) FREAK
nell’intorno del keypoint è determinata sulla base degli schemi di campionamento illustrati nelle figure 2.9(a) e 2.9(b).
Il numero totale di test binari possibili dipende dalla configurazione dello sche- ma di campionamento. Lo schema di campionamento standard di BRISK consiste di N = 60 punti, quindi |A| = 1770. Invece nel caso di FREAK N = 43 pun- ti, quindi |A| = 903. Sono state studiate diverse strategie che possono essere usate per selezionare un sottoinsieme di queste coppie a partire dai vincoli sulla dimensione del descrittore D.
2.4.1
Codifica senza perdite
Indipendentemente dalla specifica strategia di selezione, il descrittore sarà costi- tuito da una stringa di D bit, ognuno rappresentante il risultato di un test binario. Siccome i test binari non sono statisticamente indipendenti, è possibile modellare il descrittore come una sorgente binaria con memoria ed eseguire una codifica sen- za perdite utilizzando un numero di bit R ≤ D. Sia H(πn), n = 1, ..., D, l’entropia
dell’n-esimo elemento del descrittore, che viene calcolata come:
In modo simile, è possibile calcolare l’entropia condizionata H(πn1|πn2). Le stati-
stiche utilizzate per calcolare H(πn) e H(πn1|πn2)possono essere ottenute analiz-
zando un insieme di descrittori di prova estratti da una collezione di immagini. Sia ˜
πn, n = 1, ..., D, una permutazione delle D coppie selezionate, che indica l’ordine
sequenziale utilizzato per codificare il descrittore. La lunghezza media della codi- fica necessaria per codificare senza perdite il descrittore è limitata inferiormente da R = D X n=1 H(˜πn|˜πn−1, ..., ˜π1). (2.15)
Per ottimizzare l’efficienza della codifica, risulta utile trovare la permutazione che minimizza il limite inferiore (2.15). Per fare questo viene adottata una strategia Greedy, che assume che il descrittore possa essere modellato come una sorgente di Markov del prim’ordine, cioè H(˜πn|˜πn−1, ..., ˜π1) = H(˜πn|˜πn−1). Per questo motivo
il descrittore viene poi riordinato selezionando iterativamente gli elementi. In modo specifico, l’elemento n-esimo viene scelto come l’elemento che minimizza l’entropia condizionata rispetto agli elementi selezionati precedentemente
˜
πn = arg min πn
H(πn|˜πn−1) (2.16)
Per quanto riguarda il primo elemento, viene selezionato quello con l’entropia minore, anche se è stato verificato che questa scelta euristica non influisce in modo significativo sulla dimensione della codifica.
2.4.2
Costruzione del descrittore: codifica con perdite
In questa sezione vengono considerate diverse strategie di selezione, a partire da quelle adottate nelle implementazioni di BRISK e FREAK, arrivando poi a descri- vere altre tre nuove strategie presentate in [28], cioè la strategia matching-based, la strategia coding-based e la strategia hybrid.Strategia di BRISK
La strategia di Brisk per la costruzione del descrittore è stata esposta nella Se- zione 2.2.3. Come abbiamo visto, il numero di elementi D del descrittore dipende dal valore della soglia sulla distanza δmax. In [11], δmax è stata fissata a 13.67σm,
in modo tale che venga ottenuto un descrittore con D = |S| = 512 elementi. In [28] viene proposto invece di variare δmax per testare dimensioni differenti del de-
scrittore.
Strategia di FREAK
La fase di descrizione di FREAK introduce un algoritmo euristico per selezionare l’insieme di test binari usati per costruire il descrittore. Durante una fase preli- minare, FREAK analizza tutte le possibili N(N − 1)/2 coppie nell’insieme A, a partire da un elevato numero di chiazze dell’immagine estratte da diverse immagi- ni. Sia D ∈ {0, 1}N (N −1)/2×Q una matrice contenente i risultati dei test binari per
tutte le chiazze Q. FREAK calcola la varianza di ogni coppia e seleziona come prima coppia quella con la varianza maggiore. Ciò è equivalente a selezionare la coppia per la quale le occorrenze di zeri e uni sono distribuite in modo più uniforme, ossia la coppia con l’entropia maggiore. In seguito vengono selezionate iterativamente le altre coppie, scegliendo la coppia che minimizza la correlazio- ne con la coppia selezionata precedentemente. L’algoritmo risulta quindi di tipo Greedy per natura e, ad ogni passo, cerca di selezionare una coppia in modo tale da massimizzare la diversità. L’algoritmo termina quando la disponibilità D è esaurita.
Strategia matching-based
La strategia di selezione utilizzata in FREAK considera la distribuzione statistica dei test binari compiuti su un elevato numero di chiazze. Tuttavia non considera
la bontà delle coppie selezionate quando vengono confrontati descrittori estratti da immagini diverse dello stesso luogo. La strategia di selezione matching-based considera la distribuzione congiunta di test binari effettuati nel caso in cui vengano trovate corrispondenze tra le chiazze e nel caso in cui non vengano trovate. Questa strategia sfrutta la disponibilità del dataset introdotto in [29], che include un vasto insieme di chiazze estratte da diverse immagini dello stesso luogo e acquisite da diversi punti di vista. Il dataset fornisce inoltre informazioni riguardo a quali chiazze corrispondono allo stesso keypoint fisico. Come per FREAK, sia D ∈ {0, 1}N (N −1)/2×Q una matrice contenente i risultati dei test binari per tutte le chiazze Q. Sia M invece l’insieme di indici delle coppie con corrispondenze:
M = {(q1, q2)|dq1 e dq2 sono keypoint corrispondenti} (2.17)
In modo simile è possibile definire un insieme N di indici di coppie senza corrispon- denze. Quindi, per ognuna delle coppie in A, è possibile ricavare l’informazione condivisa IM(π n), m = 1, ..., N (N − 1)/2, IM(πn) = X x∈0,1 X y∈0,1 pMn (x, y) log2 p M n (x, y) pn(x) · pn(y) , (2.18)
dove pn(0) e pn(1) sono le probabilità di osservare rispettivamente zero o uno
come risultato del test binario relativo all’ n-esima coppia in A. La probabilità pMn (x, y) misura le occorrenze congiunte di zeri e uni nelle coppie di descrittori che corrispondono. Ad esempio pM
n (0, 0) rappresenta la probabilità che entrambi
i descrittori in una coppia con corrispondenze contengano uno zero nell’elemento relativo all’n-esimo test binario. Viene definita allo stesso modo l’informazione InN per le coppie senza corrispondenze. In conclusione, per ognuna delle coppie in A viene ricavata la seguente funzione di punteggio:
e le coppie vengono classificate in ordine decrescente di Jn. Questa strategia sce-
glie poi le prime D coppie con il più alto valore di Jn.
Strategia coding-based
La strategia di selezione coding-based procede costruendo un descrittore di D ele- menti con l’obiettivo di minimizzare il numero di bit necessari per codificarlo. La strategia di selezione segue lo stesso approccio descritto nella Sezione 2.4.1 ma, ad ogni iterazione dell’algoritmo Greedy, considera tutte le possibili N(N − 1)/2 coppie piuttosto che un sottoinsieme di D coppie. L’algoritmo termina quando vengono selezionate D coppie.
Strategia hybrid
L’approccio hybrid combina il metodo matching-based con quello coding-based. Delementi del descrittore vengono selezionati per mezzo della seguente strategia:
˜
πn= arg max πn
α(IM(πn) − IN(πn)) − (1 − α)H(πn|˜πn−1) (2.20)
Per quanto riguarda la prima coppia ˜π1 il termine H(πn|˜πn−1) viene sostituito da
H(πn).