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

100 Chapter 4. Basic Motion Estimation Techniques

By ignoring the cross terms (i.e., s∈A HD(s)·VD(s) ≈ 0), it can be shown
that the general analytical solution of Ca orio and Rocca (Equation (4.12))
reduces to the simple heuristic solution of Limb and Murphy (Equation (4.4)).
The main assumption in deriving the di erential estimate of Equation (4.12)
using Taylor series expansion is that the motion vector d is small. As d
increases, the quality of the approximation becomes poor. Thus, the main
drawback of di erential methods is that they can only be used to measure
small motion displacements (up to about ±3 pels). A number of methods
have been proposed to overcome this problem, like, for example, the iterative
method of Yamaguchi [83]. In this method, an initial motion vector is rst
estimated, using Equation (4.12), between a block in the current frame and a
corresponding block in the same location in the reference frame. In the next
iteration, the position of the matched block in the reference frame is shifted
by the initial motion vector, and then the di erential method is applied again
to produce a second estimate. This second estimate acts as a correction term
for the initial estimate. This process of shift and estimation continues until the
correction term becomes adequately small.
Another drawback of di erential methods is that the spatial gradient oper-
ator, ∇ s , is sensitive to data noise. This can be reduced by using a larger set
of data in its calculation.
There are also cases where di erential methods can fail [84]. For example,
in smooth areas the gradient is approximately equal to zero and the matrix in
Equation (4.12) becomes singular. Also, when motion is parallel to edges in
T
the image, i.e., d ∇ s ≈ 0, the frame di erence, Equation (4.10), becomes zero,
giving a wrong displacement of zero. Such problems may be partially solved
by increasing the data area, but this may give rise to the accuracy problem.

4.4 Pel-Recursive Methods

T
Given a function g(r) of several unknowns r =[r 1 ;:::;r n ] , the most straight-
forward way to minimize it is to calculate its partial derivatives with respect
to each unknown, set them equal to 0, and solve the resulting simultaneous
equations. This is called gradient-based optimization and can be represented
in vector form as
∇ r g(r)=0: (4.13)
In cases where the function g(r) cannot be represented in closed form and=or
the set of simultaneous Equations (4.13) cannot be solved, numerical iterative
methods are employed.
One of the simplest numerical methods is the steepest-descent method. Since
the gradient vector points in the direction of the maximum, this method updates