Motion Video Compression System With Inverse Discrete Cosine Transform Mismatch Control

This invention relates to data compression. More particularly, this invention relates to controlling inverse discrete cosine transform mismatch between an encoder and a decoder.

The Discrete Cosine Transform ("DCT") has been widely used in digital signal processing, especially for image and speech because it approaches the statistically optimal Karhunen-Loeve transform for highly correlated signals. For image compression applications, the two-dimensional separable DCT has been widely used in many international image compression standards, such as the Joint Photographic Experts Group, ("JPEG"), Comite Consulatif International Telegraphique et Telephonique Recommendation H.261-Video Codec for Audiovisual Services at px64 Kbit/s ("CCITT H.261") and the Motion Pictures Expert Group Phase 1 and Phase 2 video compression standards ("MPEG-1 and MPEG-2").

While DCTs may be implemented by software on general-purpose digital computers, they are more typically implemented by dedicated hardware in video encoders and decoders. In the case of hardware implementation, fixed point arithmetic is normally employed because of speed requirements for the hardware. However, there is an inherent accuracy problem due to the finite word length in fixed-point arithmetic. For image compression, when an encoder and decoder use inverse DCT ("IDCT") with different implementations, by using either a different IDCT method or different arithmetic precision, a difference may occur in the reconstructed pixels between the encoder and the decoder until intraframe data is sent to the decoder for refresh. This difference may accumulate and become visible in the decoded picture. This phenomena is called IDCT mismatch since the visible distortion in the decoded picture is caused by different IDCT implementations in the encoder and decoder. IDCT mismatch is a serious problem for high quality coding schemes such as those conforming to the MPEG-1 and MPEG-2 standards. Thus, in order to get high coding quality, IDCT mismatch must be controlled.

There have been several approaches to controlling IDCT mismatch. One approach is known as intra refreshing. In intra refreshing, an image sequence is cyclically intra-frame coded which allows the current picture to be coded without reference to either previous pictures or future pictures. Thus, any distortion accumulated in the reference picture cannot affect the current picture. This approach may be effective in removing errors caused by either IDCT mismatch or coding. However, as the refresh interval is restricted by bitrate and bandwidth limitations, a chosen refresh interval may not adequately control IDCT mismatch. Moreover, since intra-frame-coded pictures require more bits to be coded than do inter-frame-coded pictures, considerable coding efficiency may be lost if the refresh interval is small enough to avoid IDCT mismatch. Therefore, the intra refreshing approach may not be a good solution to the IDCT mismatch problem under all conditions.

Another approach to controlling IDCT mismatch includes oddification methods which must be used in both the encoder and decoder. In this approach, the reconstructed or dequantization data is oddified at both the encoder and the decoder sides before the IDCT step. Oddification methods may give good results for low to medium quality coding since the oddification of the reconstructed value may prevent distortion from accumulating in the decoder. However, oddification cannot control IDCT mismatch under all coding conditions, nor is it suitable for high quality coding.

IDCT mismatch may be controlled under all coding conditions, in accordance with one example of the invention, by a novel apparatus and method which forces synchronization between an encoder and decoder by selectively setting certain small DCT coefficients, which are prone to mismatch, to zero at the encoder. Advantageously, the invention may be implemented solely in the encoder to minimize system complexity and cost, and allow for IDCT mismatch control utilizing conventional decoders.

The discussion in this Summary and the following Brief Description of the Drawings, Detailed Description, and drawings only deals with examples of this invention and is not to be considered in any way a limitation on the scope of the exclusionary rights conferred by a patent which may issue from this application. The scope of such exclusionary rights is set forth in the claims at the end of this application.

FIG. 1 is a simplified block diagram of an illustrative video encoder embodying principle in accordance with the invention.

FIG. 2 shows comparative experimental results illustrating improved signal-to-noise ratios achievable with the invention.

FIG. 3 shows comparative experimental results illustrating improvement in the number of mismatched macroblocks achievable with the invention.

It will be helpful to begin with a brief theoretical exposition of the phenomena called inverse discrete cosine transform ("IDCT") mismatch. Generally speaking, IDCT mismatch is the accumulation of the IDCT error caused by the finite length arithmetic in the computation of the IDCT in the encoder and the decoder. The two dimensional 8.times.8 discrete cosine transform ("DCT") used in the image compression is defined as: ##EQU1##

The inverse 8.times.8 DCT ("IDCT") is defined as: ##EQU2## where i, j are the coordinates in the time domain, k, l are the coordinates in the transform domain, X.sub.k,l are DCT coefficients, and x.sub.i,j are pixel values or pixel residuals. Those skilled in the art will appreciate that DCTs and IDCTs may be implemented using various methods. For example, they may either use full matrix multiplications, which is also called the direct form implementation, or different fast algorithms with their sparse matrices. For full matrix multiplication, Equation (2) can be rewritten as: ##EQU3## If all DCT coefficients are zero except X.sub.0,0 X.sub.4,0, and X.sub.4,4, then since ##EQU4## x.sub.i,j can be written as ##EQU5## When X.sub.0,0 .+-.X.sub.0,4 .+-.X.sub.4,0 .+-.X.sub.4,4 =.+-.4,.+-.12, . . . ,x.sub.0,0 can be exact value I+0.5, where I is any integer number. Since different implementations have different ways of computing the x.sub.0,0, the value of x.sub.0,0 after rounding can be either I or I+1 depending on the actual implementation and truncation of the word length. That is, when the encoder and decoder use different IDCTs, the reconstructed integer data may differ by 1.

