Project 4 · Part VII: Projects
Image Color Quantization
Every pixel is a point in RGB space. Cluster the points with $k$-means, and the centers become a $k$-color palette: image compression with twenty lines of code.
After this project you will be able to
- Cluster pixels with $k$-means.
- Implement $k$-means++ and vectorized assignment.
- Measure compression against quality (MSE, PSNR).
- Speed up clustering with sampling and mini-batches.
Code: projects/p4_color_quantization/. Background: Chapter 13.
P4.1The Problem
Replace every pixel by one of $k$ palette colors so it needs $\log_2 k$ bits instead of 24, as GIF and PNG-8 do. $k$-means picks the palette that minimizes total squared color error.
P4.2The Data
By default, scikit-learn's bundled temple photograph (640×427, about 97,000 distinct colors); any image path works. Each pixel is $(r, g, b)\in[0,1]^3$, giving 273,280 points.
P4.3Building It from Scratch
Expanding $\norm{\vx - \vc}^2 = \norm{\vx}^2 - 2\vx\T\vc + \norm{\vc}^2$ and dropping the constant turns assignment into one matrix product. Fit the palette on 20,000 sampled pixels, then map all pixels.
def assign(X, C):
d = -2 * X @ C.T + np.sum(C**2, axis=1)
return d.argmin(1)
def quantize(img, k, sample=20000, seed=0):
X = img.reshape(-1, 3)
rng = np.random.default_rng(seed)
S = X[rng.choice(len(X), size=min(sample, len(X)), replace=False)]
C, _, _ = kmeans(S, k, seed=seed) # k-means++ seeding + Lloyd iterations
return C[assign(X, C)].reshape(img.shape), C
P4.4Using Libraries
KMeans(16, n_init=4) reached MSE 0.00177 on the sample; MiniBatchKMeans reached 0.00185 in less than half the time.
P4.5Results and Discussion
| $k$ | Bits per pixel | Size vs 24-bit | PSNR (dB) |
|---|---|---|---|
| 4 | 2 | 12× smaller | 21.5 |
| 8 | 3 | 8× smaller | 24.9 |
| 16 | 4 | 6× smaller | 27.3 |
| 32 | 5 | 4.8× smaller | 30.0 |
| 64 | 6 | 4× smaller | 32.3 |
Each extra bit buys about 2.5–3 dB. $k$-means spends many colors on large smooth regions and few on small salient details, because it minimizes total squared error rather than perceived error; perceptual color spaces and dithering help.
P4.6Extensions
- Cluster in CIELAB instead of RGB and compare at $k = 8$.
- Implement Floyd–Steinberg dithering with the learned palette.
- Plot $J$ against $k$: is there an elbow?
- Use a Gaussian mixture instead of $k$-means.