Optimal data partitioning of MPEG-2 coded video

We analyze the problem of optimal data partitioning of MPEG-2 coded video in an operational rate-distortion context. The optimal algorithm is characterized and shown to have high complexity and delay. A causally optimal algorithm based on Lagrangian optimization is proposed, that optimally solves the problem for intra (I) pictures, while it provides an optimal solution for predicted/interpolated (P/B) pictures when the additional constrains of causal operation and/or low-delay are imposed. A memoryless version of the algorithm, theoretically optimal for intra-pictures only, is shown to perform almost identically but with significantly less computational complexity. Finally, a fast, suboptimal algorithm using slice-based optimization is also proposed, and is shown to perform quite close (within 1 dB) to the causally optimal one