Out of curiosity, yesterday I decided to start writing a VQ compression routine, based on the PVR VQ format.
Basically, there is a 2048 byte codebook, or palette, that stores the pixels, the actual texture is encoded as 8 bit indices into the palette.
The complex part is constructing the codebook.
My algorithm, using plain c and no external libs, stores the source pixels in a sorted array, discarding duplicate pixels.
From the sorted array, the pixels are averaged until they fit into the codebook.
Results are surprisingly good! In almost all cases, my VQ compression algorithm beats the downsampled texture, with better compression!
The Left Texture is uncompressed. Middle Texture is 1/2 resolution. Right Texture is VQ compressed: