1. Technical Field
The present invention relates to computer and digital data compression, and more specifically to preventing rounding errors that can accumulate in MPEG-2 type decompression.
2. Description of the Prior Art
Digitized images require a large amount of storage space to store and a large amount of bandwidth to transmit. A single, relatively modest-sized image, having 480 by 640 pixels and a full-color resolution of twenty-four bits per pixel (three 8-bit bytes per pixel), occupies nearly a megabyte of data. At a resolution of 1024 by 768 pixels, a 24-bit color screen requires 2.3 megabytes of memory to represent. A 24-bit color picture of an 8.5 inch by 11 inch page, at 300 dots per inch, requires as much as twenty-five megabytes to represent.
Video images are even more data-intensive, since it is generally accepted that for high-quality consumer applications, images must occur at a rate of at least thirty frames per second. Current proposals for high-definition television (HDTV) call for as many as 1920 by 1035 or more pixels per frame, which translates to a data transmission rate of about 1.5 billion bits per second. This bandwidth requirement can be reduced somewhat if one uses 2:1 interleaving and 4:1 decimation for the xe2x80x9cUxe2x80x9d and xe2x80x9cVxe2x80x9d chrominance components, but 0.373 billion bits per second are still required.
Traditional lossless techniques for compressing digital image and video information, such as Huffman encoding, run length encoding and the Lempel-Ziv-Welch algorithm, are far from adequate to meet this demand. For this reason, compression techniques which can involve some loss of information have been devised, including discrete cosine transform techniques, adaptive discrete cosine transform techniques, and wavelet transform techniques. Wavelet techniques are discussed in DeVore, Jawerth and Lucier, Image Compression Through Wavelet Transform Coding, IEEE Transactions on Information Theory, Vol. 38, No. 2, pp. 719-746 (1992); and in Antonini, Barlaud, Mathieu and Daubechies, Image Coding Using Wavelet Transform, IEEE Transactions on Image Processing, Vol. 1, No. 2, pp. 205-220 (1992).
The Joint Photographic Experts Group (JPEG) has promulgated a standard for still image compression, known as the JPEG standard, which involves a discrete cosine transform-based algorithm. The JPEG standard is described in a number of publications, including the following incorporated by reference herein: Wallace, The JPEG Still Picture Compression Standard, IEEE Transactions on Consumer Electronics, Vol. 38, No. 1, pp. xviii-xxxiv (1992); Purcell, The C-Cube CL550 JPEG Image Compression Processor, C-Cube Microsystems, Inc. (1992); and C-Cube Microsystems, JPEG Algorithm Overview (1992).
An encoder using the JPEG algorithm has four steps: linear transformation, quantization, run-length encoding (RLE), and Huffman coding. The decoder reverses these steps to reconstitute the image. For the linear transformation step, the image is divided up into 8*8 pixel blocks and a Discrete Cosine Transform is applied in both spatial dimensions for each block. The purpose of dividing the image into blocks is to overcome a deficiency of the discrete cosine transform algorithm, which is that the discrete cosine transform is seriously non-local. The imager is divided into blocks in order to overcome this non-locality by confining it to small regions, and doing separate transforms for each block. However, this compromise has a disadvantage of producing a tiled appearance (blockiness) upon high compression.
The quantization step is essential to reduce the amount of information to be transmitted, though it does cause loss of image information. Each transform component is quantized using a value selected from its position in each 8*8 block. This step has the convenient side effect of reducing the abundant small values to zero or other small numbers, which can require much less information to specify.
The run-length encoding step codes runs of same values, such as zeros, in items identifying the number of times to repeat a value, and the value to repeat. A single item like xe2x80x9ceight zerosxe2x80x9d requires less space torepresent than a string of eight zeros, for example. This step is justified by the abundance of zeros that usually result from the quantization step.
Huffman coding translates each symbol from the run-length encoding step into a variable-length bit string that is chosen depending on how frequently the symbol occurs. That is, frequent symbols are coded with shorter codes than infrequent symbols. The coding can be done either from a preset table or one composed specifically for the image to minimize the total number of bits needed.
Similarly to JPEG, the Motion Pictures Experts Group (MPEG) has promulgated two standards for coding image sequences. The standards are known as MPEG-1 and MPEG-2. The MPEG algorithms exploit the common fact of relatively small variations from frame to frame. In the MPEG standards, a full image is compressed and transmitted only once for every twelve frames. The JPEG standard is typically used to compress these xe2x80x9creferencexe2x80x9d or xe2x80x9cintraxe2x80x9d frames. For the intermediate frames, a predicted frame is calculated and only the difference between the actual frame and the, predicted frame is compressed and transmitted. Any of several algorithms can be used to calculate a predicted frame, and the algorithm is chosen on a block-by-block basis depending on which predictor algorithm works best for the particular block. Motion detection can be used in some of the predictor algorithms. MPEG 1 is described in detail in International Standards Organization (ISO) CD 11172.
Accordingly, for compression of video sequences the MPEG technique is one which treats the compression of reference frames substantially independently from the compression of intermediate frames between reference frames. The present invention relates primarily to the compression of still images and reference frames for video information, although aspects of the invention can be used to accomplish video compression even without treating reference frames and intermediate frames independently.
The above techniques for compressing digitized images represent only a few of the techniques that have been devised. However, none of the known techniques yet achieve compression ratios sufficient to support the huge still and video data storage and transmission requirements expected in the near future. The techniques also raise additional problems, apart from pure compression ratio issues. In particular, for real time, high-quality video image decompression, the decompression algorithm must be simple enough to be able to produce thirty frames of decompressed images per second. The speed requirement for compression is often not as extreme as for decompression, since for many purposes, images can be compressed in advance. Even then, however, compression time must be reasonable to achieve commercial objectives. In addition, many applications require real time compression as well as decompression, such as real time transmission of live events. Known image compression and decompression techniques which achieve high compression ratios, often do so only at the expense of requiring extensive computations either on compression or decompression, or both.
The MPEG-2 video compression standard is defined in ISO/IEC 13818-2 xe2x80x9cInformation technologyxe2x80x94Generic coding of moving pictures and associated audio information: Videoxe2x80x9d. MPEG-2 uses motion compensation on fixed sized rectangular blocks of pixel elements (xe2x80x9cmacroblocksxe2x80x9d) to use temporal locality for improved compression efficiency. The location of these xe2x80x9cmacroblocksxe2x80x9d in the reference pictures is given on half pixel boundaries, and so requires an interpolation of pixel elements. Such interpolation is specified in the MPEG-2 standard, as follows:
The xe2x80x9c//xe2x80x9d operator at the ends of cases B, C, and D is defined in the MPEG-2 specification as: xe2x80x9cInteger division with rounding to the nearest integer. Half-integer values are rounded away from zero unless otherwise specified [ . . . ]xe2x80x9d. Therefore, when a two or a four are the right hand operand and the left hand operand is greater or equal zero, the operator xe2x80x9c//xe2x80x9d can be replaced according to: x//2=(x+1) greater than  greater than 1; x//4=(x+2) greater than  greater than 2, where xe2x80x9c greater than  greater than xe2x80x9d denotes a binary right shift of the left hand operator by the right hand operator designated number of bits.
Since xe2x80x9cavg(p00, p01):=(p00, p01)//2=(p00, p01+1) greater than  greater than 1xe2x80x9d is a simple operation to implement on a microprocessor, many commercial microprocessors include this operation as a built-in instruction. For example, xe2x80x9cpavgusbxe2x80x9d is included in Intel processors with the SSE extension, and AMD processors with the 3DNow! extensions. Such instruction is very useful in computing cases B and C, above.
The built-in xe2x80x9cpavgusbxe2x80x9d instruction is very tempting for use in implementing case-D, e.g., by executing it twice, as in xe2x80x9cavg(avg(p00, p01), avg(p10, p11))xe2x80x9d. This is also an interesting alternative for a pure hardware implementation, because the circuit to implement the first step of averaging can also be used a second time to do the second step. But to do so, will generate objectionable visual artifacts.
The usual sub-routine to implement case-D requires the execution of twenty-seven instructions, as is listed in the left column of Table I. But if xe2x80x9cpavgusbxe2x80x9d is used, the sub-routine can be reduced to five instructions, as is listed in the right column of Table I. So the temptation to use the quicker solution for case-D is very great.
One problem with the shortcut solution is that it causes, artifacts because rounding is handled different, than the MPEG standard dictates. So to have artifact-free implementations, the short-cut solution is prohibited.
The rounding error for a specific combination of four pixels can be calculated as:
err(p00, p01, p10, p11)=((((p00+p01+1) greater than  greater than 1)+((p10+p11+1) greater than  greater than 1)+1) greater than  greater than 1)xe2x88x92((p00, p01+p10+p11+2) greater than  greater than 2)
The overall error is only affected by the two least significant bits of each coefficient, so the total average error can be calculated as:   avgerr  =                                          xe2x80x83                    ⁢                                    xe2x80x83                                      i              =              0                        3                          ⁢                              xe2x80x83                    ⁢                                                    xe2x80x83                            ⁢                                                xe2x80x83                                                  j                  =                  0                                3                                      ⁢                          xe2x80x83                        ⁢                                          xe2x80x83                            ⁢                                                xe2x80x83                                                  k                  =                  0                                3                                      ⁢                          xe2x80x83                        ⁢                                          xe2x80x83                            ⁢                                                xe2x80x83                                                  l                  =                  0                                3                                      ⁢                          err              ⁢                              (                                  i                  ,                  j                  ,                  k                  ,                  l                                )                                                                4        ?        4        ?        4        ?        4              =                  3        8            .      
The rounding error is less than one least-significant-bit for first-generation compensation, and is not a problem. But the MPEG-2 standard allows for multi-generation compensation. The consequence of this is a predicted picture can be used as a reference picture for successive pictures. When a predicted picture is used as a reference picture, rounding errors can add up to more than one least significant bit, and the accumulated rounding errors can be large enough over several compensation generations to create objectionable visual artifacts.
Such visual artifacts or optical effects are called xe2x80x9cpumpingxe2x80x9d, and are perceived by the eye as image brightening over a series of predicted pictures that jump back to normal brightness at the next intra-picture. In particular, sequences that have an unusually high number of predicted pictures between intra codes pictures can experience serious pumping. For example, field structure encoded sequences or material that lack xe2x80x9cbi-directionalxe2x80x9d predicted pictures will suffer from pumping.
The invention comprises a method wherein two-step motion prediction errors for MPEG-2 interpolation case-D are corrected. An improved MPEG-2 decoder includes a logic gate, multiplexer, and adder. When both the horizontal (h0) and vertical (h1) motion vector components require a half pixel interpolation (case-D), the multiplexer forwards the constant minus three to the adder, otherwise a constant zero is used. Such adder modifies the D C coefficient input to the inverse discrete cosine transformer to include a correction term for the predicted pixels calculated by a two-step predictor. A correction value of xe2x88x920.375 is evenly distributed over all sixty-four resulting spatial coefficients during the inverse discrete cosine transform. This results statistically in a slightly brighter set of correction terms. Such offsets a slightly darker prediction that are formed by the two-step predictor. The output frames are statistically correct images.