Investigation and Analysis of Different Fast Block Matching Motion Estimation Algorithms for Video Compression

With advancement in video processing applications such as Digital TV, Internet Streaming Video, Videophones, Multi-media Communication and Video conferencing in last decade, one of the most essential components of video is its compression which is used for efficient storage and transmission of video signal. Video contains temporal redundancy between two successive frames which can be exploited to improve coding efficiency. One of technique used to remove temporal redundancy is motion estimation. A number of motion estimation techniques are used, out of which block matching motion estimation is most popular and proved efficient in terms of quality and bit rate and adopted in many video coding standards. Many fast block matching algorithms have been developed to improve processing speed, visual image quality and power consumption. This paper explores recently developed fast block based motion estimation algorithms such as Three Step Search (TSS), Simple and efficient search (SES), Diamond Search (DS) and most recently developed Adaptive Rod Pattern Search (ARPS) and presents the computational and performance trade-offs involved in preferring a motion estimation algorithm for video coding applications. These block based motion estimation algorithms are compared and implemented for different video sequences with different types of motion in terms of PSNR and Computational complexity. It is proved from results that Adaptive Rod Pattern Search (ARPS) achieves the best trade-off between PSNR and Computational complexity for different video sequences with slow, medium and fast motion activity.