Some time ago I found interesting octree color quantization algorithm, previously often used in computer graphics (when devices can display only a limited number of colors), and nowadays mainly used in gif images.
I've implemented one of the most used algorithm of octree color quantization in Python. Here is a repository on github: https://github.com/delimitry/octree_color_quantizer
Result image (colors reduced to 8 bit):
Result image palette:
Algorithm:
Octree is a tree where each node has up to 8 children. Leaf node has no active children.
Each leaf node have a number of pixels with this color (pixel_count) and color value.
1) Addition of a new color to the octree.
Start at the level 0.
For example a pixel RGB color is (90, 13, 157). In binary it is (01011010, 01110001, 10011101).
The next level node index is calculated the following way:
Write in binary R, G and B bits, starting from MSB, for current level. So the index will be from 000 to 111 (binary), i.e. from 0 to 7 (decimal).
If the maximum depth of tree is less than 8, only first bits of color will matter.
Here is the image with first steps of addition the color:
If we have a tree with maximum depth of 8, eventually we will have the next indices:
The full tree with depth 8 after add the color (90, 113, 157):
If the next pixel color is again (90, 113, 157), the leaf node color R, G, B values will be increased by new color R, G, B values as well as the value of pixels with this color. And the color will be (180, 226, 314) and pixel_count will be 2:
2) Reduction
To make image color palette with for example 256 colors maximum, from palette with far more colors the tree leaves must be reduced.
The reduction of nodes:
As we have a sum of R, G and B values and the number of pixels with this color, we can add all leaves pixels count and color channels to parent node and make it a leaf node (we could not even remove it, because get leaves method will not go deeper if current node is leaf).
Reduction continues while leaves count it more than needed maximum colors (in our case 256).
The main disadvantage of this approach is that up to 8 leaves can be reduced from node and the palette could have only 248 colors (in worst case) instead of expected 256 colors.
I've implemented one of the most used algorithm of octree color quantization in Python. Here is a repository on github: https://github.com/delimitry/octree_color_quantizer
Original image (24 bit):
Result image (colors reduced to 8 bit):
Result image palette:
Octree is a tree where each node has up to 8 children. Leaf node has no active children.
Each leaf node have a number of pixels with this color (pixel_count) and color value.
1) Addition of a new color to the octree.
Start at the level 0.
For example a pixel RGB color is (90, 13, 157). In binary it is (01011010, 01110001, 10011101).
The next level node index is calculated the following way:
Write in binary R, G and B bits, starting from MSB, for current level. So the index will be from 000 to 111 (binary), i.e. from 0 to 7 (decimal).
If the maximum depth of tree is less than 8, only first bits of color will matter.
Here is the image with first steps of addition the color:
To make image color palette with for example 256 colors maximum, from palette with far more colors the tree leaves must be reduced.
The reduction of nodes:
As we have a sum of R, G and B values and the number of pixels with this color, we can add all leaves pixels count and color channels to parent node and make it a leaf node (we could not even remove it, because get leaves method will not go deeper if current node is leaf).
Reduction continues while leaves count it more than needed maximum colors (in our case 256).
The main disadvantage of this approach is that up to 8 leaves can be reduced from node and the palette could have only 248 colors (in worst case) instead of expected 256 colors.
As soon as we've got count of leaves less or equal needed maximum colors we can build a palette.
3) Palette building
Palette is filled with average colors, from each leaf. As each leaf has the number of pixels with color and color's sum of R, G and B values, average color could be received by dividing color channels by the number of pixels: palette_color = (color.R / pixel_count, color.G/ pixel_count, color.B / pixel_count).
