Automatic Parallelization of Full 2-D Block Matching for Real Time Motion Compensation and Mapping into Special Purpose Architectures

Abstract The most important issue in video encoding is motion compensation within a frame sequence. Block matching techniques are used by various algorithms [5], [6] to estimate the motion into succesive frames. Full search 2-D block matching is the most widely used algorithm for video encoding in all standards (H261, MPEG1-2, HTDV etc). It provides with the best SNR, since it uses exhaustive search to find the best, in terms of MAD or MSE matching candidate block. Its main disadvantage is that it requires a lot of computations which should be performed for every candidate frame. Consequently, real time application of the 2-DFS algorithm for video compression, requires the use of parallel architectures, to achieve large amount of computations. This paper presents the application of automatic loop parallelization techniques to provide with scalable or fixed systolic arrays, with optimal performance, in terms of total computation time. We transform the BMA algorithm into an equivalent form, in order to apply the automatic parallelization method. Starting from the dependence index space, we map the matching algorithm to 2-D or 3-D systolic arrays and we propose an alternative mapping for fixed size architectures. I. BLOCK MATCHING MOTION ESTIMATION CONCEPTS: Block-matching motion estimation/compensation is used to remove the temporal redundancy within a frame sequence, thus resulting into significant bit-rate reductions for digital image encoding methods. Nevertheless it requires a large amount of computation and heavy memory bandwidth. In the block-matching techniques, the candidate frame for encoding is partitioned into quadratic blocks of nxn pixels. These blocks, resulting from the segmentation of the current and previous frames, are called current and previous block, respectively. For each current block, the best matching previous block is sought within a search area surrounding the previous block: (k,l) Displaced previous block Previous frame Fn-1 m/2 m/