Optimal anchor node placement for indoor localization in wireless

Politecnico di Milano
Facoltà di ingegneria dell’Informazione
Corso di Laurea Magistrale in Ingegneria Informatica
ANALISI ENERGETICA E OTTIMIZZAZIONE
DELL’ALGORITMO BRISK
Autore:
Matr.
Simone ANGHILERI
782978
Relatore:
Ing. Matteo CESANA
Correlatore: Ing. Alessandro REDONDI
Anno Accademico 2012-2013
Sommario
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 sono alimentati tramite batteria, uno dei requisiti fondamentali è l’efficienza. Il
progetto Greeneyes ha lo scopo di lavorare in questa direzione attraverso la creazione 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 acquisita, 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 svolgere i compiti di analisi visuale, inviando poi al nodo centrale una rappresentazione
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 paradigmi CTA e ATC, con l’intento di paragonarne i consumi e determinare quindi
quale sia la soluzione migliore.
1
Indice
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
Metodi di riconoscimento e analisi di accuratezza . . . . . . . . .
25
2.3.1
Metodi di riconoscimento . . . . . . . . . . . . . . . . . . .
25
2.3.2
Misure di accuratezza . . . . . . . . . . . . . . . . . . . . .
28
Codifica di descrittori binari . . . . . . . . . . . . . . . . . . . . .
29
2.4.1
Codifica senza perdite . . . . . . . . . . . . . . . . . . . .
30
2.4.2
Costruzione del descrittore: codifica con perdite . . . . . .
31
Modello rate-accuratezza . . . . . . . . . . . . . . . . . . . . . . .
34
2.3
2.4
2.5
2
3 Ottimizzazioni di BRISK
40
3.1
Dispositivo utilizzato . . . . . . . . . . . . . . . . . . . . . . . . .
40
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’immagine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
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 necessaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 Implementazione e risultati
53
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 necessaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Comprimi-poi-analizza vs Analizza-poi-comprimi
69
71
5.1
Confronto rate-energia . . . . . . . . . . . . . . . . . . . . . . . .
71
5.2
Risultati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
5.3
Codifica Entropica . . . . . . . . . . . . . . . . . . . . . . . . . .
79
6 Conclusioni e direzioni di lavoro future
3
81
Bibliografia
84
4
Elenco delle figure
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
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-
2.9
zione VGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4
Tempi di esecuzione delle singole operazioni di BRISK alla risoluzione SVGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5
45
46
Tempi di esecuzione delle singole operazioni di BRISK alla risoluzione XGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
46
3.6
Registri a 128 bit utilizzati dall’insieme di istruzioni SSE . . . . .
50
3.7
Rappresentazione dell’esecuzione dell’istruzione NEON VADD . .
51
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à smussata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
4.4
Speedup ottenuto con l’ottimizzazione relativa all’intensità smussata 60
4.5
Speedup relativo all’ottimizzazione di ridimensionamento delle immagini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6
63
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 analizzapoi-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. . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4
Tempi di esecuzione necessari per la fase di description al variare
del numero di keypoint . . . . . . . . . . . . . . . . . . . . . . . .
5.5
74
75
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 ottimizzata di BRISK rispetto all’originale(ZuBuD) . . . . . . . . . . . .
6
79
5.9
Guadagno energetico in termini percentuali della versione ottimizzata di BRISK rispetto all’originale(Oxford) . . . . . . . . . . . .
7
80
Capitolo 1
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’interesse anche da parte del settore industriale, nell’ottica di un utilizzo commerciale
dei servizi che possono essere forniti da questa tecnologia [1][2]. In particolare, 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 quantizzando 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. Attualmente l’approccio più utilizzato nel campo dell’analisi visuale è quello che
8
CAPITOLO 1. INTRODUZIONE
prevede la creazione di una versione compressa, e quindi qualitativamente peggiore, 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 importanza. 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’acquisizione 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 successo 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 paradigma dell’Internet degli oggetti [8][9]. Le VSN sono in grado infatti di prendersi
carico di funzioni complesse di analisi, quali localizzazione, monitoraggio, riconoscimento 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, nell’ottica di un sistema maggiormente focalizzato sugli aspetti legati ai consumi
energetici ed in linea con gli obiettivi del progetto europeo GreenEyes. In particolare, 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 ottenuti. Si prende inoltre in considerazione l’algoritmo di analisi visuale BRISK (Binary
9
CAPITOLO 1. INTRODUZIONE
Robust Invariant Scalable Keypoints) [11], rivelatosi tra i più efficienti, con l’obiettivo 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 sensori 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 rappresentazione 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 destinazione finale, al fine di rendere possibile l’esecuzione 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’architettura 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
10
CAPITOLO 1. INTRODUZIONE
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 incorporate che possono essere utilizzate 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 anche 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 significativo impatto in tutti quegli scenari applicativi nei quali l’analisi visuale non è
11
CAPITOLO 1. INTRODUZIONE
al momento fattibile a causa di vincoli energetici molto stringenti. Un esempio
può essere il caso del monitoraggio ambientale in zone pericolose o inaccessibili. 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 copertura più completa del territorio, rendendo 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 Greeneyes 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 meno onerosa dei compiti di analisi visuale e di conseguenza ottenere un risparmio
energetico. Per il conseguimento di questo obiettivo questa tesi si occupa di modificare 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. Dopo 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 guadagno apportato da quest’ultima. Viene infine effettuato un confronto sul piano
12
CAPITOLO 1. INTRODUZIONE
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 riguardanti gli algoritmi di analisi visuale. In seguito viene offerta una panoramica sui
principali algoritmi di analisi visuale allo stato dell’arte, concentrandosi poi sulle modalità di riconoscimento degli oggetti e sui metodi utilizzati per la misura
dell’accuratezza. Viene poi illustrato il concetto di descrittore binario e delle modalità 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 ricercare quali sono le parti più dispendiose di esso e 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 della versione ottimizzata dell’algoritmo BRISK, rapportato a quello della versione
originale.
Il Capitolo 6 infine conclude la tesi e si occupa di delineare quali sono gli sviluppi
futuri.
13
Capitolo 2
Stato dell’arte
In questo capitolo viene fornito una descrizione dettagliata riguardo ai concetti
relativi all’analisi visuale. Vengono inizialmente introdotti concetti utili a comprendere il funzionamento dei principali algoritmi di analisi. Si passa quindi ad
analizzare tre di questi algoritmi allo stato dell’arte. Vengono infine esposti i meccanismi 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 estrazione di feature. Le feature visuali vengono solitamente utilizzate in diversi ambiti
applicativi, a partire dall’acquisizione di immagini e video fino ad arrivare al monitoraggio 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 spaziale 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
14
CAPITOLO 2. STATO DELL’ARTE
(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 rappresenta 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 strutture simili a chiazze. La Figura 2.1 mostra un esempio di feature identificate in
un’immagine.
Il processo di estrazione delle feature viene effettuato in due passi. Inizialmente 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 caratterizzate 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 corrispondente non sono standard. Keypoint individuati su scala ridotta corrispondono a
15
CAPITOLO 2. STATO DELL’ARTE
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 individuate. 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
2.2.1
Algoritmi di analisi visuale
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 base 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 consolidato 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 keypoint 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 dire16
CAPITOLO 2. STATO DELL’ARTE
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 scala può essere effettuata tramite 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 input 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 approssimazione 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 sinistra). 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
17
CAPITOLO 2. STATO DELL’ARTE
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 curvatura. Questo processo, oltre a migliorare il riconoscimento e la stabilità,
permette anche di scartare i keypoint con un basso contrasto. Una fase ulteriore si occupa di non considerare i keypoint lungo i bordi, contribuendo
al miglioramento delle prestazioni.
18
CAPITOLO 2. STATO DELL’ARTE
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’orientamento finale, viene individuato il picco più alto dell’istogramma e, per
19
CAPITOLO 2. STATO DELL’ARTE
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 trasformazioni, quali i cambiamenti di illuminazione. La Figura 2.4 mostra il processo di
costruzione del descrittore di SIFT. In primo luogo vengono campionate le intensità 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 posizione della finestra. In seguito viene costruito il descrittore del keypoint, tramite
Figura 2.4: Creazione del descrittore.Immagine tratta da [16]
20
CAPITOLO 2. STATO DELL’ARTE
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 esecuzione efficiente e mirata al risparmio energetico. Questo miglioramento viene
ottenuto appoggiandosi a immagini integrali per la convoluzione compiuta dal detector 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 computazione 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
G(σ) · I(x, y)
∂x2
∂ ∂
G(σ) · I(x, y)
∂x ∂y
#
∂ ∂
G(σ) · I(x, y)
∂x ∂y
∂2
G(σ) · I(x, y)
∂y 2
(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 deriva21
CAPITOLO 2. STATO DELL’ARTE
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 possono 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 ) = Dxx Dyy − (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 però, a causa dell’utilizzo di filtri e immagini integrali, lo scale-space di SURF
viene creato applicando filtri di dimensioni diverse direttamente sull’immagine 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 nonmassimo 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.
22
CAPITOLO 2. STATO DELL’ARTE
• Assegnazione dell’orientamento:
per ottenere l’invarianza alla rotazione, anche SURF identifica un orientamento 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 scorrevole 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 ciascun keypoint una regione quadrata, orientata lungo l’orientamento dominante e
la cui dimensione è proporzionale alla scala del keypoint. La regione viene quindi suddivisa in 4x4 sottoregioni più piccole. All’interno 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 feature. 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
i
|dy | .
(2.4)
Il descrittore finale viene ottenuto concatenando i vettori delle feature di tutte le sottoregioni, producendo un vettore di description composto da 64 elementi. Analogamente a SIFT, l’invarianza al contrasto viene ottenuta tramite
normalizzazione.
23
CAPITOLO 2. STATO DELL’ARTE
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 Scalable 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’immagine 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 AGAST [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
Ip − t, dove t è una soglia predefinita. Ad ogni spigolo viene quindi assegna24
CAPITOLO 2. STATO DELL’ARTE
to un punteggio s, definito 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, velocizzando 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 rilevanza. 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, mentre 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 rilevanza) 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 precisato a livello di pixel ed in seguito, tramite l’adattamento ad una parabola
1D lungo l’asse delle scale, viene interpolata la scala esatta del keypoint.
25
CAPITOLO 2. STATO DELL’ARTE
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 campionamento 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
una delle N (N − 1)/2 coppie di punti campione e I(pi , σi ) e I(pj , σj ) sono i
26
CAPITOLO 2. STATO DELL’ARTE
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:
I(pj , σj ) − I(pi , σi )
.
kpj − pi k2
Considerando poi l’insieme A di tutte le coppie di punti campione:
g(pi , pj ) = (pj − pi ) ·
A = (pi , pj ) ∈ R2 × R2 |i < N ∧ j < i ∧ i, j ∈ N
(2.5)
(2.6)
vengono definiti il sottoinsieme S delle coppie di breve distanza e il sottoinsieme L delle coppie di lunga distanza:
S = {(pi , pj ) ∈ A| kpj − pi k < δmax } ⊆ A
27
(2.7)
CAPITOLO 2. STATO DELL’ARTE
L = {(pi , pj ) ∈ A| kpj − pi k > δ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:
gx
1
g=
= ·
gy
L
X
g(pi , pj ).
(2.9)
(pi ,pj )∈L
Per questo calcolo vengono utilizzate le coppie di L , sulla base dell’assunzione 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 quanto si basa sul concetto di descrittore binario, che fu proposto 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 descrittore 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:
(
1, I(pαj , σj ) > I(pαi , σi )
b=
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.
28
CAPITOLO 2. STATO DELL’ARTE
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 accuratezza
Le feature visuali locali estratte con gli algoritmi visti finora vengono spesso utilizzate per molte funzioni dell’analisi visuale. In particolare sono molto efficaci per
quanto riguarda compiti di riconoscimento visuale. Esempi applicativi sono: il riconoscimento di oggetti, il riconoscimento 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 struttura: 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 in29
CAPITOLO 2. STATO DELL’ARTE
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 questa 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 corrisponde ad una feature di un’immagine del database viene effettuata la cosiddetta 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 genere tra l’immagine in input e quelle del database. Per ottimizzare 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 problema, 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
30
CAPITOLO 2. STATO DELL’ARTE
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 corrispondenze. Per questa ragione esiste un’altra soluzione in grado di scartare
quelle corrispondenze che non rispettano una trasformazione geometrica globale. 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 classifica 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 corrispondenze). 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 ancora 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
31
CAPITOLO 2. STATO DELL’ARTE
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:
Pn
APq =
k=1
Pq (k)rq (k)
,
Rq
(2.12)
dove Pq (k) rappresenta la precisione (cioè la frazione degli elementi rilevanti recuperati) considerando i primi k risultati nella classifica delle immagini del database;
32
CAPITOLO 2. STATO DELL’ARTE
rq (k) è una funzione che risulta uguale a 1 se l’elemento in posizione k è rilevante per l’interrogazione 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:
PQ
2.4
APq
,
Q
q=1
M AP =
(2.13)
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 perdite 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
33
CAPITOLO 2. STATO DELL’ARTE
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 schema di campionamento. Lo schema di campionamento standard di BRISK consiste
di N = 60 punti, quindi |A| = 1770. Invece nel caso di FREAK N = 43 punti, 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à costituito 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 senza 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:
H(πn ) = −pn (0) log2 pn (0) − pn (1) log2 pn (1)
34
(2.14)
CAPITOLO 2. STATO DELL’ARTE
In modo simile, è possibile calcolare l’entropia condizionata H(πn1 |πn2 ). Le statistiche utilizzate per calcolare H(πn ) e H(πn1 |πn2 ) possono essere ottenute analizzando 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 codifica necessaria per codificare senza perdite il descrittore è limitata inferiormente
da
R=
D
X
H(π̃n |π̃n−1 , ..., π̃1 ).
(2.15)
n=1
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 H(πn |π̃n−1 )
πn
(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 descrivere altre tre nuove strategie presentate in [28], cioè la strategia matching-based,
la strategia coding-based e la strategia hybrid.
35
CAPITOLO 2. STATO DELL’ARTE
Strategia di BRISK
La strategia di Brisk per la costruzione del descrittore è stata esposta nella Sezione 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 descrittore.
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 preliminare, 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 immagini. 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 correlazione 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
36
CAPITOLO 2. STATO DELL’ARTE
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 corrispondenze. Quindi, per ognuna delle coppie in A, è possibile ricavare l’informazione
condivisa I M (πn ), m = 1, ..., N (N − 1)/2,
I M (πn ) =
X X
pM
n (x, y) log2
x∈0,1 y∈0,1
pM
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
InN per le coppie senza corrispondenze. In conclusione, per ognuna delle coppie in
A viene ricavata la seguente funzione di punteggio:
Jn = I M (πn ) − I N (πn ),
37
(2.19)
CAPITOLO 2. STATO DELL’ARTE
e le coppie vengono classificate in ordine decrescente di Jn . Questa strategia sceglie 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 elementi 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.
D elementi del descrittore vengono selezionati per mezzo della seguente strategia:
π̃n = arg max α(I M (πn ) − I N (πn )) − (1 − α)H(πn |π̃n−1 )
πn
(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 presupposto, 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
38
CAPITOLO 2. STATO DELL’ARTE
banda e energia. Tale quantità di dati corrisponde non solo ai bit usati per codificare 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 rappresenta 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 dalla 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
d
. Il rate complessivo necessario per trasmettere le feature locali
descrittore r∆,i
dell’immagine I è uguale a
d
),
ρI = MI (rIk + r∆,i
(2.21)
dove rIk è 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
d
disponibilità di bitrate rD,i
. Il rate complessivo necessario per trasmettere le
feature locali binarie dell’immagine I risulta quindi uguale a:
39
CAPITOLO 2. STATO DELL’ARTE
d
).
ρI = MI (rIk + rD,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 centrale. La maggior parte dei detector producono coordinate rappresentate con una
precisione in virgola mobile, tuttavia la maggior parte dei compiti di analisi richiede una precisione minore. Per questa ragione le coordinate di ciascun keypoint
vengono codificate utilizzando rIk = log2 4Nx + log2 4Ny , 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 rilevate 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 numero 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
40
CAPITOLO 2. STATO DELL’ARTE
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)
gM (ρ) = mρ + pM , hM (ρ) = qm .
(2.24)
41
CAPITOLO 2. STATO DELL’ARTE
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 osservata. 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:
Figura 2.11: Curva di allocazione interna con dataset ZuBuD e feature di SURF.
42
CAPITOLO 2. STATO DELL’ARTE
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.
43
Capitolo 3
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 energetici, 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 rivelarsi molto dispendiosa per i nostri scopi. Si rivela quindi necessaria un’analisi
approfondita dell’algoritmo di BRISK, con lo scopo di individuare ulteriori ottimizzazioni 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
44
CAPITOLO 3. OTTIMIZZAZIONI DI BRISK
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
• alimentazione a +5V tramite connettore o porta USB.
45
CAPITOLO 3. OTTIMIZZAZIONI DI BRISK
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 BRISK
L’assunzione che sta alla base di questo lavoro è quella per cui il consumo energetico 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 strumento 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
46
CAPITOLO 3. OTTIMIZZAZIONI DI BRISK
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 ridimensionamento di 1/2 e l’altra di 2/3), permettendo quindi di lavorare
su scale differenti.
47
CAPITOLO 3. OTTIMIZZAZIONI DI BRISK
• 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 individuati 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 operazioni: 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 binario 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 esecuzione. 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
48
CAPITOLO 3. OTTIMIZZAZIONI DI BRISK
del nucleo occupa una fetta rilevante del tempo di esecuzione totale. Tuttavia è
importante notare che questa parte può essere eseguita in modo totalmente indipendente 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.
70
Generazione nucleo
Costruzione piramide
Estrazione keypoint
Description
60
Percentuale
50
40
30
20
10
0
60
70
80
90
Soglia
100
110
120
Figura 3.3: Tempi di esecuzione delle singole operazioni di BRISK alla risoluzione
VGA, al variare della soglia.
49
CAPITOLO 3. OTTIMIZZAZIONI DI BRISK
80
Generazione nucleo
Costruzione piramide
Estrazione keypoint
Description
70
Percentuale
60
50
40
30
20
10
0
60
70
80
90
Soglia
100
110
120
Figura 3.4: Tempi di esecuzione delle singole operazioni di BRISK alla risoluzione
SVGA, al variare della soglia.
80
Generazione nucleo
Costruzione piramide
Estrazione keypoint
Description
70
Percentuale
60
50
40
30
20
10
0
60
70
80
90
Soglia
100
110
120
Figura 3.5: Tempi di esecuzione delle singole operazioni di BRISK alla risoluzione
XGA, al variare della soglia.
3.3
Ottimizzazioni
In questa sezione verranno esposte le migliorie pensate per rendere l’esecuzione di
BRISK più efficiente. Le osservazioni fatte precedentemente hanno messo in mostra come nessuna parte dell’algoritmo presenti tempi di esecuzione trascurabili.
50
CAPITOLO 3. OTTIMIZZAZIONI DI BRISK
L’obiettivo diventa quindi quello di cercare di ottimizzare ogni singola porzione
di BRISK, con un occhio di riguardo per la fase di description, e fatta eccezione
per quanto riguarda la generazione del nucleo, che come abbiamo visto può essere
eseguita una sola volta all’inizio di tutto il processo di analisi.
3.3.1
Selezione delle coppie di punti
Questa ottimizzazione ha l’obiettivo di migliorare l’efficienza della fase di description. Come si è visto nella Sezione 2.2.3, per la creazione del costruttore, BRISK agisce tramite l’esecuzione di test binari che confrontano i valori di intensità
smussata delle coppie di punti appartenenti all’insieme S. Il risultato di ciascun
confronto determina il valore di uno dei bit del descrittore binario risultante. La
dimensione del descrittore dipende quindi dal numero di confronti che vengono
effettuati, in quanto tale numero corrisponde alla grandezza in bit del descrittore.
In ultima analisi quindi, è la quantità di coppie presenti nell’insieme S a determinare la dimensione finale del descrittore. La versione originale di BRISK prevede
che l’insieme S sia composto da 512 coppie, con la conseguenza che i descrittori
binari sono composti da 512 bit. La Sezione 2.4.2 ci ha mostrato che può essere
determinata la dimensione ottimale dei descrittori per garantire la massima accuratezza al variare del rate. Di conseguenza, si può pensare di rimuovere il vincolo
presente sulla dimensione del descrittore (fissa a 512), permettendo invece la determinazione di descrittori che abbiano anche dimensioni ridotte. Una modifica di
questo tipo può impattare positivamente anche sull’efficienza dell’algoritmo. Dimensioni ridotte dei descrittori comportano infatti un numero minore di confronti
necessari, riducendo così il carico computazionale. L’algoritmo deve quindi essere
modificato in modo tale da permettere una selezione delle coppie che compongono
l’insieme S basata sulle strategie esposte nella Sezione 2.4.2.
51
CAPITOLO 3. OTTIMIZZAZIONI DI BRISK
3.3.2
Calcolo dell’intensità smussata solo per i punti utilizzati
Anche questa ottimizzazione viene pensata per ridurre il costo associato alla fase
di description. Come si è visto in precedenza, i confronti effettuati per determinare i bit del descrittore prendono in considerazione i valori di intensità dei punti
attorno al keypoint, valori che vengono però smussati, al fine di evitare effetti
di aliasing durante la fase di campionamento. Questa operazione viene compiuta
applicando il cosiddetto smussamento Gaussiano, con una deviazione standard
proporzionale alla distanza tra i punti sul rispettivo cerchio dello schema di campionamento. L’operazione di smussamento utilizza i valori di una distribuzione
gaussiana in due dimensioni per costruire una matrice di convoluzione che viene
poi applicata all’immagine originale. L’intensità di un determinato pixel assume
poi il valore della media pesata delle intensità dei punti attorno al pixel stesso.
Il carico computazionale associato a questa operazione risulta quindi piuttosto
considerevole. L’implementazione di BRISK degli autori prevede che durante la
fase di description vengano calcolati i valori di intensità smussata per ciascuno dei
60 punti previsti dallo schema di campionamento. Dalle esecuzioni di BRISK si
osserva che per generare un descrittore di 512 bit vengono solitamente utilizzati
tutti i 60 punti dello schema. L’implementazione dell’ottimizzazione proposta nella Sezione precedente implicherebbe tuttavia la possibilità di lavorare con vettori
di descrizione di dimensioni anche molto minori di 512 bit. Siccome nel caso di
descrittori di dimensioni ridotte le coppie prese in considerazione per i test binari
sulle intensità sono poche, non tutti i punti previsti dallo schema di campionamento vengono effettivamente utilizzati. Di conseguenza il calcolo dell’intensità
smussata per questi punti rappresenterebbe un’operazione del tutto inutile. La
miglioria che deve essere implementata in questo caso deve quindi fare in modo
che l’intensità smussata venga determinata solamente per i punti dello schema di
campionamento realmente utilizzati.
52
CAPITOLO 3. OTTIMIZZAZIONI DI BRISK
3.3.3
Conversione delle funzioni di ridimensionamento dell’immagine
La fase di costruzione della piramide relativa allo scale-space è occupata prevalentemente dall’esecuzione di due funzioni che svolgono il compito di ridimensionare
l’immagine di partenza, una di un fattore 1/2 e l’altra di un fattore 2/3, permettendo così la formazione dei vari strati della piramide. Ottimizzare questa porzione di codice significa quindi migliorare le due funzioni di ridimensionamento.
L’implementazione originale di BRISK relativa a questa parte prevede l’utilizzo
di alcune istruzioni SSE2 e SSE3, che permettono di ottenere prestazioni migliori
in termini di velocità di esecuzione. Le SSE (Streaming SIMD Extensions) sono
un insieme di istruzioni SIMD (Single Instruction, Multiple Data) implementate da processori Intel. Le funzioni di ridimensionamento dell’immagine devono
effettuare molte operazioni identiche sui pixel dell’immagine. Siccome molti di
questi calcoli possono essere fatti in modo indipendente tra loro, BRISK sfrutta l’insieme di istruzioni SSE per elaborare tali dati in parallelo, ottenendo così
un incremento delle prestazioni. Naturalmente questa ottimizzazione è limitata
dal fatto che l’esecuzione dell’algoritmo deve avvenire su un’architettura (x86)
in grado di supportare queste istruzioni. Molti dei dispositivi in commercio che
possono essere utilizzati come nodi di una rete di sensori visuali si basano però
su un’architettura ARM, che è incompatibile con l’insieme di istruzioni SSE. E’
questo il caso del dispositivo Beaglebone utilizzato per questa tesi. La versione
di BRISK degli autori prevede che, nel caso di un’architettura non x86, vengano
utilizzate funzioni standard di ridimensionamento che non sono ottimizzate. Il
miglioramento che può essere apportato in questo caso è quindi una conversione
delle istruzioni SSE in istruzioni equivalenti supportate dall’architettura ARM. La
controparte delle SSE su ARM è rappresentata dalla tecnologia chiamata NEON.
NEON è una combinazione di istruzioni SIMD nata per accelerare e standardizzare il trattamento e l’elaborazione di segnali multimediali. Una conversione di
53
CAPITOLO 3. OTTIMIZZAZIONI DI BRISK
questo tipo permetterebbe quindi di ottenere le stesse prestazioni ottimizzate anche nel caso di architetture ARM. L’obiettivo è quello di effettuare una traduzione
che produca funzioni in grado di ottenere gli stessi risultati delle funzioni originali.
Entrambe le tecnologie hanno la caratteristica comune di lavorare con registri a
128 bit. In Figura 3.6 è mostrata una rappresentazione dei registri utilizzati dalle
istruzioni SSE, che possono essere suddivisi in elementi da 32 o 64 bit a seconda
delle necessità.
Figura 3.6: Registri a 128 bit utilizzati dall’insieme di istruzioni SSE.
Anche nel caso della tecnologia NEON i registri possono contenere diverse combinazioni di numeri interi o a virgola mobile, con dimensioni che possono variare
dai 16 bit ai 64 bit. Una volta riempiti, questi registri possono essere utilizzati per
eseguire operazioni in parallelo sui vari elementi che li compongono. La Figura
3.7 mostra un esempio di operazione di addizione bit a bit tra registri vettoriali,
eseguita tramite istruzioni NEON. Q1 e Q2 sono i registri sorgente composti da 8
elementi da 16 bit ciascuno mentre Q0 rappresenta il registro destinazione. L’operazione di addizione viene eseguita in parallelo tramite un’unica istruzione, e
54
CAPITOLO 3. OTTIMIZZAZIONI DI BRISK
Figura 3.7: Rappresentazione dell’esecuzione dell’istruzione VADD.I16 Q0, Q1, Q2.
Q1 e Q2 sono i due registri sorgente a 128 bit, suddivisi in 8 elementi da 16 bit (lane).
Q0 è il registro destinazione in cui vengono memorizzati i risultati.
indipendentemente per ogni coppia di elementi appartenenti ai registri Q1 e Q2;
i risultati vengono poi memorizzati negli elementi di Q0.
Sfruttando quindi la disponibilità delle istruzioni di NEON per l’architettura ARM, è possibile ottimizzare le funzioni di ridimensionamento dell’immagine
riproducendo gli algoritmi implementati originariamente con istruzioni SSE. La
difficoltà che si può incontrare risiede nel fatto che per molte delle istruzioni SSE
non esiste un’istruzione NEON corrispondente che svolga la stessa funzione. La
realizzazione di questo miglioramento contribuirebbe a ridurre il peso della fase
di detection.
3.3.4
Rimozione di operazioni di interpolazione
Nella Sezione 2.2.3 è stato mostrato come agisce BRISK per determinare i keypoint nella fase di detection. In particolare si è visto che un punto viene classificato
55
CAPITOLO 3. OTTIMIZZAZIONI DI BRISK
come keypoint solamente se il punteggio s a lui associato è maggiore non solo del
punteggio di tutti suoi vicini, ma anche di tutti i punteggi dei pixel sugli strati
della piramide immediatamente superiori e inferiori (nella zona corrispondente).
Più precisamente, in ognuno dei tre strati presi in considerazione, BRISK considera la rilevanza di un pixel come una quantità continua, e per questa ragione ricava
il punto con la rilevanza locale massima per mezzo di un’interpolazione. Questa
operazione presenta naturalmente dei vantaggi in termini di precisione dell’analisi. Tuttavia, nell’ottica di un risparmio energetico derivante dalla riduzione del
carico computazionale, può essere interessante studiare cosa succede nel caso in
cui questa operazione di rifinitura tramite interpolazione non venga eseguita, e
considerando quindi la rilevanza di un punto come una quantità discreta. L’idea
è quella di ricavare i punteggi massimi, sul livello superiore e sul livello inferiore
della piramide, per mezzo di semplici confronti, e prendendo in considerazione il
maggiore tra tutti i valori s associati ai punti della zona in analisi. Per verificare
poi se questa modifica può essere applicata con successo è necessario effettuare
delle valutazioni riguardanti sia i tempi di esecuzione sia l’accuratezza finale. In
particolare devono essere confrontati i tempi di esecuzione della fase di detection
originale e della detection in cui è stata rimossa l’interpolazione. Allo stesso modo deve essere effettuato un confronto sull’accuratezza finale della procedura di
riconoscimento dell’immagine. Per la valutazione dell’accuratezza è possibile utilizzare la misura del MAP, come abbiamo visto nella Sezione 2.3.2. Se i risultati
mostrano che i tempi di esecuzione vengono ridotti in modo rilevante e allo stesso
tempo l’accuratezza finale non peggiora significativamente, può essere considerata
l’applicazione di questa modifica, contribuendo a rendere meno onerosa la fase di
detection.
3.3.5
Esecuzione in parallelo del test binario
Come si è visto nella Sezione 3.3.3, su un’architettura ARM esiste la possibilità
di sfruttare le potenzialità del calcolo parallelo per mezzo dell’insieme di istru56
CAPITOLO 3. OTTIMIZZAZIONI DI BRISK
zioni NEON. Una parte del codice di BRISK per cui può essere implementata
questa funzionalità è la procedura di esecuzione del test binario. Come mostrato
in precedenza, questa fase prevede che per ciascuno dei keypoint individuati nella
detection vengano effettuati una serie di confronti, che danno poi come risultato
i bit di cui è composto il vettore di descrizione. Questi confronti risultano del
tutto indipendenti tra loro, in quanto vengono comparati valori di intensità già
calcolati in precedenza. Si può quindi pensare di sfruttare le potenzialità del calcolo parallelo per eseguire questo processo. I valori di intensità che devono essere
confrontati possono essere rappresentati tramite interi a 32 bit. Siccome la tecnologia NEON prevede l’utilizzo di registri a 128 bit, è possibile riempire ciascuno
di questi registri con quattro elementi da 32 bit. Di conseguenza ogni registro può
contenere fino a quattro diversi valori di intensità. Supponiamo di riempire due di
questi registri in modo tale che gli elementi in posizioni corrispondenti contengano
i valori delle intensità che ci interessa confrontare. Per esempio, chiamando I1 e I2
i valori delle intensità che devono essere comparate, se il primo elemento del primo
registro contiene I1 , il primo elemento del secondo registro dovrà contenere I2 . A
questo punto è possibile eseguire quattro confronti contemporaneamente con una
sola istruzione. Tramite l’istruzione adeguata vengono confrontati gli elementi dei
registri nella posizione corrispondente e il risultato viene poi memorizzato in un
registro destinazione. Un’ottimizzazione di questo tipo permetterebbe quindi, in
linea teorica, di eseguire il test binario quattro volte più velocemente.
3.3.6
Rimozione dell’invarianza alla rotazione quando non
necessaria
La fase di description di BRISK comprende, come abbiamo visto nella Sezione
3.2, l’esecuzione di una procedura che ha lo scopo di ottenere l’invarianza alla
rotazione. Grazie ad essa l’algoritmo risulta in grado di effettuare anche il riconoscimento di immagini ruotate rispetto all’immagine originale. Tuttavia non
tutti gli scenari applicativi necessitano di questa funzione: si pensi ad esempio
57
CAPITOLO 3. OTTIMIZZAZIONI DI BRISK
al caso del monitoraggio ambientale, in cui le fotocamere sono solitamente fisse
e acquisiscono immagini di un preciso luogo; anche i sistemi di video sorveglianza possono presentare queste caratteristiche e non necessitare quindi di sistemi
di riconoscimento invarianti alla rotazione. Per questa ragione, nei casi in cui i
vincoli energetici siano particolarmente stringenti e non sia presente l’eventualità
di dover riconoscere immagini ruotate, risulta ragionevole pensare di rimuovere
la fase di esecuzione relativa all’invarianza alla rotazione. Pur non essendo un
miglioramento applicabile in un contesto generale, si rivela comunque interessante osservare cosa comporta dal punto di vista dei consumi energetici, offrendosi
come possibile applicazione negli gli scenari sopra citati. Dal momento che questa operazione viene eseguita per ciascuno dei keypoint e prevede lo svolgimento
di calcoli piuttosto dispendiosi, ci si aspetta che una sua rimozione porti ad un
miglioramento incisivo delle prestazioni.
58
Capitolo 4
Implementazione e risultati
In questo capitolo verranno discussi i dettagli relativi all’implementazione delle ottimizzazioni esposte in precedenza e verranno mostrati i risultati ottenuti. Ognuna delle seguenti sezioni si riferisce all’ottimizzazione corrispondente illustrata nel
Capitolo 3.
4.1
I dataset
Nel corso di questo lavoro di tesi, le modifiche proposte vengono testate su due dataset differenti. Questi dataset sono disponibili pubblicamente e sono ampiamente
utilizzati allo stato dell’arte:
• ZuBuD:
lo Zurich Building Database5 (ZuBuD) contiene 1005 immagini a colori di
201 edifici appartenenti alla città di Zurigo. Ad ogni edificio sono associate
cinque immagini VGA (640x480), acquisite da punti di vista casuali, in stagioni differenti, in diverse condizioni climatiche e da due diverse fotocamere.
Un archivio separato rappresenta invece il dataset delle interrogazioni, e
contiene 115 immagini (alla risoluzione di 320x240) degli stessi edifici (immagini ottenute a partire da condizioni di acquisizione differenti). Alcune
immagini di questo dataset sono illustrate in Figura 4.1.
59
CAPITOLO 4. IMPLEMENTAZIONE E RISULTATI
(a)
(b)
(c)
Figura 4.1: Immagini campione del dataset ZuBuD
(a)
(b)
(c)
Figura 4.2: Immagini campione del dataset Oxford
• Oxford:
L’Oxford Building Database consiste di 5062 immagini ottenute da Flickr
attraverso la ricerca di determinati luoghi di Oxford. L’insieme di immagini
è stato poi manualmente annotato per costituire una tabella delle corrispondenze relativa a 11 diversi luoghi, ognuno rappresentato da cinque possibili
interrogazioni. Ciò fornisce un insieme di 55 interrogazioni sulle quali basare
la valutazione di un sistema di riconoscimento. Alcune immagini di questo
dataset sono illustrate in Figura 4.2.
4.2
Selezione delle coppie di punti
L’implementazione di questa ottimizzazione comporta una modifica della fase di
generazione del nucleo. E’ qui che viene infatti generato l’insieme S delle coppie
di breve distanza che viene poi utilizzato per ricavare il vettore di descrizione. La
versione originale di BRISK prevede che questo insieme sia formato dalle coppie
60
CAPITOLO 4. IMPLEMENTAZIONE E RISULTATI
di punti la cui distanza (in valore assoluto) sia minore della soglia δmax =9.75t,
dove t è la scala del keypoint. Per fare quindi in modo che vi sia la possibilità
di selezionare le coppie deve essere modificata la modalità di generazione dell’insieme S. In particolare, la nuova versione del codice è in grado di leggere, da
un file appositamente creato, quali sono le coppie da considerare per la creazione
del descrittore. Le coppie presenti nel file vengono scelte sulla base di una delle
strategie di selezione esposte nella Sezione 2.4.2. Usufruendo di una struttura
dati ausiliaria, le coppie vengono quindi acquisite dal file e vengono poi utilizzate
per la generazione dell’insieme S. Di seguito possiamo osservare una porzione del
codice modificato, che si occupa di riempire la struttura dati shortPairs, corrispondente all’insieme S, con l’insieme delle coppie precedentemente acquisite da
un file esterno:
1
2
3
4
5
6
for(int isp=0;isp<pairs.size();isp++){
BriskShortPair& shortPair = shortPairs_[indexChange[noShortPairs_]];
shortPair.i = temp_idx[isp].i;
shortPair.j = temp_idx[isp].j;
noShortPairs_++;
}
In Figura 4.3 possiamo osservare (linea rossa) il comportamento dei tempi di
esecuzione relativi alla computazione di un descrittore al variare del numero di
coppie utilizzate. Per l’ottenimento di questo grafico sono state prese in considerazione tre diverse risoluzioni: VGA, SVGA e XGA. Le coppie utilizzate per la
creazione dell’insieme S sono state generate casualmente, in quanto l’interesse di
questa analisi è focalizzato sui tempi di esecuzione della fase di description e la
procedura di riconoscimento può essere trascurata. Naturalmente una risoluzione
elevata, come nel caso di XGA, implica una maggiore quantità di dati che devono
essere processati e comporta l’identificazione di un numero più elevato di keypoint
rispetto a risoluzioni più basse. Per questa ragione i tempi di esecuzione risultano
maggiori. Il grafico mostra che il tempo impiegato per ricavare un descrittore
cresce in modo proporzionale al numero di coppie utilizzate. Possiamo osservare
61
CAPITOLO 4. IMPLEMENTAZIONE E RISULTATI
ad esempio che, se il numero di coppie utilizzate è basso (attorno a 100), il tempo di esecuzione impiegato per ricavare un singolo descrittore risulta ridotto di
circa 0,05 ms rispetto al tempo ottenuto con l’uso di tutte le coppie. Nell’ottica
del modello rate-accuratezza illustrato nella Sezione 2.3.2, che prevede l’utilizzo
di descrittori di dimensioni inferiori a 512 bit, questa ottimizzazione è in grado
quindi di apportare un primo miglioramento alle prestazioni di BRISK.
4.3
Calcolo dell’intensità smussata solo per i punti
utilizzati
Per implementare questa miglioria è necessario agire sia sulla fase di generazione
del nucleo sia sulla fase di description. Nel momento in cui le coppie vengono
inserite nell’insieme S, si procede anche alla memorizzazione di un dato, relativo
ad ognuno dei punti, che specifica se il punto stesso deve essere utilizzato durante
la fase di campionamento oppure no. Nell’implementazione originale della fase di
descrizione sono presenti due iterazioni tramite cui vengono presi in considerazione tutti gli N = 60 punti dello schema di campionamento e per ognuno di essi
viene ricavata l’intensità smussata. La modifica introdotta fa in modo che durante
queste iterazioni, considerando i dati raccolti nella fase di generazione del nucleo,
vengano calcolate le intensità smussate solamente per i punti effettivamente utilizzati. Ecco una porzione del codice modificato:
1
2
3
4
5
6
7
8
for(unsigned int i = 0; i<points_; i++){
if(pointUsed[i]==1){
*(pvalues++)=smoothedIntensity(image, _integral, x,y,scale,0,i);
}
else{
*(pvalues++);
}
}
pvalues è la struttura dati contenente i valori calcolati delle intensità smussate.
Se il punto preso in considerazione ha come valore associato 1 (pointUsed[i]==1)
62
CAPITOLO 4. IMPLEMENTAZIONE E RISULTATI
0.9
0.85
Tempo (ms)
0.8
0.75
0.7
0.65
0.6
Intensità smussata per tutti i punti
Intensità smussata per i punti utilizzati
0.55
0.5
0
100
200
300
400
Numero di coppie
500
600
Figura 4.3: Tempi di esecuzione per il calcolo di un singolo descrittore al variare del
numero di coppie selezionate, sia nel caso in cui l’intensità smussata venga calcolata
per tutti i punti dello schema di campionamento (linea rossa), sia nel caso in cui venga
calcolata solamente per i punti effettivamente utilizzati (linea blu).
viene eseguita la funzione per il calcolo dell’intensità smussata, altrimenti viene
semplicemente incrementato il puntatore.
Anche in questo caso sono stati acquisiti i tempi di esecuzione al variare del
numero di coppie utilizzate. In Figura 4.3 (linea blu) è possibile osservare i risultati relativi al tempo di esecuzione necessario per ricavare un singolo descrittore.
Come per il caso precedente sono state prese in considerazione tre diverse risoluzioni e le coppie utilizzate per la creazione dell’insieme S sono state generate
casualmente. Anche in questo grafico possiamo osservare i tempi di esecuzione
crescere all’aumentare del numero di coppie utilizzate. Tuttavia, possiamo notare
che quando il numero di coppie è basso, i tempi per il calcolo del descrittore si
63
CAPITOLO 4. IMPLEMENTAZIONE E RISULTATI
1.6
1.5
Speedup
1.4
1.3
1.2
1.1
1
0.9
0
100
200
300
400
Numero di coppie
500
600
Figura 4.4: Speedup ottenuto (al variare del numero di coppie) con l’ottimizzazione
del calcolo dell’intensità smussata solo per i punti utilizzati, rispetto al calcolo per tutti
i punti dello schema di campionamento.
riducono drasticamente. Questo si verifica poiché, quando le coppie considerate
sono poco numerose, anche i punti dello schema di campionamento utilizzati risultano conseguentemente pochi, limitando così il numero di esecuzioni necessarie
della funzione per il calcolo delle intensità smussate. In particolare, se il numero di
coppie considerate è minore di 150, il miglioramento che si può osservare è molto
significativo e influisce positivamente sulle prestazioni. Nella Figura 4.4 possiamo
osservare lo speedup che si ottiene.
64
CAPITOLO 4. IMPLEMENTAZIONE E RISULTATI
4.4
Conversione delle funzioni di ridimensionamento dell’immagine
Per quanto riguarda la conversione delle funzioni di ridimensionamento, l’obiettivo è quello di cercare di riprodurre fedelmente, tramite la tecnologia NEON,
l’implementazione originale fatta con le istruzioni SSE. Si è cercato quindi di seguire la stessa struttura dell’algoritmo degli autori, avvalendosi dei registri per
eseguire le stesse operazioni in parallelo sui vari elementi. Per utilizzare l’insieme
di istruzioni NEON è possibile sia seguire la via della programmazione in ARM
Assembly, sia usufruire dell’alternativa chiamata intrinsics. Le funzioni intrinsics permettono di incorporare facilmente operazioni specifiche di un determinato
dominio in porzioni di codice C o C++, senza la necessità di implementazioni
complesse. Una funzione intrinsics appare come una chiamata di funzione in C o
C++, ma durante la compilazione viene sostituita da una sequenza specifica di
istruzioni a basso livello. Il compilatore è in grado di generare automaticamente
la combinazione migliore di istruzioni per la specifica architettura utilizzata [31].
Ad esempio, la funzione di addizione saturata tra due interi in istruzioni intrinsics
assume la seguente forma:
1
2
3
int a, b, result;
...
result = L_add(a, b);
Il compilatore effettua poi la sostituzione con la seguente istruzione a basso livello:
1
QADD r0, r0, r1 /* Assumendo r0 = a, r1 = b */
Tramite queste funzioni è quindi possibile realizzare istruzioni ARM Assembly
direttamente dal codice C o C++. Abbiamo quindi scelto di utilizzare questa
alternativa, realizzando la conversione da SSE direttamente all’interno del codice
C++ di BRISK, sia per ragioni di comodità, sia perché l’implementazione originale utilizza anch’essa istruzioni intrinsics (per architetture intel).
Per lo svolgimento delle funzioni di analisi visuale svolte da BRISK, ogni immagine assume la forma di una matrice di pixel. Le funzioni di ridimensionamento
65
CAPITOLO 4. IMPLEMENTAZIONE E RISULTATI
dell’immagine agiscono quindi su questa matrice. In particolare, per quanto riguarda la funzione di dimezzamento dell’immagine, vengono effettuate operazioni
in parallelo per il calcolo del valore medio tra vari pixel. I risultati vengono poi
memorizzati in una matrice che avrà dimensioni corrispondenti alla metà della
grandezza della matrice di partenza. Anche il ridimensionamento di 2/3 prevede
una struttura simile, ma richiede anche operazioni più complesse, come interpolazioni o salvataggi condizionati in memoria.
Per alcune delle istruzioni SSE esiste una controparte NEON che è strutturata
esattamente nello stesso modo e svolge la medesima funzione. In questi casi la
conversione si è rivelata un’operazione semplice. Prendiamo ad esempio il caso
dell’operazione di load di un dato dalla memoria e caricamento in un registro.
Nella versione SSE assume la seguente forma:
1
2
3
__m128i* p1=(__m128i*)srcimg.data;
__m128i upper;
upper=_mm_load_si128(p1);
La stessa procedura svolta con istruzioni NEON prevede una struttura del tutto
simile:
1
2
3
int32_t* p1=(int32_t*)srcimg.data;
int32x4_t upper;
upper=vld1q_s32(p1);
In altri casi tuttavia la conversione non risulta così lineare. Molte delle istruzioni
SSE infatti non possiedono una versione equivalente in NEON, e si rende quindi necessario riprodurle tramite una combinazione di istruzioni diverse. Vediamo come
esempio il caso del salvataggio condizionato in memoria. La seguente operazione
SSE salva in memoria alla posizione dest1 il contenuto del vettore resultUpper,
sulla base dei bit significativi di ciascun byte del selettore storeMask:
1
_mm_maskmoveu_si128(resultUpper, storeMask, (char*)dest1);
Per eseguire questa stessa procedura in NEON sono necessarie operazioni differenti:
1
uint8x16_t tmp_dest1 = vld1q_u8((uint8_t*)dest1);
66
CAPITOLO 4. IMPLEMENTAZIONE E RISULTATI
1.55
1.5
VGA
SVGA
XGA
Speedup(Detection)
1.45
1.4
1.35
1.3
1.25
1.2
1.15
1.1
60
70
80
90
Soglia
100
110
120
Figura 4.5: Speedup ottenuto con le nuove funzioni di ridimensionamento rispetto
alla fase di detection originale, al variare della soglia per la fase di detection, per tre
diverse risoluzioni dell’immagine.
2
3
vbslq_u8(tmp_dest1,resultUpper,storeMask);
vst1q_u8((uint8_t*)dest1,tmp_dest1);
In questo caso viene creato un registro temporaneo che viene utilizzato per effettuare l’operazione bit a bit di inserimento condizionato vbslq; successivamente il
risultato ottenuto viene salvato in memoria nella posizione iniziale.
Una volta effettuata la conversione completa, è necessario verificare che le nuove
funzioni abbiano lo stesso comportamento di quelle originali e producano quindi
gli stessi risultati. Per effettuare questo controllo abbiamo effettuato un confronto
bit a bit delle matrici risultato prodotte.
Nel grafico in Figura 4.5 è possibile osservare lo speedup che si ottiene nella fase
67
CAPITOLO 4. IMPLEMENTAZIONE E RISULTATI
di detection applicando le funzioni di ridimensionamento con istruzioni NEON,
rispetto alla versione originale che prevede l’utilizzo di funzioni C (per l’esecuzione
su architetture ARM). Anche in questo caso sono state prese in considerazione tre
diverse risoluzioni e la soglia per la fase di detection è stata fatta variare tra 60
e 120. Ciò che si osserva è innanzitutto che il miglioramento è tanto maggiore
quanto più la risoluzione è alta. Questo deriva dal fatto che risoluzioni elevate
implicano immagini di dimensioni maggiori; di conseguenza la fase di ridimensionamento comporta un carico computazionale molto rilevante durante la detection.
Per questa ragione il miglioramento di queste funzioni influisce notevolmente sullo
speedup della procedura di detection. In secondo luogo, dal grafico si può vedere
che lo speedup acquista un peso maggiore al crescere della soglia. La motivazione
è che per soglie basse, il numero di keypoint individuati risulta molto alto, e di
conseguenza la funzioni di ridimensionamento hanno un impatto relativamente
basso sul tempo di esecuzione totale. Al contrario, per soglie alte, la fase di detection individua un numero ridotto di keypoint, dando così una rilevanza maggiore
alle procedure in questione. In conclusione, la conversione da istruzioni SSE a
istruzioni NEON permette di ottenere un significativo aumento delle prestazioni,
favorendo il risparmio energetico.
4.5
Rimozione di operazioni di interpolazione
Per l’implementazione di questa ottimizzazione è necessario modificare la parte di
codice della fase di detection relativa dell’estrazione dei keypoint dell’immagine.
In particolare, viene fatto uso di due funzioni, chiamate getScoreMaxAbove() e
getScoreMaxBelow(), che si occupano di ricavare il punteggio massimo locale nei
due strati immediatamente superiore e inferiore della piramide delle scale. Le due
funzioni agiscono in due passi: inizialmente controllano tutti i punteggi dei pixel
nella zona considerata e trovano il valore massimo; in seguito perfezionano il dato
su questo valore tramite un’operazione di interpolazione. Al fine di implementare
68
CAPITOLO 4. IMPLEMENTAZIONE E RISULTATI
1
originale
modificato
0.9
0.8
0.7
MAP
0.6
0.5
0.4
0.3
0.2
0.1
0
40
45
50
55
60
Soglia
65
70
75
80
Figura 4.6: Accuratezza dell’algoritmo BRISK nella versione originale e nella versione modificata rimuovendo l’operazione di interpolazione. Le misure di accuratezza
(MAP) sono state calcolate al variare della soglia. Le immagini utilizzate sono quelle
appartenenti al dataset ZuBuD
la modifica desiderata è quindi sufficiente rimuovere questa seconda fase in cui
il valore del punteggio massimo viene interpolato. Nella Figura 4.6 vengono mostrate le curve di accuratezza ottenute in corrispondenza della versione originale
e di quella modificata. E’ stata fatta variare ancora una volta la soglia e sono
stati calcolati i valori di misura dell’accuratezza (MAP). I dati sono stati ricavati
a partire dall’analisi delle immagini presenti nel dataset ZuBuD ed è stato utilizzato il controllo di consistenza geometrica RANSAC. Dai risultati ottenuti si vede
che la differenza in accuratezza nei due casi è pressoché trascurabile. L’algoritmo
modificato risulta anzi leggermente più accurato dell’originale (nel range di valori
di soglia preso in considerazione). E’ tuttavia necessario analizzare ora i risultati
69
CAPITOLO 4. IMPLEMENTAZIONE E RISULTATI
legati ai tempi di esecuzione per poter esprimere un giudizio completo. La Figura 4.7 mostra lo speedup che si ottiene sul tempo di esecuzione della procedura
di detection dopo aver rimosso l’operazione di interpolazione. Si può notare che
vi è un miglioramento tanto più grande quanto più la soglia è bassa. Un tale
comportamento è dovuto al fatto che soglie besse implicano vincoli poco stringenti per l’individuazione dei keypoint, e le due funzioni getScoreMaxAbove() e
getScoreMaxBelow() vengono eseguite molte volte. Sulla base di questi risultati
si può quindi concludere che, dal punto di vista dei tempi di esecuzione, anche
questa modifica contribuisce ad aumentare le prestazioni.
Un esito di questo tipo conferma quindi la validità dell’ottimizzazione in que-
1.16
VGA
SVGA
XGA
1.14
Speedup
1.12
1.1
1.08
1.06
1.04
1.02
40
50
60
70
80
Soglia
90
100
110
120
Figura 4.7: Speedup ottenuto sulla fase di detection rispetto all’implementazione
originale, rimuovendo l’operazione di interpolazione, al variare della soglia e per tre
diverse risoluzioni dell’immagine.
70
CAPITOLO 4. IMPLEMENTAZIONE E RISULTATI
1.6
1.55
VGA
SVGA
XGA
1.5
Speedup
1.45
1.4
1.35
1.3
1.25
60
70
80
90
Soglia
100
110
120
Figura 4.8: Speedup ottenuto rispetto all’implementazione originale grazie al contributo di entrambe le ottimizzazioni per la fase di detection: ridimensionamento dell’immagine e rimozione dell’operazione di interpolazione. Sono state prese in considerazione
tre risoluzioni ed è stata fatta variare la soglia.
stione, che rende possibile un miglioramento considerevole della fase di detection.
Nella Figura 4.8 possiamo invece osservare lo speedup che si ottiene per le tre
risoluzioni grazie al contributo di entrambe le ottimizzazioni relative alla fase di
detection (rimozione dell’interpolazione e conversione delle funzioni di ridimensionamento). Possiamo notare che lo speedup cresce all’aumentare della soglia,
indicando che l’ottimizzazione sul ridimensionamento è quindi quella che influisce
maggiormente. Se prendiamo ad esempio in considerazione la risoluzione VGA,
vediamo che lo speedup parte da un valore di 1.25 per soglie basse fino ad arrivare
a 1.45 quando la soglia è 120.
71
CAPITOLO 4. IMPLEMENTAZIONE E RISULTATI
4.6
Esecuzione in parallelo del test binario
Anche per l’esecuzione in parallelo del test binario abbiamo scelto di utilizzare
le istruzioni intrinsics per comodità di implementazione. La versione originale di
BRISK esegue il test binario sfruttando un vettore ausiliario di 60 elementi che
contiene i valori di intensità smussata di ciascun punto dello schema di campionamento. Vengono poi iterate tutte le coppie, prendendo in considerazione i valori
di intensità nelle posizioni del vettore i cui indici corrispondono ai punti da confrontare. Per eseguire il test binario in parallelo è tuttavia necessario modificare
questa struttura. Il vettore ausiliario originale viene sostituito da due vettori che
contengono, nelle posizioni corrispondenti, i valori di intensità che devono essere
confrontati. Questa scelta è inevitabile per un efficiente caricamento dalla memoria ai registri. Una volta effettuata questa fase preliminare è possibile iniziare la
computazione in parallelo. I registri vengono riempiti con i valori delle intensità
presenti in memoria, come mostrato nell’esempio seguente:
1
q8=vld1q_u32(p1);
Vengono poi confrontati a due a due tramite l’istruzione vcgtq, che inizializza
a 0 o a 1 tutti i bit dell’elemento corrispondente del registro destinazione, sulla
base dell’esito del confronto. Vediamo un esempio di come vengono effettuati 16
diversi confronti utilizzando 4 istruzioni:
1
2
3
4
q8=vcgtq_u32(q8, q9);
q9=vcgtq_u32(q10, q11);
q10=vcgtq_u32(q12, q13);
q11=vcgtq_u32(q14, q15);
E’ possibile organizzare il codice in cicli da 32 confronti (utilizzando quindi 8 registri). Dopo alcune operazioni di shifting e riordinamento di registri, si arriva
ad ottenere un elemento composto da 32 bit che costituirà parte del vettore di
descrizione. Ognuno dei bit rappresenta infatti il risultato di un confronto tra i
valori delle intensità smussate.
La comparazione del tempo di esecuzione del codice originale e di quello modifi72
CAPITOLO 4. IMPLEMENTAZIONE E RISULTATI
cato mostra però che il risparmio ottenuto implementando questa ottimizzazione
è minimo. Il motivo è da ricercarsi nel fatto che la creazione iniziale dei vettori ausiliari contenenti i valori delle intensità è piuttosto onerosa e non permette
di ottenere il guadagno sperato. Inoltre, la computazione del test binario richiede un tempo di esecuzione particolarmente basso in relazione all’intera fase di
description, rendendo sostanzialmente invisibile questo miglioramento. In conclusione, questa modifica sfortunatamente non permette di osservare un incremento
significativo delle prestazioni.
4.6.1
Rimozione dell’invarianza alla rotazione quando non
necessaria
L’implementazione originale di BRISK permette di rimuovere in maniera semplice la procedura che si occupa di ottenere l’invarianza alla rotazione. E’ infatti
sufficiente modificare il valore di una variabile booleana per disabilitare questa
funzione. Abbiamo quindi acquisito i tempi di esecuzione relativi all’analisi di
quattro diverse immagini senza invarianza alla rotazione. Nella Figura 4.9 possiamo osservare lo speedup che si ottiene per la fase di description rispetto alla
versione originale, sommando i contributi di quest’ultima ottimizzazione e di quella mostrata nella Sezione 4.3. Sono stati acquisiti i valori per 16, 32, 64,128, 256 e
512 coppie. Si osserva che lo speedup è tanto maggiore quanto minore è il numero
di coppie utilizzate. La curva del grafico mostra un andamento simile a quella in
Figura 4.4; in questo caso però la rimozione della procedura di invarianza alla rotazione contribuisce ad aumentare ulteriormente lo speedup. Possiamo vedere che
anche per un numero di coppie piuttosto alto (attorno a 300) il miglioramento che
si ottiene è notevole. Siccome nella versione originale i calcoli relativi all’invarianza alla rotazione vengono effettuati per ciascuna delle feature, il miglioramento che
si ottiene è proporzionale al numero di keypoint rilevati. In conclusione, per tutte
quelle applicazioni che non necessitano dell’invarianza alla rotazione, è possibile
ottenere un incremento delle prestazioni molto significativo.
73
CAPITOLO 4. IMPLEMENTAZIONE E RISULTATI
3.5
Speedup(Description)
3
2.5
2
1.5
1
0
100
200
300
400
Numero di coppie
500
600
Figura 4.9: Speedup ottenuto nella fase di description grazie al contributo delle due
ottimizzazioni di calcolo dell’intensità smussata solo per i punti utilizzati e di rimozione
dell’operazione relativa all’ottenimento dell’invarianza alla rotazione. La curva si basa
sui valori acquisiti a partire dall’analisi di 2 immagini del dataset ZuBuD e 2 appartenenti
al dataset Oxford
74
Capitolo 5
Comprimi-poi-analizza vs
Analizza-poi-comprimi
Le ottimizzazioni presentate finora hanno lo scopo di favorire l’adozione del nuovo
paradigma analizza-poi-comprimi (ATC) in sostituzione del tradizionale comprimipoi-analizza (CTA). La Figura 5.1 mostra il funzionamento dei due paradigmi. Nel
caso CTA le immagini vengono acquisite tramite i nodi della rete provvisti di fotocamera, vengono compresse e quindi inviate al nodo centrale per l’analisi. Nel caso
ATC invece, il nodo di acquisizione si occupa di estrarre direttamente le feature
dall’immagine, per poi codificarle e inviarle al nodo centrale, dove verrà eseguita
la fase di riconoscimento. In questo capitolo vengono confrontati i due paradigmi
sul piano energetico, stimandone i consumi sulla base dei tempi di esecuzione. In
particolare viene analizzato il comportamento sia della versione originale di BRISK sia di quella ottimizzata, nell’ipotesi di un’esecuzione secondo il paradigma
ATC; vengono poi confrontati questi risultati con il caso CTA, in cui l’immagine
acquisita viene compressa tramite la codifica JPEG. Tutti i tempi presi in esame
si riferiscono all’esecuzione sul dispositivo Beaglebone (Sezione 3.1).
5.1
Confronto rate-energia
Per entrambi i casi in analisi, l’energia necessaria per eseguire le funzionalità
richieste sul nodo della rete è data dal contributo dell’energia spesa dal processore
75
CAPITOLO 5. COMPRIMI-POI-ANALIZZA VS
ANALIZZA-POI-COMPRIMI
(a) CTA
(b) ATC
Figura 5.1: Funzionamento dei due paradigmi comprimi-poi-analizza (a) e analizzapoi-comprimi (b).
per l’acquisizione e l’analisi dei dati, sommato al contributo dell’energia spesa per
l’invio dei dati al nodo centrale. Come abbiamo visto nella Sezione 3.2, possiamo
assumere che l’energia consumata dal processore per l’esecuzione di algoritmi sia
dipendente dal tempo stesso di esecuzione. Per quanto riguarda il caso CTA, se
consideriamo la potenza dissipata dal processore Pcpu e il tempo di esecuzione
necessario per codificare l’immagine tcpu (ρ), l’energia può quendi essere espressa
come:
ECT A (ρ) = Ecpu (ρ) + Etx (ρ)
(5.1)
dove ρ rappresenta il bitrate, Etx è l’energia spesa per la trasmissione, e Ecpu (ρ) =
Pcpu · tcpu (ρ) è l’energia spesa dal processore. La Figura 5.2 mostra i tempi di
esecuzione rilevati per la codifica JPEG.
76
CAPITOLO 5. COMPRIMI-POI-ANALIZZA VS
ANALIZZA-POI-COMPRIMI
0.034
0.032
Tempo [s]
0.03
0.028
0.026
0.024
0.022
0
10
20
30
40
50
Rate [kB]
Figura 5.2: Tempi di esecuzione necessari per la codifica JPEG al variare del rate. E’
stato utulizzato il dataset ZuBuD.
Il caso del paradigma ATC richiede invece una stima dell’energia più complessa.
Prendiamo in considerazione separatamente i tempi della fase di detection e di
description BRISK. La Figura 5.3 mostra che il tempo della fase di detection
dipende dal numero M di keypoint individuati, e può quindi essere espresso come:
tdet (M ) = τof f + M τdet .
(5.2)
τdet è il coefficiente angolare della retta, e rappresenta quindi il tempo necessario
per la detection di un keypoint. τof f è invece un offset che si riferisce al tempo
necessario per l’inizializzazione della piramide dello scale-space.
E’ possibile fare un ragionamento simile anche per la fase di description (Figura
5.4). Tuttavia, supponendo di lavorare secondo il modello rate-accuratezza mo77
CAPITOLO 5. COMPRIMI-POI-ANALIZZA VS
ANALIZZA-POI-COMPRIMI
0.22
0.2
0.18
Tempo [s]
0.16
0.14
0.12
0.1
0.08
0.06
0
100
200
300
400
500
Num keypoint
600
700
800
900
Figura 5.3: Tempi di esecuzione necessari per la fase di detection al variare del numero
di keypoint. E’ stato utilizzato il dataset ZuBuD.
strato nella Sezione 2.3.2, il tempo di esecuzione dipende in questo caso dalla
dimensione ottimale dei descrittori utilizzati. Il grafico della Figura 5.4 mostra i
risultati ottenuti utilizzando descrittori di 512 bit. Abbiamo rilevato i tempi di
esecuzione anche per dimensioni minori dei descrittori. Si osserva che al diminuire della grandezza, i tempi possono essere modellati come rette con coefficienti
angolari τdesc sempre più piccoli. La dimensione dei descrittori dipende dal rate
ρ. Il modello rate-accuratezza infatti, tramite il calcolo dell’allocazione interna,
ricava il numero ottimale di keypoint M (ρ) che devono essere utilizzati ad un
determinato rate. Di conseguenza la dimensione ottimale D dei descrittori può
essere ricavata come:
D(ρ) =
ρ
,
M (ρ)
78
(5.3)
CAPITOLO 5. COMPRIMI-POI-ANALIZZA VS
ANALIZZA-POI-COMPRIMI
0.7
0.6
Tempo [s]
0.5
0.4
0.3
0.2
0.1
0
0
100
200
300
400
500
Num keypoint
600
700
800
900
Figura 5.4: Tempi di esecuzione necessari per la fase di description al variare del
numero di keypoint. E’ stato utilizzato il dataset ZuBuD.
ed è possibile esprimere il tempo di descrizione come:
tdesc (ρ) = M (ρ)τdesc (ρ),
(5.4)
in cui τdesc (ρ) è il tempo necessario per la descrizione di una feature, dipendente
dalla dimensione D e quindi dal rate ρ. A questo punto è possibile ricavare
le stime dell’energia necessaria in entrambe le fasi. Per la detection i consumi
saranno quindi pari a:
Edet (ρ) = Pcpu · [τof f + M (ρ)τdet ] .
(5.5)
L’energia necessaria per la fase di description dipende invece anche dalla dimensione dei descrittori, e quindi:
Edesc (ρ) = Pcpu · M (ρ)τdesc (ρ).
79
(5.6)
CAPITOLO 5. COMPRIMI-POI-ANALIZZA VS
ANALIZZA-POI-COMPRIMI
La Figura 5.5 mostra i consumi derivanti dalla descrizione di una singola feature, al variare della dimensione dei descrittori. Più i descrittori sono piccoli,
minore è l’energia necessaria. In conclusione, possiamo esprimere il valore totale
dell’energia consumata con il paradigma ATC come:
(5.7)
EAT C (ρ) = Pcpu · [τof f + M (ρ)(τdet + τdesc (ρ))] + Etx (ρ)
−3
1.8
x 10
1.6
1.4
Energia [J]
1.2
1
0.8
0.6
0.4
ottimizzato con invarianza rotazione
ottimizzato senza invarianza rotazione
originale
0.2
0
0
100
200
300
400
Dimensione descrittore [bit]
500
600
Figura 5.5: Energia necessaria per la descrizione di una feature al variare della dimensione dei descrittori, nel caso originale (rosso), ottimizzato con invarianza alla rotazione
(blu) e ottimizzato senza invarianza alla rotazione(verde).
80
CAPITOLO 5. COMPRIMI-POI-ANALIZZA VS
ANALIZZA-POI-COMPRIMI
5.2
Risultati
Grazie all’allocazione interna, come visto nella Sezione 2.3.2, è quindi possibile
ricavare il numero ottimale di keypoint da utilizzare al variare del rate. Sulla base
di questo calcolo e dei tempi di esecuzione acquisiti per i dataset ZuBuD e Oxford
abbiamo ottenuto i risultati esposti di seguito. Per effettuare la stima dei consumi
energetici sono stati utilizzati i valori seguenti:
• Pcpu = 2.1 [W]
• Etx = 2.6 × 10−6 [J/bit]
20
CTA
ATC BRISK originale
ATC BRISK ottimizzato
ATC BRISK ottimizzato no invarianza rotazione
18
16
Energia [J]
14
12
10
8
6
4
2
0
0
5
10
15
20
Rate [kB]
25
30
35
40
Figura 5.6: Confronto energetico tra il paradigma CTA e ATC basato sia sulla versione
originale di BRISK sia su quelle ottimizzate (con e senza invarianza alla rotazione). I
risultati si riferiscono ad un analisi effettuata sul dataset ZuBuD.
81
CAPITOLO 5. COMPRIMI-POI-ANALIZZA VS
ANALIZZA-POI-COMPRIMI
25
CTA
ATC BRISK originale
ATC BRISK ottimizzato
ATC BRISK ottimizzato no invarianza rotazione
Energia [J]
20
15
10
5
0
0
20
40
60
80
100
Rate [kB]
Figura 5.7: Confronto energetico tra il paradigma CTA e ATC basato sia sulla versione
originale di BRISK sia su quelle ottimizzate (con e senza invarianza alla rotazione). I
risultati si riferiscono ad un analisi effettuata sul dataset Oxford.
Le figure 5.6 e 5.7 mostrano i risultati del confronto tra il paradigma CTA e il paradigma ATC, ottenuti analizzando immagini dei dataset ZuBuD e Oxford. Come
si può vedere, e come è stato già osservato in altri lavori [32], il paradigma CTA
(linea rossa) richiede in generale un’energia minore rispetto al paradigma ATC
basato sull’esecuzione della versione originale di BRISK (linea verde). Tuttavia i
risultati mostrano anche che per bassi bitrate la scelta del paradigma ATC si rivela
non solo la migliore, ma anche l’unica che può essere utilizzata. L’implementazione delle ottimizzazioni di BRISK permette inoltre di ridurre in modo significativo
i consumi energetici derivanti dall’utilizzo del paradigma ATC (linea blu). Nel
caso non ci fosse la necessità di invarianza alla rotazione si riuscirebbe ad ottenere
82
CAPITOLO 5. COMPRIMI-POI-ANALIZZA VS
ANALIZZA-POI-COMPRIMI
un risparmio ancora più grande, avvicinandosi molto ai consumi del paradigma
CTA (linea nera). Le figure 5.8 e 5.9 mostrano il guadagno in energetico termini
percentuali della versione ottimizzata di BRISK (con e senza invarianza alla rotazione) rispetto a quella originale.
Da questi risultati si può quindi concludere che allo stato attuale, e per quanto riguarda il dispositivo Beaglebone, il paradigma CTA risulta energeticamente
più efficiente. Grazie alle migliorie apportate all’algoritmo di BRISK è tuttavia
possibile ridurre il divario tra ATC e CTA. Esiste la possibilità che future ottimizzazioni hardware o software permettano di colmare completamente questo divario,
100
100
90
90
80
80
70
70
Guadagno [%]
Guadagno [%]
rendendo il paradigma ATC il più efficiente.
60
50
40
60
50
40
30
30
20
20
10
10
0
0
5
10
15
20
Rate [kB]
25
30
35
0
40
(a) Con invarianza alla rotazione
0
5
10
15
20
Rate [kB]
25
30
35
40
(b) Senza invarianza alla rotazione
Figura 5.8: Guadagno energetico in termini percentuali della versione ottimizzata di
BRISK rispetto all’originale. Il dataset utilizzato è ZuBuD.
5.3
Codifica Entropica
Nella Sezione 2.4.1 abbiamo visto come sia possibile codificare un descrittore (di
dimensione D) con un numero di bit R ≤ D. Per alleggerire ulteriormente il
paradigma ATC, si può pensare di codificare entropicamente i descrittori binari
ottenuti con BRISK prima di inviarli al nodo centrale. Nel caso in cui l’energia
spesa per effettuare la codifica fosse trascurabile, si potrebbero ridurre i consumi
83
100
100
90
90
80
80
70
70
Guadagno [%]
Guadagno [%]
CAPITOLO 5. COMPRIMI-POI-ANALIZZA VS
ANALIZZA-POI-COMPRIMI
60
50
40
60
50
40
30
30
20
20
10
10
0
0
20
40
60
80
0
100
0
20
40
Rate [kB]
60
80
100
Rate [kB]
(a) Con invarianza alla rotazione
(b) Senza invarianza alla rotazione
Figura 5.9: Guadagno energetico in termini percentuali della versione ottimizzata di
BRISK rispetto all’originale. Il dataset utilizzato è Oxford.
dovuti all’invio dei descrittori, in quanto dipendenti dalla loro dimensione.
Tuttavia, alcuni test effettuati misurando i tempi di esecuzione relativi alla
codifica hanno mostrato che non si ottiene il risparmio energetico sperato. I
risultati, mostrati nella tabella 5.1, mostrano infatti che l’energia spesa per
effettuare la codifica entropica risulta maggiore di quella che si risparmierebbe
nell’invio.
Tabella 5.1: Dati relativi all’energia consumata per effettuare la codifica entropica
DIMENSIONE
DESCRITTORE
[bit]
GUADAGNO
TEMPO
CODIFICA
[ms]
ENERGIA
CODIFICA [mJ]
ENERGIA
RECUPERATA
[mJ]
NETTO [mJ]
16
32
64
128
256
512
8%
9%
11 %
15 %
21 %
29 %
0.0372
0.0670
0.1267
0.2461
0.4811
0.9477
0.08
0.14
0.27
0.52
1.01
1.99
0.003
0.008
0.019
0.053
0.148
0.411
-0.077
-0.132
-0.25
-0.47
-0.86
-1.58
84
Capitolo 6
Conclusioni e direzioni di lavoro
future
Per lo sviluppo delle Visual Sensor Networks è necessario ottenere prestazioni
ottimali in termini di efficienza, permettendo ai nodi della rete alimentati da
batteria di consumare meno energia possibile. Il progetto Greeneyes si muove in
questa direzione, proponendo un cambiamento rispetto al modello tradizionale e
prevedendo la possibilità per i nodi della rete di eseguire direttamente i compiti
di analisi visuale. Questa tesi vuole contribuire all’ottenimento degli obiettivi che
il progetto si prefigge. In particolare, sono stati presentati alcuni miglioramenti
per l’algoritmo di estrazione di feature BRISK, ed è stato effettuato un confronto
sul piano energetico tra i paradigmi comprimi-poi-analizza (CTA) e analizza-poicomprimi (ATC).
In primo luogo, abbiamo fornito una panoramica dei principali algoritmi di estrazione delle feature allo stato dell’arte, partendo da quelli classici come SIFT, fino
ad arrivare ad algoritmi più recenti (BRISK) e caratterizzati da un’efficienza maggiore. Questo ci è servito per comprendere il funzionamento di tali algoritmi ed
essere poi in grado di analizzarli allo scopo di implementare delle ottimizzazioni.
Abbiamo poi esposto le principali tecniche di riconoscimento di immagini e come
è possibile misurarne l’accuratezza. Ci siamo quindi concentrati sui metodi di
codifica dei descrittori binari, utili per comprendere il funzionamento di BRISK.
85
CAPITOLO 6. CONCLUSIONI E DIREZIONI DI LAVORO FUTURE
E’ stato inoltre illustrato un modello rate-accuratezza, che permette di effettuare l’estrazione di feature in condizioni ottimali, contribuendo ad un’esecuzione
efficiente.
Nella parte successiva ci siamo occupati di esporre quali sono le ottimizzazioni
pensate per BRISK. Per fare questo abbiamo prima analizzato la struttura dell’algoritmo, determinando quali sono le parti più onerose. Abbiamo poi visto come
è possibile implementare dei miglioramenti nell’ottica di una maggiore efficienza
computazionale.
Nel seguito sono stati illustrati i risultati ottenuti dopo l’implementazione delle
ottimizzazioni e dopo averle testate sul dispositivo Beaglebone. E’ risultato che
quasi tutte le migliorie corrispondono ad una diminuzione dei tempi di esecuzione,
contribuendo così ad un incremento delle prestazioni.
Nell’ultima parte è stato effettuato il confronto sul piano energetico dei due paradigmi CTA e ATC. Grazie ad una stima effettuata sulla base dei tempi di
esecuzione, si è mostrato che il paradigma CTA risulta ancora quello più efficiente
per bitrate elevati, mentre nel caso di una bassa disponibilità di banda ATC si
rivela la soluzione migliore. Inoltre, le migliorie apportate all’algoritmo di BRISK
permettono di avvicinare in modo significativo le prestazioni di CTA, riducendo
l’energia necessaria per l’esecuzione. Questa riduzione del divario tra i due paradigmi può rappresentare un punto di partenza per ulteriori ottimizzazioni future
a favore della soluzione ATC. Bisogna infatti tenere in considerazione che le ottimizzazioni sono state testate solamente sul dispositivo Beaglebone. Inoltre il
paradigma CTA si basa sull’utilizzo della codifica JPEG, il cui algoritmo è il risultato di più di 20 anni di ottimizzazioni; al contrario gli algoritmi utilizzati nella
modalità ATC sono molto recenti e ben lontani dall’avere prestazioni ottimali in
termini di consumi energetici.
Le misure di potenza, e quindi quelle dei consumi energetici, sono state ricavate
a partire da alcune stime. Esse sono utili per dare un’idea generale del compor-
86
CAPITOLO 6. CONCLUSIONI E DIREZIONI DI LAVORO FUTURE
tamento dei due paradigmi ma non possono ritenersi totalmente accurate. Una
prima direzione di lavoro è quindi quella che prevede la misura diretta dei consumi
dei due paradigmi tramite uno strumento adatto, come può essere l’oscilloscopio.
In questo modo sarebbe possibile conoscere il comportamento esatto della Beaglebone in termini di potenza e ricavare dei valori accurati.
Siccome questa tesi è basata sull’utilizzo del dispositivo Beaglebone, un altro possibile sviluppo può essere la ripetizione degli stessi test su altri dispositivi con le
stesse caratteristiche. E’ inoltre possibile che in futuro vengano prodotti nuovi
computer con le stesse funzionalità ma molto più efficienti in termini di consumi
energetici, favorendo così l’applicazione del paradigma ATC. Inoltre la Beaglebone è stata utilizzata con un sistema operativo Ubuntu Linux per esigenze legate
alla comunicazione di rete. E’ stato brevemente osservato tuttavia che i tempi
di esecuzione sono differenti se si utilizza la distribuzione di Linux Ångström. Si
potrebbe quindi ripetere il lavoro su questo sistema operativo, maggiormente ottimizzato per dispositivi come la Beaglebone, e verificare se è possibile un ulteriore
incremento delle prestazioni.
Infine, possibili lavori futuri consistono nello sviluppo di nuovi algoritmi di estrazione di feature, strettamente mirati all’efficienza energetica. Si sta già lavorando
in questa direzione attraverso delle ricerche sui cosiddetti Application Specific Integrated Circuits (ASIC), capaci di individuare ed estrarre feature con consumi
bassissimi.
I miglioramenti che possono essere fatti in termini di efficienza sono quindi ancora
molti, nell’ottica di un passaggio dal paradigma comprimi-poi-analizza a quello
analizza-poi-comprimi.
87
Bibliografia
[1] Lambros Sarakis, Theodore Zahariadis, Helen-Catherine Leligou, and Mischa
Dohler. A framework for service provisioning in virtual sensor networks.
EURASIP J. Wireless Comm. and Networking, 2012:135, 2012.
[2] J.A. Stankovic. Wireless sensor networks. Computer, 41(10):92–95, 2008.
[3] G. Lu, B. Krishnamachari, and C.S. Raghavendra. Performance evaluation of
the ieee 802.15.4 mac for low-rate low-power wireless networks. In Performance, Computing, and Communications, 2004 IEEE International Conference
on, pages 701–706, 2004.
[4] Yeong-Hyun Kwon and Dong-Ryeol Shin. The security monitoring system
using ieee 802.15.4 protocol and cmos image sensor. In New Trends in Information and Service Science, 2009. NISS ’09. International Conference on,
pages 1197–1202, 2009.
[5] P. Chen, P. Ahammad, C. Boyer, Shih-I Huang, Leon Lin, E. Lobaton,
M. Meingast, Songhwai Oh, S. Wang, Posu Yan, A.Y. Yang, Chuohao Yeo,
Lung-Chung Chang, J. D. Tygar, and S.S. Sastry. Citric: A low-bandwidth
wireless camera network platform. In Distributed Smart Cameras, 2008.
ICDSC 2008. Second ACM/IEEE International Conference on, pages 1–10,
2008.
[6] Y. Charfi, N. Wakamiya, and M. Murata. Challenging issues in visual sensor
networks. Wireless Communications, IEEE, 16(2):44–49, 2009.
88
BIBLIOGRAFIA
[7] Bulent Tavli, Kemal Bicakci, Ruken Zilan, and JoseM. Barcelo-Ordinas. A
survey of visual sensor network platforms. Multimedia Tools and Applications,
60(3):689–726, 2012.
[8] Jayavardhana Gubbi, Rajkumar Buyya, Slaven Marusic, and Marimuthu Palaniswami. Internet of things (iot): A vision, architectural elements, and
future directions. CoRR, abs/1207.0203, 2012.
[9] M. Zorzi, A. Gluhak, S. Lange, and A. Bassi. From today’s intranet of things
to a future internet of things: a wireless- and mobility-related view. Wireless
Communications, IEEE, 17(6):44–51, 2010.
[10] Gerald Coley. Beaglebone rev a6 system reference manual. Computer, 2012.
[11] S. Leutenegger, M. Chli, and R.Y. Siegwart. Brisk: Binary robust invariant
scalable keypoints. In Computer Vision (ICCV), 2011 IEEE International
Conference on, pages 2548–2555, 2011.
[12] A. Canclini, M. Cesana, M.Tagliasacchi A.Redondi, J. Ascenso, and R. Cilla.
Evaluation of low-complexity visual feature detectors and descriptors. 2013.
[13] David G. Lowe. Object recognition from local scale-invariant features. In
Proceedings of the International Conference on Computer Vision-Volume 2
- Volume 2, ICCV ’99, pages 1150–, Washington, DC, USA, 1999. IEEE
Computer Society.
[14] Tony Lindeberg. Scale-space theory: A basic tool for analysing structures at
different scales. Journal of Applied Statistics, pages 224–270, 1994.
[15] Krystian Mikolajczyk. Detection of local features invariant to affines transformations. PhD thesis, Institut National Polytechnique de Grenoble, July
2002.
89
BIBLIOGRAFIA
[16] David G. Lowe. Distinctive image features from scale-invariant keypoints.
Int. J. Comput. Vision, 60(2):91–110, November 2004.
[17] Herbert Bay, Tinne Tuytelaars, and Luc Gool. Surf: Speeded up robust
features. In Aleš Leonardis, Horst Bischof, and Axel Pinz, editors, Computer
Vision – ECCV 2006, volume 3951 of Lecture Notes in Computer Science,
pages 404–417. Springer Berlin Heidelberg, 2006.
[18] Tony Lindeberg.
Feature detection with automatic scale selection.
International Journal of Computer Vision, 30:79–116, 1998.
[19] Edward Rosten, R. Porter, and Tom Drummond. Faster and better: A machine learning approach to corner detection. Pattern Analysis and Machine
Intelligence, IEEE Transactions on, 32(1):105–119, 2010.
[20] Elmar Mair, GregoryD. Hager, Darius Burschka, Michael Suppa, and Gerhard Hirzinger. Adaptive and generic corner detection based on the accelerated segment test. In Kostas Daniilidis, Petros Maragos, and Nikos Paragios, editors, Computer Vision – ECCV 2010, volume 6312 of Lecture Notes
in Computer Science, pages 183–196. Springer Berlin Heidelberg, 2010.
[21] Michael Calonder, Vincent Lepetit, Mustafa Özuysal, Tomasz Trzcinski,
Christoph Strecha, and Pascal Fua.
Brief: Computing a local binary
descriptor very fast.
[22] Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu. An optimal algorithm for approximate nearest neighbor searching
fixed dimensions. J. ACM, 45(6):891–923, November 1998.
[23] Simon A. J. Winder, Gang Hua, and Matthew Brown. Picking the best daisy.
In CVPR, pages 178–185. IEEE, 2009.
90
BIBLIOGRAFIA
[24] Martin A. Fischler and Robert C. Bolles. Random sample consensus: a
paradigm for model fitting with applications to image analysis and automated
cartography. Commun. ACM, 24(6):381–395, June 1981.
[25] James Philbin, Ondrej Chum, Michael Isard, Josef Sivic, and Andrew Zisserman.
Object retrieval with large vocabularies and fast spatial mat-
ching. In Computer Vision and Pattern Recognition, 2007. CVPR’07. IEEE
Conference on, pages 1–8. IEEE, 2007.
[26] E. Rublee, V. Rabaud, K. Konolige, and G. Bradski. Orb: An efficient alternative to sift or surf. In Computer Vision (ICCV), 2011 IEEE International
Conference on, pages 2564–2571, 2011.
[27] Alexandre Alahi, Raphaël Ortiz, and Pierre Vandergheynst. FREAK: Fast
Retina Keypoint. In IEEE Conference on Computer Vision and Pattern
Recognition, IEEE Conference on Computer Vision and Pattern Recognition,
New York, 2012. Ieee. CVPR 2012 Open Source Award Winner.
[28] A. Redondi, M. Cesana, and M. Tagliasacchi. Rate-accuracy optimization of
binary descriptors. In IEEE International Conference on Image Processing,
September 2013.
[29] M. Brown, Gang Hua, and S. Winder. Discriminative learning of local image
descriptors. Pattern Analysis and Machine Intelligence, IEEE Transactions
on, 33(1):43–57, 2011.
[30] Redondi Alessandro, Matteo Cesana, Marco Tagliasacchi, Joao Ascenso, and
Luca Baroffio. Rate-accuracy optimization in visual wireless sensor networks.
ICIP, page 1105–1108, 2012.
[31] Realview compilation tools. 2010.
[32] Alessandro Redondi. Energy-aware visual analysis for wireless multimedia
sensor networks. PhD thesis, Politecnico di Milano, 2013.
91