A fast motion estimation algorithm equivalent to exhaustive search

A fast algorithm is proposed for block motion estimation for video sequences. The proposed algorithm is proven to be equivalent to exhaustive search. In a multiresolution approach, it uses a mathematically derived threshold to prune search candidates whose low-resolution versions are too far from the low resolution version of the block for which a best match is sought. Experimental results show that speed ups of around 36, compared to full search, may be achieved, for some typical test video sequences. This is the fastest full-search-equivalent motion estimation reported in the literature to date, and has speed ups comparable to inexact fast motion estimation methods