N
U
IVERSITA DI ISA
P
Facolt`
a d’Ingegneria
Corso di Laurea Specialistica in Ingegneria
Informatica
Dipartimento di Ingegneria dell’Informazione
Progettazione e sviluppo
di un algoritmo di visione
con singola telecamera
per la stima della distanza
di oggetti noti
Candidato:
Relatore:
Angelo Castellano Prof. Giorgio Buttazzo
Indice
Sommario vi
1 Introduzione 1
1.1 Computer Vision . . . 1
1.1.1 Rilevamento traffico stradale . . . 2
1.1.2 Riconoscimento facciale . . . 3
1.1.3 Visione industriale . . . 3
1.1.4 Controllo veicoli autonomi . . . 3
1.1.5 Navigazione nei robot . . . 4
1.1.6 Individuazione eventi . . . 4
1.2 La stima della distanza . . . 4
1.2.1 Visione stereoscopica . . . 4
1.2.2 Struttura dal movimento . . . 5
1.2.3 Tempo di volo . . . 6
1.2.4 Luce strutturata . . . 8
1.3 Approccio software . . . 8
1.3.1 La sensor fusion . . . 8
1.3.2 Sistemi di stima software . . . 11
1.4 AC range estimator . . . 12
2 Descrizione del sistema 13 2.1 Microsoft Kinect . . . 13
2.2 Architettura del sistema . . . 16
2.3 Il formato immagine interno . . . 17
2.4 Ingresso e uscita . . . 18
2.4.1 Flussi video . . . 18
2.5 Il Model Sampler . . . 19
2.6 La Calibration Unit . . . 20
2.6.1 Conversioni colore e istogramma . . . 20
2.6.2 Back projection e CAMSHIFT . . . 22
2.6.3 Campionamento e funzione di stima . . . 23
2.7 Il Range Estimator . . . 23
INDICE ii
3 AC range estimator 25
3.1 La stima con telecamera singola . . . 25
3.2 Segmentazione . . . 26
3.2.1 Running Gaussian average . . . 27
3.3 Object tracking . . . 28
3.3.1 Conversione di spazio colore . . . 28
3.3.2 Istogramma immagine . . . 29
3.3.3 Back Projection . . . 31
3.3.4 Momenti . . . 32
3.3.5 Algoritmi hill climbing . . . . 34
3.4 Campionamento . . . 35
3.4.1 Corrispondenza tra immagini . . . 35
3.4.2 Raccolta campioni . . . 36
3.5 Funzione di stima . . . 36
3.6 Fase operativa . . . 38
4 Implementazione 39 4.1 Ingresso dati: Kinect e OpenCV . . . 39
4.2 Running Gaussian Average . . . 41
4.3 Gestione istogrammi . . . 43
4.4 Tracciamento: back projection e CAMSHIFT . . . 45
4.5 Depth Map . . . 46
4.6 Raccolta dei campioni . . . 47
4.7 Il metodo dei minimi quadrati . . . 48
5 Testing 50 5.1 Il sistema di riferimento . . . 50
5.2 L’oggetto campione . . . 50
5.3 Il software di testing . . . 51
5.4 Test di efficienza computazionale . . . 54
5.5 Test di precisione . . . 54 5.5.1 Ambiente monocromatico . . . 54 5.5.2 Ambiente generico . . . 60 5.5.3 Analisi risultati . . . 62 6 Conclusioni 64 Ringraziamenti 70
Elenco delle figure
1.1 Discipline correlate alla Computer Vision . . . 2
1.2 Tassonomia delle tecniche di misurazione della distanza . . . 5
1.3 Visione stereoscopica . . . 6
1.4 Sistemi a tempo di volo, principio di funzionamento e multi-path error . . . 7
1.5 Principio di funzionamento di sensore a luce strutturata . . . 8
1.6 Localizzazione delle prede attraverso ecolocazione . . . 9
1.7 Sistemi che fanno uso di algoritmi di sensor fusion . . . 10
1.8 Sensor fusion su immagini satellitari . . . 10
2.1 Dispositivi a bordo del Kinect . . . 14
2.2 Datasheet dei sensori visuali presenti sulla Kinect . . . 15
2.3 Architettura software del sistema che realizza l’algoritmo . . . 16
2.4 Formato immagine interno . . . 17
2.5 Schematizzazione del processo di background subtraction . . 20
2.6 Formato immagine interno . . . 21
2.7 Un esempio di back projection e ri-scalatura . . . 22
3.1 Spazi colore coinvolti nelle trasformazioni di coordinate cro-matiche . . . 29
3.2 Ingrandimento del canale hue . . . 30
3.3 Esempi d’istogramma immagine . . . 31
3.4 Principio di funzionamento della back projection . . . 32
3.5 Diagramma di flusso dell’algoritmo CAMSHIFT riadattato . 35 4.1 Back projection dell’istogramma dell’oggetto campione . . . . 45
4.2 Una visualizzazione dei campioni estratti durante i test pre-liminari . . . 49
5.1 Oggetti campione . . . 51
5.2 Schermata principale del software . . . 52
5.3 Schermata della modalità di tracciamento . . . 53
5.4 Schermata della modalità operativa . . . 53 5.5 Risultati del test effettuato con campione verde e luce artificiale 55
ELENCO DELLE FIGURE iv
5.6 Risultati del test effettuato con campione blu e illuminazione
artificiale . . . 56
5.7 Risultati del test effettuato con campione arancione e
illumi-nazione artificiale . . . 57
5.8 Risultati del test effettuato con campione verde e luce naturale 58
5.9 Risultati del test effettuato con campione blu e luce naturale 59
5.10 Risultati del test effettuato con campione arancione e luce naturale . . . 60 5.11 Risultati dei test effettuati con oggetto verde su diversi
inter-valli di campionamento . . . 61 5.12 Risultati del test effettuato con campione arancione in
Indice del codice
4.1 Formato immagine interno . . . 40
4.2 Implementazione delle immagini monocromatiche . . . 40
4.3 Funzione di traduzione di coordinate per la ROI . . . 41
4.4 Implementazione del canale di maschera . . . 41
4.5 Implementazione dell’istogramma immagine . . . 43
4.6 Supporto delle immagini di profondità o depth map . . . 46
4.7 Frammento di codice per la cattura della depth map correlata al frame RGB . . . 46
4.8 Struttura dati d’immagazzinamento campioni . . . 47
Sommario
Obiettivi
Il presente lavoro affronta tematiche legate alla visione artificiale (computer vision) toccando argomenti quali la sottrazione dello sfondo (background subtraction) e il tracciamento di oggetti in movimento (object tracking).
Esso è rivolto, nello specifico, alla creazione di uno strato software di libreria che implementi dei servizi per l’elaborazione di dati sensoriali. Il codice realizzato ha, in ultima analisi, l’obiettivo di supportare un algoritmo di stima della distanza di un oggetto noto, caratterizzato dall’utilizzo di un singolo sensore immagine (image sensor ). Le informazioni di esercizio per consentire a questo di operare in assenza di altri dati vengono fornite da un sensore di profondità (depth sensor ) che viene attivato temporaneamente durante un’iniziale fase di calibrazione.
Entrambi i sensori sono disponibili sul dispositivo selezionato per lo svi-luppo, il Microsoft Kinect. La scelta è stata dettata dalla presenza simul-tanea dei due sensori e dalla disponibilità di driver per Windows e Linux, argomento questo che suggerisce una prima possibilità di porting tra i due sistemi.
L’ambiente operativo selezionato è Linux, data la sua flessibilità e la conseguente diffusione in contesti embedded, settore, quest’ultimo, che ha indirizzato molte scelte di progetto, rivolte principalmente al mantenimento di un alto livello di semplicità algoritmica, al fine di garantire anche a sistemi integrati di scarsa potenza computazionale la possibilità di fruire delle fun-zionalità offerte. É infatti auspicabile che i risultati ottenuti possano essere trasferiti in maniera relativamente semplice su un sistema integrato munito di sensori equivalenti a quelli del Kinect.
Metodologia utilizzata
Si è scelto di lavorare a un livello di astrazione tale da ignorare i dettagli fisici dell’hardware a disposizione, utilizzando a tal fine un algoritmo di ca-librazione. Nello specifico sono state tralasciate le problematiche relative al
SOMMARIO vii trasferimento dell’informazione visiva dalla scena reale alla rappresentazione digitale.
La trattazione inizia da due matrici di pixel, ottenute da un sensore RGB e da un sensore di profondità. Sulle due immagini, opportunamente trattate, viene individuato l’oggetto su cui effettuare le misurazioni e inizia la fase di calibrazione durante la quale il sistema ricava una relazione tra le dimensioni apparenti dell’oggetto stesso e la sua distanza dal Kinect. Terminata questa fase il sistema passa in modalità operativa, che prevede lo spegnimento del sensore di profondità e la stima della distanza basata sulle dimensioni apparenti rilevate e sulla relazione costruita.
Contributi innovativi
L’algoritmo di stima della distanza è stato pensato per lavorare in mancanza d’informazioni sull’ottica della camera e sull’ambiente operativo (in modo da adattarsi “al volo” alle condizioni contingenti); è il sistema stesso a ricavare le informazioni necessarie durante la fase iniziale, terminata la quale è pronto a fornire la sua stima avendo come input esclusivamente il flusso video RGB acquisito.
Determinante nelle scelte di progetto è stata la volontà di utilizzare, nel periodo operativo del sistema, soltanto un sensore al fine di ridurre i consumi energetici che costituiscono con grande frequenza i principali trade-off progettuali per soluzioni analoghe.
La libreria software è stata sviluppata in linguaggio C utilizzando il para-digma WOCA (Write Once, Compile Anywhere). La scelta è stata dettata dalla volontà di aprire la soluzione al contesto dei sistemi embedded, nei quali spesso non è disponibile, nativamente, un supporto all’elaborazione grafica. Usando il C, inoltre, è stato possibile individuare e ottimizzare le sezioni di codice critiche dal punto di vista delle prestazioni. D’altra parte l’approccio proposto impone di mantenere il codice il più snello possibile, poiché non sono a disposizione tutti gli strumenti concessi dai linguaggi di più alto livello, forti del loro paradigma object oriented e avvantaggiati nel-la gestione delnel-la complessità. Queste scelte hanno stabilito il compromesso dominante nello sviluppo della libreria, quello tra prestazioni e flessibilità: da un lato si è cercato di mantenere basso il carico computazionale, evitan-do l’implementazione degli algoritmi più “pesanti” e riducenevitan-do al minimo le operazioni sui pixel, dall’altro si è cercato di rendere la libreria idonea all’u-tilizzo con diversi tipi di immagine e a interfacciarla con sistemi di input e output differenti, creando strutture dati capaci di supportare un più vasto numero di operazioni.
SOMMARIO viii
Risultati ottenuti
La libreria software è capace di gestire in maniera efficiente immagini su tre canali con conversione colore, mascheramento e sottrazione dello sfondo. Un certo numero di altre operazioni è disponibile operando su singolo cana-le incluse quelcana-le di computer vision come segmentazione e object tracking. Ci sono poi una serie di operazioni di supporto come la gestione degli isto-grammi, il calcolo dei momenti statistici e il supporto all’algebra matriciale, necessarie all’algoritmo di stima per raggiungere il suo obiettivo funzionale. L’algoritmo realizzato si è mostrato capace di stimare la distanza del-l’oggetto campione con un margine di errore che oscilla intorno al 4.2%. L’algoritmo di tracking si è rivelato robusto rispetto ai disturbi ambienta-li e idoneo ad un utiambienta-lizzo in condizioni non controllate. I test su PC con hardware di fascia media (ad aprile 2018) hanno evidenziato il mantenimen-to delle capacità real-time con un’influenza dell’elaborazione sul frame-rate pari circa al 9%. Le uniche dipendenze presenti nel progetto sono le librerie standard del C e quelle di I/O (OpenKinect per l’ingresso e OpenCV per ingresso e uscita).
Descrizione capitoli
Il primo capitolo presenta il contesto operativo, inserendo le tematiche af-frontate nella più grande area della Computer Vision, ed esamina le varie soluzioni esistenti di misura della distanza sia con tradizionali approcci sen-soristici sia con metodiche software basate sui concetti di fusione sensoriale, in fase di penetrazione sul mercato per la loro flessibilità.
Il secondo capitolo esamina il principale dispositivo hardware utilizzato, il Microsoft Kinect, poiché questo ha indirizzato alcune scelte di progetto, e presenta l’architettura del sistema, evidenziando il flusso d’informazioni dall’acquisizione alla restituzione dei risultati.
Il terzo capitolo analizza tutti gli algoritmi utilizzati e i principi di base che ne caratterizzano il funzionamento, dotando la descrizione generale di una solida base teorica.
Il quarto capitolo mostra come le operazioni esaminate siano state ripor-tate in codice e illustra le strutture e le funzioni di supporto che si sono rese necessarie al fine di implementare le procedure richieste.
Il quinto capitolo presenta l’ambiente di testing, il software di stima e i ri-sultati ottenuti mettendo in esercizio il sistema in un ambiente parzialmente controllato, mostrando i suoi punti di forza e i suoi limiti.
Capitolo 1
Introduzione
Questo lavoro è focalizzato sulla stima della distanza di un oggetto noto in un ambiente non controllato mediante un sensore immagine operante nello spettro visibile, previa calibrazione attraverso un sensore di profondità a luce strutturata. La base teorica richiesta affonda le sue radici in una disciplina in espansione e che trova applicazione in molteplici settori della tecnologia attuale, la Computer Vision.
1.1
Computer Vision
Uno dei principali problemi nel trattamento delle immagini, laddove ne sia richiesto un processamento automatico, è l’interpretazione del contenuto in-formativo della matrice di pixel che costituisce la rappresentazione base di ogni immagine digitale. Se negli esseri viventi questa operazione è stata affinata da milioni di anni di evoluzione lo stesso non si può dire dei siste-mi di elaborazione artificiali che necessitano di specifici algoritsiste-mi, capaci di estrarre dalla rappresentazione grezza della scena, gli elementi che la compongono.
Queste esigenze emersero verso la fine degli anni ’60, trattando argo-menti d’intelligenza artificiale, e furono convogliate in un campo di studi ben preciso, connesso con numerose altre discipline (Figura 1.1) e oggi noto come Computer Vision o Visione Artificiale.
Inizialmente sovrapposta al Digital Image Processing o Elaborazione del-le Immagini Digitali, la Computer Vision prese una strada a sé, differenzian-dosi per ciò che può essere definito come un “fine interpretativo automatiz-zato”. Lo scopo di questa disciplina è, infatti, quello di ricavare dalla scena delle caratteristiche a un livello di astrazione più elevato di quanto non venga richiesto nella semplice elaborazione delle immagini e, di frequente, queste informazioni vengono utilizzate per comandare sistemi di attuazione o di comunicazione in maniera autonoma.
CAPITOLO 1. INTRODUZIONE 2
Computer Vision Intelligenza
artificiale
Fisica dello stato solido
Neurobiologia
Teoria dei segnali Matematica
Elaborazione delle immagini Robotica
Figura 1.1: Discipline correlate alla Computer Vision.
Sebbene questi dati essere catturati da sensori ad hoc è bene sfruttare il potenziale che gli algoritmi di Computer Vision mettono a disposizione. Infatti, a differenza degli apparati sensoriali tradizionali, i sistemi basati su questa disciplina si affidano a una rilevazione esclusivamente visiva, che tenta di riprodurre il comportamento del sistema di visione umano, cercando di sfruttare la flessibilità e l’adattabilità che gli occhi hanno conferito alle specie viventi.
Sul piano applicativo le metodiche di Visione Artificiale permettono di estrarre, da immagini o sequenze video, una serie d’informazioni circa gli oggetti presenti, il movimento, le linee, le forme, i contorni e altri dettagli aggiuntivi con un livello di astrazione via via più elevato.
La computer vision è ampiamente utilizzata in un numero considere-vole di sistemi e soluzioni integrate, alcuni dei quali verranno brevemente esaminati.
1.1.1 Rilevamento traffico stradale
Tutti i sistemi di rilevamento del traffico statale basato su immagini si affi-dano a tecniche di computer vision per estrarre informazioni sulla posizione reciproca dei veicoli e sulla loro identificazione. Esistono sistemi che riescono a catturare queste informazioni anche in condizioni difficili di illuminazione o congestione come in [6].
CAPITOLO 1. INTRODUZIONE 3 A titolo esemplificativo può essere citato il SICVE (Sistema informativo per il controllo della velocità), noto comunemente come Safety Tutor e attivo su molti tratti autostradali italiani, che utilizza questo tipo di algoritmi per individuare e leggere la targa degli autoveicoli di passaggio.
1.1.2 Riconoscimento facciale
E’ un caso specifico di riconoscimento di pattern (pattern recognition), pro-cedura anch’essa classificabile come appartenente alla computer vision. Con-siste nell’estrazione di un viso da un’immagine composta e il suo confronto con una serie di foto della persona da identificare. Al termine del processo il viso in esame viene associato a un’identità.
Basata su algoritmi di una discreta complessità, questa procedura ha trovato applicazione nei servizi di videosorveglianza e più recentemente nel-l’ambito della classificazione delle foto digitali, come ad esempio avviene sulla piattaforma Facebook.
1.1.3 Visione industriale
Nella produzione industriale è impossibile garantire una manifattura total-mente esente da difetti. La maggior parte delle imperfezioni o mancanze è riscontrabile visivamente ed è qui che s’inserisce la visione industriale nelle sue declinazioni di surface inspection e completeness inspection.
Attraverso gli algoritmi alla base di queste discipline è possibile garan-tire un controllo oggettivo, non dipendente dall’operatore, sul 100% della produzione, abbattendo i costi della manodopera.
1.1.4 Controllo veicoli autonomi
Le autovetture a guida autonoma, alle quali si lavora da diversi decenni, sono entrate in una fase di sviluppo avanzata negli ultimi anni grazie agli sforzi di numerose aziende tra cui Mercedes-Benz, Nissan, Toyota, Renault e Google. In alcuni stati USA e in paesi europei come la Germania l’auto senza pilota è già in fase di testing su strada e probabilmente entrerà presto in fase di produzione.
Parallelamente, una moltitudine di altri veicoli si affida, attualmente, alla guida autonoma compresi veicoli militari, spaziali (i rover su Marte ad esempio) e civili come il trasporto pubblico.
Tutta questa automazione si appoggia a una serie di discipline informa-tiche e ingegnerisinforma-tiche tra le quali la computer vision gioca un ruolo impor-tante. I sensori immagine, parte fondamentale dei sistemi di navigazione, sono infatti gestiti mediante i suoi algoritmi.
CAPITOLO 1. INTRODUZIONE 4
1.1.5 Navigazione nei robot
Ogni dispositivo mobile automatizzato richiede tre principali funzioni per poter operare in modo efficiente e sicuro: le capacità di auto-localizzazione, pianificazione del percorso e costruzione della mappa ambientale.
Queste funzionalità sono molto spesso implementate facendo uso della visione e in questo caso gli algoritmi di computer vision sono essenziali per interpretare i dati forniti dai sensori. Un esempio è fornito in [24] dove i dati visivi sono completati, secondo i principi della sensor fusion, dal rilevamento della distanza fornito da un sensore ultrasonico.
1.1.6 Individuazione eventi
Questo settore è composto dai sistemi di videosorveglianza che hanno lo sco-po di rilevare situazioni di pericolo o in altro modo interessanti. Un esempio su tutti è il rilevamento automatico d’incendi come in [32] basato sulla tra-sformata wavelet, concetto entrato recentemente nel pool di algoritmi di computer vision.
1.2
La stima della distanza
Esistono numerose metodologie finalizzate alla determinazione della distan-za di un oggetto da un sistema e, in tema di flessibilità, le più valide si basano sul rilevamento ottico. In figura 1.2 è possibile osservare una sche-matizzazione delle tecniche di distance detection più utilizzate in ambito ingegneristico. [2]
La principale differenza nei sistemi visuali è quella tra sensori attivi e sensori passivi che si può riassumere nella presenza o meno di un dispositivo emettitore che modifica in qualche modo la scena per favorire il processo di acquisizione. Nei sistemi passivi il sensore cattura esclusivamente la radia-zione luminosa presente nell’ambiente (in uno spettro non necessariamente limitato alla luce visibile) mentre nei sistemi attivi un proiettore emette una luce, in qualche spettro, che viene captata dal sensore stesso al fine di rica-vare le informazioni desiderate. Le camere stereoscopiche sono un esempio di sistema passivo mentre le telecamere a tempo di volo rappresentano la classe dei sistemi attivi.
1.2.1 Visione stereoscopica
La visione artificiale stereoscopica (computer stereo vision) è quel processo che prevede di estrarre le informazioni sulla distanza dei punti che compon-gono un’immagine confrontando la scena ripresa da due differenti punti di vista (Figura 1.3). Tipicamente prevede due sensori, disposti l’uno accanto all’altro similmente all’apparato di visione binoculare umano. Utilizzando i
CAPITOLO 1. INTRODUZIONE 5
Figura 1.2: Tassonomia delle tecniche di misurazione della distanza (derivata da
[2]).
due punti di vista della scena viene creata una mappa di disparità (disparity map) dalla quale si può estrarre la distanza, punto per punto.
Questo approccio al problema permette di ottenere una buona risoluzione e un range operativo arbitrariamente ampio (in quanto dipendente dalla distanza tra i due sensori) ma, oltre a richiedere due sensori, comporta un carico computazionale consistente, dovuto al pretrattamento necessario a compensare le distorsioni ottiche e a calcolare le proiezioni geometriche richieste. Necessita, inoltre, di una fase di calibrazione iniziale vincolata alla distanza tra i due sensori e invalidata al variare di quest’ultima. Le soluzioni basate sulla stereoscopia presentano un ulteriore inconveniente in condizioni di scarsa texturizzazione delle superfici riprese e di pattern ripetitivi, in presenza dei quali è difficoltoso e impreciso calcolare la mappa di disparità. Non trascurabile è anche il costo ancora elevato per accaparrarsi soluzioni complete e pronte all’uso.
1.2.2 Struttura dal movimento
La struttura dal movimento (structure from motion) è una tecnica di ri-costruzione di un ambiente tridimensionale basato sull’analisi visiva di una serie di fotogrammi catturati da un agente in movimento secondo modalità note. E’ simile alla visione stereoscopica nella misura in cui sia possibile considerare le varie immagini catturate come punti di vista differenti della stessa scena. Per questa ragione fa uso di algoritmi simili e soffre delle
stes-CAPITOLO 1. INTRODUZIONE 6 ( , , )x y z ( ,x yL L) ( ,x yR R) Left Camera Right Camera Epipolar line
Figura 1.3: Tipico scenario della visione stereo: due videocamere che osservano
la stessa scena hanno due differenti rappresentazioni di un punto tridimensionale. Con l’adeguata elaborazione, la posizione e la profondità del punto 3D possono essere estratti dalle immagini [3].
se limitazioni della soluzione a doppia telecamera oltre a necessitare di una vasta disponibilità di immagini [30].
1.2.3 Tempo di volo
I sensori a tempo di volo (time-of-flight cameras o ToF ) costituiscono un esempio significativo di sensore attivo in quanto dotato di un emettitore dedicato che irradia la scena d’impulsi luminosi. La misura del tempo inter-corso tra l’invio di un impulso e la ricezione della sua riflessione permette di stimare la distanza dell’oggetto più vicino rilevato (Figura 1.4). E’ lo stesso principio per il quale i pipistrelli utilizzano l’eco di un segnale sonoro da loro prodotto al fine di localizzare le prede; questo per non dimenticare come la natura abbia “progettato” secondo le sue regole una vasta gamma di dispositivi biologici simili, per funzionalità, a quelli oggetto di ricerca ingegneristica.
Sensori di questo tipo forniscono una mappa di profondità (depth map) che associa un valore di distanza ad ogni pixel che compone l’immagine, e vengono per questo definiti a campo intero.
Questa tecnologia non richiede algoritmi complessi per poter fornire i suoi servizi di rilevamento ed è ben adattabile ai sistemi integrati data la compattezza dei dispositivi costitutivi. Ciononostante non offre un’elevata risoluzione e può soffrire, a seconda della natura dell’emettitore, del proble-ma del multipath error che introduce errori nella stiproble-ma della distanza (Fi-gura 1.4). In questa categoria ricadono i distanziometri laser e la maggior parte dei laser scanner.
CAPITOLO 1. INTRODUZIONE 7 d scena dispositivo (a)
A
B
(b)Figura 1.4: Sistemi a tempo di volo, principio di funzionamento e multipath error:
(a) Principio di funzionamento di dispositivi basati su ToF. La distanza si ottiene dall’equazione d = cτ
2 dove c è la velocità della luce e τ il tempo impiegato dal segnale per tornare alla sorgente [2]; (b) Le riflessioni allungano il percorso del segnale portando a una sovrastima della distanza [2].
CAPITOLO 1. INTRODUZIONE 8
1.2.4 Luce strutturata
I sistemi a luce strutturata fanno uso di particolari proiettori che disegnano un pattern luminoso noto a priori sulla scena da riprendere. Rilevando le sue distorsioni, dovute alla presenza di oggetti, è possibile ricavare informazioni circa le distanze per tutti i punti, il che li rende sensori a campo intero. Il pattern più usato è quello a strisce parallele ma ne possono essere impiegati
altri a seconda delle applicazioni. Il Kinect, dispositivo usato in questo
progetto, costituisce un caso particolare di sistema a luce strutturata basato su triangolazione [2].
Figura 1.5: Principio di funzionamento di sensore a luce strutturata. [13]
1.3
Approccio software
Unitamente ai sensori dedicati esistono degli algoritmi che permettono di determinare la distanza di un oggetto effettuando elaborazioni software sui dati grezzi catturati da sensori eterogenei e che normalmente non forniscono indicazioni metriche. Tali procedure rientrano nella classe più ampia degli algoritmi di sensor fusion.
1.3.1 La sensor fusion
Le forme di vita sulla Terra, nel loro percorso evolutivo, hanno sviluppato diverse tecniche per percepire l’ambiente intorno a loro, al fine di sopravvi-vere e prosperare. Usando i loro sensi specializzati ottengono le informazioni di cui necessitano per cacciare, evitare i pericoli o fuggire dai predatori (Fi-gura 1.6). Nella loro lotta per la sopravvivenza hanno dovuto affinare tutti i loro “sensori”, migliorandoli da una generazione all’altra, per renderli più efficienti, veloci e sensibili. Inoltre hanno imparato, nei lughi tempi su cui lavora l’evoluzione, a combinare le informazioni che ricevono da due o più
CAPITOLO 1. INTRODUZIONE 9 apparati sensoriali al fine di ricavare una conoscenza più completa della realtà.
Figura 1.6: Localizzazione delle prede attraverso ecolocazione (Wikipedia).
In informatica lo stesso tipo di attività è denominata sensor fusion. Due o più sensori, spesso di natura completamente diversa, vengono usati insie-me per estrarre dall’ambiente delle informazioni non direttainsie-mente ricavabili dall’utilizzo individuale.
Negli ultimi anni gli algoritmi di fusione sensoriale hanno assunto un’im-portanza crescente in contesti di manipolazione dei dati in cui le applica-zioni richiedono prestaapplica-zioni più elevate, impossibili o troppo costose, per l’approccio sensoristico tradizionale (Figura 1.7). Inoltre ci sono contesti in cui l’unione di dati proveniente da differenti classi di sensori permette di ottenere rappresentazioni più dettagliate dell’ambiente sotto osservazione.
Applicazioni
Esistono diverse aree in cui la sensor fusion è attualmente impiegata. Un primo esempio è la tecnologia alla base delle immagini satellitari, che utilizza in modo consistente questo approccio per mescolare immagini pancromatiche e multispettrali.[5]
I sistemi informativi geografici (GIS) costituiscono un altro esempio. In questi sistemi la sensor fusion è impiegata per fondere i dati provenienti da un sistema di navigazione inerziale con le informazioni ottenute dal Global Positioning System (GPS) allo scopo di correggere il drift proveniente dal primo tipo di sensori [12].
Altra area d’interesse è lo sviluppo di sistemi di visualizzazione ad al-to dettaglio per la conduzione di veicoli in teleoperazione. Difatti quando un operatore deve manovrare questo tipo di veicoli necessita di una grande quantità di informazioni, ottenibile attraverso l’impiego di display che rice-vono dati complessi elaborati attraverso algoritmi di sensor fusion a partire da rilevamenti di sonar e sensori d’immagine [10].
CAPITOLO 1. INTRODUZIONE 10
Figura 1.7: Sistemi che fanno uso di algoritmi di sensor fusion (Semico Research).
CAPITOLO 1. INTRODUZIONE 11 Il monitoraggio delle condizioni di funzionamento dei macchinari indu-striali è un altro scenario di utilizzo tipico. Unendo i dati provenienti da sensori acustici, magnetici e di temperatura è possibile identificare i
mal-funzionamenti, permettendo così di prendere le dovute contromisure. Il
controllo delle condizioni ambientali è una variazione sullo stesso tema [14]. Con i sensori adeguati anche la medicina diagnostica può beneficiare della sensor fusion. Infatti, la fusione di immagini mediche di diversa natura costituisce uno strumento molto promettente per applicazioni cliniche [8].
Il campo della robotica è uno dei più interessati alle possibilità offerte dalla sensor fusion. I robot mobili autonomi necessitano di una serie di ca-pacità che li assistano nel riconoscimento e nella localizzazione di oggetti, nella navigazione e in altre attività analoghe. Per portare a termine questi compiti, gli algoritmi di sensor fusion sono tra gli approcci più adeguati, come confermato dal grande interesse che stanno riscuotendo in ambito di ricerca [14]. Molti studi presentano sistemi di navigazione per robot ba-sati sulla fusione sensoriale che costruiscono una rappresentazione interna dell’ambiente esplorato. Ad esempio, uno studio datato 2011 ha esplora-to le possibilità offerte dalla localizzazione attraverso segnali radio (RFID) raffinata dal contributo di un sensore ultrasonico [4].
1.3.2 Sistemi di stima software
Esistono alcuni progetti di ricerca che ricalcano gli obiettivi del presente lavoro pur differenziandosi in taluni aspetti che andremo ad esaminare. In [24] troviamo un metodo di navigazione basato su visione in ambienti indoor per robot autonomi in cui vengono utilizzati una telecamera e un sensore ultrasonico.
Nel sistema citato la navigazione è stata realizzata con un algoritmo di correzione di posizione retroattivo e, per evitare gli ostacoli, è stato adottato un duplice approccio: fondato sulla visione, attraverso un singola camera, per gli oggetti statici e basato sulle letture del sensore ultrasonico per quanto riguarda gli ostacoli in movimento.
Questa soluzione utilizza due sensori, attivi durante tutto il periodo ope-rativo, e svolge elaborazioni complesse ,come edge detection e filtraggio di Kalman, che richiedono una potenza di calcolo tale da escludere un’ampia parte di dispositivi embedded dai possibili candidati a ospitarla.
Nella stessa direzione procede il sistema realizzato in [15] dove si sono utilizzati un maggior numero di sensori e un ampio arsenale algoritmico come il filtraggio di Kalman, la teoria Dempster-Shafer, i sistemi a regole, le reti neurali e la logica fuzzy.
Il risultato è stato il raggiungimento di un livello di conoscenza più ele-vato rappresentato dalla produzione interna di una mappa dell’ambiente, dall’autolocalizzazione e dal riconoscimento degli oggetti al costo di una crescita esponenziale della complessità computazionale.
CAPITOLO 1. INTRODUZIONE 12 In [21] è proposto un algoritmo di stima della distanza a corto e lungo raggio di grande precisione e con un range operativo di centinaia di metri,
basato su visione stereoscopica. Le performance di rilievo, simulate con
il software MATLAB R, si pagano in termini di complessità algoritmica,
espressa in questo caso dal STKF (Short Tracking Kalman Filter ) e da un algoritmo custom per il miglioramento della disparity map.
Una soluzione molto simile a quella proposta è stata realizzata in [26]. Si tratta di un problema di auto-localizzazione di un robot in un ambiente chiuso, risolto misurando la distanza dello stesso da alcuni oggetti situati in posizioni predeterminate. Per il processamento è richiesto un modello degli oggetti da riconoscere, dei coni stradali arancioni nel caso in questione. Il sistema fondamentalmente fa uso degli algoritmi CAMSHIFT e POSIT per ricavare l’informazione di distanza. Dei due, il secondo è sicuramente più oneroso in termini computazionali poiché richiede aritmetica in virgola mobile; ciononostante si attesta su buoni livelli prestazionali [9].
1.4
AC range estimator
L’algoritmo di stima della distanza, denominato AC range estimator, svi-luppato e implementato autonomamente, offre il servizio di rilevamento con efficienza e portabilità significative rispetto alle altre soluzioni esaminate.
Utilizza una versione personalizzata dell’algoritmo CAMSHIFT e una funzione approssimante per fornire la stima della distanza. Il processamento è stato ottimizzato per ridurre al minimo i tempi operativi, usando una libreria software di computer vision sviluppata appositamente.
Il sistema non necessita di alcun modello dell’oggetto da riconoscere se non quello costruito dallo stesso nella fase di calibrazione.
La libreria sviluppata ha dipendenze esterne minimali e può essere adat-tata a qualsiasi sensore e dispositivo di output o attuatore per cui esistano API in linguaggio C, intervenendo sul codice sorgente con modifche nell’or-dine di 2 o 3 funzioni (per il collegamento con i driver). La quasi totalità del processamento è, inoltre, basato su aritmetica intera e può essere portato su sistemi privi di unità floating point che devono quindi simulare i calcoli in virgola mobile con significativi cali prestazionali.
La precisione mostrata è in linea con le caratteristiche dei sensori uti-lizzati e degli algoritmi implementati, con un margine di errore medio del 4.2%, valore che rende il sistema idoneo a contesti in cui la velocità nella risposta sia prioritaria rispetto all’accuratezza.
Capitolo 2
Descrizione del sistema
Il sistema utilizzato per la produzione della libreria software e per l’im-plementazione dell’algoritmo è costituito da due entità fondamentali: un notebook equipaggiato con Linux e il sensore composito Microsoft Kinect, ad esso collegato attraverso l’interfaccia USB.
La macchina utilizzata nelle fasi di sviluppo è stata scelta, volutamen-te, sottodimensionata da un punto di vista computazionale (Intel Pentium T4500) rispetto a quelle attuali (tra le quali spicca il processore Intel
i7-6950X, il più performante nella fascia consumer in data 10/2/2017). Il
divario prestazionale tra le due CPU si attesta intorno al 1488% [27]. La selezione di una tale configurazione è stata dettata dalla convenienza di rile-vare in maniera immediata un sottoinsieme delle possibili inefficienze intro-dotte da costrutti poco ottimizzati presenti nel codice. Nonostante questo non sia sufficiente a garantire buone prestazioni del software si è ritenuto utile disporre di una prima indicazione circa l’efficienza delle implementa-zioni realizzate. Sulla macchina girava il sistema operativo Linux Mint 17.3 “Rosa” (kernel 3.19.0-32-generic x86_64).
La libreria e l’algoritmo sono stati realizzati integralmente in linguaggio C, servendosi dell’ambiente di sviluppo Eclipse, configurato per operare con il compilatore GCC (GNU Compiler Collection) in versione 4.8.4. Il soft-ware non fa uso esplicito di accelerazione grafica; tutte le elaborazioni sono a carico della CPU. Questa scelta è stata dettata da uno degli obiettivi pre-fissati nella stesura del codice ovvero la possibilità di adattare al più vasto numero di sistemi le funzionalità della libreria.
2.1
Microsoft Kinect
Il Kinect è un sensore combinato disponibile sul mercato dal 2010 per console XboX R e rilasciato in versione PC nel 2012, corredato di uno speciale
adat-tatore precedentemente acquistabile a parte. A livello non ufficiale, però, lo sviluppo di applicazioni per PC da parte della comunità di appassionati
CAPITOLO 2. DESCRIZIONE DEL SISTEMA 14
Figura 2.1: Dispositivi a bordo del Kinect (MSDN).
e di aziende interessate, è iniziato nel dicembre 2010 grazie al rilascio di driver open source (per sistemi Windows e Linux) ad opera dell’azienda Pri-me Sense. SuccessivaPri-mente Microsoft ha rilasciato i suoi driver proprietari (esclusivamente per il proprio sistema operativo), in versione beta, finché nel giugno 2011 non ha definitivamente supportato il suo prodotto con i driver in versione finale.
Il prodotto integra i seguenti dispositivi, assemblati in un involucro plastico:
• Un sensore immagine nella banda della luce visibile (RGB) • Un sensore immagine nella banda dell’infrarosso
• Un proiettore nella banda infrarossa
• Quattro microfoni distribuiti, internamente, lungo il dispositivo • Un motore per spostamenti verticali del punto di vista (variazione
dell’orientamento angolare) • Un accelerometro
La camera RGB (Micron MT9V112, Figura 2.2(a)) cattura immagini a una risoluzione di 640x480 su tre canali sensibili al rosso, al verde e al blu a una frequenza massima di 30 frame al secondo. Il proiettore emette un fascio di luce nell’infrarosso, riflessa dall’ambiente e rilevata dal sensore ap-posito (d’ora in poi camera IR). Da questi dati il sistema estrae, punto per punto, la distanza dell’oggetto più vicino. La camera IR (Micron MT9M001, Figura 2.2(b)) lavora a una risoluzione massima di 1280x1024. Purtroppo, essendo un prodotto commerciale protetto da segreto industriale, il Kinect dispone di una documentazione ufficiale che non separa in maniera netta le caratteristiche fisiche dei sensori dalle limitazioni imposte dai driver, per cui le effettive modalità di utilizzo (prima fra tutte la risoluzione interna)
posso-CAPITOLO 2. DESCRIZIONE DEL SISTEMA 15 no essere definite in maniera esatta solo dai programmatori dei driver (open source ma soprattutto ufficiali) e gli utilizzatori del dispositivo possono ap-procciarsi al suo utilizzo accettando i vincoli imposti dalle API. Agli effetti esterni il sensore composito fornisce i due flussi video a una risoluzione di 640x480 con cadenza pari a 30 frame al secondo. Alcuni driver concedono l’accesso all’array di microfoni e al motore mentre l’accelerometro è usato esclusivamente per rilevare l’inclinazione del dispositivo. La precisione effet-tiva dipende dalla distanza rilevata e si attesta intorno a pochi millimetri, per oggetti molto vicini, e a circa 4 cm per oggetti situati al massimo range operativo. [16].
PARAMETER TYPICAL VALUE
Optical Format 1/6-inch (4:3)
Active Imager Size 2.30mm(H) x 1.73mm(V)
2.88mm Diagonal
Active Pixels 640H x 480V
Pixel Size 3.6µm x 3.6µm
Color Filter Array RGB Bayer Pattern
Shutter Type Electronic Rolling
Shutter (ERS) Maximum Data Rate/
Master Clock 12 MPS–13.5 MPS/24 MHz–27 MHz Frame Rate (VGA 640H x 480V) 30 fps at 27 MHz
ADC Resolution 10-bit, on-chip
Responsivity 1.0 V/lux-sec (550nm)
Dynamic Range 71dB
SNRMAX 44dB
Supply Voltage I/O Digital 1.7V–3.6V
Core Digital 1.7V–1.9V or 2.5V–3.1V (1.8V or 2.8V nominal) Analog 2.5V–3.1V (2.8V nominal) Power Consumption 76mW at 1.8V, 15fps Operating Temperature -30°C to +70°C
Packaging 36-Ball ICSP, wafer or die
(a)
Parameter Value
Optical format 1/2-inch (5:4) Active imager size 6.66mm(H) x 5.32mm(V) Active pixels 1,280H x 1,024V Pixel size 5.2µm x 5.2µm
Shutter type Electronic rolling shutter (ERS) Maximum data rate/
master clock 48 MPS/48 MHz Frame rate SXGA (1280 x 1024) 30 fps progressive scan; programmable ADC resolution 10-bit, on-chip Responsivity 2.1 V/lux-sec Dynamic range 68.2dB SNRMAX 45dB
Supply voltage 3.0V−3.6V, 3.3V nominal Power consumption 363mW at 3.3V (operating);
294mW (standby) Operating temperature 0°C to +70°C Packaging 48-pin CLCC
(b)
Figura 2.2: Datasheet del sensore RGB (a) e del sensore IR (b) in uso sulla Kinect
[18] [17].
La maggior parte delle informazioni disponibili su Kinect sono frutto di reverse engineering effettuato sul flusso dati USB in quanto né Micro-soft né Prime Sense hanno rilasciato documentazione dettagliata sul suo funzionamento.
I principali framework a disposizione per il Kinect sono 3: Microsoft SDK, OpenNI e OpenKinect. Il primo è l’unico ad essere disponibile esclu-sivamente per Windows e a non essere open source. Per scelta aziendale ha anche un range di funzionamento più ristretto (0.8m 4m) contro gli 0.5m -9m degli altri due (decisione motivata dall’imprecisione crescente del sensore in condizioni limite). In [23] è stata verificata la linearità della relazione tra distanza effettiva e valore restituito dal sistema, utilizzando il framework OpenNI, derivata dal processamento, da parte del framework, dei dati non
CAPITOLO 2. DESCRIZIONE DEL SISTEMA 16 lineari forniti dal sensore.
La scelta del framework da utilizzare per comandare l’acquisizione visua-le attraverso il Kinect è ricaduta su OpenKinect poiché offre visua-le funzionalità richieste dal progetto nel modo più diretto possibile (è scritta anch’essa in linguaggio C) ed è inclusa nella maggior parte delle distribuzioni Linux (cosa che facilita messa a punto e sperimentazione).
2.2
Architettura del sistema
Di seguito verrà illustrata l’architettura software (Figura 2.3) che implemen-ta l’algoritmo di stima, delegando a una tratimplemen-tazione successiva le funzioni di libreria sviluppate per supportarlo.
Model Sampler Calibration Unit object model Range Estimator estimation function Estimated Distance Depth feed RGB feed
Figura 2.3: Architettura software del sistema che realizza l’algoritmo.
Inizialmente il sistema si trova in uno stato di attesa in cui è attivo il blocco funzionale indicato Figura 2.3 con il nome di Model Sampler. Com-piendo una serie di scelte, che nel sistema realizzato sono interattive ma che nel passaggio al mondo embedded dovranno essere automatizzate secondo opportuni criteri, si costruisce un modello dell’oggetto campione sul quale effettuare le misurazioni di distanza. Il flusso di ingresso necessario a que-sta fase proviene dal sensore RGB e serve a definire le features richieste dal blocco successivo per individuare il bersaglio.
CAPITOLO 2. DESCRIZIONE DEL SISTEMA 17 Il campione passa alla Calibration Unit che riceve inoltre i dati dal sen-sore di profondità e da quello RGB. L’oggetto viene così tracciato e la sua distanza viene misurata in ogni istante. Nel modulo è presente un campiona-tore che, all’attivazione, estrae delle misurazioni di distanza e le memorizza congiuntamente a una delle caratteristiche visuali dell’immagine. I dati rac-colti vengono processati da una sotto-unità algebrica che ricava una funzione analitica, approssimante la relazione che lega la distanza e la caratteristica visuale prescelta. Questa funzione, in figura identificata come estimation function, costituisce l’output del blocco.
Il Range Estimator è il componente finale del sistema e ha il compito di esaminare il flusso RGB in ingresso, tracciando l’oggetto modello nella scena. La caratteristica visuale viene misurata su di esso e data come argomento alla estimation function che quindi restituisce il corrispondente valore di distanza ovvero l’approssimazione dell’effettiva distanza tra il sensore di profondità (che in questa fase è disattivato) e l’oggetto stesso.
2.3
Il formato immagine interno
Tutte le immagini processate dalla libreria vengono convertite, durante l’ac-quisizione da parte del sottosistema di I/O, in un formato interno (Figu-ra 2.4) che prevede una memorizzazione sepa(Figu-rata per i tre canali. Questi sono memorizzati per intero in tre distinte zone di memoria. Tale scelta è motivata dal fatto che molti degli algoritmi implementati agiscono su imma-gini monocromatiche che con questo tipo di memorizzazione corrispondono esattamente al singolo canale di una intera immagine. Senza ricorrere a conversioni è dunque possibile manipolare i singoli canali, mantenendo al contempo la migliore ottimizzazione possibile relativamente allo spazio di memoria occupato e al tempo di accesso.
(a) canale 1 (b) canale 2 (c) canale 3 (d) canale mask
Figura 2.4: Canali che compongono un’immagine: (a), (b) e (c) sono i tre canali
immagine, in questo caso in formato BGR, (d) è il canale binario di maschera. I canali sono visualizzati con delle tinte di colore; in realtà vanno immaginati mono-cromatici e le tonalità di rosso, verde e blu utilizzate sono da considerarsi semplici ausili a dedurre cosa rappresentano i singoli canali all’interno dell’immagine.
CAPITOLO 2. DESCRIZIONE DEL SISTEMA 18 Il formato immagine prevede un ulteriore canale, detto mask channel, che contiene informazioni su quali pixel sono considerati “mascherati” ov-vero esclusi dalle elaborazioni funzionali. Questa entità è stata realizzata in formato compresso, in modo da minimizzare l’occupazione in memoria (1 bit per pixel) e i relativi tempi di accesso.
2.4
Ingresso e uscita
Per ottenere i dati d’ingresso e fornire i suoi risultati il sistema necessita di un comparto di I/O capace di catturare dei flussi video ed eventualmente vi-sualizzarli. Questo sottosistema è realizzato in maniera modulare per poter essere esteso a ospitare tipi di ingresso e di uscita aggiuntivi. Attualmente in ingresso il sistema supporta il sensore Microsoft Kinect, attraverso la libreria freenect, implementazione del progetto OpenKinect e i tradizionali sensori immagine RGB, attraverso la libreria OpenCV. In uscita invece il supporto è concentrato sulla gestione dello schermo effettuata dalla libreria OpenCV. E’ importante sottolineare che, nonostante OpenCV costituisca il principale riferimento tout-court in tema di computer vision, in questa sede viene uti-lizzato esclusivamente per disporre di un rapido accesso ai sensori immagine e alle funzionalità di output su PC. Tutto il software è basato sulla libreria appositamente realizzata e i riferimenti a OpenCV possono essere sostituiti con gli strati software di gestione dei sensori dei sistemi sui quali viene ese-guito l’algoritmo. In particolare, quello che viene richiesto al programmatore che vuole effettuare un porting del sistema su una piattaforma arbitraria è la stesura del codice che converte le immagini dal formato interno a quello definito per i driver dei sensori e degli eventuali visualizzatori.
2.4.1 Flussi video
I flussi video in ingresso al sistema, come visto, sono due: uno di tipo RGB, catturato dal sensore immagine, e uno di tipo depth, generato, nella configurazione scelta, dal sistema proiettore/sensore IR.
Nel sistema utilizzato i flussi d’ingresso possono essere gestiti da CV, che gestisce le normali webcam presenti nel sistema, oppure da Open-Kinect, che supporta sia il flusso RGB sia il flusso depth, esclusivamente sul dispositivo in questione. Entrambe le interfacce software forniscono tre byte per ogni pixel del frame catturato; il formato è BGR (per OpenCV) o RGB (per OpenKinect), relativamente al sensore immagine. Per quanto riguarda il flusso depth, vengono restituiti due byte per ogni pixel con i quali si rappresenta la sua distanza dal piano del sensore, espressa in millimetri. La libreria effettua le conversioni nel formato interno: nel primo caso sul canale 1 va il blu, sul canale 2 il verde e sul canale 3 il rosso, nel secondo caso sul canale 1 va la parte meno significativa delle distanze, sul canale 2
CAPITOLO 2. DESCRIZIONE DEL SISTEMA 19 quella piu significativa. Le maschere vengono aggiustate in modo che le im-magini RGB abbiano tutti i pixel non mascherati mentre le imim-magini depth abbiano mascherati i pixel per i quali non sono disponibili informazioni sulla distanza (ciò avviene, ad esempio, per oggetti fuori portata o per superfici che mettono in difficoltà il sensore).
In uscita è presente il solo supporto offerto da OpenCV. Le funzioni che si occupano di questa operazione hanno il compito di convertire le im-magini dalla rappresentazione interna al formato supportato da OpenCV, delegando poi a questo le operazioni di visualizzazione a video. Questo pas-saggio non è necessario durante l’esecuzione su sistemi embedded privi di interfacce di visualizzazione. In questo caso i flussi di uscita possono essere semplicemente ignorati. Un piccolo ausilio alla progettazione è fornito dal-l’implementato supporto alla stampa di stringhe di caratteri, sovraimpresse al video visualizzato.
2.5
Il Model Sampler
Questo blocco funzionale si occupa della segmentazione di un frame al fine di estrarre un modello dell’oggetto che verrà utilizzato come riferimento della distanza da misurare. Il suo unico ingresso è il flusso video RGB.
La segmentazione è un processo tipico della computer vision che si oc-cupa di attribuire certe caratteristiche predefinite a sottoinsiemi diversi di pixel presenti in una immagine. Al termine di questa operazione si disporrà di una serie d’insiemi che identificano entità diverse a seconda delle features specificate. E’ possibile ad esempio specificare delle caratteristiche cromati-che cromati-che individuano un oggetto nella scena ed effettuare una segmentazione che contrassegna i pixel ad esso appartenenti, distinguendoli dagli altri.
Nel blocco, in prima istanza, viene costruito, a partire da un insieme di frame, un modello dello sfondo. Durante questa procedura il sensore imma-gine deve inquadrare una scena priva dell’oggetto da rilevare e il più statica possibile. Al termine si può mostrare l’oggetto al sistema, che provvederà a “staccarlo” dallo sfondo. Questa operazione è nota con il nome di background subtraction (Figura 2.5).
L’algoritmo utilizzato in questo progetto è una versione personalizzata del Running Gaussian average [28]. Proposto da Wren et al. in [33], l’algo-ritmo prevede di associare ad ogni pixel una densità di probabilità di tipo gaussiano e nello specifico i suoi valori di media e deviazione standard. Per calcolare tali valori si utilizza una running average ovvero una combinazione lineare di una precedente valutazione della stessa e dell’ultimo valore rileva-to. Questo permette di ottimizzare lo spazio in memoria che dal prevedere n valori precedenti per ogni pixel, per il calcolo usuale della media, si riduce a richiederne due. L’algoritmo viene esaminato in dettaglio al paragrafo 3.2.1.
CAPITOLO 2. DESCRIZIONE DEL SISTEMA 20
Figura 2.5: Schematizzazione del processo di background subtraction [25].
L’insieme di pixel ottenuti dalla segmentazione rappresenta, a tutti gli effetti, il modello dell’oggetto campione.
2.6
La Calibration Unit
L’unità di calibrazione ha il compito di mettere in relazione una caratte-ristica dimensionale della proiezione dell’oggetto modello sul piano della telecamera con la distanza del suo centro dal sensore di profondità. La re-lazione così costruita viene passata al blocco successivo e usata per le stime di distanza.
2.6.1 Conversioni colore e istogramma
Ottenuto l’insieme dei pixel che costituisce il modello dell’oggetto si può procedere all’estrazione di una rappresentazione utile dello stesso. La scelta è ricaduta sull’utilizzo di un modello cromatico che implica l’identificazione attraverso il colore dei pixel. L’informazione di colore, nel formato RGB, è però distribuita sui tre canali e questa dispersione ne rende più difficile l’estrazione. Inoltre, nell’implementazione scelta, questo formato richiede l’accesso a tre diverse locazioni di memoria, per ogni pixel, con conseguente aggravio computazionale. E’ necessario, infatti, porre la massima attenzione a non appesantire le operazioni sul pixel, in quanto sono quelle che più incidono sulle performance, poiché ripetute centinaia di migliaia di volte per ogni singola immagine, già alle medie risoluzioni.
Per ovviare a questo inconveniente i pixel del modello vengono convertiti in una rappresentazione HSV (Hue, Saturation, Value) (di cui si può osser-vare un esempio in Figura 2.6) attraverso una trasformazione algebrica. La componente hue (o tinta) conterrà l’informazione di colore e sul relativo canale verrà costruito un istogramma immagine, cioè una rappresentazione della sua distribuzione tonale.
CAPITOLO 2. DESCRIZIONE DEL SISTEMA 21
(a) (b) hue
(c) saturation (d) value
Figura 2.6: Scomposizione dell’immagine in (a) nei tre canali componenti dello
CAPITOLO 2. DESCRIZIONE DEL SISTEMA 22 Ottenuto il canale di tinta si esegue la normalizzazione dell’istogramma costruito dal Model Sampler. Questa modifica comporta l’aggiunta di un ulteriore semantica ai valori in esso contenuti. Infatti, normalizzando i valori dell’istogramma all’intervallo [0, 1], questi si possono interpretare come la probabilità che un certo valore di tinta appartenga all’oggetto modello.
2.6.2 Back projection e CAMSHIFT
La back projection effettua una sostituzione di pixel in un’immagine mono-cromatica. Prende in ingresso un’immagine e un istogramma e sostituisce ogni pixel col valore di probabilità letto sull’istogramma, in corrispondenza della sua intensità. Questa tecnica costruisce una matrice di valori di pro-babilità che, ri-scalata a 255, fornisce una nuova immagine monocromatica in cui ogni pixel è tanto più luminoso quanto più è alta la sua probabilità di adattarsi all’istogramma fornito (Figura 2.7).
Figura 2.7: Un esempio di back projection e ri-scalatura (Wikipedia).
Se l’istogramma viene costruito sull’oggetto modello allora la back pro-jection genera un’immagine in cui i pixel più luminosi sono quelli con mag-giore probabilità di appartenere ad esso.
A questo punto interviene un’importante algoritmo di tracciamento og-getti, molto usato in computer vision, conosciuto come CAMSHIFT [1]. Sfruttando il risultato delle operazioni di back projection, l’algoritmo si sposta in maniera iterativa sull’immagine, seguendo la direzione di massima crescita del gradiente, fino a convergere al punto di massima probabilità, e
CAPITOLO 2. DESCRIZIONE DEL SISTEMA 23 ridimensionando una finestra di ricerca in maniera opportuna. Il risultato è un algoritmo di object tracking robusto ed efficiente, idoneo anche a lavorare in real-time. [22].
I servizi offerti dall’algoritmo di CAMSHIFT comprendono anche il cal-colo dell’ellisse che meglio racchiude i punti di massima probabilità e la sua inclinazione. Queste informazioni sono state considerate poco utili ai fini del rilevamento della distanza ed escluse dall’implementazione, che ha puntato ad ottenere la massima efficienza.
Il sistema utilizza una finestra di tracciamento quadrata, quindi gli ogget-ti migliori da selezionare come modelli, sono quelli invarianogget-ti alle rotazioni.
2.6.3 Campionamento e funzione di stima
Il tracciamento dell’oggetto permette di conoscerne la posizione sul piano dell’immagine e quindi di avere un riferimento per il sensore di profondità. Il punto centrale dell’oggetto è quello selezionato per il rilevamento della di-stanza. A questo punto può entrare in azione il campionatore della distanza che colleziona una serie di coppie distanza/dimensione. Durante questa fase l’oggetto modello deve spostarsi, avvicinandosi e allontanandosi dal sensore, possibilmente su tutto il range operativo. La dimensione apparente dell’og-getto selezionata per essere associata alla distanza e rilevata successivamente per la ricostruzione è la sua area. Le coppie citate quindi avranno la natura di distanza/area. Al termine del campionamento si disporrà di una lunga lista di coppie che tuttavia conterrà un piccolo sottoinsieme dei possibili va-lori di distanza rilevabili dal sensore di profondità. Per completare il sistema è necessario colmare queste lacune e l’approccio scelto si basa su una tecnica di regressione non lineare.
A partire dai campioni raccolti si procede alla ricerca di una funzione che riesca ad approssimare nel modo più preciso possibile l’andamento delle coppie rilevate. E’ stato impiegato, a tale fine, il metodo dei minimi qua-drati, implementato in modo da permettere la scelta delle funzioni utilizzate per l’approssimazione. Osservando l’andamento dei dati raccolti e il tipo di relazione intercorrente tra essi, si scelgono alcune tipologie di queste fun-zioni e dall’esecuzione del metodo si ottengono i coefficienti che rendono la combinazione lineare delle funzioni approssimanti la migliore approssima-zione della funapprossima-zione cercata nel senso dei minimi quadrati. Questa funapprossima-zione, indicata in Figura 2.3 come estimation function, viene passata allo stadio successivo.
2.7
Il Range Estimator
La struttura di questo blocco è la più semplice poiché si dispone ormai di tutte le informazioni necessarie a mettere in esercizio il sistema. Utilizzando
CAPITOLO 2. DESCRIZIONE DEL SISTEMA 24 la estimation function si ricava la distanza esaminando l’area della proiezione dell’oggetto sul piano dell’immagine.
Capitolo 3
AC range estimator
L’algoritmo di stima della distanza realizzato nel presente lavoro è stato de-nominato AC (Area Coverage) range estimator poiché utilizza l’area della finestra di tracciamento di un oggetto su un piano immagine bidimensiona-le per fornire un’indicazione di distanza dello stesso dal sensore immagine responsabile della cattura.
Poiché l’operazione di stima in sé è ridotta al calcolo del valore di una combinazione lineare di lunghezza indipendente dalle variabili operative (complessita computazionale pari a O(1)) le operazioni interessanti sono concentrate nelle fasi di costruzione della combinazione stessa e in quelle di reperimento delle informazioni necessarie a tale fine. In questo capitolo, do-po un’analisi dei vantaggi di un sistema a singola telecamera, verranno ana-lizzate tali operazioni, evidenziando come contribuiscono al raggiungimento dell’obiettivo finale.
3.1
La stima con telecamera singola
Come evidenziato nella disamina dei sistemi di rilevamento software effet-tuata al paragrafo 1.3 esistono diversi modi di combinare una serie di sensori per ricavare una misura di distanza di oggetti inquadrati. Quando però si considera il contesto embedded, destinazione auspicata per l’algoritmo svi-luppato, emerge un’esigenza che in altri contesti spesso non ha la stessa rilevanza ovvero l’efficienza energetica. Un sistema integrato è tanto più efficace nel suo contesto operativo quanto più riesce a funzionare autono-mamente e se non è dotato di sufficiente energia necessita di interventi più frequenti, creando un innalzamento dei costi di manutenzione.
Altra caratteristica dei sistemi integrati è la loro pervasività e questo ne rende necessaria la costante riduzione dimensionale. L’ingombro può essere un fattore determinante a seconda dei contesti e i sistemi che svolgono le stesse funzioni occupando meno spazio tendono a diffondersi con più facilità sul mercato.
CAPITOLO 3. AC RANGE ESTIMATOR 26 Inoltre, dovendo essere prodotti su larga scala e a prezzi altamente com-petitivi, i sistemi embedded benificiano anche delle più piccole riduzioni di costo, favorite da un minor numero di dispositivi a bordo. Laddove po-chi euro di differenza sembrano irrilevanti si gioca la partita tra sistemi di successo e soluzioni dimenticate.
L’adozione di un algoritmo basato su singola telecamera risponde a que-ste esigenze poiché si adatta a sique-stemi che da un lato possono depennare una serie di sensori dal computo delle componenti che assorbono energia, dall’al-tro si riducono dimensionalmente e nel peso e possono aggredire il mercato con prezzi più accattivanti.
Il sistema presentato offre il vantaggio dell’efficienza energetica poiché dopo la fase di calibrazione gli eventuali sensori aggiuntivi possono essere spenti (se i dispositivi lo consentono) e può offrire gli altri due se supportato da un hardware distinto per la fase di calibrazione e quella operativa, in modo, ad esempio, che la telecamera RGB possa staccarsi del resto del sistema e operare indipendentemente, una volta completata la calibrazione iniziale.
3.2
Segmentazione
La segmentazione è quel processo di partizionamento di un’immagine che consente di isolare oggetti o parti di oggetto presenti nella scena. Viene usata spesso per separare oggetti di interesse da uno sfondo o per selezionare parti specifiche di una certa entità come il viso o gli arti di una persona. Lavorando sulle parti invece che sull’intera immagine è anche possibile ridurre il carico computazionale poiché i pixel da esaminare si riducono considerevolmente in numero.
La background subtraction è una tecnica di segmentazione finalizzata a separare un insieme di pixel considerati di sfondo da un sottoinsieme di pixel che rappresenta un’entità d’interesse. Esistono numerosi metodi per eseguire questa operazione, tutti basati sulla stima del modello dello sfondo ricavata da una sequenza temporale di fotogrammi. In [28] sono elencati i metodi più usati che sono, dal più semplice al più complesso:
• Running Gaussian average • Temporal median filter • Mixture of Gaussians
• Kernel Density Estimation (KDE) • Sequential KD aproximation • Cooccurrence of image variations • Eigenbackgrounds
Tra loro, l’unico ad avere una complessità O(1) sia in tempo di ese-cuzione sia in occupazione di memoria è il Running Gaussian average, con
CAPITOLO 3. AC RANGE ESTIMATOR 27 un’accuratezza pari o inferiore a tutti gli altri [28], considerata soddisfacente per il ruolo che l’algoritmo ricopre nel sistema progettato.
3.2.1 Running Gaussian average
Questo metodo, proposto in [33], prevede di modellizzare il background a livello puntuale ovvero di conservare un informazione di background singo-larmente per ogni pixel, senza fare riferimento, ad esempio, ai pixel adiacenti. Per ogni pixel si calcolano la media e la deviazione standard ma, invece di operare come di consueto, ovvero disponendo di un certo numero di valo-ri, si procede con una calcolo cumulativo, durante l’esecuzione, utilizzando soltanto l’ultimo valore rilevato e la media precedente, secondo la seguente equazione:
µt= αIt+ (1 − α)µt−1 (3.1)
dove µt rappresenta la media corrente, It il valore di intensità del
pi-xel e µt−1 la media calcolata al passo precedente. Il valore α costituisce
un peso empirico scelto come compromesso tra la stabilità e la velocità di aggiornamento del modello.
In originale non viene esplicitamente descritto il metodo per il calcolo della deviazione standard, che è, quindi, stato ricavato per similitudine:
σt= α|It− µt| + (1 − α)σt−1 (3.2)
Disponendo di entrambi i valori, per ogni pixel, si può procedere al-la fase di segmentazione vera e propria, realizzata esaminando al-la seguente disequazione:
|It− µt| > kσt (3.3)
e considerando il pixel come appartenente al foreground se vale. In caso contrario il pixel verrà classificato come background.
L’algoritmo procede all’aggiornamento dello sfondo, con le equazioni vi-ste, a cadenza regolare e questo comporta il fatto che un oggetto lasciato per il tempo sufficiente nell’inquadratura, si fonde con lo sfondo. Per ovviare a questo problema esiste un’estensione, presentata in [19] e detta selective background update, che prevede di saltare l’aggiornamento dello sfondo per i pixel che sono stati classificati come foreground. Nel sistema l’algoritmo deve operare per il tempo necessario a catturare l’immagine dell’oggetto model-lo dunque, dopo un’iniziale acquisizione delmodel-lo sfondo, l’aggiornamento può essere disattivato, mantenendo attiva soltanto la sezione di segmentazione data dall’equazione 3.3.
CAPITOLO 3. AC RANGE ESTIMATOR 28
3.3
Object tracking
Le tecniche di object tracking hanno come obiettivo quello di inseguire un oggetto nei frame consecutivi di un flusso video. Questo compito è reso diffi-cile dalla necessità di individuare l’orientamento dell’oggetto che, proiettato sul piano bidimensionale dell’immagine, fornisce una figura di forma variabi-le. Gli algoritmi che adempiono a queste necessità devono, dunque, disporre di una rappresentazione delle caratteristiche tridimensionali dell’oggetto da tracciare. É altresì vero che particolari simmetrie riscontrabili nella geo-metria degli oggetti da tracciare possono semplificare notevolmente queste operazioni come accade, ad esempio per gli oggetti sferici, che conservano una forma proiettata invariabile.
Il problema del tracciamento degli oggetti è strettamente correlato al-la loro individuazione (object detection), che in aggiunta alle problematiche condivise con il primo, deve operare senza la semplificazione di disporre dell’informazione di localizzazione derivante dai frame precedenti. In ef-fetti quando si vuole tracciare un oggetto è necessario prima individuarlo, dunque, formalmente, devono agire in sequenza gli algoritmi di object de-tection e quelli di object tracking. Alcuni algoritmi, tra cui Mean Shift e CAMSHIFT, adempiono a entrambe le necessità. Le maggiori difficoltà af-frontate nel problema dell’individuazione si traducono nella tendenza a una minore efficienza temporale rispetto alle soluzioni algoritmiche che operano nell’ambito del tracciamento. I principali algoritmi sono basati sui seguenti argomenti:
• Flusso ottico (denso e sparso) • Filtraggio di Kalman
• Scalata del gradiente
Gli algoritmi di scalata del gradiente lavorano su particolari mappe di den-sità che devono essere preventivamente costruite.
3.3.1 Conversione di spazio colore
Al fine di costruire un istogramma dell’immagine modello, per poterlo utiliz-zare con l’algoritmo di back projection sull’immagine oggetto di scansione, è necessario disporre di un canale che contenga l’informazione cromatica con la quale si è deciso d’identificare l’oggetto. Nella rappresentazione RGB l’in-formazione sul colore è distribuita su tutti e tre i canali quindi è opportuno trasformare le coordinate colore dallo spazio RGB ad uno spazio nel quale invece sia sufficiente esaminare un canale per ricavare i dati sul colore. Uno di questi è lo spazio conico HSV, composto dai valori di hue, saturation e value e selezionato come spazio d’arrivo della trasformazione colore in esa-me. In Figura 3.1 è possibile osservare gli spazi di origine e destinazione della trasformazione colore.
CAPITOLO 3. AC RANGE ESTIMATOR 29
(a) Spazio RGB (Wikimedia Commons) (b) Spazio HSV (Wikipedia UK)
Figura 3.1: Notare come in (a) il colore varî spostandosi su una qualsiasi
del-le coordinate mentre nello spazio (b) soltanto variando l’angolo percorso dalla componente hue si verifichi una variazione della tinta.
A partire da un pixel PRGB = (r, g, b), con valore delle componenti che
varia nell’intervallo [0, 1], la trasformazione fornisce l’equivalente proiettato nello spazio colore HSV, PHSV = (h, s, v).
Definiti M = max(R, G, B) m = min(R, G, B) ¯ r = M − R M − m g =¯ M − G M − m ¯ b = M − B M − m le componenti si ottengono mediante le seguenti formule
v = M s = M − m M h = 16 · ( 5 + ¯b, se m = g 1 − ¯g, altrimenti, se M = r ( 1 + ¯r, se m = b 3 − ¯b, altrimenti, se M = g ( 3 + ¯g, se m = r 5 − ¯r, altrimenti, se M = b (3.4)
Al termine dell’operazione si dispone di una rappresentazione HSV del-l’immagine e si può esaminare il canale di tinta (un esempio, svincolato dal progetto, in Figura 3.2) per costruire un istogramma dell’oggetto modello.
3.3.2 Istogramma immagine
Le immagini digitali sono composte, come noto, da un certo numero di pixel, di colori differenti. Il modo in cui i colori sono distribuiti sul piano le
caratte-CAPITOLO 3. AC RANGE ESTIMATOR 30
Figura 3.2: Ingrandimento del canale hue ripreso dal paragrafo 2.6.1. Le diverse
CAPITOLO 3. AC RANGE ESTIMATOR 31 rizza in maniera significativa. Se si considera un’immagine monocromatica di 8 bit per pixel si disporrà di una matrice di valori presi dall’interval-lo [0, 255]. Un istogramma immagine è una tabella che contiene l’insieme dei possibili valori d’intensità disponibili per un pixel e il relativo conteg-gio, inteso come occorrenze di quel valore nella matrice. Per un’immagine monocromatica, ad esempio, la tabella conterrà 256 voci (dette bins). La somma delle altezze di tutte le bins restituirà il conteggio totale dei pixel dell’immagine. É anche possibile scalare l’altezza delle bins in modo tale che la loro somma sia pari a 1. In questo caso si parla di istogramma nor-malizzato e l’altezza di ogni singola bin rappresenta la frazione di pixel che ha una certa tonalità (Figura 3.3).
0 50 100 150 200 250 0 2,000 4,000 6,000 bins # pixel s (a) 0 50 100 150 200 250 0 2 4 6 8 bins % of pixel s (b)
Figura 3.3: Un esempio d’istogramma immagine in (a) e la sua versione normalizzata in (b).
Se si costruisce l’istogramma esclusivamente sui pixel che rappresentano l’oggetto modello si otterrà, di fatto, la densità di probabilità discreta di una variabile aleatoria I ∈ [0, 255], definita come l’intensità di un pixel qualsiasi dell’oggetto modello.
pI(z) = P (I = z), per z ∈ I (3.5)
3.3.3 Back Projection
La back projection ([20, p 102]) è una tecnica che permette di misurare quanto i pixel di un’immagine si adattino alla distribuzione di pixel di un istogramma. Si esegue sostituendo ogni pixel di un immagine con il valore di probabilità letto sull’istogramma in corrispondenza dell’intensità rilevata per il pixel. Ad esempio, se un pixel ha intensità pari a 113, si esamina l’istogramma e si legge il valore di probabilità in corrispondenza della bin 113, riportando poi il valore, sull’immagine originale, alle stesse coordinate, previa un’operazione di ri-scalatura a 255 (Figura 3.4).
