Fast full-search block matching

Abstract

A fast full-search block-matching algorithm is developed. The matching criterion is the sum of absolute differences or the mean-square error. The algorithm evaluates lower bounds for the matching criteria for subdivided blocks in order to reduce the number of search positions. It also uses the lower bounds for a fast calculation of the matching criterion for the remaining search positions. The computational complexity of the algorithm is evaluated and compared to the three-step search strategy. The search result of the algorithm is identical to the search result of the exhaustive search.