Employing a novel cross-diamond search in a modified hierarchical search motion estimation algorithm for video compression

• Novel three levels hierarchical motion estimation algorithm.
• The quality of the proposed algorithm is 98% similar to the Full Search algorithm.
• The complexity is reduced by 83.4% compared to the Full Search algorithm.
• A new search pattern is proposed at the middle level of the hierarchy.
• The algorithm outperforms the state-of-the-art work in this field.

The large amount of bandwidth that is required for the transmission or storage of digital videos is the main incentive for researchers to develop algorithms that aim at compressing video data (digital images) whilst keeping their quality as high as possible. Motion estimation algorithms are used for video compression as they reduce the memory requirements of any video file while maintaining its high quality. Block matching has been extensively utilized in compression algorithms for motion estimation. One of the main components of block matching techniques is search methods for block movements between consecutive video frames whose aim is to reduce the number of comparisons. One of the most effective searching methods that yield accurate results but is computationally very expensive is the Full Search algorithm. Researchers try to develop fast search motion estimation algorithms to reduce the computational cost required by full-search algorithms. In this research, the authors present a new fast search algorithm based on the hierarchical search approach, where the number of searched locations is reduced compared to the Full Search. The original image is sub-sampled into additional two levels. The Full Search is performed on the highest level where the complexity is relatively low. The Enhanced Three-Step Search Algorithm and a new proposed searching algorithm are used in the consecutive two levels. The results show that by using the standard accuracy measurements and the standard set of video sequences, the performance of the proposed hierarchal search algorithm is close to the Full Search with 83.4% reduction in complexity and with a matching quality over 98%.