Vector quantization is the process of partitioning a large set of vectors into groups (clusters), each represented by a single centroid. In the context of color, every pixel is a 3D vector (R, G, B), and vector quantization reduces millions of unique colors down to a small, representative palette.
K-Means Clustering
The most common algorithm for vector quantization is K-means. It works by:
- Choosing K initial centroids (e.g., randomly or via K-means++)
- Assigning every pixel to its nearest centroid (using Euclidean distance)
- Recalculating each centroid as the average of its assigned pixels
- Repeating steps 2–3 until convergence (centroids stop moving)
Median Cut Alternative
Median cut is a deterministic alternative that recursively splits the color space along its longest axis. It produces exactly 2ⁿ colors and tends to allocate more palette entries to regions of the image with greater color variation.
Our Approach: Exact + Grouped
Rather than using K-means, our palette extraction uses a two-tier strategy. For indexed images (≤ 256 unique colors), we extract the exact palette. For RGB images with thousands of colors, we use agglomerative grouping: merge pixels by Euclidean distance and keep the top 64 dominant colors. This avoids K-means' dependence on random initialization and gives consistent, deterministic results.
// Simplified grouping approach
function groupColors(
colors: Map<string, number>,
maxColors: number,
threshold: number,
): string[] {
// Sort by frequency (most common first)
// Merge colors within `threshold` Euclidean distance
// Return top `maxColors` representatives
}