Digital Signal Processing Reference
In-Depth Information
image sequence contains moving objects, then the motion of
these objects within the scene can be measured, and the infor-
mation used to predict the location of the object in frames later in
the sequence.
Unfortunately, this is not as simple as just comparing regions
in one frame to another. If the background is constant, and
objects move in the foreground, there will be significant
unchanging areas of the frames. But, if the camera is panning
across a scene, there will be areas of subsequent frames that are
the same, but will have shifted location from frame to frame. One
way to measure this is to sum up all the absolute differences
(without regard to sign), pixel by pixel, between two frames. Then
the frame can be offset by one or more pixels, and the same
comparison run. After many such comparisons, the sum of
differences in the results can be compared, where the minimum
result corresponds to the best match, and provides the basis for
a method to determine the location offset of the match between
frames. This is known as the minimum absolute differences
(MAD) method, or sometimes it's referred to as sum of absolute
differences (SAD).
An alternative is the minimum mean square error (MMSE)
method, which measures the sum of the squared pixel differ-
ences. This method can be useful because it accentuates large
differences, due to the squaring, but the trade-off is the require-
ment for multiplies as well as subtractions.
14.1 Block Size
A practical trade-off has to be made when determining the
block size (or macroblock) over which the comparison is run. If
the block size is too small thereisnobenefitintryingtoreuse
pixel data from a previous frame rather than just use the
current frame data. If the block is too large, many more
differences will be likely, and it is difficult to get a close match.
One obvious block size to run comparisons across would be
the 8
8 block size used for DCT. Experimentation has shown
that a 16
16 pixel area works well, and this is commonly
used.
The computational efforts of running these comparisons can
be enormous. For each macroblock, 256 pixels must be compared
against a 16
16 area of the previous frame. If we assume the
macroblock data could shift by up to, for example, 256 pixels
horizontally or 128 pixels vertically (a portion of an HD
1080
1920) from one frame to another, there will be 256
