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

Quantization as Histogram Segmentation: Optimal Scalar Quantizer Design in Network Systems,10.1109/TIT.2007.911170,IEEE Transactions on Information Th

Quantization as Histogram Segmentation: Optimal Scalar Quantizer Design in Network Systems   (Citations: 18)
BibTex | RIS | RefWorks Download
We propose a polynomial-time algorithm for optimal scalar quantizer design on discrete-alphabet sources. Special cases of the proposed approach yield opti- mal design algorithms for fixed-rate and entropy-constrained scalar quantizers, multi-resolution scalar quantizers, multiple description scalar quantizers, and Wyner-Ziv scalar quantizers. The algorithm guarantees globally optimal solu- tions for fixed-rate and entropy-constrained scalar quantizers and constrained optima for the other coding scenarios. We derive the algorithm by demonstrat- ing the connection between scalar quantization, histogram segmentation, and the shortest path problem in a certain directed acyclic graph.
Journal: IEEE Transactions on Information Theory - TIT , vol. 54, no. 1, pp. 344-366, 2008
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...The case of scalar source codes for the WZ problem was handled in several papers, e.g., [3] and [4]...

    Avraham Reaniet al. Efficient On-Line Schemes for Encoding Individual Sequences With Side ...

    • ...Globally optimal solutions for the MRSQ design problem under the cell convexity constraint were proposed in [19], [24], [3], [4], and [20] using combinatorial approaches...
    • ...In [9] and [20], an example of finite alphabet source with mean squared error (MSE) distortion, was given for which the optimal MRSQ with two refinement stages must have nonconvex cells (in other words, noncontiguous cells)...
    • ...For general distributions, Effros and Muresan proved in [9] and [20] that convexity of cells in the highest resolution partition does not prevent from optimality when the distortion measure is the squared distance...

    Sorina Dumitrescu. Fast Encoder Optimization for Multi-Resolution Scalar Quantizer Design

    • ...in several papers, e.g. [7] and [8]. In contrast to our case, these schemes operate under...

    Avraham Reaniet al. Efficient On-line Schemes for Encoding Individual Sequences with Side ...

    • ...The main design methods can be classified into two types: generalized Lloyd algorithms [4], [12], [17], [26], [27], and combinatorial algorithms [5]‐[8], [16], [22], [23]...
    • ...These algorithms ensure globally optimal solution under the above convexity constraint. Specifically, in [22], [23] the...

    Sorina Dumitrescuet al. On properties of locally optimal multiple description scalar quantizer...

    • ...Under broad assumptions on the distortion measure, design under the codecell contiguity requirement guarantees a globally optimal code in the SQ case; unfortunately, the optimal MRSQ, MDSQ, and WZSQ with contiguous codecells may achieve performances worse than those of the corresponding optimal codes with non-contiguous codecells [5]...
    • ...possible in an acyclic graph).In the partial RD graph used for optimal ECSQ design, the vertex labels give the topological order of the vertices.In general, ordering the vertices requires O(V + E) steps [5]...
    • ...We focus our description on variable-rate MDSQ design with M =2 (i. e. , 2DSQ) for simplicity.The generalizations to fixed-rate coding, M> 2, MRSQ, and other examples of MDSQs with restricted packet-loss scenarios are extensions of the variablerate M = 2 solution, as described briefly at the end of this work and in full in [5]...
    • ...Due to space considerations, we here exclude a variety of algorithm extensions described in [5].Those extensions include fixed- and variable-rate M-DSQs for M ≥ 2. These codes require an increase in design complexity, but complexity in both cases remains polynomial.In fixed-rate M-DSQ design, the complexity increase arises from the need to constrain the partition sizes, which requires inclusion of the current partition size in the vertex ...
    • ...The above MDSQ discussion assumes that all packet loss scenarios occur with nonzero probability.A variety of codes, including MRSQ, can be described as MDSQs with restricted allowed packet loss scenarios.In [5], we modify the general MDSQ design algorithm for use with arbitrary scenario sets.The discussion treats both an optimized design algorithm for the highly structured packet-loss framework of MRSQ and a general algorithm for arbitrary ...
    • ...The final extension described in [5] treats the problem of fixed- and variable-rate...

    Dan Muresanet al. Quantization as Histogram Segmentation: Optimal Scalar Quantizer Desig...

Sort by: