点群から最近傍点を検出したい

ある点や点群に含まれる点から最も近い点を点群から検出する方法についてまとめています。技術的には最近傍探索などがキーワードになると思います。３次元の点同士の近傍探索の他にももっと高次元になった場合などが研究されている分野です。

最も簡単に近傍点を検出する方法として、誰もが思いつくものとして全てのペアで距離を計算する方法があります。総当りによる検出です。しかし、点群は優に10000点を越えることがあるため、総当りを毎回計算してはとても使い物にならない速度になります。 上記の問題を解決すべく 空間を分割して整理することで高速化する方法などがよくとられます。 ここではPCLでも使用されるkdtreeとoctreeについて紹介します。

KDTreeを用いることで最近傍点の検出を高速化することができます。kdtreeは空間分割をするにあたってデータ構造の作成や変更をするのに若干時間がかかります。なので頻繁に構造が変わる場合には不向きです。kdtreeは高次元になったときには遅くなりますが、3次元では十分かと思います。 c++の実装をするにあたっては、FLANNなどのライブラリを用いて行われることが多いです。

kdtreeでは二分割することによって分割していましたが、Octreeでは空間を8分割することによって点群の位置情報を管理します。 Octreeは更新、削除がkdtreeよりも高速なので大方の場合こちらが好んで使用されます。

通常の近傍探索を行う場合は、Octreeを使用して実行することが多い。Octreeを使った場合は、Kdtreeより高速にデータの整理を行うことができます。 最もシンプルな全ペアの総当り探索は、３次元点群のように多くのデータ点がある場合、通常は遅くて使用するのが厳しいです。