Analisi energetica e ottimizzazione dell'algoritmo BRISK

ANALISI ENERGETICA E OTTIMIZZAZIONE

DELL’ALGORITMO BRISK

Autore:

Simone ANGHILERI

Matr.

782978

Relatore:

Ing. Matteo CESANA

Correlatore: Ing. Alessandro REDONDI

Nel campo dell’internet degli oggetti stiamo assistendo ad uno sviluppo sempre maggiore delle Visual Sensor Network (VSN), reti di sensori che si occupano di trasferire ed analizzare immagini. Siccome i nodi che compongono la rete so-no alimentati tramite batteria, uso-no dei requisiti fondamentali è l’efficienza. Il progetto Greeneyes ha lo scopo di lavorare in questa direzione attraverso la crea-zione di un nuovo paradigma che permetta ai nodi della rete di eseguire complessi compiti di analisi visuale. Per fare questo è necessario abbandonare il modello tradizionale comprimi-poi-analizza (CTA), che prevede che l’immagine venga ac-quisita, compressa ed inviata ad un nodo centrale per l’analisi. Il nuovo paradigma analizza-poi-comprimi(ATC) contempla invece che siano i nodi della rete a svolge-re i compiti di analisi visuale, inviando poi al nodo centrale una rappsvolge-resentazione concisa dell’immagine. Affinché questo nuovo modello possa essere implementato, è necessario che gli algoritmi che analizzano le immagini siano molto efficienti. Questa tesi ha lo scopo di ottimizzare l’algoritmo di analisi visuale BRISK, con il fine di migliorarne le prestazioni dal punto di vista dei consumi energetici. Si pone inoltre l’obiettivo di effettuare un confronto sul piano energetico dei due pa-radigmi CTA e ATC, con l’intento di paragonarne i consumi e determinare quindi quale sia la soluzione migliore.

Abstract 1

Elenco delle figure 3

1 Introduzione 4

1.1 Progetto GreenEyes e scenario applicativo . . . 6

1.2 Ottimizzazione di BRISK . . . 8

1.3 Struttura della tesi . . . 9

2 Stato dell’arte 10 2.1 Concetti preliminari . . . 10

2.2 Algoritmi di analisi visuale . . . 12

2.2.1 SIFT . . . 12

2.2.2 SURF . . . 17

2.2.3 BRISK . . . 20

2.3 Metodi di riconoscimento e analisi di accuratezza . . . 25

2.3.1 Metodi di riconoscimento . . . 25

2.3.2 Misure di accuratezza . . . 28

2.4 Codifica di descrittori binari . . . 29

2.4.1 Codifica senza perdite . . . 30

2.4.2 Costruzione del descrittore: codifica con perdite . . . 31

3.2 Considerazioni preliminari e struttura di BRISK . . . 42 3.3 Ottimizzazioni . . . 46 3.3.1 Selezione delle coppie di punti . . . 47 3.3.2 Calcolo dell’intensità smussata solo per i punti utilizzati . 48 3.3.3 Conversione delle funzioni di ridimensionamento

dell’imma-gine . . . 49 3.3.4 Rimozione di operazioni di interpolazione . . . 51 3.3.5 Esecuzione in parallelo del test binario . . . 52 3.3.6 Rimozione dell’invarianza alla rotazione quando non

neces-saria . . . 53

4 Implementazione e risultati 55

4.1 I dataset . . . 55 4.2 Selezione delle coppie di punti . . . 56 4.3 Calcolo dell’intensità smussata solo per i punti utilizzati . . . 58 4.4 Conversione delle funzioni di ridimensionamento dell’immagine . . 61 4.5 Rimozione di operazioni di interpolazione . . . 64 4.6 Esecuzione in parallelo del test binario . . . 68

4.6.1 Rimozione dell’invarianza alla rotazione quando non neces-saria . . . 69

5 Comprimi-poi-analizza vs Analizza-poi-comprimi 71

5.1 Confronto rate-energia . . . 71 5.2 Risultati . . . 77 5.3 Codifica Entropica . . . 79

1.1 Architettura del sistema GreenEyes . . . 7

2.1 Immagini campione del dataset ZuBuD . . . 11

2.2 Costruzione della piramide scale-space . . . 14

2.3 Individuazione massimi e minimi SIFT . . . 15

2.4 Creazione del descrittore SIFT . . . 16

2.5 Approssimazioni di SURF . . . 18

2.6 Detection dei punti di interesse nello scale-space . . . 22

2.7 Schema di campionamento di BRISK . . . 23

2.8 Esempio di corrispondenze trovate tra due immagini utilizzando BRISK . . . 28

2.9 Schemi di campionamento di BRISK e di FREAK . . . 30

2.10 Curva rate-accuratezza . . . 37

2.11 Curva di allocazione interna . . . 38

3.1 Dispositivo Beaglebone . . . 41

3.2 Consumi di potenza Beaglebone . . . 42

3.3 Tempi di esecuzione delle singole operazioni di BRISK alla risolu-zione VGA . . . 45

3.4 Tempi di esecuzione delle singole operazioni di BRISK alla risolu-zione SVGA . . . 46

3.5 Tempi di esecuzione delle singole operazioni di BRISK alla risolu-zione XGA . . . 46

4.1 Immagini campione del dataset ZuBuD . . . 56

4.2 Immagini campione del dataset Oxford . . . 56

4.3 Tempi di esecuzione con l’ottimizzazione relativa all’intensità smus-sata . . . 59

4.4 Speedup ottenuto con l’ottimizzazione relativa all’intensità smussata 60 4.5 Speedup relativo all’ottimizzazione di ridimensionamento delle im-magini . . . 63

4.6 Confronto accuratezze versione di BRISK originale e senza fase di interpolazione . . . 65

4.7 Speedup rimozione interpolazione . . . 66

4.8 Speedup totale fase di detection . . . 67

4.9 Speedup totale description senza invarianza alla rotazione . . . 70

5.1 Funzionamento dei due paradigmi comprimi-poi-analizza (a) e analizza-poi-comprimi (b). . . 72

5.2 Tempi di esecuzione necessari per la codifica JPEG al variare del rate 73 5.3 Tempi di esecuzione necessari per la fase di detection al variare del numero di keypoint. . . 74

5.4 Tempi di esecuzione necessari per la fase di description al variare del numero di keypoint . . . 75

5.5 Energia necessaria per la descrizione di una feature al variare della dimensione dei descrittori . . . 76

5.6 Confronto energetico tra il paradigma CTA e ATC (ZuBuD) . . . 77

5.7 Confronto energetico tra il paradigma CTA e ATC (Oxford) . . . 78

5.8 Guadagno energetico in termini percentuali della versione ottimiz-zata di BRISK rispetto all’originale(ZuBuD) . . . 79

Introduzione

La ricerca nell’ambito delle Wireless sensor Networks (WSNs), cioè reti senza fili di sensori, sta prendendo sempre più piede, dando luogo ad una crescita dell’inte-resse anche da parte del settore industriale, nell’ottica di un utilizzo commerciale dei servizi che possono essere forniti da questa tecnologia [1][2]. In particola-re, l’integrazione di tecnologie senza fili a basso consumo energetico e dispositivi hardware a basso costo per l’acquisizione di immagini [3] ha portato allo sviluppo delle cosiddette wireless multimedia sensor networks (WMSNs), conosciute anche come visual sensor networks (VSNs)[4][5]. Una VSN può essere pensata come una rete di dispositivi senza fili in grado di rilevare del contenuto multimediale, come immagini, video, audio, etc [6]. I nodi provvisti di sensori forniscono al nodo centrale le informazioni che hanno raccolto e sono in grado di processare i dati ottenuti in modo distribuito e collaborativo [7].

Le fotocamere digitali sono realizzate sull’esempio dell’apparato visivo umano. Le immagini vengono acquisite in formato digitale campionando e quantizzan-do il campo luminoso su un reticolo discreto di pixel. In seguito le immagini (o sequenze di immagini) vengono compresse per essere poi memorizzate oppure trasmesse. L’analisi dei dati raccolti può essere compiuta in linea di principio direttamente dai nodi della rete, tuttavia sistemi di questo tipo sono spesso molto costosi e soprattutto caratterizzati da un significativo consumo energetico. At-tualmente l’approccio più utilizzato nel campo dell’analisi visuale è quello che

