Color quantization
Tags: computerscience, algorithms, architecture, performance
Published: 2022-11-24 15:07:59

Let's discuss about algorithms to reduce the number of colors belonging to an image, this is not an easy task, but it might well helps PNG file losing weight since when they are below 256 colors, they can become indexed color PNG type which instead of storing chunks of colors following each other of 32 bits they only store the index of the color making it weight 8 bits per pixel which reduce the size of approximately 75%!

Ok, let's begin, imagine you import a poor JPEG file with some 20K colors for a size of 200x400... Those are real-life numbers, you'll get approximately as much colors as twenty thousands for a thumbnail, JPEG encoding is quite smart but well, what does interest us is to not have artifact (pixel glitching around complex textures) and a correctly low-sized PNG file...

Well, we might take smooth images, like cars, portrait and other stuff which could make it be a beautiful drawing in real-life to demonstrate all the power belonging into it.

---

How to get that done? https://en.wikipedia.org/wiki/Color_quantization

---

Okay I still need to improve my skills into coding such solutions but let's maybe for this first part take a tour into what I've used (as of, Technics that works, to do my quantization algorithm.).

What is a pixel?

Often you'll have Red, Green, Blue, Alpha intensities between 0-255 making up a whole Usigned Integer or float onto 32 bits, a byte per component as these are four of them!

---

1) My first trick was to round them to their 1/8, 1/4, or even 1/2 depending the number of color, as we have color nearly impossible to blend together as they are so close, better rig them into lower scheme to filter a great part of them at glance! 

2) The second trick was to create clusters, two possibilities: either sum-up the whole 32 bits cutting through each component by some division to sum-up colors into groups of 12bits possibilities (4096 clusters) or 8bits possibilities (256 clusters), this work well as I decided the third part which is expensive when there is many colors against many colors to process it's distance and blending with blending intensity following the frequencies of the colors (the more the color to blend is frequent the more weighted it is against the closest color that match a certain threshold).

3) Blend them all! We sum up comparing colors within those 256 or 4096 clusters and compare all of them to all of them, which is ~10x less CPU consuming when we end up skipping the colors that won't match in anyway as they are in one too far color dimension, for example, 10 groups of 100 colors makes 10000 operations ten time, instead 1000 colors multiplied by 1000 colors make it one million operation! How yeah baby let me put them into cluster (I call my clusters some kind of eggs) then we fries the colors together and we sum up having nice brand new colors in a small palette as we carefully blend them based on their weight!

---

Okay, this was a short post, what do you think of theses concepts? At first it took minutes without enough computer knowledge, now it takes milliseconds! Test it out, https://pixa.pics/ (Images into pixelarts and NFTs...)