Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1999-01-08
2001-04-03
Rao, Andy (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240090
Reexamination Certificate
active
06212235
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to video compression. More precisely, the invention relates to an encoder and method for performing motion compensated encoding of video data. The invention also relates to a decoder for decoding video data thus encoded.
BACKGROUND OF THE INVENTION
Motion compensated prediction is a key element of the majority of video coding schemes.
FIG. 1
is a schematic diagram of an encoder for compression of video sequences using motion compensation. Essential elements in the encoder are a motion compensated prediction block
1
, a motion estimator
2
and a motion field coder
3
. The operating principle of the motion compensating video encoder is to compress the prediction error E
n
(x,y), which is a difference between the incoming frame I
n
(x,y) to be coded, called the current frame, and a prediction frame P
n
(x,y), wherein:
E
n
(
x,y
)=I
n
(
x,y
)−P
n
(
x,y
) (1)
Compression of the prediction error E
n
(x,y) typically introduces some loss of information. The compressed prediction error, denoted {tilde over (E)}
n
(x,y), is sent to the decoder. The prediction frame P
n
(x,y) is constructed by the motion compensated prediction block
1
and is built using pixel values of the previous, or some other already coded frame denoted R
ref
(x,y), called a reference frame, and motion vectors describing estimated movements of pixels between the current frame and the reference frame. Motion vectors are calculated by motion field estimators
2
and the resulting motion vector field is then coded in some way before applying it to the predictor block
1
. The prediction frame is then:
P
n
(
x,y
)=R
ref
[x+&Dgr;x
(
x,y
),
y+&Dgr;y
(
x,y
)] (2)
The pair of numbers [&Dgr;x(x,y), &Dgr;y(x,y)] is called the motion vector of a pixel in location (x,y) in the current frame, whereas &Dgr;x(x,y) and &Dgr;y(x,y) are the values of horizontal and vertical displacement of this pixel. The set of motion vectors of all pixels in the current frame I
n
(x,y) is called motion vector field. The coded motion vector field is also transmitted as motion information to the decoder.
In the decoder shown in
FIG. 2
, pixels of the current frame I
n
(x,y) are reconstructed by finding the pixels' predictions P
n
(x,y) from the reference frame R
ref
(x,y). The motion compensated prediction block
21
generates the prediction frame using the received motion information and the reference frame R
ref
(x,y). In the prediction error decoder
22
a decoded prediction error frame {tilde over (E)}
n
(x,y) is then added with the prediction frame, the result being the approximated current frame Ĩ
n
.
The general object of the motion compensated (MC) prediction encoder is to minimise the amount of information which needs to be transmitted to the decoder. It should minimise the amount of prediction error measured according to some criteria, e.g. the energy associated with E
n
(x,y), and minimise the amount of information needed to represent the motion vector field.
The document N. Nguen, E. Dubois, “Representation of motion information for image coding”. Proc. Picture Coding Symposium '90, Cambridge, Mass., Mar. 26-18, 1990, pages 841-845, gives a review of motion field coding techniques.
As a rule of the thumb, a reduction of prediction error requires a more refined sophisticated motion field, i.e. more bits must be spent on its encoding. Therefore the overall goal of the video encoding is to encode the motion vector field as compactly as possible keeping at the same time the measure of prediction error as low as possible.
Due to the very large number of pixels in the frame, it is not efficient to transmit a separate motion vector for each pixel. Instead, in most of the video coding schemes the current frame is divided into image segments, as shown for example in
FIG. 3
, so that all motion vectors of the segment can be described by a few parameters. Image segments can be square blocks. For example 16×16 pixel blocks are used in codecs in accordance with international standard ISO/IEC MPEG-1 or ITU-T H.261, or they can comprise completely arbitrarily shaped regions obtained for instance by a segmentation algorithm. In practice segments include at least a few tens of pixels.
The motion field estimation block
1
of
FIG. 1
calculates motion vectors of all the pixels of a given segment which minimise some measure of prediction error in this segment, for example the square prediction error. Motion field estimation techniques differ both in the model of the motion field and in the algorithm for minimisation of the chosen measure of prediction error.
In order to compactly represent the motion vectors of the pixels in the segments it is desirable that their values are described by a function of few parameters. Such a function is called a motion vector field model. A known group of models are linear motion models, in which motion vectors are approximated by linear combinations of motion field basis functions. In such models the motion vectors of image segments are described by a general formula:
Δ
x
(
x
,
y
)
=
∑
i
=
1
N
c
i
f
i
(
x
,
y
)
Δ
y
(
x
,
y
)
=
∑
i
=
N
+
1
N
+
M
c
i
f
i
(
x
,
y
)
(
3
)
where parameters c
i
are called motion coefficients and are transmitted to the decoder. Functions f
i
(x,y) are called motion field basis functions and they have a fixed form known to both encoder and decoder.
The problem when using the linear motion model having the above described formula is how to minimise in a computationally simple manner the number of motion coefficients c
i
which are sent to the decoder, keeping at the same time some measure of distortion, e.g. a chosen measure of prediction error E
n
(x,y), as low as possible.
The total amount of motion data which needs to be sent to the decoder depends both on the number of segments in the image and the number of motion coefficients per segment. Therefore, there exist at least two ways to reduce the total amount of motion data.
The first way is to reduce the number of segments by combining (merging) together those segments which can be predicted with a common motion vector field model without causing a large increase of prediction error. The number of segments in the frame can be reduced because very often adjacent, i.e. neighbouring, segments can be predicted well with the same set of motion coefficients. The process of combining such segments is called motion assisted merging.
FIG. 3
shows a frame divided into segments. The prior art techniques for motion coefficient coding include several techniques for motion assisted merging. After motion vectors of all the segments have been estimated, motion assisted merging is performed. It is done by considering every pair of adjacent segments S
i
and S
j
with their respective motion coefficients c
i
and c
j
. The area of combined segments S
i
and S
j
is denoted S
ij
. If the area S
ij
can be predicted with one set of motion coefficients c
ij
without causing excessive increase of prediction error over the error resulting from separate predictions of S
i
and S
j
, then S
i
and S
j
are merged. The methods for motion assisted merging differ essentially in the way of finding a single set of motion coefficients c
ij
which allow a good prediction of segments combined together.
One method is known as merging by exhaustive motion estimation. This method estimates “from scratch” a new set of motion parameters c
ij
for every pair of adjacent segments S
i
and S
j
. If the prediction error for S
ij
is not excessively increased then the segments S
i
and S
i
are merged. Although this method can very well select the segments which can be merged it is not feasible for implementation because it would increase the complexity of the encoder typically by several orders of magnitude.
Another method is known as merging by motion field extension. This method tests whether area of S
ij
Karczewicz Marta
Nieweglowski Jacek
Nokia Mobile Phones Ltd.
Perman & Green LLP
Rao Andy
LandOfFree
Video encoder and decoder using motion-based segmentation... 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 encoder and decoder using motion-based segmentation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Video encoder and decoder using motion-based segmentation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2546691