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

Section 8.3. The Simplex Minimization (SM) Optimization Method 177

An optimization problem can be thought of as a search process where the
function surface is searched over a given search space to :nd its minimum
(or maximum). This search is performed by examining the function value at
a :nite number of search locations. In BMME, the search space is the search
window in the reference frame. Each candidate block within this window rep-
resents a search location, (i; j). This is the displacement between the block in
the current frame and the candidate block in the reference frame. With full-pel
2
accuracy, there are (2d m +1) possible search locations in the search space. The
corresponding BDMvalues form the function surface. Since BDMis a distor-
tion measure, this surface is also referred to as the error surface. The set of
motion vectors assigned to the blocks of the frame form a block-motion !eld.

8.2.2 A Possible Solution
As shown in Section 8.2.1, BMME can be formulated as an optimization
problem. This problem can, therefore, be solved, with reduced complexity,
using a wealth of mature optimization methods.
There are few fast BMME algorithms that are based on optimization
methods. For example, the TDL search of Jain and Jain [54] is an extension
of the 1-D binary logarithmic search [170], the OTS and CDS algorithms of
Srinivasan and Rao [146] are based on the conjugate directions (CD) opti-
mization method [171], and the GMS algorithm of Chow and Liu [148] is
based on the genetic algorithm (GA) optimization method [172].
In a similar fashion, this chapter solves the BMME optimization problem
using the simplex minimization (SM) optimization method [173]. The resulting
solution is called the simplex minimization search (SMS).
Figure 8.1 shows the basic building blocks of any constrained optimization
method. It can be seen that when trying to solve an optimization problem,
there are two main design stages. The :rst, and probably the most important,
stage is to choose a suitable optimization method. Section 8.3 describes the
SMoptimization method and outlines the reasons for choosing it to solve the
BMME optimization problem. The second stage is to design a suitable initial-
ization procedure, a termination criterion, and constraints on the independent
variables of the search. For the SMS, this stage is detailed in Section 8.4.

8.3 The Simplex Minimization (SM) Optimization
Method

8.3.1 Basic Algorithm

Simplex minimization (SM) is a multidimensional unconstrained optimization
method that was introduced by Nelder and Mead in 1965 [173]. A simplex is a