A nested-multilevel redundancy exploitation for fast block matching

In this paper we propose a block matching algorithm (BM) that reduces the computational burden of the motion estimation in an hybrid video encoder. To decrease the global complexity it acts at three different levels represented by the frame itself, the searching window and the macroblock (MB). To achieve an optimal performance also onto current general purpose processors provided with SIMD register files, a particular sub-sampling pattern of the MB is used. The algorithm shows a lower complexity than the three step search (TSS). In sequences where the motion field is formed by large motion vectors, the quality performance can be better than the full search algorithm (FSA) with an a priori fixed maximum motion vector. The algorithm is in fact able to adapt itself to the sequence