Every pixel of an image is a point in the three-dimensional space of red, green and blue intensities. K-means (Algorithm 15.1) groups these points into K clusters: the E step gives each pixel the label of its nearest centre, the M step moves each centre to the mean colour of its pixels. Redrawing every pixel in its centre's colour segments the image into K colours, and storing only the K centres and one label per pixel compresses it. Step through the algorithm, watch the distortion J fall, and compare the bit count with the quality of the picture. Switch to 2 × 2 blocks to quantise groups of neighbouring pixels instead, as the book suggests at the end of Section 15.1.1.
The image has N = 240 × 180 = 43,200 pixels with 8 bits per channel (24N bits). Vector quantisation sends the K codebook vectors (8 bits per number) and ⌈log2K⌉ bits per code. PSNR = 10 log10(1/MSE), with intensities in [0, 1]; higher is better. k-means++ draws each further starting centre with probability proportional to its squared distance from the centres already chosen.
code/ch15_discrete_latent_variables.py (vq_init, vq_kmeans, vq_bits; Figures 15.3 and 15.S1). With the same image, K, start and seed, the distortions shown here equal those of vq_kmeans.