Algorithms and Parallel Computing

16.5 HIERARCHICAL FORMULATION OF MOTION ESTIMATION

There are several complications associated with motion estimation. First, the algorithm operations are not homogeneous, viz, subtraction, absolute value calculation, and minimum search. Second, a pixel is used more than once for several adjacent reference blocks. Third, a current block requires data from adjacent blocks around it. All these complications indicate that a hierarchical design methodology must be employed; hardware control must be considered during the design process; and extensive buffering must be used. Our strategy is to express Eq. 16.1 by a progressive set of hierarchical descriptions of the operations to be performed. The goal is to explore efficient parallel hardware architectures for each description at each hierarchy level. Figure 16.3 shows the (2P + 1)2 SAD values associated with a particular current block for a certain search area. Each SAD value is obtained at a different relative shift pair (k, l) between blocks c and r. The figure assumes P = 3 for simplicity, and the black circles indicate the minimum SAD value of each row. Figure 16.4 is a block diagram for the hierarchical decomposition of the full-search motion estimation hardware. The functions of each hierarchy level are described in the following sections.

Figure 16.3 Different SAD values obtained due to the different k, l relative shifts between blocks c and r for P = 3.

Figure 16.4 A block diagram for the proposed hierarchical decomposition ...