MINMAX bit allocation for quantization-based video coders

Ringenburg et al. developed MultiStage, a bit-allocation algorithm for embedded video coders, that generates near-constant quality sequences. In this work, we show how the algorithm can be applied to quantization-based coders, and implement it for H.263. We also describe a novel approach for block-level bit allocation for H.263, cast as a variation on the multiple-choice knapsack problem, and show how to solve it efficiently with dynamic programming. Our results show that very stable quality can be achieved using relatively few coding iterations, with very little sacrifice in mean distortion.