Super 4PCS : Registration rapide globale de nuages de points par indexation intelligente

L’acquisition de données dans des scènes à grande échelle implique régulièrement l’accumulation d’informations issues de plusieurs balayages. Une approche courante consiste à aligner localement des paires de balayages à l’aide de l’algorithme ICP (ou de ses variantes), mais celle-ci suppose des scènes statiques et des déplacements faibles entre les paires de balayages. Cette contrainte empêche l’accumulation de données sur plusieurs sessions de balayage et/ou avec des modalités d’acquisition différentes (par exemple, stéréo, balayages en profondeur). À la place, on peut utiliser un algorithme d’enregistrement global permettant aux balayages d’être initialement placés dans des poses arbitraires. Toutefois, l’état de l’art en matière d’enregistrement global, l’algorithme 4PCS, présente une complexité temporelle quadratique par rapport au nombre de points de données, ce qui limite considérablement son application à l’acquisition d’environnements de grande taille. Nous proposons Super 4PCS, une méthode d’enregistrement global de nuages de points qui est optimale, c’est-à-dire qu’elle fonctionne en temps linéaire (par rapport au nombre de points) et est également sensible à la sortie, c’est-à-dire que sa complexité dépend de la surprenance (inconnue) entre les paires de balayages. Techniquement, nous reformulons l’algorithme comme un problème d’instance et le résolvons efficacement grâce à une organisation intelligente des données par indexation. L’algorithme est simple, efficace en mémoire et rapide. Nous démontrons que Super 4PCS permet une accélération significative par rapport aux approches alternatives, et ouvre la voie à une acquisition non structurée et efficace de scènes à des échelles auparavant inaccessibles. Le code source complet et les jeux de données sont disponibles à l’adresse suivante pour une utilisation de recherche : http://geometry.cs.ucl.ac.uk/projects/2014/super4PCS/.