Image analysis – Applications – Motion or velocity measuring
Reexamination Certificate
1998-09-14
2002-02-05
Boudreau, Leo (Department: 2621)
Image analysis
Applications
Motion or velocity measuring
C382S100000, C073S488000, C356S027000
Reexamination Certificate
active
06345106
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a technique for estimating motion vectors for a video or film sequence and may be used for example in a motion estimator for use with a standards converter or a video compression system.
2. Description of the Related Art
Gradient motion estimation is one of three or four fundamental motion estimation techniques and is well known in the literature (references 1 to
18).
More correctly called ‘constraint equation based motion estimation’ it is based on a partial differential equation which relates the spatial and temporal image gradients to motion.
Gradient motion estimation is based on the constraint equation relating the image gradients to motion. The constraint equation is a direct consequence of motion in an image. Given an object, ‘object(x, y)’, which moves with a velocity (u, v) then the resulting moving image, I (x, y, t) is defined by Equation 1;
I
(
x,y,t
)=object (
x−ut, y−vt
)
This leads directly to the constraint equation, Equation 2;
u
∂
I
(
x
,
y
,
t
)
∂
x
+
v
∂
I
(
x
,
y
,
t
)
∂
y
+
∂
I
(
x
,
y
,
t
)
∂
t
=
∂
object
(
x
,
y
)
∂
t
=
0
where, provided the moving object does not change with time (perhaps due to changing lighting or distortion) then ∂object/∂t=0. This equation is, perhaps, more easily understood by considering an example. Assume that vertical motion is zero, the horizontal gradient is +2 grey levels per pixel and the temporal gradient is −10 grey levels per field. Then the constraint equation says that the ratio of horizontal and temporal gradients implies a motion of 5 pixels/field. The relationship between spatial and temporal gradients is summarised by the constraint equation.
To use the constraint equation for motion estimation it is first necessary to estimate the image gradients; the spatial and temporal gradients of brightness. In principle there are easily calculated by applying straightforward linear horizontal, vertical and temporal filters to the image sequence. In practice, in the absence of additional processing, this can only really be done for the horizontal gradient. For the vertical gradient, calculation of the brightness gradient is confused by interlace which is typically used for television pictures; pseudo-interlaced signals from film do not suffer from this problem. Interlaced signals only contain alternate picture lines on each field. Effectively this is vertical sub-sampling resulting in vertical aliasing which confuses the vertical gradient estimate. Temporally the situation is even worse, if an object has moved by more than 1 pixel in consecutive fields, pixels in the same spatial location may be totally unrelated. This would render any gradient estimate meaningless. This is why gradient motion estimation cannot, in general, measure velocities greater than 1 pixel per field period (reference 8).
Prefiltering can be applied to the image sequence to avoid the problem of direct measurement of the image gradients. If spatial low pass filtering is applied to the sequence then the effective size of ‘pixel’ is increased. The brightness gradients at a particular spatial location are then related for a wider range of motion speeds. Hence spatial low pass filtering allows higher velocities to be measured, the highest measurable velocity being determined by the degree of filtering applied. Vertical low pass filtering also alleviates the problem of vertical aliasing caused by interlace. Alias components in the image tend to be more prevalent at higher frequencies. Hence, on average, low pass filtering disproportionately removes alias rather than true signal components. The more vertical filtering that is applied the less is the effect of aliasing. There are, however, some signals in which aliasing extends down to zero frequency. Filtering cannot remove all the aliasing from these signals which will therefore result in erroneous vertical gradient estimates and, therefore, incorrect estimates of the motion vector.
Prefiltering an image sequence results in blurring. Hence small details in the image become lost. This has two consequences, firstly the velocity estimate becomes less accurate since there is less detail in the picture and secondly small objects cannot be seen in the prefiltered signal. To improve vector accuracy hierarchical techniques are sometimes used. This involves first calculating an initial, low accuracy, motion vector using heavy prefiltering, then refining this estimate to higher accuracy using less prefiltering. This does, indeed, improve vector accuracy but it does not overcome the other disadvantage of prefiltering, that is, that small objects cannot be seen in the prefiltered signal, hence their velocity cannot be measured. No amount of subsequent vector refinement, using hierarchical techniques, will recover the motion of small objects if they are not measured in the first stage. Prefiltering is only advisable in gradient motion estimation when it is only intended to provide low accuracy motion vectors of large objects.
Once the image gradients have been estimated the constraint equation is used to calculate the corresponding motion vector. Each pixel in the image gives rise to a separate linear equation relating the horizontal and vertical components of the motion vector and the image gradients. The image gradients for a single pixel do not provide enough information to determine the motion vector for that pixel. The gradients for at least two pixels are required. In order to minimise errors in estimating the motion vector it is better to use more than two pixels and find the vector which best fits the data from multiple pixels. Consider taking gradients from 3 pixels. Each pixel restricts the motion vector to a line in velocity space. With two pixels a single, unique, motion vector is determined by the intersection of the 2 lines. With 3 pixels there are 3 lines and, possibly, no unique solution. This is illustrated in FIG.
1
. The vectors E
1
to E
3
are the error from the best fitting vector to the constraint line for each pixel.
One way to calculate the best fit motion vector for a group of neighouring pixels is to use a least mean square method, that is minimising the sum of the squares of the lengths of the error vectors E
1
to E
3
FIG.
1
. The least mean square solution for a group of neighbouring pixels is given by the solution of Equation 3;
[
σ
xx
2
σ
xy
2
σ
xy
2
σ
yy
2
]
·
[
u
0
v
0
]
=
-
[
σ
x1
2
σ
y1
2
]
where
σ
xx
2
=
∑
∂
I
∂
x
·
∂
I
∂
x
,
σ
xy
2
=
∑
∂
I
∂
x
·
∂
I
∂
y
etc
where (u
0
, v
0
) is the best fit motion vector and the summations are over a suitable region. The (direct) solution of equation 3 is given by Equation 4;
[
u
0
v
0
]
=
1
σ
xx
2
σ
yy
2
-
σ
xy
4
[
σ
xy
2
σ
yt
2
-
σ
yy
2
σ
xt
2
σ
xy
2
σ
xt
2
-
σ
xx
2
σ
yt
2
]
Small regions produce detailed vector fields of low accuracy and vice versa for large regions. There is little point in choosing a region which is smaller than the size of the prefilter since the pixels within such a small region are not independent.
Typically, motion estimators generate motion vectors on the same standard as the input image sequence. For motion compensated standards converters, or other systems performing motion compensated temporal interpolation, it is desirable to generate motion vectors on the output image sequence standard. For example when converting between European and American television standards the input image sequence is 625 line 50 Hz (interlaced) and the output standard is 525 line 60 Hz (interlaced). A motion compensated standards converter operating on a European input is required to produce motion vectors on the American output television stand
Boudreau Leo
Choobin Mahmood
Innovision Limited
Young & Thompson
LandOfFree
Gradient based motion estimation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Gradient based motion estimation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Gradient based motion estimation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2983514