Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1999-10-27
2003-01-14
Kelley, Chris (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
06507617
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to video data encoding and decoding, and more particularly relates to the compression and decompression of video data using motion compensated prediction.
A schematic diagram of a video coding system using motion compensated prediction is shown in FIG.
1
and
FIG. 2
of the accompanying drawings.
FIG. 1
illustrates an encoder and
FIG. 2
illustrates a corresponding decoder. Motion compensated prediction in such a system is outlined below.
In typical video sequences the change in the content of successive frames is to a great extent the result of the motion in the scene. This motion may be due to camera motion or due to motion of an object depicted in the scene. Therefore, typical video sequences are characterised by significant temporal correlation, which is highest along the trajectory of the motion, and efficient compression of video sequences requires exploitation of this property of video sequences. Motion compensated (MC) prediction is a widely recognised technique for compression of video. It utilises the fact that in a typical video sequence, the image intensity value in a particular frame can be predicted using image intensities of some other already coded frame, given the motion trajectory between these two frames.
In the encoder shown in
FIG. 1
the Motion Estimation block calculates motion vectors (&Dgr;x(x,y),&Dgr;y(x,y)) of pixels between the frame being coded I
n
(x,y), called the current frame, and a reference frame denoted R
ref
(x,y).
The reference frame is one of the previously coded frames (e.g. the frame preceding the one being coded) which at a given instant is available in the Frame Memory of the encoder and of the decoder. The pair of numbers (&Dgr;x(x,y),&Dgr;y(x,y)) is called the motion vector of the pixel at location (x,y) in the current frame, and &Dgr;x(x,y) and &Dgr;y(x,y) are the values of horizontal and vertical displacement, respectively.
The set of motion vectors of all pixels in the current frame, called a motion vector field, is compressed by the Motion Field Coding block and transmitted to the decoder. To indicate that the compression of the motion vector field is typically lossy the compressed motion vectors are denoted as ({tilde over (&Dgr;)}x(x,y),{tilde over (&Dgr;)}y(x,y)). In the Motion Compensated (MC) Prediction block, the compressed motion vectors ({tilde over (&Dgr;)}x(x,y),{tilde over (&Dgr;)}y(x,y)) and the reference frame are used to construct the prediction frame P
n
(x,y):
P
n
(
x,y
)=
R
ref
(
x+{tilde over (&Dgr;)}x
(
x,y
),
y+{tilde over (&Dgr;)}y
(
x,y
)). (1)
The prediction error, i.e., the difference between the current frame I
n
(x,y) and the prediction frame P
n
(x,y):
E
n
(
x,y
)=
I
n
(
x,y
)−
P
n
(
x,y),
(2)
is compressed and sent to the decoder. The compressed prediction error is denoted as {tilde over (E)}
n
(x,y).
In the decoder shown in
FIG. 2
pixels of the current coded frame Ĩ
n
(x,y) are reconstructed by finding the prediction pixels in the reference frame R
ref
(x,y) using the received motion vectors and by adding the received prediction error {tilde over (E)}
n
(x,y), i.e.,
Ĩ
n
(
x,y
)=
R
ref
(
x+{tilde over (&Dgr;)}x
(
x,y
),
y+{tilde over (&Dgr;)}y
(
x,y
)+
{tilde over (E)}
n
(
x,y
). (3)
Ĩ
n
(x,y) is not identical to I
n
(x,y), due to the loss introduced in coding. The difference between the coded frame and the original frame
D
n
(
x,y
)=
I
n
(
x,y
)−
Ĩ
n
(
x,y
) (4)
is called the reconstruction error.
An objective of motion compensated prediction is to find an optimum trade-off between the amount of information which needs to be transmitted to the decoder and the loss introduced in encoding, i.e.,
1. minimize the amount of prediction error, and
2. minimize the amount of information needed to represent motion vector field.
Due to the very large number of pixels in a frame it is not efficient to transmit a separate motion vector for each pixel. Instead, in most video coding schemes, the current frame is divided into larger image segments so that all motion vectors of the segment can be described by a few coefficients. Depending on the way the current frame is divided into the segments, two types of motion compensator coders can be distinguished;
1. Block based coders where the current frame is divided into fixed and known blocks e.g. 16×16 pixel blocks in International Standard ISO/IEC MPEG 1 or ITU-TH.T6 1 codecs (see
FIG. 3
a
), or
2. Segmentation based, i.e. region based, coders where the current frame is divided into arbitrarily shaped segments, e.g. obtained by a segmentation algorithm
FIG. 3
b.
A frame of a typical video sequence contains a number of objects with different motion. MC prediction is performed by dividing the frame I
n
(x,y) into several segments S
k
and estimating the motion of these segments between that frame and the reference frame R
ref
(x,y). In practice, a segment includes at least a few tens of pixels. In order to represent the motion vectors of these pixels compactly, it is desirable that their values are described by a function of few parameters. Such a function is called a motion vector field model. Motion compensated video coding schemes approximate the motion vectors of an image segment using a general formula:
Δ
^
x
(
x
,
y
)
=
∑
n
=
1
N
c
n
f
n
(
x
,
y
)
,
(
5
)
Δ
^
y
(
x
,
y
)
=
∑
n
=
N
+
1
N
+
M
c
n
f
n
(
x
,
y
)
,
(
6
)
where parameters c
n
are called motion coefficients and are compressed and transmitted to the decoder. The compressed motion coefficients will be denoted as {tilde over (c)}
n
. Functions f
n
are called basis functions and have to be known both to the encoder and decoder. Segmentation information is an inherent part of motion representation and it also needs to be coded and transmitted to the decoder. In the decoder, segmentation information and coefficients {tilde over (c)}
n
are used to obtain the compressed motion vector field for each segment:
Δ
~
x
(
x
,
y
)
=
∑
n
=
1
N
c
~
n
f
n
(
x
,
y
)
,
Δ
~
y
(
x
,
y
)
=
∑
n
=
N
+
1
N
+
M
c
~
n
f
n
(
x
,
y
)
.
(
7
)
In the encoder, the Motion Field Coding block aims to minimise the number of bits necessary for representation of the motion vector field while at the same time retaining low prediction error. The total number of bits needed to represent the motion vector field depends on:
the number of segments in the image,
the number of motion coefficients per segment,
the number of bits required to represent the motion coefficients.
A prior art system for performing Motion Field Coding is shown in
FIG. 4
, and consists of 4 main building blocks: a QR Motion Analyzer
1
, a Segment Merging block
2
, an Orthogonalization block
3
and a Motion Coefficient Removal block
4
. Such a system is described in PCT publications WO97/16025 and WO97/40628.
The inputs to the Motion Field Coding block are:
the motion vector field (&Dgr;x(x,y),&Dgr;y(x,y)) found by the Motion Estimation block,
the current frame,
a reference frame, and
initial segmentation of the current frame. The initial segmentation can be obtained in the encoder before or during Motion Estimation. The segmentation can also be provided to the encoder by some external means.
The Motion Field Coding block can reduce the total number of bits which have to be sent to the decoder by:
Reducing the number of segments by combining (merging) together those segments which can be predicted with a common vector of motion coefficients without causing a large increase of prediction error. The process of combining such segments is called motion assisted merging, and is performed by the Segment Merging block
2
.
Using basis functions which have low sensitivity to quantization (performed by the Quantisation block
5
) of corresponding motion coefficients so that these coefficients can be represented with a smal
Karczewicz Marta
Oktem Levent
Bugg George A.
Kelley Chris
Nokia Mobile Phones Ltd.
Perman & Green LLP
LandOfFree
Video coding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Video coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Video coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3068131