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

Section A.6. The Diamond Search (DS) 265

A.6 The Diamond Search (DS)

The diamond search (DS) algorithm was proposed by Zhu and Ma in 1997
[150,151]. An identical version of the algorithm has also been proposed by
Tham et al. in 1998 [149]. The algorithm uses two #xed-search patterns. It
starts with a pattern of nine locations forming a diamond with a step size of
2. At each step, this search pattern is centered at the minimum location from
the previous step. This process 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 algorithm switches to the second pattern. This consists of #ve
locations forming a diamond with a step size of 1. This pattern is used only
once and the search is then terminated. 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 nine locations forming a diamond with a step size of 2 centered
at the current center location (c x;c y ). 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 d 1
where
= {(c x;c y ); (c x +2;c y ); (c x − 2;c y ); (c x;c y +2); (c x;c y − 2)
P d 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)}:
3. IF the minimum is at the center of the search pattern, i.e., (m x;m y )=(c x;c y ),
THEN
(a) Evaluate the BDM at #ve locations forming a diamond with a step size of 1
centered at the current center location (c x;c y ). 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 d 2
where
= {(c x;c y ); (c x +1;c y ); (c x − 1;c y ); (c x;c y +1); (c x;c y − 1)}:
P d 2
(b) STOP.
4. 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 2.