A Multigrid Approach to the Scalar Quantization Problem

Abstract

A multigrid framework for the one-dimensional (scalar) fixed-rate quantization problem is presented. The framework is based on the Lloyd-Max iterative process, which is a central building block in many quantization algorithms. This process iteratively improves a given initial solution and generally converges to a local minimum of the quantization distortion. Contrary to the classical Lloyd-Max process, the convergence of the multigrid algorithm is practically independent of the number of representation levels sought. Using this approach, a local minimum is reached at the cost of just a few Lloyd-Max iterations. The complexity of the proposed method is O(n) operations for the continuous case and 3N+O(n) for the discrete case, where n is the number of representation levels sought and N is the size of the discrete probability density function. In addition to its independent attributes, this work is a precursor to the more important vector quantization problem, for which a multiscale framework is also being developed.