Fast algorithms for block motion estimation

Two fast algorithms are presented to reduce the computational complexity of block motion estimation. Previously proposed fast algorithms reduce the number of computations by limiting the number of locations that are searched to find the motion vectors of each block. The techniques presented use block and pixel subsampling to reduce the number of computations of block motion estimation. Because an exhaustive search is used to estimate a fraction of the motion vectors, these techniques are more robust than those previously proposed. Alternating the pixel subsampling patterns with the searched locations minimizes the effects of the aliasing that is introduced by subsampling the pixels without prior low-pass filtering. Block and pixel subsampling by a factor of four each reduce the computational complexity of block motion estimation by a factor of 16. Performance similar to full exhaustive search is obtained