Side match and overlap match vector quantizers for images

We investigate a class of vector quantizers with memory that are known as finite state vector quantizers (FSVQ's), in the image coding framework. Introduced in this paper are two new FSVQ designs, namely, side match vector quantizers (SMVQ's) and overlap match vector quantizers (OMVQ's). These new designs take advantage of the two-dimensional spatial contiguity of pixel vectors as well as the high spatial correlation of pixels in typical grey-level images. The underlying ideas of SMVQ and OMVQ are simple and intuitive, and thus, so are their design procedures. They try to minimize the granular noise that causes the annoying effect of visible pixel block boundaries in ordinary vector quantization (VQ). Experimental results prove that when applied to 512 by 512 grey level images, SMVQ and OMVQ can achieve communication quality reproduction (33.5-dB peak signal-to-noise ratio (PSNR)) at an average of 1/2 b/pixel per image frame, and acceptable quality reproduction (30-dB PSNR) at 1/4 b/pixel. These performances are superior to those of ordinary VQ by more than 3 dB in PSNR. Further, because block boundaries are less visible, the perceived improvement in quality over ordinary VQ is even greater. We obtained the above bit rates by using simple memoryless variable length noiseless codes. Owing to the structure of SMVQ and OMVQ, simple variable length noiseless codes can achieve as much as 60% bit rate reduction over fixed length noiseless codes. Although many FSVQ's require large memory spaces for state codebooks (or subcodebooks), it is shown that the memory space requirement of SMVQ and OMVQ can be reduced to a manageable size without impairing the quality.