Tesi Robotica Analisi, progettazione e implementazione... | Page 19

i

i
“LP_Tesi” — 2013/10/17 — 18:27 — page 19 — #19

i

i

è stata descritta in [Dieny et al., 2011]. Gli autori di questo articolo hanno
adattato il classico algoritmo di Needleman & Wunsch per l’allineamento di
sequenze [Needleman and Wunsch, 1970] (usato in bioinformatica per allineare
le sequenze di proteine) in modo da scoprire le corrispondenze tra pixel delle
due immagini stereo. Per quanto riguarda l’implementazione degli algoritmi di allineamento in hardware, molte architetture sono state prodotte negli
anni recenti [Che et al., 2008, Fernandez et al., 2010]. In particolare è possibile trovare molte implementazioni FPGA dell’algoritmo di Smith-Waterman
[Smith and Waterman, 1981], frequentemente usato per “l’allineamento locale”
delle proteine. Anche se la descrizione ad alto livello del problema di allineamento globale è fondamentalmente la stessa di quella dell’allineamento locale,
questa architettura non può essere applicata direttamente al problema che si
sta trattando a causa delle molte differenze esistenti. La differenza principale
sta nel fatto che le sequenze trattate in bioinformatica sono di dimensioni molto
differenti tra loro, la sequenza di riferimento può essere lunga anche migliaia di
elementi, mentre quella di controllo può essere lunga al massimo poche decine
di elementi, per quanto riguarda il problema dello stereo matching si hanno
sempre sequenze delle stesse dimensioni, e questo impatta molto sui requisiti di
memoria. Come se non bastasse in Bioinformatica sono solo quattro i simboli
trattati, al contrario le immagini usate per la stereo vision sono composte da
pixel che nel caso migliore sono larghi 8 bit e che quindi possono rappresentare
la bellezza di 256 simboli.
Il presente lavoro di tesi è suddiviso in 3 parti contenenti 9 capitoli:
I Parte
Nel capitolo 1 viene introdotto l’approccio classico alla stereoscopia, tale approccio comprendente l’uso di tecniche di machine learning per trovare il match
fra i punti chiave delle due immagini analizzate.
Nel capitolo 2 l’approccio classico viene abbandonato in favore di tecniche che
cercano di trovare match fra i pixel delle immagini senza utilizzare punti chiave,
fra tali approcci è presente l’algoritmo descritto nel seguito della tesi.
II Parte
Nel capitolo 3 si fornisce una panoramica sui sistemi embedded, si evidenziano
le peculiarità che distinguono tali sistemi da quelli general purpose, descrivendo come gli obiettivi e vincoli di progetto si riflettono sulle scelte architetturali. Si descrive in particolare l’architettura di un FPGA, il modo in cui
viene programmato e una breve panoramica su cosa significhi programmare in
HDL.
19

i

i
i

i