On Image Matching and Feature Tracking for Embedded Systems: A State-of-the-Art - Advances in Heuristic Signal Processing and Applications - page 364

Fig. 16.10 Three-step search
(3SS) algorithm for tracking:
3 iterations with D = 8,

D 2pixelsfor

reaching the correlation
maximum

= 4, and D =

Fig. 16.11 NTSS algorithm
convolution principle

distances of D pixels. The algorithm selects the region with the largest correlation

score and calculates 8 new correlations at distances of

±

D/ 2 pixels from the center
of the selected region. The algorithm finds a correct match under the hypothesis that
surface defined by the values of the correlations is unimodal. The main drawback of
the TSS algorithm is that small motions can be missed because of the lower bound
on the step size and search window size.
A new three-step search (NTSS, N3SS, Fig. 16.11 ) algorithm [ 50 ], implemented
in the MPEG1/2/4 and H.261 standards, is more reliable. At initialization, the cor-
relation is calculated at 16 points: at a 3

±

× 3( S = 1 from the predicted match) and at

a D D from the predicted match) window. If the best correlation is found

in the initial prediction, the algorithm ends; otherwise, the point with the maximal
correlation score is selected as algorithm's new starting point and the whole corre-
lation process restarts with D replaced by D/ 2 (Note that some of the correlation
scores have already been calculated in the previous step).
Po and Ma [ 73 ] propose an improvement to NTSS (N3SS) named the four step
search algorithm (FSS, 4SS). Two square patterns of different sizes D

× D ( S =

1
(Fig. 16.12 , left and central), but with a common center, are used to select the pixels

= 2or D =