Vector quantization (VQ) is a lossy compression method that groups samples into blocks (vectors), and replaces each vector by the index of the closest vector (codeword) in a pre-designed codebook.
Scalar vs vector quantization. Scalar quantization rounds each pixel separately. VQ quantizes a group of pixels together, so it can exploit the correlation between neighbouring pixels and reach lower bit rates.
Steps
- Form vectors: divide the image into small blocks, e.g. 2×2 pixels → 4-dimensional vectors.
- Design a codebook of \(K\) representative vectors (codewords) from training images, usually with the LBG (Linde–Buzo–Gray) algorithm, which is similar to K-means clustering.
- Encoding: for each input vector, find the nearest codeword (minimum Euclidean distance) and transmit only its index (\(\log_2K\) bits).
- Decoding: the decoder has the same codebook and replaces each index by its codeword (a simple table look-up).
Example. Take pairs of adjacent pixels as 2-D vectors: (10, 12), (11, 11), (200, 198), (202, 205), (100, 98). Codebook: index 0 = (11, 11), index 1 = (200, 200), index 2 = (100, 100).
- (10, 12) → 0, (11, 11) → 0, (200, 198) → 1, (202, 205) → 1, (100, 98) → 2
- Transmitted: 0, 0, 1, 1, 2 (2 bits each)
- Reconstructed: (11, 11), (11, 11), (200, 200), (200, 200), (100, 100), close to the original.
Each pair originally needs 16 bits (2 × 8); now it needs 2 bits, a compression ratio of 8:1. With 2×2 blocks (32 bits) and a 256-codeword codebook (8-bit index), the ratio is 4:1, i.e. 2 bits per pixel.
Advantages: high compression ratios; very fast decoding (look-up only).
Disadvantages: lossy; codebook design and the nearest-codeword search during encoding are computationally expensive; edges may look blocky; quality depends on how well the training images match the input.