29.1.1 Digital Video and Need for Compression

Digital video data consist of a series of images captured using a camera or artificially generated (e.g., computer-generated movies). Figure 29.1a shows four images of a color video sequence captured at 30 frames per second (fps). Each image of color video consists of a luminance (also referred to as luma and denoted by Y) component and two chrominance components (also referred to as chroma and denoted by U and V). Since the human eye is more sensitive to luma than chroma, the chroma components are typically subsampled to lower the data rate. Figure 29.1b shows YUV 4:2:0 format image where the U and V chroma components are quarter the size of luma component. Consumer video is predominantly in the 4:2:0 format with 8 bits per pixel. Higher chroma resolution (no chroma subsampling) and higher bit depth (10-bits or more) are typically used in production quality video generated in studios. Video can be captured in one of two formats—progressive or interlaced. In progressive format all lines in the image are scanned from top to bottom, whereas in interlaced format odd lines in the image are scanned first followed by even lines. The odd lines are called the top field and the even lines are called the bottom field.

Raw digital video requires a lot of data to be stored or transmitted. For example, a 1920 × 1080 (1080p) high-definition (HD) YUV 4:2:0 video sequence with 8 bits per pixel at 60 fps generates around 1.5 Gbps data which are an order of magnitude more than the bandwidth currently supported on broadband networks (~1–10 Mbs). A movie of 90 min would generate around 1 Tbyte of data which are again an order of magnitude more than the capacity available on common storage discs such as Blu-ray (50 GB capacity). Hence, video compression is essential for transmitting or storing digital video.

29.1.2 Video Compression Basics

The goal of video compression is to encode digitized video using as few bits as possible while maintaining acceptable visual quality. Video compression is achieved by removing redundancies in the video signal. Several types of redundancies exist in video signals; spatial, perceptual, statistical, and temporal redundancies.

29.1.3 Basic Video Coding Architecture

A common approach in video coding is to combine motion estimation/compensation, spatial prediction, transform, quantization, and entropy coding into a hybrid scheme to exploit all forms of redundancies in video sequences. A video coding architecture that forms a basis of most of the existing video coding standards is shown in Figure 29.8.

Pictures are coded in either of the two modes—INTER or INTRA. In INTRA-coding, the current picture is encoded without any relation to the previous picture. Spatial prediction can be used to predict blocks of pixels from neighboring pixel values. In INTER coding, the current image is predicted from neighboring pictures using block motion compensation and the difference between the current image and the predicted image is encoded. Note that INTER coding requires that a copy of the neighboring pictures be stored in the frame buffer. The first picture in the video sequence is coded in the INTRA-mode to initialize the frame buffer. There are two types of INTER pictures—P picture and B picture as shown in Figure 29.9. P pictures are coded with respect past pictures where as B pictures are coded with respect to both past and future pictures.

The basic unit of data operated on is called a macroblock (MB) and are the data (both luma and chroma components) corresponding to a block of 16 × 16 pixels. The input image is split into disjoint MBs and the processing is done on an MB basis. In INTER MBs, ME is performed on the MB to be encoded and motion vector (MV) is estimated between the current picture and neighboring picture for the MB to be encoded. ME is typically done using only the luma component of the video images. For chroma components, the luma MV is appropriately scaled to take care of the different spatial resolutions of the luma and chroma components before it is used. The motion compensation prediction error is calculated by subtracting each pixel in the MB with its motion-shifted counterpart in the neighboring picture. In INTRA-MBs, when spatial prediction is used, the prediction error is calculated by subtracting each pixel in MB from its spatial prediction from neighboring pixel values.

2D DCT is applied on prediction error (if spatial prediction or ME is used) or on original MB (if no prediction is used). The resulting DCT coefficients are then quantized. Depending on the quantization step size, this will result in a significant number of zero-valued coefficients. To efficiently encode the DCT coefficients which remain nonzero after quantization, the DCT coefficients are typically zig-zag scanned and run-length encoded. The run-length-encoded DCT coefficients and the MVs are variable length encoded before transmission. Arithmetic coding can also be used instead of VLC.

