6

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

目前，我使用 kmeans-algorithm 对整个图像进行聚类。但这需要很长时间。有人知道如何使用 kmeans 对颜色直方图进行聚类，所以我可以执行这个算法吗？

4

3 回答 3

5

首先对图像进行下采样，然后运行 ​​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-means 的复杂性是O(n*k*i)，其中n是您拥有的像素数， k是所需的输出颜色数，i是收敛所需的迭代次数。

n：通过下采样，您可以轻松减少n最大的因素。在许多情况下，您可以在看到性能下降之前显着减少这种情况。

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

i：各种因素都会对收敛产生影响（包括其他两个因素！），但最强的可能是具有良好的起始值。因此，如果您有一个非常快速但质量低的方法来选择调色板，请先运行它，然后使用 k-means 来优化此调色板。不过，也许 OpenCV 已经为此包含了适当的启发式方法！

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

于 2012-11-28T23:28:47.833 回答
1

我的答案与直方图聚类无关，但最近我需要加快算法的聚类过程。为此，我做了以下事情：

  1. 将图像调整为较小的图像（实际上已经建议）
  2. 减少颜色数量（图像量化）。我按照这里的建议做了：如何使用 OpenCV 减少图像中的颜色数量？.

这确实帮助我在某些时候加速了集群化。您也可以尝试使用 OpenCV 的mean-shift filtering。

于 2012-11-29T12:53:59.987 回答
0

您需要为每个数据分配一个权重，即直方图箱中的值的数量。然后，当您计算集群质心的新值时，您使用加权平均值而不是普通平均值。但是 OpenCV KMeans 聚类的接口不支持加权值。您可以使用确实支持它的C 集群库，它有很好的文档记录（尽管从生物信息学中获取示例），并且易于集成（单个 .h/.c 文件）。

于 2012-11-29T09:11:30.750 回答