Machine Learning from First Principles

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 pixelSize vs 24-bitPSNR (dB)
4212× smaller21.5
838× smaller24.9
1646× smaller27.3
3254.8× smaller30.0
6464× smaller32.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

  1. Cluster in CIELAB instead of RGB and compare at $k = 8$.
  2. Implement Floyd–Steinberg dithering with the learned palette.
  3. Plot $J$ against $k$: is there an elbow?
  4. Use a Gaussian mixture instead of $k$-means.
Machine Learning from First Principles · Edition 2.0 · Companion site to the PDF book.