prevede la creazione di una versione compressa, e quindi qualitativamente peggio-re, dell’immagine originale. Questa metodologia contrasta però parzialmente con il paradigma adottato dal sistema visivo umano. In primo luogo i dati relativi alle immagini vengono memorizzati e trasmessi conservando una rappresentazione a livello di pixel, ma c’è la possibilità che sia solo la parte semantica ad avere impor-tanza. Ciò comporta un’inefficienza in termini di risorse di rete e computazionali usate, specialmente quando l’analisi si basa su dati raccolti a partire dall’acqui-sizione di più di una fotocamera. In secondo luogo, l’efficienza energetica viene spesso trascurata e assume un ruolo di importanza secondaria, siccome la gran parte del processo computazionale associato all’analisi visuale viene svolto su un nodo centralizzato che non presenta problemi energetici.

Un tale paradigma, del tipo comprimi-poi-analizza, è stato utilizzato con suc-cesso in molti scenari applicativi, come ad esempio la video sorveglianza, nei quali non vi sono vincoli stringenti dovuti al consumo energetico. Negli ultimi anni le VSN hanno ricoperto un ruolo sempre più importante nell’evoluzione del para-digma dell’Internet degli oggetti [8][9]. Le VSN sono in grado infatti di prendersi carico di funzioni complesse di analisi, quali localizzazione, monitoraggio, ricono-scimento di oggetti etc., e forniscono così la base per nuove applicazioni in ambiti che spaziano della sorveglianza all’assistenza sanitaria.

Questa tesi mira ad andare oltre il modello tradizionale comprimi-poi-analizza, concentrandosi invece su un nuovo paradigma del tipo analizza-poi-comprimi, nel-l’ottica di un sistema maggiormente focalizzato sugli aspetti legati ai consumi energetici ed in linea con gli obiettivi del progetto europeo GreenEyes. In partico-lare, facendo uso di un dispositivo BeagleBone [10], vengono analizzati i consumi energetici sia nel caso di un sistema basato modello tradizionale, sia nel caso di un sistema basato sul nuovo paradigma, andando poi a confrontare i risultati ottenu-ti. Si prende inoltre in considerazione l’algoritmo di analisi visuale BRISK (Binary

Robust Invariant Scalable Keypoints) [11], rivelatosi tra i più efficienti, con l’o-biettivo di produrne una versione ulteriormente ottimizzata dal punto di vista dei consumi energetici. Viene analizzata nel dettaglio la struttura dell’algoritmo, al fine di implementare delle modifiche che lo rendano più efficiente limitando il più possibile i consumi energetici.

1.1

Progetto GreenEyes e scenario applicativo

Il progetto GreenEyes è un progetto che mira a sviluppare un insieme di nuove metodologie, algoritmi e protocolli, con il fine di fornire alle reti senza fili di sen-sori capacità visive comparabili a quelle ottenibili con i sistemi di acquisizione di immagine tradizionali. Il principio chiave è che la maggior parte delle funzioni di analisi visuale possono essere portate a termine sulla base di una rappresen-tazione compressa dell’immagine, in grado di mantenere le caratteristiche globali e locali ma che allo stesso tempo non fa uso della sottostante rappresentazione a livello di pixel. Inoltre, operando secondo vincoli energetici molto stringenti è imperativo ottimizzare la fase di computazione, di codifica e di trasmissione delle feature dell’immagine. Per quanto riguarda l’aspetto delle computazione e della codifica, Greeneyes affronta il problema capovolgendo il paradigma tradizionale comprimi-poi-analizza. Questo nuovo approccio prevede che i nodi provvisti di sensori acquisiscano i dati sulle immagini, li processino e li inviino alla destina-zione finale, al fine di rendere possibile l’esecudestina-zione di funzioni di analisi visuale di alto livello, per mezzo di algoritmi di analisi che possano essere eseguiti sia in modo centralizzato che distribuito, ricalcando così il sistema visivo umano.

La Figura 1.1 mette in mostra una rappresentazione illustrativa dell’architet-tura ad alto livello del sistema proposto, mettendo in rilievo i moduli funzionali e le loro dipendenze. I nodi sono equipaggiati con microprocessori a basso consumo energetico e chip radio, in modo tale che possano comunicare tra loro e con un

Figura 1.1: Architettura del sistema GreenEyes. I nodi blu sono i nodi equipaggiati con una fotocamera ed hanno quindi la capacità di acquisire immagini, oltre a quella di processare i dati raccolti. I nodi gialli rappresentano i nodi generici, che pur non potendo acquisire immagini contribuiscono al funzionamento del sistema in quanto favoriscono il calcolo distribuito e l’instradamento dei pacchetti informativi.

nodo centrale, quando disponibile. I nodi sono caratterizzati da una batteria con capacità limitata, da capacità eterogenee in termini di potenza computazionale, da una banda di comunicazione e dalla disponibilità di dispositivi sensoriali. In particolare, un sottoinsieme dei nodi è equipaggiato con fotocamere incorpora-te che possono essere utilizzaincorpora-te per acquisire i dati sulle immagini, necessari per eseguire vari compiti di analisi visuale. Lo scenario che viene concepito è quindi quello in cui i nodi muniti di sensori sono in grado di elaborare i dati localmente per quanto possibile, piuttosto che trasmettere una rappresentazione compressa nel dominio dei pixel delle immagini acquisite. Si può inoltre osservare che an-che nodi non dotati di un sensore visivo rappresentano una importante risorsa, in quanto possono essere sfruttati sia per l’instradamento delle informazioni sulla rete, sia per il calcolo distribuito.

Le metodologie sviluppate con il progetto GreenEyes possono avere un signifi-cativo impatto in tutti quegli scenari applicativi nei quali l’analisi visuale non è

al momento fattibile a causa di vincoli energetici molto stringenti. Un esempio può essere il caso del monitoraggio ambientale in zone pericolose o inaccessibi-li. Oppure il caso di sistemi di video sorveglianza in luoghi non raggiunti dalle linee elettriche. Anche in ambito militare è possibile trovare delle applicazioni, ad esempio per il monitoraggio delle forze alleate sul campo di battaglia. Come esempio illustrativo, i risultati di questo progetto possono essere particolarmente rilevanti nel contesto delle cosiddette città intelligenti: anche se l’alimentazione elettrica è generalmente disponibile in ambiente urbano, la disponibilità di nodi con sensori visuali alimentati da una batteria permette di ottenere una copertu-ra più completa del territorio, rendendo copertu-raggiungibili aree più ampie e limitando i costi delle infrastrutture necessarie. Dispositivi di questo tipo possono essere adottati per il monitoraggio del traffico, per parcheggi intelligenti, etc.

1.2

Ottimizzazione di BRISK

Questa tesi vuole contribuire al raggiungimento degli obiettivi del progetto Gree-neyes tramite alcuni miglioramenti apportati all’algoritmo di estrazione di feature BRISK, che è stato scelto in quanto risulta attualmente uno dei più efficienti. Riuscire ad ottimizzarlo ulteriormente significherebbe favorire un’esecuzione me-no onerosa dei compiti di analisi visuale e di conseguenza ottenere un risparmio energetico. Per il conseguimento di questo obiettivo questa tesi si occupa di mo-dificare il codice di BRISK, implementando alcune ottimizzazioni che permettono di rendere più efficiente l’algoritmo. Viene ad esempio sfruttato il calcolo parallelo per la computazione di alcune fasi e viene resa possibile l’esecuzione secondo il modello rate-accuratezza, in grado di aumentare al massimo le prestazioni. Do-po aver implementato queste ottimizzazioni si procede ad una stima dei consumi energetici derivanti dall’utilizzo del paradigma analizza-poi-comprimi, basato sia sulla versione originale di BRISK che su quella modificata, analizzando il gua-dagno apportato da quest’ultima. Viene infine effettuato un confronto sul piano

