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

Section A.5. The Cross-Search Algorithm (CSA) 263

5. Evaluate the BDM at the center of the search and its immediate top and bottom neighbors.
Out of this set of three locations, #nd the one that achieves the minimum BDM:

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

6. IF the minimum is at the center of the search pattern, i.e., (m x;m y )=(c x;c y ), THEN
(a) Set the #nal motion vector to the current minimum:
(d x;d y )=(m x;m y )

(b) STOP.
7. ELSE
(a) Move the center of the search to the new minimum location:
(c x;c y )=(m x;m y ):

(b) GOTO step 5 (i.e., continue in the vertical direction).

A.5 The Cross-Search Algorithm (CSA)

The cross-search algorithm (CSA) was proposed by Ghanbari in 1990 [147].
The search includes an early-termination criterion where, in the #rst step, a
threshold is used to detect if the block is stationary. The search starts with a
uniform pattern of #ve locations (the center and endpoints of an × shape). At
each step, the search 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. In this case, the search switches to one of two uniform patterns:
#ve locations using either an × shape or a + shape. This is explained in the
following procedure.
1. Evaluate BDM(0; 0).
2. IF BDM(0; 0) ¡ Threshold, THEN STOP.
3. Initialize the center of search to the origin of the search window:

(c x;c y )=(0; 0):
4. Initialize the search step size to half the maximum allowed displacement:
� �
s = d m :
2