A novel fast search motion estimation algorithm in video coding

Full search (FS) motion estimation algorithm compares the current block with every possible block of the reference block to find the most accurate motion vector (MV) with the least matching error by the mean square error (MSE). Using FS motion estimation algorithm in real time applications is impractical because of the cumbersome computations. In order to decrease the amount of significant computation on a FS motion estimation algorithm a fast search algorithm is proposed. A fast search algorithm samples a few possible locations in a search block in order to find local minimum MSE. A fast search algorithm improves the processing time and also gives a good quality performance in terms of the quality in the reconstructed frame. The proposed fast search algorithm aims to remove computational redundancy by eliminating most highly impossible candidate locations. Experiments show that proposed algorithm reduces the computations greatly up to 99% and 22% compared to FS and diamond search (DS).