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

262 Appendix. Fast Block-Matching Algorithms

5. IF the search step size is 1, i.e., if s =1, THEN
(a) Set the #nal motion vector to the minimum location found so far:

(d x;d y )=(m x;m y ):
(b) STOP.
6. ELSE (when the step size is not 1, i.e. s =1)

(a) Halve the step size: s
s = :
2
(b) Set the center of the search to the minimum location:
(c x;c y )=(m x;m y ):
(c) GOTO step 4.

A.4 The One-at-a-Time Search (OTS)

The one-at-a-time search (OTS) was proposed by Srinivasan and Rao in 1985
[146]. It uses two #xed-size uniform patterns. The search starts using a hori-
zontal pattern of one center location and its immediate left and right neighbors.
At each step, this search pattern is moved horizontally and centered at the min-
imum location from the previous step. This continues until the minimum is in
the center of the pattern (i.e., the minimum is the same as that of the previous
step). In this case, the search switches to the vertical direction using a pattern
of one center location and its immediate top and bottom neighbors. This is
explained in the following procedure.
1. Initialize the center of search to the origin of the search window:
(c x;c y )=(0; 0):
2. Evaluate the BDM at the center of the search and its immediate left and right 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 h
where
P h = {(c x;c y ); (c x +1;c y ); (c x − 1;c y )}:

3. IF the minimum is at the center of the search pattern, i.e., (m x;m y )=(c x;c y ), THEN GOTO
step 5 (i.e., vertical direction).
4. ELSE
(a) Move the center of the search to the new minimum location:
(c x;c y )=(m x;m y ):
(b) GOTO step 2 (i.e., continue in the horizontal direction).