Linearly constrained generalized Lloyd algorithm for virtual codebook vector quantization

Linearly-constrained vector quantization (LCVQ) is efficient for block-based compression of images that require low complexity decompression. It is the ´de facto´ standard for 3D graphics cards that use texture compression. We extend the generalized Lloyd (1982) algorithm (GLA) for vector quantizer (VQ) codebook improvement and codebook design to a new linearly-constrained generalized Lloyd algorithm (LCGLA). This LCGLA improves VQ codebooks that are formed as linear combinations of Q reduced set of base codewords. As such, it finds application in a wide variety of signal compression and pattern recognition applications where linearly-constrained nearest-neighbour techniques are used. Experimental results show that the LCCLA significantly improves PSNR of standard high-quality lossy 6:1 LCVQ compressed images.