Moduli

La libreria `e scomposta in svariati moduli che implementano funzionalit`a e interfacce da offrire ad altri moduli e al programmatore:

• pcl_common

raggruppa tutte le strutture dati e i loro metodi che sono condivisi e servono a tutti gli altri moduli della libreria: `e qui che si trova la classe PointCloude tutti i PointType, da quelli pi`u semplici fino a quelli pi`u

complessi relativi ai descrittori di features; funge anche da contenitore di tutti quei metodi strettamente algebrici e indipendenti dal contesto delle point cloud ma che vengono spesso utilizzati dagli algoritmi come strumenti indispensabili: calcolo distanze, norme, medie, covarianze, trasformazioni geometriche e molte altre;

• pcl_features

`

e uno dei moduli pi`u importanti per realizzare applicazioni che ese- guono confronti fra point cloud perch´e permette di sintetizzare delle descrizioni ad-hoc che siano compatte e pi`u descrittive dei singoli punti della nuvola (cap. 5). Questo modulo contiene tutte le strutture dati e metodi per mettere in pratica la maggior parte degli algoritmi presenti allo stato dell’arte nell’ambito della descrizione di point cloud;

• pcl_filters

Ogni rilevazione e misura operata con sensori `e soggetta ad errori che generano disturbo e rumore per la presenza di punti outliers, ovvero punti estranei che non avrebbero dovuto essere presenti nella nuvola. Questo modulo contiene molti algoritmi utili per filtrare questo genere di punti secondo svariati criteri pi`u o meno precisi. Fra gli algoritmi proposti per filtrare ci sonoPassThroughche seleziona punti in base ai limiti

di coordinate impostate dal programmatore; Conditionalche si basa sulla

definizione di funzioni di validit`a sulle propriet`a dei punti; RadiusOutlier

che esclude tutti i punti che non hanno una sufficiente quantit`a di vicini all’interno della loro sfera d’azione; StatisticalOutlierRemovalche sfrutta la

densit`a e rimuove i punti lontani dalla media statistica delle distanze inter-punto;VoxelGridche effettua il downsampling suddividendo la point

cloud in volumi elementari (voxel); • pcl_kdtree

serve per realizzare strutture di memorizzazione complesse come alberi a k dimensioni; un kD-Tree partiziona lo spazio dati e memorizza un insieme di punti a k dimensioni in una struttura ad albero; lo scopo per cui sono utilizzati `e sostanzialmente la ricerca di k nearest neighbors oppure una range search, dato un punto di partenza. Sono cruciali

per trovare corrispondenze fra gruppi di punti o descrittori di featu- res. Esiste anche la versione approssimata FLANN (Fast Library for Approximate Nearest Neighbor), pi`u veloce ma meno precisa;

• pcl_keypoints

`

e il modulo fondamentale per la branca delle features locali; i punti chiave o keypoints sono punti di particolare interesse, rappresentativi di propriet`a specifiche ricercate dagli algoritmi facenti parte di questo modulo. Tali punti ritrovati vengono poi usati in combinazione con algoritmi di descrizione di features locali, ovvero viene circoscritto il calcolo delle descrizioni alle regioni intorno a ciascun keypoint. Servo- no per ridurre il numero di punti in un minor quantitativo giudicato essenziale, stabile e distintivo per riconoscere regioni della point cloud intera;

• pcl_io

`

e il modulo che contiene classi e funzioni per le interazioni di input e output con dispositivi di acquisizione depth-camera o la memoria di massa. I file sono in formato .pcd e vengono modificati tramite appositi metodi di read e save; invece le acqusizioni di point cloud sfruttano il framework OpenNI che sviluppa driver open source per periferiche come le depth-camera. PCL per`o offre una nuova interfaccia grabber generica per fornire un accesso rapido e snello a vari dispositivi e ai loro driver. L’interfaccia del driver grabber `e molto potente e riesce a trattare in modo generale tutte le videocamere compatibili con OpenNI permettendo quindi al programma di collegarsi ad esse con facilt`a; • pcl_registration

la ”image registration” `e il processo di trasformazione di diversi insiemi di dati e la ricomposizione in un unico sistema di coordinate; per dati diversi si intendono fotografie 3D da pi`u punti di vista, tempi diversi e/o con sensori diversi. Con queste tecniche si pu`o ricomporre la scena intera utilizzando tutti i dati raccolti;

• pcl_segmentation

`

e il modulo che contiene algoritmi per segmentare le point cloud; serve per isolare parti (cluster) da scene complesse e analizzarle separata- mente in modo indipendente da tutto il resto che le circonda. `E uno strumento essenziale per le applicazioni che devono riconoscere e af- ferrare gli oggetti perch´e devono poterlo riconoscere nel mezzo di una

scena. Gli strumenti possibili sono laEuclideanClusterExtraction basata sul-

la distanza di punti; ConditionalEuclideanClusteringsimile al precedente ma

con ulteriori funzioni booleane create dal programmatore; RegionGrowing

eRegionGrowingRGB usati per raggruppare punti in base alla levigatura sul-

la superficie; MinCutSegmentation per separare dall’esterno punti all’interno

di regioni sferiche; oppure DifferenceOfNormalsEstimation che individua pun-

ti che appartengono ad una certa scala, usato per point cloud molto grosse;

• pcl_sample_consensus

contiene modelli geometrici elementari che possono essere usati per identificarli e trovarli nelle point cloud. Possono essere linee, piani, di- schi, sfere, cilindri e molti altri; esistono dei metodi appositi che iden- tificano la somiglianza con i modelli a partire da parametri impostati dal programmatore. Per esempio un modello planare `e utile per isolare dagli oggetti le superfici come tavoli e muri;

