Page 184 - Video Coding for Mobile Communications Efficiency, Complexity, and Resilience

Section 7.3. Techniques Based on a Reduced Set of Motion Vector Candidates 161

Table 7.1: Pro)ling results of Telenor’s H.263 baseline mode when used to encode QCIF FOREMAN
at 64 kbits= s
Function CPU Time (ms) Percentage (%)

Motion estimation 240,354 69.7
Input= output 32,552 9.4
DCT= IDCT 29,412 8.5
Others 42,353 12.4
Total 344,671 100.0

in Chapter 6) have a computational complexity that is several orders of
magnitude higher than that shown in the preceding examples. The former uses
higher spatial resolutions and larger search windows, and the latter extends
the search over several reference frames.
The following sections of this chapter review the main categories of
reduced-complexity BMME algorithms. Although each category can be used
on its own, careful encoder design can utilize di-erent combinations to achieve
higher speed-up ratios.

7.3 Techniques Based on a Reduced Set of Motion
Vector Candidates

Instead of searching over all possible blocks within the search window, this
category restricts the search over a selected subset of the blocks. Most
algorithms in this category are, implicitly or explicitly, based on the uni-
modal error surface assumption [54], which states that the block distortion
measure (BDM) increases monotonically as the search location moves away
from the best-match location. Therefore, the search starts by evaluating the
BDM at locations coarsely spread over the search window according to some
prede)ned uniform pattern. This is then repeated with )ner resolution (i.e.,
smaller spread) around the search location with the minimum BDM from the
preceding step.
The )rst algorithm reported in this category was the two-dimensional log-
arithmic (TDL) search proposed in 1981 by Jain and Jain [54]. Figure 7.1
shows an example of the TDL search with a maximum displacement of d m =6
pels. The search is initialized at the origin of the search window with a suit-
able step size (i.e., the spacing between the search locations). In each step of
the TDL search, the BDM is evaluated at )ve search locations. In the given
example, the search locations (0; 0), (+2; 0), (−2; 0), (0; +2), (0; −2) form