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

260 Appendix. Fast Block-Matching Algorithms

• It is assumed that the search procedure keeps a record of all locations
searched so far and their BDM values. This avoids reevaluating the same
BDMs in subsequent steps.

A.2 The Two-Dimensional Logarithmic (TDL) Search

The two-dimensional logarithmic (TDL) search was proposed by Jain and
Jain in 1981 [54]. It uses a uniform search pattern of #ve locations (the
center and endpoints of a + shape). At each step, the search pattern is
centered at the minimum location from the previous step. The step size is
halved if the center of the search is the same as that of the previous step.
The search is stopped when the step size is 1. In this case, nine locations,
rather than #ve, are searched (the center and endpoints of a ∗ shape) to #nd
the #nal motion vector. The TDL algorithm is described in the following
procedure.

1. Initialize the search step size to
s = max(2; 2 log 2 d m −1 ):

2. Initialize the center of search to the origin of the search window:
(c x;c y )=(0; 0):
3. Evaluate the BDM at the center of the search and its four vertical and horizontal neighbors
at a step size of s. Out of this set of #ve locations, #nd the one that achieves the minimum
BDM:
(m x;m y ) = arg min BDM(i; j);
(i; j) ∈ P 1
where
P 1 = {(c x;c y ); (c x + s; c y ); (c x − s; c y ); (c x;c y + s); (c x;c y − s)}:
4. IF the minimum is at the center of the search pattern, i.e., if (m x;m y )=(c x;c y ),
THEN
(a) Halve the search step size:
s
s = :
2
(b) IF the search step size is 1, i.e., if s =1, THEN
i. Evaluate the BDM at the center of the search and its eight immediate neigh-
bors. Out of this set of nine locations, set the motion vector to the one that
achieves the minimum BDM:
(d x;d y ) = arg min BDM(i; j);
(i; j) ∈ P 2