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

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

Murugesan Ezhilarasan (Pondicherry Engineering College, India), Kumar K. Nirmal (Pondicherry Engineering College, India) and P. Thambidurai (Perunthalaivar Kamarajar Institute of Engineering and Technology, India)
DOI: 10.4018/978-1-4666-9685-3.ch006
OnDemand PDF Download:


The Motion Estimation is an indispensable module in the design of video encoder. It employs Block Matching algorithm which involves searching a candidate block in the entire search window of the reference frame taking up to 80% of the total video encoding time. In order to increase the efficiency, several Block Matching Algorithms are employed to minimize the computational time involved in block matching. The chapter throws light on an efficient approach to be applied to the existing Block Matching Search techniques in HEVC which outperforms the various Block Matching algorithms. It involves two steps namely – Prediction and Refinement. The prediction step considers two parameters such as the temporal correlation and the direction to predict the MV of the candidate block. Several combinations of the search points are formulated in the refinement step of the algorithm to minimize the search time. The results depict that the Efficient Motion Estimation schemes provide a faster search minimizing the computational time upon comparison with the existing Motion Estimation algorithms.
Chapter Preview


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

Complete Chapter List

Search this Book: