Tài liệu Image and Videl Comoression P11 ppt

12

© 2000 by CRC Press LLC

Pel Recursive Technique

As discussed in Chapter 10, the pel recursive technique is one of the three major approaches to

two-dimensional displacement estimation in image planes for the signal processing community.

Conceptually speaking, it is one type of region-matching technique. In contrast to block matching

(which was discussed in the previous chapter), it recursively estimates displacement vectors for

each pixel in an image frame. The displacement vector of a pixel is estimated by recursively

minimizing a nonlinear function of the dissimilarity between two certain regions located in two

consecutive frames. Note that region means a group of pixels, but it could be as small as a single

pixel. Also note that the terms pel and pixel have the same meaning. Both terms are used frequently

in the field of signal and image processing.

This chapter is organized as follows. A general description of the recursive technique is provided

in Section 12.1. Some fundamental techniques in optimization are covered in Section 12.2.

Section 12.3 describes the Netravali and Robbins algorithm, the pioneering work in this category.

Several other typical pel recursive algorithms are introduced in Section 12.4. In Section 12.5, a

performance comparison between these algorithms is made.

12.1 PROBLEM FORMULATION

In 1979 Netravali and Robbins published the first pel recursive algorithm to estimate displacement

vectors for motion-compensated interframe image coding. Netravali and Robbins (1979) defined a

quantity, called the displaced frame difference (DFD), as follows.

(12.1)

where the subscript n and n – 1 indicate two moments associated with two successive frames based

on which motion vectors are to be estimated; x, y are coordinates in image planes, dx, dy are the

two components of the displacement vector, , along the horizontal and vertical directions in the

image planes, respectively. DFD(x, y; dx, dy) can also be expressed as DFD(x, y; . Whenever it

does not cause confusion, it can be written as DFD for the sake of brevity. Obviously, if there is

no error in the estimation, i.e., the estimated displacement vector is exactly equal to the true motion

vector, then DFD will be zero.

A nonlinear function of the DFD was then proposed as a dissimilarity measure by Netravali

and Robbins (1979), which is a square function of DFD, i.e., DFD2.

Netravali and Robbins thus converted displacement estimation into a minimization problem.

That is, each pixel corresponds to a pair of integers (x, y), denoting its spatial position in the image

plane. Therefore, the DFD is a function of . The estimated displacement vector = (dx, dy)T

,

where ( )T denotes the transposition of the argument vector or matrix, can be determined by

minimizing the DFD2. This is a typical nonlinear programming problem, on which a large body

of research has been reported in the literature. In the next section, several techniques that rely on

a method, called descent method, in optimization are introduced. The Netravali and Robbins

algorithm can be applied to a pixel once or iteratively applied several times for displacement

estimation. Then the algorithm moves to the next pixel. The estimated displacement vector of a

pixel can be used as an initial estimate for the next pixel. This recursion can be carried out

DFD x y d d f x y f x d y d xy n n x y ( ) ,; , , , , = ( ) - -- -1( )

v

d v

d

v

d v

d