This paper describes a new approach to fixed-rate entropy-constrained vector quantization (FEVQ) for stationary memoryless sources where the structure of codewords are derived from a variable-length scalar quantizer. We formulate the quantization search operation as a zero–one integer optimization problem, and show that the resulting integer program can be closely approximated by solving a simple linear program. The result is a Lagrange formulation which adjoins the constraint on the entropy (codeword length) to the distortion. Unlike the previously known methods with a fixed Lagrange multiplier, we use an iterative algorithm to optimize the underlying objective function while updating the Lagrange multiplier until the constraint on the overall rate is satisfied. The key feature of the new method is the substantial reduction in the number of iterations, in comparison with previous related methods. In order to achieve some packing gain, we combine the process of trellis-coded quantization with that of FEVQ. This results in an iterative application of the Viterbi algorithm on the underlying trellis for selecting the Lagrange multiplier. Numerical results are presented which demonstrate substantial improvement in comparison with the alternative methods reported in the literature.

This paper describes a new approach to fixed-rate entropy-constrained vector quantization (FEVQ) for stationary memoryless sources where the structure of codewords are derived from a variable-length scalar quantizer. We formulate the quantization search operation as a zero-one integer-optimization problem, and show that the resulting integer program can be closely approximated by solving a simple linear program. The result is a Lagrange formulation which adjoins the constraint on the entropy (codeword length) to the distortion. Unlike the previously known methods with a fixed Lagrange multiplier, we use an iterative algorithm to optimize the underlying objective function, while updating the Lagrange multiplier until the constraint on the overall rate is satisfied. The key feature of the new method is the substantial reduction in the number of iterations in comparison with previous related methods. In order to achieve some packing gain, we combine the process of trellis-coded quantization with that of FEVQ. This results in an iterative application of the Viterbi algorithm on the underlying trellis for selecting the Lagrange multiplier. Numerical results are presented which demonstrate substantial improvement in comparison with the alternative methods reported in the literature

In the quantization of a non-uniform source, the entropy coding of the quantizer output can result in a substantial decrease in bit rate. A straight-forward entropy coding scheme faces us with the problem of variable data rate. A solution in a space of dimensionality N is to select a subset of elements in the N-fold cartesian product of a scalar quantizer and represent them with code-words of the same length. For a memoryless source, a reasonable rule is to select the N-fold symbols with the lowest additive self-information. The search/addressing of this scheme can no longer be achieved independently along the one-D subspaces. Fortunately, the selected subset has a high degree of structure which can be used to substantially decrease the complexity. We discuss a method based on dynamic programming to facilitate the search/addressing operations. We build our recursive structure required for the dynamic programming in a hierarchy of steps. This results in several benefits over the conventional trellis-based approaches. Using this structure, we develop efficient rules (based on merging the states) to substantially reduce the search/addressing complexities while keeping the degradation negligible. We choose the quantizer points from a lattice resulting in a higher granular gain in comparison with simply using the cartesian product of a set of scalar quantizers. We introduce a special class of lattices which have a low decoding complexity, and at the same time result in a noticeable granular gain. Examples are given of image coding.