Farthest Point Sampling

• Aussi appelé: FPS, furthest point sampling
• Catégorie: Sensing › Perception outputs
• Mots-clés: point-cloud, sampling, 3d-perception, preprocessing, deep-learning

Méthode gloutonne pour choisir un nombre fixe de points dans un nuage de points de sorte qu'ils se répartissent uniformément sur la forme, en choisissant de manière répétée le point le plus éloigné de ceux déjà choisis.

Définition

Échantillonnage par point le plus éloigné (farthest point sampling, FPS) : méthode qui sélectionne un sous-ensemble de M points parmi un ensemble de N. Elle part d'un point, choisi au hasard ou fixé, et ajoute à chaque étape le point dont la distance au plus proche point déjà sélectionné est la plus grande. Une implémentation conserve, pour chaque point d'entrée, sa distance au plus proche point sélectionné et met à jour cette valeur après chaque ajout, de sorte que le coût croît comme N fois M. Le résultat couvre toute la forme de manière homogène, quelle que soit la densité de l'échantillonnage d'origine. La même règle gloutonne est la 2-approximation classique du problème de partitionnement k-centre, donnée par Gonzalez en 1985.

En apprentissage profond sur nuages de points, le FPS s'est imposé avec PointNet++, qui l'utilise pour choisir les centres des voisinages locaux à chaque couche, et de nombreux réseaux ultérieurs l'emploient pour sous-échantillonner les nuages d'entrée à une taille fixe avant l'inférence. Par rapport à l'échantillonnage aléatoire, qui suit la densité de l'entrée et peut manquer des parties fines ou peu observées, le FPS conserve la couverture de l'objet entier. Par rapport au sous-échantillonnage par grille de voxels, il renvoie un nombre exact de points, ce dont ont besoin les réseaux à taille d'entrée fixe.

Le FPS comporte des compromis. Il favorise délibérément les points aberrants : un point de bruit isolé est loin de tout le reste et il est choisi tôt, c'est pourquoi les nuages sont normalement filtrés d'abord. La procédure est séquentielle, ce qui la rend lente sur de très grands nuages ; les implémentations GPU parallélisent les mises à jour de distance au sein de chaque étape, et des variantes approchées travaillent sur des partitions spatiales. Le résultat dépend du point de départ, et sur les maillages, des variantes géodésiques mesurent la distance le long de la surface plutôt qu'en ligne droite.

Pourquoi c'est important

Les réseaux pour nuages de points ont besoin d'entrées de taille fixe, et les capteurs de profondeur produisent bien plus de points qu'ils ne peuvent en traiter. Une couverture homogène signifie que des parties petites mais importantes, comme les poignées, les bords et les becs, survivent au sous-échantillonnage, ce qui compte pour la prédiction de prises et d'affordances.

Applications principales

• Prétraitement des nuages de points à une taille fixe pour les réseaux de neurones
• Choix des centres de voisinage dans les réseaux de points hiérarchiques
• Sous-échantillonnage des nuages avant le calcul de la distance de Chamfer ou de l'Earth mover's distance
• Sélection d'un ensemble bien réparti de points candidats de prise ou de contact
• Choix de points clés ou d'échantillons variés pour la couverture

En pratique

Une caméra de profondeur au-dessus d'un établi produit plusieurs centaines de milliers de points par image. La chaîne de traitement recadre l'espace de travail, supprime les points aberrants statistiques, sous-échantillonne par voxels pour réduire le travail, puis exécute le FPS pour obtenir exactement le nombre de points avec lequel le réseau a été entraîné, par exemple 2048. L'équipe utilise la même procédure d'échantillonnage à l'entraînement et sur le robot, car un réseau entraîné sur des nuages échantillonnés par FPS voit une distribution de points différente de celle d'un réseau entraîné sur des échantillons aléatoires.

Idées reçues

• Le FPS fournit un échantillon aléatoire uniforme — il est déterministe une fois le point de départ fixé, et répartit les points uniformément dans l'espace au lieu d'échantillonner au hasard
• Le FPS est robuste au bruit — les points aberrants sont loin de tout le reste et sont sélectionnés tôt, c'est pourquoi les nuages sont normalement filtrés d'abord
• Le FPS conserve l'information de densité du scan — il égalise délibérément la densité, ce qui aide la couverture mais supprime l'indice de l'endroit où le capteur a vu plus de points

Qui devrait le savoir

• Ingénieurs en perception 3D
• Chercheurs en apprentissage automatique travaillant sur les réseaux pour nuages de points
• Ingénieurs en manipulation qui utilisent des politiques fondées sur des nuages de points

Technologies associées

• PointNet++
• Sous-échantillonnage par grille de voxels (Voxel Grid Downsampling)
• Échantillonnage aléatoire (Random Sampling)
• Partitionnement k-centre (k-Center Clustering)
• Échantillonnage par disques de Poisson (Poisson Disk Sampling)
• Open3D

Termes associés

• Point Cloud
• Chamfer Distance
• Octree
• Depth Camera
• Open-Vocabulary Detection

Projets associés

• Open3D: Modern library for 3D point cloud processing, mesh operations, and 3D machine learning
• PCL: Industry-standard C++ library for point cloud processing in robotics perception
• OpenDroneMap: Open-source photogrammetry toolkit that turns drone images into maps and 3D models
• pySLAM: Hybrid Python/C++ visual SLAM pipeline with classic and deep-learning front-ends
• LeGO-LOAM: Classic lightweight, ground-optimized lidar odometry and mapping baseline (IROS 2018)
• libpointmatcher: Modular ICP library for 2D/3D point cloud registration and mapping