Page 284 - Video Coding for Mobile Communications Efficiency, Complexity, and Resilience

Section A.3. The N -Steps Search (NSS) 261

where
P 2 = {(c x;c y ); (c x +1;c y ); (c x − 1;c y ); (c x;c y +1); (c x;c y − 1);
(c x − 1;c y − 1); (c x − 1;c y +1); (c x +1;c y − 1); (c x +1;c y +1)}:
ii. STOP
(c) ELSE (when the step size is not 1, i.e., s =1) GOTO step 3.

5. ELSE (when the minimum is not in the center, i.e., (m x;m y ) =(c x;c y ))

(a) Set the center of the search to the new minimum location:
(c x;c y )=(m x;m y ):
(b) GOTO step 3.

A.3 The N -Steps Search (NSS)

This is the general form of the three-steps search (TSS) reported by Koga
et al. in 1981 [145]. It uses a uniform search pattern of nine locations (the
center and endpoints of a ∗ shape). At each step, the step size is halved
and the search pattern is centered at the minimum location from the previous
step. The search is stopped when the step size is 1. The TSS starts with
a step size of ± 4 pels in the #rst step, then ± 2 pels in the second step
and ± 1 pel in the third step. This gives a maximum allowed displacement of
± 4± 2± 1= ± 7 pels. For larger search windows the number of steps must be
increased. This is called the N -steps search and is described in the following
procedure.
1. Find the required number of steps N such that
N
2 N −1 ≤d m≤2 :
2. Initialize the search step size to
s =2 N −1 :
3. Initialize the center of search to the origin of the search window:
(c x;c y )=(0; 0):
4. Evaluate the BDM at the center of the search and its eight neighbors at a step size of s.
Out of this set of nine locations, #nd the one that achieves the minimum BDM:

(m x;m y ) = arg min BDM(i; j);
(i; j) ∈ P
where
P = {(c x;c y ); (c x + s; c y ); (c x − s; c y ); (c x;c y + s); (c x;c y − s);
(c x − s; c y − s); (c x − s; c y + s); (c x + s; c y − s); (c x + s; c y + s)}: