Fast block matching algorithm based on the winner-update strategy

Many fast algorithms for block matching were proposed in the past, but most of them do not guarantee that the match found was the globally optimal match in a search range. A new fast algorithm, named the winner-update algorithm, which can speed up the computation of block matching while still guaranteeing that the minimum matching error can be obtained was proposed. Experiments showed that, when applying to motion vector estimation for several widely-used test videos, 92% to 98% of operations can be saved while still guaranteeing the global optimality. Moreover, the proposed algorithm can be easily modified either to meet the limited time requirement or to provide an ordered list of best candidate matches.