A k-means palette generation mockup

kmeans.md

static uint32_t num_itters = 32;
static uint32_t num_clusters = 16;

struct rgb_t {
    uint8_t r, g, b;
};

struct cluster_t {
    uint32_t r, g, b;
    uint32_t mr, mg, mb, mw;
};

uint32_t distance(const rgb_t &a, const cluster_t &b) {
    int32_t dr = int32_t(b.r) - int32_t(a.r);
    int32_t dg = int32_t(b.g) - int32_t(a.g);
    int32_t db = int32_t(b.b) - int32_t(a.b);
    return dr*dr + dg*dg + db*db;
}

void init(std::array<cluster_t, num_clusters> &c) {
    //     - evenly spaced ?
    //     - poison distribution
    //     - random
}

void create_palette(const image_t &img, palette_t &palette) {

    const uint32_t w = img.width, h = img.height;

    std::array<cluster_t, num_clusters> cluster;
    cluster.fill(cluster_t{0});
    init(cluster);

    while (num_itters--) {

        // cluster pixels in the pixel map
        for (uint32_t i=0; i<w*h; ++i) {

            // pixel colour
            const rgb_t pix = {
                img.pixels[i] & 0x0000ff) >> 0,
                img.pixels[i] & 0x00ff00) >> 8,
                img.pixels[i] & 0xff0000) >> 16,
            };

            // find nearest cluster
            const uint32_t best = distance(pix, cluster[0]);            
            for (uint32_t c=1; c<num_clusters; ++c) {

                // rgb space distance
                const uint32_t dist = distance(cluster[c], pix);
                
                // save the best
                if (dist < best) {
                    map[i] = c;
                }
            }

            // add to nearest cluster
            cluster[best].mr += pix.r;
            cluster[best].mg += pix.g;
            cluster[best].mb += pix.b;
            cluster[best].mw++;
        }
        
        // calculate mean of all clusters
        for (auto &c: cluster) {

            // note: poorly performing clusters could be reassigned (moved)
        
            // divide by w
            if (c.mw) {
                c.r = c.mr / c.mw;
                c.g = c.mg / c.mw;
                c.b = c.mb / c.mw;
            }
            
            // clear accumulator
            c.mr = c.mg = c.mb = c.mw = 0;
        }
        
    }
}