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秒.

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

有没有替代kmeans颜色量化？有没有办法更快地运行kmeans(我不这么认为,因为我尝试了很多不同的参数)？

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

Answer 1

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

均匀量化

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

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

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

K均值聚类

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

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

结果受初始化影响.

八叉树量化

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

这是Gimp使用的方法.

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

最小方差量化

rgb2indOP提到的MATLAB做了均匀量化,他们称之为"最小方差量化":

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

我不确定这意味着什么.此页面不会提供任何其他内容,但它的图形看起来像RGB多维数据集的kd树分区.Kd树是空间索引结构,其将空间数据递归地分成两半.在每个级别,您选择具有最多分离的维度,并沿该维度拆分,从而导致一个额外的叶子节点.与八叉树相反,分裂可以发生在最佳位置,而不是在节点的中间.

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

[编辑两周后]我一直在考虑可能的实施,并想出了一个.这是算法:

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

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

对照

在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

快速成对基于最近邻居的 8种颜色算法
高质量和快速

高效，边缘感知， 8种颜色组合的色彩量化和抖动功能
高质量（32种或更少）的颜色，但速度较慢

8种颜色的空间颜色量化
高质量的32种或更少的颜色，但最慢

示例c ++代码
为了提高速度，可能取决于 GPU并行编程C / C ++。