Development of a rate-distortion optimized encoder control algorithms for hybrid video coders.

The rate-distortion efficiency of today's hybrid video coders (see Fig. 1) is based on a sophisticated interaction between various motion representation possibilities, waveform coding of differences, and waveform coding of various refreshed regions. Hence, a key problem in high compression video coding is the operational control of the encoder. This problem is compounded by the widely varying content and motion found in typical video sequences, necessitating the selection between different representation possibilities with varying rate-distortion efficiency. This research project addresses the problem of video encoder optimization and identifies its consequences on the compression architecture of the overall coding system.

The proposed solutions are based on Lagrangian optimization techniques trying to answer the crucial question: "What part of the video signal should be coded using what method and parameter settings?"

The specification of most video coding standards including H.262 / MPEG-2 Visual, H.263, MPEG-4 Visual, and H.264 / MPEG-4 AVC provide only the bit-stream syntax and the decoding process in order to enable interoperability.  The encoding process is left out of the scope to permit flexible implementations.  However, the development of an efficient encoder control is a key problem in video coding. This issue became even more important with the new H.264 / MPEG-4 AVC video coding standard, since it provides much more coding options (e.g. 259 possibilities to partition a macroblock for motion-compensated prediction) compared to older standards. For the encoding of a video source, a variety of coding parameters such as macroblock modes, sub-macroblock modes, motion vectors, reference picture indices, intra prediction modes, and transform coefficient levels has to be determined.  The chosen values determine the rate-distortion efficiency of the produced bit-stream for a given video coding standard. The coding parameters are often predicted using already transmitted of preceding blocks inside the picture and/or coded using conditioned entropy codes.  Moreover, the motion-compensated prediction introduces a temporal dependency because reference is made to prior decoded pictures. Because of these spatial and temporal dependencies, a global optimization is virtually not possible. Instead, the selection of the coding options is separated into smaller sub-problems, and already determined coding parameters are considered as given. The selection of a coding parameter p proceeds by minimizing a Lagrangian cost measure D(p)+l×R(p) with D(p) and R(p) being the distortion and the number of bits, respectively, that are associated with a coding mode p.

For error-free transmission, the distortion D can be directly determined at the encoder side, while for error-prone transmission, the distortion of the decoded video sequence is dependent on the actually occurring transmission errors. Consequently, the distortion term D(p) is replaced by the corresponding expectation value E{ D(p) }.  For the Lagrangian coder control for error-prone transmission channels, the expected decoder distortion is determined on the basis of several decoder simulations with different error characteristics.

The development of the Lagrangian coder control led to a change of the encoding strategy that is used in standardization. It now represents the recommended technique for H.263, MPEG-4 Visual, and H.264 / MPEG-4 AVC. Moreover, the increased coding efficiency of the highly flexible H.264 / MPEG-4 AVC standard is strongly connected to Lagrangian encoder control techniques.