学步园

转自 http://www.kaixinwenda.com/article-lisztlee-8460245.html

前几天在研究chromium代码的时候看到了一个取PNG图片主色调（dominant color）的算法，这个算法不是取图片中所有点的平均RGB值，也不是取同一RGB值最多的点的RGB。chromium中取图片主色调用的算法用的是 KMean clustering。可以算是KMean clustering的一个实际应用，chromium自己将其取名为RGB KMean Algorithm。

     首先我们可以来简单了解一下KMean clustering算法（如果你已经足够熟悉，这里可以略过）。酷壳中有一篇K-Means 算法的文章专门介绍过这个算法，我最初对这个算法的了解也源于此，讲的也挺详细。如果你觉得这个还不能满足你的需求，可以再继续看看维基k-means clustering。

     KMean clustering算法的基本思想就是：

          1、随机在图中取K个种子点。
          2、然后对图中的所有点求到这K个种子点的距离，假如点Pi离种子点Si最近，那么Pi属于Si点群。

          3、接下来，我们要移动种子点到属于他的“点群”的中心。

          4、然后重复第2）和第3）步，直到，种子点没有移动。

     接下来我们再来了解一下chromium是如何利用KMean clustering算法来算出图片主色调的。

     之前我们了解到的KMean clustering算法是从坐标空间来计算的。而主色调算法RGB KMean Algorithm则需要从RGB空间来计算的。总体思想还是一至，就是将坐标空间向RGB空间做了一个转换。

     RGB KMean Algorithm的基本执行步骤如下：

          1、定义一个迭代次数上限M。

          2、随机在图中找N个点，取出它的RGB值作为种子点。
          3、然后对图中的每个点找到一个RGB值和它最相近的种子点，并将这个点加到RGB值最相近得种子点所在点群中。假如点Pi离种子点Si的RGB值最相 近，那么Pi属于Si点群。（我们为每个点群记录一个累加总值以及一个计数器，每加入一个点时我们都要更新这两个值）。

          4、计算种子点群的平均RGB值（累加总值/点的个数），并将这个RGB值作为新的种子点。

          5、比较这个新的值是否和旧值是否相等。

           a) 如果相等，则种子点收敛完成，进入第6步。

           b) 如果不等，则继续执行第2步，直至迭代次数达到M次。

          6、当种子点收敛完成或者迭代次数达到M次，我们对所有种子点的权重做一个排序（权重即其中包含点的个数）。

          7、取出权重最高的种子点的值，这个值即我们所需的图片的主色调。

     chromium中的代码设计的比较多，我会把其中主要的代码贴出来，其中还涉及到了其他的一些实现，可以直接到chromium的代码color_analysis.h，color_analysis.cc中查看（找到CalculateKMeanColorOfPNG方法的实现即可）。如果还想搜其他的代码，你可以根据自己的需求在google codesearch中查找。

     chromium中实现代码如下：