前言
之前想对图片素材进行分类管理，除了打标签，还有一种是通过主题色进行分类。于是开始寻找能提取主题色的工具，最后找到了大名鼎鼎的 Leptonica 库，其中就有中位切割算法的实现。下面附上中位切割算法的其他语言版本的实现。
- JavaScript版：quantize （此库有提取颜色数量不对的问题，见 issues/9）
- Java版：theme-color （我自己基于 quantize 实现的Java版）
中位切割算法（Median cut）
theme-color 项目的效果如下：
在介绍中位切分法之前，我们先来聊一下颜色如何描述。
颜色模型
常见的颜色模型包括 RGB 和 HSV 等，而中位切分法是基于 RGB 模型的。RGB 模型是一种加色模型，通过不同比例的红（Red）、绿（Green）、蓝（Blue）三原色的色光相加来合成各种色彩光。每个像素用一个由24位编码的 RGB 值表示，这里使用三个8位无符号整数（0到255）表示红色、绿色和蓝色的强度。如果将所有的颜色采用三维空间来进行描述，则如下图所示：
算法实现
中位切割算法（Median cut）是由 Paul Heckbert 在 1979 年提出的算法。它的原理是将图像颜色映射成三维色彩空间中的长方体，然后沿着 RGB 中最长的一边，从颜色数量统计的中位数一切为二，使得到的两个长方体所包含的像素数量相同。重复这个步骤，直到得到想要数量的长方体。
虽然算法很简单，但是 Leptonica 的实现包含了很多细节。
压缩颜色总数
算法需要统计图像的每种颜色的数量（色彩分布图），也就是需要将三维的长方体映射到一维的数组中。由于 RGB 总颜色数量达到了 1677 万（2^8 * 2^8 * 2^8），这在检索的时候会造成不小的性能开销。因此，将 8 位无符号整数（0到255）压缩到 5 位无符号整数（0到31）可以大大减少总数量到 2^5 * 2^5 * 2^5 = 32768。而且可以使用 int 来表示数组下标了。
中位切分的优化
原始的中位切分法是按照颜色数量的中位数将长方体（vbox）切成两半的。Leptonica 中对此进行了优化，改成了先通过中位数将 vbox 分为左右两个vbox（只是分出左右，还未切割），然后从左右选出体积较大的vbox的中点进行切割。以下是作者原话：
Determine the cut planes, making sure that two vboxes are always produced. Generate the two vboxes and compute the sum in each of them. Choose the cut plane within the greater of the (left, right) sides of the bin in which the median pixel resides. Here’s the surprise: go halfway into that side. By doing that, you technically move away from “median cut,” but in the process a significant number of low-count vboxes are produced, allowing much better reproduction of low-count spot colors.
长方体体积大包含像素少问题
存在某些条件下，VBox 体积很大但只包含少量像素。解决的方法是，每次切分前先对所有 vbox 排序，再取出优先级最高的 vbox 进行中位切分。如果需要切割的 vbox 总数为 total，那么前 total * FractByPopulation 个 vbox 以 vbox包含的像素数 排序，后 total * (1-FractByPopulation) 个 vbox 以 包含像素数 * vbox体积 排序。
Leptonica 库中的 FractByPopulation 值为 0.85，在 quantize 库中为 0.75。
总结
本文介绍了中位切割算法以及在 Leptonica 库中的实现。
备注：文章使用chagGPT进行润色。
参考资料
三原色光模式 – 维基百科，自由的百科全书 (wikipedia.org)