• pcl_visualization

Permette tutte le operazioni grafiche per visualizzare e riprodurre su schermo le point cloud e le operazioni compiute su di esse. Fra quelli pi`u usati ci sono il PCLVisualizere PCLPlotter.

Per quanto riguarda la parte di I/O `e utile spiegare il progetto OpenNI (Open Natural Interaction) da cui dipende anche la PCL. Si trattava di un framework cross-platform open-source in grado di gestire l’interazione con dispositive NI (Natural Interaction) mediante interfacce API. I dispositivi di questa famiglia sono in grado di riprodurre i principali sensi umani, come la vista e l’udito ma anche il tatto. Nell’ambito della percezione spaziale supporta varie RGB-camera famose come la MS Kinect e Asus XTion.

Le API OpenNI si occupano di gestire in modo standard la variet`a di dispositivi esistenti, consentendo quindi di sviluppare applicazioni che so- no indipendenti dal dispositivo usato, a patto che sia compatibile con le interfacce API per sensori e software applicativo.

Descrizione degli oggetti

Un camera-3D non riproduce una point cloud contenente solo l’oggetto da individuare ma anche tutta la scena che rientra nel suo campo visivo. Il risultato di questa acqusizione `e una point cloud generalmente grande qualche centinaia di migliaia di punti. L’oggetto di interesse si trova all’interno di questa scena insieme a tutto il resto. Analizzarla tutta comporterebbe un notevole sforzo computazionale.

Pertanto si rendono necessari dei passaggi di pre-elaborazione dei dati grezzi ottenuti dal sensore visivo. La pipeline generale composta dalle singole fasi `e rappresentata in figura 5.1.

Figura 5.1: Pipeline di elaborazione della point cloud 45

5.1

Segmentazione

`

E necessario individuare l’oggetto di interesse all’interno della scena. Tale operazione si chiama segmentazione o clustering; consiste nella suddivisione di tutti i punti della scena inquadrata in sottoinsiemi che rappresentano le sue parti, secondo criteri predeterminati. Individuare l’oggetto fin da subito riduce anche il costo computazionale in termini di tempo e memoria nelle fasi successive.

Figura 5.2: Esempio scena ripresa. Fonte: pointclouds.org

Verranno adottate due tecniche che permettono di isolare cluster di punti che possiedono determinate propriet`a geometriche. Per individuare cluster particolari relativi ai piani si far`a ricorso al moduloSampleConsensus; per quanto

riguarda gli altri cluster si ricorre alla tecnica EuclideanCluster.

L’approccio euclideo [11] `e semplice ma serve bene allo scopo di indivi- duare oggetti solidi, i cui punti sono densamente concentrati in regioni dello spazio. L’algoritmo fa uso delle distanze euclidee per calcolare la vicinanza fra punti e isolarli in cluster separati.

Gli step dell’algoritmo possono essere cos`ı schematizzati:

• aggiungere il generico punto pinon analizzato ad una lista (inizialmente

vuota);

• per ogni punto appartenente alla lista:

– individuare tutti i punti che distano meno di una certa distanza d < raggiosoglia;

– fra questi mettere i punti che non sono stati analizzati all’interno della lista e ripetere l’analisi;

• se tutti i punti sono stati analizzati, la lista di punti corrisponde ad un cluster;

• estrarre il cluster dalla point cloud e ripetere per trovare altri cluster; • se non ci sono punti rimasti l’algoritmo termina.

L’altro procedimento usato per individuare i piani si chiama RANSAC (RANdom SAmple Consensus) [12].

Si tratta di una tecnica iterativa per stimare parametri di un modello geometrico sintetico all’interno di un insieme di dati. Non `e deterministico perch´e produce risultati corretti secondo una certa probabilit`a crescente con il numero di iterazioni eseguite. L’idea di base `e che i dati possono essere suddivisi in inliers e outliers a seconda che rispettino o meno le caratteristiche di un modello. L’obiettivo viene raggiunto in seguito a una serie di iterazioni in cui viene scelto e perfezionato un sottoinsieme casuale dei dati.

Gli step dell’algoritmo possono essere cos`ı schematizzati: • si seleziona un sottoinsieme di punti;

• come assunzione iniziale vengono considerati tutti inliers, ovvero si sup- pone che siano punti che rispettano il modello predefinito e si calcolano le sue propriet`a;

• si aggiungono altri punti casuali e si verificano di nuovo le ipotesi per vedere quanti inliers sono stati prodotti;

• se non viene rispettata una certa tolleranza d’errore si riparte con un’altra selezione casuale, altrimenti si aggiungono i nuovi inliers e si ricalcolano le propriet`a geometriche del nuovo cluster.

