Studio di algoritmi di estrazione informazioni ad alto livello per sistema di visione embedded

9 
 
1. Introduzione  
Permettere ad un robot di vedere il mondo circostante, insegnargli a distinguere 
oggetti ed ostacoli vicini e lontani è, da sempre, uno dei principali obbiettivi per molti 
ingegneri. Nel settore della robotica tale condizione è indispensabile per fornire 
un’importante autonomia al robot: quella di movimento in un ambiente sconosciuto.  
Lo studio di sistemi di visione robotici, ad oggi, non si può considerare completo ed è 
tuttora considerevole l’attività di ricerca svolta in questo ambito. Anche 
STMicroelectronics, azienda leader nella produzione di componenti elettronici, con il 
suo AST-Robotics (laboratorio di ricerca e sviluppo robotica), ha avviato innumerevoli 
progetti per lo studio e lo sviluppo di sistemi di visione intelligenti.  
Una delle principali innovazioni introdotte da STMicroelectronics, si concretizza nel 
sistema di visione embedded RVS Module (Robotic Vision System), il quale, concentra 
in un unico elemento una videocamera da 2 Mpx, un microcontrollore e una memoria 
RAM. Tale apparato risulta essere molto innovativo se paragonato a sonar o scanner 
laser, precedentemente utilizzati.  
Proprio da uno degli innumerevoli progetti nati per sfruttare al massimo le potenzialità 
di questo modulo, prende vita questo progetto di tesi. Essa si concentra su una 
importante fase necessaria ai sistemi di visione: permettere l’estrazione di 
informazioni ad alto livello dall’immagine acquisita. Nello specifico, l’obbiettivo 
principale sarà l’ottimizzazione dell’algoritmo per la visione Harris Corner Detector, 
deputato alla ricerca dei punti caratteristici di un’immagine attraverso l’analisi delle 
variazioni di luminosità presenti. Come punti chiave sono considerati gli spigoli di 
corpi “visti” dal robot, i quali permetteranno l’identificazione di oggetti nell’ambiente 
circostante.  
L’algoritmo al centro della trattazione era già presente in forma preliminare su PC 
all’interno di un progetto inerente la visione stereoscopica. L’ottimizzazione renderà 
lo stesso fruibile all’interno del microcontrollore dell’RVS Module. Così completato, 
l’algoritmo potrà essere unito ad altri già esistenti (Blob Search, Face Detection) 
contribuendo a comporre un set di applicazioni grazie a cui sarà possibile rendere 
“intelligente” il modulo di visione RVS, permettendone il concreto utilizzo sui futuri 
robot.
10 
 
1.1. Obbiettivi 
Come si è potuto apprendere dall’introduzione, l’algoritmo di ricerca dei punti chiave 
di un’immagine Harris Corner Detector (H.C.D.), esistente su PC in fase preliminare, 
necessita di alcuni sostanziali miglioramenti e variazioni per poter essere eseguito 
all’interno di un microcontrollore.  Di seguito verranno illustrati i principali obbiettivi  
prefissati. 
1.1.1. Ottimizzazione dell’algoritmo 
L’obbiettivo principale è l’ottimizzazione dell’algoritmo per permetterne l’impiego 
all’interno del microcontrollore dell’RVS Module (un microcomputer dalle risorse 
limitate). Nella forma originale infatti, l’algoritmo H.C.D. non è fruibile ai fini pratici 
poichØ richiede una potenza di calcolo e una memoria troppo elevate per essere 
eseguibile all’interno del microcontrollore.  La riduzione dei costi di allocazione e la 
riduzione dei tempi di calcolo saranno i primi, fondamentali passi da compiere. 
1.1.2. Scrittura algoritmo nel linguaggio del microcontrollore 
Dopo la fase principale di ottimizzazione, effettuata attraverso il software Matlab, è 
necessario implementare H.C.D. in linguaggio C per renderlo eseguibile dal 
microcontrollore e quindi effettivamente utilizzabile all’interno dell’RVS Module.  
La trascrizione in linguaggio C, non è da considerare di secondaria importanza poichØ, 
la sua sostanziale differenza con il linguaggio Matlab, obbliga ad un attento utilizzo 
dei costrutti, in modo da evitare di vanificare i miglioramenti precedentemente 
apportati. 
1.1.3. Parametrizzazione delle funzioni 
H.C.D. utilizza al suo interno alcuni parametri da cui dipende la quantità e la qualità 
dei risultati forniti; in origine essi sono stati impostati con valori costanti a seconda 
della specifica necessità. Attraverso la parametrizzazione delle funzioni, si vuole 
fornire ad utenti successivi la possibilità di variare al bisogno il valore di tali parametri 
caratteristici, senza dover intervenire sull’intero script ma, garantendone il corretto 
funzionamento e la correttezza dei risultati.
11 
 
 
 
1.2. Schema della tesi 
Attraverso questa tesi, si vuole ripercorrere e descrivere il lavoro portato avanti 
durante il periodo di stage presso STMicroelectronics. La scelta della struttura, in 
primis, è significativa per la comprensione del percorso intrapreso. I capitoli principali 
sono relativi alle fasi di: comprensione degli obbiettivi, studio teorico dell’argomento, 
applicazione pratica con descrizione delle soluzioni avanzate ed infine, conclusioni, 
comprensive delle valutazioni sul conseguimento degli obbiettivi.  
 
Nel primo capitolo, viene introdotto il settore della visione robotica e indicato 
l’algoritmo di visione Harris Corner Detector come elemento principale su cui verterà 
questo lavoro di tesi. La descrizione degli obbiettivi permette al lettore di conoscere 
da subito cosa si vuole ottenere e quali saranno i vantaggi derivanti. 
 
