Technical Report CS-2005-08

Title: A Multigrid Approach to the 1-D Quantization Problem
Authors: Yair Koren, Irad Yavneh, Alon Spira
Abstract: A multigrid framework for the 1-D (scalar) 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 with machine accuracy is reached in a matter of several iterations and the need for traditional stopping criteria for the process is alleviated. In addition, the proposed method often achieves better local minima than other quantization methods such as classical Lloyd-Max and LBG. 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.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2005
To the main CS technical reports page

Computer science department, Technion