# Improving color quantization heuristics

DevFeed: [Improving color quantization heuristics](<https://devfeed.tech/articles/improving-color-quantization-heuristics-26113.md>)

Original publisher: [Read original article](<http://blog.pkh.me/p/39-improving-color-quantization-heuristics.html>)

Published: 2022-12-31T12:00:43Z

Content type: article

Language: en

Sources: [The Last Static Blog RSS](<https://devfeed.tech/sources/the-last-static-blog-rss.md>)

Topics: [quantization](<https://devfeed.tech/topics/quantization.md>), [color](<https://devfeed.tech/topics/color.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [FFmpeg (Fast Forward Moving Picture Experts Group)](<https://devfeed.tech/topics/ffmpeg.md>), [Compression](<https://devfeed.tech/topics/compression.md>), [image animation](<https://devfeed.tech/topics/image-animation.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [article](<https://devfeed.tech/tags/article.md>), [blog](<https://devfeed.tech/tags/blog.md>), [color](<https://devfeed.tech/tags/color.md>), [compression](<https://devfeed.tech/tags/compression.md>), [ffmpeg](<https://devfeed.tech/tags/ffmpeg.md>), [gif](<https://devfeed.tech/tags/gif.md>), [math](<https://devfeed.tech/tags/math.md>), [prog](<https://devfeed.tech/tags/prog.md>), [quantization](<https://devfeed.tech/tags/quantization.md>)

## AI overview

The article examines improvements to color quantization heuristics, including evaluating color distances in a perceptually uniform color space such as OkLab instead of using Euclidean distance between RGB values. It explains palette quantization as reducing an image's colors to a smaller representative subset, with applications including compression, limited-palette codecs such as GIF, and artistic effects.

## Source excerpt

In 2015, I wrote an article about how the palette color quantization was improved in FFmpeg in order to make nice animated GIF files. For some reason, to this day this is one of my most popular article. As time passed, my experience with colors grew and I ended up being quite ashamed and frustrated with the state of these filters. A lot of the code was naive (when not terribly wrong), despite the apparent good results. One of the major change I wanted to do was to evaluate the color distances using a perceptually uniform color space, instead of using a naive euclidean distance of RGB triplets. As usual it felt like a week-end long project; after all, all I have to do is change the distance function to work in a different space, right? Well, if you're following my blog you might have noticed I've add numerous adventures that stacked up on each others: I had to work out the colorspace with integer arithmetic first ...which forced me to look into integer division more deeply ...which confronted me to all sort of undefined behaviours in the process And when I finally reached the point where I could make the switch to OkLab (the perceptual colorspace), a few experiments showed that the flavor of the core algorithm I was using might contain some fundamental flaws, or at least was not implementing optimal heuristics. So here we go again, quickly enough I find myself starting a new research study in the pursuit of understanding how to put pixels on the screen. This write-up is the story of yet another self-inflicted struggle. Palette quantization But what is palette quantization? It essentially refers to the process of reducing the number of available colors of an image down to a smaller subset. In sRGB, an image can have up to 16.7 million colors. In practice though it's generally much less, to the surprise of no one. Still, it's not rare to have a few hundreds of thousands different colors in a single picture. Our goal is to reduce that to something like 256 colors that r