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

182 Chapter 8. The Simplex Minimization Search

Let p m =(m x ;m y ) be the point that yields the smallest BDM, then the BDM
is also evaluated at its eight nearest neighbors, (m x ;m y ± a), (m x ± a; m y ) and
(m x ± a; m y ± a), where a is the accuracy of the search, e.g., a = 1 for full-pel
accuracy. At this stage, all points (including those from the initial procedure)
are arranged in ascending order according to their BDMs and the :rst three
are chosen to form the initial simplex. If this is still a degenerate one, then
the appropriate point is dropped and replaced by the next one in the list. This
is repeated until a nondegenerate simplex is formed.
Once a nondegenerate initial simplex is formed, the search proceeds
as shown in Figure 8.2, subject to the constraints outlined in Section 8.4.2,
and is terminated when the criterion described in Section 8.4.3 is
satis:ed.

8.4.2 Constraints on the Independent Variables
The SMmethod assumes continuous unconstrained independent variables.
However, when applied to the constrained minimization problem of BMME,
two constraints have to be imposed. Firstly, the vertices of the simplex must
always be set to the required accuracy before any BDMevaluation can take
place. For example, if full-pel accuracy is assumed, then any point produced
by reCection, expansion, or contraction must be rounded to the nearest integer
value. Secondly, the vertices of the simplex must always be kept within the
search window. Any point produced by reCection, expansion, or contraction
must be set to the closest point within the range −d m ≤ i; j ≤ + d m before any
BDMevaluation can take place. This constraint is more eDcient than other
possible constraints, like, for example, assigning a large function value to the
vertex outside the search window.

8.4.3 Termination Criterion

There are many possible ways to terminate optimization methods. One of the
most widely used approaches is to terminate the search if the current minimum
function value is below some threshold. In the SMcase, another approach is
to terminate the search if the fractional range from the highest, in terms of
function value, to the lowest vertices of the simplex is below some threshold
[174].
According to Property 4:6:7:4, the function value at the global minimum
is unpredictable. Thus, if the preceding termination criteria are used, then
the threshold needs to be adjusted from one sequence to another, from one
frame to another, and even from one block to another. This makes such criteria
unsuitable for BMME. A more suitable criterion is as follows. Let p h =(h x ;h y ),
p s =(s x ;s y ), and p l =(l x ;l y ) be the vertices of the simplex where the BDMis