The computational complexity issue is critical for present and future video applications implemented by relatively new video coding standards, such as the H.264/AVC (Advanced Video Coding), which has a large number of coding modes. One of the main reasons for the importance of providing an efficient complexity control in video coding applications is a strong need to decrease the encoding/decoding computational complexity, especially when the encoding and/or decoding devices are resource-limited, such as portable devices. In turn, efficient complexity control enables reducing the video coding processing time and enables saving power resources during the encoding and/or decoding process. Since the recent dramatic progress in the development of multimedia technologies has made portable devices widespread everywhere, especially in order to provide or receive real-time video contents, the need to enhance the computational complexity control in video coding applications is expected to be further significantly increased as a function of the dramatic increase in the mobile/portable device penetration into the every-day life environment. In this chapter, the authors perform a comprehensive review of the recent advances in computational complexity techniques for video coding applications. This chapter will not only summarize the recent advances in this field, but will also provide explicit directions for the design of the future complexity-aware video coding applications.
TopBackground
The H.264/AVC (ISO/IEC MPEG-4 Part 10) video coding standard (Wiegand & Sullivan, 2003; Wiegand, et al., 2003a, 2003b), which was officially issued in 2003, has become a challenge for real-time video applications. Compared to others standards, it gains about 50% in bit-rate, while providing the same visual quality. In addition to having all the advantages of MPEG-2, H.263 and MPEG-4, the H.264 video coding standard possesses a number of improvements, such as the Content-Adaptive-Based Arithmetic Coder (CABAC), enhanced transform and quantization, prediction of Intra macroblocks (spatial prediction), and others. H.264 is designed for both Constant Bit-Rate (CBR) and Variable Bit-Rate (VBR) video coding, useful for transmitting video sequences over statistically multiplexed networks (e.g., the CBR statistical multiplexing is common in terrestrial broadcast applications, whereas researchers usually prefer the VBR multiplexing). This video coding standard can also be used at any bit-rate range for various applications, varying from wireless video phones to High Definition Television (HDTV) and Digital Video Broadcasting (DVB). In addition, H.264 provides significantly improved coding efficiency and greater functionality, such as rate scalability, Intra-prediction and error resilience in comparison with its predecessors, MPEG-2 and H.263. However, H.264/AVC is much more complex in comparison to other coding standards and to achieve maximum quality encoding, high computational resources are required (Grois, et al., 2010c, 2009; Kaminsky, et al., 2008).
One of the important concepts of H.264/AVC is the separation of the system into two layers, as schematically illustrated in Figure 1: a Video Coding Layer (VCL), providing the high-compression representation of data, and a Network Adaptation Layer (NAL), packaging the coded data in an appropriate manner based on the characteristics of the transmission network (Saponara, et al., 2003; Wiegand, et al., 2003a, 2003b). The basic coding framework defined by the H.264/AVC is similar to the one of previous video coding standards: translational block-based motion estimation and compensation, residual coding in a transformed domain and entropy coding of quantized transform coefficients. Additional tools improve the compression efficiency at an increase of computational complexity cost: e.g., the motion compensation scheme supports multiple previous reference pictures and a large number of different block sizes, from 16x16 up to 7 modes, including 16x8, 8x16, 8x8, 8x4, 4x8, and 4x4 pixel blocks; also, the motion vector field can be specified with a higher spatial accuracy (quarter or eighth-pixel resolution instead of half pixel) and a Rate-Distortion (RD) Lagrangian technique (Sullivan & Wiegand, 1998) optimizes both motion estimation and coding mode decisions (Saponara, et al., 2003).
Figure 1. Structure of H.264/AVC video encoder (Wiegand, et al., 2003b)
The computational complexity issue is critical for the present and future real-time video applications using the H.264/AVC standard, which has a large number of coding modes. In conventional advanced video coding applications, these coding modes are not fully selected at the time of video sequence encoding, since selecting all possible coding modes leads to a significant increase of the overall computational complexity. The greater computational complexity is, the larger processing (power) resources are required; the power issue becomes critical for wireless applications. On the other hand, not selecting all possible coding modes leads to an increase of the encoded video sequence distortion, and in turn to a decrease of the overall video quality.
It should be noted that in order to change the overall computational constraints, the method needs to be robust. The difference in the overall video sequence quality, related to an optimal and constant computational complexity and bit allocations, defines the level of robustness (Grois, et al., 2010c).