Farthest Point Sampling

• Detto anche: FPS, furthest point sampling
• Categoria: Sensing › Perception outputs
• Tag: point-cloud, sampling, 3d-perception, preprocessing, deep-learning

Un metodo greedy per scegliere un numero fisso di punti da una nuvola di punti in modo che si distribuiscano uniformemente sulla forma, scegliendo ripetutamente il punto più lontano da quelli già scelti.

Definizione

Campionamento del punto più lontano (farthest point sampling, FPS) seleziona un sottoinsieme di M punti da un insieme di N. Parte da un punto, scelto a caso o fissato, e a ogni passo aggiunge il punto la cui distanza dal punto già selezionato più vicino è massima. Un'implementazione conserva, per ogni punto in ingresso, la sua distanza dal punto selezionato più vicino e aggiorna quel valore dopo ogni aggiunta, quindi il costo cresce con N per M. Il risultato copre l'intera forma in modo uniforme, qualunque sia la densità del campionamento originale. La stessa regola greedy è la classica 2-approssimazione per il problema di clustering k-center, data da Gonzalez nel 1985.

Nel deep learning sulle nuvole di punti, l'FPS è diventato importante con PointNet++, che lo usa per scegliere i centri degli intorni locali a ogni livello, e molte reti successive lo usano per sottocampionare le nuvole in ingresso a una dimensione fissa prima dell'inferenza. Rispetto al campionamento casuale, che segue la densità dell'ingresso e può perdere parti sottili o osservate in modo rado, l'FPS mantiene la copertura dell'intero oggetto. Rispetto al sottocampionamento a griglia di voxel, restituisce un numero esatto di punti, che è ciò di cui hanno bisogno le reti con dimensioni d'ingresso fisse.

L'FPS ha dei compromessi. Favorisce deliberatamente gli outlier: un punto di rumore isolato è lontano da tutto il resto e viene scelto presto, per cui di norma le nuvole vengono filtrate prima. La procedura è sequenziale, il che la rende lenta su nuvole molto grandi; le implementazioni su GPU parallelizzano gli aggiornamenti delle distanze all'interno di ogni passo, e le varianti approssimate lavorano su partizioni spaziali. Il risultato dipende dal punto di partenza e, sulle mesh, le varianti geodetiche misurano la distanza lungo la superficie anziché in linea retta.

Perché è importante

Le reti per nuvole di punti richiedono ingressi di dimensione fissa, e i sensori di profondità producono molti più punti di quanti ne possano elaborare. Una copertura uniforme fa sì che parti piccole ma importanti, come manici, bordi e beccucci, sopravvivano al sottocampionamento, il che conta per la predizione di prese e affordance.

Applicazioni principali

• Pre-elaborazione delle nuvole di punti a una dimensione fissa per le reti neurali
• Scelta dei centri degli intorni nelle reti gerarchiche per punti
• Sottocampionamento delle nuvole prima di calcolare la distanza di Chamfer o la Earth mover's distance
• Selezione di un insieme distribuito di punti candidati di presa o di contatto
• Scelta di keypoint o campioni diversificati per la copertura

In pratica

Una telecamera di profondità sopra un banco di lavoro produce diverse centinaia di migliaia di punti per fotogramma. La pipeline ritaglia l'area di lavoro, rimuove gli outlier statistici, sottocampiona a voxel per ridurre il lavoro e poi esegue l'FPS per ottenere esattamente il numero di punti con cui la rete è stata addestrata, per esempio 2048. Il team usa la stessa procedura di campionamento in addestramento e sul robot, perché una rete addestrata su nuvole campionate con FPS vede una distribuzione di punti diversa da quella di una rete addestrata su campioni casuali.

Idee sbagliate comuni

• L'FPS dà un campione casuale uniforme — è deterministico una volta fissato il punto di partenza, e distribuisce i punti uniformemente nello spazio anziché campionare a caso
• L'FPS è robusto al rumore — gli outlier sono lontani da tutto il resto e vengono selezionati presto, per cui di norma le nuvole vengono filtrate prima
• L'FPS conserva l'informazione sulla densità della scansione — uniforma deliberatamente la densità, il che aiuta la copertura ma elimina l'indizio di dove il sensore ha visto più punti

Chi dovrebbe saperlo

• Ingegneri della percezione 3D
• Ricercatori di machine learning che lavorano su reti per nuvole di punti
• Ingegneri di manipolazione che usano policy basate su nuvole di punti

Tecnologie correlate

• PointNet++
• Sottocampionamento a griglia di voxel (Voxel Grid Downsampling)
• Campionamento casuale (Random Sampling)
• Clustering k-center (k-Center Clustering)
• Campionamento a disco di Poisson (Poisson Disk Sampling)
• Open3D

Termini correlati

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

Progetti correlati

• 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