【Python】Open3DでKDTreeを実装して近傍点探索
KDTreeの概要
KDTree (K-dimensional tree)は、3D 空間内の点の集合を効率的に検索するためのデータ構造です。
KDTreeは、点集合を二分探索木によって管理することで、指定された点に最も近い点を効率的に求めることができます。各ノードは、空間を2つに分割する直線を定義し、この直線によって空間を左右に分割します。
3D モデリング、ゲーム開発、コンピュータグラフィックスなどのアプリケーションに利用されます。
アルゴリズム
KDtree (K-dimensional tree) は、次元空間上の点を効率的に管理するためのアルゴリズムの一つです。このアルゴリズムは、多点探索タスクや近傍点探索タスクなどで広く利用されています。
このアルゴリズムは、データポイントを k 次元空間内に分類することで、検索操作を高速化するというアイデアをもとにしています。k 次元空間内には、最初に規則的なグリッドを構築し、それに基づいてデータポイントをグループ分けします。
このグリッドは、再帰的に分割されていき、最終的には各グリッドに対して 1 つのデータポイントしか含まれないようになります。
流れとしては以下の通りです。
１．K-D Tree の根ノードを作成します。このノードには、全ての点を含む最大の空間領域を表すようにします。
２．根ノードを中心とする空間を、点の中央値を基準として 2 つに分割します。これらの分割領域は、左側と右側の2つの子ノードとして表されます。
３．分割された子ノードに対して同様の操作を繰り返します。繰り返しが終了するタイミングは、各ノードに含まれる点が十分少ない場合、または分割ができない場合になります。
４．各ノードには、そのノードが表す空間に属する点のリストを格納します。
KDtree のアルゴリズムは、多数のデータポイントを管理する必要がある場合に特に有用です。3D点群データの検索や、多数の計算機ビジョンタスクに利用されています。
Pythonコード
Open3Dを用いてKDtreeを実装します。全体のコードは以下の通りです。
# KDTreeの構築
print("Testing kdtree in Open3D...")
print("Load a point cloud and paint it gray.")
pcd = o3d.io.read_point_cloud("../../test_data/Feature/cloud_bin_0.pcd")
pcd.paint_uniform_color([0.5, 0.5, 0.5])
pcd_tree = o3d.geometry.KDTreeFlann(pcd)
# 1500点目を注目点とする
print("Paint the 1500th point red.")
pcd.colors[1500] = [1, 0, 0]
# KDTreeによる最近傍点計算
print("Find its 200 nearest neighbors, and paint them 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, and paint them 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.")
o3d.visualization.draw_geometries([pcd],
zoom=0.5599,
front=[-0.4958, 0.8229, 0.2773],
lookat=[2.1126, 1.0163, -1.8543],
up=[0.1007, -0.2626, 0.9596])実行結果です。青色の200点がKDtreeによる近傍点の計算結果、緑色が注目点から半径(0.2m)以内の点になります。
