Algorithms and Parallel Computing

16.4 FORMULATION OF THE FBMA

The motion vector v associated with the current block c(i, j) is the displacement vector v(i, j) = [k* l*]^t, which minimizes the sum of absolute differences, SAD (i, j, k, l), given by

(16.1)

where c(i + m, j + n) is the pixel intensity (luminance value) in the current block with coordinates (i, j); r(i + k + m, j + l + n) is the pixel intensity in the reference block with coordinates (i + k, j + l).(k, l) is a relative displacement between the reference block and the current block in the search area (as shown in Fig. 16.1), and (k*, l*) is the optimum relative displacement. The ranges of the indices i, j, k, and l are

where

The expressions above ensure valid bounds near the edges of the frame. Thus, the displacement vector v(i, j) can be expressed by

(16.2)

Full-search motion estimation is a highly regular iterative algorithm with several embedded loops to reflect a hierarchical structure. We will make use of the embedded loop structure in what follows to illustrate a SIMD processor architecture that could be developed for each level of the hierarchy. ...