For purposes of color allocation, an image is a set of n pixels, where each pixel is a point in RGB space. The algorithm maps this domain onto a tree in which each node represents a cube within that domain. The vertex nearest the origin in RGB space and the vertex farthest from the origin. Each lower level in the tree is generated by subdividing one node's cube into eight smaller cubes of equal size. This corresponds to bisecting the parent cube with planes passing through the midpoints of each edge.
Classification builds a color description tree for the image.
Reduction collapses the tree until the number it represents, at most, is the number of colors desired in the output image. Assignment defines the output image's color map and sets each pixel's color by reclassification in the reduced tree. Our goal is to minimize the numerical discrepancies between the original colors and quantized colors. Classification begins by initializing a color description tree of sufficient depth to represent each possible input color in a leaf. However, it is impractical to generate a fully-formed color description tree in the classification phase for realistic values of cd max u .