All Directional Search Motion Estimation Algorithm

The search performance of block-matching motion estimation algorithms, i.e., search speed and motion estimation quality, mainly depends on the shape and size of the search pattern. Most motion estimation algorithms employ search patterns of square, diamond, hexagonal, cross diamond or cross hexagonal shapes. These search patterns achieve good results for video sequences with simple motion activity, but unfavourable results for video sequences with complex motion activity. After a thorough investigation of the effect of search pattern on search performance, this paper proposes an all-direction search (ADS) pattern, which searches for the best block in all possible directions. For further improvement in search speed, a half way stop technique is applied in search process. The results show that the proposed ADS algorithm outperforms other state-of-the-art and eminent motion estimation algorithms. The higher the direction complexity in the neighbouring motion vectors, the better the prediction quality of ADS, which is further proved by the simulation results.