MULTIMEDIA COMMUNICATION
Motion Estimation
8th Semester ETC Engineering
Module-III, Unit-6
1
Motion Estimation
• Motion estimation is a process in which the
movement of objects in a sequence of images
or video frames is analyzed and quantified.
• The goal of motion estimation is to determine
how objects move from one frame to the next
in order to facilitate tasks such as video
compression, object tracking, and video
stabilization.
• The process of motion estimation involves
comparing two or more consecutive frames of
a video sequence to detect the changes in the
position, orientation, or shape of objects in
the scene.
• This comparison can be done at various levels
of granularity, from individual pixels to larger
regions of the image.
ME Apply to the Video Standard
Input Coder
Video Control
Signal Control
Data
Transform/
Quant.
Scal./Quant.
- Transf. coeffs
Decoder Scaling &
Split into
Macroblocks Inv.
16x16 pixels Transform
Entropy
Coding
De-blocking
Intra-frame Filter
Prediction
Output
Inter/Intra Motion- Video
Compensation Signal
Motion
Data
Motion
Estimation
Basic Structure for Video
Standard
Motion Estimation / Compensation
Motion Estimation: Estimates motion parameters of
moving objects in an image sequence.
— At the encoder.
Motion Compensation: Replaces a picture, or portion
thereof, based on displaced pels of a previously
transmitted frame in an image sequence.
— At the decoder.
Why Motion Compensation?
◼ Reduce interframe correlation in image sequence.
◼ Block motion compensation is adopted by the
international standards: H.261/H.263,
MPEG1/MPEG2,..
Summary
◼ Consecutive frames in a video are similar - temporal
redundancy exists.
◼ Temporal redundancy
▪ is exploited so that not every frame of the video needs to
be coded independently as a new image. The difference
between the current frame and other frame(s) in the
sequence will be coded - small values and low entropy,
good for compression
◼ Steps of Video compression based on Motion
Compensation (MC):
▪ 1. Motion Estimation (motion vector search).
▪ 2. MC-based Prediction.
▪ 3. encode prediction error, i.e., the difference.
6
Motion Estimation Techniques
For Image Sequence Coding
◼1969: Haskell and Limb filed a patent
◼1969: Rocca published a paper in
Picture Coding Symposium
◼Three major groups of approaches:
(i) Block matching methods
(ii) Differential (gradient) methods
(iii)Fourier methods
Motion Estimation Problem
◼ Moving object: A group of contiguous pels that
share the same set of motion parameters ─not
necessarily match the ordinary meaning of
object.
◼ Assumptions:
(i)Objects are rigid bodies; hence, object
deformation can be neglected for at least a few
nearby frames.
(ii)Objects move only in translational
movement for, at least, a few frames.
Motion Estimation Problem (cont.)
◼ Assumptions: (cont.)
(iii)Illumination is spatially and
temporally uniform; hence, the
observed object intensities are
unchanged under movement.
(iv)Occlusion of one object by another
and uncovered background are
neglected.
13
Block Matching Motion Estimation
◼ Basic Concept: A correlation technique that
searches for the best match between the current image
block and candidates in a confined area of the previous
frame ─ Essentially an object recognition method.
◼ Assumption: Images are partitioned into non-
overlapped rectangular blocks.
(i) Each block is viewed as an independent object.
(ii) The motion of pels within the same block is
uniform.
Term Definition
Terms: candidate blocks, current blocks,
search range/search window/search region,
motion vector
search points
Search Region/Search Range
Maximum horiz.and vert.displacements: dmax_ x and dmax_ y
Number of search points: (2d
max_ x
+1)(2dmax_ y +1)
Block Matching
◼ Parameters in a
search process: ME
a. Search strategy
(i) Number of
candidate blocks,
search points
(iii) Search order of
candidates
b. Matching function
c. block size
Full Search Algorithm
Pros and Cons of Block Matching
◼ Advantages of BMA (Block Matching Algorithm)
▪ Low overhead: one vector per block
▪ Straightforward, regular parallel procedure good for
VLSI implementation, Low cost VLSI implementation .
➢ Robust (immunity to noise)
◼ Disadvantages:
➢ A block may contain several moving objects.
➢ Minimizing a numerical criterion may not give us the
true movement
➢ Fail to zoom rotational motion, local deformation
▪ Blocking artifact
Fast Search
◼ Basic Principle: Break up the search process into a
few sequential steps. Choose the next-step search
direction based on the current-step result. At each
step, only a small number of search points are
calculated.
◼ Popular Fast Search Algorithms:
1. 2D-Log Search - Jain and Jain (1981)
2. Three Step Search - Koga et al. (1981)
3. Modified Log Search - Kappagantula and Rao
(1985)
4. One-at-a-time Search - Srinivasan and Rao (1985)
5. Conjugate Search - Puri, Hang and Schilling (1987)
21
Motion Vector (--3,2)
Three Step Search
The search starts with a step
size equal to or slightly
larger than half of the
maximum search range. In
each step, nine search
points are compared. The
step size is reduced by half
after each step, and the
search ends with the step
size of 1 pel. We need three
search steps for a maximum
search range between 4 to
7 pels and four steps for a
maximum range between 8
to 15 pels.
24
