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 of the full-search motion estimation hardware. The thick output arrows from the blocks at hierarchy level 3 indicate 2P + 1 outputs.
16.5.1 Hierarchy Level 3 (Leftmost Level)
Referring to Fig. 16.4, blocks in hierarchy level 3 are divided into 2P + 1 groups. Each group contains B one-dimensional (1-D) blocks as shown. All outputs from one group are fed to one block of the next level in the hierarchy. Each group is associated with a particular relative vertical shift l between blocks c and r. Each 1-D block of a group corresponds to one row of blocks c and r and produces 2P + 1 SAD values (one at a time). The output of each 1-D block is given by the expression
16.5.2 Hierarchy Level 2
Referring to Fig. 16.4, each block at hierarchy level 2 produces 2P + 1 SAD values (at different time instances but on a single output line) that are associated with a particular relative vertical shift l between blocks c and r. Each output corresponds to a particular relative horizontal shift k between blocks c and r and is represented by one circle in Fig. 16.3. The output from a SAD block associated with a particular relative shift pair (k, l) can be written as
where D(i, j, k, l, m) represents an output of a 1-D block from hierarchy level 3.
16.5.3 Hierarchy Level 1
Referring to Fig. 16.4, each block at hierarchy level 1 produces the minimum SAD value H-min(i, j, l) for one row in Fig. 16.3 corresponding to a relative vertical shift l between blocks c and r. The output of each H-min block can be written as
(16.5)
where min is the function that selects the minimum of 2P + 1 values and SAD (i, j, k, l) represents an output of a SAD block from hierarchy level 2.
16.5.4 Hierarchy Level 0 (Rightmost Level)
Referring to Fig. 16.4, level 0 of the hierarchy produces the motion vector v(i, j) by selecting the minimum SAD value from among a set of minimum values, H-min (i, j, l), which are indicated by the black circles in Fig. 16.3. The output of the V-min block corresponds to the output in Eq. 16.1 and can be written as
(16.6)
where V-min is the function that selects the minimum of 2P + 1 values and H-min (i, j, l) represents an output of an H-min block from hierarchy level 1.