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

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

这段代码需要几秒钟的时间来处理，这对我来说非常非常慢。我为此使用了Matlab（rgb2ind）速度很快。差不多0.01秒。

我想将我的代码用于生产，用户期望程序速度快。

除了 kmeans 之外还有什么颜色量化的替代方案吗？有什么方法可以更快地运行 kmeans （我不这么认为，因为我尝试了许多不同的参数）？

Edit:
事实证明，颜色量化是一个非常复杂的主题，需要时间来编写一个良好的优化主题。我决定使用Magick++ (ImageMagick API)为了这。
因此，我还没有尝试过 Cris Luengo 的新（编辑）答案。但我将其标记为答案（也请查看评论），这样其他人就不会认为这个问题没有得到解答。

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

均匀量化

在这里，我们使用具有均匀分布颜色的颜色图，无论它们是否存在于图像中。用 MATLAB 语言你可以这样写

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

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

K-均值聚类

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

您只需一次遍历所有像素即可创建直方图。接下来，您运行常规 k 均值聚类，但使用直方图箱。每个数据点现在也有一个权重（该箱内的像素数），您需要考虑这一点。算法中确定聚类中心的步骤会受到影响。您需要计算数据点的加权平均值，而不是常规平均值。

结果受初始化的影响。

八叉树量化

八叉树是一种用于空间索引的数据结构，其中通过将每个轴切成两半，将卷递归地分为 8 个子卷。因此，该树由每个节点有 8 个子节点组成。对于颜色量化，RGB 立方体由八叉树表示，并计算每个节点的像素数（这相当于构建颜色直方图，并在其上构建八叉树）。接下来，删除叶节点，直到留下所需数量的叶节点。删除叶子节点一次发生 8 个，这样上一层的节点就成为叶子。有不同的策略来选择要修剪的节点，但它们通常围绕修剪像素数较低的节点进行。

这就是 Gimp 使用的方法。

因为八叉树总是从中间分割节点，所以它不像 k-means 聚类或 next 方法那么灵活。

最小方差量化

MATLAB的rgb2ind https://www.mathworks.com/help/matlab/ref/rgb2ind.htmlOP提到的，进行统一量化和他们所谓的“最小方差量化”：

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

我不确定这意味着什么。这一页 https://www.mathworks.com/help/images/reduce-the-number-of-colors-in-an-image.html#f8-13153没有透露更多信息，但它有一个看起来像 RGB 立方体的 k-d 树分区的图形。 K-d 树是一种空间索引结构，它将空间数据递归地分成两半。在每一级别，您选择分离程度最高的维度，并沿该维度进行拆分，从而产生一个额外的叶节点。与八叉树相反，分裂可以发生在最佳位置，而不是节点的中间。

使用空间索引结构（k-d 树或八叉树）的优点是颜色查找非常快。您从根开始，根据 R、G 或 B 值做出二元决策，直到到达叶节点。无需像 k 均值那样计算到每个原型簇的距离。

[两周后编辑]我一直在考虑一个可能的实施方案，并且想出了一个 https://github.com/DIPlib/diplib/blob/master/src/segmentation/minimum_variance_partitioning.cpp。这是算法：

• 全色直方图被视为分区。这将是 k-d 树的根，它现在也是叶节点，因为还没有其他节点。
• 创建优先级队列。它包含k-d树的所有叶节点。优先级由分区沿一个轴的方差给出，如果我们要沿该轴分割分区，则减去两半的方差。选择分割位置以使两半的方差最小（使用大津算法）。也就是说，优先级越大，我们通过分割减少的总方差就越多。对于每个叶节点，我们计算每个轴的该值，并使用最大的结果。
• We process partitions on the queue until we have the desired number of partitions:
  • 我们沿着轴并在确定优先级时计算的位置分割具有最高优先级的分区。
  • 我们计算两半的优先级，并将它们放入队列中。

当这样描述时，这是一个相对简单的算法，the code https://github.com/DIPlib/diplib/blob/master/src/segmentation/minimum_variance_partitioning.cpp有点复杂，因为我试图使其高效但通用。

比较

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

请注意，随着簇数量的增加，k 均值需要更多的迭代，因此时间呈指数增长。通常情况下，人们不会使用这么大的直方图，我想要拥有大数据以使计时更加稳健。

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

Input:

制服与N=4导致多达 64 种不同的颜色 [与N=2得到8种不同的颜色并与其他方法进行比较，结果非常难看]：

K-means 有 8 种颜色：

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

与 K 均值结果相比，我更喜欢最后一个结果，尽管它们非常相似。

该程序说明了如何使用进行颜色量化DIPlib https://diplib.org及其最小方差划分的实现：

#include "diplib.h"
#include "dipviewer.h"
#include "diplib/simple_file_io.h"
#include "diplib/histogram.h"
#include "diplib/segmentation.h"
#include "diplib/lookup_table.h"

int main() {
   dip::Image input = dip::ImageRead( "/Users/cris/dip/images/flamingo.tif" );
   input.SetColorSpace( "RGB" ); // This image is linear RGB, not sRGB as assumed when reading RGB TIFFs.

   // Compute the color histogram.
   dip::Histogram hist( input, {}, { dip::Histogram::Configuration( 0.0, 255.0, 64 ) } );

   // Cluster the histogram, the output histogram has a label assigned to each bin.
   // Each label corresponds to one of the clusters.
   dip::uint nClusters = 8;
   dip::Image histImage = hist.GetImage(); // Copy with shared data
   dip::Image tmp;
   dip::CoordinateArray centers = dip::MinimumVariancePartitioning( histImage, tmp, nClusters );
   histImage.Copy( tmp ); // Copy 32-bit label image into 64-bit histogram image.

   // Find the cluster label for each pixel in the input image.
   dip::Image labels = hist.ReverseLookup( input );

   // The `centers` array contains histogram coordinates for each of the centers.
   // We need to convert these coordinates to RGB values by multiplying by 4 (=256/64).
   // `centers[ii]` corresponds to label `ii+1`.
   dip::Image lutImage( { nClusters + 1 }, 3, dip::DT_UINT8 );
   lutImage.At( 0 ) = 0; // label 0 doesn't exist
   for( dip::uint ii = 0; ii < nClusters; ++ii ) {
      lutImage.At( ii + 1 ) = { centers[ ii ][ 0 ] * 4, centers[ ii ][ 1 ] * 4, centers[ ii ][ 2 ] * 4 };
   }

   // Finally, we apply our look-up table mapping, painting each label in the image with
   // its corresponding RGB color.
   dip::LookupTable lut( lutImage );
   dip::Image output = lut.Apply( labels );
   output.SetColorSpace( "RGB" );

   // Display
   dip::viewer::ShowSimple( input, "input image" );
   dip::viewer::ShowSimple( output, "output image" );
   dip::viewer::Spin();
}