When is bit allocation for predictive video coding easy?

This paper addresses the problem of bit allocation among frames in a predictively encoded video sequence. Finding optimal solutions to this problem potentially requires making an exponential number of calls to the encoder. To better understand the structure of the rate-distortion data output by video encoders, a simple model of a sequentially encoded autoregressive Gaussian random field is theoretically investigated. The rate-distortion data for the model exhibits an additive-separability property, i.e. the rate can be decomposed into a sum of independent functions of single distortion variables. This property implies the near-optimal behavior of a non-backtracking steepest-descent (SD) based bit allocation algorithm. The SD algorithm when applied to video coding produces near-optimal solutions by making a linear number of calls to the encoder. Results are presented for MPEG-2 encoding of standard video sequences.