Question

(a) Describe 3-step search algorithm used in MPEG2 compression with the help of a diagram.

Answer 1

The three step search

reduces the number of candidate blocks and covers a large

area, making it a fast search technique.

In first step in TSS algorithm, compare nine search points

surrounding the center point with p step size equal to or large maximum searching area. In the second step, search

eight search points around best match among first step. In the

third step, again search eight points around best match

among second step. The best match from this third step is

chosen as the result of the search algorithm [8]. A description

of the three step search follows:

1. Search center location (0, 0).

2. Set step size S = 2N−1.

3. Search eight locations ±S pixels around the center (0,

0).

4. Pick the location with smallest SAD from nine

searching location and make this new search origin.

5. Set step size S = S/2.

6. Repeat step 3 to 5 until S=1.

Three Step Search (TSS) Algorithm Diagram:

1 1 1 3 3 3 1) 1 2 2 2 1

There are 25 search comparisons are required for finding

best match in TSS algorithm for motion estimation. In

general, (8N+ 1) comparisons are required for a search area

of +/- (2N - 1) pixels.