OCTREE

4/7/2004

An Octree is a data structure with eight subnodes per node. Relative to binary trees, Octrees offer faster searching and insertion offset by slow deletion and moving of nodes. Octrees are effective storage structures for three dimensional data since the eight subnodes can be matched to the eight possible combinations of three binary bits of data. Octrees are often used to create color palette information for digital images.

Because colors are typically represented as three colors (for example Red, Green Blue), the 3 dimensionality of octrees is well matched to the needs of handling color images. The usual approach is to create an 8x8x8 (24 bit) octree; count the cells of each color; then collapse the tree to the "most important" 256 colors. The 256 colors then become the palette used for the image. Octrees are a computationally efficient tool for producing an individualized 256 color palette for an image.

Widely used image formats including BMP and GIF offer Octree generated palleting as an alternative to Windows halftone for 8 bit color data. The advantage of Octree in this context is not so much the beauty of the Octree structure per se, as the fact that Windows halftone is a fixed palette of 256 colors. Octree on the other hand is a palette of 256 colors selected to match the needs of the image. Octree often produces subjectively superior color images.

http://cubic.org/docs/octree.htm