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

264 Appendix. Fast Block-Matching Algorithms

5. Evaluate the BDM at the center of the search and its four diagonal 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 − s); (c x + s; c y − s); (c x − s; c y + s); (c x + s; c y + s)}:
6. IF search step size is 1, i.e., if s =1, THEN
(a) IF the minimum (m x;m y ) is one of the three locations (c x;c y ), (c x − 1;c y − 1),
or (c x +1;c y + 1), THEN
i. Set the center of search to the minimum location:
(c x;c y )=(m x;m y ):
ii. Evaluate the BDM at the center of the search and its four horizontal and
vertical immediate neighbors. Out of this set of #ve 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
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)}:
iii. STOP.
(b) ELSE
i. Set the center of search to the minimum location:

(c x;c y )=(m x;m y ):
ii. Evaluate the BDM at the center of the search and its four diagonal imme-
diate neighbors. Out of this set of #ve 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 3
where
P 3 = {(c x;c y ); (c x − 1;c y − 1); (c x +1;c y − 1);
(c x − 1;c y +1); (c x +1;c y +1)}:
iii. STOP.
7. ELSE (when 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 5.