Complexity comparison of fast block-matching motion estimation algorithms

Block-matching algorithm (BMA) for motion estimation (ME) has been widely adopted 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. This paper measures the contributions on computational costs reduced by different fast BMAs including four-step search, diamond search, hexagon-based search and 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.