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

Section 4.6. Block-Matching Methods 105

because they appear as multiple peaks in the correlation surface. In addition
to its use in video coding, the phase correlation method has been successfully
incorporated into commercial standards conversion equipment [93].
There are few other frequency-domain motion estimation methods. For
example, Chou and Hang [94] analyzed frequency-domain motion
estimation in both noise-free and noisy situations. Their analysis is very similar
to the noise analysis in phase or frequency modulation systems, and it
provides insights into the performance limits of motion estimation. They
formulated frequency-domain motion estimation as a set of simultaneous
equations, which they solved using a modi ed least-mean-square (LMS) algo-
rithm. The resulting algorithm is known as the frequency component method.
It provides more reliable estimates than the phase correlation method, partic-
ularly for noisy sequences. Young and Kingsbury [95] proposed a frequency-
domain method based on the complex lapped transform. Koc and Liu [96]
used the pseudophase hidden in the DCT transform to propose a DCT-based
frequency-domain motion estimation method. The algorithm has a low compu-
tational complexity and was later extended to achieve interpolation-free subpel
accuracy [97].

4.6 Block-Matching Methods

Block-matching motion estimation (BMME) is the most widely used motion
estimation method for video coding. Interest in this method was initiated by
Jain and Jain in 1981 [54]. In their block-matching algorithm (BMA), the
current frame, f t , is rst divided into blocks of M × N pels. The algorithm
then assumes that all pels within the block undergo the same translational
T
movement. Thus, the same motion vector, d =[d x ;d y ] , is assigned to all pels
within the block. This motion vector is estimated by searching for the best-
) pels
match block in a larger search window of (M +2d m x ) × (N +2d m y
centered at the same location in a reference frame, f t−@t , where d m x and d m y
are the maximum allowed motion displacements in the horizontal and vertical
directions, respectively. This process is illustrated in Figure 4.2 and can be
formulated as follows:

ˆ ˆ ; (4.28)
(d x ; d y ) = arg min BDM(i; j); where |i|≤d m x and |j|≤d m y
i; j
and BDM(i; j)isa block distortion measure that measures the quality of match
between the block in the current frame and a corresponding candidate block in
the reference frame shifted by a displacement (i; j). It is very common to use
square blocks of N × N pels and a maximum motion displacement of ± d m
in both directions. When Equation (4.28) is evaluated for all possible (i; j)