A hierarchical design methodology for full-search block matching motion estimation

Many useful DSP algorithms have high dimensions and complex logic. Consequently, an efficient implementation of these algorithms on parallel processor arrays must involve a structured design methodology. Full-search block-matching motion estimation is one of those algorithms that can be developed using parallel processor arrays. In this paper, we present a hierarchical design methodology for the full-search block matching motion estimation. Our proposed methodology reduces the complexity of the algorithm into simpler steps and then explores the different possible design options at each step. Input data timing restrictions are taken into consideration as well as buffering requirements. A designer is able to modify system performance by selecting some of the algorithm variables for pipelining or broadcasting. Our proposed design strategy also allows the designer to study time and hardware complexities of computations at each level of the hierarchy. The resultant architecture allows easy modifications to the organization of data buffers and processing elements-their number, datapath pipelining, and complexity-to produce a system whose performance matches the video data sample rate requirements.