Farthest Point Sampling

• 別名: FPS, furthest point sampling
• カテゴリ: Sensing › Perception outputs
• タグ: point-cloud, sampling, 3d-perception, preprocessing, deep-learning

すでに選んだ点から最も遠い点を繰り返し選ぶことで、点群から形状全体に均等に広がる固定数の点を選ぶ貪欲な手法。

定義

最遠点サンプリング（Farthest point sampling、FPS）は、N 点の集合から M 点の部分集合を選ぶ。ランダムに選ぶか固定した 1 点から始め、各ステップで、すでに選ばれた点のうち最も近いものまでの距離が最大となる点を加える。実装では、各入力点について最も近い選択済みの点までの距離を保持し、点を加えるたびにその値を更新するので、計算量は N と M の積に比例して増える。元のサンプリング密度にかかわらず、結果は形状全体を均等に覆う。同じ貪欲な規則は、Gonzalez が 1985 年に示した、k センタークラスタリング問題に対する古典的な 2 近似でもある。

点群の深層学習では、FPS は PointNet++ によって広く知られるようになった。PointNet++ は各層で局所近傍の中心を選ぶのに FPS を使い、その後の多くのネットワークも推論の前に入力点群を固定サイズにダウンサンプリングするのに FPS を使っている。入力の密度に従うため薄い部分やまばらにしか観測されていない部分を取りこぼしうるランダムサンプリングと比べ、FPS は物体全体のカバレッジを保つ。ボクセルグリッドによるダウンサンプリングと比べると、正確な点数を返すので、入力サイズが固定のネットワークにはこれが必要になる。

FPS にはトレードオフがある。外れ値を意図的に優先してしまう。孤立したノイズ点は他のすべての点から遠いので早い段階で選ばれるため、通常は先に点群をフィルタリングする。手順は逐次的なので、非常に大きな点群では遅い。GPU 実装は各ステップ内の距離更新を並列化し、近似的な変種は空間分割の上で動作する。出力は開始点に依存し、メッシュ上では、測地線を使う変種が直線ではなく表面に沿って距離を測る。

重要な理由

点群ネットワークは固定サイズの入力を必要とするが、深度センサはネットワークが処理できるよりはるかに多くの点を生み出す。均等なカバレッジにより、取っ手、縁、注ぎ口のように小さいが重要な部分がダウンサンプリング後も残る。これは把持やアフォーダンスの予測にとって重要である。

主な用途

• ニューラルネットワーク向けの点群の固定サイズへの前処理
• 階層型の点群ネットワークにおける近傍中心の選択
• Chamfer 距離や Earth mover's distance を計算する前の点群のダウンサンプリング
• 分散した把持候補点や接触点の選択
• カバレッジのための多様なキーポイントやサンプルの選択

実際の使われ方

作業台の上の深度カメラは、1 フレームあたり数十万点を生成する。パイプラインは作業空間を切り出し、統計的な外れ値を除去し、計算量を減らすためにボクセルダウンサンプリングを行い、そのうえで FPS を実行して、ネットワークの学習時と同じ点数、たとえば 2048 点をちょうど得る。FPS でサンプリングした点群で学習したネットワークは、ランダムサンプルで学習したネットワークとは異なる点の分布を見ることになるため、チームは学習時とロボット上で同じサンプリング手順を使う。

よくある誤解

• FPS は一様なランダムサンプルを与える — 開始点を固定すれば決定的であり、ランダムにサンプリングするのではなく空間内に点を均等に広げる
• FPS はノイズに強い — 外れ値は他のすべての点から遠いため早い段階で選ばれてしまうので、通常は先に点群をフィルタリングする
• FPS はスキャンの密度情報を保つ — 意図的に密度をならすので、カバレッジには役立つが、センサがどこで多くの点を見たかという手がかりは失われる

知っておくべき人

• 3D 知覚のエンジニア
• 点群ネットワークに取り組む機械学習の研究者
• 点群ポリシーを使うマニピュレーションのエンジニア

関連技術

• PointNet++
• ボクセルグリッドダウンサンプリング（Voxel Grid Downsampling）
• ランダムサンプリング（Random Sampling）
• k センタークラスタリング（k-Center Clustering）
• ポアソンディスクサンプリング（Poisson Disk Sampling）
• Open3D

関連用語

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

関連プロジェクト

• 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