K-means聚類算法計算給定圖像中主要顏色

pn0264 10年前發布 | 30K 次閱讀算法

來自： https://blog.0xbbc.com/2016/02/using-k-means-cluster-algorithm-to-compute-the-dominant-colors-of-given-image/

早在2012的時候，iTunes 11就可以從封面中自動提取出主要的顏色用在歌曲列表里的字體和背景上了。

然而當時的我萬萬沒有想到的是，如今自己也需要這樣的算法了。

簡單考慮了一下，打算用OpenCV讀圖，然后自己實現一下K-means算法來計算出給定圖像中主要顏色。

對于聚類算法的綜合性介紹可以參見這篇zhihu上的回答，用于數據挖掘的聚類算法有哪些，各有何優勢？，及其這篇scikit-learn上的文章，scikit-learn Clustering?。本文不再對聚類算法展開敘述。

其實整體思路很簡單，先加載圖片，然后按比例縮放為較小的圖，隨后統計小圖中所有出現的顏色及其次數，從這些顏色中隨機選k個作為初始條件開始進行K-means聚類，隨機數用標準MersenneTwister PRNG，在計算距離時用L2 norm的歐式距離（Euclidean distance），最后以精度作為迭代結束的條件。

核心的K-means聚類算法就寥寥數十行，

Cluster mashiro::kmeans(const vector<MashiroColorWithCount>& pixels, std::uint32_t k, double min_diff) noexcept {
    Cluster clusters;
    uint32_t randmax = static_cast<uint32_t>(pixels.size());
    // 使用標準MersenneTwister PRNG保證取的點的隨機性
    MersenneTwister mt(static_cast<uint32_t>(time(NULL)));
    // 取出k個點
    for (uint32_t i = 0; i < k; i++) {
        auto iter = pixels.cbegin();
        for (uint32_t t = 0; t < mt.rand() % randmax; t++, iter++);
        clusters.emplace_back(iter->first);
    }

    while (1) {
        ClusteredPoint points;
        // 與每一類的中心點比較距離, 找一個最鄰近的類
        for (auto iter = pixels.cbegin(); iter != pixels.cend(); iter++) {
            MashiroColor color = iter->first;

            double smallestDistance = DBL_MAX;
            double distance;
            uint32_t smallestIndex;
            for (uint32_t i = 0; i < k; i++) {
                distance = mashiro::euclidean(color, clusters[i]);
                if (distance < smallestDistance) {
                    smallestDistance = distance;
                    smallestIndex = i;
                }
            }
            points[smallestIndex].emplace_back(MashiroColorWithCount(color, iter->second));
        }
        // 重新計算每類的中心值
        double diff = 0;
        for (std::uint32_t i = 0; i < k; i++) {
            MashiroColor oldCenter = clusters[i];
            MashiroColor newCenter = mashiro::center(points[i]);
            clusters[i] = newCenter;
            diff = max(diff, mashiro::euclidean(oldCenter, newCenter));
        }
 
        // 當差距足夠小時, 停止循環
        if (diff < min_diff) {
            break;
        }
    }
    return clusters;
}

你可以在我的GitHub上找到這個項目，mashiro

mashiro的API的形式也很簡單

Mat image = imread("/PATH/TO/AN/IMAGE");

mashiro mashiro(image);
mashiro.color(color, [](Mat& image, const Cluster colors){
    for_each(colors.cbegin(), colors.cend(), [](const MashiroColor& color){
        cout<<"("
            <<std::get<mashiro::toType(MashiroColorSpaceRGB::Red)>(color)<<", "
            <<std::get<mashiro::toType(MashiroColorSpaceRGB::Green)>(color)<<", "
            <<std::get<mashiro::toType(MashiroColorSpaceRGB::Blue)>(color)<<")"
            <<endl;
      });
});

我們將用這張圖來測試