Complexity comparison of fast block-matching motion estimation algorithms

Block-matching algorithms (BMA) have been widely adopted for motion estimation (ME) by real-time video coding applications due to its effectiveness and simplicity in implementation. Most fast BMAs are based on the assumption that ME matching error decreases monotonically as the search approaches the position of the global minimum error. The paper measures the contributions to computational cost reduction by different fast BMAs, including four-step search, diamond search, hexagon-based search and the recently proposed adaptive multi-mode search (AMMS). Comparison results show that the AMMS algorithm achieves a significant improvement based on the given mathematical models. Experimental coding results are also presented.