What to try
- Move the representatives to their cluster means, then reassign the samples.
- Select a representative and move its R or G coordinate to try a different starting point.
What to look for: Each Lloyd step keeps or lowers the squared error. After a mean update, held assignment lines can temporarily disagree with the new nearest-center regions.
How it works
Each input color is assigned to its nearest representative. In a k-means-style update, each representative moves to the mean of its assigned colors. Repeating assignment and updating reduces squared distance until the assignments or centers stop changing.
The distance space, initialization and weighting affect the result. The experiment uses a two-channel slice of RGB with blue fixed at 96, so its two-dimensional graph is an exact view of the chosen RGB distance problem. It is an educational Lloyd iteration, separate from the Lab’s median-cut, popularity and uniform palette methods.
Use it in the Lab
Use this model to understand why reducing palette size creates reconstruction error and why a representative color may not be one of the original samples. Compare that idea with the Lab’s Indexed palette tool.
Limits & distinctions
K-means can reach a local optimum. Minimizing RGB squared error is not the same as preserving every perceptually important accent.
Further reading
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
}Key Takeaway
Vector quantization is the theoretical foundation behind GIF, PNG palette modes, and any "reduce to N colors" operation. Whether you use K-means, median cut, or agglomerative grouping, the goal is always the same: represent the data with fewer vectors while minimizing error.
Related Lab categories
Sources & references
Guide updated