ANALISI E OTTIMIZZAZIONE DELLE
PRESTAZIONI DI UNA WIRELESS VISUAL
SENSOR NETWORK
Tesi di Laurea in Ingegneria Informatica
Autore:
Angelo BORGHETTI
Matr.
783692
Relatore:
Ing. Matteo Cesana
Correlatore:
Ing. Alessandro Redondi
Le Wireless Visual Sensor Network sono un campo in veloce e continuo sviluppo, ed in futuro, in svariati ambiti della società, saranno sempre più presenti nella vita quotidiana. Queste reti, costituite da un numero svariato di sensori, sono in grado, con dei nodi-fotocamera, di catturare delle immagini e, attraverso que-ste, di effettuare complesse operazioni di analisi visuale, come l’identificazione di oggetti, persone o eventi. Il modello convenzionalmente usato prevede che le immagini vengano catturate, compresse e poi trasmesse sulla rete al nodo cen-trale che si occupa di elaborarle per effettuare le operazioni di riconoscimento (paradigma che prende il nome di ”Compress-Then-Analyze”). Il progetto Gree-nEyes, coordinato dal Politecnico di Milano, si prefigge lo scopo di capovolgere questo paradigma e di spostare parte dell’elaborazione dell’immagine sui sensori. Questi catturano le immagini, estraggono le ”visual feature” (i punti significativi) e le inviano attraverso la rete al nodo principale (modello che è stato chiamato ”Analyze-Then-Compress”). In questo modo non vengono trasmesse le immagi-ni, ma una loro rappresentazione concisa. Il principale problema delle WVSN è quello del consumo energetico, per questo è necessario ottimizzare al meglio le funzioni eseguite. All’interno di quest’ottica si inserisce questa tesi, che cercherà di affrontare quello che è il problema dell’ottimizzazione della trasmissione dei dati usando la tecnologia Wi-Fi. La tesi si propone di trovare un comportamen-to ottimo che i sensori possano praticare al variare della qualità del canale su cui avviene la trasmissione, utilizzando alternativamente il paradigma Analyze-Then-Compress o quello Compress-Then-Analyze e il protocollo di trasmissione
Abstract 1
Elenco delle figure 6
Elenco delle tabelle 9
1 Introduzione 10
1.1 GreenEyes . . . 11
1.2 Motivazione ed esposizione del problema . . . 12
2 Background e stato dell’arte 15 2.1 Wireless Visual Sensor Networks . . . 15
2.1.1 User Data Protocol . . . 15
2.1.2 Transmission Control Protocol . . . 17
2.1.3 Confronto delle performance . . . 18
2.2 Local Visual Features . . . 19
2.2.1 Scale Invariant Feature Transform . . . 19
2.2.2 Binary Robust Invariant Scalable Keypoints . . . 21
2.2.3 Confronto delle performance . . . 22
2.3 Riconoscimento di oggetti . . . 23
2.4 Misura dell’accuratezza . . . 23
2.5 Compress-then-analyze e analyze-then-compress . . . 24
3.1 Piattaforma di riferimento: BeagleBoard . . . 29
3.2 Modello di rete . . . 32
3.2.1 CTA: ”Compress-Then-Analyze” . . . 32
3.2.2 CTA con UDP . . . 34
3.2.3 CTA con TCP . . . 37
3.2.4 Differenze in CTA tra UDP e TCP . . . 39
3.2.5 ATC: ”Analyze-Then-Compress” . . . 40
3.2.6 ATC con UDP . . . 42
3.2.7 ATC con TCP . . . 43
3.2.8 Differenze in ATC tra UDP e TCP . . . 43
3.3 NeTeM . . . 46
4 Valutazione delle prestazioni 47 4.0.1 Dataset . . . 47
4.1 Compress-Then-Analyze . . . 48
4.1.1 CTA-UDP: Numero di blocchi ottimo . . . 48
4.1.2 Perdita di accuratezza all’aumento del numero di blocchi . 52 4.1.3 CTA-UDP: accuratezza ottima . . . 55
4.1.4 CTA-UDP: ritardo ottimo . . . 57
4.1.5 CTA-TCP . . . 58
4.1.6 CTA: Confronto UDP TCP . . . 61
4.2 Analyze-Then-Compress . . . 62
4.2.1 ATC-UDP . . . 63
4.2.2 ATC-TCP . . . 65
4.2.3 ATC: confronto UDP TCP . . . 66
4.4.2 Condizione 2% perdita di pacchetti . . . 76
4.4.3 Condizione 5% perdita di pacchetti . . . 77
4.4.4 Condizione 10% perdita di pacchetti . . . 78
4.5 Analisi conclusiva e tabella riassuntiva dei risultati . . . 79 5 Conclusioni e sviluppi futuri 81
1.1 Struttura sintetica di una Rete di Sensori Wireless . . . 10
1.2 GreenEyes . . . 12
2.1 Modello TCP/IP UDP/IP . . . 16
2.2 UDP Header Format . . . 16
2.3 TCP Header Format . . . 18
2.4 Esempio di matching di features . . . 23
2.5 CTA . . . 25
2.6 ATC . . . 27
3.1 Beaglebone . . . 30
3.2 Diagramma a blocchi del sistema . . . 31
3.3 Edimax 7811Un . . . 31
3.4 Diagramma a blocchi del modello di trasmissione CTA UDP . . . 36
3.5 Diagramma a blocchi del modello di trasmissione CTA TCP . . . 38
3.6 Diagramma a blocchi del modello di trasmissione ATC UDP . . . 44
3.7 Diagramma a blocchi del modello di trasmissione ATC TCP . . . 45
4.1 ZuBuD . . . 48
4.2 Rapporto tra numero di blocchi e dimensione . . . 49
4.3 Ritardo e numero di blocchi al variare della qualità del canale . . 49
4.4 Accuratezza e numero di blocchi al variare della qualità del canale 50 4.5 Ritardo e accuratezza per numero di blocchi e qualità del canale con 20 di ”quality factor’ . . . 51
4.7 Esempio di aumento dei keypoint aumentando il numero blocchi . 53 4.8 Aumento del numero di keypoint di noise all’aumentare dei blocchi 54
4.9 CTA: UDP accuratezza ottima, dimensione-ritardo . . . 55
4.10 CTA: UDP accuratezza ottima, accuratezza-ritardo . . . 56
4.11 CTA: UDP accuratezza ottima, accuratezza-dimensione . . . 57
4.12 CTA: UDP ritardo ottimo, accuratezza-ritardo . . . 58
4.13 CTA: TCP, dimensione-ritardo . . . 59
4.14 CTA: TCP, accuratezza-dimensione . . . 59
4.15 CTA: TCP, accuratezza-ritardo . . . 60
4.16 CTA: UDP vs TCP, dimensione-ritardo . . . 61
4.17 CTA: UDP vs TCP, accuratezza-ritardo . . . 62
4.18 ATC: UDP, dimensione-ritardo . . . 63
4.19 ATC: UDP, accuratezza-ritardo . . . 64
4.20 ATC: TCP, dimensione-ritardo . . . 65
4.21 ATC: TCP, accuratezza-ritardo . . . 66
4.22 ATC: UDP vs TCP, dimensione-ritardo . . . 67
4.23 ATC: UDP vs TCP, accuratezza-ritardo . . . 67
4.24 Accuratezza senza perdita di pacchetti al variare del threshold . . 69
4.25 Ritardo per numero di keypoint, con 60 threshold . . . 70
4.26 Ritardo per numero di keypoint, con 90 threshold . . . 70
4.27 Accuratezza per numero di keypoint, con 60 threshold . . . 72
4.28 Accuratezza per numero di keypoint, con 90 threshold . . . 72
4.29 Ritardo-Accuratezza per numero di keypoint e qualità del canale . 73 4.30 ATC vs CTA 0% perdita pacchetti . . . 75
4.31 ATC vs CTA 2% perdita pacchetti . . . 76
3.1 Componenti della Beaglebone . . . 30 4.1 Tabella riassuntiva . . . 80
Introduzione
Le Wireless Sensor Networks sono delle reti costituite da sensori indipendenti che sono in grado di monitorare individualmente le condizioni esterne e in modo coo-perativo di far fluire i dati dalla rete a un gateway principale. Queste reti possono essere costituite da pochi sensori fino ad alcune centinaia. Le reti di sensori wi-reless (WSN) sono un campo emergente che si sta mostrando utile in numerose applicazioni di monitoraggio e controllo. Troviamo applicazioni in campo militare, dal monitoraggio delle forze alleate, equipaggiamenti e munizioni, alla sorveglian-za del campo di battaglia, in campo ambientale, con il monitoraggio della qualità dell’acqua o dell’aria, nel riconoscimento di possibili incendi o movimenti del ter-reno che possono preannunciare possibili frane, nell’agricoltura di precisione, con il controllo in tempo reale dell’umidità e della temperatura delle coltivazioni, in campo medico, con il monitoraggio della salute dei pazienti a casa o in ospedale,
in campo industriale e nelle Smart home. Fattori importanti all’interno di una WSN sono il consumo di potenza per nodo, fornita dalle batterie, la scalabilità, ovvero la capacità di accettare l’ingresso nella rete di nuovi nodi, la tolleranza ai guasti ed il costo. L’integrazione nelle reti di sensori di tecnologie di ”low-power wireless networking”, reti a basso consumo di energia, e fotocamere poco costose, ha permesso la costruzione di quelle che vengono chiamate “Wireless Multimedia Sensor Network” (WMSN), conosciute anche come “Wireless Visual Sensor Net-work” (WVSN). Le WVSN possono essere pensate come reti di dispositivi wireless in grado di catturare contenuti multimediali, come immagini, video, audio, map-pe, etc. Grazie alla loro flessibilità e basso costo le WVSN hanno ottenuto un grande successo negli ultimi anni, con applicazioni nell’ambito del riconoscimen-to di oggetti, individuazione, locazione e tracciamenriconoscimen-to di eventi. All’interno di questo contesto tecnologico si inserisce il progetto europeo di GreenEyes.
1.1
GreenEyes
Il progetto ”GreenEyes: Networked energy-aware visual analysis”, coordinato dal Politecnico di Milano, si sviluppa nell’ottica di lungo termine per cui in un pros-simo futuro i sensori saranno in grado, oltre che di catturare dati, di effettuare operazioni di complessa analisi visuale. GreenEyes si propone di sviluppare un in-sieme di metodologie, algoritmi e protocolli per potenziare le reti di sensori visuali per renderle comparabili con sistemi di fotocamere. Di conseguenza, vincolati dal-la necessità di mantenere i consumi il più bassi possibile, l’imperativo è quello di ottimizzare la computazione, la codifica e la trasmissione dei dati. GreenEyes pro-pone di sostituire il paradigma convenzionale di Compress-Then-Analyze (CTA) con quello di Analyze-Then-Compress (ATC). L’approccio tradizionale nell’analisi visuale prevede infatti che le immagini, o sequenze di immagini, vengano campio-nate in formato digitale e quindi, una volta compresse, vengano inviate attraverso la rete ad un gateway principale per l’analisi. Il nuovo approccio invece prevede
Figura 1.2: GreenEyes
di spostare la computazione in parte o interamente sui sensori. Un gran numero di ricerche si sono concentrate sull’analisi di dati visuali per realizzare operazioni molto complesse, come il riconoscimento di lettere, volti, oggetti, eventi etc. Par-te di quesPar-te operazioni possono essere svolPar-te direttamenPar-te sul sensore, tuttavia in genere si tratta di operazioni molto costose, caratterizzate da un consumo signifi-cativo di potenza. Allo stesso tempo la trasmissione di dati non elaborati, ovvero immagini o parti di immagini, risulta molto inefficiente sia in termini computa-zionali sia in termini di risorse di rete usate, in particolar modo quando l’analisi si basa su dati raccolti da più di una camera. Di conseguenza è necessario uno studio per comprendere e definire quali siano i comportamenti migliori in termini energetici.
1.2
Motivazione ed esposizione del problema
Fatte queste premesse per inquadrare l’ambito entro il quale si svilupperà que-sta tesi, ci soffermiamo più attentamente su quelli che sono gli obbiettivi specifici. L’obiettivo della tesi è quello di trovare un ”modus operandi” che i nodi di una rete di sensori visuali possano utilizzare come guida per ottenere le prestazioni migliori nella trasmissione dei dati utilizzando la tecnologia Wi-fi, IEEE 802.11. I sensori possono infatti modificare il loro comportamento utilizzando diversi protocolli e
diversi paradigmi di trasmissione, possono utilizzare una trasmissione veloce, ma senza controllo di ricezione (protocollo UDP) oppure più lenta, ma con la sicurezza che tutti i dati vengano ricevuti lato ricevitore (protocollo TCP) e possono deci-dere di utilizzare alternativamente il paradigma ATC (Analyze-Then-Compress) oppure quello CTA (Compress-Then-Analyze). Abbiamo quindi strutturato di-versi casi di test per verificare le prestazioni delle 4 configurazioni possibili: ATC con UDP, ATC con TCP, CTA con UDP e CTA con TCP, e abbiamo analizzato i risultati per capire quale configurazione ottenga prestazioni migliori nel rapporto accuratezza del riconoscimento e tempo di trasmissione al variare delle condizioni di disturbo del canale. I due parametri fondamentali della ricerca su cui basare il confronto tra le varie configurazioni sono quindi l’accuratezza con la quale il nostro sistema, partendo dai dati estratti dall’immagine, effettua il riconoscimen-to dell’oggetriconoscimen-to e il tempo col quale il nostro sistema è in grado di effettuare la trasmissione di un insieme di dati. L’accuratezza come indice di qualità dell’in-formazione e il tempo come indicatore della velocità di invio e ricezione dei dati e del consumo di potenza nel nodo. Ottenuti quindi questi dati è possibili definire un comportamento ottimo che i nodi possono utilizzare, al variare delle condizioni del canale su cui avviene la trasmissione ed alla soglia di accuratezza e ritardo considerata accettabile dal sistema.
Nel dettaglio, nel Capito 2 andremo a riportare quello che è lo stato dell’arte, il ”background” tecnologico entro il quale si muove la tesi, dapprima le tecnologie di trasmissione dei dati, UDP e TCP, poi le tecnologie di identificazione delle feature, SIFT e BRISK, quindi le tecniche per il riconoscimento degli oggetti e di verifica dell’accuratezza dell’identificazione, ed infine i due paradigmi usati nella tesi, CTA e ATC. Quindi nel Capitolo 3 verranno presentati i dispositivi hardware utilizzati, la Beaglebone e la chiavetta Wi-Fi, le scelte per costruire il sistema di test, quindi la struttura client-server nelle varie configurazioni ATC-CTA, UDP-TCP, ed infine il tool che ha permesso di simulare una rete con interferenze sul
canale. Nel Capitolo 4 verranno presentati i test ed i risultati ottenuti, quindi nel Capitolo 5 verranno tratte le conclusioni e presentati possibili sviluppi futuri.
Background e stato dell’arte
In questo capitolo affronteremo un’analisi dettagliata di quelle che sono le tecno-logie dello ”stato dell’arte” usabili nella trasmissione dei dati sulla rete Wi-Fi e nell’analisi visuale.
2.1
Wireless Visual Sensor Networks
Come abbiamo accennato nell’introduzione, le reti di sensori visuali wireless (WV-SN) sono delle reti composte da uno svariato numero di sensori di cui alcuni, di tipo visuale (fotocamere), raccolgono dati e tramite un antenna li inviano direttamente (nodo-gateway) oppure indirettamente (multi-hop, in cui le informazioni passa-no da un sensore all’altro prima di arrivare a destinazione)[1][2]. Le trasmissioni possono essere effettuate con svariati protocolli di trasporto, ci concentreremo su quelli utilizzati in questa tesi, ovvero UDP/IP e TCP/IP.
2.1.1
User Data Protocol
Il protocollo UDP è stato ideato nel 1980 da David P. Reed e poi formalmente definito nel RFC768[3]. Questo protocollo è stato definito per rendere disponibi-le una modalità di trasmissione di pacchetti all’interno di una rete di computer connessi tra loro. E’ un protocollo di livello tre (transport layer), presuppone che a livello due (internet layer) venga utilizzato il protocollo IP. [4][5] e fornisce al
Figura 2.1: Modello TCP/IP UDP/IP
livello applicativo una procedura per trasmettere messaggi ad altri programmi. Il protocollo è di tipo transaction-oriented, ovvero si concentra sulla comunicazione tra una sorgente e un destinatario, e non esiste nessuna garanzia sulla consegna o non duplicazione dei messaggi trasmessi. L’header è molto semplice e costituito da soli 64 bit (8 byte), la SourceP ort è un campo opzionale e specifica la porta sorgente del messaggio, DestinationP ort è la porta destinazione, Lenght la lun-ghezza dei dati più l’header, e il checksum è il complemento a uno della somma
dei complementi a uno dello pseudo header delle informazioni ottenute dall’header IP, dall’header UDP e dai dati, completato con zeri (se necessario) per renderlo di 16 bit. Questo campo viene usato per verificare eventuali errori nell’header o nei dati. Viene calcolato dal dispositivo trasmittente e inserito nel header, poi viene di nuovo calcolato dal ricevitore e se i due valori non sono uguali il pacchetto viene scartato in quanto corrotto.
2.1.2
Transmission Control Protocol
Il protocollo TCP è stato per la prima volta descritto nella pubblicazione ”A Pro-tocol for Packet Network Intercommunication.” pubblicato dal IEEE nel 1974 da Vint Cerf e Bob Kahn[6]. Viene poi definito nel RFC 793[7] e su di esso si ap-poggiano gran parte delle applicazioni internet. E’ un protocollo di trasmissione a pacchetti che si appoggia su IP[4][5] e permette di inviare e ricevere segmenti di informazione di lunghezza variabile racchiusi in una ”busta” IP. A livello IP ven-gono specificate informazioni sull’indirizzo sorgente e destinatario, inoltre viene specificato il livello di precedenza, di sicurezza e di accesso al pacchetto TCP. Il protocollo TCP è stato ideato con l’intenzione di fornire un servizio di comuni-cazione processo-a-processo in un ambiente multi-rete. TCP, dopo aver stabilito una connessione, è capace di trasferire uno stream continuo di byte in ciascuna di-rezione tra i suoi utenti, sotto forma di pacchetti. In generale TCP decide quando bloccare o scartare informazioni in base alla convenienza. TCP inoltre garantisce di poter recuperare dati danneggiati, persi, duplicati o consegnati fuori ordine. Questo viene assicurato assegnando a ciascun pacchetto trasmesso un numero in sequenza e richiedendo in risposta a ciascun pacchetto inviato un pacchetto di conferma della ”correttezza della ricezione”, chiamato ACK (Acknowledgment). Lato ricevitore la numerazione dei pacchetti permette di riordinarli e di eliminare possibili duplicati. Il checksum, come per UDP, permette di scartare eventua-li pacchetti danneggiati. TCP ha inoltre funzionaeventua-lità di controllo di flusso e di congestione.
Figura 2.3: TCP Header Format
L’header TCP è di 192 bits (24 byte).
2.1.3
Confronto delle performance
Le principali differenze tra i due protocolli sono:
• TCP è un protocollo orientato alla connessione, pertanto, per stabilirla, mantenerla e chiuderla, è necessario inviare pacchetti di servizio che aumen-tano l’overhead di comunicazione. UDP, al contrario, è senza connessione, invia solo i dati forniti dal livello applicativo;
• UDP non offre nessuna garanzia sull’affidabilità della comunicazione, ovvero sull’effettivo arrivo dei dati trasmessi e sul loro ordine, al contrario TCP tramite meccanismi di acknowledgment e di ritrasmissione su timeout riesce a garantire la consegna dei dati;
• l’oggetto della comunicazione TCP è un flusso di byte, uno stream, invece quello di UDP è un singolo datagramma;
In conclusione TCP è preferibile ad UDP se è necessario avere una garanzia sulla consegna dei dati o sull’ordine di arrivo dei pacchetti trasmessi. Al contrario si preferisce l’uso di UDP nel caso ci siano forti vincoli di velocità o di risorse, per esempio uno streaming video.
2.2
Local Visual Features
Una ”local visual feature” è un frammento caratteristico dell’immagine e può coin-cidere con una struttura particolare di pixel. Dei bordi, degli angoli, degli incroci a T oppure delle chiazze con una particolare forma possono essere considerati ottimi candidati per essere delle local feature in un’immagine. Nel tempo sono stati costruiti numerosi algoritmi per identificarli e questi algoritmi sono comu-nemente definiti detectors. Il concetto di local visual feature include quindi due parti: l’identificazione di una posizione e la sua rappresentazione. In generale viene utilizzata la parola keypoint per riferirsi ad una particolare posizione nel-l’immagine dove si trova la ”forma caratteristica”. Nella maggior parte dei casi i keypoint possono essere trovati non solo in differenti posizioni, ma anche a dif-ferenti grandezze, la scala con cui vengono identificate le feature non è fissa, ma variabile. Per ciascun keypoint la local feature corrispondente è rappresentata da una feature vector o descrittore, che codifica i pixel attorno al keypoint in un vettore numerico. Gli algoritmi per i descrittori sono generalmente progetta-ti affinché i loro risultaprogetta-ti siano robusprogetta-ti anche al variare delle immagine, cambio di punto di vista, zoom, rotazione o variazione di illuminazione. Nei sotto ca-pitoli successivi vedremo in dettaglio due differenti algoritmi di estrazione delle features. Iniziando da ”Scale Invariant Feature Transform” (SIFT)[8], considerato lo standard di riferimento, per poi passare a ”Binary Robust Invariant Scalable Keypoints” (BRISK)[9], algoritmo meno oneroso computazionalmente, che meglio si adatta ad un contesto di piattaforme con necessità di un basso consumo di potenza, com’è la rete di sensori visuali.
2.2.1
Scale Invariant Feature Transform
L’algoritmo di SIFT è stato proposto per la prima vola da David Lowe nel 1999[8][10] ed è tuttora considerato lo standard di riferimento nell’estrazione e analisi delle visual local features. E’ considerato un algoritmo capace di
estrar-re un gran numero di caratteristiche ben posizionate ed altamente distinguibili, che possono essere usate facilmente in fase di riconoscimento. SIFT consiste di quattro fasi principali:
• identificazione dei keypoint nello spazio in scala; • posizionamento dei keypoint;
• assegnamento di un orientamento; • definizione di un descrittore.
Nella prima fase l’immagine viene analizzata per posizione e scala cercando po-tenziali punti di interesse. Questa viene implementata efficientemente costruendo una Gaussian pyramid, si tratta di una tecnica molto usata nell’analisi delle im-magini e consiste nel creare una serie di imim-magini che sono pesate verso il basso usando una Gaussian Blur (Sfocatura Gaussiana). Quando questa tecnica è usa-ta più volte si crea una pila di immagini sempre più piccole, in cui ciascun pixel è la media di un corrispondente gruppo di pixel dell’immagine nel piano superio-re. Dopo aver creato la piramide di Gaussiane i keypoint vengono cercati nella serie di immagini ”difference-of-Gaussian” (DoG). Nella seconda fase viene iden-tificata la posizione dei punti chiave all’interno di un sistema di coordinate 2D, costituito dalla struttura a pixel della matrice che costituisce l’immagine. Nella terza fase, viene definito l’orientamento dominante per ciascun keypoint, basan-dosi sulla parte di immagine in cui si trova. L’assegnamento di un orientamento, di una scala e di una posizione permette a SIFT di costruire una vista canonica per ciascun keypoint che è invariante a trasformazioni di somiglianza. L’ultimo passo dell’algoritmo di SIFT è quello che porta alla rappresentazione di ciascun keypoint basandosi sul gruppo di pixel che si trovano attorno. Gruppo di pixel che è stato precedentemente centrato attorno al keypoint, ruotato in base all’orien-tamento dominante e rappresentato in una scala appropriata. L’obbiettivo ora è quello di creare un descrittore che sia compatto, altamente distinguibile e robusto
ai cambiamenti di vista e illuminazione. Il descrittore viene quindi creato cam-pionando la magnitudine e l’orientamento del gradiente della parte di immagine attorno al keypoint e costruito arrotondando gli istogrammi di gradienti orienta-ti per catturarne gli aspetorienta-ti peculiari. Un array 4x4 degli istogrammi, ciascuno con 8 orientamenti, cattura la struttura spaziale del blocco. Questo vettore di 128 elementi è quindi normalizzato e limitato per rimuovere elementi con valori piccoli.
2.2.2
Binary Robust Invariant Scalable Keypoints
Negli ultimi anni è emerso un nuovo tipo di algoritmo per il calcolo dei detectors e dei descriptors, progettato appositamente per architetture a basso consumo di potenza. L’attenzione principale si è focalizzata sul progetto di algoritmi che computazionalmente fossero molto meno costosi dei precedenti, pur mantenen-dosi molto performanti. Seguendo queste linee guida Leutenegger ha proposto il metodo BRISK nel 2011[9][11] . Con l’attenzione puntata sull’efficienza della computazione, il detector di BRISK è ispirato al popolare detector FAST(Fast Accelerated Segment Test). I punti di interesse sono identificati nelle immagini usando criteri di rilevanza. Il detector classifica un punto p (con intesità Ip) come
keypoint se n pixel contigui nel cerchio di Bresenham di raggio 3 attorno a p sono tutti più brillanti di Ip+ t, o tutti più scuri di Ip− t, con t una soglia predefinita
(threshold). A ciascun angolo viene attribuito un punteggio s, definito come la massima soglia per cui p è un keypoint. Il descrittore di BRISK usa un modello di punti pi per campionare la zona circostante a ciascun keypoint. Il modello
de-finisce due insiemi di coppie di punti di campionamento, chiamati abbinamenti a lunga-distanza e abbinamenti a breve-distanza. L’insieme a lunga-distanza è com-posto da tutte quelle coppie (i,j) tali che |pi− pj| > δmin e queste sono utilizzate
per calcolare l’orientamento dei keypoint facendo una media del gradiente locale. Una volta che l’orientamento è stato stimato, il modello di campionamento viene ruotato di conseguenza e, usando gli abbinamenti a breve-distanza (quelli in cui la
distanza del punto di campionamento è minore della soglia δmax), viene costruito
il descrittore. Per ciascun pi viene calcolata un’intensità con una Gaussian Blur
(o Gaussian Smoothing) con deviazione standard σi, proporzionale alla distanza
tra il punto e il centro. Per rendere maggiormente efficiente il modello di posi-zionamento dei punti e l’informazione di smoothing è possibile costruire off-line e memorizzare una tavola di ”look-up” con tutti i possibili orientamenti. Per co-struire il descrittore, viene creata una stringa binaria concatenando i risultati di tutti i confronti di intensità di breve-distanza tra coppie (pi,pj) tali che ciascun
bit b corrisponda a:
b = 1, I(pj, σj) > I(pi, σi)
0, otherwise (2.1)
dove I(pi, σi) denota il valore di intensità smussato di pi. Nell’implementazione
standard di BRISK, δmax è costruito affinché il descrittore sia di 512 bit.
2.2.3
Confronto delle performance
Riassumendo, SIFT è un algoritmo molto performante nell’accuratezza del rico-noscimento, necessita però di un’elevata capacità computazionale a causa delle complesse elaborazioni che deve effettuare e quindi mal si adatta all’utilizzo su dispositivi come i sensori delle WVSN dove l’imperativo è quello di ridurre il con-sumo di potenza. BRISK invece ha performance inferiori rispetto a SIFT, ma richiede un dispendio minore di potenza nel calcolo dei descrittori[12].
2.3
Riconoscimento di oggetti
Le features locali, keypoint e descrittori, sono usate come base per molte fun-zioni visuali. In particolar modo mostrano risultati eccellenti nelle funfun-zioni di riconoscimento, di oggetti, di paesaggi, di volti etc[13][8].
Tipicamente un sistema di riconoscimento ha questa struttura: un’immagi-ne vieun’immagi-ne data in input al sistema, può provenire da una fotocamera e contieun’immagi-ne l’oggetto da riconoscere, e viene processata con uno degli algoritmi di estrazione di feature (es.SIFT,BRISK). Il sistema di riconoscimento utilizza un database di immagini di riferimento (a ciascun immagine del database corrispondono featu-re pfeatu-recedentemente estratte) e cerca di identificafeatu-re quali di queste siano simili a quella di input. Per fare questo il sistema cerca quali immagini del database han-no più feature che corrispondohan-no con quelle dell’immagine in ingresso. A questo punto effettua un ordinamento dei risultati e restituisce l’immagine più simile o un numero definito di immagini simili.
Figura 2.4: Esempio di matching di features
2.4
Misura dell’accuratezza
Per valutare le performance di un sistema di riconoscimento uno dei metodi più utilizzati, che sarà usato anche nella tesi, è il Mean of Average Precision MAP. Data una query di immagini q, la Average Precision è definita come:
APq =
Pn
k=1Pq(k)rq(k)
Rq (2.2)
dove Pq(k)è la precisione considerando la top-k dei risultati nella lista ordinata
delle immagini del database, rq(k)è un funzione che è uguale a 1 se l’oggetto nella
posizione k è pertinente con la query, 0 altrimenti; Rq è il numero totale di oggetti
pertinenti con la query q e n è il numero totale di oggetti nella lista. Il Mean Average Precision (MAP) per un insieme Q di query è la media aritmetica dei singoli AP: M AP = PQ q=1APq Q (2.3)
2.5
Compress-then-analyze e analyze-then-compress
Dopo aver presentato quelli che sono i metodi di analisi delle immagini, invio dei dati e riconoscimento di un oggetto partendo dalle sue note caratteristiche (feature) possiamo effettuare un’analisi più approfondita dei due metodi ATC e CTA[14]. Entrambi contengono tre fasi distinte:
• cattura ed elaborazione dell’immagine sul dispositivo trasmittente; • trasmissione e ricezione dei dati;
• elaborazione dei dati e matching sul dispositivo ricevente;
2.5.1
CTA
Come abbiamo già detto più volte questo è il metodo standard che viene usato al momento nei sistemi di reti di sensori visuali wireless.
Le immagini o un video vengono ottenuti attraverso un sensore visuale, quindi avviene una fase di compressione JPEG in cui i dati vengono elaborati, l’immagine viene compressa e si passa da una matrice di pixel ad uno vettore di dati e sotto questa forma le informazioni vengono quindi inviate sulla rete tramite un’antenna.
I dati passano da un nodo all’altro e arrivano al gateway centrale, in genere un computer con alta capacità computazionale, che si occupa di ricostruire l’imma-gine e di estrarne le feature. Quindi, in ultimo, viene effettuato il confronto con le feature delle immagini presenti nel database per effettuare il riconoscimento. La caratteristica peculiare di questo metodo è il fatto che il carico delle opera-zioni più onerose viene affidato al sistema locale, al server. Qui viene effettuata l’estrazione delle feature senza vincoli di potenza spesa ed è quindi possibile usare gli algoritmi più performanti nell’accuratezza (come SIFT). Le performance della fase di trasmissione sono però legate alla quantità di byte che il sistema invia sulla rete. Questa quantità è legata alla grandezza del buffer uscente dalla funzione di compressione JPEG.
Figura 2.5: CTA
E’ necessario aprire quindi una parentesi per approfondire questa fase. Codifica e compressione JPEG
Per non trasmettere una quantità di byte pari a quella che costituisce l’immagine digitale, ovvero i byte che rappresentano la matrice nxm, in cui n è il numero di colonne e m il numero di righe di pixel di cui è composta, viene effettuata la compressione JPEG ( Joint P hotographic Experts Group)[15]. JPEG è uno standard che è stato definito da un gruppo di esperti nel 1991[16][17]. E’ un algoritmo che può portare ad una compressione significativa dell’immagine, ma è di tipo lossy ovvero c’è la possibilità di perdita di qualità dell’immagine. Si distinguono una serie di operazioni in sequenza:
• lettura del file sorgente: i dati letti dal file immagine, sono organizzati come tre matrici nello Spazio Colore RGB. Ogni matrice viene divisa in blocchi di dimensione 8x8, ovvero ogni blocco contiene 64 pixel dell’immagine ori-ginale. Se l’immagine non è multipla di 8, sono aggiunte delle copie della prima o dell’ultima colonna alla matrice dell’immagine originale affinchè la dimensione della nuova matrice sia multipla di 8;
• trasformazione spazio colore: l’immagine viene trasformata dallo Spazio del Colore RGB a quello Yuv;
• trasformata del coseno (DCT): ad ogni matrice divisa in blocchi di dimen-sione 8x8 è applicata la trasformata DCT bidimensionale che restituisce ancora un blocco di dimensione 8x8. Con la trasformata si passa da una rappresentazione nel dominio spaziale ad una nel dominio delle frequenze; • quantizzazione: questa è la prima operazione lossy dell’algoritmo. Dopo
aver ricevuto l’immagine (8x8) delle frequenze, l’algoritmo applica delle di-visioni e arrotondamenti per rendere i valori il più vicini a 0. In questa fase ogni elemento di ciascun blocco viene diviso per un coefficiente presente nel-la tabelnel-la di quantizzazione. L’effetto è quello di arrotondare i valori delnel-la DCT, portando a zero quelli vicini allo zero, smorzando le alte frequenze e arrotondando le basse frequenze. Più c’è approssimazione, maggiore è la perdita di dettaglio dell’immagine, ma minore sarà anche la dimensione del buffer ottenuto a fine compressione;
• codifica dell’immagine quantizzata: ”codifica DC”, la ”sequenza a zig-zag” e la ”codifica di Huffman”;
Di conseguenza nel momento della decodifica avremo immagini tanto più definite, quanto minore è stata la perdita di informazione nella compressione. Altresì, più la perdita di informazione è bassa, maggiore è la dimensione dei dati che si
devono inviare, nello specifico si parla di variazione del ”Quality Factor”.. Velocità di trasmissione si paga in accuratezza del riconoscimento.
2.5.2
ATC
ATC[14][18][19] è il protocollo alternativo a quello standard. Direttamente nel nodo sensore vengono catturate le immagini, vengono estratte le feature con BRI-SK e queste ultime vengono compresse con codifica entropica e serializzate. I dati vengono quindi inviati sulla rete e nel nodo centrale vengono decodificati. Qui avviene il confronto tra le feature dell’immagine e quelle delle immagini del database per il riconoscimento. Una delle peculiarità di questo metodo è il fatto
Figura 2.6: ATC
che il carico della parte di estrazione delle feature viene effettuata sul dispositivo remoto, che, come abbiamo ampiamente affermato, necessita di un forte control-lo delle risorse utilizzate. Di conseguenza non è possibile usare algoritmi molto dispendiosi come SIFT, ma si preferisce BRISK. Allo stesso tempo i dati inviati sulla rete non sono le immagini, ma dati già elaborati, le feature. La dimensione dei dati trasmessi sulla rete dipende dalla compressione entropica e dal numero di feature estratte da BRISK. Eseguendo BRISK è infatti possibile impostare un parametro chiamato threshold, soglia. Più il threshold sarà alto, minore sarà il numero di keypoint che il nostro sistema troverà all’interno dell’immagine, così da un lato avremo un numero minore di byte che il nostro sistema dovrà inviare, quindi un minor ritardo nella ricezione delle feature, dall’altro con meno punti significativi sarà però più difficile il riconoscimento dell’immagine, in quanto nella
fase di matching ci saranno meno punti da confrontare. Ora si può aprire una piccola parentesi per descrivere la codifica entropica utilizzata per comprimere i keypoint e i descrittori.
Codifica Entropica
I descrittori di BRISK sono costituiti da una stringa di D bit, ciascuno dei quali è il risultato di un confronto binario. Poiché i confronti binari non sono staticamente indipendenti è possibile costruire i descrittori come sorgenti binarie con memoria utilizzando un numero di bit R ≤ D. Considerando H(πn), n = 1, ..., D l’entropia
dell’ennesimo elemento del descrittore, che si può calcolare come
H(πn) = −pn(0)log2pn(0) − Pn(1)log2pn(1) (2.4)
In modo simile è possibile calcolare l’entropia condizionata H(πn1|πn2) che
si può ottenere analizzando un insieme campione di descrittori. Preso ˜πn, n =
1, ..., D permutazione delle coppie D, il limite inferiore è: R =
D
X
n=1
H(˜πn|˜πn−1, ..., ˜π1) (2.5)
Per ottimizzare l’efficienza del codice, è utile trovare la permutazione che mi-nimizza il limite inferiore. La strategia adottata in questo caso è di tipo greedy, assumendo che il descrittore può essere modellato come una sorgente di Markov del prim’ordine, i.e., H(˜πn|˜πn−1, ..., ˜π1) = H(˜πn|˜πn−1). Quindi il descrittore è
riordinato scegliendo gli elementi iterativamente. L’ennesimo elemento è scelto in modo tale da minimizzare l’entropia con l’elemento precedente
˜
πn= argminπnH(πn|˜πn−1) (2.6)
Dopo il riordinamento, ciascun descrittore è codificato usando una codifica aritmetica ”context-based”, dove ciascun bit è codificato in base al precedente.
Descrizione del Testbed
sperimentale
Dopo aver esaminato quelli che sono gli sviluppi tecnici e tecnologici dello stato dell’arte, ora andremo a vedere quelle che sono state le scelte hardware e software utilizzate nella tesi per implementare i protocolli e gli algoritmi teorici presentati nel capitolo precedente. Verranno mostrati i dispositivi utilizzati come sensori, le antenne, la struttura della rete di test, le soluzioni software utilizzate per sfruttare al meglio i protocolli e i tool utilizzati.
3.1
Piattaforma di riferimento: BeagleBoard
La BeagleBoard è un computer su singola scheda a basso consumo di potenza prodotto con hardware open-source fornito dalla Texas Instruments in associa-zione con la Digi-Key e la Newark element14. La Beaglebone è stata progettata per mantenere bassi i costi di vendita e di esercizio, pur offrendo prestazioni e connettività simili a quelli di un laptop.
Figura 3.1: Beaglebone
La BeagleBone si basa su un poten-te syspoten-tem-on-a-chip, l’OMAP3530, che offre prestazioni eccellenti grazie al mi-croprocessore superscalare ARM Cor-tez TM-A8 con coprocessore NEON RM SIMD e alle elevate performance audio-video garantite dal processore di segnale digitale e dal acceleratore gra-fico. Una caratteristica peculiare della BeaglBoard è il carattere open dell’in-tero progetto che lo rende un ottimo strumento a carattere educativo e di ricerca.
Nel dettaglio:
Tabella 3.1: Componenti della Beaglebone
Componente F eature
P rocessore AM3358/AM3359 500MHZ-USB Powered 720MHZ-DC Powered M emoria 256MB DDR2 400MHZ P M ICT P S65217B Power Regulators Alimentazione USB
5VDC External Jack Indicatori Power
4-User Controllable LEDs HD microSD Connector
Processore: Il dispositivo usa un processore AM3358 o AM3359 nel pac-chetto 15x15. La velocità è determinata dal tipo di alimentazione;
Memoria: E’ usato come dispositivo DDR2 x16 bit e la configurazione stan-dard è 256MB a 400MHz;
Alimentazione: L’alimentazione può essere fornita o tramite la porta USB, o tramite un cavo Jack a 5 Volt oppure tramite un’espansione con batterie;
Connettore MicroSD: Connettore singolo microSD che agisce da boot pri-mario. Una microSD da 4Gb è fornita con il dispositivo. Può supportare anche SD con capacità maggiore;
Il sistema operativo usato è Ubuntu e sono state utilizzate le librerie di Open-CV 2.4.9.
Figura 3.2: Diagramma a blocchi del sistema
Come dispositivo trasmittente è stato utilizzata una chiavetta wifi compatibile con la beaglebone, ovvero la chiavetta Edimaz 7811Un con chipset Realtek, usando i driver rtl8192cu realtek del 2012.
3.2
Modello di rete
Per effettuare i test si è deciso di strutturare la rete come un sistema client/server in cui il ruolo di sensore/client è svolto da un dispositivo di tipo beaglebone e il server/gateway è costituito da un computer. Sul client si trovano le immagini di test, queste vengono elaborate in maniera differente se ci troviamo nella configu-razione ATC o CTA e vengono inviate tramite una socket UDP o TCP. Il server, che è sempre in attesa di una connessione, riceve i dati, questi vengono salvati e successivamente elaborati per ottenere i valori di accuratezza per ciascuna query.
3.2.1
CTA: ”Compress-Then-Analyze”
Nel caso ”Compress-Then-Analyze” la prima operazione effettuata è l’apertura di una socket tra client e server. Quindi, sul client, le immagini della query vengono lette in un elemento di tipo Mat della libreria di OpenCV e viene eseguita una funzione di codifica chiamata ”imencode”. Questa funzione riceve una matrice di pixel (Mat) e restituisce un buffer di uchar che può essere inviato sulla socket. La ”imencode” effettua un processo di codifica e compressione JPEG (2.5.1). Nella codifica JPEG è possibile specificare un parametro tra 0 e 100, il quality factor, che indica la qualità con cui viene effettuata; più la qualità è bassa più sarà piccola la dimensione del buffer da inviare, ma minore sarà la definizione dell’immagine che verrà ricostruita lato server.
/* client CTA */
...
vector<int> p; p.push_back(1);
//quality factor tra 0 e 100
p.push_back(quality_factor);
if (imencode(".JPG", image, vector, p) == false) { printf("Error encoding image.\n"); }
...
Quindi il client invia un pacchetto iniziale verso il server per comunicare alcuni dati essenziali alla ricezione successiva. Infine viene mandato il buffer di uchar, che viene ricevuto dal server e decodificato con una funzione di OpenCV chiamata ”imdecode”. Operazione che è l’inverso della ”imencode” e, partendo da un buf-fer, attraverso una funzione di decodifica e decompressione, riottiene l’immagine iniziale in una matrice di tipo Mat. Ora che il server ha ricevuto l’immagine può effettuare la fase di ”detection” e ”description”. Poichè non esiste un vincolo di po-tenza spesa lato server, useremo SIFT (2.2.1) come protocollo di estrazione delle feature. Una volta estratte le feature viene calcolato l’AP della singola immagine e poi il MAP dell’intera query.
3.2.2
CTA con UDP
Testeremo quindi la differenza di prestazioni tra il protocollo UDP e TCP. UDP non necessita di stabilire una connessione, dopo la creazione della socket di tipo UDP è sufficiente usare una ”send” con contenute le informazioni da inviare.
/* Client UDP */
...
if ((sd = socket(AF_INET, SOCK_DGRAM, 0)) < 0) { perror("UDP Client - socket() error"); exit(-1);
} ...
send(sd, &buffer, sizeof(buffer), 0); ...
Nella configurazione che abbiamo utilizzato, UDP è strutturato in modo tale che ciascun pacchetto oltre la dimensione di 1512 byte, 1470 byte di dati, venga fram-mentato in sotto-pacchetti a livello IP. Quando un pacchetto a livello IP viene perso risulta impossibile ricostruire il pacchetto generale a livello UDP e questo provoca la perdita intera dei dati. Per far fronte a questo problema si è deciso di spezzare la trasmissione UDP in pacchetti più piccoli in modo da non avere una perdita totale delle informazioni, ma solo di parte di queste. Nel caso CTA si è deciso di dividere l’immagine in N × N blocchi, considerandola come una matrice, e di codificare e inviare ciascun blocco in modo indipendente. Questo fa sì che l’immagine arrivi divisa in singoli frammenti, ciascuno con un suo in-dice che ne rappresenta la posizione all’interno della matrice. Nel modello che abbiamo costruito è possibile specificare il valore di N ogni volta che si esegue il client. Quindi, divisa l’immagine in N × N blocchi, otteniamo che la dimensione del buffer da inviare può essere calcolata come:
dim =
N ×N
X
k=1
in cui Jpegk è il numero di byte risultante dalla codifica JPEG del cappesimo
blocco e H è l’header del pacchetto, nel nostro caso di 12 byte. L’header ha una maggiore incidenza tanto più è piccolo il pacchetto, se invece è molto grande diventa ininfluente.
L’immagine viene quindi ricostruita lato server decodificando ciascun pacchet-to ricevupacchet-to e posizionando il blocco nella posizione corretta. In caso di perdita l’immagine risulta come ”forata” in quanto al posto delle parti perse appaiono dei quadrati neri.
Prima dell’invio dei dati è necessaria la trasmissione di un pacchetto con conte-nute delle informazioni necessarie al server per la ricostruzione corretta dell’imma-gine. Questo pacchetto, come quello di fine invio dei dati, è un datagramma di cui si deve avere la certezza di arrivo a destinazione. Per garantire questo, si è deciso di imporre la risposta da parte del server con un ”ack” di conferma, se questa non viene ricevuta dal client il pacchetto viene rinviato dopo un determinato timeout. Il pacchetto iniziale è di 20 byte e contiene il tipo (iniziale=1,dati=2,finale=3), il numero di colonne dell’immagine, il numero di righe, il numero di blocchi in cui viene divisa e il valore di quality factor usato. Una volta ricevuto questo data-gramma iniziale il sistema può iniziare l’invio dei dati veri e propri. I pacchetti hanno una dimensione variabile, in base alla codifica JPEG, e hanno un header di 12 byte che contiene il tipo, l’indice e la dimensione dei dati. Gli altri datagram-mi di servizio hanno la dimensione di 4 byte. Finito l’invio la socket può essere chiusa.
3.2.3
CTA con TCP
Nel caso TCP, dopo aver creato la socket e aver posto il server in attesa, è necessa-rio effettuare una connect prima di ogni trasmissione, questa funzione, chiamata dal client, usa una three − wayhandshake, una connessione in tre passi. Il primo passo prevede un pacchetto di SYN (sincronizzazione) mandato dal client verso il server, settando il numero di sequenza del pacchetto ad un valore random A. Quindi, in risposta il server manda un SYN-ACK. Il numero del acknowledgment è settato a un valore A+1 e il valore che il server sceglie per il numero di sequenza del pacchetto è un altro valore random B. Nel terzo e ultimo passo, il client invia un ACK al server il cui valore di acknowledge è settato a A+1 e il numero del pacchetto a B+1. Tutto questo è nascosto al livello applicativo in quanto viene gestito automaticamente dal protocollo TCP.
/* Client TCP */
...
if ((sd = socket(AF_INET, SOCK_STREAM, 0)) < 0) { perror("TCP server - socket() error"); exit(-1);
} ...
connect(sd, (struct sockaddr *) &serveraddr, serveraddrlen); ...
send(sd,&buf,sizeof(buf),0); ...
Poiché per ciascun segmento inviato con il protocollo TCP si ha la certezza della corretta ricezione, grazie ai sistemi di numerazione, di acknowledgment e di rinvio (2.1.2), non è necessario dividere l’immagine in blocchi. L’immagine viene quindi inviata interamente senza effettuare scomposizioni. Questo permette di avere l’efficienza migliore del sistema di codifica e compressione JPEG che opera sulla figura intera e non su una parte di essa.
Prima di inviare il pacchetto coi dati, come in UDP, viene inviato un pacchetto con delle informazioni iniziali: il numero di righe e di colonne dell’immagine, il valore di quality factor dell’immagine e la dimensione dei dati. Non viene richiesta nessuna risposta dal server.
3.2.4
Differenze in CTA tra UDP e TCP
La differenza che si aggiunge alle caratteristiche peculiari già descritte di UDP e TCP(2.1.3), che sono da un lato la maggiore velocità di trasmissione dei dati in UDP rispetto a TCP e dall’altro la sicurezza della ricezione di tutte le infor-mazioni con TCP, cosa invece impossibile con UDP, è la divisione in blocchi. In TCP non abbiamo divisione in blocchi, quindi la codifica JPEG riesce ad opera-re sull’intera immagine e non su una parte di essa, quindi al massimo delle sue capacità. In UDP, per non avere la perdita completa dell’immagine ogni volta che si perde un pacchetto IP perché il canale è corrotto, si è deciso di dividere l’immagine. Operando su una parte dell’immagine la codifica perde gran parte della sua capacità di compressione e il numero di byte inviati risulta crescente all’aumentare del numero di blocchi. Partendo dalla formula (3.1) e considerando l’header trascurabile possiamo quindi scrivere che:
dim.udpN ×N < dim.udpM ×M
dove
N × N < M × M ⇒ N < M (3.2) con dim.udpy×y la dimensione del buffer ottenuta dividendo la matrice in y × y
blocchi. E che: dim.tcp = J pegni = N ×N =1 X k=1 J pegk= dim.udp1 (3.3)
ovvero che la dimensione del buffer inviato da TCP è uguale a quella del buffer utilizzato da UDP nel caso mandi l’immagine in un unico blocco. Quindi possiamo
concludere:
dim.tcp < dim.udpN ×N
con
N 6= 1 (3.4)
ovvero che la dimensione del buffer inviato da TCP è inferiore a quella di UDP in tutti i casi divida in blocchi diversi dal blocco unitario. Sarà quindi necessario in una fase preliminare definire un valore di blocchi ottimo in base ai risultati di accuratezza ed ai tempi di trasmissione dell’immagine al variare della qualità del canale. Dopo questa fase, utilizzando UDP con il numero di blocchi ottimo si dovrà verificare se le prestazioni di UDP sono comparabili con quelle di TCP nel piano accuratezza e ritardo al variare della qualità di compressione JPEG e al variare della qualità del segnale.
3.2.5
ATC: ”Analyze-Then-Compress”
Nel caso ”Analyze-Then-Compress” dopo aver creato la socket tra client e ser-ver, sul client vengono lette le immagini e caricate in una matrice Mat. Quindi viene usato BRISK (2.2.2) per estrarre le feature, vengono creati un detector, specificando il livello di threshold usato, e un extractor fornendogli le coppie pre-cedentemente salvate. Successivamente viene passata al detector la matrice che rappresenta l’immagine e da questa vengono estratti i keypoint, che sono in nume-ro maggiore, quanto minore è il threshold impostato, infine al extractor vengono passati i keypoint e la matrice, e questo restituisce la matrice dei descrittori.
/* Client ATC */ ... Ptr<FeatureDetector> detector; Ptr<DescriptorExtractor> extractor; ... int aux_pairs[BRISK_LENGTH_BITS]; ifstream fileRank; fileRank.open("thirdparty/coder/brisk/ranking_original_optimized512.bin", ios::in|ios::binary);
fileRank.read((char*)aux_pairs,sizeof(int)*BRISK_LENGTH_BITS); fileRank.close();
for(int i=0; i<BRISK_LENGTH_BITS; i++){ pairs.push_back(aux_pairs[i]); }
detector = new cv::BriskFeatureDetector(brisk_threshold,4); extractor = new cv::BriskDescriptorExtractor(pairs);
detecto->detect(matrix,keypoints);
extractor->compute(matrix,keypoints,descriptor); ...
Quindi il client invia un primo pacchetto contenente alcune informazioni iniziali e può poi dare inizio alla trasmissione dei dati, costituiti da keypoint e descriptor serializzati e codificati con codifica entropica (2.5.2).
/* Client ATC */
...
vector<uchar> desc_bitstream;
encoder.encodeBinaryDescriptors("BRISK", descriptor, descriptor_bitstream);
vector<uchar> keypoint_bitstream;
encoder.encodeKeyPoints(keypoint,keypoint_bitstream, matrix.columns,matrix.rows);
Il server riceve i dati, li decomprime ed effettua il matching con le feature estratte dal database con BRISK ad un threshold di 40, per ottenere il valore di AP dell’immagine e poi il MAP della query.
3.2.6
ATC con UDP
Inizialmente viene aperta la socket UDP, quindi viene letta l’immagine, vengono estratti i keypoint e costruita la matrice dei descrittori. Ora, per la stessa ragione descritta nella sezione 3.2.2, ovvero per non perdere l’intera serie di dati nel caso di canale con interferenze, si è deciso di non inviare un pacchetto unitario con tutti i keypoint e i descrittori codificati, ma di suddividere l’invio in pacchetti più piccoli. Si è deciso quindi di costruire pacchetti di dimensione variabile conte-nenti un numero di keypoint n per pacchetto, che può essere deciso all’avvio del client. Ogni pacchetto contiene n keypoint, nel caso il numero totale N di key-point dell’immagine non sia multiplo di n, nell’ultimo pacchetto vengono inseriti i keypoint restanti dalla divisione di N per n, e i descrittori associati a questi keypoint, ovvero una matrice n × 64 dove 64 è il numero di byte che costituisce il descrittore. Una volta ottenuti questo sottoinsieme di keypoint e la sotto-matrice di descrittori, entrambi vengono codificati con codifica entropica e poi serializzati aggiungendo un header di 12 byte, contenente il tipo, la dimensione dei descrittori e la dimensione dei keypoint.
La dimensione totale del buffer può essere calcolata come: dim = K X k=1 (αk+ βk+ Hk) (3.5) con K = N/n, if Nmod(n) = 0 N/n + 1, otherwise (3.6) α e β rispettivamente il numero di byte ottenuti con la codifica entropica dei keypoint e dei descrittori del pacchetto k-esimo, K il numero totale di pacchetti inviati e H l’header.
Prima dell’invio effettivo dei pacchetti, preparati dal client, viene inviato un datagramma preliminare con contenuti, il tipo, il numero di righe e di colonne della matrice iniziale (dati necessari nella decodifica entropica dei keypoint), il numero massimo di keypoint per pacchetto e il fattore di conversione. Questo
datagramma come nel caso CTA subisce un controllo di invio e ricezione. Quindi vengono inviati i pacchetti dati senza nessun controllo ed infine un datagramma di ”acknowledge”. Ora il server esegue BRISK sul database e effettua il matching.
3.2.7
ATC con TCP
Il protocollo TCP non necessita di inviare i dati frammentati in pacchetti più piccoli, ma può effettuare l’invio in un solo flusso di dati. Quindi dopo aver creato la socket ed effettuato la connect per stabilire la connesione, il client, usando l’algoritmo BRISK, estrae i keypoint dall’immagine e genera i descrittori. Dopo aver effettuato la codifica entropica, manda un primo pacchetto preliminare e poi il flusso di dati. Lato server tutti i dati vengono ricevuti, decodificati ed elaborati per poi effettuare il matching con il database.
3.2.8
Differenze in ATC tra UDP e TCP
Come in CTA, anche in ATC, nel caso TCP non abbiamo la divisione in pacchetti che abbiamo in UDP. In questo caso, però, aumentando il numero di pacchet-ti (che vuol dire ridurre il numero di keypoint per datagramma) non si verifica un aumento così significativo nella grandezza totale dei byte inviati, dovuto al peggioramento dell’efficienza dell’algoritmo. Infatti la codifica entropica ha per-formance pressoché invarianti. Quindi, in una prima fase di testing, osserveremo i comportamenti dei due protocolli variando il threshold e la qualità del canale e mantenendo costante il numero massimo di keypoint per pacchetto, poi in una seconda fase, verificheremo qual’è il comportamento più appropriato da usare nel frammentare la trasmissione UDP.
3.3
NeTeM
In questa sezione viene descritto il tool che ha permesso di effettuare dei test mo-dificando in maniera software la percentuale di pacchetti persi dalla connessione e quindi simulando un canale con qualità variabile. Questo tool è NetEm (Network Emulator), è una funzionalità fornita da linux ed è controllato da linea di coman-do con il comancoman-do ’tc’ che è parte del pacchetto di tool ”iproute2”. Con NetEm è possibile simulare in locale i comportamenti di una rete, quindi è possibile inserire un ritardo oppure definire una quantità di pacchetti persi, duplicati, corrotti o ordinati in maniera errata. NetEm è un sistema utilizzabile lato trasmittente a livello IP quindi nel nostro caso andrà a scartare una determinata quantità di pacchetti di livello IP in base alla percentuale specificata nelle impostazioni.
Nel nostro test andremo ad usare un ”loss” dello 0% (caso senza uso di NetEm), 2%, 5% e 10%, percentuali superiori non sono considerate consistenti. Un esempio è il seguente:
# tc qdisc add dev wlan0 root netem loss 10%
dove wlan0 è la periferica su cui si vuole introdurre la regola, il comando loss specifica il valore di perdita che nel caso d’esempio è del 10%.
Valutazione delle prestazioni
In questo capitolo vengono presentati i casi di test preparati sui modelli presentati nel Capitolo 3 e ne vengono riportati i risultati, dapprima viene affrontato il caso CTA, in cui si testano le prestazioni del protocollo UDP e poi quello TCP, quindi allo stesso modo vengono presentati i risultati dei test nella configurazione ATC con UDP e TCP. Le conclusioni con il confronto delle prestazioni tra le quattro configurazioni vengono invece presentati nella parte finale del capitolo. Le grandezze principali alla base dei grafici che proponiamo sono il ”Query Delay” e il ”MAP”, il primo è il tempo utilizzato per un invio, ottenuto con dei timer posti sul server, che misurano l’istante di inizio della ricezione (primo pacchetto arrivato dal client) e l’istante di ricezione dell’ultimo pacchetto (nel caso UDP l’arrivo del ack), mentre il secondo rappresenta l’accuratezza del riconoscimento (sezione 2.4).
4.0.1
Dataset
Esistono numerosi dataset di immagini utilizzabili con cui testare i valori di accuratezza di un sistema di riconoscimento. In questa tesi viene usato:
ZuBudD: ”The Zurich Building Database”[20] contiene 1005 immagini a co-lori di 201 edifici della città di Zurigo. Ciascun edificio ha cinque immagini VGA(640x480), prese da punti di vista diversi e casuali, in stagioni diverse, con condizioni meteo diverse e da due fotocamere differenti. Un altro archivio
con-Figura 4.1: ZuBuD
tiene 115 immagini (con una risoluzione 320x240) degli stessi edifici presenti nel database (prese in maniera diversa). Esiste inoltre un file ”ground truth” che for-nisce al sistema il matching tra query e database per valutare l’accuratezza del riconoscimento.
4.1
Compress-Then-Analyze
Il test di CTA viene effettuato inviando la query ZuBuD, composta da 115 im-magini, variando il ”quality factor” da 0 a 100 con passo di 5, con un canale con lo 0%, 2%, 5% e 10% di perdita di pacchetti, per un totale di 2415 immagine per 4 configurazioni. Come accennato nella sezione(3.2.2), una fase preliminare sarà dedicata all’individuazione del numero di blocchi ottimo in cui dividere le immagini nel caso UDP.
4.1.1
CTA-UDP: Numero di blocchi ottimo
Per fare questo abbiamo inviato ripetutamente la query del database ZuBuD con valori prefissati di ”quality factor” 10-20-30 con una divisione in blocchi crescente. Nella Figura 4.2 verifichiamo quello che si era intuito teoricamente, ovvero che la crescita del numero di blocchi introduca un aumento molto significativo della quantità totale di byte da inviare. Nel caso specifico tra la dimensione della query con blocco unitario e quella con 500 blocchi esiste un divario di quasi un ordine di grandezza.
Per quanto riguarda il rapporto tra numero di blocchi e tempo necessario per l’invio dell’immagine (figura 4.3), possiamo vedere come all’aumentare del numero
0 50 100 150 200 250 300 350 400 450 500 0 0.5 1 1.5 2 2.5 3 3.5x 10 5 Number of block
Query size [byte]
Quality Factor 10 Quality Factor 20 Quality Factor 30
Figura 4.2: Rapporto tra la dimensione del buffer e il numero di blocchi senza perdita di pacchetti e con ”quality factor” variabile
0 50 100 150 200 250 300 350 400 450 500 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 Number of blocks Query Delay [s] UDP 0% UDP 2% UDP 5% UDP 10%
Figura 4.3: Rapporto tra ritardo e numero di blocchi al variare della qualità del canale e con un ”quality factor” di 30
0 50 100 150 200 250 300 350 400 450 500 0.64 0.66 0.68 0.7 0.72 0.74 0.76 0.78 0.8 0.82 Number of blocks MAP UDP 0% UDP 2% UDP 5% UDP 10%
Figura 4.4: Rapporto tra accuratezza e numero di blocchi al variare della qualità del canale e con un ”quality factor” di 30
di blocchi ci sia un aumento lineare del tempo necessario all’invio dei dati, conse-guente all’aumento della quantità di informazioni da inviare.
Nell’accuratezza invece (figura 4.4) possiamo osservare due fenomeni:
• uno, prevedibile, per cui all’aumentare del numero di pacchetti persi si veri-fica una diminuzione dell’accuratezza del riconoscimento, dovuta alla dimi-nuzione dell’informazione posseduta dall’immagine, che raggiunge il server priva di alcune parti;
• l’altra, meno prevedibile, per cui a parità di pacchetti persi, aumentando il numero di blocchi con cui è divisa l’immagine, si verifica una diminuzione dell’accuratezza.
0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 0.5 0.55 0.6 0.65 0.7 0.75 0.8 Query Delay [s] MAP UDP 0% UDP 2% UDP 5% UDP 10%
Figura 4.5: Andamento del ritardo e dell’accuratezza con ”quality facor” 20 variando il numero di blocchi e la qualità del canale
0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 0.5 0.55 0.6 0.65 0.7 0.75 0.8 Query Delay [s] MAP UDP 0% UDP 2% UDP 5% UDP 10%
Figura 4.6: Andamento del ritardo e dell’accuratezza con ”quality facor” 30 variando il numero di blocchi e la qualità del canale
Come vediamo nelle figure 4.5 e 4.6, che rappresentano l’andamento del ritardo e dell’accuratezza, rispettivamente nel caso con ”quality factor” 30 e 40, si verifica un andamento prima crescente e poi decrescente. Quindi, tolto il caso con per-centuale nulla di perdita di pacchetti, aumentando il ritardo abbiamo un aumento dell’accuratezza e poi una successiva diminuzione, con picco che coincide con un numero di blocchi tra i 16 e i 64, ovvero una matrice con dimensione tra le 4x4 e le 8x8 blocchi. Per i nostri test successivi abbiamo deciso quindi di porci nella situazione di massima accuratezza ovvero attorno al picco dei grafici nel piano ”Query delay-MAP”, quindi inviando le immagini divise in 36 pacchetti (6x6), e nella situazione di ritardo minimo, ovvero nel caso in cui l’immagine venga inviata in un unico blocco.
4.1.2
Perdita di accuratezza all’aumento del numero di
bloc-chi
E’ però interessante, prima di procedere con i test, capire il perché della diminuzio-ne dell’accuratezza all’aumentare del numero di blocchi. Intuitivamente l’aumento del numero di blocchi in cui dividere l’immagine avrebbe dovuto portare ad un aumento dell’accuratezza, perché perdere blocchi piccoli dovrebbe essere preferi-bile a perdere blocchi molto grandi. All’occhio umano appare infatti più facile riconoscere un oggetto da un’immagine in cui le parti mancanti sono frammenti piccoli e numerosi, piuttosto che pochi e grandi; in quanto il cervello umano nel-la prima situazione è maggiormente in grado di riconoscerne nel-la struttura globale sottostante.
Prendiamo un immagine qualsiasi del database ZuBuD (nel caso l’immagine 65) con quality factor di 30 e osserviamo il comportamento di BRISK nella ricerca dei descrittori (4.7). Partendo dall’angolo in alto a sinistra e spostandosi verso de-stra troviamo, prima l’immagine senza perdita, con sovrapposti i keypoint trovati
Figura 4.7: Esempio in cui possiamo osservare i keypoint ottenuti usando il protocollo di BRISK su un immagine di ZuBuD aumentando la divisione in blocchi. In alto a sinistra troviamo l’immagine senza divisione in blocchi, spostandosi verso destra e poi in basso vediamo l’aumento del numero di keypoint con il crescere dei blocchi in cui viene divisa l’immagine
dal detector, e poi quelle ottenute aumentando progressivamente il numero dei blocchi (simulando una perdita di pacchetti del 30%). Possiamo osservare come ci sia un aumento del numero di keypoint individuati da BRISK e questi vengano localizzati attorno al blocco nero della parte di immagine mancante. Questi sono keypoint di ”noise”, di disturbo e sono via via in numero maggiore quanto più aumentano i blocchi mancanti. Ciascun blocco nero inserito nell’immagine intro-duce quindi dei keypoint fasulli, trovati negli angoli, e questi, sommati a quelli corretti, rendono più difficile il riconoscimento in fase di matching e portano ad una diminuzione dell’accuratezza.
Figura 4.8: Grafico con rappresentato l’aumento del numero di keypoint di noise (in blu) all’aumento del numero di blocchi. In rosso sono rappresentati il numero di keypoint che dovrebbero essere individuati teoricamente dal sistema con il 30% di pacchetti persi.
4.1.3
CTA-UDP: accuratezza ottima
Ora, fissato il numero di blocchi ottimo per l’accuratezza a 36, ovvero dividendo l’immagine in una matrice ”6x6”, possiamo testare le prestazioni del modello CTA con UDP. 0 1 2 3 4 5 6 7 8 9 x 104 0 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 0.045
Query Size [byte]
Query Delay [s]
UDP 0% UDP 2% UDP 5% UDP 10%
Figura 4.9: Ritardo al variare della dimensione e della qualità del canale nella configurazione UDP
In Figura 4.9 possiamo osservare come il ritardo aumenti in maniera lineare alla dimensione dei dati inviati con una pendenza che è la velocità di trasmissione pro-pria di UDP. Nella figura 4.10 osserviamo come l’accuratezza segua un andamento crescente all’aumentare del ritardo (ovvero della qualità della compressione) e rag-giunga poi una soglia di saturazione in cui la qualità delle informazioni è tale per cui non c’è un miglioramento del riconoscimento. Nel confronto tra le condizioni con differente percentuale di perdita di pacchetti, nel grafico dimensione ritardo possiamo osservare come le 4 rette siano praticamente sovrapposte, ovvero il rate si mantiene costante (piccole variazioni sono dovute alla perdita possibile del ack, quindi un aumento dovuto al timeout nel rinvio), mentre nel piano MAP-delay
0 0.002 0.004 0.006 0.008 0.01 0.012 0.014 0.016 0.018 0.02 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Query Delay [s] MAP UDP 0% UDP 2% UDP 5% UDP 10%
Figura 4.10: UDP: ritardo-accuratezza con dati ottenuti modificando il qualityf actor e la qualità del canale
vediamo che aumentando la perdita di pacchetti, si abbassa il valore di saturazio-ne del grafico, quindi diminuisce la soglia massima di accuratezza ottenibile con UDP (quasi del 10% tra condizione del canale migliore e peggiore). Un fenomeno che si osserva in questo grafico è come ci sia un peggioramento dell’accuratezza in stato di saturazione con l’aumentare della percentuale di pacchetti persi. Questo è dovuto al fatto che, aumentando la quantità di dati N da trasmettere, mentre rimane costante la probabilità di perdere un singolo pacchetto a livello IP, au-menta la probabilità di perdere il pacchetto UDP. I pacchetti a livello IP hanno grandezza massima di 1512 byte, di cui 1470 di tipo dati. Consideriamo P (n) la probabilità di perdere il pacchetto IP n, se prendiamo un pacchetto a livello UDP di dimensioni m ∗ n, la probabilità di perdere quello a livello UDP è:
P (n1∪n2∪...∪nm) = 1 − ((1 − P (n1))(1 − P (n2))...(1 − P (nm))) = 1 − (1 − P (n))m
(4.1) Quindi, aumentando le dimensioni del pacchetto UDP da inviare, si incrementa
il numero di pacchetti a livello IP in cui effettuare la frammentazione (aumenta m) e si verifica un conseguente aumento della probabilità di perdere l’immagine. Nel caso di test abbiamo un numero di pacchetti UDP pari a 36, quindi ciascun
2 3 4 5 6 7 8 9 x 104 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8
Query Size [byte]
MAP
UDP 0% UDP 2% UDP 5% UDP 10%
Figura 4.11: UDP: accuratezza al variare della dimensione del buffer con dati ottenuti modificando il qualityf actor e la qualità del canale
pacchetto UDP è sotto la soglia dei 1470 byte quando la dimensione del buffer tra-smesso è al di sotto di circa 50000 byte, oltre questa soglia il datagramma viene diviso in due pacchetti IP, quindi pressapoco raddoppia la probabilità di per-dere informazione. Di conseguenza abbiamo un abbassamento della saturazione dell’accuratezza come appunto osserviamo nel grafico 4.11.
4.1.4
CTA-UDP: ritardo ottimo
Esaminiamo quindi il comportamento nel caso in cui le immagini vengano inviate in un unico blocco, senza subire frammentazione. In questo caso possiamo osser-vare come nella condizione senza perdita di pacchetti ci sia un comportamento simile a quello di UDP con 36 blocchi, l’accuratezza aumenta con il ritardo e si stabilizza ad un valore di saturazione. Altresì, aumentando la perdita di pacchetti
0 0.002 0.004 0.006 0.008 0.01 0.012 0.014 0.016 0.018 0.02 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Query Delay [s] MAP UDP 0% 1block UDP 2% 1block UDP 5% 1block UDP 10% 1block
Figura 4.12: UDP con ritardo ottimo: nel piano ritardo-accuratezza con dati ottenuti modificando il qualityf actor e la qualità del canale
abbiamo un crollo delle prestazioni del sistema che più aumenta il ritardo (ovvero più è grande il buffer che stiamo inviando) più diminuisce il riconoscimento, fino ad essere praticamente nullo. Questo fenomeno è lo stesso che abbiamo spiegato nella sezione precedente per cui, aumenta la probabilità di perdita del macro-pacchetto UDP aumentando il numero di sotto-pacchetti IP che lo compongono. Per questo nei successivi confronti nel caso CTA-UDP con un blocco andremo a considerare solo il caso ideale in cui non ci sia perdita di pacchetti e trascureremo le altre curve.
4.1.5
CTA-TCP
In TCP come abbiamo già detto non c’è frammentazione, ma l’immagine viene mandata interamente in un unico flusso di dati (sezione 3.2.3)
Variando la qualità del canale vediamo come ci sia un aumento del ritardo nel-l’invio della query (figura 4.13) dovuto all’aumento di pacchetti persi e rinviati dal protocollo. Abbiamo quindi una diminuzione del ”rate” di TCP al peggioramento
0 1 2 3 4 5 6 7 8 9 x 104 0 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 0.045
Query Size [byte]
Query Delay [s]
TCP 0% TCP 2% TCP 5% TCP 10%
Figura 4.13: Ritardo di trasmissione al variare della dimensione del buffer e della qualità del canale nella configurazione TCP
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 x 104 0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8
Query Size [byte]
MAP
TCP 0% TCP 2% TCP 5% TCP 10%
Figura 4.14: TCP: accuratezza al variare della dimensione con dati ottenuti modificando il qualityf actor e la qualità del canale
del canale. Nella figura 4.14 invece osserviamo come TCP mantenga costante il rapporto tra byte inviati e MAP, in quanto non si ha mai perdita di informazione. Unendo i due grafici precedenti, ovvero riportando i dati dell’accuratezza nel piano del ritardo (figura 4.15), possiamo osservare come al peggioramento della qualità del canale coincida uno slittamento della curva verso destra, conseguente all’aumento del ritardo.
0 0.002 0.004 0.006 0.008 0.01 0.012 0.014 0.016 0.018 0.02 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Query Delay [s] MAP TCP 0% TCP 2% TCP 5% TCP 10%
Figura 4.15: TCP: nel piano ritardo-accuratezza con dati ottenuti modificando il qualityf actor e la qualità del canale
![Il mappamondo cinese di Giulio Aleni [Ai Rulüe] (Brescia, 1582 – Yanping 1649)](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACH5BAEAAAAALAAAAAABAAEAAAICRAEAOw==)