A more specific example is shown below. In this example, for the same DCT coefficients, the reconstructed data from an exact IDCT are all 0s, while the data obtained from a finite accuracy IDCT are 0s and 1s. ##EQU6##

Here, the DCT coefficients are zeros except X.sub.0,0 and X.sub.0,4. IDCT1 (float) is the reconstructed data represented by 64-bit floating point and obtained from the direct form implementation without rounding. IDCT1(int) is the reconstructed data represented by 32-bit fix point and obtained from the direct form implementation with rounding and truncation. IDCT2(int) is the reconstructed value represented by 32-bit fix point and obtained by using fast implementation with rounding and truncation. It will be appreciated from the previous analysis and examples that any data close to I+0.5 in IDCT computation, where I can be any integer number, is the source for IDCT mismatch when different IDCT implementations are involved. Thus, if the precision for calculation and representation are different, the same input could produce totally different output.

FIG. 1 is a simplified block diagram of an illustrative video encoder in accordance with the invention. A digital image sequence signal VIDEO IN is supplied as input to encoder 100 on line 101. Depending on whether intra- or inter-coding is utilized, VIDEO IN is sent to DCT coefficient generator 103 or motion estimator and frame store 117. For purposes of this example, coding is performed on a macroblock basis. However, those skilled in the art will appreciate that the principles of the invention may also be applied on a picture basis. In intra-coding mode 102, VIDEO IN is directly supplied as input to intra/inter DCT coefficient generator 103. In inter-coding mode, VIDEO IN is supplied as input to motion estimator and frame store 117 on line 140, where motion vectors are estimated. Those skilled in the art will appreciate that the motion vectors can be unidirectional or bi-directional depending on the picture type. The motion vectors and the current input frame on line 116 is supplied as input to motion compensator 114, where the prediction of the current frame is computed. The predicted signal of the current frame on line 115 is subtracted from VIDEO IN on line 101 in adder 145 to form a residual signal on line 102. The residual signal on line 102 is supplied as input to intra/inter DCT coefficient generator 103.

The DCT transform coefficients are output from intra/inter DCT coefficient generator 103 on line 104 to quantizer 105, where the coefficients are quantized by using flat or steep quantization matrix similar to those specified in MPEG-1 standard. The quantized coefficients on line 106 and the quantization step size mquant on line 118 are supplied as inputs to IDCT mismatch controller 107. IDCT mismatch controller 107 processes the quantized coefficents, in accordance with the invention, to produce an output signal on line 108 which may be transmitted to a remote decoder (not shown). In order to produce the reconstructed picture, on line 115, the output signal on line 108 is supplied as input to inverse quantizer 109, where the quantized DCT coefficients are reconstructed. The reconstructed DCT coefficients on line 110 are supplied as an input to inverse DCT generator 111 to produce the reconstructed data. The reconstructed data from inverse DCT generator 111 output on line 112 may be pixel data, or residual data corresponding to the intra- and inter-coding modes. In intra-coding mode, the reconstructed data on line 112 equals the signal on line 113, and is stored in motion compensator 114. In inter-coding mode, the signal on line 113 is obtained by the reconstructed data on line 112 and the predicted signal on line 115 which are summed together in adder 150.

As stated above, IDCT mismatch may be controlled by processing the quantized DCT coefficients in IDCT mismatch controller 107. Advantageously, the control need only be performed in the encoder. Details of the operations performed in IDCT mismatch controller 107 are described below.

Let q.sub.-- coeff(i, j), i, j=0,1, . . . , 7 be the quantized DCT coefficients, on line 106, and mquant be the quantization step size, on line 116. For an intra-coded macroblock, there is no modification of q.sub.-- coeff. For inter-coded macroblocks, if we define the absolute sum of the quantized coefficients as ##EQU7## where T.sub.1, T.sub.b are predetermined thresholds. IDCT mismatch controller 107 sets some small DCT coefficients to zero according to Equation 14. Thus, by forcing some small DCT coefficients to zeros at the encoder, the encoder and decoder are forced to synchronize because determination of zero-valued coefficients is not affected by IDCT implementation. As will be appreciated by those skilled in the art, forcing small coefficients to zero has negligible effect on picture quality.

FIGS. 2 and 3 show comparative experimental results illustrating improvements in IDCT mismatch achievable with the invention. FIG. 2 shows comparative experimental results illustrating improved signal-to-noise ratios achievable with the invention. As shown, when IDCT mismatch controller 107 (FIG. 1) is disabled, the signal-to-noise ratio of the decoded picture rapidly decreases with an increasing number of coded frames. When IDCT mismatch controller 107 is enabled, the the signal-to-noise ratio remains constant with an increasing number of frames. FIG. 3 shows comparative experimental results illustrating improvement in the number of mismatched macroblocks achievable with the invention. When IDCT mismatch controller 107 is disabled, the number of mismatched macroblocks increases with the number of frames. When IDCT mismatch controller is enabled, the number of mismatched macroblocks remains constant. The values of T.sub.a and T.sub.b used in the experiments, the results of which are shown in FIGS. 2 and 3, were 3 and 2, respectively. Of course, those skilled in the art will appreciate that other values of T.sub.a and T.sub.b could also be used to achieve IDCT mismatch control depending upon the specific application and circumstances.