Top 3 color quantization algorithms
I have been writing on the desktop image processing application. At the version 1.0, I use the octree color quantization algorithm to reduce image to 256 colors, which is highly memory efficient with each pixel assigned the color at the center of the octree bin in which it falls. On the other hand, generates the palette using the distribution of colors in the image, but it does not consider the frequency of color. This means that if an image is composed of similar colors overall but has many different low-frequency colors or noise, octree’s results can be very poor.
Then I find an article called "Convert 32 bit PNGs to high quality 8 bit PNGs with C#" after googling. It adapted an algorithm developed by Xiaolin Wu. Xialoin Wu's fast optimal color quantizer, which is one of the most effective color quantization methods, provides excellent results. However, low frequency colors in the original image tend to be excluded during the histogram counting process. On top of that, the quantized image in areas of smooth color gradients, in the form of false edges, are clearly visible. Reduced 256 colors by Xiaolin Wu. Xialoin Wu's fast optimal color quantizer without dithering:
Next I tried the NeuQuant Neural-Net Quantization Algorithm from pngnq which shows excellent results with most images. The results are very natural and have a low MAE and MSE because it spontaneously considers the distribution of colors. However, the speed is quite slow to achieve the best quality. More importantly, high frequency colors are learned many times, so they update the weights many times. This means that high frequency colors influence neighbor nodes much more. In particular, the loss of original color increases when it uses a small number of boxes to quantize the image with a small number of colors.
Reduced to 256 colors by NeuQuant Neural-Net Quantization Algorithm:
To reduce such artifacts, a subsequent dithering step is typically employed after quantization as learnt from Dennis lee v3 color quantization. Dithering distributes quantization errors into neighboring pixels, helping to hide the false edges. Thus, to complement these disadvantages, a better color quantization algorithm that is effective even when it uses only a small number of colors by using the Fast pairwise nearest neighbor based algorithm. This algorithm was only supporting RGB only. I enhanced it to fully support the alpha layer by image transparency detection. It was using RGB555 to filter original colors into 16 bit high color. I change it to use RGB565 for image without transparency, ARGB1555 for image without semi transparency, ARGB4444 for image with semi transparency to digest original colors for the quantization process.
Reduced to 256 colors by Pairwise Nearest Neighbor Quantization Algorithm:
To reduce the effect of the color shifted, the fast pairwise nearest neighbor based algorithm with CIELAB color space is established. The CIELAB color space is one of the approximately uniform color spaces recommended for device-independent color representation in electronic color image systems. If colors are represented by the CIELAB space, the axes of lightness L* and chromaticities a* and b* have to be suitably quantized. The largest color quantization steps are always found at the border of the color spaces. Much smaller variations appear if the new color difference formula CIE 2000, DE* 00 is used. In this formula, quantization steps of chroma are valued much less if chroma values are high.
To quantize the image to 32 colors or less, the following quantization algorithms produces better result.
Fast pairwise nearest neighbor based algorithm with CIELAB color space with 16 colors High quality and fast
Efficient, Edge-Aware, Combined Color Quantization and Dithering with 16 colors High quality for 32 or less colors but slower
Spatial color quantization with 16 colors High quality for 32 or less colors but the slowest
All in all, the top 3 color quantization algorithms for 256 colors are:
- Fast pairwise nearest neighbor based algorithm
- Xialoin Wu's fast optimal color quantizer
- NeuQuant Neural-Net Quantization Algorithm
The top 3 color quantization algorithms for 32 colors or less are:
- Fast pairwise nearest neighbor based algorithm with CIELAB color space
- Efficient, Edge-Aware, Combined Color Quantization and Dithering algorithm
- Spatial color quantization algorithm
The above sample images are referenced from
The source code is ready for the following github projects:
Visual C++ https://github.com/mcychan/nQuantCpp/