Image analysis – Color image processing – Compression of color images
Reexamination Certificate
1998-11-05
2001-02-20
Tadayon, Bijan (Department: 2721)
Image analysis
Color image processing
Compression of color images
C382S235000
Reexamination Certificate
active
06192148
ABSTRACT:
FIELD OF THE INVENTION
The present application pertains to encoding video.
BACKGROUND OF THE INVENTION
Several standards are available for encoding and decoding video to reduce the bandwidth of the video such as H.261, H.262, H.263, MPEG-1 and MPEG-2. These standards typically utilize both temporal and spatial compression. A to be encoded video picture (field or frame) is divided into non-overlapping macroblocks, where each macroblock is a two dimensional array of luminance blocks and each chrominance block overlapping thereon. Each luminance or chrominance block, in turn, is an 8×8 array of (luminance or chrominance) pixel data. In temporal encoding, one or more reference pictures are designated for each to be encoded video picture. For each macroblock of the to be temporally encoded video picture, a search is carried out, e.g., using a block matching technique, to identify a prediction macroblock in a reference picture which best matches the macroblock of the to be encoded picture. This is referred to as motion estimation. The prediction macroblock is identified by a motion vector which indicates a spatial (pixel row and column) and temporal (picture of the sequence) offset from the macroblock of the to be encoded picture to the prediction macroblock. A prediction error macroblock is then formed by subtracting the macroblock of the to be temporally encoded picture from the prediction macroblock. The individual blocks of the prediction error macroblock are then spatially encoded.
Spatial encoding involves the steps of discrete cosine transforming (orthogonally transforming) a block, quantizing the transformed block, and entropy encoding the quantized block (e.g., run-level encoding the quantized block and variable length encoding the run-level encoded block). The encoded data thus produced is formatted into a bitstream including other header, flag and parameter data.
According to the MPEG-2 standard, it is not strictly necessary to encode each macroblock. Rather, if a prediction error macroblock has a zero spatial offset motion vector, and only zero valued quantized block data, no data need be provided in the bitstream for the macroblock. Instead, indicator information is placed in the bitstream to indicate that a macroblock has been skipped.
It is an object of the present invention to provide an improved determination process for determining whether or not to skip a macroblock.
SUMMARY OF THE INVENTION
This and other objects is achieved by the present invention. According to one embodiment, a method is provided for encoding video pictures according to the following steps: (a) A sequence of video pictures is obtained. (b) Certain ones of the pictures of the sequence are designated for predictive encoding and one or more of the pictures of the sequence are designated as reference pictures for each picture designated for predictive encoding. (c) A picture designated for predictive encoding is divided into macroblocks. (d) The following steps are then iterated once for each i
th
macroblock of the picture designated for encoding: (e) The i
th
macroblock is motion estimated using only the luminance blocks of the i
th
macroblock. This produces a motion vector, indicating the temporal and spatial offset from the i
th
macroblock to a prediction macroblock in a designated reference picture, and the mean absolute difference of the luminance blocks of the i
th
macroblock and the luminance pixels of the prediction macroblock. The mean absolute difference is generated by evaluating:
∑
x
=
l
j
∑
y
=
l
k
&LeftBracketingBar;
P
i
Y
[
x
,
y
]
-
MB
i
Y
[
x
,
y
]
&RightBracketingBar;
where P
Y
i
is the luminance pixel data of the prediction macroblock for the i
th
macroblock, MB
Y
i
is the luminance pixel data of the i
th
macroblock and j and k are the number of rows and columns of luminance pixel data in a macroblock, respectively. (f) If the motion vector is zero and the mean absolute difference is below a first threshold, then the following steps (g), (h) and (i) are performed. Otherwise, only steps (j), (k), (l), (m) and (n) are performed. (g) The chrominance mean absolute difference between the chrominance blocks of the i
th
macroblock and the prediction macroblock is generated by evaluating:
∑
x
=
l
a
∑
y
=
l
b
&LeftBracketingBar;
P
i
Cr
[
x
,
y
]
-
MB
i
Cr
[
x
,
y
]
&RightBracketingBar;
+
∑
x
=
l
a
∑
y
=
l
b
&LeftBracketingBar;
P
i
Cb
[
x
,
y
]
-
MB
i
Cb
[
x
,
y
]
&RightBracketingBar;
where P
Cr
i
is the red chrominance pixel data of the prediction macroblock for the i
th
macroblock, MB
Cr
i
is the red chrominance pixel data of the i
th
macroblock, P
Cb
i
is the blue chrominance pixel data of the prediction macroblock for the i
th
macroblock, MB
Cb
i
is the blue chrominance pixel data of the i
th
macroblock and a and b are the number of rows and columns of red and blue chrominance pixel data in a macroblock, respectively. (h) If the chrominance mean absolute difference is less than a second threshold, then the following step (i) is performed. Otherwise, steps (j), (k), (l), (m) and (n) are performed. (i) An indication is inserted into the bitstream indicating that the i
th
macroblock is skipped. No further steps (namely, (j), (k), (l), (m) and (n)) are performed for the i
th
macroblock. On the other hand, if step (i) is not performed for the i
th
macroblock, the following steps (j), (k), (l), (m) and (n) are performed for the i
th
macroblock: (j) The luminance and chrominance blocks of the i
th
macroblock are subtracted from the prediction macroblock to form the prediction error macroblock for the i
th
macroblock. (k) Each block of the prediction error macroblock for the i
th
macroblock is then orthogonally transformed. (l) Each transformed block of the prediction error macroblock for the i
th
macroblock is quantized. (m) Each quantized block of the prediction error macroblock for the i
th
macroblock and the motion vector are entropy encoded. (n) The entropy encoded blocks of the prediction error macroblock and motion vector for the i
th
macroblock are then inserted into the encoded bitstream. Thus steps (j), (k), (l), (m) and (n) are not performed for the i
th
macroblock if step (i) is performed for the i
th
macroblock.
According to another embodiment, an encoding system is provided including a memory for temporarily storing pictures pending encoding and reference pictures, and a processor for performing the above steps.
The technique according to the invention is amenable for an encoder implemented as software executing on one or more processors. Specifically, the decision of whether or not to skip a macroblock is performed prior to the spatial encoding steps of orthogonally transforming, quantizing and entropy encoding. As orthogonal transforms are highly computationally intensive, a dramatic savings in processing time is achieved for a processor implementation, which additional time can be used to perform other encoding or non-encoding processing tasks.
REFERENCES:
patent: 2269070 (1942-01-01), White
patent: 5978029 (1999-11-01), Boice et al.
patent: 5984512 (1999-11-01), Jones et al.
Azarian Seyed
Proskauer Rose LLP
Tadayon Bijan
Winbond Electronics Corp.
LandOfFree
Method for determining to skip macroblocks in encoding video does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for determining to skip macroblocks in encoding video, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for determining to skip macroblocks in encoding video will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2574031