A Fast Diamond Motion Estimation Search Algorithm for Real Time Video Applications

Abstract

This Motion Estimation (ME) has been widely used in most of the video standards. It is the most computationally intensive part of video compression. Speed up this process will open new real time applications. A novel Fast Diamond Search (FDS) algorithm is proposed in this journal. The proposed algorithm is a modified version of the conventional Diamond Search (DS) algorithm. Two main steps are added to the conventional DS algorithm for more computational savings achievement and keeping an acceptable coding efficiency (good bit-rate and Peak Signal to Noise Ratio of the transmitted video signal). The first step is to accurately remove the internal redundancy when calculating the Sum of Absolute Difference (SAD) between the current and the candidate blocks. This will be achieved using the Dynamic Internal Stop Search (DISS) algorithm.The second step aims to skip all the irrelevant blocks in the search area using Dynamic External Stop Search (DESS) algorithm. Additionally, more savings in computations are achieved in the early stage of the proposed FDS using both early search termination and adaptive pattern selection techniques. Compared to the conventional Full Search (FS) algorithm and DS algorithm, respectively, the proposed FDS algorithm achieves up to 99% and 20% more reduction in computations. The FDS algorithm guarantees high computational savings and keeping low degradation in both the Peak Signal to Noise Ratio (PSNR) and the bit-rate. Additionally, falling in a local minimum while computing the SAD is disappeared using the proposed FDS