八分木
(8分木 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/18 16:07 UTC 版)
ナビゲーションに移動 検索に移動
八分木（英: Octree）とは、木構造の一種で、各ノードに最大8個の子ノードがある。3次元空間を8つのオクタント（八分空間）に再帰的に分割する場合によく使われる。四分木を3次元に拡張したものと見ることができる。英語の名称は oct + tree に由来するが "octtree" とは書かず "octree" と書く。
空間表現としての八分木
八分木の各ノードは空間を8つのオクタントに分割する。PR (point region) 八分木の場合、各ノードは明確に1つの3次元の点を格納していて、それがそのノードに対応する空間領域の中心点となる。また、その点は子ノードそれぞれに対応する空間領域の頂点（隅）になり、逆に言えば、その点を中心としてオクタントに分ける。MX八分木では、対応する空間領域の幾何学的中心点を暗黙のうちに分割の中心とする。PR八分木の根ノードは無限の空間を表せるが、MX八分木の根ノードは有限の空間しか表せない（そうでないと幾何学的中心が求められない）。このように空間分割表現として八分木を使う場合、それはkd木の3次元の場合の特殊ケースとなる。
主な用途
色量子化への応用
八分木による色量子化アルゴリズムは、1988年、Gervautz と Purgathofer が考案した。これは、画像の色データを最大9レベルの深さの八分木で符号化するものである。八分木がこの用途に使われるのは、
カテゴリ
- 8分木のページへのリンク
