Optimization of video encoding for computational complexity reduction and performance improvement


Student thesis: Doctoral Thesis

View graph of relations


  • Hanli WANG

Related Research Unit(s)


Awarding Institution
Award date2 Oct 2007


With the widespread adoption of technologies such as DVD-video, video conferencing and Internet Protocol TeleVision (IPTV), video coding has become an essential component of broadcast and entertainment media. The past two decades have witnessed a great success of the development of video coding standards, such as MPEG-4 and H.264, by introducing several advanced coding techniques. Although the coding efficiency is greatly improved by these leading video coding standards, the computational complexity of video encoding is dramatically increased, which seriously limits these video codecs into real-time applications such as mobile multimedia communications where the processing power and battery life of mobile devices are very limited and scarce resources. Therefore, it is much preferable and sometimes even imperative to reduce the computational complexity of video encoding whilst maintaining the coding efficiency. At the same time, practical limits determined by the transmission environment put constraints on the bit rate and image quality that may be achieved. It is important to control the video encoding process in order to maximize compression performance, namely high compression and/or good image quality, whilst satisfying the practical transmission constraints. To this aim, Rate Control (RC) algorithms, which employ Rate-Distortion (R-D) optimization methods, are developed to maximize image quality subject to transmission bit rate constraints. Practical RC algorithms can be judged according to how closely they approach optimal performance. However, designing a near-optimum RC algorithm can be a very complex problem indeed, especially for the video coding standard H.264 due to the inter-dependency problem between R-D optimization and RC. In order to address the problems mentioned above, several novel optimization techniques are proposed in this thesis to reduce the computational complexity of video encoding and to improve the RC performance. First, the Discrete Cosine Transform (DCT) and Quantization (Q) functions are studied for 8 × 8 DCT based video encoders such as MPEG-4, and three predictive models are proposed to early detect Zero Quantized DCT (ZQDCT) coefficients prior to implementing DCT and Q. Such early detection techniques are useful to avoid redundant DCT and Q operations, and thus the computational complexity of video encoding is reduced. Then, three kinds of optimization techniques are proposed to improve the performance of H.264 encoding, including ZQDCT coefficients prediction technique, reduced-complexity mode decision and Motion Estimation (ME) technique and RC optimization technique, which are described as below. Novel prediction techniques are proposed to early detect ZQDCT coefficients for reducing redundant DCT and Q computations of the H.264 encoder where an integer 4 × 4 DCT is adopted and a scaling multiplication is integrated into the quantiser to avoid divisions for Q. Compared with other algorithms in the literature, the proposed prediction approaches derive more precise and efficient conditions to predict ZQDCT coefficients and reduces more computations for H.264 encoding. A novel algorithm is proposed to jointly optimize ME and mode decision for H.264 encoding. Based on our theoretical analysis of the sufficient condition used to detect all-zero blocks in H.264, adaptive thresholds are derived to early terminate ME and mode decision. Besides the aforementioned early termination technique, the proposed algorithm also introduces temporal-spatial checking, thresholds based prediction and monotonic error surface based prediction methods to skip checking unnecessary encoding modes. Finally, a R-D optimization RC algorithm is presented to improve the H.264 encoding performance. A linear model is investigated to model the Distortion- Quantization (D-Q) relation. Based upon the proposed linear D-Q model and an improved MPEG-4 Q2 rate-quantization model, a close-form solution is deduced to calculate optimal quantization parameters for encoding. The proposed RC algorithm also employs an adaptive initialization scheme which considers the specific content of video sequences.

    Research areas

  • Computational complexity, Video compression, Coding theory