La stima del modello `e abbastanza robusta anche in presenza di outliers perch´e fa uso di modelli preconfezionati con cui esegue il fitting. Il rovescio della medaglia `e che una tecnica del genere non ha un limite superiore al nu- mero di esecuzione per restituire un risultato corretto, pertanto `e necessario valutare bene il numero di iterazioni da fare a seconda della complessit`a dei dati e del loro quantitativo.

Supponendo per ipotesi progettuale che l’oggetto da individuare si trovi appoggiato su un tavolo `e possibile seguire la seguente procedura:

1. `e necessario prima di tutto trovare la zona del tavolo; per fare ci`o si devono ricercare cluster planari, ovvero che presentano punti tutti pi`u o meno alla stessa altezza e vicini entro un margine di tolleranza affinch´e vengano considerati appartenti al cluster; in una scena come quella enunciata nella premessa, gli unici due piani saranno il pavimento e il tavolo. Fra i due, il tavolo corrisponder`a al cluster con numero minore di punti;

2. viene calcolata quindi la sua altezza dal suolo, facendo la media delle componenti Y dei punti del cluster;

3. si eliminano dalla scena i punti corrispondenti ai piani e con quelli ri- manenti si passa alla clusterizzazione euclidea che consiste nel ricavare dalla scena tutti i sottoinsiemi di punti che sono pi`u vicini di una certa distanza di tolleranza. Il motivo `e che qualsiasi oggetto solido e com- patto presenter`a punti vicini fra loro. Si tratta di una clusterizzazione pi`u generale e meno restrittiva della precedente che aveva il vincolo della planarit`a;

4. fra tutti questi cluster quello che corrisponder`a all’oggetto `e quello che si trova ad una distanza dal suolo pari a quella del tavolo, calcolata precedentemente; in altre parole `e il cluster i cui punti hanno compo- nenti Y maggiori dell’altezza del tavolo. In una scena del genere non ci saranno dubbi su quale sia l’oggetto perch´e il tavolo `e uno solo, cos`ı come l’oggetto in questione. Qualsiasi altro cluster che compare nella scena non risponder`a ai requisiti richiesti (o sar`a sul pavimento o po- tr`a trovarsi sospeso in aria nel mezzo della scena; il primo caso viene escluso dall’algoritmo, il secondo `e molto improbabile);

5. tuttavia se si vuole rendere il sistema pi`u tutelato da queste interferenze si pu`o selezionare l’oggetto anche in base alle coordinate X e Z relative ai margini del tavolo precedentemente individuato.

Nel caso in cui ci siano pi`u oggetti sul tavolo, l’algoritmo `e estendibile dato che basta non inserire la condizione di terminazione una volta trovato l’oggetto le cui coordinate corrispondono a quelle di un oggetto sopra il tavolo. Lasciandolo continuare in questo modo, l’algoritmo li isola tutti seguendo lo stesso criterio e alla fine invece di avere una sola point cloud corrispondente all’oggetto si avr`a una serie di point cloud di oggetti che stanno sul tavolo.

Un algoritmo del genere `e del tutto indipendente dalla posizione della telecamera la quale pu`o quindi trovarsi in qualsiasi punto della scena e spo- starsi al suo interno. La ragione `e che l’algoritmo non si basa su coordinate fisse in cui ci si aspetta di trovare l’oggetto, ma gli basta individuare il tavolo in qualunque punto si trovi; da l`ı poi ricava la point cloud di ci`o che vi sta sopra.

Supponendo invece che la posizione relativa del tavolo rispetto alla tele- camera rimanga fissa in una regione ben definita da estremi espressi in coor- dinate XYZ note, si pu`o semplificare l’algoritmo evitando di fare clustering sull’intera point cloud ma posticipandolo a seguito di una pre-elaborazione:

1. eliminare tutti i punti le cui coordinate X superano quelle dei margini laterali del tavolo;

2. eliminare tutti i punti le cui altezze Y sono inferiori a quelle del tavolo; 3. eliminare tutti i punti la cui profondit`a Z `e superiore a quella del

margine posteriore del tavolo;

4. in questo modo si eliminano con un rapido ciclo tutti i punti non neces- sari e si ottiene una point cloud estremamente ridotta in cui compaiono solo la superficie planare del tavolo e l’oggetto sopra di essa;

5. a questo punto si pu`o ripetere l’algoritmo che individua il piano, ma stavolta trover`a un solo cluster, quindi sar`a pi`u veloce;

6. fra i cluster restanti quello con maggior numero di punti sar`a l’oggetto desiderato (eventuali altri cluster minori saranno dovuti ai possibili disturbi presenti sulla scena).

`

E evidente che un algoritmo di questo tipo potrebbe non funzionare se le posizioni relative camera-tavolo vengono modificate eccessivamente.

(c) Fase 4 (d) Fase 6