如何加速openCV中的颜色聚类？

Question

对于一个项目我想实现一个颜色聚类算法,它用一个簇的平均颜色替换相似的颜色.

现在,我使用kmeans算法来聚类整个图像.但这需要很长时间.有人知道如何使用kmeans聚类颜色直方图,所以我可以执行这个算法吗？

Answer 1

首先对图像进行下采样,然后运行k-means.

如果你在x和y中将图像的大小调整为1/2,它不应该对颜色产生太大影响,但k-means应该最多占用1/4的时间.如果重新采样到宽度和高度的1/10,k-means应该快100倍.

https://en.wikipedia.org/wiki/Color_quantization

通过对图像进行下采样,可以在聚类期间处理较少的"像素".但最终,它应该产生大致相同的配色方案.

k -means的小摘要:

1. 它将每个对象(=像素)映射到最近的聚类中心(=调色板条目)
2. 它重新计算每个调色板条目以最好地表示指定的点(=像素)
3. 重复,直到没有任何变化.

所以实际输出不是图像或图像区域.这是调色板.

然后,您可以通过简单地用最接近的颜色替换每个像素,将任意图像(包括全分辨率版本)映射到此调色板!

复杂性和性能:

所述的k均值复杂度O(n*k*i),其中,n是的数目像素你有,ķ输出颜色的期望数目和我需要直到收敛的迭代次数.

n:通过下采样,您可以轻松减少n,最大的因素.在许多情况下,在看到性能下降之前,可以非常显着地减少这种情况.

k:这是您想要的输出颜色数.是否可以减少这种情况取决于您的实际使用情况.

i:各种因素会对收敛产生影响(包括其他因素!),但最强的可能是具有良好的起始值.因此,如果你有一个非常快但质量低的方法来选择调色板,先运行它,然后使用k-means来优化这个调色板.也许OpenCV已经包含了适当的启发式算法!

你可以看到,最简单的方法是减少n.您可以n显着减少,为缩略图生成优化的调色板,然后在整个图像上重新运行 k-means,以修整此调色板.正如 - 希望 - 这将显着减少迭代次数,这有时可以很好地执行.