1

Pel-Recursive Motion Estimation Algorithm 

By

H. Gharavi

National Institute of Standards & Technology (NIST)

100 Bureau DR Stop8920, Gaithersburg, MD 20899-8920, USA.

And

H. Reza-Alikhani

Loughborough University

Loughborough, Leics., LE11 3TU, UK.

Abstract: This paper presents a new pel recursive motion compensated prediction algorithm for 

video coding applications. The derivation of the algorithm is based on Recursive Least Squares 

(RLS) estimation that minimizes the mean square prediction error for each pel (picture element). A 

comparison with the modified Steepest-descent gradient estimation algorithm shows significant 

improvement in terms of mean-square prediction error performance.

Introduction: Netravali and Robbins [1] developed a pel recursive spatio-temporal steepest-descent 

gradient technique in which the displacement of a pel was predicted from previously transmitted 

information. Since then various algorithms have been proposed to improve the performance of pel 

recursive motion estimation (PRME) techniques. The most important contribution was the

modification of the steepest-descent algorithm which was introduced by Walker and Rao [2]. In this 

paper we present a simple but very efficient PRME algorithms that can significantly outperform the 

modified steepest-descent technique developed by Walker and Rao.

Proposed Algorithm: For the sake of our analysis, we assume the translation movement of an 

object is in a plane parallel to the camera and illumination is uniform. We also assume the effect of 

uncovered background to be negligible. Under these assumptions, let S (x, y, t) denote the

monochrome intensities at point x, y of a moving object in the image plane where its transnational 

NISTIR 6822

2007
2

movement is at the constant velocity of vx and vy. We can show that after Δt second (one frame 

period), the object moves to a new location where we can show,

Expanding the field in a power series in Δt and neglecting the higher order terms, 

or 

where dx and dy correspond to the horizontal and vertical components of the motion displacement 

ED, LD, and FD as the magnitude of the element, line, and frame difference at point n, from (3), 

we can write,

Where ( ) T is transpose and,

From (4) the frame difference (FD) measurement can be shown as, 

For a cluster of M moving pels, the least-squares estimate of D can be obtained as, 

S ( x, y: t + t ) = S ( x, y: t) +

 x

Δ S ( x, y: t) [ vx ] Δ S ( x, y: t) [ vy ] Δ

¶

¶

¶

¶

t

y

+ t (2)

S ( x,y: t + t ) - S ( x, y: t) =

 x

S ( x, y: t) dx

y

Δ S ( x, y: t) dy (3)

¶

¶

¶

¶

+

vector D. Assuming that are known for each x, y, t and definining ¶

¶

¶

x ¶

S ( x, y: t) and 

 y

S ( x, y: t) 

S ( x, y: t + D t ) = S [( x +vxDt), ( y +vy Dt): t] (1)

LSE = 

n n

T

 

min { ( D ) } (7)

D n=1

m

2 ∑ ξ − Φ

n

n D noise T ξ = Φ + (6)

where D = [d

T

(x),d(y)] is the motion vector estimate.

Φn 

n n

n n

=

 x

S ( x , y : t)

 y

S ( x , y : t)

 (5)

∂

∂

∂

∂

























=

























ED

LD

FD = Φn D (4) T
3

After minimization, 

For,

the estimated motion vector from (8) is obtained as, 

For recursive estimation of η and R, we can write 

Based on the so-called matrix inversion lemma, the inverse of RI can be obtained as, 

From (10), (11), and (12),

In the above equation, The term in the right hand side bracket can be replaced by what is known as 

the Displaced Frame Difference, DFD. Thus,

Simplifications:

To avoid matrix inversion at each iteration, (14) can be simplified by neglecting the x and y cross 

terms in calculating φn and R. Thus, from (5) and (9),

 R and R 

M

(x) ( )

M

y

j M

M

j

= ∑ = ∑

1 2 1 2

ED j LD j

 and (y) (15) Fn x Fn( ) = ED = LD

n=1

m

∑ = D ∑ (8)

=

Φn n Φ Φ

n

m

n

T ξ n

1

D R (10) -1 = η

 

R = R -

R R

1 + R

 (12)

i

-1

i-1

-1 i-1

-1

n n i-1

-1

-1

i-1

Φ Φ

Φ Φ

T

n

T

n

i

T

η ηi

 = + ξ 

R = R + (11) 

n n

i i-1 n n

−1 Φ

Φ Φ

 = -

1 +

( - ) (13) i i-1

i-1

-1

n

n i-1

-1

n

D D i-1

