Rate-distortion optimized multipass video encoding with application to MPEG-4

In this paper we propose a rate-distortion optimized multipass algorithm for video encoding. The problem of dependent quantization in a hybrid coding framework is addressed by constructing a trellis from the exponentially growing search tree which is then searched using a Lagrangian cost function. To avoid exponential growth, states with similarly distorted reference frames are merged based on the assumption that similar rate-distortion behavior will result for future frames. The goal is to select an optimal quantizer for each frame such that the overall R-D performance is optimized. The algorithm is applied to MPEG-4 SP and typical average PSNR gains of 0.3 dB are achieved. A comparison with the DivX 5.2 codec shows PSNR gains of up to 2 dB.