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

176 Chapter 8. The Simplex Minimization Search

algorithms) are presented. They represent di+erent degrees of compromise
between prediction quality and computational complexity.
The rest of the chapter is organized as follows. Section 8.2 formulates
BMME as a two-dimensional constrained optimization problem. The SM
method and the reasons for choosing it to solve the BMME problem are
described in Section 8.3. The design of the single-reference SMS algorithm is
detailed in Section 8.4, and the results of testing it are presented in Section
8.5. Section 8.6 extends the SMS algorithm to the multiple-reference case. The
chapter concludes with a discussion in Section 8.7.
Preliminary results of this chapter have appeared in Refs. 165, 166, 167,
168, and 169.

8.2 Block Matching: An Optimization Problem

8.2.1 Problem Formulation

As discussed in Chapter 4 (Section 4.6), in BMME the current frame, f t ,is
usually partitioned into nonoverlapping blocks of N × N pels and the same
motion vector is assigned to all pels within a block. The motion vector or
T
displacement, d =[d x ;d y ] , of a block is estimated by searching for the best-
match block in a larger window of (N +2d m ) × (N +2d m ) pels centered at the
same location in a reference frame, f t−7t , where d m is the maximum allowed
motion displacement. This process can be formulated as follows:

(d x ;d y ) = arg min BDM(i; j); (8.1)
i; j
where −d m ≤ i; j ≤ + d m and

� �
N
N
BDM(i; j)= g[f t (x; y) − f t−7t (x − i; y − j)]: (8.2)
y =1 x =1
The BDMcan be any positive function that measures the distortion between
the block in the current frame and the candidate displaced block in the
reference frame. Commonly used BDMs are the SSD, g[·]=(·) , and the SAD,
2
g[·]= |·|.
Equations (8.1) and (8.2) clearly indicate that BMME is a two-dimensional
constrained optimization problem. The two dimensions are the horizontal, i,
and vertical, j, motion displacements, the function to be optimized (minimized
in this case) is the BDM, and the independent variables, (i; j), are constrained
within a limited range, −d m ≤ i; j ≤ +d m , and are usually evaluated to a certain
accuracy, e.g., full- or half-pel accuracy.