Suggestion: Add kmeans, binarysplit and Wu algorithms to Quantize

[Lepuff]

I think Quantize can use some better algorithms to use. These three algorithms I can vouch for provide better results than Octree, particularly when aiming for lower color images (8-64 colors). Also some can support more than 256 colors. Sometimes you want to reduce to 512 or 2048 with one algorithm (i.e binary split) before proceeding further with another algorithm (i.e. kmeans). Results may improve depending on the order of the algorithms used, one may be better to initially use first, then a second pass using a different algorithm, as opposed to going down to 64 colors in just one pass.

 

K-means (Llyod's algorithm)

Article on iterative k-means for reducing colors: https://muthu.co/reduce-the-number-of-colors-of-an-image-using-k-means-clustering/

ckmeans (cartesian k-means) possibly gives better results: https://cran.r-project.org/web/packages/Ckmeans.1d.dp/Ckmeans.1d.dp.pdf

Reference C++ code for ckmeans: https://github.com/cran/Ckmeans.1d.dp/blob/master/src/Ckmeans.1d.dp.cpp

kmeans color quantizer C++ code: https://gist.github.com/Erkaman/80a2407ca70c50958dc983bbaad40c64

 

Binary Split

Color quantization of images (Original paper): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.154.6757&rep=rep1&type=pdf

Charles A. Bouman's reference implementation of Binary Split: https://engineering.purdue.edu/~bouman/software/color_quantization/

 

Wu

Reference C code: https://www.ece.mcmaster.ca/~xwu/cq.c

A decent third option, very good performance and decent results (binary split is better, but Wu is better than octree and NeuQuant)

 

 

It also could be super useful to show an SSIM value (https://en.wikipedia.org/wiki/Structural_similarity), telling the user how much the result has changed from the original, to better evaluate each algorithm.

 

 

 

 

Edited April 19, 2022 by Lepuff

[BoltBait]

This seems like something that could be handled by writing a plugin.

 

Why not give that a try?