Farthest Point Sampling
- También llamado: FPS, furthest point sampling
- Categoría: Sensing › Perception outputs
- Etiquetas: point-cloud, sampling, 3d-perception, preprocessing, deep-learning
Un método voraz para escoger un número fijo de puntos de una nube de puntos de modo que se repartan de manera uniforme sobre la forma, eligiendo repetidamente el punto más alejado de los ya elegidos.
Definición
Muestreo del punto más lejano (farthest point sampling, FPS) selecciona un subconjunto de M puntos a partir de un conjunto de N. Empieza por un punto, elegido al azar o fijo, y en cada paso añade el punto cuya distancia a su punto ya seleccionado más cercano es la mayor. Una implementación guarda, para cada punto de entrada, su distancia al punto seleccionado más cercano y actualiza ese valor tras cada adición, así que el coste crece con N por M. El resultado cubre toda la forma de manera uniforme, sea cual sea la densidad del muestreo original. La misma regla voraz es la clásica 2-aproximación para el problema de agrupamiento k-centro, dada por Gonzalez en 1985.
En el aprendizaje profundo sobre nubes de puntos, el FPS cobró protagonismo con PointNet++, que lo usa para elegir los centros de las vecindades locales en cada capa, y muchas redes posteriores lo usan para submuestrear las nubes de entrada a un tamaño fijo antes de la inferencia. En comparación con el muestreo aleatorio, que sigue la densidad de la entrada y puede perder partes finas o escasamente observadas, el FPS mantiene la cobertura de todo el objeto. En comparación con el submuestreo por rejilla de vóxeles, devuelve un número exacto de puntos, que es lo que necesitan las redes con tamaños de entrada fijos.
El FPS tiene contrapartidas. Favorece deliberadamente los valores atípicos: un punto de ruido aislado está lejos de todo lo demás y se elige pronto, así que normalmente las nubes se filtran antes. El procedimiento es secuencial, lo que lo hace lento en nubes muy grandes; las implementaciones en GPU paralelizan las actualizaciones de distancia dentro de cada paso, y las variantes aproximadas trabajan sobre particiones espaciales. El resultado depende del punto de partida, y en mallas, las variantes geodésicas miden la distancia a lo largo de la superficie en lugar de en línea recta.
Por qué importa
Las redes para nubes de puntos necesitan entradas de tamaño fijo, y los sensores de profundidad producen muchos más puntos de los que pueden procesar. Una cobertura uniforme significa que partes pequeñas pero importantes, como asas, bordes y picos, sobreviven al submuestreo, lo que importa para la predicción de agarres y de affordances.
Aplicaciones clave
- Preprocesamiento de nubes de puntos a un tamaño fijo para redes neuronales
- Elección de los centros de vecindad en redes jerárquicas de puntos
- Submuestreo de nubes antes de calcular la distancia de Chamfer o la Earth mover's distance
- Selección de un conjunto repartido de puntos candidatos de agarre o de contacto
- Elección de puntos clave o muestras diversos para la cobertura
En la práctica
Una cámara de profundidad sobre un banco de trabajo produce varios cientos de miles de puntos por fotograma. El pipeline recorta el área de trabajo, elimina los valores atípicos estadísticos, aplica un submuestreo por vóxeles para reducir el trabajo y luego ejecuta el FPS para obtener exactamente el número de puntos con el que se entrenó la red, por ejemplo 2048. El equipo usa el mismo procedimiento de muestreo en el entrenamiento y en el robot, porque una red entrenada con nubes muestreadas por FPS ve una distribución de puntos distinta de la de una entrenada con muestras aleatorias.
Ideas erróneas comunes
- El FPS da una muestra aleatoria uniforme — es determinista una vez fijado el punto de partida, y reparte los puntos de manera uniforme en el espacio en lugar de muestrear al azar
- El FPS es robusto al ruido — los valores atípicos están lejos de todo lo demás y se seleccionan pronto, así que normalmente las nubes se filtran antes
- El FPS conserva la información de densidad del escaneo — iguala deliberadamente la densidad, lo que ayuda a la cobertura pero elimina la pista de dónde vio el sensor más puntos
Quién debería saberlo
- Ingenieros de percepción 3D
- Investigadores en aprendizaje automático que trabajan con redes para nubes de puntos
- Ingenieros de manipulación que usan políticas basadas en nubes de puntos
Tecnologías relacionadas
- PointNet++
- Submuestreo por rejilla de vóxeles (Voxel Grid Downsampling)
- Muestreo aleatorio (Random Sampling)
- Agrupamiento k-centro (k-Center Clustering)
- Muestreo de disco de Poisson (Poisson Disk Sampling)
- Open3D
Términos relacionados
Proyectos relacionados
- 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