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

Section 4.4. Pel-Recursive Methods 101

i
the present estimate, r ˆ , of the location of the minimum in the direction of the
negative gradient, to obtain a new improved estimate
i
i
r ˆ i+1 = ˆ r − ∇ r g(r ˆ ); (4.14)
where ¿ 0 is an update step size and i is the iteration index.
Pel-recursive methods are based on an iterative gradient-based minimization
of the prediction error. They were rst proposed by Netravali and Robbins in
1979 [85]. In their algorithm, they use a steepest-descent approach to iteratively
minimize the square of the displaced-frame di erence, DFD(s; d), with respect
to the displacement vector, d. Thus

2
g(r) = DFD (s; d); (4.15)
where

DFD(s; d)= f t (s) − f t−@t (s − d): (4.16)

Substituting Equation (4.15) into Equation (4.14) and setting = 2 gives
ˆ i
2

ˆ i
d ˆ i+1 = d − ∇ d DFD (s; d ): (4.17)
2
Now,
2
∇ d DFD (s; d) = 2 DFD(s; d) ∇ d DFD(s; d)
= 2 DFD(s; d) ∇ d [f t (s) − f t−@t (s − d)]
= 2 DFD(s; d) ∇ s f t−@t (s − d): (4.18)
Substituting Equation (4.18) into Equation (4.17) gives
ˆ i
ˆ i
ˆ i
d ˆ i+1 = d − DFD(s; d )∇ s f t−@t (s − d ); (4.19)
ˆ i
where the spatial gradient ∇ s f t−@t (s − d ) can be approximated by Equations
ˆ i
(4.7) and (4.8) but evaluated at a displaced location (s − NINT[d ]) in the
reference frame. As in di erential methods, this estimate is highly dependent
on the spatial gradient. For this reason, pel-recursive methods are sometimes
considered a subset of gradient or di erential methods.
The iterative approach of Equation (4.19) is normally applied on a pel-
ˆ
by-pel basis, leading to a dense motion eld, d(s). Iterations may proceed
along a scanning line, from line to line, or from frame to frame. In order to
smooth out the e ect of noise, the update term can be evaluated over an area
A = {s 1 ;:::; s p } as follows:

p
ˆ i
ˆ i
ˆ i
d ˆ i+1 = d − W j DFD(s j ; d )∇ s f t−@t (s j − d ); (4.20)
j=1