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

96 Chapter 4. Basic Motion Estimation Techniques

In forward motion estimation, however, the same pel is related to a pel in
a future reference frame at time t +@t by

f t (s)= f t+@t (s + d(s)): (4.2)
The aim of motion estimation is to nd the motion vector d(s)=[d x (s);
T
d y (s)] . Note that d(s) is not necessarily a full-pel accurate motion vector.
Thus, a motion estimation technique may need to access intensity values at
nonsampling locations in the reference frame. This is achieved using inter-
polation techniques like nearest-neighbor, bilinear, and cubic interpolation. In
this book, bilinear interpolation is employed because of its good compromise
between interpolation quality and computational complexity. It is de ned as

f(x; y)=(1 − x f )(1 − y f )f(x i ;y i )+ x f (1 − y f )f(x i +1;y i )

+(1 − x f )y f f(x i ;y i +1)+ x f y f f(x i +1;y i +1); (4.3)
where (x i ;y i ) and (x f ;y f ) are, respectively, the integer and fractional parts of
the pel coordinates (x; y).
Care should be taken when interpreting the terms forward and backward.
The two terms can be used to refer to either the motion estimation process or
the motion compensation process. A forward motion estimation process cor-
responds to a backward motion compensation process, and vice versa. Note
that forward motion estimation is associated with a coding delay. Thus, most
video coding standards employ backward estimation (i.e., forward compensa-
tion), although forward estimation is sometimes employed (e.g., in B-frames
in MPEG1–2 and PB-frames in H.263).

4.2.3 An Ill-Posed Problem

The preceding formulation of the motion estimation problem indicates that it
1
is an ill-posed problem. It su ers from the following problems [10]:
• Existence of solution: For example, no motion can be estimated for
covered=uncovered background pels. This is known as the occlusion
problem.
• Uniqueness of solution: At each pel, s, the number of unknown inde-
pendent variables (d x and d y ) is twice the number of equations, (4.1)
or (4.2). This is known as the aperture problem.

1 A problem is called ill-posed if a unique solution does not exist and=or the solution does not
continuously depend on the data [79].