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

Chapter 7

Reduced-Complexity Motion

Estimation Techniques

7.1 Overview

As already discussed, one of the main requirements for mobile video com-
munication is reduced-complexity. It is not di cult to show that the high
computational complexity of a typical video codec is due mainly to the mo-
tion estimation process. Thus, by reducing the complexity of this process, the
overall complexity of the codec can be reduced. This chapter reviews reduced-
complexity motion estimation techniques. In particular, the chapter concen-
trates on reduced-complexity block-matching motion estimation (BMME)
techniques. The chapter also presents the results of a study comparing dif-
ferent reduced-complexity BMME techniques.
The rest of the chapter is organized as follows. Section 7.2 uses imple-
mentation examples and pro)ling results to highlight the need for reduced-
complexity motion estimation. Sections 7.3–7.7 review the main categories of
reduced-complexity BMME algorithms. Section 7.8 presents the results of a
study comparing the di-erent categories. The chapter concludes with a discus-
sion in Section 7.9.

7.2 The Need for Reduced-Complexity Motion
Estimation

Processing digital video requires a signi)cant amount of computational power.
This represents one of the main challenges for real-time mobile video com-
munication, where processing power and battery life are scarce resources. For
example, an MPEG-4 simple pro)le codec has recently been implemented

159