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

Section 8.4. The Simplex Minimization Search (SMS) 181

8.4 The Simplex Minimization Search (SMS)

Having decided on the optimization method to be used (the SMoptimization
method in this case), the second stage is to design a suitable initialization
procedure, a termination criterion, and constraints on the independent variables
of the search. The performance of an optimization method can be greatly
improved if this design stage exploits a priori knowledge of the problem
at hand. For example, the basic properties of the BMME problem can be
exploited to avoid local minima and initialize the search at a location close
to the global minimum. This improves the prediction quality and at the same
time increases the speed-up ratio.
Although the TDL, OTS, CDS, and GMS algorithms are all based on good
optimization methods, they do not take into account the basic properties of
the BMME problem. As a result, such algorithms can either get trapped in
local minima, resulting in suboptimal prediction quality, or lead to a relatively
small speed-up ratio. In the simplex minimization search (SMS) algorithm,
however, the initialization procedure, termination criterion, and constraints on
the independent variables of the search are designed to exploit the basic prop-
erties of the BMME problem. This is described in more detail in the following
subsections.

8.4.1 Initialization Procedure
Block-matching motion estimation is a two-dimensional problem. As already
mentioned, a simplex, in two-dimensions, is a triangle. Thus, three points need
to be chosen to de:ne the initial nondegenerate simplex. As is shown later,
the performance of the SMmethod is highly dependent on the choice of these
points. The following initialization procedure is used.
According to Property 4:6:7:1, the vector (0; 0) has the highest probability
of occurrence within the block-motion :eld. One of the initial three points is
therefore set to (0; 0). In addition, Property 4:6:7:2 states that there is a high
correlation between the motion vectors of adjacent blocks. In fact, most video
coding standards take advantage of this property by predictively coding the
motion vectors. To exploit this property, and to match the motion estimation
process to the motion coding process, the other two points of the initial simplex
are set to the motion vectors of the blocks above and to the left of the current
block. If such neighboring vectors are not available, as in border blocks, they
are set to (0; 0).
Note that this procedure does not guarantee to produce a nondegenerate
initial simplex. For example, if two points are identical, then the simplex is
degenerate. In this case, a local search is applied to :nd other candidates.
The BDMis :rst evaluated at the points chosen by the foregoing procedure.