The decoder uses a reverse process to reproduce the MB at the receiver. After entropy decoding the received video bitstream, the pixel values of the prediction error are reconstructed by inverse quantization and inverse DCT. The spatially predicted pixels or the motion-compensated pixels from the neighboring picture contained in the frame buffer are added to the prediction error to reconstruct the particular MB transmitted. All MBs of a given picture are decoded and the whole picture is reconstructed.

29.1.4 Early Video Coding Standards

29.2.1 Coding Tools in H.264/AVC

The structure of H.264/AVC codec is similar to one shown in Figure 29.8. However, every coding block in H.264/AVC is improved by adopting new coding tools. This subsection highlights some of those tools.

29.2.2 Encoder Optimization and SEI

The H.264/AVC standard defines only the decoding process as normative part. However, it also provides a guideline and reference software for the encoder [16], which describes optimized mode selection scheme, adaptive rounding control, and so on. In addition, SEI can be used to improve the performance, especially for error resilience coding.

H.264/AVC provides various coding modes. For example, each MB can have intra or inter prediction type. Each prediction type consists of several modes as described in Section 29.2.1. Therefore, it is important to choose the optimal coding mode to improve coding efficiency, that is, to achieve less distortion at lower bitrate. The optimal solution can be found by using the Lagrangian optimization [17,18]. In general, an H.264/AVC encoder tries to calculate the actual bitrate and distortion incurred by each prediction mode, and calculates the rate-distortion (RD) cost as

where L and λ are Lagrange cost and Lagrange multiplier, respectively, D denotes sum of squared error (SSE), and R represents bitrate. The optimal Lagrange multiplier can be selected by taking derivative of distortion and bitrate of the compressed video as a function of quantization step size [19,20]. By exactly measuring bitrate and distortion for each prediction mode, the optimal coding mode can be selected.

Adaptive rounding control [21] is another encoding tool that improves coding efficiency by selecting a rounding offset value during the quantization process. The rounding offset value can be selected to adjust a deadzone size, and the adaptive rounding control accumulates statistics to find optimal offset value. This provides additional compression when the operating bitrate is very high. Various fast ME and fast mode decision algorithms are supported as well in the reference software.

SEI can also be used to improve the performance of H.264/AVC in different environments. SEI is a nonnormative part, which means that it is not mandatory for a decoder to support. However, an encoder can transmit information in the SEI, so that a decoder can support additional features. For example, spare picture SEI defines alternative reference frame to increase error resilience. Subsequence SEI enables UEP by defining hierarchical picture structure. Film grain SEI provides information to emulate film grain noise in an input sequence, so that similar noise can be reproduced at the decoder after coding the sequence without noise.

29.2.3 Profile Information and Performance Analysis

Profiles are defined to specify sets of coding tools used in different applications. A decoder can then conform to a particular profile without supporting all tools in H.264/AVC. In the first version of the standard, three profiles were defined; baseline, main, and extended profiles. Figure 29.14 shows the tools included in these profiles. Baseline profile includes less complex tools, for applications with limited resources, such as mobile applications.

Later, Fidelity Range Extension work [22,23] was added, which results in High, High 10, High 4:2:2, High 4:4:4 profiles. High profile, which includes ABT and quantization matrix in addition to the tools in main profile, is provided for the applications with less restriction in computation, memory, and power, such as HD broadcasting and storage like Blu-ray Disc. The other profiles are for applications requiring very high quality by supporting, for example, 10 bit per pixel, 4:2:2 and 4:4:4 or RGB color formats, lossless coding.

Similarly, levels are also specified for different application by defining maximum bitrate, buffer size, frame size, memory bandwidth, maximum MV range, and so on. For example, level 1 can only support resolutions up to 128 × 96 at 30.9 fps with 8 stored reference frames, and level 5.1 can support up to 4096 × 2048 at 30 fps with 5 stored reference frames.

