Processing for compression - The MPEG - page 90

One way of reducing the amount of computation is to perform the matching in stages where the first stage is
inaccurate but covers a large motion range but the last stage is accurate but covers a small range. The first
matching stage is performed on a heavily filtered and subsampled picture, which contains far fewer pixels. When a
match is found, the displacement is used as a basis for a second stage which is performed with a less heavily
filtered picture. Eventually the last stage takes place to any desired accuracy. This hierarchical approach does
reduce the computation required, but it suffers from the problem that the filtering of the first stage may make small
objects disappear and they can never be found by subsequent stages if they are moving with respect to their
background. Many televised sports events contain small, fast-moving objects. As the matching process depends
upon finding similar luminance values, this can be confused by objects moving into shade or fades.
The simple block-matching systems described above can only measure motion to the nearest pixel. If more
accuracy is required, interpolators will be needed to shift the image by sub-pixel distances before attempting a
match. The complexity rises once more. In compression systems an accuracy of half a pixel is accurate enough for
most purposes.
3.16.2 Gradient matching
At some point in a picture, the function of brightness with respect to distance across the screen will have a certain
slope, known as the spatial luminance gradient. If the associated picture area is moving, the slope will traverse a
fixed point on the screen and the result will be that the brightness now changes with respect to time. This is a
temporal luminance gradient. Figure 3.55 shows the principle. For a given spatial gradient, the temporal gradient
becomes steeper as the speed of movement increases. Thus motion speed can be estimated from the ratio of the
spatial and temporal gradients. [ 21 ]
Figure 3.55: The principle of gradient matching. The luminance gradient across the screen is compared with that
through time.
The method only works well if the gradient remains essentially constant over the displacement distance; a
characteristic which is not necessarily present in real video. In practice there are numerous processes which can
change the luminance gradient. When an object moves so as to obscure or reveal the background, the spatial
gradient will change from field to field even if the motion is constant. Variations in illumination, such as when an
object moves into shade, also cause difficulty.
The process can be assisted by recursion, in which the motion is estimated over a larger number of fields, but this
will result in problems at cuts.
3.16.3 Phase correlation
Phase correlation works by performing a discrete Fourier transform on two successive fields and then subtracting
all the phases of the spectral components. The phase differences are then subject to a reverse transform which
directly reveals peaks whose positions correspond to motions between the fields. [ 22 ][ 23 ] The nature of the transform
domain means that if the distance and direction of the motion is measured accurately, the area of the screen in
which it took place is not. Thus in practical systems the phase-correlation stage is followed by a matching stage not
dissimilar to the block-matching process. However, the matching process is steered by the motions from the phase
correlation, and so there is no need to attempt to match at all possible motions. By attempting matching on
measured motion the overall process is made much more efficient.
One way of considering phase correlation is that by using the Fourier transform to break the picture into its
constituent spatial frequencies the hierarchical structure of block matching at various resolutions is in fact