An Efficient Algorithm for Fast Block Motion Estimation in High Efficiency Video Coding

Introduction

The rapid advancements in the field of Video Coding lead to the evolution of video coding standards. With H.261 and H.263 developed by ITU-T and MPEG-1 and MPEG-4 Visual developed by ISO/IEC, the experts of ITU-T Video Coding Experts Group (VCEG) and ISO/IEC Moving Pictures Experts Group (MPEG) standardization organizations come up with a Joint Collaborative Team on Video Coding (JCT-VC) which prepared the H.265. Taking into account the demands of the market, which expects Ubiquitous HD in all real-time applications, all the Video CODECs fail to meet up with the requirements. H.265 also known as HEVC, the successor of H.264/MPEG-4 AVC, helps to provide the video of same perceptual quality in half the bit rate of AVC. In addition, HEVC also provides support for Ultra HD format and can also help to achieve Ubiquitous HD. A few notable applications of HEVC includes Broadcasting of High Definition (HD) TV signals over the satellite, cable and other terrestrial transmission systems, Video Content Acquisition system, Security Applications, Blue-Ray Discs, Real-time applications, Video Conferencing and Telepresence systems. The development of HEVC is to essentially address all existing H.264/MPEG-4 AVC applications and focus on two important attributes: Increased usage of parallel processing structures and increased resolution of the video sequences (Sullivan, 2012).

The block based video coding merely involves two important processes namely, the Motion Estimation and the Motion Compensation. The Motion Estimation (ME) module compares two frames namely; the reference frame and the current frame and identify the best matched block position depicting the Motion Vector. The Motion Compensation (MC) module is used to generate the compensated frames through the Motion Vectors. Upon comparison, it has been identified that the ME module is very challenging and time consuming than the MC module. The ME module involves division of the frames into variable sized non-overlapping blocks and computation of the displacement of the best matched block from the reference frame. It includes search techniques which play a vital role in eliminating the temporal redundancy of a video sequence (see Figure 1 and 2).

Figure 1.

Quad-Tree Coding Structure in HEVC

Figure 2.

Quad-Tree Structure

The problem of Temporal Redundancy can be mitigated to a greater extent by the employment of efficient algorithms in the ME module. For specific applications like the Distributed Video Coding, the complexity of the ME module can be shifted to the side of the decoder, but, the overall complexity remains unaffected (Purnachand et al., 2012; Dufaux et al., 2009). A few other techniques that can be employed by the ME module apart from the video compression is the Frame Interpolation which is primarily used to Frame Rate up-conversion (Asencenso et al., 2005; Hong et al., 2010). Block Matching is the process of comparing each target block of the current frame with that of the previous (reference frame) so as to identify the best matching block. The best match can be calculated using Mean Absolute Difference (MAD) (Cafforio. C & Rocca. F, 1976) (see Figure 3).

Figure 3.

Illustration of ME process