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

160 Chapter 7. Reduced-Complexity Motion Estimation Techniques

1
on Texas Instruments’ TMS320C541 40-MHz processor [5]. Pro)ling results
show that this codec cannot achieve real-time processing even when using
SQCIF sequences. It can encode only about 1 frame=s, and it can decode only
about 20 frames=s. Another example is the implementation of the H.263 base-
line mode on the more powerful TMS320C62 200-MHz processor, as described
in Ref. 6. Again, this implementation cannot achieve real-time processing, for
it only can encode about 5 QCIF frames=s.
Looking at the building blocks of a typical video codec, it is not di cult
to realize that this huge computational complexity is due mainly to the motion
estimation process. As already discussed, most video codecs estimate motion
using the block-matching motion estimation (BMME) algorithm. The most
straightforward BMME algorithm is the full-search (FS) algorithm, sometimes
referred to as the exhaustive search or the brute-force search. This algorithm
is guaranteed to )nd the best-match block because it exhaustively searches
over all possible blocks (search locations or candidate motion vectors) within
the search window. The algorithm produces the best possible prediction qual-
ity. This is, however, at the expense of a huge computational complexity.
For example, for a CIF video sequence encoded at 30 frames=s with 16 × 16
blocks, maximum displacement of ± 15 pels, and SAD as the distortion mea-
sure, a direct implementation of a full-pel FS-BMME algorithm requires about
9
9
6 × 10 integer additions and subtractions, 3 × 10 magnitude operations, and
6
11 × 10 comparisons per second. In fact, the computational complexity of this
motion estimation process is greater than that of all the remaining encoding
steps combined. This is clear from Table 7.1, which shows pro)ling results 2
of the baseline mode of Telenor’s H.263 encoder [144] when used to encode
the QCIF FOREMAN sequence at 64 kbits=s. In this case, the motion estimation
3
process consumes about 70% of the overall encoding time.
Because of this high computational complexity, motion estimation has be-
come a bottleneck problem in many applications, e.g., mobile video termi-
nals and software-based video codecs, especially if real-time video coding is
required. This has motivated the development of a number of fast motion
estimation algorithms since the early 1980s. In fact, recent advances in video
coding not only highlight the importance of such algorithms, but even call for
further research into the area of reduced-complexity motion estimation. For
example, HDTV and multiple-reference motion estimation (discussed

1 According to Ref. 5, about half of all mobile phones currently use a ‘C54x processor.
2 The results were obtained using the pro)ler of the Visual C++ 5.0 compiler run on a PC
with a Pentium 100-MHz processor, 64 MB of RAM, and a Windows 98 operating system.
3 The baseline mode of Telenor’s H.263 codec uses block matching with 16 × 16 blocks, SAD
as the distortion measure, and ±15 pels maximum displacement. Full-pel accuracy is )rst obtained
using full search. This is then re)ned to half-pel accuracy.