Farthest Point Sampling

はじめに

 今回は点群処理の前処理としてしばしば使われるFarthest Point Sampling(FPS)を紹介する。本手法は密な点群が手元にあるとき、あらかじめ決めた点(3次元座標)の数に「良い具合に」間引くものである。

アルゴリズム

 
 アルゴリズムは以下の通りである。

  1. 最初に、与えられた点群から適当に1点を選びこれをAとする(図1)。
  2. 次にAから最も離れた点を見つけこれをBとする(図2)。
  3. 残りの点とA,Bとの距離を計算し、より短い方の距離を記録する。図3では、Aに近い点を緑で、Bに近い点を赤で塗分けた。
  4. これらの距離の中で最も長い距離を持つ点をCとする(図4)。図4の場合は、最も長い距離は緑点に属している。
  5. 選択した点が所定の数になるまで繰り返す。


とても単純な処理であるが、空間的な位置関係を見ながら間引くので、乱数で点を選ぶ場合より「良い塩梅」の結果を得ることができる。

実行結果

 上のアルゴリズムをC++で実装した。ソースはここにある。以下の結果は、113662個の点群(図5の青点)から1000個の点群(図6の黒点)に間引いた結果である。比較のため乱数で1000個の点を選んだ結果も示す(図7の黒点)。図6と7の点のサイズは見やすさのため大きくしてある。

本手法(図6)の方が空間的に一様に点を選択できていることが分かる。

コード

 以下はFPSを実行する関数である。cloudは入力点群を格納した配列、kは選択したい点の数である。このコードの肝はmin_distancesである。この配列の中に各点と選択点との最短距離が記録される(29行目)。そして、その中から最大の距離を持つ点が選ばれる(20行目)。

まとめ

 今回は、点群の前処理として使われるFPSを紹介した。FPSは点の数をあらかじめ決めた数になるように間引く処理である。点群処理においても最近では深層学習が使われることが多い。深層学習では、入力データ(画像やベクトル)は固定サイズであることがほとんどであるからFPSが使われる機会は多い。

Kumada Seiya

Kumada Seiya

仕事であろうとなかろうと勉強し続ける、その結果”中身”を知ったエンジニアになれる

最近の記事

  • 関連記事
  • おすすめ記事
  • 特集記事

アーカイブ

カテゴリー

PAGE TOP