A Caltech Library Service

Quantization as Histogram Segmentation: Optimal Scalar Quantizer Design in Network Systems

Muresan, Dan and Effros, Michelle (2008) Quantization as Histogram Segmentation: Optimal Scalar Quantizer Design in Network Systems. IEEE Transactions on Information Theory, 54 (1). pp. 344-366. ISSN 0018-9448. doi:10.1109/TIT.2007.911170.

See Usage Policy.


Use this Persistent URL to link to this item:


An algorithm for scalar quantizer design on discrete-alphabet sources is proposed. The proposed algorithm can be used to design fixed-rate and entropy-constrained conventional scalar quantizers, multiresolution scalar quantizers, multiple description scalar quantizers, and Wyner–Ziv scalar quantizers. The algorithm guarantees globally optimal solutions for conventional fixed-rate scalar quantizers and entropy-constrained scalar quantizers. For the other coding scenarios, the algorithm yields the best code among all codes that meet a given convexity constraint. In all cases, the algorithm run-time is polynomial in the size of the source alphabet. The algorithm derivation arises from a demonstration of the connection between scalar quantization, histogram segmentation, and the shortest path problem in a certain directed acyclic graph.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2008 IEEE. Reprinted with permission. Manuscript received October 19, 2004; revised September 15, 2007. [Posted online: 2008-01-04] The material in this paper was presented at The Data Compression Conference, Snowbird, UT, March 2002. The authors are enormously grateful to anonymous reviewer A, whose detailed and insightful suggestions improved this document significantly.
Subject Keywords:Optimal design, multiple descriptions, multiresolution, scalar quantizer, successive refinement, Wyner–Ziv
Issue or Number:1
Record Number:CaltechAUTHORS:MURieeetit08
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9584
Deposited By: Archive Administrator
Deposited On:11 Feb 2008
Last Modified:08 Nov 2021 21:00

Repository Staff Only: item control page