A novel hybrid technique for discrete rate-distortion optimization with applications to fast codebook search for SVQ

A key part of any efficient source coder involves the optimal allocation of bit rate among a discrete set of competing quantization choices, as employed in the selected coding paradigm. This can be classified under the general label of budget-constrained discrete optimization, with coding applications including optimal bit allocation in scalar or vector quantizer based frameworks, entropy-constrained quantization frameworks, and codebook search for scalar-vector quantization (SVQ). For this class of problems dynamic programming (DP) methods (such as the Viterbi algorithm) provide the optimal solution. However DP is typically very costly computationally. An alternate technique to solving this class of problems uses Lagrange multipliers. This approach is much more efficient than DP but cannot guarantee optimality in general as it limits itself to convex-hull operating points, which may be sparse in many applications. We propose a novel hybrid technique that combines the speed of the Lagrangian approach with the versatility of the DP technique that is aimed at extracting the “best of both worlds”. We present an application of our hybrid technique to the codebook search problem for SVQ, demonstrating significantly improved speed over the previously proposed DP-based search methods while mitigating the suboptimality of the Lagrangian based approach