Various studies have also been conducted to assess the performance of H.264/AVC compared to previous standards such as MPEG-2 and MPEG-4 in terms of bitrate reduction and visual quality. The verification test performed inside MPEG [9] reveals that H.264/AVC can achieve more than 50% of bitrate savings with better subjective quality. Figure 29.15 shows an example, where the Crew sequence is compressed using MPEG-2 at 10 Mbps, and H.264/AVC at 6 Mbps. H.264/AVC provides significantly better subjective quality compared to MPEG-2 with reduced blocking artifact and preservation of details in the scene. Another evaluation of H.264/AVC visual quality is also available in [24].

29.3.1 H.264/SVC Overview

H.264/SVC inherits all the features of H.264/AVC, which enable the production of a highly efficient video bitstream. Moreover, it is equipped with added features that support scalability by taking advantage of lower-layer signals in the higher layer encoding to minimize the redundant signal included in a compressed stream. There are mainly three types of scalability supported in the H.264/SVC standard: Temporal, spatial, and SNR scalability. In addition, they can be combined flexibly to provide multiple forms of scalability in a single stream. The coding efficiency of each scalable coding can be found in [25] and [26].

29.3.2 Other H.264/SVC Features

There are other improvements for EL encoding in H.264/SVC besides inter-layer prediction methods. Some of them are briefly covered in this subsection.

29.3.3 H.264/SVC Bitstream Structure

Table 29.3 shows the important NAL units in H.264/SVC with their NAL unit types. In addition to the NAL units (1, 5, 7, and 8) in H.264/AVC, the H.264/SVC standard defines new NAL units to distinguish EL and BL and provides necessary information for scalable video decoding. They include prefix NAL unit, subset SPS, and coded slice extension. The coded slice extension has all MB parameters and data in the EL slice and the subset SPS has sequence-level parameters specific to EL. The prefix NAL unit is appended to the coded slices of BL, so that the information necessary for scalable video decoding can be assigned even to BL slices. Figure 29.20 illustrates the structures of NAL units. The NAL units of H.264/AVC consist of 1-byte header, which signals the NAL unit type and NAL unit payload. However, the prefix NAL unit and the coded slice extension have 3-byte NAL unit header extension between NAL unit header and payload, in which D, Q, and T IDs of a slice are signaled. The values of D, Q, and T represent spatial, quality, and temporal resolution of a slice and make it easy for a decoder to detect and extract the target layer that the decoder wants to display. It should be noted that the coded slice extension includes the payload of prefix NAL unit inside its payload.

With the NAL units introduced in H.264/SVC, the generation of a SVC stream from multiple AVC streams and an AVC stream from one SVC stream can be completed simply by adding and removing new NAL units. For example, Figure 29.21 shows AVC, SVC, and extracted AVC stream formats. Suppose that a SVC stream is generated from two simulcast AVC streams. It can be done by adding the Prefix NAL units to coded slices of one AVC stream, converting SPS and coded slice of the other AVC stream to the subset SPS and coded slice extension, respectively and finally arranging them in the correct order. The AVC stream can be recovered again by identifying and removing SVC NAL units.

29.3.4 H.264/SVC Profiles

Three profiles are defined for H.264/SVC; Scalable Baseline, Scalable High, and Scalable High Intra profile. Scalable Baseline profile is defined on top of AVC Baseline profile. AVC base layers in the bitstreams conforming to this profile should be compliant to AVC baseline profile. For ELs, several coding tools allowed in AVC High profile, such as B picture, CABAC and 8 × 8 transform, are supported. However, interlaced, picture-adaptive field/frame (PICAFF) and MB adaptive field/frame (MBAFF) coding are not allowed. The biggest constraint for ELs is the scaling factor in spatial scalable coding. The scaling factor in SVC Baseline profile is limited to 2 and 1.5. However, there is no restriction to SNR and temporal scalable coding.

