Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-09-14
2002-08-27
Kelley, Chris (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
06442202
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates motion estimation in video and film signal processing, in particular, to a technique for assessing the reliability of motion vectors.
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
) Equation 1
This leads directly to the contraint 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
Equation
2
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 these 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 temporal 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 ‘pixels’ 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 notion vector. One advantage of this invention is its ability to detect erroneous motion estimates due to vertical aliasing.
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 front 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 neighbouring 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;
&AutoLeftMatch;
[
σ
xx
2
σ
xy
2
σ
xy
2
σ
yy
2
]
·
[
u
0
v
0
]
=
-
[
σ
xt
2
σ
yt
2
]
where
σ
xx
2
=
∑
∂
I
∂
x
·
∂
I
∂
x
,
σ
xy
2
=
∑
∂
I
∂
x
·
∂
I
∂
y
etc
Equation
3
where (u
0
, v
0
) is the best fit motion vector and the summations are over a suitable region. This is an example of the well known technique of linear regression analysis detailed, for example, in reference 19 and many other texts. 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
]
Equation
4
Analysing small image regions produces 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 convert
Kelley Chris
Leitch Europe Limited
Votu Tung
LandOfFree
Motion vector field error 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 Motion vector field error estimation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Motion vector field error estimation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2965022