energetico con il paradigma comprimi-poi-analizza, allo scopo di verificare quale sia la soluzione migliore.

1.3

Struttura della tesi

Questo lavoro di tesi è organizzato come segue.

Nel Capitolo 2 vengono inizialmente introdotti i concetti preliminari riguardan-ti gli algoritmi di analisi visuale. In seguito viene offerta una panoramica sui principali algoritmi di analisi visuale allo stato dell’arte, concentrandosi poi sul-le modalità di riconoscimento degli oggetti e sui metodi utilizzati per la misura dell’accuratezza. Viene poi illustrato il concetto di descrittore binario e delle mo-dalità di codifica, concetto che viene poi utilizzato in tutto il resto della tesi. Infine viene esposto un modello di rate-accuratezza, che sta alla base di parte del lavoro compiuto.

Nel Capitolo 3 viene analizzata la struttura dell’algoritmo BRISK, al fine di ri-cercare quali sono le parti più dispendiose di esso e ri-cercare quindi di ottimizzarle. Vengono quindi esposte nei particolari quali sono le ottimizzazioni pensate per migliorare l’efficienza dell’algoritmo.

Il Capitolo 4 tratta l’implementazione delle ottimizzazioni illustrate e i risultati che sono stati ottenuti. Riprendendo il Capitolo precedente, vengono illustrate le modalità di implementazione delle singole ottimizzazioni e quali sono i contributi apportati da esse in termini di efficienza.

Nel Capitolo 5 viene effettuato il confronto in termini di consumi energetici, sulla base del caso preso in esame, tra il paradigma comprimi-poi-analizza ed il nuovo paradigma analizza-poi-comprimi. Viene inoltre analizzato il comportamento del-la versione ottimizzata dell’algoritmo BRISK, rapportato a quello deldel-la versione originale.

Il Capitolo 6 infine conclude la tesi e si occupa di delineare quali sono gli sviluppi futuri.

Stato dell’arte

In questo capitolo viene fornito una descrizione dettagliata riguardo ai concetti relativi all’analisi visuale. Vengono inizialmente introdotti concetti utili a com-prendere il funzionamento dei principali algoritmi di analisi. Si passa quindi ad analizzare tre di questi algoritmi allo stato dell’arte. Vengono infine esposti i mec-canismi tramite i quali tali algoritmi sono in grado di effettuare il riconoscimento di oggetti.

2.1

Concetti preliminari

Parlando di analisi visuale bisogna anzitutto introdurre il concetto di feature, in quanto gli algoritmi che verranno presi in considerazione sono algoritmi di estra-zione di feature. Le feature visuali vengono solitamente utilizzate in diversi ambiti applicativi, a partire dall’acquisizione di immagini e video fino ad arrivare al mo-nitoraggio o al riconoscimento di oggetti. Possono essere suddivise in due classi: feature globali e feature locali. Le feature globali rappresentano il contenuto di un’immagine nel suo insieme, senza fare diretto riferimento alla disposizione spa-ziale del contenuto visivo. Pur rappresentando una soluzione molto efficace nei casi in cui si lavora su larga scala, le feature globali non sono adatte a scenari in cui è richiesto di descrivere in modo preciso il contenuto locale di un’immagine. Le feature locali cercano di superare questi limiti grazie ad una rappresentazione

(a) Immagine originale (b) Feature dell’immagine

Figura 2.1: Esempio di feature di un’immagine. I cerchi blu indicano feature chiare mentre i cerchi blu feature scure.

dell’immagine che si comporti in modo robusto nei confronti di trasformazioni geometriche e cambi di illuminazione [12]. Si può dire che una feature locale rap-presenta una porzione degna di nota di un’immagine, che potrebbe coincidere con una particolare struttura nella rappresentazione nel dominio dei pixel. Esistono diversi algoritmi, detti detector, che si occupano di individuare feature locali, in particolare analizzando parti dell’immagine che contengono angoli, bordi o strut-ture simili a chiazze. La Figura 2.1 mostra un esempio di feastrut-ture identificate in un’immagine.

Il processo di estrazione delle feature viene effettuato in due passi. Inizial-mente il detector analizza l’immagine e individua un insieme di punti salienti, detti keypoint, che rappresentano quelle parti dell’immagine che contengono più informazione. Generalmente il numero di keypoint individuati è dipendente dal contenuto dell’immagine. La rappresentazione di una scena con molti dettagli implica un maggior numero di keypoint individuati, viceversa per immagini ca-ratterizzate da pochi bordi, spigoli o chiazze. L’individuazione dei keypoint viene inoltre fatta anche su scale differenti, tramite una rappresentazione nota come scale-space, con la conseguenza che le dimensioni della feature locale corrispon-dente non sono standard. Keypoint individuati su scala ridotta corrispondono a

piccoli dettagli dell’immagine, mentre keypoint individuati su larga scala faranno riferimento a strutture più grandi.

Dopo la fase di detection è il momento della fase di description, che ha lo scopo di produrre una rappresentazione in grado di descrivere le feature locali indivi-duate. Per ognuna di esse, viene creato un descrittore (o vettore di descrizione), ricavato tramite una serie di confronti relativi ai punti nell’intorno del keypoint.

2.2

Algoritmi di analisi visuale

2.2.1

SIFT

L’algoritmo Scale Invariant Feature Transform (SIFT) fu inizialmente proposto da David Lowe nel 1999 [13] ed è oggi considerato l’algoritmo che sta alla ba-se dell’estrazione e descrizione di feature visuali. Esso consiste di due parti: un detector di feature invariante alla scala e un algoritmo di descrizione ben consoli-dato in grado di produrre descrittori che possono essere utilizzati in modo efficace per eseguire in modo affidabile funzioni di riconoscimento. Molti dei più recenti algoritmi di estrazione di feature (ed in particolare l’algoritmo BRISK utilizzato in questa tesi) tendono a ricalcare la struttura di SIFT. Per questa ragione può essere importante analizzare nel dettaglio il funzionamento di questo algoritmo.

Detector

Il detector di SIFT agisce secondo lo schema seguente: detection di estremi nello scale-space, localizzazione dei keypoint e assegnazione dell’orientamento. Nella prima fase, utilizzando l’approccio dei filtri a cascata, vengono individuati i key-point sul piano dell’immagine e in tutte le scale dell’immagine. In seguito, per ognuna delle posizioni candidate viene creato un modello dettagliato allo scopo di determinare in modo accurato la collocazione e la scala di ognuno dei keypoint. Viene infine assegnato un orientamento ad ogni keypoint, sulla base della

dire-zione del gradiente locale dell’immagine. In questo modo l’algoritmo garantisce l’invarianza rispetto alla posizione, alla scala e all’orientamento.

• Detection dei keypoint:

l’individuazione di punti dell’immagine invarianti ai cambiamenti di sca-la può essere effettuata tramite sca-la ricerca di estremi nello scale-space. La rappresentazione scale-space viene generalmente definita come una funzione L(x,y,σ) prodotta dalla convoluzione di una fuzione Gaussiana G(x, y, σ) con l’immagine in imput I(x, y):

L(x, y, σ) = G(x, y, σ) ∗ I(x, y),

dove * è l’operazione di convoluzione. Per individuare efficientemente dei keypoint stabili, l’algoritmo propone una convoluzione dell’immagine in in-put con una funzione di differenza Gaussiana (DoG) D(x, y, σ), ottenuta come risultato della differenza tra due scale vicine separate da un fattore costante k:

D(x,y,σ) = (G(x,y,kσ)-G(x,y,σ)) ∗ I(x,y) (2.1) E’ stato mostrato che questa funzione scale-space risulta una approssima-zione molto vicina al Laplaciano di Gaussiana [14], necessario per ottenere una vera invarianza alla scala, e produce un insieme di feature più stabili se confrontate con una gamma di altre possibili funzioni [15]. L’approccio per la costruzione di D(x,y,σ) è mostrato in Figura 2.2. L’immagine iniziale viene sottoposta a convoluzioni continue utilizzando filtri Gaussiani, fino a produrre immagini separate da un fattore di scala costante (colonna di sini-stra). Successivamente viene effettuata la sottrazione di immagini adiacenti offuscate per produrre le immagini DoG mostrate sulla destra. Quando è stato processato un numero predefinito di scale, l’immagine in input viene

