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

102 Chapter 4. Basic Motion Estimation Techniques

where W j ≥ 0 and p W j = 1. Netravali and Robbins also proposed a simpli-
j=1
ed expression for hardware implementation:
ˆ i
ˆ i
ˆ i
d ˆ i+1 = d − sign[DFD(s; d )] sign[∇ s f t−@t (s − d )]: (4.21)
The convergence of this method is highly dependent on the constant step
size . A high value of leads to quick convergence but less accuracy, whereas
a small value of leads to slower convergence but more accurate estimates.
Thus, a compromise between the two is desired. A number of algorithms have
been reported to improve the performance of pel-recursive algorithms, e.g.,
Ref. 86. Most of them are based on the idea of substituting the constant step
size by a variable step size to achieve better adaptation to the local image
statistics and, consequently, faster convergence and higher accuracy. A good
review of such methods with comparative results can be found in Ref. 87.
The dense motion eld of pel-recursive methods can overcome the accuracy
problem. This is, however, at the expense of a large motion overhead. To
overcome this drawback, the update term from one iteration to the other can
be based on previously transmitted data only. In this case, the decoder can
estimate the same displacements generated at the encoder, and no motion
information needs to be transmitted. A disadvantage of this causal approach,
however, is that it constrains the method and reduces its prediction capability.
In addition, it increases the complexity of the decoder.
Another disadvantage of pel-recursive methods is that they can easily con-
verge to local minima within the error surface. In addition, smooth intensity
regions, discontinuities within the motion eld, and large displacements cannot
be e!ciently handled [55].

4.5 Frequency-Domain Methods

Frequency-domain motion estimation methods are based on the Fourier trans-
form (FT) property that a translational displacement in the spatial domain
corresponds to a linear phase shift in the frequency domain. Thus, assuming
that the image intensities of the current frame, f t , and the reference frame,
f t−@t , di er over a moving area, A, only due to a translational displacement,
(d x ;d y ), then

f t (x; y)= f t−@t (x − d x ;y − d y ); (x; y) ∈ A: (4.22)

Taking the FT of both sides with respect to the spatial variables (x; y) gives
the following frequency-domain equation in the frequency variables (w x ;w y ):

F t (w x ;w y )= F t−@t (w x ;w y )e j(−w x d x −w y d y ) ; (4.23)