Conditional Entropy-Constrained Vector Quantization: High-Rate Theory and Design Algorithms

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