Block matching algorithms for motion estimation using modified Cross-Diamond-Hexagonal search / Abd Razak Mahmud

Block-matching motion estimation is the most important part in today's video coding techniques and standard, such as 1S0/IEC MPEG-1, 2, 4, ITU-T H.261, H.263, and the emerging H.264. Each of the video frames is divided into macroblocks. The computational of the current pixel in current frame is compared to the previous decoded frame as a reference. The simplicity and effectiveness of the computational is the main criteria of different ME techniques. The fast search for ME techniques have their own shapes or patterns to work with in order to produce the best matching algorithm. The shape is actually representing the number of candidate need to be evaluated and fewer numbers of candidates will reduce the complexity of computational yet trying to keep a good block matching. A modified of Cross-Diamond-Hexagonal search (MCDHS) based on the Cross-Diamond-Hexagonal search (CDHS) is proposed to match or increase the performance of the Peak-signal-to-noise ratio (PSNR) and reduce the computational complexity of previous motion estimation techniques such as Three Step search (TSS), Simple and Efficient Three Step search (SESTSS), New Three Step search (NTSS), Four . Step search (4SS), Diamond search (DS), Adaptive Rood Pattern Search (ARPS) and Cross-Diamond-Hexagonal search (CDHS). This algorithm basically employs two crossshaped search patterns consecutively in the very beginning steps and switch using diamond-shaped patterns. To further reduce the checking points, two pairs of hexagonal search patterns are proposed in conjunction with candidates found located at diamond corners. The results show that MCDHS performance is equal to CDHS and better than other fast search for ME techniques in average number of search points except ARPS.