A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
The performance of optimum vector quantizers subject to a conditional entropy constraint is studied in this paper. This new class of vector quantizers was originally suggested by Chou and Lookabaugh. A locally optimal design of this kind of vector quantizer can be accomplished through a generalization of the well-known entropy-constrained vector quantizer (ECVQ) algorithm. This generalization of the ECVQ algorithm to a conditional entropy-constrained is called CECVQ, i.e., conditional ECVQ. Furthermore, we have extended the high-rate quantization theory to this new class of quantizers to obtain a new high-rate performance bound, which is a generalization of the works of Gersho and Yamada, Tazaki and Gray. The new performance bound is compared and shown to be consistent with bounds derived through conditional rate-distortion theory. Recently, a new algorithm for designing entropy-constrained vector quantizers was introduced by Garrido, Pearlman, and Finamore, and is named entropy-constrained pairwise nearest neighbor (ECPNN). The algorithm is basically an entropy-constrained version of the pairwise nearest neighbor (PNN) clustering algorithm of Equitz. By a natural extension of the ECPNN algorithm we develop another algorithm, called CECPNN, that designs conditional entropy-constrained vector quantizers. Through simulation results on synthetic sources, we show that CECPNN and CECVQ have very close distortion-rate performance. The advantages of CECPNN over CECVQ are that the CECPNN enables faster codebook design, and for the same distortion-rate performance the codebooks generated by the CECPNN tend to be smaller. We have compared the operational distortion-rate curves obtained by the quantization of synthetic sources using CECPNN codebooks with the analytical performance bound. Surprisingly, the theory based on the high-rate assumption seems to work very well for the tested synthetic sources at lower rates. © 1995 IEEE
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
B. Wagle
EJOR
Eric Price, David P. Woodruff
FOCS 2011
Yvonne Anne Pignolet, Stefan Schmid, et al.
Discrete Mathematics and Theoretical Computer Science