Farthest Point Sampling

• Também chamado: FPS, furthest point sampling
• Categoria: Sensing › Perception outputs
• Tags: point-cloud, sampling, 3d-perception, preprocessing, deep-learning

Um método guloso para escolher um número fixo de pontos de uma nuvem de pontos de modo que eles se espalhem uniformemente sobre a forma, escolhendo repetidamente o ponto mais distante dos já escolhidos.

Definição

Amostragem do ponto mais distante (farthest point sampling, FPS) seleciona um subconjunto de M pontos a partir de um conjunto de N. Ela começa por um ponto, escolhido ao acaso ou fixo, e a cada passo acrescenta o ponto cuja distância ao ponto já selecionado mais próximo é a maior. Uma implementação guarda, para cada ponto de entrada, sua distância ao ponto selecionado mais próximo e atualiza esse valor após cada adição, então o custo cresce com N vezes M. O resultado cobre a forma inteira de modo uniforme, qualquer que seja a densidade da amostragem original. A mesma regra gulosa é a clássica 2-aproximação para o problema de agrupamento k-centro, dada por Gonzalez em 1985.

No aprendizado profundo com nuvens de pontos, a FPS ganhou destaque com o PointNet++, que a usa para escolher os centros das vizinhanças locais em cada camada, e muitas redes posteriores a usam para subamostrar as nuvens de entrada para um tamanho fixo antes da inferência. Em comparação com a amostragem aleatória, que segue a densidade da entrada e pode perder partes finas ou pouco observadas, a FPS mantém a cobertura do objeto inteiro. Em comparação com a subamostragem por grade de voxels, ela retorna um número exato de pontos, que é o que redes com tamanhos de entrada fixos precisam.

A FPS tem contrapartidas. Ela favorece deliberadamente os outliers: um ponto de ruído isolado fica longe de todo o resto e é escolhido cedo, por isso as nuvens normalmente são filtradas antes. O procedimento é sequencial, o que o torna lento em nuvens muito grandes; implementações em GPU paralelizam as atualizações de distância dentro de cada passo, e variantes aproximadas trabalham sobre partições espaciais. O resultado depende do ponto de partida e, em malhas, variantes geodésicas medem a distância ao longo da superfície em vez de em linha reta.

Por que importa

Redes para nuvens de pontos precisam de entradas de tamanho fixo, e sensores de profundidade produzem muito mais pontos do que elas conseguem processar. Cobertura uniforme significa que partes pequenas mas importantes, como alças, bordas e bicos, sobrevivem à subamostragem, o que importa para a predição de preensão e de affordances.

Principais aplicações

• Pré-processamento de nuvens de pontos para um tamanho fixo para redes neurais
• Escolha dos centros de vizinhança em redes hierárquicas de pontos
• Subamostragem de nuvens antes de calcular a distância de Chamfer ou a Earth mover's distance
• Seleção de um conjunto espalhado de pontos candidatos de preensão ou de contato
• Escolha de pontos-chave ou amostras diversos para cobertura

Na prática

Uma câmera de profundidade sobre uma bancada produz várias centenas de milhares de pontos por quadro. O pipeline recorta a área de trabalho, remove outliers estatísticos, faz subamostragem por voxels para reduzir o trabalho e então roda a FPS para obter exatamente o número de pontos com que a rede foi treinada, por exemplo 2048. A equipe usa o mesmo procedimento de amostragem no treinamento e no robô, porque uma rede treinada com nuvens amostradas por FPS vê uma distribuição de pontos diferente da de uma treinada com amostras aleatórias.

Equívocos comuns

• A FPS dá uma amostra aleatória uniforme — ela é determinística depois que o ponto de partida é fixado, e espalha os pontos uniformemente no espaço em vez de amostrar ao acaso
• A FPS é robusta a ruído — outliers ficam longe de todo o resto e são selecionados cedo, por isso as nuvens normalmente são filtradas antes
• A FPS preserva a informação de densidade da varredura — ela iguala deliberadamente a densidade, o que ajuda a cobertura, mas remove a pista de onde o sensor viu mais pontos

Quem deve saber

• Engenheiros de percepção 3D
• Pesquisadores de machine learning que trabalham com redes para nuvens de pontos
• Engenheiros de manipulação que usam políticas baseadas em nuvens de pontos

Tecnologias relacionadas

• PointNet++
• Subamostragem por grade de voxels (Voxel Grid Downsampling)
• Amostragem aleatória (Random Sampling)
• Agrupamento k-centro (k-Center Clustering)
• Amostragem de disco de Poisson (Poisson Disk Sampling)
• Open3D

Termos relacionados

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

Projetos 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