Image-sequence coding with generalized threshold replenishment - A new algorithm for adaptive vector quantization

Vector quantization (VQ) has recently received significant attention as-a-powerful technique for data compression. VQ is theoretically attractive due to results from rate-distortion theory that show that VQ is asymptotically optimal for the coding of stationary data sources. However, the nonstationary nature of the sources common in practical applications has prompted a search for more general VQ algorithms that are capable of adapting to changing source statistics as the coding progresses. Such algorithms are commonly referred to as adaptive vector quantization (AVQ). We describe a new AVQ algorithm called generalized threshold replenishment (GTR) which differs from prior AVQ algorithms in that it features an explicit, online consideration of both rate and distortion, Rate-distortion cost criteria are used in both the determination of nearest-neighbor codewords and the decision to update the codebook. Results presented indicate that, for the coding of an image sequence, 1) most AVQ algorithms achieve distortion much lower than that of nonadaptive VQ for the same rate (about 1.5 bits/pixel), and 2) the GTR algorithm achieves rate-distortion performance substantially superior to that of the prior AVQ algorithms for low-rate coding, being the only algorithm to achieve a rate below 1.0 bits/pixel for our image-sequence testing data.