Figura 2.2: Costruzione della piramide scale-space.Immagine tratta da [16]

ridimensionata di un fattore 1/2, e il processo viene ripetuto per tutte le ottave. Una volta costruito lo scale-space, ognuno dei punti campione viene confrontato con i suoi otto vicini nella scala corrente e con in nove vicini nella scala superiore e nella scala inferiore, come mostrato in Figura 2.3. Il punto campione viene selezionato come estremo solo se è più grande o più piccolo di tutti i suoi vicini. Una volta che viene individuato un keypoint, l’algoritmo procede alla creazione di un modello in grado di rappresentare le caratteristiche del punto, specificando posizione, scala e rapporto di cur-vatura. Questo processo, oltre a migliorare il riconoscimento e la stabilità, permette anche di scartare i keypoint con un basso contrasto. Una fase ul-teriore si occupa di non considerare i keypoint lungo i bordi, contribuendo al miglioramento delle prestazioni.

Figura 2.3: I massimi e minimi delle immagini DoG vengono individuati facendo il confronto tra un pixel (contrassegnato da una X) e i suoi 26 vicini(contrassegnati da cerchi) nelle regioni 3x3, nella scala corrente e in quelle adiacenti. Immagine tratta da [16]

• Assegnazione dell’orientamento:

il processo di detection continua poi con l’ottenimento di un orientamento consistente al keypoint, in modo tale che il descrittore possa contenere questa informazione e ottenendo così l’invarianza alla rotazione. L’orientamento viene ricavato grazie alla formazione di un istogramma composto di 36 parti (che coprono l’intero angolo di 360 gradi), il quale viene riempito con i campioni nell’intorno del keypoint. Per ogni campione viene poi calcolato l’orientamento θ utilizzando differenze tra pixel:

θ(x, y) = tan−1((L(x, y + 1) − L(x, y − 1))/(L(x + 1, y) − L(x − 1, y))). Prima di aggiungere un campione all’istogramma, gli viene assegnato un peso sulla base dell’intensità del suo gradiente. Per selezionare l’orien-tamento finale, viene individuato il picco più alto dell’istogramma e, per

una migliore accuratezza, tramite l’adattamento a una parabola dei 3 valori dell’istogramma più vicini al picco, viene interpolato l’orientamento finale.

Descrittore

La fase di detection fornisce quindi i keypoint, con informazioni riguardo alla posizione, alla scala e all’orientamento. A questo punto deve essere ricavato un descrittore per la feature locale dell’immagine, in grado di contenere tutti questi dati e che permetta possibilmente di ottenere l’invarianza rispetto ad altre trasfor-mazioni, quali i cambiamenti di illuminazione. La Figura 2.4 mostra il processo di costruzione del descrittore di SIFT. In primo luogo vengono campionate le intensi-tà dei gradienti dell’immagine e gli orientamenti nell’intorno di ciascun keypoint: tutte le coordinate vengono ruotate utilizzando l’orientamento del keypoint per ottenere l’invarianza alla rotazione. Per l’assegnamento dei pesi viene utilizzata una funzione Gaussiana (illustrata con una finestra circolare nel lato sinistro della Figura 2.4), che misura l’intensità di ogni punto campionato, al fine di evitare cambiamenti improvvisi nel descrittore causati da piccole variazioni nella posizio-ne della fiposizio-nestra. In seguito vieposizio-ne costruito il descrittore del keypoint, tramite

la creazione di istogrammi di orientamento nelle regioni di campionamento 4x4 (lato destro della Figura 2.4). Il descrittore viene ricavato a partire da un vettore contenente i valori di tutte le voci dell’istogramma relativo all’orientamento. La Figura 2.4 mostra un array 2x2 degli istogrammi relativi all’orientamento, tuttavia il descrittore standard di SIFT viene costruito a partire da un array di istogrammi 4x4, ognuno composto da 8 parti. Il descrittore SIFT risulta quindi formato da un vettore di feature di 4x4x8=128 elementi per ogni keypoint. Per ridurre gli effetti dovuti ai cambi di illuminazione il descrittore viene normalizzato alla lunghezza unitaria.

2.2.2

SURF

L’algoritmo Speeded Up Robust Features (SURF)[17] si avvicina alle prestazioni di SIFT, ma allo stesso tempo risulta più veloce nella computazione. Per questo motivo si rivela interessante analizzare il suo funzionamento, nell’ottica di un ese-cuzione efficiente e mirata al risparmio energetico. Questo miglioramento viene ottenuto appoggiandosi a immagini integrali per la convoluzione compiuta dal de-tector e semplificando gli schemi esistenti di costruzione del descrittore.

Detector

Il detector di SURF si basa su un’approssimazione della matrice Hessiana [18], in quanto essa permette di ottenere delle buone prestazioni in termini di computa-zione e accuratezza. Dato un punto (x, y) in un’immagine I, la matrice Hessiana H(x, y, σ) alla scala σ è definita come:

H(x, y, σ) = "

∂2

∂x2G(σ) · I(x, y) _∂x∂ _∂y∂ G(σ) · I(x, y) ∂ ∂x ∂ ∂yG(σ) · I(x, y) ∂2 ∂y2G(σ) · I(x, y) # (2.2)

dove I(x, y) rappresenta l’intensità del pixel alle coordinate (x, y) e G(σ) è il nucleo Gaussiano. Il calcolo della matrice Hessiana implica delle convoluzioni con

deriva-Figura 2.5: Da destra a sinistra: derivate parziali Gaussiane del second’ordine e approssimazioni di SURF tramite filtri.Immagine tratta da [18]

te Gaussiane del second’ordine, e questo può risultare molto costoso. Per ridurre la complessità, SURF approssima questi calcoli utilizzando dei filtri che posso-no essere processati in modo efficiente utilizzando delle immagini integrali, come mostrato in 2.5. Denotando le convoluzioni con Dxx, Dyy e Dxy, il determinante

Hessiano può essere approssimato come:

det(Happrox) = DxxDyy− (0.9Dxy)2 (2.3)

• Detection dei keypoint:

in modo simile a SIFT, il detector di SURF è invariante alla scala e si basa sulla costruzione di una piramide nello scale-space. A differenza di SIFT pe-rò, a causa dell’utilizzo di filtri e immagini integrali, lo scale-space di SURF viene creato applicando filtri di dimensioni diverse direttamente sull’imma-gine originale, mantenendo il costo. Di conseguenza lo scale-space viene analizzato aumentando di volta in volta le dimensioni del filtro piuttosto che ridurre in modo iterativo le dimensioni dell’immagine. Infine, come in SIFT, i keypoint sono localizzati con il metodo della soppressione del non-massimo in un volume 3x3x3 di pixel nello scale-space. Quindi, i massimi del determinante della matrice Hessiana approssimata vengono interpolati utilizzando lo stesso approccio di SIFT.

• Assegnazione dell’orientamento:

per ottenere l’invarianza alla rotazione, anche SURF identifica un orienta-mento riproducibile per ogni keypoint. Invece di operare su istogrammi dei gradienti locali, SURF calcola le risposte alla wavelet Haar in direzione x e y, in un intorno circolare del keypoint, come fase precedente all’assegnamento Gaussiano dei pesi. L’orientamento dominante viene stimato calcolando la somma di tutte le risposte all’interno di una finestra di orientamento scor-revole che copre un angolo di π/3, e quindi scegliendo l’orientamento che massimizza la somma.

Descrittore

