A statistical adaptive block-matching motion estimation

We address the problem of motion estimation (ME) in digital video sequences and propose a new fast, adaptive, and efficient block-matching algorithm. Higher quality and efficiency are achieved using a statistical model for the motion vectors. This model introduces adaptation in the search window, drastically reducing the number of positions where correlation-type computation is performed. The efficiency is further improved by progressively undersampling the macroblock. Patterns for undersampling are proposed to obtain the maximum benefit from single instruction multiple data (SIMD) instructions. In contrast with existing motion-estimation techniques, search strategy and subsampled patterns are closely linked. This shows that a good search strategy is much more important than blindly reducing the number of pixels considered for the matching pattern. We describe an implementation of the proposed matching strategy that exploits the very long instruction word (VLIW) and SIMD technology available in the new Itanium processor family. Results show that the proposed algorithm adapts easily to the evolution of the scene avoiding annoying quality drops that can be observed with other deterministic algorithms. The total number of operations required by the proposed method is inferior to those required by traditional approaches.