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

Facebookシェア Twitterツイート LINEで送る Googleシェア このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
Up
0
Down

要約

概要

ある点や点群に含まれる点と最も近い最近傍点を検出する方法について幾らか紹介します。検出する方法の違いには速度があります。
ー 条件 ー
  • 入力は点の座標と最近傍を含む点群
ー 効果 ー
  • ある点から最も近い点を検出する
ーポイントー
  • 速度の違いにより選択する方法が異なる

解  説

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

1.単純な方法による検出

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

2.KDTreeによる検出

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

3.Octreeによる検出

kdtreeでは二分割することによって分割していましたが、Octreeでは空間を8分割することによって点群の位置情報を管理します。 Octreeは更新、削除がkdtreeよりも高速なので大方の場合こちらが好んで使用されます。
octreeについて
通常の近傍探索を行う場合は、Octreeを使用して実行することが多い。Octreeを使った場合は、Kdtreeより高速にデータの整理を行うことができます。 最もシンプルな全ペアの総当り探索は、3次元点群のように多くのデータ点がある場合、通常は遅くて使用するのが厳しいです。
検出に関して結論
この章を学んで新たに学べる
Comments

Reasons
>>隠す