From Glassner (1990) :
The principle of the octree quantisation method is as follows. The image is read in sequentially. The first K different colours are used as initial entries to the colour table. If another colour is added, which means that the already processed part of the image has K + 1 different colours, some very near neighbours are merged into one and substituted by their mean. This step is repeated for every additional colour, so that at any moment no more than K representatives are left. This property, of course, remains true after the image is completely processed.
The algorithm is done in three phases:
These will now be looked at in greater detail.
The octree is constructed only in those parts that are necessary for the image we want. At the beginning, the octree is empty. Every colour that occurs in the image is now inserted by generating a leaf in depth eight; thereby, the colour is represented exactly.
inserts the colour RGB into the subtree Tree
if Tree = nil then
NewAndInit (Tree); produces and inits a new octree node.
if Leaf then we have reached the eighth level.
inc(Tree^.ColourCount); update the number of represented pixels
AddColours(Tree^.RGB,RGB);sum up the colour values
else InsertTree (Next[Branch(RGB)],RGB);
ReduceTree combines the successors of an intermediate node to
one leaf node
GetReducible(Tree); finds a reducible node
Sum <- (0,0,0);
Children <- 0;
for i:integer <- 0, 7 do
if Next[i] <> nil then there is an ith successor
Children <- Children + 1;
Tree^.Leaf <- true; cut the tree at this level
Tree^.RGB <- Sum; the node represents the sum of all colour values
Size <- Size - Children + 1; of children
Reducing the octree, the following criteria are relevant:
To construct the octree, the whole image has to be read once and all colours of the image have to be inserted into the octree.
At the end, the K leaves of the octree contain the colours for the colour table (the mean value of all represented colours = RGB/ColourCount). They can be written into the colour table by recursively examining the octree. During this recursive tree traversal in every leaf node of the octree also its own colour index is stored.
The mapping of the original colours onto their representatives can now be managed easily with the octree, too. Trying to find any original colour in the reduced octree will end at a leaf in some depth. This node contains a colour very similar to the one in search, and is therefore its representative. Since the index of the colour table is stored there too, no further search has to be carried out.
If the original image used less than K colours, no reduction will have taken place, and the found colour table entry will contain exactly the correct colour. Otherwise, only the path to the leaf in depth eight was shortened by the reduction, so that the colour will be displayed less exactly by the means of all the colours that had their paths over this node. Since the octree contains only K leaves, all original colours are mapped onto valid colour table entries. For this, the image has to be read a second time.
The visual result using this octree quantisation is of similar quality as the result using the median cut method.
for the original colour its representative
is searched for in the octree, and the index of its
colour table entry is returned
if Leaf then
return Tree^.ColourIndex stored colour index in the tree
A significant portion of the time is spent with the search for an optimal reducible node every time a reduction of the octree has to take place. These nodes can be collected easily in an appropriate structure during the construction of the tree. They have to be sorted by depth to ensure quick access. An appropriate structure for this purpose has proved to be eight linear lists (one for every depth level) containing all reducible nodes. All nodes of one depth level are elements of the same list. The node with the largest depth can then be found quickly for reduction.
An intermediate node is inserted into its list of reducible nodes after its creation during NewAndInit.
At any given moment one level of the octree will be the depth in which the reductions take place. This depth is the level of the deepest intermediate nodes. At the beginning, this is level seven, and it moves toward the root during octree construction. This "reduction" level states what the minimal distance between two representatives will already have to be. This minimal distance can never again decrease even by adding more colours to the octree. Therefore, nothing beneath this reduction level + 1 will ever again be relevant so that the insertion of colours can also stop at that depth. The depth of the octree is not constant, but decreases with lifetime.
Let N be the number of pixels of the original image. If the image is run-length encoded, N can also be the number of runs of the image. The algorithm has to be modified slightly by using runs instead of pixels in the octree.
Let K be the number of representatives, that is, the size
of the colour table. Let D be the number of different colours in
the original image. In general the following equations hold:
N > D > K and N >> K.
Upper bounds for the number of steps for the insertions,
for the generation of the colour table and for the quantisation
Colour table generation:2.K.