Il primo passo per l’estrazione del descrittore consiste nel centrare attorno a cia-scun keypoint una regione quadrata, orientata lungo l’orientamento dominante e la cui dimensione è proporzionale alla scala del keypoint. La regione viene quin-di sudquin-divisa in 4x4 sottoregioni più piccole. All’interno quin-di ogni regione vengono selezionati 25 punti di campionamento regolarmente distanziati. Per ognuno di questi punti vengono calcolate le risposte orizzontali e verticali alla wavelet Haar, indicate rispettivamente con dx e dy. In seguito le risposte vengono sommate in

ogni sottoregione, formando così un primo insieme di valori del vettore delle featu-re. Vengono inoltre calcolate le somme dei valori assoluti delle risposte |dx| e |dy|.

Quindi, ogni sottoregione è caratterizzata da un vettore a quattro dimensioni, definito come: hX dx, X dy, X |dx| , X |dy| i . (2.4)

Il descrittore finale viene ottenuto concatenando i vettori delle feature di tut-te le sottoregioni, producendo un vettore di description composto da 64 ele-menti. Analogamente a SIFT, l’invarianza al contrasto viene ottenuta tramite normalizzazione.

2.2.3

BRISK

Negli ultimi anni si è assistito alla comparsa di nuovi tipi di algoritmi di detection e description, pensati in modo specifico per essere eseguiti su architetture che hanno a disposizione una potenza limitata. In particolare questi nuovo algoritmi mirano ad essere molto meno esigenti per quanto riguarda la parte di computazione, ma mantenendo allo stesso tempo performance di alta qualità. Nel 2011, in linea con queste caratteristiche, viene proposto l’algoritmo Binary Robust Invariant Scala-ble Keypoints (BRISK) [11], algoritmo che viene preso in considerazione per gran parte di questa tesi.

Detector

I punti di interesse dell’immagine sono identificati sia attraverso il piano dell’im-magine che attraverso lo scale-space, utilizzando un criterio di rilevanza. Per dare una spinta all’efficienza della computazione, i keypoint vengono individuati sia negli strati della piramide corrispondenti alle ottave, sia negli strati intermedi. La posizione e la scala di ognuno dei keypoint vengono ottenute nel dominio continuo attraverso l’adattamento ad una funzione quadratica. L’elemento fondamentale di BRISK, che garantisce un aumento della velocità, risiede nell’applicazione di un nuovo detector:

• Detection dei keypoint:

Con un occhio di riguardo per l’efficienza della computazione, il detector di BRISK si ispira al popolare detector di spigoli Fast Accelerated Segment Test (FAST) [19], che risulta uno strumento molto efficiente per l’estrazione di feature. Esiste inoltre una versione migliorata di FAST, chiamata AGA-ST [20], la quale prevede che un punto candidato p (di intensità Ip) viene

classificato come spigolo se, nel Cerchio di Bresenham di raggio 3 attorno a p, n pixel contigui risultano tutti più luminosi di Ip+ t o tutti più scuri di

assegna-to un punteggio s, definiassegna-to come la soglia più grande per la quale p viene classificato come spigolo. Lo svolgimento come prima cosa di un test lungo le quattro direzioni principali del cerchio permette di escludere fin da subito quei punti che non sono spigoli, accelerando così il processo di detection. Inoltre, tramite un approccio di apprendimento automatico, AGAST è in grado di classificare un punto candidato sulla base di pochi test, velocizzan-do così la fase di detection. Questa soluzione richiede in media meno di 2.3 test per pixel per determinare se esso corrisponda o no ad una feature. Con l’obiettivo di ottenere l’invarianza alla scala, BRISK si spinge oltre, andando a ricercare i keypoint non solo nel piano dell’immagine ma anche nello scale-space, utilizzando il punteggio s di FAST come misura di rile-vanza. BRISK si basa su una struttura piramidale dello scale-space. Gli strati della piramide si costituiscono di n ottave ci e di n intra-ottave di,

per i = {0, 1, ..., n − 1} e tipicamente n = 4. Le ottave vengono formate tramite un progressivo ridimensionamento di un fattore 1/2 dell’immagine originale (che corrisponde a c0). Ogni intra-ottava di si trova tra gli strati ci

e ci+1, come mostrato in Figura 2.6. La prima intra-ottava d0 è ottenuta con

un sottocampionamento dell’immagine originale c0 di un fattore 1.5,

men-tre il resto degli strati intra-ottave vengono derivati da sottocampionamenti successivi di un fattore 2. Quindi, se t denota la scala, allora t(ci) = 2i e

t(di) = 2i · 1.5. La Figura 2.6 mostra come vengono individuati i punti di

interesse nello scale-space: un keypoint (cioè il punto con massima rilevan-za) viene identificato all’ottava ci sia analizzando i valori dei punteggi di

rilevanza dei suoi 8 vicini sia valutando i valori dei punteggi relativi ai vicini negli strati immediatamente sopra e immediatamente sotto. In tutti e tre gli strati di interesse, il punto con rilevanza massima locale viene precisa-to a livello di pixel ed in seguiprecisa-to, tramite l’adattamenprecisa-to ad una parabola 1D lungo l’asse delle scale, viene interpolata la scala esatta del keypoint.

La posizione del keypoint viene poi ulteriormente re-interpolata alla scala determinata tra tutti i punteggi massimi della zona presa in esame.

Figura 2.6: Detection dei punti di interesse nello scale-space. Figura tratta da [11]

• Assegnazione dell’orientamento:

Per quanto riguarda l’assegnazione dell’orientamento, BRISK si basa su uno schema utilizzato per campionare i punti vicini nell’intorno del keypoint. Questo schema (Figura 2.7) definisce N posizioni equamente spaziate su cerchi concentrici attorno al keypoint. Per evitare l’aliasing, durante il cam-pionamento di un punto pi nello schema viene applicato lo smussamento

Gaussiano con una deviazione standard σi, proporzionale alla distanza tra i

punti sul rispettivo cerchio. Considerando un keypoint k, se (pi, pj) denota

Figura 2.7: Schema di campionamento di BRISK con N = 60 punti: i piccoli cerchi blu rappresentano le posizioni in cui viene fatto il campionamento; i cerchi più grossi tratteggiati vengono determinati ad un raggio σ corrispondente alla deviazione standard del nucleo Gaussiano usato per smussare i valori di intensità corrispondenti ai punti campione. Lo schema esposto si applica ad una scala di t = 1. Figura tratta da [11]

rispettivi valori di intensità smussata dei punti, il gradiente locale g(pi, pj)

può essere stimato come:

g(pi, pj) = (pj − pi) ·

I(pj, σj) − I(pi, σi)

kpj− pik2

. (2.5)

Considerando poi l’insieme A di tutte le coppie di punti campione:

A =(pi, pj) ∈ R2× R2|i < N ∧ j < i ∧ i, j ∈ N

(2.6) vengono definiti il sottoinsieme S delle coppie di breve distanza e il sottoin-sieme L delle coppie di lunga distanza:

L = {(pi, pj) ∈ A| kpj− pik > δmin} ⊆ A (2.8)

Le distanze di soglia sono definite come δmax = 9.75t e δmin = 13.67t (dove

t è la scala di k). Iterando attraverso le coppie di punti in L viene infine stimato l’orientamento del keypoint k come:

g =gx gy  = 1 L · X (pi,pj)∈L g(pi, pj). (2.9)

Per questo calcolo vengono utilizzate le coppie di L , sulla base dell’assun-zione che i gradienti locali si annullano a vicenda e non sono quindi necessari per la determinazione del gradiente globale.

Descrittore

L’ottenimento dei descrittori di BRISK risulta un’operazione molto veloce in quan-to si basa sul concetquan-to di descritquan-tore binario, che fu proposquan-to per la prima volta in [21]. Un descrittore binario viene assemblato come una stringa di bit, ottenuta a partire da una serie di confronti delle intensità dei pixel, cosa che richiede una potenza computazionale molto bassa. Per quanto riguarda la formazione di un de-scrittore che tenga conto dell’invarianza alla rotazione e alla scala, BRISK applica lo schema di campionamento ruotato di un angolo α = arctan 2(gy, gx)attorno al

keypoint k. Il descrittore risulta quindi un vettore di bit dk, assemblato tramite il

