Farthest Point Sampling
- 다른 이름: FPS, furthest point sampling
- 카테고리: Sensing › Perception outputs
- 태그: point-cloud, sampling, 3d-perception, preprocessing, deep-learning
이미 선택된 점들에서 가장 먼 점을 반복해서 골라, 점군에서 정해진 수의 점을 형상 전체에 고르게 퍼지도록 고르는 탐욕적 방법.
정의
최원점 샘플링(farthest point sampling, FPS)은 N개의 점 집합에서 M개의 점으로 이루어진 부분집합을 선택한다. 무작위로 고르거나 고정한 한 점에서 시작해, 각 단계에서 이미 선택된 점 중 가장 가까운 점까지의 거리가 가장 큰 점을 추가한다. 구현은 모든 입력 점에 대해 가장 가까운 선택된 점까지의 거리를 유지하고 매번 추가한 뒤 그 값을 갱신하므로, 비용은 N 곱하기 M에 비례해 늘어난다. 결과는 원래 샘플링의 밀도가 어떻든 형상 전체를 고르게 덮는다. 같은 탐욕적 규칙은 1985년 Gonzalez가 제시한, k-중심 군집화 문제에 대한 고전적인 2-근사 알고리즘이다.
점군 딥러닝에서 FPS는 PointNet++를 통해 두드러지게 되었는데, PointNet++는 각 층에서 국소 이웃의 중심을 고르는 데 FPS를 사용하며, 이후의 많은 네트워크는 추론 전에 입력 점군을 고정된 크기로 다운샘플링하는 데 이를 사용한다. 입력의 밀도를 따르며 얇거나 드물게 관측된 부분을 놓칠 수 있는 무작위 샘플링과 비교해, FPS는 물체 전체의 커버리지를 유지한다. 복셀 격자 다운샘플링과 비교하면, 고정된 입력 크기를 가진 네트워크에 필요한 정확한 수의 점을 반환한다.
FPS에는 트레이드오프가 있다. 이상점을 의도적으로 선호한다. 고립된 잡음 점은 다른 모든 것에서 멀리 떨어져 있어 일찍 선택되므로, 점군은 보통 먼저 필터링한다. 절차가 순차적이어서 매우 큰 점군에서는 느리다. GPU 구현은 각 단계 안에서 거리 갱신을 병렬화하고, 근사 변형은 공간 분할 위에서 작동한다. 출력은 시작점에 따라 달라지며, 메시에서는 측지선 변형이 직선 대신 표면을 따라 거리를 잰다.
중요한 이유
점군 네트워크는 고정된 크기의 입력이 필요하고, 깊이 센서는 네트워크가 처리할 수 있는 것보다 훨씬 많은 점을 만든다. 고른 커버리지는 손잡이, 가장자리, 주둥이처럼 작지만 중요한 부분이 다운샘플링 후에도 살아남는다는 뜻이며, 이는 파지 및 어포던스 예측에 중요하다.
주요 응용
- 신경망을 위해 점군을 고정된 크기로 전처리
- 계층적 점 네트워크에서 이웃 중심 선택
- Chamfer 거리나 Earth mover's distance를 계산하기 전 점군 다운샘플링
- 후보 파지점이나 접촉점을 고르게 퍼지도록 선택
- 커버리지를 위해 다양한 키포인트나 샘플 선택
실제 사례
작업대 위의 깊이 카메라는 프레임마다 수십만 개의 점을 만든다. 파이프라인은 작업 공간을 잘라 내고, 통계적 이상점을 제거하고, 작업량을 줄이기 위해 복셀 다운샘플링을 한 다음, FPS를 실행해 네트워크가 학습된 것과 정확히 같은 수, 예를 들어 2048개의 점을 얻는다. 팀은 학습과 로봇 위에서 같은 샘플링 절차를 사용하는데, FPS로 샘플링한 점군으로 학습한 네트워크는 무작위 샘플로 학습한 네트워크와 다른 점 분포를 보기 때문이다.
흔한 오해
- FPS는 균일한 무작위 샘플을 준다 — 시작점이 고정되면 결정론적이며, 무작위로 샘플링하는 것이 아니라 공간에 점을 고르게 퍼뜨린다
- FPS는 잡음에 강건하다 — 이상점은 다른 모든 것에서 멀리 떨어져 있어 일찍 선택되므로, 점군은 보통 먼저 필터링한다
- FPS는 스캔의 밀도 정보를 유지한다 — 의도적으로 밀도를 고르게 만들며, 이는 커버리지에 도움이 되지만 센서가 어디에서 더 많은 점을 보았는지라는 단서를 없앤다
알아야 할 사람
- 3D 인식 엔지니어
- 점군 네트워크를 연구하는 머신러닝 연구자
- 점군 정책을 사용하는 매니퓰레이션 엔지니어
관련 기술
- PointNet++
- 복셀 격자 다운샘플링(Voxel Grid Downsampling)
- 무작위 샘플링(Random Sampling)
- k-중심 군집화(k-Center Clustering)
- 푸아송 디스크 샘플링(Poisson Disk Sampling)
- Open3D
관련 용어
관련 프로젝트
- 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