How to use a KdTree to search

探索におけるKdTreeの使い方

出典:http://pointclouds.org/documentation/tutorials/kdtree_search.php#kdtree-search

このチュートリアルでは、KdTreeを使用して特定のポイントまたは場所のK最近傍点を見つける方法を説明する。次に、ユーザーが指定した半径以内のすべての近隣点を見つける方法(この場合はランダム)を紹介する 。

基礎理論

$k-d$ツリー、すなわち$k$次元木とは、$k$次元の空間内のいくつかの点の組織化のため計算機科学で使用されるデータ構造である。なんらかの制約が課された二分探索木といえる。 K-d木は、領域内探索や最近傍探索に非常に有用である。我々の目的では一般に3次元の点群を取り扱うだけなので、我々が扱うk-d木はみな3次元とみなせる。 k-d木の各レベルは、対応する軸に垂直な超平面を使用して、特定の次元に沿ってすべての子ノードを分割する。木の根ノードでは、すべての子ノードが第1次元に基づいて分割される(つまり、第1次元の座標が根ノードよりも小さい場合は左の部分木にあり、根ノードより大きい場合は右の部分木にある)。木の下の階層のレベルはそれぞれその次の次元に基づいて分割され、すべて次元が使い尽くされると、第1次元に戻る。 k-d木を構築する最も効率的な方法は、クイックソートがやるように、根ノードに中央値点を配置することである。分割する最後の部分木が1つの要素だけで構成されるまで、この手順を左右の部分木で再帰的に繰り返す。

WikiPediaからの図: http://pointclouds.org/documentation/tutorials/_images/2d_kdtree.png

2次元のk-d木の例

http://pointclouds.org/documentation/tutorials/_images/nn_kdtree.gif

これは最近傍短絡のデモ

(PCLのC++コードは省略) (以下省略)

Open3DのKDTreeのコードの例。FLANNを用いて最近傍のノードを探索する:(クエリー点は赤、k(下のコードでは200)個の最近傍点は青、指定された半径(下のコードでは0.2)内の点を緑で表示)

In [1]:
# src/Python/Tutorial/Basic/kdtree.py

import numpy as np
from py3d import *

if __name__ == "__main__":

    print("Testing kdtree in py3d ...")
    print("Load a point cloud and paint it gray.")
    pcd = read_point_cloud("./TestData/Feature/cloud_bin_0.pcd")
    pcd.paint_uniform_color([0.5, 0.5, 0.5])
    pcd_tree = KDTreeFlann(pcd)

    print("Paint the 1500th point red.")
    pcd.colors[1500] = [1, 0, 0]

    print("Find its 200 nearest neighbors, paint blue.")
    [k, idx, _] = pcd_tree.search_knn_vector_3d(pcd.points[1500], 200)
    np.asarray(pcd.colors)[idx[1:], :] = [0, 0, 1]

    print("Find its neighbors with distance less than 0.2, paint green.")
    [k, idx, _] = pcd_tree.search_radius_vector_3d(pcd.points[1500], 0.2)
    np.asarray(pcd.colors)[idx[1:], :] = [0, 1, 0]

    print("Visualize the point cloud.")
    draw_geometries([pcd])
    print("")
Testing kdtree in py3d ...
Load a point cloud and paint it gray.
Paint the 1500th point red.
Find its 200 nearest neighbors, paint blue.
Find its neighbors with distance less than 0.2, paint green.
Visualize the point cloud.