Trellis-based R-D optimal quantization in H.263+

We describe a trellis-based algorithm which enables R-D optimum quantization decisions in the H.263+ video coding standard. The use of the trellis allows the quantization decisions for all coefficients in a block to be made jointly, and contrasts with more commonly used R-D optimizations which operate on one coefficient at a time. Experiments conducted using H.263+ for video coding rates of 40-50 kbps show an average improvement of 3.5% in bit rate, or equivalently 0.17 dB in PSNR, relative to implementations which follow the International Telecommunications Union (ITU) Test Model specifications in making quantization decisions.