Scalable High profile is defined on top of AVC High profile. AVC base layers in the bitstreams conforming to this profile are compliant to AVC High profile. Most of the coding tools in AVC High profile are supported for ELs. Most importantly, arbitrary scaling factors other than 2 and 1.5 are supported for spatial scalable coding in SVC High profile. Scalable High Intra profile is defined for professional applications such as high-quality movies. The difference with Scalable High profile is that it uses only IDR coding for all layers.

29.4.1 H.264/MVC Overview

H.264/MVC, which is extended from the H.264/AVC standards, has been designed to support efficient coding of multiple views into a single bitstream. Figure 29.22 shows the overall structure of a H.264/MVC system. The temporally synchronized videos from multiple cameras are fed into the H.264/MVC encoder to be coded into a single bitstream. Based on the fact that spatially neighboring pictures are correlated, the encoder saves bits required to encode additional views using so-called interview prediction. The coded stream is decoded and displayed by the H.264/MVC decoder in several ways depending on application. For FVV applications, the decoder decodes the desired view only, that is, target view, among multiple views and can switch the target view whenever necessary. For 3D video application, it is also possible to decode stereo views.

Multiple camera sources can be encoded using various prediction structures, which might depend on camera array size and structures, for example, parallel or circular. Figure 29.23 depicts an exemplary prediction structure in the case of stereo-view encoding, where left view is an AVC base view that is always encoded independently. Figure 29.23a is the simplest way that encodes all views independently without interview prediction. However, as shown in Figure 29.23b and (c), the coding efficiency is improved by allowing nonbase views to be predicted from neighboring views for anchor (I or P) pictures, or both anchor and nonanchor pictures (B), respectively. In general, the interview prediction is more effective for anchor pictures than for nonanchor picture. The performance of interview prediction is well studied in [28].

The same NAL units in Table 29.3 are used for H.264/MVC as well, although their contents are quite different from those for H.264/SVC. For example, the prefix NAL unit and coded slice extension stream have NAL unit header extension between NAL unit header and payload. However, the NAL unit header extension in MVC has different syntax elements such as view ID and interview flag as shown in Figure 29.24. The coded slice extension in MVC is the same to the coded slice (nal_unit_type = 1 or 5) except for the reference picture list generation process due to interview prediction. It means that there is no MB-level change like inter-layer prediction in SVC for enhancement view encoding. The interview prediction is simply realized by adding reconstructed neighboring view pictures in the reference list of the current view. Therefore, the H.264/AVC encoder can be easily extended to support multiview coding.

There are two profiles defined for in H.264/MVC, namely, Multiview High profile and Stereo High profile. The main difference between two profiles is the number of views in a stream. Multiview High profile, which allows more than two views, is defined on top of the AVC High profile with some restrictions. For example, the interlaced picture coding tools including PICAFF and MBAFF are not supported in this profile. The AVC base view in the Stereo High profile is compliant to the AVC High profile as well.

However, the interlaced picture coding tools can be supported in the Stereo High profile, which allows only up to two views.

29.4.2 Stereo 3D Video Coding via H.264/AVC SEI Messages

There are two H.264/AVC SEI messages for stereo 3D video, stereo video information SEI and frame packing arrangement SEI. They are used to support stereo 3D video in H.264/AVC without any change of actual encoding and decoding process. Specifically, they inform a decoder how the decoded picture is generated from two pictures, and the decoder rearranges the decoded picture based on this information for display purpose.

Figure 29.25 describes the overall structure of a 3D video system of H.264/AVC with SEI messages. In the encoder side, temporally synchronized left and right view sequences go through the down converter, by which each picture of left and right view sequences is down-sized by 2 based on the SEI message. The down-sized left and right views are composed into a single picture and coded by an H.264/AVC encoder. In the decoder side, the decoded picture by an H.264/AVC decoder is decomposed into left and right views and both views are up-converted into the original size based on the SEI message. The stereo information and frame packing arrangement SEI messages are similar as both follow the structure in Figure 29.25; however, they define different down- and up-conversion formats. One of formats in the stereo information SEI message is illustrated in Figure 29.26, for which the interview prediction can be realized. As shown in Figure 29.27, by encoding each field separately and allowing bottom field to refer top field, we can have the same effect as the interview prediction in H.264/MVC, with the reduced resolution.

