A comparison of block-matching motion estimation algorithms

Block-matching motion estimation is an efficient algorithm for reducing the temporal redundancy in video coding and is adopted by video coding standards. Many fast block-matching algorithms have been devised to reduce the computational complexity without degrading the estimation quality. Seven algorithms are implemented and compared - using quality of prediction and efficiency: the full-search, the three-step search, the four-step search, the diamond search, the hexagonal block search, the multi-directional gradient descent search and the fast directional gradient descent search. The aforementioned algorithms are chosen not only because of their popularity, but also because they are rather generic and they represent different ways of cutting down the computation. The most efficient algorithms are the hexagonal block search, the multi-directional gradient descent search and the fast directional gradient descent search. The hexagonal block search produces low quality of prediction, while the two others have the best quality prediction among all analysed algorithms. Also, the hexagonal block search has shown to be less affected by the variation in the block size.