DIP 6620 Spring 2004 Final Project Paper 1
Abstract—This paper is a review of the block matching
algorithms used for motion estimation in video compression. It
implements and compares 7 different types of block matching
algorithms that range from the very basic Exhaustive Search to
the recent fast adaptive algorithms like Adaptive Rood Pattern
Search. The algorithms that are evaluated in this paper are
widely accepted by the video compressing community and have
been used in implementing various standards, ranging from
MPEG1 / H.261 to MPEG4 / H.263. The paper also presents a
very brief introduction to the entire flow of video compression.
Index Terms— Block matching, motion estimation, video
compression, MPEG, H.261, H.263
I. I
NTRODUCTION
ITH
the advent of the multimedia age and the spread of
Internet, video storage on CD/DVD and streaming
video has been gaining a lot of popularity. The ISO Moving
Picture Experts Group (MPEG) video coding standards pertain
towards compressed video storage on physical media like
CD/DVD, where as the International Telecommunications
Union (ITU) addresses real-time point-to-point or multi-point
communications over a network. The former has the advantage
of having higher bandwidth for data transmission.
In either standard the basic flow of the entire compression-
decompression process is largely the same and is depicted in
Fig. 1. The encoding side estimates the motion in the current
frame with respect to a previous frame. A motion compensated
image for the current frame is then created that is built of
blocks of image from the previous frame. The motion vectors
for blocks used for motion estimation are transmitted, as well
as the difference of the compensated image with the current
frame is also JPEG encoded and sent. The encoded image that
is sent is then decoded at the encoder and used as a reference
frame for the subsequent frames. The decoder reverses the
process and creates a full frame. The whole idea behind
motion estimation based video compression is to save on bits
by sending JPEG encoded difference images which inherently
have less energy and can be highly compressed as compared to
Manuscript received April 26, 2004. This work was done as partial
fulfillment for the completion of class ECE 6620, Digital Image Processing,
at Utah State University.
Aroh Barjatya is a graduate student with the ECE dept at Utah State
University, Logan Utah. 84322 (phone: 435-881-1616; e-mail:
arohb@cc.usu.edu).
sending a full frame that is JPEG encoded. Motion JPEG,
where all frames are JPEG encoded, achieves anything
between 10:1 to 15:1 compression ration, where as MPEG can
achieve a compression ratio of 30:1 and is also useful at 100:1
ratio [1] [2] [3]. It should be noted that the first frame is
always sent full, and so are some other frames that might occur
at some regular interval (like every 6
th
frame). The standards
do not specify this and this might change with every video
being sent based on the dynamics of the video.
The most computationally expensive and resource hungry
operation in the entire compression process is motion
estimation. Hence, this field has seen the highest activity and
research interest in the past two decades. This paper
implements and evaluates the fundamental block matching
algorithms from the mid-1980s up to the recent fast block
matching algorithms of year 2002. It also presents a literature
review of few papers from the last 3 years. The algorithms that
have been implemented are Exhaustive Search (ES), Three
Step Search (TSS), New Three Step Search (NTSS), Simple
and Efficient TSS (SES), Four Step Search (4SS), Diamond
Search (DS), and Adaptive Rood Pattern Search (ARPS).
Section II explains block matching in general and then the
above algorithms in detail. Section III compares them and
presents some simulation results. Section IV is a literature
survey of the more recent algorithms, followed by summary
and references.
Block Matching Algorithms
For Motion Estimation
Aroh Barjatya, Student Member, IEEE
W
Fig. 1. MPEG / H.26x video compression process flow.
- 1
- 2
- 3
- 4
前往页