International Conference on
Information, Communications and Signal Processing
ICICS '97
Singapore, 9-12 September 1997
1D2.5
A
New Diamond Search Algorithm for
Fast
Block
Matching Mot ion Estimation
Shan
Zhu
t
and Kai-Kuang Ma
1
School
of
Electrical and Electronic Engineering
Nanyang Technological University
Nanyang Avenue, Singapore
639798
Republic
of
Singapore
t
Email: saint-jose@bigfoot.com
$
Email: ekkma@ntu.edu.sg
Abstract
Based on the analysis of certain existing fast block-
matching algorithms
(BMAs)
and study of motion vec-
tor distributions
of
real-world image sequences,
a
new
diamond search
(DS)
algorithm for fast block-matching
motion estimation is proposed in this paper. Simula-
tion results demonstrate that the proposed
DS
algorithm
greatly outperforms the well-known three-step search
(TSS)
algorithm. Compared with the new three-step
search (NTSS) algorithm, the
DS
algorithm achieves
similar performance but requires approximate 20%-25%
less computation. Compared with some recently pro-
posed fast BMAs, such as the four-step search (4SS)
and the block-based gradient descent search (BBGDS)
,
our
DS
algorithm also shows its superiority.
1
Introduction
Due to limited channel bandwidth and stringent re-
quirements of real-time video playback] video coding is
an indispensable process for many visual communica-
tion applications and always requires
a
very high com-
pression ratio. The high temporal correlation, or
so-
called
redundancy
from the compression viewpoint, be-
tween adjacent frames in an image sequence, requires
to be properly identified and eliminated to achieve this
objective. An effective and popular technique to re-
duce the temporal redundancy, called
block-matching
motzon estzmatzon,
has been widely adopted in various
video coding standards, such as CCITT (now ITU-T)
H.261, H.263, MPEG-1 and MPEG-2
111.
In fact, block-
matching motion estimation is instrumental to any
motion-compensated video coding technique. Therefore,
fast algorithms for block matching are highly desirable.
By exhaustively testing all the candidate blocks
within the search window,
full search
(FS)
algorithm
gives the global minimum block distortion (MBD) po-
sition which corresponds to the best matching block.
However,
a
substantial computational load is demanded.
To overcome this drawback, many fast BMAs have
been developed, for examples, 2-0
logarithmzc search
(LOGS)
[2],
three-step search
(TSS) [3],
conjugate dz-
rection search
(CDS)
[4],
cross search
(CS)
[5],
dy-
namic search-wzndow adjustment
(DSWA) search [6]
new three-step search
(NTSS)
[7],
four-step search
(42%)
[8]
,
block-based gradzent descent search
(BBGDS)
[9]
,
etc.
Based on the analysis of the above-mentioned fast
BMAs and study of motion vector distribution from
several commonly used real-world test image sequences,
a new
diamond search
(DS)
algorithm for fast block-
matching motion estimation is proposed in this paper.
It
will be shown that our
DS
algorithm greatly outper-
forms the well-known TSS algorithm and works better
than NTSS,
4SS
and
BBGDS
on average, in terms of
error performance and computational complexity.
2
Observations
The main objective
of
fast BMAs
[2]-[9]
is to search for
an optimum or near-optimum solution with drastically
reduced number of search points which is constantly re-
quired in the
FS
algorithm. The shape and size of search
patterns exploited by the fast BMAs jointly determines
not only the error performance but also the computa-
tion complexity. Due to the multiple local
MBD
points
located in the search window, searching with
a
small
search pattern (for example, t,he pattern exploited in
BBGDS
[9]
with size of
3
x
3) is quite likely to be trapped
into
a
local minimum and hence deteriorates the perfor-
mance especially for those image sequences with large
motion content.
On the other hand, a large search pattern exploited
by TSS [3] with size of
9
x
9 an ine sparse check-
ing points is quite likely to mislead the search path
to
a
wrong direction and hence miss the optimum point,.
Since the distribution of the global minimum point in
real-world video is centered
at
zero [7],
a
center-biased
TSS algorithm, called NTSS [7], tends to achieve bet-
ter performance because it has a higher possibility to
catch the global optimum point. The average number
of search points in
NTSS
is fewer than that of TSS, how-
ever NTSS loses the regularity and simplicity
nf
TSS
to
0-7803-3676-3/97/$10.00
0
1997
IEEE
292
Authorized licensed use limited to: Shanghai Jiao Tong University. Downloaded on May 15, 2009 at 07:50 from IEEE Xplore. Restrictions apply.