A

A

D

Φ

Φ Φ

T Φ

T ξ

η = ξ

1

M

 and R =

1

M

 (9)

n=1

n

n=1

M

n 

M

∑ Φ ∑ Φ Φ n n

T

i i-1

i-1

-1

n

n i-1

-1

n

 = -

A

1 + A

D D [DFD(x, y, D ) ] (14) i-1

Φ

Φ Φ

T
4

Applying (15) to (14), the components of the motion displacement estimates can be shown as,

Simulation Results

The computation involved in (16) is performed recursively. At each iteration the estimated motion 

displacement is applied to measure a new DFD. This would first require obtaining the location of 

the displaced pel on the previous frame, based on the estimated components of motion

displacement. Since the motion estimates are expected to be non-integer, the luminance value of the 

displaced pel is predicted by a two dimensional interpolator which uses the four corners of the 

surrounding pels in a two dimensional grid. In our experiments, the DFD is measured at two 

locations with reference to the current pel; the pel above (i.e., previous line), and the previous pel 

along the same line. The average of the two DFD’s (with equal weightings) is then used to update 

the displacement estimates. 

The ED and LD in (16) were also measured using the interpolated luminance values from the 

displaced previous frame. For ΣED2 and ΣLD2 the summation includes the luminance values of 

three interpolated neighboring pels from the previous frame. The above algorithm is applied to a 

cluster of pels that are classified as moving areas. In our experiments, a moving area consists of 

three neighboring pels (including the current pel) whose frame difference exceeds a predefined 

threshold (i.e. |FD| > threshold). 

Two video sequences, known as “Salesman” and “Suzie,” were considered for evaluating the 

performance of the proposed algorithm. The format of both sequences was based on the CIF 

(Common Intermediate Format: 352-pels by 288-lines and 30 frames/s). In addition, for the sake of 

comparison, we have simulated the Walker-Rao algorithm [2]. The simulation results of both 

schemes, in terms of mean square prediction error (in dB), are shown in Figures 1 and 2 for the 

 

d (x) = d (x) 2

 { [x, y, (x)}

 (16)

d (y) = d (y) { [x, y, (x)]}

i i-1

i i-1 2

- d

- d

ED

ED

LD

LD

2

2

ED

DFD

LD

DFD

i-1

i-1

∑ +

∑ +
5

“Salesman” and “Suzie” sequences respectively. In these figures we have also included the results 

of interframe prediction without motion compensation (i.e., frame difference). The number of 

iterations for both schemes was 3 and the threshold value was 9. In addition, these results were 

obtained using the second previous frame for prediction (i.e., skipping one frame). Looking at these 

figures, it can be clearly observed that the proposed scheme can significantly reduce the motion 

compensated prediction error. In terms of subjective evaluations, Figure 3 presents the motion 

compensated prediction error images between frames 49 and 51 of the “Suzie” sequence. In these 

images, relatively darker or lighter patches represent the degree of inaccuracies in estimating the 

components of the motion displacement. Comparing the two images confirms the performance 

superiority of the proposed scheme over the modified steepest-descent algorithm, particularly in the 

regions where the motion activities are relatively high.

Conclusion: This paper proposes an efficient pel-recursive estimation technique for motion

tracking and coding of moving images. The proposed algorithm has been compared with the 

modified steepest-descent gradient algorithm. The results indicate a considerable reduction in the 

prediction error, particularly in regions where the motion activities are relatively high. 

References

[1] A. N. Netravali and J. D. Robbins, "Motion compensated television coding- part I", Bell Syst. 

Tech. J., Vol. 58, pp. 631-670, Mar. 1979.

[2] D.R. Walker and K.r. Rao, “Improved Pel-recursive motion-estimation”, IEEE Trans. Commun, 

Vol. COM-32, No. 10, 1984, pp. 1128-1134
6

(a) (b)

Figure 1: Mean-square error performance using the second previous frame for prediction

(a) Salesman sequence, (b) Suzie sequence

(a) (b)

Figure 2: Motion compensated prediction error images for Suzie sequence

(a): Walker & Rao scheme (b): Proposed scheme.

Suzie Sequence

15 17 19 21 23 25 27 29

41 43 45 47 49 51 53 55 57 59 61 63 65

Frame number

Mean square error (dB)

No-MC Walker/Rao Proposed

 Salesman Sequence

10 12 14 16 18 20 22

49 51 53 55 57 59 61 63 65 67 69 71

Frame number

Mean square error (dB)

No-MC Walker/Rao Proposed