Il secondo capitolo, lo Stato dell’arte, è rappresentativo della parte di studio effettuata 
per comprendere i linguaggi di programmazione utilizzati e le regole matematiche alla 
base dell’algoritmo. In esso vengono presentati in maniera rigorosa i principi 
scientifico-matematici piø importanti su cui si fonda H.C.D. oltre ad una panoramica 
su alcuni algoritmi di Edge Detection esistenti.  
L’intento è di permettere una comprensione piø approfondita di ciò su cui si sta 
operando e del significato delle operazioni svolte, così da consentire successivamente 
la comprensione dei risultati ottenuti. Un sottocapitolo è dedicato all’architettura 
dell’RVS Module, il sistema di visione al quale è indirizzato l’algoritmo. 
 
Nel capitolo centrale si trova la descrizione vera e propria delle innovazioni apportate 
ad H.C.D. . Viene inizialmente presentata la struttura originale dell’algoritmo su PC, 
tale da consentire la conoscenza del punto di partenza e indicare quello che sarà il 
termine di confronto per la comprensione delle innovazioni apportate e la verifica dei 
risultati. Successivamente, vengono descritte le nuove funzioni ottimizzate per la 
convoluzione e il nuovo codice dell’algoritmo di ricerca dei massimi di luminosità. 
L’ambiente di sviluppo è in questo caso Matlab, attraverso cui sarà piø facile la 
valutazione dei miglioramenti, prima dell’implementazione finale. Questa parte viene 
trattata con particolare dettaglio poichØ costituente il fulcro della tesi. La parte 
conclusiva di questo capitolo è dedicata all’implementazione in linguaggio C. 
Vengono esposti i principali costrutti utilizzati, gli accorgimenti per rendere il codice 
piø comprensibile e, ancora piø importanti, le principali differenze esistenti tra il 
codice Matlab e il codice C implementato. Un breve accenno è dedicato alle librerie 
grafiche utilizzate per visualizzare i risultati durante l’implementazione in C.
12 
 
Il quarto ed ultimo capitolo, contiene i risultati e le valutazioni finali. I risultati sono 
riportati in maniera oggettiva e di seguito commentati. 
Seguendo il filo logico dettato dagli obbiettivi, troviamo esposte le stime del costo di 
allocazione e del tempo di calcolo prima e dopo l’ottimizzazione. Tali dati ci 
permettono di dimostrare il miglioramento ricercato nel primo obbiettivo. Viene 
successivamente descritta l’implementazione in linguaggio C, anche il secondo 
obbiettivo della tesi è stato dunque raggiunto. La conclusione è infine affidata alle 
valutazioni personali dello studente, il quale descrive, in ultima battuta, le possibili 
applicazioni future.
13 
 
2. Stato dell’arte 
2.1. Algoritmi di estrazione delle features 
In Computer Vision, un angolo può essere definito come l’intersezione di due bordi, 
oppure, genericamente, come punto dove due bordi principali differenti coesistono 
nell’intorno del punto stesso.  
Un punto d’interesse è un punto all’interno di un’immagine con una ben definita 
posizione, la quale può essere rilevata con certezza. Questo significa che come punto 
di interesse possono essere classificati gli angoli (corner) ma anche punti isolati, 
corrispondenti a massimi o minimi di intensità, fine di righe o punti su una curva dove 
la curvatura è massima a livello locale. 
In pratica, la maggior parte dei cosiddetti metodi di rilevazione dei corner, rilevano 
punti di interesse piuttosto che angoli. Di conseguenza, se all’interno di un algoritmo 
devono essere individuati solo i corner, è necessario effettuare le dovute 
considerazioni a livello locale, per determinare quali effettivamente sono angoli tra i 
punti di interesse individuati. 
Diversi tentativi di affrontare questo problema di estrazione di punti caratteristici da 
un’immagine hanno portato, nel corso della storia, alla formulazione di diversi 
algoritmi.  
Oltre ad Harris Corner Detector, di Harris e Stephens, che tratteremo 
approfonditamente in seguito, si distinguono principalmente il Canny Edge Detector e 
il Moravec Corner Detector.
14 
 
2.1.1. Canny Edge Detector 
L’algoritmo formulato da John F.Canny, risalente al 1986, si propone di rilevare dei 
bordi (edge) all’interno di un’immagine. L’algoritmo riceve in input l’immagine I, il σ 
(sigma) relativo allo smoothing (vedi convoluzione Gaussiana) e i valori di soglia 
massimo e minimo. Può essere suddiviso in quattro parti principali: Noise Reduction, 
Canny Enhancer (per individuare il gradiente di luminosità dell’immagine), Non Max 
Suppression e Hysteresis Thresholding.  
 
Canny voleva appunto formulare l’algoritmo per edge detection ottimale; con ottimale 
egli intendeva che l’algoritmo dovesse riconoscere il maggior numero possibile di 
edge reali all’interno dell’immagine, che i bordi segnalati dovessero essere il piø 
vicino possibile ai bordi reali dell’immagine ed infine dovesse fornire il minor numero 
di risposte possibili, ovvero un edge dovesse venir segnalato una volta sola e la 
riduzione del rumore dovesse eliminare i falsi edge. 
Per soddisfare questi requisiti Canny individuò come funzione ottimale per il suo 
algoritmo una somma di quattro termini esponenziali, i quali possono essere ben 
approssimati dalla derivata prima della funzione Gaussiana. 
 
Figura 2: Andamento della funzione Gaussiana in 2D 
Figura 1: Raffigurazione delle quattro operazioni princi pali svolte da Canny Edge 
Detector