Jump to content

Suggestion: Add kmeans, binarysplit and Wu algorithms to Quantize

Recommended Posts

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=

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



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 by Lepuff
  • Upvote 1
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Create New...