Cryptography Reference
In-Depth Information
to compute the average difference as the block size is always fixed. Instead,
we use sum of absolute difference (SAD), which is the same as Equation (2.8)
without dividing 1616.
The search area is defined around an MB in the current frame to cover
any motion between successive frames. The full search motion estimation
algorithm is the most straightforward block-matching algorithm, which can
give the optimal estimation in terms of minimizing matching error by checking
all candidates one by one. However, for a search area of 3232 pixels, the total
number of pixel to pixel comparison would be (28+1)
2
16
2
= 73984. For a
30 Hz SDTV format of video signal, we need to perform 70457625/16/16 =
39600 block based motion estimations in a single second this is equivalent
to 7398439600 = 2.93 billion pixel to pixel comparisons in one second.
Therefore full search motion estimation is a very expensive process.
Numerous efforts have been made to find fast block-matching algorithms.
Most of these methods assume that in the video sequence, objects move in
translation in a plane parallel to camera plane, illumination is spatially and
temporally uniform, and occlusion among objects are neglected. Fast motion
estimation algorithms use different block-matching strategies and search pat-
terns with various sizes and shapes, such as two dimensional logarithmic
search [11], three-step search [12], four-step search [13], diamond search [14]
and hexagon-based search [15], etc.
(a) Frame 229 of 'garden'
(b) Motion vectors for each MB
Fig. 2.12.
Example of motion vectors.
Fig. 2.12 shows the 229
th
frame of sequence garden and its motion vec-
tors. It can be seen from this figure that the motion vectors are usually very
small, and are uniform in most of the area. Therefore it can be further com-
pressed using DPCM coding following by entropy coding.
