Octree

別名: sparse voxel octree
カテゴリ: Sensing › 3D maps & reconstruction
タグ: mapping, data-structures, 3d-perception, occupancy-mapping, point-clouds

3D 空間を再帰的に 8 つの立方体に分割し、データがある場所にだけ細かいセルを割り当てることで、コンパクトな地図と高速な空間検索を実現する木構造のデータ構造。

定義

八分木（Octree）は、各ノードが空間の立方体を表し、その立方体を 3 つの軸すべてに沿って半分に分けて得られる 8 つの八分空間それぞれに 1 つずつ、最大 8 個の子をもてる木である。ルートは体積全体を覆い、1 レベル下がるごとにセルの大きさは半分になる。計測された表面点のように関心のあるものが存在する場所だけで枝が細分されるので、空の領域や観測されていない広い領域は粗い単一のノードのまま残る。八分木は 1980 年代初めに Donald Meagher がソリッドモデリングのために記述したもので、現在ではグラフィックス、点群処理、ロボットのマッピングで標準的に使われている。

主な魅力はメモリである。大きな建物全体を細かい解像度で覆う密なボクセルグリッドはすべてのセルに記憶領域を必要とするが、八分木の記憶容量はおおよそ観測された表面積に比例して増える。また、多重解像度でのアクセスも可能で、プランナーは粗いセルを問い合わせて素早く確認し、必要に応じて下って細部を得られる。Hornung らによる広く使われているライブラリ OctoMap では、各葉が対数オッズ（log-odds）形式の確率的な占有値をもち、距離計測から更新されるので、地図は占有、空き、未知の空間を区別できる。同じ状態の子はメモリ節約のために親へと刈り込まれる。

八分木は、このコンパクトさと引き換えに速度を多少犠牲にしている。葉にたどり着くには木を下っていく必要があり、平らな配列をインデックスで参照するより遅い。ボクセルハッシングや VDB 構造などの代替手段は、作業内容によってはより高速なアクセスを提供する。八分木は点群上の最近傍探索や衝突判定の高速化にも使われ、最近のニューラルマッピングシステムでは、学習した特徴を保存する疎なボクセルを整理し、新しい深度フレームが届くたびに少しずつ成長していく。

重要な理由

ロボットには、メモリを使い果たすことなく、広い範囲を実用的な解像度で覆う 3D 地図が必要である。八分木はそれを実用的なものにし、マニピュレーションや空中ナビゲーションで使われる一般的な占有マッピングや衝突判定のツールの基礎となっている。

主な用途

OctoMap による確率的な 3D 占有マッピング
ロボットアームとドローンの衝突判定
点群上の最近傍探索と半径探索
ニューラル暗黙的マッピングや密なマッピングのための疎なボクセル構造
点群の圧縮と詳細度に応じたレンダリング

実際の使われ方

倉庫内を飛ぶドローンのために 3D 地図を作るチームは、深度カメラや LiDAR の点群を、オドメトリから得た姿勢とともに、数センチの解像度で OctoMap に入力する。各レイは、通過したセルを空きの可能性が高いものとして、終端のセルを占有の可能性が高いものとして記録する。プランナーは候補経路に沿って八分木の占有を問い合わせ、未知の空間は障害物として扱う。ロボットアームでは、MoveIt が深度センサから同じ種類の八分木を受け取り、アームの計画シーンを最新に保つことができる。エンジニアは、解像度、センサの測定範囲、ヒットとミスの確率を調整し、細かさ、メモリ、動く物体がどれだけ早く消去されるかのバランスをとる。

よくある誤解

八分木はボクセルグリッドと同じものである — ボクセルグリッドはすべてのセルを保存するが、八分木は必要な場所だけを細分し、一様な領域はまとめる
八分木は平らなグリッドより常に速い — メモリは節約できるが、検索のたびに木をたどるので、問い合わせによっては密なグリッドやハッシュ化したグリッドのほうが速いことがある
八分木の何もない空間は空き空間を意味する — 占有八分木では観測されていない空間は未知であり、プランナーは通常それを空き空間とは区別して扱うべきである

知っておくべき人

マッピングと SLAM のエンジニア
動作計画と衝突判定の開発者
3D 環境で作業するドローン自律化のエンジニア
ニューラルマッピングや密なマッピングのシステムの開発者

動画

Using Octrees and A* for Efficient Pathfinding: git-amend

ウィキペディア

八分木

Open Source Robotics