Robust Point Clouds Registration

Point clouds registration is a very well studied problem, with many different and efficient solutions. Nevertheless, the approaches in the literature rely heavily on a good initialization and on a good set of parameters. These approaches could be roughly divided into two categories: those based on features and the so-called closest-point-based. The first category aims at aligning two point clouds by first detecting some salient points, the keypoints, and calculating their descriptors so that they can be compared, in the same way it is usually done with 2D images. On the other hand, the latter category approximates correspondences by iteratively choosing the closest point, without the need for any kind of feature. The most important algorithm in this category is Iterative Closest Point (ICP). Most other algorithms are variants of ICP, so is one of the proposed approaches. In this work we introduce two novel solutions to point clouds registration. The first one is a variant of ICP, with a different data association, derived from a probabilistic model. The experiments show that is very effective at aligning a sparse point cloud with a dense one, one of the issues we had to face during this work. On the other hand, it showed very good results also on standard alignment problems, often better than other popular state of the art algorithms. We show that, for the most common approaches, the quality of the result is heavily dependent on some parameters that, thus, need to be carefully calibrated before the algorithms could be used in real applications. Moreover, a new calibration is usually required when facing a new scenario. For this reasons we propose this innovative technique, that aims, besides at being capable of aligning two generic point clouds, independently from their density, at being more robust w.r.t. wrong parameter sets. The second technique we developed is a global point cloud registration algorithm. ICP-like techniques requires, in order to converge to the right solution, an initial estimate of the transformation between the two point clouds. Without a proper initial guess, the algorithm will probably remain stuck in a local minima. On the other hand, feature-based techniques do not require any initial estimate but are not applicable to sparse point clouds, because they do not contain enough information to extract meaningful descriptors. The approach we developed combines the advantages of both approaches. It is based on a soft-computing technique, Particle Swarm Optimization, that is known for being able to escape from local optima. The result is an algorithm capable of aligning any kind of point cloud, without the need of any initial estimate of the transformation.

L’allineamento di Point Cloud (nuvole di punti) è un problema attuale e molto studiato, per il quale esistono molte soluzioni efficaci. Non di meno, gli approcci presenti in letteratura fanno affidamento su una buona inizializzazione e su un set di parametri adeguato. Questi approcci potrebbero venir divisi in due categorie: quelli basati sulle feature e quelli basati sulla distanza tra punti. Gli approcci che ricadono nella prima categoria, di solito, allineano due point cloud sfruttando dei punti salienti, keypoints, e un qualche tipo di descrittore, nello stesso modo che viene di solito usato con le immagini 2D. Gli approcci appartenenti alla seconda categoria, invece, non calcolano esplicitamente nessuna corrispondenza, ma queste vengono approssimate utilizzando il punto più vicino, senza la necessità di calcolare alcuna feature. L'algoritmo più importante in questa categoria è Iterative Closest Point (ICP). La maggior parte degli altri algoritmi, infatti, è una variante di ICP e lo stesso vale per uno degli approcci qui proposti. In questo lavoro introduciamo due nuove tecniche. La prima è una variante di ICP con una differente data association, basata su un modello probabilistico. Benché sia nata con l’obiettivo di allineare una point cloud molto sparsa, con una densa, ha dimostrato di essere capace di ottenere risultati qualitativamente migliori degli altri approcci anche su problemi di allineamento classici. Di notevole importanza, inoltre, è la sua bassa sensibilità ai parametri, un problema che, al contrario, affligge molti lavori presenti nella letteratura, come mostreremo, e che ne limita il loro utilizzo nel campo della robotica. Il secondo algoritmo da noi ideato è volto all’allineamento di due point cloud, senza la necessità di fornire alcuna stima iniziale sul loro allineamento. Questo è un vantaggio molto importante rispetto alle altre tecniche descritte nella letteratura. Mentre quelle basate su feature, benché siano in grado di allineare due nuvole di punti globalmente, senza necessità di una stima iniziale, non sono applicabili a point cloud sparse (uno dei casi che abbiamo dovuto affrontare durante questo lavoro), quelle basate su ICP hanno necessariamente bisogno di una stima iniziale adeguata, altrimenti convergeranno ad una soluzione sbagliata. L’approccio da noi utilizzato combina i vantaggi di entrambe le tecniche. E’ infatti applicabile ad ogni point cloud, indipendentemente dalla possibilità di estrarne feature, ma allo stesso tempo non ha bisogno di una stima iniziale. Per ottenere ciò abbiamo sfruttato un famoso algoritmo di ottimizzazione, Particle Swarm Optimization, che, benché non dia alcuna garanzia di convergenza ad un ottimo globale, in pratica ha mostrato una buona abilità nello uscire dagli ottimi locali, dove invece molti altri algoritmi rimangono intrappolati.