Optimal trellis-based buffered compression and fast approximations

We formalize the description of the buffer-constrained adaptive quantization problem. For a given set of admissable quantizers used to code a discrete nonstationary signal sequence in a buffer-constrained environment, we formulate the optimal solution. We also develop slightly suboptimal but much faster approximations. These solutions are valid for any globally minimum distortion criterion, which is additive over the individual elements of the sequence. As a first step, we define the problem as one of constrained, discrete optimization and establish its equivalence to some of the problems studied in the field of integer programming. Forward dynamic programming using the Viterbi algorithm is shown to provide a way of computing the optimal solution. Then, we provide a heuristic algorithm based on Lagrangian optimization using an operational rate-distortion framework that, with computing complexity reduced by an order of magnitude, approaches the optimally achievable performance. Our algorithms can serve as a benchmark for assessing the performance of buffer control strategies and are useful for applications such as multimedia workstation displays, video encoding for CD-ROMs, and buffered JPEG coding environments, where processing delay is not a concern but decoding buffer size has to be minimized.