confronto delle intensità di tutte le coppie di punti di breve distanza (pα

i, pαj) ∈ S,

in modo tale che ogni bit b corrisponde a: b = ( 1, I(pα_j, σj) > I(pαi, σi) 0, altrimenti (2.10) ∀(pα i, pαj) ∈ S

Questa modalità di calcolo dei descrittori di BRISK porta diversi vantaggi. In primo luogo utilizza uno schema di campionamento deterministico, che comporta una densità uniforme dei punti campione ad un raggio fissato attorno al keypoint.

Di conseguenza non può succedere che lo smussamento Gaussiano, che viene fatto su misura, possa accidentalmente distorcere il contenuto informativo dei confronti smussando due punti campione vicini. Inoltre BRISK utilizza un numero molto minore di punti campione, limitando così la complessità. Nell’implementazione originale di BRISK, la soglia δmax è fissata in modo tale che il descrittore risulti

un vettore di 512 bit.

2.3

Metodi di riconoscimento e analisi di

accura-tezza

Le feature visuali locali estratte con gli algoritmi visti finora vengono spesso utiliz-zate per molte funzioni dell’analisi visuale. In particolare sono molto efficaci per quanto riguarda compiti di riconoscimento visuale. Esempi applicativi sono: il ri-conoscimento di oggetti, il riri-conoscimento di punti di riferimento, le interrogazioni visuali, il recupero di immagini, etc. Nel corso di questo lavoro di tesi viene fatto uso di alcuni metodi di riconoscimento visuale. Vediamo quindi le modalità più utilizzate per implementare queste funzionalità, fornendo un’analisi delle tecniche impiegate allo stato dell’arte. Verrà inoltre mostrato come è possibile misurare l’accuratezza del riconoscimento.

2.3.1

Metodi di riconoscimento

Un sistema di riconoscimento è tipicamente caratterizzato dalla seguente struttu-ra: un dispositivo di acquisizione di immagini fornisce l’immagine in input, che contiene l’oggetto da riconoscere, e viene processata utilizzando uno degli algoritmi presentati nella Sezione 2.2. Il processo di riconoscimento utilizza un database di immagini di riferimento: per ognuna delle immagini del database vengono estratte le feature visuali corrispondenti, che vengono poi memorizzate. A questo punto deve essere identificata nel database l’immagine che è più simile all’immagine in input. Per fare questo si effettua un confronto tra le feature dell’immagine in

in-put e le feature di ognuna delle immagini del database. Per ognuno dei confronti l’algoritmo prende nota di quante corrispondenze ci sono tra le feature delle due immagini. Alla fine di questi processo, l’immagine del database con il più alto numero di corrispondenze viene considerata la più somigliante. Anche se que-sta procedura permette di ottenere dei buoni risultati di riconoscimento, possono essere implementati diversi miglioramenti per ottenere prestazioni migliori. Nel seguito ne vengono esposti due.

• Ricerca nearest neighbor:

per decidere se una una feature appartenente all’immagine in input corri-sponde ad una feature di un’immagine del database viene effettuata la cosid-detta ricerca del nearest neighbor, cioè del vicino più prossimo. Per feature a valori reali (come per SIFT), si utilizza la distanza euclidea, mentre per feature binarie si utilizza la distanza di Hamming. Tuttavia, il numero di feature contenuto nell’immagine di input e in ogni immagine del database può essere molto alto, nell’ordine delle centinaia o anche delle migliaia. Per questa ragione può essere molto costoso effettuare un confronto del gene-re tra l’immagine in input e quelle del database. Per ottimizzagene-re i tempi possono essere quindi utilizzate tecniche di ricerca come quella del nearest neighbor [22] [23]. Tuttavia, molte feature di un’immagine non presentano una corrispondenza corretta in quanto derivano da uno sfondo poco definito o non sono state individuate nelle immagini su cui si è effettuato il training. Per questo motivo, al fine di scartare le feature che non hanno una buona corrispondenza con il database, può venire l’idea di una soglia globale sulla distanza dalla feature più vicina. Questa soluzione non risolve però il pro-blema, in quanto alcuni descrittori sono molto più discriminanti di altri. Un metodo più efficace è quello di confrontare la distanza del nearest neighbor con quella del secondo nearest neighbor, utilizzando il cosiddetto test del

rapporto. La corrispondenza viene considerata valida se:

d1 ≤ τ · d2 (2.11)

dove d1 e d2 sono rispettivamente le distanze del nearest neighbor e del

secondo nearest neighbor. E’ stato dimostrato [16] che l’impiego di un test del rapporto con una soglia τ nel range 0.6-0.8 può migliorare nettamente le prestazioni.

• Controllo di consistenza geometrica:

Anche il test del rapporto non è in grado di eliminare tutte le false corri-spondenze. Per questa ragione esiste un’altra soluzione in grado di scartare quelle corrispondenze che non rispettano una trasformazione geometrica glo-bale. Questo metodo è detto RAndom SAmple Consensus (RANSAC) [24], che è in grado di stimare una omografia tra l’immagine in input e quella del database e verificare quindi quali sono le corrispondenze che rispettano l’omografia stimata.

Alla conclusione della fase di confronto delle dipendenze viene generata una clas-sifica delle immagini del database sulla base del numero di corrispondenze trovate con l’immagine in input. Le immagini che sono in cima alla classifica sono quelle più simili all’immagine in input (avranno infatti il maggior numero di corrispon-denze). La Figura 2.8 mostra le corrispondenze rilevate su un’immagine d’esempio. Quando il numero di immagini nel database è molto elevato, un tipo di confronto come quello di cui si è parlato finora può essere molto dispendioso. Possono essere utilizzati approcci differenti, i quali si appoggiano su una rappresentazione anco-ra più ridotta dell’immagine basata su descrittori di dimensioni fisse. E’ il caso del modello Bag of Visual Words (BoW) [25], con il quale i descrittori vengono quantizzati in cosiddette parole visuali, definite a partire da descrittori derivati da

Figura 2.8: Esempio di corrispondenze trovate tra due immagini utilizzando BRISK. Le linee verdi mettono in relazione le corrispondenze trovate. Immagine tratta da [11]

un certo numero di immagini campione. Pe ogni immagine, viene prodotta una firma identificativa nella forma di un istogramma, che conta il numero di volte in cui una determinata parola visuale compare nell’immagine. La corrispondenza delle immagini viene quindi ottenuta tramite il confronto degli istogrammi, invece che analizzando la corrispondenza di ogni singola feature. Tuttavia, siccome la rappresentazione BoW ignora le relazioni spaziali delle feature locali, il processo descritto precedentemente (cioè il confronto a coppie seguito dal RANSAC) viene generalmente applicato per riclassificare i risultati ottenuti con l’approccio BoW.

2.3.2

Misure di accuratezza

Per stimare le prestazioni di un sistema di riconoscimento di immagini possono essere utilizzati diversi metodi. Uno degli indici di misura più utilizzati, e che viene usato anche in questa tesi, è il Mean of Average Precision (MAP). Data un’interrogazione q, la precisione media (AP) è definita come:

APq =

Pn

k=1Pq(k)rq(k)

Rq

, (2.12)

dove Pq(k) rappresenta la precisione (cioè la frazione degli elementi rilevanti

rq(k) è una funzione che risulta uguale a 1 se l’elemento in posizione k è

rilevan-te per l’inrilevan-terrogazione e uguale a 0 altrimenti; Rq è il numero totale di elementi

rilevanti per l’interrogazione q e n è il numero totale degli elementi nella lista. Il valore medio di precisione (MAP) per un insieme Q di interrogazioni corrisponde alla media aritmetica dell’AP tra interrogazioni differenti:

M AP = PQ

q=1APq

Q , (2.13)

2.4

Codifica di descrittori binari

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 schesche-ma 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 utilizsen-zando 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 codicodi-ficare 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 pM_n (x, y) log₂ 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à pM_n (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 I_nN 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).

2.5

Modello rate-accuratezza

Il lavoro svolto in questa tesi, in particolare per quanto riguarda il confronto dei paradigmi analizza-poi-comprimi e comprimi-poi-analizza, si basa su un modello rate-accuratezza proposto in [28]. La creazione di questo modello parte dal pre-supposto, già espresso in precedenza, che nel contesto delle reti di sensori visuali è estremamente importante minimizzare il più possibile la quantità di dati da immagazzinare o trasmettere da un nodo, a causa della disponibilità limitata di

banda e energia. Tale quantità di dati corrisponde non solo ai bit usati per codi-ficare ciascuna feature visuale, ma anche dal numero totale di feature che devono essere trasmesse. Questo modello mira quindi a svolgere un’analisi che permetta di comprendere quale sia il parametro con un impatto maggiore sull’accuratezza finale: si potrebbe dover scegliere ad esempio, a parità di disponibilità di bitrate, se inviare poche feature quantizzate in modo preciso oppure se inviarne molte quantizzate grossolanamente. Viene di seguito illustrato il modello.

Sia I un’immagine che viene processata per mezzo di un detector invariante alla scala. Il detector identifica i keypoint rilevanti ki, i = 1, ..., Mi, dove Mi

rap-presenta il numero di keypoint (dipendente dal contenuto) estratti dall’immagine I. Il vettore ki = [xi, yi, σi, Hi]

t _{indica la posizione del keypoint nel dominio dello}

scale-space e una misura legata alla rilevanza del keypoint. Per ogni keypoint viene ricavato un descrittore di di dimensione proporzionale a σi a partire

dal-la chiazza intorno a (xi, yi). Se il descrittore non è binario (come per SIFT e

SURF) allora di ∈ Rd. Nel caso invece di descrittori binari (come per BRISK),

di ∈ {0, 1}d. I descrittori vengono quindi codificati attraverso uno dei metodi

esposti nella Sezione 2.4. Nel caso di descrittori non binari, ogni descrittore viene quantizzato e codificato entropicamente in modo da ottenere un rate medio per descrittore rd

∆,i. Il rate complessivo necessario per trasmettere le feature locali

dell’immagine I è uguale a

ρI = MI(rkI + r d

∆,i), (2.21)

dove rk

I è il rate necessario per codificare le coordinate spaziali di ciascun keypoint.

Nel caso invece di descrittori binari, ogni descrittore viene ricavato tramite una specifica strategia di selezione e codificato in modo tale da rispettare una certa disponibilità di bitrate rd

D,i. Il rate complessivo necessario per trasmettere le

ρI = MI(rkI + r d

D,i). (2.22)

Anche la posizione dei keypoint deve essere codificata e trasmessa, affinché possa essere effettuata la verifica spaziale (ad esempio con RANSAC) sul nodo centra-le. La maggior parte dei detector producono coordinate rappresentate con una precisione in virgola mobile, tuttavia la maggior parte dei compiti di analisi richie-de una precisione minore. Per questa ragione le coordinate di ciascun keypoint vengono codificate utilizzando rk

I = log24Nx + log24Ny, dove Nx e Ny sono le

dimensioni dell’immagine in input.

Per la realizzazione di questo modello è stato utilizzato un sistema in cui un nodo provvisto di fotocamera acquisisce un’immagine contenente un particolare oggetto, estrae quindi le feature locali e le invia ad un nodo centrale, il quale si occupa di eseguire il processo di riconoscimento. Le corrispondenze vengono rile-vate confrontando i vettori delle feature locali e quelli relativi alle immagini del database e viene utilizzato RANSAC per controllare la consistenza geometrica. Ciò che è stato osservato è che, in contrasto con gli studi precedenti, sia il nu-mero di feature M da trasmettere, sia il bitrate di quantizzazione possono essere ricavati indipendentemente per ogni immagine di interrogazione. Il numero dei keypoint estratti dipende dal contenuto dell’immagine e può verificarsi che ecceda M. E’ quindi necessario determinare un sottoinsieme di M keypoint per il calcolo e l’invio dei descrittori associati. Come è stato mostrato in [30], selezionando i primi M keypoint in ordine descrescente in base al valore di punteggio associato (come ad esempio il punteggio s per le feature di BRISK), vengono migliorate le prestazioni della fase di ricerca delle corrispondenze. A questo punto vengono ricavati M vettori di feature e vengono trasmessi al nodo centrale. L’accuratezza viene quindi valutata per mezzo del MAP. I risultati ottenuti hanno mostrato che le curve rate-accuratezza ottenute presentano lo stesso comportamento al variare del dataset e dell’algoritmo di estrazione delle feature. La Figura 2.10 mostra la

Figura 2.10: Curva rate-accuratezza nel caso del dataset ZuBuD e feature di BRISK. Ognuna delle linee colorate rappresenta la curva di rate-accuracy per un diverso numero di feature M al variare del numero D di confronti bit a bit. La linea nera tratteggiata è l’inviluppo della famiglia di curve di rate-accuratezza, e rappresenta l’accuratezza migliore che può essere ottenuta ad un dato rate. La curva corrispondente all’etichetta ALL è stata ottenuta utilizzando la totalità delle feature estratte.

famiglia di curve ottenuta utilizzando il dataset ZuBuD e le feature ottenute con BRISK. Come si può vedere, l’accuratezza finale non dipende solo dal numero di feature usate per il riconoscimento ma anche dal rate. Per esempio, prendendo in considerazione la Figura 2.10, usando M = 20 feature codificate con rd _{= 800}

bit per feature si ottiene un’accuratezza più bassa rispetto ad un utilizzo di 40 feature con 400 bit per feature, pur mantenendosi costante il rate complessivo. Allo scopo di determinare l’inviluppo della famiglia di curve, ogni curva AM(ρ)

viene approssimata con una funzione lineare a tratti composta da due parti: AM(ρ) = min(gM(ρ), hM(ρ)), (2.23)

Per ridurre il numero di parametri da stimare, viene imposto che le linee che si adattano alla prima parte della curva abbiano tutte lo stesso coefficiente angolare m, mentre le linee che si adattano la seconda parte della curva siano tutte parallele all’asse delle x. In seguito, per ogni valore di M si ottengono pM e qM con il metodo

dei minimi quadrati, andando poi ad analizzare il loro comportamento al variare di M, cosa che può essere modellata come segue:

p(M ) = α + βM, q(M ) = δ + γ

M (2.25)

dove α, β, γ e δ sono parametri del modello ottenuti dalla famiglia di curve osser-vata. L’inviluppo di tale famiglia risulta il luogo dei punti per il quale g(ρ) = h(ρ) e quindi:

M ρ + (α + βM ) = δ + γ

M (2.26)

Risolvendo per M si ottiene quindi il numero ottimale di feature da utilizzare ad un certo rate ρ al fine di massimizzare l’accuratezza del compito di analisi:

M (ρ) = −(α − δ + mρ) +p(α − δ + mρ)

2_{+ 4βγ}

2β . (2.27)

A questo punto, sostituendo la (2.27) nella (2.22), si trova il numero ottimale di bit rd_(ρ) che deve essere allocato per ogni descrittore di feature, che può essere

utilizzato per selezionare in modo appropriato il numero di confronti bit a bit D. La coppia hM(ρ), rd_(ρ)i definisce l’allocazione interna per un certo rate ρ. La

Figura 2.11 mostra la curva di allocazione interna con il dataset ZuBuD e feature di SURF.

Ottimizzazioni di BRISK

Per utilizzare un paradigma del tipo analizza-poi-comprimi, come si è visto in precedenza, è di fondamentale importanza ridurre al massimo i consumi energeti-ci, in particolare quelli derivanti dall’esecuzione dei compiti di analisi visuale sui nodi della rete. In quest’ottica risulta determinante la scelta di quale algoritmo di estrazione delle feature utilizzare. Prendendo in considerazione gli algoritmi in grado di mantenere l’invarianza alla scala, caratteristica cruciale per diverse applicazioni, è necessario scegliere quello che riesce ad eseguire il proprio compito nel modo più efficiente. Come si è visto in [12], l’algoritmo che risponde a questi requisiti è BRISK [11]. Seppure BRISK risulta molto efficiente, l’esecuzione di funzioni di analisi visuale su nodi alimentati da una batteria può comunque ri-velarsi molto dispendiosa per i nostri scopi. Si rivela quindi necessaria un’analisi approfondita dell’algoritmo di BRISK, con lo scopo di individuare ulteriori otti-mizzazioni possibili, in modo tale da rendere massima l’efficienza dell’esecuzione su dispositivi con scarse disponibilità energetiche.

3.1

Dispositivo utilizzato

Il lavoro effettuato in questa tesi si basa sull’utilizzo di un dispositivo Beaglebone, mostrato in Figura 3.1. La beaglebone è un computer di dimensioni ridotte, a basso costo, dotato di un processore ARM Cortex-A8 e che utilizza l’architettura

Figura 3.1: Dispositivo Beaglebone. La Figura mostra il lato superiore e il lato inferiore della board.

ARMv7-A. Le caratteristiche di questo dispositivo sono le seguenti[10]: • Processore ARM Cortex-A8 (fino a 720 Mhz di frequenza)

• 256 MB DDR2 RAM

• 10/100 Ethernet RJ45 socket, IPv4 e IPv6 networking • sistema operativo: Ubuntu Linux

• slot MicroSD

• card microSD da 4gb • porta USB 2.0 di tipo A

Figura 3.2: La tabella in Figura mostra i diversi consumi di potenza della Beaglebone in vari scenari esecutivi. I valori sono espressi in mA.

• dimensioni: 86.4mm x 53.3mm

In questo lavoro di tesi la Beaglebone viene utilizzata tramite connessione USB ad un computer desktop. L’accesso al dispositivo viene effettuato dal computer desktop tramite il protocollo di rete SSH. Vengono utilizzate le funzioni di analisi visuale della versione 2.4.5 di OpenCV. Nella Figura 3.2 possiamo osservare i consumi energetici della board in alcuni scenari esecutivi.

3.2

Considerazioni preliminari e struttura di

BRI-SK

L’assunzione che sta alla base di questo lavoro è quella per cui il consumo ener-getico derivante dall’esecuzione di un algoritmo sia direttamente proporzionale al tempo dell’esecuzione stessa. Una tale assunzione si è resa necessaria a causa del fatto che, per questo lavoro di tesi, gli strumenti a disposizione non permettono una misurazione diretta dell’energia effettivamente consumata. D’altro canto, i consumi energetici derivanti da un dispositivo Beaglebone durante l’esecuzione di un determinato processo sono pressoché costanti nel tempo. Grazie allo stru-mento software cpufreq è infatti possibile tenere sotto controllo la frequenza di lavoro del processore. Abbiamo osservato che durante l’esecuzione di un processo la frequenza assume lo stesso valore (500MHz) per la quasi totalità del tempo di esecuzione. Questo valore corrisponde alla frequenza massima di lavoro del

processore. Prendiamo quindi in considerazione una potenza di lavoro della CPU pari a 2.1 W, corrispondente al valore di frequenza di picco del dispositivo. Per comprendere come migliorare l’efficienza di BRISK, è necessaria una fase preliminare che analizzi la struttura di brisk e determini quali sono le parti più dispendiose di esso. La struttura dell’algoritmo può essere vista come composta di tre parti: (i) la generazione del nucleo, (ii) la fase di detection e (iii) la fase di description. Nel dettaglio:

1. Generazione del nucleo:

Questa è la fase preliminare dell’algoritmo. Vengono create le strutture dati necessarie per implementare lo schema di campionamento visto nella Sezione 2.2.3. Vengono definiti quali sono i punti da campionare attorno al keypoint e quali sono le distanze tra di essi. In seguito vengono prese in considerazione tutte le coppie di punti appartenenti allo schema, che costituiscono l’insieme A: in base alla distanza tra i due punti di una coppia e alle due soglie δmax

e δmin vengono definiti i due sottoinsiemi S delle coppie a breve distanza e

L delle coppie a lunga distanza. Questi due sottoinsiemi saranno poi utili per ottenere i descrittori e l’invarianza alla rotazione.

2. Fase di detection:

In questa fase vengono estratti i keypoint a partire dall’immagine in input. E’ prevista l’esecuzione di due funzioni:

• Costruzione della piramide delle scale: vengono determinati i vari strati nello scale-space che andranno a costituire la cosiddetta piramide. In particolare vengono definiti gli strati corrispondenti alle ottave e gli strati intermedi tra le ottave. Per questa operazione viene fatto uso di due funzioni che ridimensionano l’immagine (una che effettua un ridi-mensionamento di 1/2 e l’altra di 2/3), permettendo quindi di lavorare su scale differenti.

• Estrazione dei keypoint: questa funzione si occupa di determinare i punti salienti dell’immagine, tramite le modalità esposte nella Sezione 2.2.3. La sua implementazione prevede l’utilizzo di una soglia, che determina la severità dei vincoli che un punto deve rispettare per essere identificato come saliente. Se la soglia è alta, i vincoli sono molto stringenti, e di conseguenza il numero di keypoint individuati è basso. Viceversa, nel caso di una soglia piccola, i keypoint individuati saranno molti. Questa parte si occupa quindi di effettuare tutte le operazioni di confronto tra i valori di intensità dei pixel, sia sul piano dell’immagine che nello scale-space, sfruttando anche funzioni di interpolazione. 3. Fase di description:

In questa fase vengono determinati i descrittori sulla base dei keypoint in-dividuati nella fase di detection. L’implementazione prevede inizialmente una procedura di rimozione dei keypoint molto vicini ai bordi. In seguito, per ognuno dei keypoint individuati, vengono eseguite le seguenti operazio-ni: viene innanzitutto determinato il gradiente globale associato al keypoint per ottenere l’invarianza alla rotazione; successivamente vengono prese in considerazione tutte le coppie dell’insieme S e viene effettuato il test bina-rio per ognuna di esse, in modo tale da determinare i bit che comporranno il descrittore.

Vediamo ora come si comporta ognuna di queste fasi in termini di tempi di ese-cuzione. Sono stati acquisiti i tempi necessari per eseguire l’analisi di alcune immagini campione a tre diverse risoluzioni: VGA (640x480), SVGA (800x600) e XGA (1024x768). E’ stata inoltre fatta variare la soglia per la detection dei keypoint. Nelle figure 3.3, 3.4 e 3.5 sono rappresentati in percentuale i pesi delle singole fasi sul tempo di esecuzione totale, per ognuna delle risoluzioni. Da questi risultati si può osservare come prima cosa che, nella maggior parte dei casi, la fase di description rappresenta la parte più dispendiosa. Anche la fase di generazione

del nucleo occupa una fetta rilevante del tempo di esecuzione totale. Tuttavia è importante notare che questa parte può essere eseguita in modo totalmente in-dipendente dall’immagine che viene analizzata, in quanto si occupa solamente di creare strutture che non necessitano di nessun dato relativo all’immagine stessa. Per questa ragione la fase di generazione del nucleo può essere eseguita una sola volta all’inizio del processo, non andando così ad impattare sulle prestazioni. Per quanto riguarda la costruzione della piramide, si osserva che, alle risoluzioni più alte e considerando soglie grandi, l’impatto sul tempo totale è considerevole. E’ degno di nota il fatto che gran parte dell’esecuzione di questa fase è occupata dalle funzioni di ridimensionamento dell’immagine, che risultano quindi le parti onerose. Infine osserviamo che la fase di estrazione dei keypoint rappresenta un peso pressoché costante (poco meno del 20%) in quasi tutti i casi.

Partendo da queste osservazioni, si può pensare all’implementazione di migliorie che riducano le componenti più dispendiose.

60 70 80 90 100 110 120 0 10 20 30 40 50 60 70 Soglia Percentuale Generazione nucleo Costruzione piramide Estrazione keypoint Description

Figura 3.3: Tempi di esecuzione delle singole operazioni di BRISK alla risoluzione VGA, al variare della soglia.