An optimal fast full search motion estimation algorithm in video coding

In real time video coding, Full Search (FS) algorithm gives the most accurate motion vector causing minimum matching error. But, it requires large amount of computation. So, reduction of the computational cost in full search motion estimation is vital research point in real time video coding. Successive Elimination Algorithm (SEA) and Multi-level Successive Elimination Algorithm (MSEA) reduce the number of computations by eliminating the highly impossible candidate blocks in the search window before arriving at the calculation of Sum of Absolute Difference (SAD) that requires intensive computations. In this paper we propose an optimal fast full search motion estimation algorithm which significantly reduces unnecessary computations without affecting motion prediction quality. The proposed algorithm presents Fast Computing Method (FCM) which identifies the computational redundancy and removes it while calculating the SAD. This algorithm eliminates even less impossible candidate blocks with tighter decision boundaries. The proposed algorithm removes unnecessary computations by about 78% compared with SEA and by about 98% compared with FS.