The disadvantage of 3D video by the SEI messages is that it reduces the resolutions of both views by half. However, it is very attractive because it is compatible to existing H.264/AVC codecs and infrastructures. Using the SEI messages, stereo 3D video can be brought to home via existing devices like DVD and Blu-ray players and 3D display with minimal efforts. There is also standardization activity to support full resolution stereo 3D video with the similar approach [29].

29.4.3 MPEG 3D Video

Although the H.264/MVC standard reduces the redundancy by using interview prediction, the amount of data to be stored or transmitted is still very large especially when many views are captured and coded. Improvements to the interview prediction in H.264/MVC are currently being studied. For instance, the illumination and focus mismatch compensation method was proposed in [30], by which the different illumination conditions and focal lengths between a target view and a reference view are compensated for improved interview prediction. In [31] and [32], the interview prediction methods using view interpolation were proposed. In these methods, a target view is synthesized first based on neighboring views and this estimated target view is used as a reference for interview prediction while encoding the target view. The differential signal between the target view and the estimated target view is coded in a stream.

The idea of view interpolation is also applied to a new 3D video format of view plus depth [33]. Figure 29.28 illustrates the overall structure of a 3D system with a view-plus-depth format. The encoder encodes two views and depths into the view-plus-depth format. The decoder not only decodes coded views and depths but also synthesizes any intermediate view using depth image-based rendering (DIBR) technique [34]. Additional data could also be sent in a stream so that the decoder can have better quality of synthesized intermediate view. This 3D video representation is expected to be the most efficient way for multiview video application. However, there are several issues to be addressed for this system.

First, in the case that a ground-truth depth map is not available, the generation of high-quality depth map is the most fundamental issue. While there exist many depth map estimation methods in the literatures [35,36], these methods need to be evaluated in terms of synthesized views’ quality to develop the best depth map estimation method for this system. Regardless of whether depth map is ground truth or not, an efficient coding method for depth map should be developed. Since depth map has different characteristic from view picture, conventional video compression techniques may not be efficient. Exploiting the specific characteristics of depth map can enable higher coding efficiency. Second, it should be guaranteed that a view synthesis method employed always generates acceptable intermediate views. The quality of synthesized views will depend on the quality of coded views and depth maps, and the quality of coded and synthesized views should have similar quality. However, when there are large occluded areas between two coded views, it is not easy to synthesize intermediate views as good as coded views. To resolve this issue, the study on the additional data and its transmission method to improve synthesized views’ quality at minimum overhead is also essential [37].

The standardization effort for the 3D video coding with view-plus-depth format is being led by the ISO/IEC MPEG organization. They recently issued call for proposal [38] with common test sequences and environment. The primary goal is to define the data format and coding technology to enable high-quality reconstruction of coded and synthesized views for both stereoscopic 3D display and auto-stereoscopic multiview displays. All the issues mentioned in the above are expected to be addressed in the standard.

29.5.1 Coding Block Structure

HEVC is intended for larger resolutions and higher frame rates. Accordingly, HEVC uses larger “macroblocks (MB)” compared to H.264/AVC. In HEVC, the largest coding unit (LCU) is 64 × 64 pixels, which is 16 times larger than the 16 × 16 pixel MB used in H.264/AVC. Using a large coding unit helps to improve coding efficiency, particularly for high resolutions where many pixels may share the same characteristics. The largest coding unit can be divided into smaller coding units (CU) using a quadtree structure as shown in Figure 29.29. A split flag is transmitted to indicate whether a CU should be divided into four smaller CUs. The smallest coding unit (SCU) allowed in HEVC is 8 × 8 pixels. An additional feature in HEVC is that within an LCU, there can be a mixture of inter and intra coding units. The CU can be further divided into prediction units (PU). The PU within a coding unit will undergo the same form of prediction (either all inter or all intra). The allowed PU sizes within a CU depend on whether the CU is inter- or intra predicted. Asymmetric motion partitions (AMP) are allowed for inter predicted PU.

