改进色彩量化启发式算法

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.

2015年，我写了一篇关于FFmpeg中如何改进调色板颜色量化以制作精美动画GIF文件的文章。不知为何，直到今天这仍然是我最受欢迎的文章之一。

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.

我想做的主要改变之一是使用 perceptually uniform color space 来评估颜色距离，而不是使用 RGB triplets 的简单 euclidean distance。

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.

当我终于达到可以切换到OkLab（感知色彩空间）的阶段时，一些实验表明，我使用的核心算法的具体风格可能包含一些根本性的缺陷，或者至少没有实现最优的启发式方法。所以我们又要重头开始了，很快我发现自己又开始了一项新的研究，以追求理解...