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

Part III

Computational Complexity

In mobile terminals, processing power and battery life are very limited and
scarce resources. Given the signi cant amount of computational power required
to process video, the use of reduced-complexity techniques is essential.
Motion estimation is the most computationally intensive process in a typical
video codec. In fact, the computational complexity of this process is greater
than that of all the remaining encoding steps combined. Thus, by reducing
the complexity of this process, the overall complexity of the codec can be
reduced.
This part contains two chapters. Chapter 7 reviews reduced-complexity mo-
tion estimation techniques. The chapter uses implementation examples and pro-
ling results to highlight the need for reduced-complexity motion estimation.
It then reviews some of the main reduced-complexity block-matching motion
estimation techniques. The chapter then presents the results of a study com-
paring the di#erent techniques.
Chapter 8 gives an example of the development of a novel reduced-compl-
exity motion estimation technique. The technique is called the simplex mini-
mization search (SMS). The development process is described in detail, and
the SMS technique is then tested within an isolated test environment, a block-
based H.263-like codec, and an object-based MPEG-4 codec. In an attempt
to reduce the complexity of multiple-reference motion estimation (investi-
gated in Chapter 6), the chapter then extends the SMS technique to the
multiple-reference case. The chapter presents three di#erent extensions (or
algorithms) representing di#erent degrees of compromise between prediction
quality and computational complexity.