Digital Signal Processing Reference
In-Depth Information
TWO METHODS OF MOTION ESTIMATION
The calculation of the
motion field,
i.e., the projected motion over
the video space, must balance the optical flow constraint with
a pri-
ori
knowledge of the motion field characteristics. As mentioned in sec-
tion 2.4, we cannot determine two variables (x and y components of
projected motion) with only one constraint. Two methods of motion
estimation, block matching and optical flow balance the optimization of
the optical flow constraint with a smoothness criterion (see Figure 2.7)
to calculate the motion field.
METHOD 1: BLOCK MATCHING
Along with the optical flow constraint,
block matching
assumes that a
given neighborhood (usually, a n-by-n block) around a point moves with
the same motion. Under the assumption of a constant projected motion
over the neighborhood, we can determine the motion of a given neigh-
borhood by finding the Least Square Fit to the optical flow equation.
Block matching computation is as follows. By dividing the image re-
gion into a regular grid of n-by-n pixels, one can use a block-matching
algorithm to find the motion field for a given frame.
Let
us consider
the two frames of the video sequence,
I
current
(
x,y
)
=
I
(
x,g,t
)|
t=t
o
;
I
next
(
x,y
)
=
I
(
x,y,t
))
t=t
o
+
∆
t
.
For
simplicity,
consider
a
neighbor-
hood
N
that
is centered
around the origin
(for
a n-by-n
block,
N
=
n
n
2
n
n
{- ,..., } × (- ,..., }). From Eq. 2.1, we quantify the error of a
given motion vector by the intensity difference of the neighborhood (N)
of the current frame and an offset neighborhood in the next frame.
2
-
2
Σ
(
I
next
(
n
+
δ
) -
I
current
(
n
)
)
2
→
→
→
SS
D
(δ) =
→
(2.4)
N
where SSD is short for the Sum of Squared Difference,
n
is the 2-D offset
vector of each pixel in the neighborhood, and is the 2-D motion vector
that is constant over the neighborhood. To find the motion vector by
block matching, we wish to find arg min
(
→
n
→
→
δ
SSD
( )
)
. To compute the
→
δ
→
whole field, we repeat the calculation with the proper offset for each
block in the motion field. Assuming some upper limit on the magnitude
of the motion field velocity, the SSD minimization is generally computed
through an exhaustive search, although more efficient schemes do exist
[Chen et al., 1991] [Jain and Jain, 1981].
Problems with block matching are due to the assumption of constant
velocity over the neighborhood. In addition to the optical flow assump-
tions,
δ
the locality assumptions about
the neighborhood can be violated
as well because:
Search WWH ::
Custom Search