Image analysis – Image compression or coding – Interframe coding
Reexamination Certificate
1999-11-12
2003-04-29
Johnson, Timothy M. (Department: 2623)
Image analysis
Image compression or coding
Interframe coding
C375S240130
Reexamination Certificate
active
06556718
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to video picture compression techniques, and, more particularly, to an algorithm for optimizing performance of a motion estimation system and for optimizing a discrete cosine transform (DCT) of the video data in compression and coding phases.
BACKGROUND OF THE INVENTION
The set of pixels of a field of a picture may be placed in a position of a subsequent picture obtained by translating the preceding one. These transpositions of objects may expose to the video camera parts that were not visible before as well as changes of their contours, such as during zooming, for example. The family of algorithms suitable to identify and associate these portions of images is generally referred to as motion estimation. Such an association permits calculation of the portion of a difference image by removing the redundant temporal information. This makes the subsequent process of compression by discrete cosine transform, quantization and entropy coding more effective.
A typical example of such a method is found in the MPEG-2 standard. In consideration of the importance of such a widely adapted standard, and by way of example, reference will be made in the following description to the MPEG-2 standard for making the illustration easier to follow. The considerations that will be made remain valid for other standards and for motion estimation systems.
A typical block diagram of a video MPEG-2 coder is depicted in FIG.
1
. Such a system is made up of the following functional blocks:
Field ordinator. This block is composed of one or several field memories outputting the fields in the coding order required by the MPEG standard. For example, if the input sequence is I B B P B B P etc., the output order will be I P B B P B B . . .
I (Intra coded picture) is a field and/or a semifield containing temporal redundancy;
P (Predicted-picture) is a field and/or semifield from which the temporal redundancy with respect to the preceding I or P (previously codecoded) has been removed;
B (Bidirectionally predicted-picture) is a field and/or a semifield whose temporal redundancy with respect to the proceeding I and subsequent P (or preceding P and successive P) has been removed. In both cases the I and P pictures must be considered as already co/decoded.
Each frame buffer in the format 4:2:0 occupies the following memory space:
standard PAL
720 × 576 × 8 for the luminance (Y) =
3,317,760 bits
360 × 288 × 8 for the chrominance (U) =
829,440 bits
360 × 288 × 8 for the chrominance (V) =
829,440 bits
total Y + U + V =
4,976,640 bits
standard NTSC
720 × 480 × 8 for the luminance (Y) =
2,764,800 bits
360 × 240 × 8 for the chrominance (U) =
691,200 bits
360 × 240 × 8 for the chrominance (V) =
691,200 bits
Total Y + U + V =
4,147,200 bits
Motion Estimator. This block removes the temporal redundancy from the P and B pictures. This functional block operates only on the most energetic components of the sequence to be coded, i.e., the richest of picture information, such as the luminance component.
DCT. This block implements the discrete cosine transform (DCT) according to the MPEG-2 standard. The I picture and the error pictures P and B are divided in 8*8 blocks of pixels Y, U, V onto which the DCT is performed.
Quantizer Q. An 8*8 block resulting from the DCT is then divided by a quantizing matrix to reduce the magnitude of the DCT coefficients. In such a case, the information associated to the highest frequencies less visible to human sight tends to be removed. The result is reordered and sent to the successive block.
Variable Length Coding (VLC). The codification words output from the quantizer tend to contain a large number of null coefficients, followed by non-null values. The null values preceding the first non-null value are counted and the count figure constitutes the first portion of a codification word, the second portion of which represents the non-null coefficient.
These paired values tend to assume values more probable than others. The most probable ones are coded with relatively short words, e.g., composed of 2, 3 or 4 bits, while the least probable are coded with longer words. Statistically, the number of output bits is less than in the case such methods are not implemented.
Multiplexer and Buffer. Data generated by the variable length coder, the quantizing matrices, the motion vectors and other syntactic elements are assembled for constructing the final syntax contemplated by the MPEG-2 standard. The resulting bitstream is stored in a memory buffer. The size limit of the memory buffer is defined by the MPEG-2 standard, and cannot be overfilled. The quantizer block Q supports this limit by adjusting the division of the DCT 8*8 blocks. This division is based on the space available in the memory buffer, and on the energy of the 8*8 source block taken upstream of the motion estimation and the DCT process.
Inverse Variable Length Coding (I-VLC). The variable length coding functions specified above are executed in an inverse order.
Inverse Quantization (IQ). The words output by the I-VLC block are reordered in the 8*8 block structure, which is multiplied by the same quantizing matrix that was used for its preceding coding.
Inverse DCT (I-DCT). The DCT function is inverted and applied to the 8*8 block output by the inverse quantization process. This permits passing from the domain of spatial frequencies to the pixel domain.
Motion Compensation and Storage. Two pictures may alternatively be present at the output of the I-DCT block. First alternative is a decoded I picture or semipicture that must be stored in a respective memory buffer for removing the temporal redundancy from subsequent P and B pictures. A second alternative is a decoded prediction error picture (semipicture) P or B that must be summed to the information removed previously during the motion estimation phase. In case of a P picture, such a resulting sum stored in a dedicated memory buffer is used during the motion estimation process for the successive P pictures and B pictures. These field memories are generally distinct from the field memories that are used for re-arranging the blocks.
Display Unit. This unit converts the pictures from the format 4:2:0 to the format 4:2:2 and generates the interlaced format for displaying the images. The most energetic and therefore richer of information component, such as the luminance, is represented as a matrix of N lines and M columns. Each field is divided in portions called macroblocks, with each portion having R lines and S columns. The results of the divisions N/R and M/S must be two integer numbers, but not necessarily equal to each other.
Upon referring to
FIG. 2
a
, two subsystems which include the estimator block shown in
FIG. 1
are the following:
a) Motion estimator. This first subblock searches the predictors of each macroblock according to a certain estimation algorithm and decides, among the different predicting options described by the standard, the one that yields the best results. It supplies the successive block and the final buffer with the motion vectors and the type of prediction selected.
The prediction forms for the different types of fields are as follows. For the Intra fields, the prediction forms include Intra, P fields, Forward field, Frame field and Dual prime. For the B fields, the prediction forms include Field Forward, Field Backward, Filed Interpolated, Frame Forward, Frame Backward and Frame Interpolated
b) Decider. This sub-block is the part of the estimator that selects the coding mode of the single macroblocks, as well as the transform mode in the domain of the frequencies of the prediction errors relative to each one of them. The coding mode for the Intra fields are Intra. The different coding modes for the P fields are Intra, Forward Predictive and No motion compensated. The different coding modes for the B fields are Intra, For
Pau Danilo
Pezzoni Luca
Piccinelli Emiliano
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Johnson Timothy M.
Jorgenson Lisa K.
STMicroelectronics S.r.l.
LandOfFree
Video pictures compression and coding with decision step for... 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 pictures compression and coding with decision step for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Video pictures compression and coding with decision step for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3001145