29.5.2 Inter Prediction

Similar to H.264/AVC, quarter-pixel resolution MVs are supported in HEVC. HEVC uses a larger 8-tap DCT interpolation filter (DCTIF) that operates directly on the integer pixels rather than the two step 6-tap approach used in H.264/AVC. In addition, advanced motion vector prediction (AMVP) is used to signal the MV data. Compared to H.264/AVC, more neighbors are used for MV prediction. To signal skip or direct mode, merge mode is used, where multiple neighbors are used to predict the MVs and reference index.

29.5.3 Intra Prediction

Depending on the PU size, up to 34 directional modes are used for intra prediction of luma pixels. In addition, there are separate planar and DC modes. Depending on the prediction mode, intrasmoothing is applied to the reference pixels. For chroma pixels, four directional modes can be used, one of which can be the same as the luma mode. In addition, luma-based chroma prediction (LM chroma) can be used where chroma intra prediction is performed using the reconstructed luma pixels.

29.5.4 Transform

To support the larger resolutions, HEVC uses transforms from 4 × 4 up to 32 × 32. For a given coding unit, the transform sizes are signaled using a residual quadtree (RQT). For example, a CU of size 16 × 16 can be split into 16 4x4 transforms using a quadtree of depth 2.

For 4 × 4, based on intramode, a discrete sine transform (DST) is used for certain prediction modes. Nonsquare transforms (NSQT) with sizes 4 × 16/16 × 4, 8 × 32/32 × 8 are allowed for residual of inter prediction. An adaptive scan order is used for intrapredicted coefficients to map them from the 2-D transform to the 1-D set of coefficients to be coded by the entropy coder.

29.5.5 Loop Filters

A deblocking filter is applied to the 8 × 8 edges. Similar to H.264/AVC there is both a strong filter, which is applied to 3 pixels on either side of the edge, and a weak filter, which is applied to 2 pixels on either side of the edge. The chroma filter affects 1 pixel on either side of the edge.

Two additional loop filters shown in Figure 29.30 are used in HEVC: sample adaptive offset (SAO) and adaptive loop filter (ALF). After the deblocking filter, SAO is applied on a pixel basis based on the neighboring information. There are two methods of determining the offset with SAO: band offset and edge offset. In band offset, the size of the offset is determined based on the magnitude of the pixel. In edge offset, a two-point gradient is taken around the pixel and the difference dictates the offset that is to be added to the pixel. SAO can be enabled and disabled on an LCU basis, and is signaled using a quadtree.

ALF is an adaptive FIR Wiener filter, which is applied after SAO. The number of filters taps in ALF can change for each slice; within each slice, there are sixteen sets of coefficients. There are two methods of selecting the coefficients: region-based and block-based. Region-based ALF involves breaking a frame into sixteen regions (i.e., dividing the frame into four in both vertical and horizontal directions). A coefficient set can be assigned to each region and all pixels within each region will use the same coefficient set. In block-based ALF, the coefficient set is selected based on the local characteristics of a given block of pixels. A separate filter is used for the chroma components. ALF can be enabled and disabled using the existing CU quadtree of the coding block structure.

29.5.6 Entropy Coding

Similar to H.264/AVC, HEVC uses context adaptive binary arithmetic coding (CABAC). However, improvements have been made to CABAC to enable higher throughput. This includes changes to the binarization and context selection of various syntax elements such as coefficient level, to reduce the number of context coded bins as well as overall number of bins. Bins are also reordered such that context coded bins with similar contexts are grouped together to enable parallel context processing, and bypass bins are grouped together to enable higher throughput.