Università degli Studi di Padova
Facoltà di Ingegneria
Dipartimento di Ingegneria dell’Informazione
Tesi di Laurea Magistrale in Ingegneria Informatica
Sistema software per la stima della posa
di oggetti industriali da dati
tridimensionali
Laureando Relatore
Nicolò Frezzato
Prof. Emanuele Menegatti
Correlatore
Stefano Tonello
15 Aprile 2014
Dedica...
Sommario
Lo scopo del presente lavoro è sviluppare un algoritmo per individuare la posa di oggetti utilizzando point cloud tridimensionali ottenute con un sistema di triangolazione laser. La posa 6DOF viene individuata utilizzando un algoritmo per il riconoscimento di oggetti basato su PCL (Point Cloud Library). Tale algoritmo è sviluppato per essere utilizzato in un sistema industriale per bin picking.
La soluzione proposta per il riconoscimento di oggetti si basa su corre-spondences grouping, in particolare, utilizzando una versione della GHT (Ge-neralized Hough Transform) estesa allo spazio tridimensionale. L’algoritmo proposto è stato confrontato con una soluzione che utilizza, in combinazio-ne, clustering e registrazione di point cloud, attualmente utilizzata in campo industriale.
Indice
Introduzione 1
1 Sistema per bin picking 3
1.1 Cos’è il bin picking . . . 4
1.2 Componenti del sistema . . . 4
1.3 Sistema di visione . . . 5
1.4 Sistema Software . . . 6
1.4.1 Smart Pick 3D . . . 6
1.4.1.1 Esecuzione offline e dump . . . 7
1.4.2 Point Cloud Library . . . 8
1.4.2.1 Versione 1.7 . . . 10
1.5 OpenMP API . . . 10
2 Il riconoscimento 13 2.1 Definizione del problema . . . 14
2.1.1 Input . . . 14
2.1.2 Output . . . 16
2.2 Riconoscimento basato su registrazione . . . 16
2.3 Riconoscimento basato su correspondence grouping . . . 18
2.3.1 Keypoint . . . 19
2.3.1.1 SIFT Keypoint . . . 20
2.3.1.2 Uniform Keypoints . . . 20
2.3.2 Descrittori . . . 21
2.3.2.1 FPFH (Fast Point Feature Histogram) . . . . 22
2.3.2.2 SHOT352 (Signature of Histograms of Orien-Tations) . . . 23
2.3.2.3 BOARD LRF (Local Reference Frame) . . . . 23
2.3.3 Corrispondenze . . . 24
2.3.4 Correspondence grouping . . . 26
2.3.4.1 Hough 3D Grouping . . . 27
2.3.5.1 Pre-validazione . . . 30
2.3.6 Allineamento finale . . . 31
2.3.6.1 Validazione . . . 32
3 Algoritmi 35 3.1 Algoritmo 1: clustering + registrazione . . . 35
3.1.1 Analisi . . . 35
3.2 Algoritmo 2: correspondence grouping . . . 37
3.2.1 Versione parallelizzata . . . 38
3.2.2 Parametri . . . 39
4 TestFramework 41 4.1 Analisi dei requisiti . . . 41
4.2 Architettura . . . 41 4.3 Interfaccia Grafica . . . 43 5 Prestazioni e Risultati 45 5.1 Oggetti e dataset . . . 46 5.1.1 Prodotto A . . . 46 5.1.2 Prodotto B . . . 46 5.1.3 Prodotto C . . . 47 5.1.4 Dataset . . . 47 5.2 Configurazione . . . 48 5.2.1 Configurazione prodotto A . . . 48 5.2.2 Configurazione prodotto B . . . 48 5.2.3 Configurazione prodotto C . . . 49
5.3 Test 1: rate di riconoscimento . . . 49
5.4 Test 2: numero di cicli . . . 50
5.4.1 Configurazione . . . 50
5.4.2 Risultati prodotto B . . . 50
5.4.3 Risultati prodotto C . . . 50
5.5 Test 3: valutazione speedup . . . 51
Indice ix
Introduzione
Negli ultimi anni sono stati fatti grandi progressi nel campo della computer vision applicata alla robotica industriale. Lo studio di sistemi di visione per robot in campo industriale è stato, infatti, incentivato da diversi fattori come, ad esempio, l’implementazione di algoritmi per l’elaborazione di immagini e dati tridimensionali sempre più efficaci e ottimizzati, la diminuzione del costo di hardware dotato di grande potenza di calcolo e sensori di visione sempre più precisi ed economici.
Sistemi industriali robotizzati sprovvisti di un sistema di visione non han-no la percezione dell’ambiente, hanhan-no quindi la necessità di un contesto strut-turato e ben definito per operare correttamente. Tale vincolo influenza l’inte-ra catena di produzione in quanto è necessario studiare soluzioni ad hoc per manipolare i prodotti tra una fase della produzione e la successiva. Questo tipo di sistemi non è vantaggioso ad esempio per situazioni in cui si produco-no quantitativi limitati di diverse tipologie. Spesso, infatti, durante alcune fasi della produzione vari tipi di prodotti vengono depositati alla rinfusa in contenitori.
Un sistema dotato di percezione è configurabile per la lavorazione di diver-se tipologie di oggetti diver-senza la necessità di sviluppare sistemi di caricamento adattati ad ogni prodotto.
Nel presente elaborato si focalizza l’attenzione sull’individuazione della posa di oggetti disposti alla rifusa in un contenitore in modo da consentirne la manipolazione da parte di un robot. La stima della posa avviene attraverso algoritmi di visione per il riconoscimento di oggetti in scansioni tridimensio-nali ottenute con un sistema di triangolazione laser. Questo task fa parte del problema del bin picking.
A tale scopo è stato sviluppato un algoritmo per il riconoscimento di og-getti basato su correspondence grouping sfruttando PCL (Point Cloud Libra-ry), un framework open-source per la manipolazione e l’elaborazione di strut-ture dati tridimensionali, su cui sono basate un gran numero di applicazioni utilizzate nel campo della robotica.
al riconoscimento alternativo rispetto a quello esistente (basato su clustering e registrazione), utilizzato in un software dedicato al bin picking corrente-mente sfruttato in sistemi di produzione industriali. Proprio l’introduzione di un secondo algoritmo ha motivato l’implementazione di un framework per testare le diverse configurazioni del software e confrontare i risultati ottenuti con i due diversi algoritmi di riconoscimento.
Capitolo 1
Sistema per bin picking
6DOF è l’acronimo di sei gradi di libertà (Six Degrees Of Freedom) e si riferisce al movimento nello spazio tridimensionale, ovvero l’abilità di traslare liberamente avanti/indietro, in alto/in basso, sinistra/destra (traslare in tre assi perpendicolari); i movimenti di traslazione possono essere combinati a rotazioni attorno ai tre assi (imbardata, beccheggio, rollio).
Figura 1.1: Rappresentazione dei tre possibili movimenti di traslazione e i tre movimenti di rotazione
1.1
Cos’è il bin picking
Il problema del bin picking consiste nell’individuare e prelevare, degli ogget-ti posogget-ti alla rinfusa all’interno di un contenitore (bin) uogget-tilizzando un robot manipolatore. La soluzione generale al problema è complessa e consiste nel-l’essere in grado di individuare e manipolare oggetti senza che il sistema ne conosca la forma a priori. Per questo motivo si semplifica il problema operando riconoscimento e prelievo di oggetti di cui si conosce la forma. I campi di applicazione sono molteplici, specialmente in ambito industriale. Ad esempio, nei sistemi di packaging, nell’assemblaggio o in particolari fasi della lavorazione i componenti escono da fasi di lavorazione precedenti in contenitori disposti alla rinfusa.
Il sistema per bin picking deve eseguire le seguenti operazioni:
1. Acquisire dati, cioè ottenere una scansione tridimensionale del conte-nitore.
2. Identificare oggetti, cioè rilevare la posa esatta degli oggetti nel conte-nitore.
3. Prelevare e estrarre un oggetto dal contenitore.
Si possono identificare quindi tre componenti fondamentali del sistema: un sistema di visione, un sistema che si occupa dell’identificazione e loca-lizzazione degli oggetti, un robot manipolatore che si occupa del prelievo dell’oggetto dal contenitore.
1.2
Componenti del sistema
Il sistema per bin picking utilizzato è composto principalmente da:
• Sistema di visione: è il sistema di acquisizione dati, composto da telecamere o altri sensori e dall’illuminazione (laser, luce strutturata). • Supporto per sistema di visione: può essere fisso (telecamere 2D)
o mobile (per scansioni 3D) ad esempio montato su un robot. • Bin o contenitore: contiene gli oggetti o i prodotti da prelevare. • Braccio robotico o manipolatore: è dotato di una uno strumento di
presa, intercambiabile a seconda dei prodotti da prelevare (6/8 g.d.l). • PLC: si occupa di mettere in comunicazione e sincronizzare i vari
1.3. Sistema di visione 5
• Computer: utilizzato per l’esecuzione degli algoritmi di visione, com-putazionalmente troppo complessi per essere eseguiti dal PLC.
• Software: implementazione degli algoritmi di visione e comunicazione con il PLC.
Si analizzano ora i componenti più rilevanti nell’ambito degli algoritmi di riconoscimento di oggetti.
Figura 1.2: Braccio robotico e bin contenete i prodotti da individuare e raccogliere.
1.3
Sistema di visione
Il sistema di visione utilizzato dal sistema è montato su un supporto mobile al di sopra del cesto che contiene i prodotti da prelevare. Tale sistema permette di ottenere una scansione tridimensionale mediante triangolazione laser. Le tre componenti principali sono:
• una telecamera ad alta risoluzione (28 fps - risoluzione 1600x1200 px) ; • due proiettori laser (5mW - λ 640-670nm).
Figura 1.3: Sistema di visione.
La tecnica di triangolazione calcola l’altezza di ogni pixel basandosi sulla sulla deviazione della luce causata dalla presenza di un oggetto. Per ogni frame acquisito dalla telecamera viene calcolata l’altezza di ogni pixel sulla linea, in questo modo ogni frame fornisce una linea di altezze.
Utilizzando questo sistema si ottengono delle nuvole di punti (point cloud ) che vengono utilizzate come input per il software di riconoscimento che si occupa di individuare la posa degli oggetti nel bin.
1.4
Sistema Software
1.4.1
Smart Pick 3D
Smart Pick 3D è il software sviluppato da IT+Robotics per l’identificazione, tramite visione, della posizione e dell’orientamento dei prodotti all’interno della linea di produzione. Attraverso i dati acquisiti dal sistema di visione è possibile controllare i movimenti del robot, permettendo il prelievo dei pezzi da lavorare da un cassone o da un nastro trasportatore disposti in maniera totalmente casuale.
Nello sviluppo di Smart Pick 3D sono state utilizzate molte librerie soft-ware e API per ottenere algoritmi di visione efficienti e all’avanguardia. Per quanto riguarda il presente lavoro, i componenti più rilevanti sono:
• PCL: Point Cloud Library è un framework open-source che include numerosi algoritmi per l’elaborazione di immagini 2D/3D e point cloud n-dimensionali.
• OpenMP: API multipiattaforma per la creazione di applicazioni pa-rallele su sistemi a memoria condivisa.
1.4. Sistema Software 7
Figura 1.4: Screenshot di Smart Pick 3D. É visibile il risultato di un ciclo di esecuzione: in verde, gli oggetti individuati all’interno del contenitore, in rosso. Il componente in blu è stato scelto per il prelievo.
1.4.1.1 Esecuzione offline e dump
Durante l’esecuzione del software in produzione, per ogni ciclo viene salvato un dump. Ognuno di essi contiene in sintesi:
• Configurazione corrente (algoritmi da utilizzare, parametri, prodotto da prelevare, ecc.)
• Stato corrente
• Point cloud ottenuta dal sistema di visione
• Posizione del prodotto prelevato nel ciclo precedente
Tali dump sono eseguibili in un secondo momento in modalità offline, ovvero senza necessità di essere collegati al sistema di visone né al robot. Hanno principalmente due scopi:
• consentire il debug di nuove funzionalità o algoritmi senza essere colle-gati al sistema.
1.4.2
Point Cloud Library
PCL[1] è un progetto open-source, cross-platform, rilasciato con licenza BSD. Compilabile e distribuibile su Linux, Mac OS X, Windows, Android e iOS.
Il framework contiene numerosi algoritmi allo stato dell’arte che includono filtraggio, calcolo di feature, registrazione, segmentazione e molti altri. Questi algoritmi possono essere usati ad esempio per filtrare dati rumorosi, unire nuvole di punti, segmentare parti di una scena, estrarre keypoint e calcolare descrittori per il riconoscimento di oggetti. Tali funzionalità insieme a molte altre sono alla base di qualsiasi algoritmo di visione.
Per rendere più semplice lo sviluppo utilizzando questo vasto framework, PCL è diviso in una serie di librerie più piccole che possono essere compilate separatamente. La scelta si rivela vincente, per esempio, per distribuire PCL su piattaforme con capacità computazionale ridotta. Il grafico delle librerie di PCL [2] è riportato in figura 1.5.
Figura 1.5: Grafico dei moduli di PCL alla versione 1.6. I moduli principali e utilizzati per lo sviluppo sono:
• common contiene le strutture di dati comuni e i metodi usati dalla maggior parte delle librerie PCL. La struttura dei dati di base include la classe Point Cloud e diversi tipi di punti che sono utilizzati per rappresentare punti semplici, le normali delle superfici, i valori di colore RGB e i descrittori delle features. Contiene inoltre numerose funzioni per calcolare distanze/norme, medie e covarianze, conversioni angolari e trasformazioni geometriche.
1.4. Sistema Software 9
albero che permette efficienti range search e nearest neighbor search. Le nearest neighbor searches sono operazioni fondamentali quando si lavora con point cloud e possono essere utilizzate per trovare corri-spondenze tra gruppi di punti, descrittori di features, o per definire una neighborhood locale attorno a un punto o ad un insieme di punti. • filters contiene algoritmi di rimozione di outlier e rumore per il
filtrag-gio di point cloud 3D. Contiene inoltre filtri generici usati per estrarre sottoinsiemi di point cloud, per escluderne una parte o effettuare il downsampling. Viene utilizzato ad esempio per il filtraggio voxel. • features utilizzato per la stima delle features 3D sulle point cloud.
Queste descrivono pattern geometrici basati sulle informazioni dispo-nibili intorno ad un punto, dove la neighborhood del punto può essere definita o come l’insieme dei punti contenuti in una sfera di centro il punto considerato e raggio arbitrario o in termini di k-neighborhood (i k punti più vicini al punto considerato).
• keypoints contiene l’implementazione di vari algoritmi per l’indivi-duazione di punti di interesse nelle point cloud, punti cioè che siano distintivi della cloud considerata e che, una volta che su di essi siano stati calcolati dei descrittori, siano in grado di formare una rappresen-tazione compatta (il numero di keypoints è minore del numero di punti della point cloud ) e tuttavia completa e distintiva dei dati originali. • registration implementa una serie di algoritmi di la registrazione di
point cloud, tra cui algoritmi per il correspondence finding, correspon-dence rejection, transformation estimation e ICP (Iterative Closest Point). • segmentation contiene algoritmi per la segmentazione di point cloud
in cluster. Questo è utilizzato in fase preliminare nell’approccio basato su clusterizzazione della scena.
• sample_consensus contiene metodi basati su SAmple Consensus co-me RANSAC e modelli (linee, piani, cilindri, sfere etc.) può essere utilizzato per il plane detection o per individuare oggetti con una struttura geometrica comune.
• io contiene classi e funzioni per la lettura e la scrittura di point cloud da/su disco.
1.4.2.1 Versione 1.7
Nel Luglio 2013 è stata rilasciata ufficialmente la versione 1.7 del progetto seguita, pochi mesi dopo, dalla versione 1.7.1 che introduce alcune migliorie e bugfix.
Con il rilascio ufficiale dell’ultima versione è stato aggiunto il modulo recognition che implementa alcuni algoritmi per il riconoscimento di oggetti basati su correspondece grouping. L’introduzione di tale modulo ha motivato lo sviluppo di un nuovo sistema di riconoscimento da confrontare a quello attualmente esistente e funzionate.
1.5
OpenMP API
OpenMP è una Application Program Interface (API)[3], definita congiunta-mente da un insieme dei maggiori produttori hardware e software. OpenMP fornisce un modello portabile e scalabile per lo sviluppo di applicazioni pa-rallele con memoria condivisa. Sono supportati i linguaggi C/C++ e Fortran su una vasta gamma di architetture.
I componenti di OpenMP possono essere sintetizzati in: • Direttive del compilatore
• Runtime Library • Variabili d’ambiente
I programmi che usano OpenMP sono parallelizzati attraverso l’uso di th-read. Un thread è la più piccola unità di un processo che può essere schedulata dal sistema operativo.
1.5. OpenMP API 11
Capitolo 2
Il riconoscimento
Nel campo della computer vision il riconoscimento di oggetti (object recogni-tion) consiste nell’individuare in una scena, bidimensionale o tridimensionale, l’oggetto ricercato. L’uomo è in grado di riconoscere in pochi istanti un gran-de numero di oggetti, anche variando il punto di vista o la scala; non incontra particolari difficoltà nemmeno se gli oggetti sono parzialmente nascosti alla vista (occlusioni).
Per una macchina questo compito è un problema complesso e computa-zionalmente molto dispendioso, specialmente se la scena in cui si vogliono riconoscere gli oggetti è tridimensionale.
Al giorno d’oggi, in computer vision, la ricerca di un algoritmo di ri-conoscimento robusto, accurato e veloce è di fondamentale importanza per una moltitudine di applicazioni come la realtà aumentata, o come nel ca-so trattato, per il rilevamento della posa di oggetti per la manipolazione robotica.
Con il rilascio ufficiale delle Point Cloud Library 1.7, avvenuto nel luglio 2013, sono stati introdotti dei metodi specifici per l’object recognition, prima non supportati. In questo elaborato è stato sviluppato un algoritmo di rico-noscimento di oggetti industriali per la stima della posa di quest’ultimi. Le point cloud dei modelli sono ottenute partendo da disegni CAD. Il sistema opera il riconoscimento elaborando le scansioni tridimensionali ottenute con il sistema di triangolazione laser. L’algoritmo sviluppato, basato su Hou-gh3DGrouping implementato in PCL 1.7, è stato confrontato con un algo-ritmo di riconoscimento basato su registrazione [4] e clustering, sviluppato antecedentemente all’introduzione del modulo recognition.
Figura 2.1: Esempio di riconoscimento: a sinistra scansione trimensionale della scena; a destra, in bianco, modelli CAD degli oggetti riconosciuti e allineati sulla scena, in rosso.
Nel presente capitolo viene definito il problema del riconoscimento, ana-lizzata la teoria alla base degli algoritmi e proposti due approcci di soluzione generale allo stesso.
2.1
Definizione del problema
L’obiettivo finale, nel caso in esame, è quello di trovare le coordinate del punto di presa degli oggetti presenti all’interno della scena scansionata dal sistema di triangolazione laser. Posto che il punto di presa può variare a seconda della natura degli oggetti cercati, si semplifica questa parte del problema cercando, nella fase di riconoscimento, una matrice di roto-traslazione che sovrappone un modello (partendo da una posizione nota) ad una istanza dell’oggetto trovata nella scena: l’allineamento tra scena e modello deve essere preciso per consentire la presa del braccio robotico.
2.1.1
Input
I dati di partenza per effettuare un riconoscimento sono essenzialmente il modello e la scena:
2.1. Definizione del problema 15
una istanza di un oggetto. Il fatto di usare le facce del modello riduce l’errore di rotazione e di traslazione nella ricerca della posa[5].
• scena: point cloud ottenuta dal sistema di scansione, contiene gli og-getti disposti in posizione casuale e il cesto che li contiene (Figura 2.3). Utilizzando un filtro voxel si riduce la risoluzione della scena per ridurre la complessità computazionale.
Figura 2.2: Modelli: quattro viste del modello completo visibile al centro. Le point cloud del modello e delle viste sono ottenute da CAD.
2.1.2
Output
La soluzione al problema è costituita, quindi, da un set di matrici di roto-traslazione utilizzate per allineare la point cloud del modello alla parte visibile nella scena ottenuta con il sistema di visione.
Una trasformazione rigida è rappresentata da una matrice 4x4: r11 r12 r13 t1 r21 r22 r23 t2 r31 r32 r33 t3 0 0 0 1
La matrice 4x4 in coordinate omogenee, da cui si ottiene la trasformazione
rigida, è costituita da: una sottomatrice 3x3 (ri,j) che rappresenta la
rotazio-ne rotazio-nello spazio 3D e dal vettore (ht1 t2 t3
i
) che rappresenta la traslazione .
2.2
Riconoscimento basato su
registrazione
Il metodo per allineare due o più nuvole di punti tridimensionali è chiama-to registrazione. Il processo consiste brevemente nell’identificare i punti corrispondenti tra più viste di una scena o di un oggetto, trovare una tra-sformazione che minimizza la distanza tra tali punti in modo da allineare perfettamente le point cloud ricostruendo la scena. Iterativamente si cerca di raggiungere un allineamento perfetto.
2.2. Riconoscimento basato su registrazione 17
Il problema del riconoscimento può essere considerato un caso particolare della registrazione, in cui si cerca di allineare un modello alla scena. Tuttavia, la presenza di più istanze di un determinato oggetto nella stessa scena mette in crisi il metodo di registrazione in quanto ad un punto nel modello ne possono corrispondere uno o più nella scena, entrambi validi. Ma lo scopo di questa tecnica è trovare la migliore trasformazione che allinea due point cloud quindi, in questo caso, la tecnica di registrazione ha un’alta probabilità di fallire.
Per questo motivo si adotta la tecnica di clustering[6] per separare gli og-getti da riconoscere nella scena prima di utilizzare la tecnica di registrazione. Successivamente è possibile registrare il modello o una vista di quest’ultimo con ogni cluster.
Figura 2.5: Esempio di clustering: ogni colore identifica un cluster, su ogni cluster si utilizza l’algoritmo di registrazione.
In breve, la procedura di registrazione di due point cloud consiste nei seguenti passi:
• per ogni nuvola di punti si identificano i punti di interesse o keypoint che meglio rappresentano la scena in entrambi i data set
• per ogni keypoint si calcola un descrittore
• si scartano le corrispondenze non valide che contribuirebbero in maniera negativa alla registrazione
• dalle corrispondenze rimanenti si stima una trasformazione rigida
Figura 2.6: Point Cloud Library Registration API (immagine tratta dalla documentazione ufficiale di PCL [4]).
Iterando questi passi fino a raggiungere determinati criteri di convergenza è possibile raggiungere l’allineamento. L’implementazione dell’algoritmo ICP (Iterative Closest Point) è un esempio di adattamento della pipeline appena descritta. Solitamente ICP viene utilizzato nella fase finale della registrazione per perfezionare l’allineamento.
2.3
Riconoscimento basato su
correspondence
grouping
2.3. Riconoscimento basato su correspondence grouping 19
Si analizza ora il flusso di lavoro di un algoritmo di riconoscimento basato su correspondence grouping mediante Hough Voting. Le fasi principali del riconoscimento si possono riassumere nello schema in figura 2.7
Figura 2.7: Object Recogintion pipeline. Nello specifico:
1. Keypoint: il primo passo consiste nel calcolare dei keypoint, o punti chiave, per il modello e per la scena.
2. Descrittori: per ogni keypoint si calcola un descrittore (feature), ovvero una caratteristica unica che lo distingue dagli altri keypoint. 3. Corrispondenze: utilizzando le feature estratte al punto precedente
si calcolano le corrispondenze modello-scena.
4. Correspondence Grouping: le corrispondenze trovate vengono clu-sterizzate, ogni cluster rappresenta una ipotesi di posa.
5. Allineamento iniziale: ogni gruppo di corrispondenze permette di calcolare una trasformazione del modello sulla scena, ottenendo così una serie di istanze che sono una prima ipotesi della posa del modello nella scena.
6. Allineamento finale: utilizzando ICP si cerca di migliorare l’allinea-mento iniziale del modello.
7. Validazione: come ultimo passaggio vengono rimossi falsi positivi o duplicati utilizzando una funzione di validazione.
2.3.1
Keypoint
usati in combinazione con i descrittori, si ottiene una descrizione compatta dei dati originali.
Esistono diversi tipi di keypoint, ci si limita a riportare una breve intro-duzione di quelli testati e scelti durante lo studio.
2.3.1.1 SIFT Keypoint
Un SIFT (Scale-Invariant Feature Transform) keypoint è un adattamento al 3D del metodo studiato da David Lowe [7] per l’estrazione di keypoint. Un SIFT keypoint è una regione circolare che possiede un’orientazione, questo è descritto da un frame di quattro parametri: le coordinate x e y del centro, il raggio della regione che comprende (i.e. la sua “scale”) e la sua orienta-zione espressa come un angolo in radianti. I parametri che influenzano il rilevamento di questi keypoint sono diversi: anzitutto essi vengono cercati su più “scale”, o cosiddetti “livelli di smoothing”, mediante la costruzione di un Gaussian space scale, cioè una collezione di immagini ottenute applicando iterativamente filtri gaussiani all’immagine di partenza. Questi filtri appor-tano appunto un effetto di smoothing e comporappor-tano pertanto una graduale perdita di risoluzione.
2.3.1.2 Uniform Keypoints
Lo uniform sampling funziona in maniera analoga al filtro voxel l’unica dif-ferenza che si può osservare è data dal fatto che il keypoint risultante è un punto della point cloud di partenza, vincolo che non è necessariamente ri-spettato dal voxel filter in quanto, in questo caso, per ogni voxel viene scelto il centroide dei punti al suo interno. La procedura, dunque, è la seguente:
1. viene costruita una griglia di cubi di dimensione fissata come parame-tro;
2. viene computato il voxel point per ciascun cubo;
3. viene scelto come keypoint per ciascun cubo il punto della point cloud più vicino al voxel point.
2.3. Riconoscimento basato su correspondence grouping 21
Figura 2.8: Confronto tra keypoints SIFT (sinistra) e uniform (destra). Si no-ti come nel secondo caso sia ben visibile la struttura a griglia precedentemente discussa.
Nel presente lavoro è stato scelto di utilizzare gli uniform keypoints in quanto, per la natura degli oggetti trattati, la scelta di keypoint con un par-ticolare algoritmo (come SIFT) non ha portato vantaggi significativi, anzi riducendo il numero di keypoint si riducono il numero di corrispondenze tro-vate. Infine il tempo di estrazione dei keypoint è significativamente maggiore con SIFT.
Calcolo keypoint
Per il calcolo degli Uniform keypoint si utilizza la classe pcl::UniformSampling di PCL che prevede:
• Input: point cloud di cui calcolare i keypoint • Parametri:
– leaf_size: dimensione delle foglie della griglia 3D • Output: point cloud di keypoint
2.3.2
Descrittori
le corrispondenze tra i keypoint di modello e scena. Nel presente lavoro sono stati testati due tipi di descrittori [8]: FPFH e SHOT352.
2.3.2.1 FPFH (Fast Point Feature Histogram)
L’algoritmo che calcola i descrittori FPFH [9] (o Fast-PFH) è, come suggeri-sce il nome, una implementazione dell’algoritmo PFH [10] che riduce drasti-camente la complessità computazionale e temporale senza inficiare eccessiva-mente l’informazione apportata. I descrittori FPFH sono delle feature locali basate sulle normali alla superficie della cloud e utilizzano l’informazione della k-neighborhood del punto corrente (i k punti più vicini).
La principale differenza tra PFH-descriptors e FPFH-descriptors è data dal fatto che, mentre l’algoritmo PFH calcola l’edge di ogni coppia della mesh
che la k-neighborhood crea ( k2 edges), FPFH tiene conto solo delle k
con-nessioni che collegano il punto in esame a ciascun punto della neighborhood.
La complessità si riduce quindi da O(n · k2) a O(n · k).
Il calcolo del descrittore FPFH per il generico punto pq avviene in due
step: F P F H(pq) = SP F H(pq) + 1 k X 1 ωk · SP F H(pk)
Come suggerisce la formula, va anzitutto calcolata la SPFH (Simplified-PFH) di tutti i punti, quindi l’istogramma FPFH per ciascun punto, utiliz-zando i valori pesati degli SPFH dei suoi vicini.
Calcolo FPFH
Per il calcolo delle feature FPFH si utilizzano le classi di PCL pcl::FPFHEstimation o pcl::FPFHEstimationOMP per la versione parallelizzata che prevede:
• Input:
– Point cloud: si usa una versione voxellizzata di quella originale in modo da ridurre il numero di punti
– Normali: calcolate sulla point cloud in input
– Keypoint: punti sui quali vengono calcolate le feature • Parametri:
– normal_rad: raggio utilizzato per il calcolo delle normali – fpfh_rad: raggio utilizzato per il calcolo
2.3. Riconoscimento basato su correspondence grouping 23
2.3.2.2 SHOT352 (Signature of Histograms of OrienTations)
Il descrittore SHOT[11] è basato sull’idea di ottenere un local reference fra-me utilizzando la eigenvalue decomposition attorno a ciascun punto. Dato questo reference frame, viene costruita una griglia di sfere centrate ciascuna in ciascun punto, in modo da dividere i punti in un insieme di neighborhood e in modo tale che ogni in ogni sfera si ottenga un istogramma pesato di normali. Il descrittore concatena tutti questi istogrammi nella signature fi-nale. Esso utilizza 9 valori per codificare il reference frame, inoltre vengono utilizzati 11 shape bins e 32 divisioni di griglie “sferiche”, cosa che porta a 352 (32 × 11) valori aggiuntivi, da cui il nome SHOT352. I descrittori sono infine normalizzati per sommare a 1.
Figura 2.9: Struttura di una SHOT signature.
In seguito ai risultati ottenuti durante primi test si è scelto di non utiliz-zare questo tipo di descrittori, preferendo quelli di tipo FPFH in quanto più performanti sia computazionalmente che qualitativamente nel calcolo delle corrispondenze per il tipo di modelli utilizzati.
2.3.2.3 BOARD LRF (Local Reference Frame)
Il BOrder Aware Repeatable Directions (BOARD[12]) è un algoritmo stu-diato per il calcolo del Local Reference Frame di un keypoint. L’algoritmo è robusto anche quando lo spazio adiacente al punto di cui si vuole calcolare l’orientazione (LRF) è occluso o non visibile (Border Point). Orientare le feature nello spazio tridimensionale è molto importante quando si cerca un match tra viste parziali di una superficie. I LRF sono utilizzati nella fase di correspondence grouping.
• Input:
– Point cloud: si usa una versione voxellizzata di quella originale in modo da ridurre il numero di punti e di conseguenza la complessità computazionale
– Normali: calcolate sulla point cloud in input
– Keypoint: punti sui quali vengono calcolate le feature • Parametri:
– normal_rad: raggio utilizzato per il calcolo delle normali – rf_rad: raggio utilizzato per il calcolo
• Output: point cloud di pcl::ReferenceFrame, uno per ogni keypoint
2.3.3
Corrispondenze
In seguito al calcolo dei descrittori si ricercano corrispondenze tra quelli di tipo FPFH. Una corrispondenza, infatti, non è altro che una coppia di feature, una del modello e una della scena, che presentano una forte somiglianza. Essendo i descrittori calcolati per ogni keypoint, in seguito al calcolo delle corrispondenze si ottengono una serie di coppie costituite da un keypoint della scena e uno del modello.
La classe pcl::registration::CorrespondeceEstimation di PCL im-plementa due metodi per il calcolo delle corrispondenze tra due point cloud di descrittori (FPFHSignature33 in questo caso). Entrambi utilizzano un KDTreeFLANN [13] per ricercare le corrispondenze tra una sorgente (mo-dello) e un obiettivo (scena). I metodi di PCL sono pensati principalmente per effettuare il processo di registrazione, in cui si cercano le corrispondenze sorgente-target (modello-scena in questo caso). Tuttavia, questo approccio non è adatto al caso in cui la scena contenga più istanze dello stesso oggetto. Nel riconoscimento di oggetti basato su correspondence grouping, invece, la fase di ricerca delle corrispondenze si effettua cercando, per ogni descrittore della scena, il descrittore più vicino del modello; si consideri che la distanza di due descrittori indica il loro grado di somiglianza. In questo modo è poi possibile, con algoritmi di correspondence grouping come Hough3DGrouping, dividere le corrispondenze in cluster, uno per ogni istanza del modello nella scena.
2.3. Riconoscimento basato su correspondence grouping 25
Figura 2.10: Esempio di corrispondenze in blu (per motivi di leggibilità è mostrata una corrispondenza su 15 rispetto a quelle realmente), in nero i keypoint della scena, in verde la vista del modello.
stesso utilizzato da PCL ma al momento della creazione della corrispondenza vengono scambiati gli indici di source e target.
Infine, le corrispondenze che hanno una distanza tra i descrittori superiore a un threshold vengono scartate.
v o i d f i n d C o r r e s p o n d e n c e s ( P o i n t C l o u d < F P F H S i g n a t u r e 3 3 >:: Ptr source , P o i n t C l o u d < F P F H S i g n a t u r e 3 3 >:: Ptr target , C o r r e s p o n d e n c e s P t r c o r r e s p o n d e n c e s ) { // I n i z i a l i z z a z i o n e K d T r e e s e a r c h :: KdTree < F P F H S i g n a t u r e 3 3 > t r e e ; t r e e . s e t I n p u t C l o u d ( t a r g e t ) ; std :: vector < int > i n d e x (1) ; std :: vector < float > d i s t a n c e (1) ; u n s i g n e d int n r _ v a l i d _ c o r r e s p o n d e n c e s = 0; // per o g n i p u n t o d e l l a s c e n a
C o r r e s p o n d e n c e c o r r ; // i n d i c e d e l l a f e a t u r e / kp del m o d e l l o c o r r . i n d e x _ q u e r y = i n d e x [ 0 ] ; // i n d i c e d e l l a f e a t u r e / kp d e l l a s c e n a c o r r . i n d e x _ m a t c h = j ; c o r r . d i s t a n c e = d i s t a n c e [ 0 ] ; // a g g i u n g i c o r r i s p o n d e n z a all ’ o u t p u t c o r r e s p o n d e n c e s - > at ( n r _ v a l i d _ c o r r e s p o n d e n c e s ++) = c o r r ; } c o r r e s p o n d e n c e s - > r e s i z e ( n r _ v a l i d _ c o r r e s p o n d e n c e s ) ; }
Listing 2.1: Funzione di calcolo corrispondenze
2.3.4
Correspondence grouping
É in questa fase che il processo di riconoscimento si distingue maggiormente dal problema di registrazione, in cui si utilizzano algoritmi come RANSAC (RANdom SAmple Consensus) per filtrare le false corrispondenze e si cerca di individuare la miglior trasformazione dell’oggetto sulla scena (Figura 2.11). Tuttavia, il metodo basato su registrazione fallisce poiché la scena contiene multiple istanze dello stesso oggetto. Per questo motivo è necessario cluste-rizzare la scena a monte, prima della ricerca delle corrispondenze, e risolvere il problema della registrazione per ogni cluster.
Figura 2.11: In alto: corrispondenze tra sorgente e target. In basso:
2.3. Riconoscimento basato su correspondence grouping 27
Un algoritmo di correspondence grouping è studiato per gestire multiple istanze dello stesso oggetto nella scena. Il suo scopo principale è dividere le corrispondenze in gruppi, ognuno dei quali è utilizzato per determinare una trasformazione del modello cercato nella scena. In questo lavoro è stata utilizzata la classe pcl::Hough3DGrouping, un sistema di correspondence grouping basato sulla trasformata generalizzata di Hough applicata al 3D.
Figura 2.12: Tre possibili istanze trovate in seguito a grouping delle
corrispondenze
Le corrispondenze visualizzate in figura 2.10 vengono divise in cluster e, per ogni cluster che soddisfa determinate condizioni, si stima una possibile trasformazione iniziale del modello. Il risultato è visibile in figura 2.12.
2.3.4.1 Hough 3D Grouping
una retta viene mappata in una coppia di parametri cioè l’arcotangente del coefficiente angolare e il termine noto, e così via. La trasformata generalizzata di Hough usa i principi del template matching per permettere, non solo di individuare un oggetto descrivibile tramite un’equazione analitica, ma anche oggetti dalla forma arbitraria descritti con un loro modello. Il problema diviene, quindi, quello di trovare la posizione del modello nella scena o, più precisamente, trovare i parametri della matrice di roto-traslazione che mappa il modello nell’immagine. La GHT usa le informazioni sui bordi per definire una mappatura dall’orientazione di un edge point ad un reference point.
Una pipeline generale della GHT consiste:
1. Lo spazio n-dimensionale dei parametri viene discretizzato in bin (iper-rettangoli di n dimensioni)
2. Per ogni edge point dell’immagine viene messo un voto in un bin dello spazio dei parametri che può aver generato quel punto, ossia ogni punto vota per quello che riconosce come proprio reference point
3. Vengono scelti i bin che hanno il maggior numero di voti
La trasformata di Hough è piuttosto robusta al rumore e conseguentemente accadrà che i punti cosiddetti “rumorosi” non voteranno in maniera consi-stente per una singola posa del modello. I dati che risultano da questi voti inesatti non hanno alcuna conseguenza apprezzabile fintanto che rimangono abbastanza edge point che concordano su un determinato reference-point.
Come già anticipato, la classe pcl::Hough3DGrouping implementa un algoritmo di correspondence grouping basato sulla GHT in uno spazio tri-dimensionale [15] [16].
Come nel caso 2D, il sistema di voti di Hough ha l’obiettivo di accumulare prove della presenza dell’oggetto cercato. Se abbastanza feature votano per la presenza dell’oggetto in una data posizione, allora l’oggetto è riconosciuto e un allineamento iniziale è determinato utilizzando corrispondenze votanti. Il primo passo consiste nel calcolare un reference point univoco per il
modello, CM, per comodità lo si fa coincidere con il centroide (punto rosso
in figura 2.13). Successivamente si calcolano i reference frame (RF), ovvero
vettori tra ciascuna feature, FM
i , e il centroide (frecce blu in 2.13). Questi
vettori sono memorizzati utilizzando il sistema di riferimento locale (LRF) in modo da rendere il sistema invariante a rototraslazioni. In questo modo, sfruttando le corrispondenze è possibile riportare i vettori sulla scena con lo stesso orientamento secondo un sistema di riferimento locale. A questo
punto ogni feature FM
i dà un voto per una posizione di un reference point
2.3. Riconoscimento basato su correspondence grouping 29
Figura 2.13: Esempio di 3D Hough Voting basato su RF.
Figura 2.14: Esempio di 3D Hough Voting basato su LRF.
La scena viene divisa in una griglia tridimensionale di bin che raccolgo-no i voti delle feature. Gli spazi che raccolgoraccolgo-no il maggior numero di voti determinano la presenza di una istanza. Grazie a questo sistema è possibile trovare più istanze dello stesso oggetto contemporaneamente.
Riassumendo, la classe pcl::Hough3DGrouping richiede: • Input:
– Keypoint del modello e della scena
– LRF calcolati sui keypoint del modello e della scena
– Corrispondenze tra i keypoint confrontando i descrittori FPFH • Parametri:
– hough_threshold: numero minimo di voti in un bin per conside-rare una possibile istanza
• Output: lista di matrici di roto-traslazione, una per ogni istanza che ha raggiunto un numero sufficiente di voti
2.3.5
Allineamento iniziale
L’allineamento iniziale consiste nella trasformazione del modello utilizzan-do la matrice di roto-traslazione che Hough3DGrouping fornisce in output. Tale matrice è calcolata utilizzando le corrispondenze clusterizzate al passo precedente, ogni gruppo di corrispondenze permette di calcolare una matrice di roto-traslazione. L’insieme delle trasformazioni permette di ottenere una serie di guess della posa dell’oggetto cercato.
2.3.5.1 Pre-validazione
Molte delle ipotesi di posa del modello, restituite dalla fase di correspon-dence grouping, sono errate o falsi positivi (disallineate o modello sbagliato). Queste istanze verranno sicuramente scartate nella fase successiva in seguito all’allineamento finale con ICP. Sperimentalmente si è verificato che l’algorit-mo ICP è un bottleneck considerevole e per questo l’algorit-motivo viene operata una prima validazione delle istanze in seguito all’allineamento iniziale, in questo modo il tempo di esecuzione viene drasticamente ridotto.
Figura 2.15: Esempio di output in seguito a prima validazione: le istanza scartate in rosso, le istanze che passano alla fase successiva in verde, la scena in nero.
2.3. Riconoscimento basato su correspondence grouping 31
rilevate al passo precedente) e la scena. Per un modello di K punti ed una scena di N punti, ad esempio, essa è calcolata come:
Average Squared Euclidean Distance = 1
K
K−1
X
i=0
minN −1j=0 d(istanza.i, scena.j) dove d(istanza.i, scena.j) rappresenta la Squared Euclidean Distance tra l’i-esimo punto dell’istanza ed il j-l’i-esimo punto della scena:
d(A, B) = (Ax− Bx)2+ (Ay − By)2+ (Az− Bz)2
Successivamente le istanze con uno score superiore a un threshold vengono scartate in quanto si ipotizza che siano frutto di un match errato; quelle “sopravvissute” a questa fase verranno infine allineate alla scena e subiranno un processo di verifica più precisa.
L’implementazione di tale metodo è mostrata nel listato 2.2.
d o u b l e s q u a r e d _ e u c l i d e a n _ d i s t a n c e ( c o n s t P o i n t C l o u d :: Ptr model , c o n s t P o i n t C l o u d :: Ptr s c e n e ) { // per r i c e r c a K n e a r e s t n e i g h b o r pcl :: KdTree < P o i n t X Y Z > k d t r e e ; k d t r e e . s e t I n p u t C l o u d ( s c e n e ) ; d o u b l e d i s t a n c e = 0; std :: vector < int > p o i n t I d x N K N S e a r c h (1) ; std :: vector < float > p o i n t N K N S q u a r e d D i s t a n c e (1) ;
for ( int i = 0; i < model - > s i z e () ; i ++) { k d t r e e . n e a r e s t K S e a r c h ( s e a r c h P o i n t , 1 , p o i n t I d x N K N S e a r c h , p o i n t N K N S q u a r e d D i s t a n c e ) d i s t a n c e += p o i n t N K N S q u a r e d D i s t a n c e [ 0 ] ; } r e t u r n d i s t a n c e / model - > p o i n t s . s i z e () ; }
Listing 2.2: Calcolo della distanza tra due pointcloud.
2.3.6
Allineamento finale
L’allineamento iniziale non è preciso a sufficienza per consentire la presa da parte di una pinza guidata da un braccio robotico. É necessario quindi affinare la trasformazione in modo che il modello sia allineato alla perfezione con l’oggetto presente nella point cloud della scena.
corrispondenze tra coppie di punti più vicini fra loro e iterativamente cerca la trasformazione geometrica che minimizza la distanza tra le nuvole di punti.
2.3.6.1 Validazione
In seguito all’allineamento finale dei match più promettenti viene calcolato un nuovo score per valutare la qualità dell’allineamento finale e, di conse-guenza, se aggiungere la trasformazione ottenuta alla lista dei match oppure se scartarla e passare alla successiva ipotesi.
Questa seconda funzione di validazione calcola la percentuale di outlier [6] presenti tra la scena ed il modello allineato. Il calcolo dello score segue la seguente procedura:
1. per ciascun punto del modello viene individuato il punto più vicino della scena
2. se la distanza tra due punti è inferiore ad una soglia fissata tale punto viene considerato un inlier ; in caso contrario viene considerato come outlier,
2.3. Riconoscimento basato su correspondence grouping 33
Capitolo 3
Algoritmi
In questo capitolo si analizzano due algoritmi di riconoscimento che utiliz-zano i due differenti approcci presentati nel capitolo precedente. Il primo algoritmo, basato sulla registrazione, è utilizzato come punto di riferimento, in quanto ampiamente collaudato e testato. Attualmente SmartPick3D uti-lizza una versione altamente ottimizzata di questo algoritmo. In questo lavoro è stato sviluppato il secondo algoritmo proposto, basato su correspondence grouping, da affiancare a quello esistente.
Queste procedure sono state sviluppate iterando alcune fasi del riconosci-mento o della registrazione, in modo da riconoscere più istanze di un oggetto utilizzando più modelli o più viste dello stesso modello (ognuna è trattata come un modello differente). Inoltre, alcuni passi sono ripetuti variando la configurazione dei parametri. Questa scelta è motivata dal fatto che per quanto si possano cercare di ottimizzare tali valori, a causa di rumore va-riabile introdotto durante l’acquisizione o differenti angolazioni di posa degli stessi oggetti, non è possibile trovare un’unica configurazione di parametri che garantisca il riconoscimento di tutte le istanze in una singola iterazione.
3.1
Algoritmo 1:
clustering + registrazione
Come già anticipato nel capitolo precedente, il primo passo consiste nel clu-stering della scena, successivamente si procede come riportato nello pseudo-codice dell’algoritmo 1.
3.1.1
Analisi
per quel cluster. Ogni trasformazione è calcolata da un set di corrispondenze stimate da un set di FPFH calcolate con lo stesso raggio.
Algoritmo 1 clustering + registrazione
Input: Cluster della scena e modelli da cercare Output: Lista di trasformazioni e punteggio
for all cluster della scena do
- trova uniform keypoint del cluster e dell’oggetto for all raggio FPFH do
- calcolo descrittori FPFH del cluster e dell’oggetto - ricerca corrispondenze tra i descrittori
for all SAC threshold do
- filtraggio delle corrispondenze con RANSAC
- stima di una trasformazione rigida utilizzando le corrispondenze rimaste che minimizzi la distanza
- score1 ⇐ Euclidean Distance
- conserva la trasformazione iniziale con score1 migliore end for
end for end for
for all trasformazione iniziale con score1 > threshold1 do - uniform sampling di scena e oggetto
- calcolo trasformazione finale utilizzando ICP su cloud ridotte - score2 ⇐ Percentuale Outlier
if score2 inferiore a soglia then
- aggiungi trasformazione a oggetti riconosciuti end if
end for
Nel caso di riconoscimento, utilizzando più modelli o più viste dello stes-so modello si introduce un ulteriore ciclo innestato all’interno del secondo, quindi si calcolano le corrispondenze tra un cluster e ogni vista del modello.
I vantaggi di questo approccio che utilizza il clustering sono:
• Riduzione del rumore nella fase di allineamento iniziale operando su cluster della scena
• Parallelizzabilità: possibilità di effettuare il riconoscimento in parallelo su più cluster contemporaneamente
3.2. Algoritmo 2: correspondence grouping 37
• Falsi negativi: cercando un match per ogni cluster si riduce la percen-tuale di falsi negativi
Tuttavia, il clustering non è sempre vantaggioso in quanto non semplice da effettuare per alcuni tipi di prodotti. Per la natura di alcuni oggetti, per esempio, sono necessarie più fasi di clustering che introducono ulteriore complessità computazionale.
Questa analisi ha motivato la ricerca di un algoritmo che non preveda la ricerca di cluster. Tuttavia, il processo di validazione studiato in questo algoritmo si è rivelato robusto, cioè in grado di validare una trasformazione con una percentuale di falsi positivi prossima a zero. Ciò è stato tenuto in considerazione e preso come spunto nello sviluppo di un nuovo algoritmo.
3.2
Algoritmo 2:
correspondence grouping
Come nel caso precedente la pipeline descritta in letteratura è stata modifi-cata inserendo delle iterazioni per alcuni parametri considerati più influenti durante l’esecuzione.
In questo caso, come già anticipato, si cercano le corrispondenze tra ogni modello e la scena. In seguito, utilizzando tali corrispondenze, si individuano una serie di ipotesi di posa degli oggetti. Tali ipotesi sono valutate con la funzione di score basata su distanza euclidea; in seguito all’allineamento finale si valida o si scarta la posa trovata a seconda del risultato. Lo pseudo-codice dell’algoritmo è riportato a pagina successiva (Algoritmo 2).
Rispetto alla versione precedente si rimuove un ciclo innestato quindi la complessità diminuisce; tuttavia, ogni ciclo opera sull’intera scena invece che su cluster, quindi il calcolo delle feature e delle corrispondenze richiede maggior tempo, coinvolgendo un numero maggiore di punti.
La scelta di rimuovere i match validi alla fine di ogni iterazione è motivata dal fatto che:
• Si riduce il numero di punti della scena e di conseguenza la complessità dell’input dell’iterazione successiva
Algoritmo 2 correspondence grouping
Input: Point cloud: scena - point cloud della scena, model - point cloud del modello da cercare.
Output: matches - lista di trasformazioni e punteggio. for all dimensione bin do
- trova uniform keypoint e descrittori FPFH di scene - trova uniform keypoint e descrittori FPFH di model - ricerca corrispondenze descrittori di scene e di model
- hypotheses ⇐ lista di ipotesi di posa ottenute clusterizzando le corrispondenze con Hough3DGrouping
for all hypothesis in hypotheses do
- score ⇐ punteggio calcolato con Euclidean Distance if score non valido then
- hypothesis scartata end if
end for
for all hypothesis in hypotheses do
- match ⇐ allineamento finale mediante ICP
- score ⇐ punteggio calcolato con Euclidean Distance if score valido then
- aggiungi match a matches end if
end for
- rimozione duplicati
- riduzione scene sottraendo matches end for
3.2.1
Versione parallelizzata
Utilizzando le API OpenMP è stata implementata anche una versione pa-rallelizzata dell’algoritmo. Come già anticipato nella sezione 1.5, OpenMP è un modello di programmazione per sistemi di tipo shared memory, fattore di cui si è dovuto tenere conto durante la parallelizzazione del codice.
3.2. Algoritmo 2: correspondence grouping 39
5) si esegue un ulteriore analisi delle prestazioni.
3.2.2
Parametri
Si presentano ora i parametri numerici necessari all’utilizzo dall’algoritmo 2. La maggior parte dei valori possono essere modificati agendo sulla configu-razione dell’algoritmo. Alcuni parametri che non necessitano di modifiche sono definiti all’interno del codice, gli altri sono passati come input nella configurazione del software.
La scelta dei seguenti parametri è stata fatta tenendo in considerazione gli effetti che essi hanno sulle performance complessive.
• resolution = 2.0 [mm]
Dimensione della griglia del filtro voxel iniziale • kp_initial_resolution = 9.0 [mm]
Dimensione della griglia utilizzata per il calcolo dei keypoint (Uniform Sampling) per l’allineamento iniziale
Condizioni: > resolution • fpfh_rad = 25.0 [mm]
Raggio utilizzato per il calcolo dei descrittori FPFH Condizioni: > normal_rad
• normal_rad = 0.8·fpfh_rad [mm]
Raggio utilizzato per il calcolo delle normali Condizioni: < fpfh_rad
• lrf_rad = fpfh_rad [mm]
Raggio utilizzato per il calcolo dei Local Reference Frame • num_bin_size = 4-8 [numero di cicli]
• min_bin_size = 8-10% della misura lato più lungo del modello [mm] • max_bin_size = 15-20% della misura lato più lungo del modello [mm]
Parametri utilizzati per il calcolo del bin_size nel ciclo: vengono ef-fettuate num_bin_size iterazioni partendo da min_bin_size fino a max_bin_size
• hough_threshold = 5 [numero di corrispondenze]
• kp_initial_resolution = 9.0 [mm]
Dimensione della griglia utilizzata per il calcolo dei keypoint (Uniform Sampling) per l’allineamento iniziale
Condizioni: > resolution
• kp_initial_resolution = 9.0 [mm]
Dimensione della griglia utilizzata per il calcolo dei keypoint (Uniform Sampling) per l’allineamento iniziale
Condizioni: > resolution
• corr_distance_threshold = 300
Soglia per considerare valida una corrispondenza: se viene trovata una corrispondenza tra due descrittori che hanno distanza maggiore di corr_distance_threshold quest’ultima viene scartata
• icp_max_iteration = 50
• icp_epsilon = 10−7
Condizioni di terminazione per l’algoritmo ICP • initial_score_threshold = 0.4
• final_score_threshold = 0.3
Capitolo 4
TestFramework
Lo sviluppo di uno strumento software per effettuare test, con diverse confi-gurazioni di parametri o di algoritmi utilizzati, è stato necessario allo scopo di confrontare l’algoritmo proposto con quello esistente. Lo stesso strumen-to potrà anche essere utilizzastrumen-to per scopi di parameter tuning. In quesstrumen-to capitolo si analizzano requisiti e architettura del framework sviluppato.
4.1
Analisi dei requisiti
Lo scopo principale è fornire uno strumento per testare la configurazio-ne dell’applicazioconfigurazio-ne SmartPick3D, dove per configurazioconfigurazio-ne si intende ti-pologia di prodotti da riconoscere, parametri e algoritmi da utilizzare. Il TestFramework deve avere le seguenti funzionalità:
• Gestire l’esecuzione automatica di dump
• Caricare più configurazioni variando parametri e algoritmi da utilizzare per l’esecuzione dei test
• Raccogliere i risultati in formato analizzabile
4.2
Architettura
L’implementazione del TestFramework ha rispettato i vincoli imposti dallo stile architetturale preesistente.
Test Configuration 1 * Dump 1 * TestExecutionManager 1 * TestResult TestResulItemData TestResulItem 1 * 1 1 1 * 1 * 1 1 1 1 TestHandler * 1 TestHandlerSmartPick3D
Figura 4.1: Schema UML delle principali classi del TestFramework. Le classi che implementano il TestFramework sono:
• Test: rappresenta il test da eseguire. Ogni test prevede l’esecuzione di uno o più dump eseguiti con una o più configurazioni.
• Dump: contiene le informazioni di stato salvate durante un ciclo di esecuzione di una applicazione.
• Configuration: configurazione di parametri.
• TestHandler: rappresenta una combinazione dump/configurazione da eseguire. Per ogni applicazione è presente un TestHandler specifico. Per SmartPick3D è presente TestHandlerSmartPick3D.
• TestExecutionManager: gestisce l’esecuzione dei Test.
• TestResult: rappresenta i risultati di un Test. Contiene per ogni combinazione configurazione/dump una lista di TestResultItem. • TestResultItemData: rappresenta un risultato dell’esecuzione di un
4.3. Interfaccia Grafica 43
4.3
Interfaccia Grafica
L’interfaccia grafica realizzata consente di caricare i file di configurazione e i dump. Durante l’esecuzione di un test è possibile visualizzare lo stato e i risultati ottenuti.
Figura 4.2: Screenshot della GUI del Test Framework sviluppata per Smart Pick 3D.
La GUI visibile in figura 4.2 è composta dalle seguenti parti: 1. Lista dei test da eseguire
2. Lista dei dump caricati
3. Lista dei file di configurazione caricati 4. Pulsanti per caricare dump e configurazioni 5. Pulsanti per avviare l’esecuzione dei test
6. Tabella in cui vengono riportati i risultati dei test
Capitolo 5
Prestazioni e Risultati
Per valutare le prestazioni dell’algoritmo sviluppato (algoritmo 2) si confron-tano i risultati con quelli ottenuti con la versione esistente (algoritmo 1). Sono stati eseguiti test con diverse tipologie di oggetti e diversi set di scan-sioni ottenute con il sistema di triangolazione laser. Il dataset a disposizione proviene da un sistema attualmente utilizzato in produzione.
I test 1 e 2 hanno lo scopo di valutare le prestazioni della soluzione pro-posta, il test 3 valuta lo speedup ottenuto con la versione parallela mentre il test 4 mette a confronto le prestazioni dei due algoritmi.
I test sono stati effettuati utilizzando una macchina avente le seguenti specifiche:
• CPU: Intel Core i7 dual-core @ 2.8GHz, Turbo Boost fino a 3.3GHz • RAM: 16GB di SDRAM DDR3L a 1600MHz
• Hard Disk: Unità flash PCIe da 512GB • Sistema Operativo: OS X Mavericks
Su questo sistema è stata installata una macchina virtuale grazie al soft-ware VMWare Fusion 6. Le specifiche della macchina guest utilizzata per sviluppare e testare il software sono le seguenti:
• CPU: 4 core virtuali condivisi con l’host • RAM: 8GB dedicati
• HD: 128GB
• Sistema Operativo: Microsoft Windows 7 SP1
5.1
Oggetti e dataset
Gli oggetti di cui si esegue il riconoscimento sono dei componenti di alluminio ottenuti tramite pressofusione. Tali prodotti devono essere prelevati da un braccio robotico per essere caricati nella fase di lavorazione successiva.
Sono stati scelti tre prodotti di forme e dimensioni diverse tra loro in modo da verificare le performance su varie tipologie di modelli. Si riporta una breve descrizione dei modelli e del numero di viste utilizzate per il riconoscimento (sezione 2.1.1).
5.1.1
Prodotto A
Il prodotto A (500 × 450 × 250 mm) è un blocco di alluminio compatto e pesante, ad eccezione di un anello laterale, ed un alloggiamento scavato al suo interno. In figura 5.1 si possono vedere la faccia superiore e inferiore del prodotto.
Figura 5.1: A sinistra: esempio di scansione di scena contenente quattro prodotti di tipo A visti dell’alto. Nella parte superiore è visibile una parete del contenitore. A destra: risultato del riconoscimento; il modello è stato allineato ai quattro oggetti individuati (point cloud in blu verde e grigio) nella scena (parti in nero). Il modello per questo tipo di prodotto non viene mostrato in quanto troppo complesso per essere leggibile.
Data la geometria e la tecnica utilizzata per impilare questo tipo di prodotti si utilizzano solo due viste del modello per il riconoscimento.
5.1.2
Prodotto B
5.1. Oggetti e dataset 47
ottenuto con la tecnica di pressofusione.
Figura 5.2: A sinistra: modello prodotto B. A destra: scansione contenitore contenente il prodotto B.
5.1.3
Prodotto C
Il prodotto C (550 mm di lunghezza, 150 mm di diametro) è un componente di un cambio meccanico, costituito da un tubo alle cui estremità sono pre-senti i supporti per il fissaggio agli altri componenti e l’alloggiamento per gli ingranaggi.
Figura 5.3: A sinistra: prodotti C su un nastro trasportatore. A destra: modello prodotto C.
Per il riconoscimento di questo oggetto si utilizzano otto viste. Questa
scelta è dovuta al fatto che la forma dell’oggetto permette la rotazione a 360◦,
a differenza dell’oggetto precedente più pesante e stabile come forma.
5.1.4
Dataset
• 18 scansioni per Prodotto A • 40 scansioni per Prodotto B • 35 scansioni per Prodotto C
5.2
Configurazione
Come già anticipato, i parametri riguardanti la dimensione del bin per il calcolo della trasformazione iniziale devono essere scelti in base alla struttura ed alla dimensione del modello che si vuole riconoscere. In questa sezione si riportano i parametri per ciascun prodotto testato. I parametri omessi sono fissati ai valori riportati nella sezione 3.2.2.
L’algoritmo esegue, quindi, un massimo di num_bin_size cicli. Per il
ciclo i viene utilizzato bin_sizei calcolato con la seguente formula:
bin_sizei = min_bin_size + i · max_bin_size−min_bin_sizenum_bin_size−1
Tali valori sono fissati per tutti i test. Infine, tutte le prove sono effettuate con la versione parallela, ad eccezione del test 3 in cui si valuta lo speedup.
5.2.1
Configurazione prodotto A
La configurazione per il prodotto A prevede: • num_bin_size = 12
• min_bin_size = 40 mm • max_bin_size = 100 mm
5.2.2
Configurazione prodotto B
La configurazione per il prodotto B prevede: • num_bin_size = 8
5.3. Test 1: rate di riconoscimento 49
5.2.3
Configurazione prodotto C
La configurazione per il prodotto C prevede: • num_bin_size = 8
• min_bin_size = 30 mm • max_bin_size = 70 mm
5.3
Test 1:
rate di riconoscimento
Il Test 1 valuta il tasso di riconoscimento dell’algoritmo proposto (Algoritmo 2). Per questo esperimento è stato scelto il prodotto A. Questo oggetto è l’unico per cui risulta possibile individuare per ispezione il numero esatto di istanze riconoscibili nella scena (si veda esempio di scansione in figura 5.1).
N. di scene processate 18
N. oggetti totali (TOT) 47
N. oggetti riconosciuti
32 Veri positivi (TP)
N. oggetti riconosciuti non corretti 0 Falsi positivi (FP)
N. oggetti non riconosciuti
15 Falsi negativi (FN)
Tempo di esecuzione medio 7,7s
Tabella 5.1: Risultati Test 1
Dai dati ottenuti è possibile calcolare il recognition rate con la formula:
RecognitionRate = T OTT P %
5.4
Test 2: numero di cicli
Il secondo Test valuta la percentuale media di prodotti riconosciuti in relazio-ne al numero di cicli effettuati dall’algoritmo. Le prove sono state effettuate sui prodotti di tipo B e C e le relative scansioni, presenti nel dataset. Per questo tipo di prodotti è difficile determinare a priori il numero di ogget-ti riconoscibili nella scena, si prende, quindi, come riferimento il massimo numero di prodotti trovati dagli algoritmi (l’algoritmo 1 viene usato come riferimento).
5.4.1
Configurazione
Per questo test si mantiene la configurazione già riportata per l’algoritmo 2, ad eccezione del parametro num_bin_size che, per il prodotto B, viene impostato a 12. L’algoritmo 1 viene eseguito fino a terminazione per avere un riferimento sul totale dei prodotti trovati.
5.4.2
Risultati prodotto B
I risultati e i tempi di esecuzione1 sono riportati in tabella:
Algoritmo 1 Algoritmo 2
Oggetti individuati 277 229
Tempo esecuzione medio 20,8 s 16,0 s
Tabella 5.2: Risultati del Test 2 sul prodotto B
L’algoritmo 2 ha riconosciuto l’82,7% dei prodotti rispetto all’algoritmo 1. Nel grafico in figura 5.4 si riporta l’andamento della percentuale di oggetti riconosciuti in relazione al numero di cicli.
Si osserva che i cicli dal nono al dodicesimo apportano solo il 5,2% del totale dei prodotti riconosciuti. Il numero di cicli massimo di default è stato quindi fissato a 8.
5.4.3
Risultati prodotto C
Analogamente si riportano i risultati ottenuti per il prodotto C.
Con questo tipo di prodotto l’algoritmo 2 ha riconosciuto l’8,1% di pro-dotti in più rispetto alla versione 1.
5.5. Test 3: valutazione speedup 51 0,0 10,0 20,0 30,0 40,0 50,0 60,0 70,0 80,0 90,0 100,0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 % O gg e & r ic o n o sc iu . Ciclo
Figura 5.4: Andamento della percentuale di oggetti riconosciuti in relazione al numero di cicli per algoritmo 2 e prodotti di tipo B.
Algoritmo 1 Algoritmo 2
Oggetti individuati 149 161
Tempo esecuzione medio 20,2 s 16,2 s
Tabella 5.3: Risultati Test 2 sul prodotto C
L’andamento è analogo a quello ottenuto per il prodotto B, l’80% degli oggetti viene riconosciuto entro il quarto/quinto ciclo di esecuzione.
5.5
Test 3: valutazione
speedup
Con questo test si valuta lo speedup ottenuto con la versione parallela dell’al-goritmo 2. Per questo test è stata imposta una condizione di terminazione aggiuntiva, ovvero si termina l’elaborazione nel momento in cui sono stati trovati almeno 5 oggetti nella scena.
5.5.1
Configurazione
0,0 10,0 20,0 30,0 40,0 50,0 60,0 70,0 80,0 90,0 100,0 0 1 2 3 4 5 6 7 8 9 % O gg e & r ic o n o sc iu . Ciclo
Figura 5.5: Andamento della percentuale di oggetti riconosciuti in relazione al numero di cicli per algoritmo 2 e prodotti di tipo C.
5.5.2
Risultati
I risultati sono riportati in forma grafica in figura 5.6.
0 2 4 6 8 10 12 14 16 18 20 22 24 26
Prodo,o B Prodo,o C Media B-‐C
Temp o esecu zi o n e [s]
Tempo esecuzione medio
Seriale Parallelo 1,5 2,2 1,8 0,0 0,2 0,4 0,6 0,8 1,0 1,2 1,4 1,6 1,8 2,0 2,2 2,4
Prodo.o B Prodo.o C Media
Spe
e
d-‐
up
Speed-‐up
Figura 5.6: Risultati della valutazione dello speedup. A sinistra: tempo di esecuzione medio per scena, si confronta la versione seriale e quella parallela. A destra: speedup ottenuti testando i prodotti B e C e speedup medio.
5.6. Test 4: confronto 53
5.6
Test 4: confronto
Lo scopo di questo test è confrontare le prestazioni degli algoritmi studiati. In questo caso si imposta la stessa condizione di terminazione usata per valutare lo speedup, ovvero l’esecuzione viene terminata quando vengono individuati
almeno n match nella scena. Questo esperimento è motivato dal campo
di applicazione del sistema studiato. Infatti, non è necessario individuare ad ogni esecuzione tutti i prodotti ma la funzione fondamentale è quella di individuare almeno un oggetto prelevabile nel minor tempo possibile.
5.6.1
Configurazione
Il test è stato eseguito con i prodotti di tipo B e C sulle relative scene a disposizione nel dataset. Le configurazioni utilizzate sono quelle già riportate. Il numero minimo di prodotti n da individuare è stato impostato a {1,2,3,4}.
5.6.2
Risultati Prodotto B
Per ogni serie di tempi di esecuzione, ottenuti dall’esecuzione di un algoritmo fissando n a un valore, sono stati calcolati media e deviazione standard e distribuzione normale.
I dati ottenuti sono riportati in tabella:
n = 1 n = 2 n = 3 n = 4
Algoritmo 1 2 1 2 1 2 1 2
µ [s] 6,32 3,14 5,93 3,29 7,39 6,09 8,45 7,55
σ2[s] 1,87 0,45 2,15 0,92 2,43 2,48 2,47 2,89
Tabella 5.4: Risultati del Test 4
In figura 5.7 sono riportati i grafici delle funzioni di densità.
0 0,2 0,4 0,6 0,8 1 0 2 4 6 8 10 12 14 16 Den si tà
Tempo di esecuzione [s] 1 Match 0 0,2 0,4 0,6 0,8 1 0 2 4 6 8 10 12 14 16 Den si tà
Tempo di esecuzione [s] 2 Match 0 0,2 0,4 0,6 0,8 1 0 2 4 6 8 10 12 14 16 Den si tà
Tempo di esecuzione [s] 3 Match 0 0,2 0,4 0,6 0,8 1 0 2 4 6 8 10 12 14 16 Den si tà
Tempo di esecuzione [s] 4 Match 0" 0,2" 0,4" 0,6" 0,8" 1" 0" 2" 4" 6" 8" 10" 12" 14" 16" 18" 20" 4"Match Algoritmo"1" Algoritmo"2"
Figura 5.7: Curve gaussiane ottenute dai risultati dei test con il prodotto B. In ogni grafico si confronta la funzione di distribuzione dei tempi dei due algoritmi impostando come condizione di terminazione n = {1,2,3,4}. Tuttavia, una volta completato il clustering, l’algoritmo 1 procede più velo-cemente nella fase di riconoscimento in quanto il calcolo avviene sui singoli cluster che sono composti da molti meno punti rispetto alla scena.
5.6.3
Risultati Prodotto C
I dati ottenuti con questo tipo di prodotti sono riportati in tabella:
n = 1 n = 2 n = 3 n = 4
Algoritmo 1 2 1 2 1 2 1 2
µ [s] 6,53 4,85 8,68 6,57 10,88 9,93 12,74 12,13
σ2[s] 1,75 1,02 3,08 3,07 4,16 3,69 5,23 4,29
Tabella 5.5: Risultati del Test 4
