Adaptive vector quantization for the coding of nonstationary sources
Stanley C. Ahalt, James E. Fowler · 1996
Vector quantization (VQ) has long been a popular technique for data compression due in part to results from rate-distortion theory that show that VQ is asymptotically optimal for the coding of a stationary source. The fact most sources of practical interest are, in reality, nonstationary has prompted a search for more general VQ algorithms that are capable of adapting to changing source statistics as the coding progresses. Such algorithms, collectively known as adaptive vector quantization (AVQ), apply often heuristically motivated modifications to VQ to achieve coding schemes that adapt to the changing statistics of nonstationary sources. The work presented here describes a mathematical model of communication systems using AVQ which we believe to be the first of its kind to appear. This model accurately describes the operation of each of the components of an AVQ communication system, is sufficiently general to apply to all reported AVQ algorithms, and allows the classification of these prior algorithms in a taxonomy, which is also presented. An additional contribution of our work is the development of a new AVQ algorithm, called generalized threshold replenishment (GTR), which is based on the explicit consideration of both rate and distortion measures concurrently with the coding of the source. We show in a series of experimental results obtained for both an artificial nonstationary source as well as for real image-sequence data that the GTR algorithm achieves rate-distortion performance superior to that of other reported AVQ algorithms, particularly for low-rate coding.