OpenCV中的快速颜色量化

Question

如何以最快的方式使用OpenCV（+ C ++）减少图像中不同颜色的数量？我不想要完整的代码。我已经使用kmeans做了它，但它不是很快。这是我的代码的一部分很慢：

kmeans(samples, clusterCount, labels,
    TermCriteria(TermCriteria::EPS + TermCriteria::COUNT, 10, 10.0),
    1, KMEANS_RANDOM_CENTERS, centers);

这段代码需要几秒钟来处理，这对我来说非常慢。我正在使用Matlab（rgb2ind）这很快。差不多0.01秒。

我希望将我的代码用于生产，用户希望程序能够快速生成。

有没有替代k的颜色量化方法？有没有办法运行k意味着更快（我不这么认为，因为我尝试了很多不同的参数）？

编辑： 原来的颜色量化是一个非常复杂的主题，需要时间来编写一个优秀的优化。我决定使用Magick++ (ImageMagick API)。 因此我没有尝试过Cris Luengo的新（编辑）答案。但我将其标记为答案（也请查看评论），以便其他人不认为这个问题没有得到解答。

Answer 1

量化颜色的方法有很多种。我在这里描述四个。

Uniform quantization

在这里，我们使用具有均匀分布颜色的颜色映射，无论它们是否存在于图像中。在MATLAB中，你会写

qimg = round(img*(N/255))*(255/N);

将每个通道量化为N水平（假设输入在[0,255]范围内。你也可以使用floor，这在某些情况下更合适。这导致N^3不同的颜色。例如使用N=8你会得到512种独特的RGB颜色。

K-means clustering

这是生成自适应调色板的“经典”方法。显然它将是最昂贵的。 OP正在对所有像素的集合应用k均值。相反，k-means可以应用于颜色直方图。这个过程是相同的，但不是1000万个数据点（现在是一个典型的图像），你只有32 ^ 3 = 33千。在处理自然照片时，由具有减少的箱数的直方图引起的量化在这里几乎没有影响。如果要量化具有有限颜色集的图形，则无需进行k均值聚类。

您可以通过所有像素单次传递以创建直方图。接下来，运行常规k-means聚类，但使用直方图箱。现在每个数据点都有一个权重（该区域内的像素数），您需要考虑它。确定群集中心的算法步骤受到影响。您需要计算数据点的加权平均值，而不是常规平均值。

结果受初始化影响。

Octree quantization

八叉树是用于空间索引的数据结构，其中通过将每个轴切成两半来将体积递归地划分为8个子体积。因此，树由每个有8个孩子的节点组成。对于颜色量化，RGB立方体由八叉树表示，并计算每个节点的像素数（这相当于构建颜色直方图，并在其上构建八叉树）。接下来，移除叶节点，直到剩下所需数量的叶节点。移除叶节点一次发生8个，使得一个级别的节点变为叶子。有不同的策略可以选择修剪哪些节点，但它们通常围绕具有低像素数的修剪节点。

这是Gimp使用的方法。

因为八叉树总是在中间分割节点，所以它不像k-means聚类或下一个方法那样灵活。

Minimum variance quantization

OP提到的MATLAB's rgb2ind做了均匀量化，他们称之为“最小方差量化”：

最小方差量化将RGB颜色立方体切割成不同尺寸的较小框（不一定是立方体），具体取决于颜色在图像中的分布方式。

我不确定这意味着什么。 This page不会放弃任何东西，但它有一个看起来像RGB立方体的k-d树分区的数字。 K-d树是空间索引结构，其将空间数据递归地分成两半。在每个级别，您选择最大分离的维度，并沿该维度拆分，从而导致一个额外的叶子节点。与八叉树相反，分裂可以发生在最佳位置，而不是在节点的中间。

使用空间索引结构（k-d树或八叉树）的优点是颜色查找非常快。从根开始，根据R，G或B值做出二元决策，直到到达叶节点。没有必要计算到每个原型集群的距离，就像k-means的情况一样。

[编辑两周后]我一直在考虑可能的实施，以及came up with one。这是算法：

• 全彩色直方图被视为分区。这将是k-d树的根，现在它也是叶节点，因为还没有其他节点。
• 创建优先级队列。它包含k-d树的所有叶节点。如果我们要沿着该轴分割分区，则优先级由沿一个轴的分区的方差给出，减去两个半部的方差。选择分割位置使得两半的方差最小（使用Otsu算法）。也就是说，优先级越大，通过进行拆分我们减少的总方差就越大。对于每个叶节点，我们为每个轴计算此值，并使用最大的结果。
• 我们处理队列中的分区，直到我们有所需的分区数： 我们沿着轴和在确定优先级时计算的位置拆分具有最高优先级的分区。 我们计算两半中每一半的优先级，并将它们放在队列中。

当用这种方式描述时，这是一个相对简单的算法，the code有点复杂，因为我试图使其高效但通用。

Comparison

在256x256x256 RGB直方图上，我得到了这些时间比较k-means聚类和这个新算法：

# clusters    kmeans (s)    minvar (s)
     5          3.98         0.34
    20         17.9          0.48
    50        220.8          0.59

注意，随着簇数的增加，k-means需要更多的迭代，因此指数时间增加。通常情况下，人们不会使用如此大的直方图，我希望拥有大量数据来使时序更加稳健。

以下是应用于测试图像的这三种方法的示例：

输入：

使用N=4统一导致多达64种不同的颜色[使用N=2获得8种不同颜色并与其他方法相比，结果非常难看]：

K-means有8种颜色：

新的“最小方差”有8种颜色：

我喜欢这个最后的结果比K-means结果更好，尽管它们非常相似。

Answer 2

Fast pairwise nearest neighbor based algorithm有8种颜色 高品质，快速

Efficient, Edge-Aware, Combined Color Quantization and Dithering有8种颜色 32或更少颜色的更高质量，但更慢

Spatial color quantization有8种颜色 32或更少颜色的更高质量，但最慢

Sample c++ code 对于速度，它可能取决于GPU parallel programming C/C++。