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

Chapter 8

The Simplex Minimization Search

8.1 Overview

As already discussed, one of the main requirements for mobile video com-
munication is reduced complexity. In Chapter 7, it was shown that reducing
the complexity of the motion estimation process is the best way to reduce the
overall complexity of a video codec.
As detailed in Chapter 7 also, there are many techniques for reduced-
complexity BMME. The most widely used approach is to use a reduced set of
motion vector candidates. Algorithms in this category are usually based on a
unimodal error surface assumption. In most cases, however, this assumption
does not hold true, and such algorithms can easily get trapped in local minima,
giving a suboptimal prediction quality. This chapter describes the design of a
novel reduced-complexity BMME technique. Although this technique is based
on using a reduced set of motion vector candidates, it is designed to be more
robust against the local minimum problem.
BMME can be viewed as a two-dimensional constrained minimization
problem. This problem can, therefore, be solved with reduced-complexity using
a wealth of mature optimization techniques. This chapter solves the BMME
optimization problem using the simplex minimization (SM) optimization
method. The resulting solution is called the simplex minimization search
(SMS). The initialization procedure, termination criterion, and constraints on
the independent variables of the search are designed to take into account
the basic properties of the BMME problem. This improves the prediction
quality of the algorithm and, at the same time, increases its speed-
up ratio.
In Chapter 6, it was concluded that one of the main drawbacks of multiple-
reference motion-compensated prediction (MR-MCP) is the huge increase in
computational complexity. To reduce complexity, this chapter extends the SMS
algorithm to the multiple-reference case. Three di+erent novel extensions (or

175