Brief
In NumPy, implement k-means++ seeding (choose starting centres that are spread far apart), Lloyd iterations (the standard k-means loop: assign each pixel to its nearest centre, then move each centre to the mean of its pixels), mini-batch k-means (the same loop on random subsets of pixels, for speed) and a full-covariance GMM (Gaussian mixture model, where each cluster is a Gaussian blob with its own shape and orientation) fitted by EM (expectation-maximisation: alternate between soft-assigning pixels to clusters and refitting the clusters). Do all of it in CIE Lab space (a colour space where distances roughly match how different two colours look to people). Optionally add Floyd–Steinberg dithering (pass each pixel's rounding error on to its neighbours so smooth gradients do not band). Quantise all 24 Kodak images to 16 colours. EM must be numerically safe: use log-sum-exp so probabilities do not underflow, and a covariance floor so no cluster collapses to zero width.
VICTORY CONDITIONS
- ≥ MEDIANCUT + 1.0 dB and ≥ LIBIMAGEQUANT − 0.3 dB, at ≤ 2 s per image (mean PSNR (peak signal-to-noise ratio in dB; higher means closer to the original) in RGB over the 24 Kodak images at a 16-colour palette; seconds per image).
- A public repository with a README that shows your result and how to reproduce it.
Terms in plain words
- PSNR
- A score in decibels for how close a compressed image is to the original; each +1 dB is a noticeable improvement.
- GMM (Gaussian mixture model)
- A clustering model where each cluster is a Gaussian with its own mean and covariance, and points belong to clusters softly.
- EM (expectation-maximisation)
- An algorithm that alternates between estimating which cluster each point belongs to and refitting the clusters to those estimates.
- CIE Lab
- A colour space designed so that equal distances look like equal colour differences to the human eye.
- Median cut
- A classic palette method that keeps splitting the box of colours at its median until there are enough boxes.
Why it rates ★☆☆☆☆
Colour quantisation is a classic toy problem, and the measurable win only shows that your EM and k-means are clean.