Method and apparatus for macroblock DC and AC coefficient prediction for video coding

Existing video data compression algorithms exploit the fact that the DCT coefficients in the neighbouring blocks are sometimes similar to those in the current block. This means that if the blocks contain completely different coefficients, for coding video data is disclosed in which element in a prediction matrix is set to an initial prediction value. In the prediction matrix, a smoothing transform is applied to the values along the rows and then along the columns, or vice versa, to obtain interpolated values. The prediction value is reset to the interpolated value and the difference between the reset prediction values and corresponding received pixel values is calculated to produce a residual prediction matrix containing the prediction residuals. A discrete cosine transform is performed on the prediction residuals to obtain elements of a compressed video data matrix. The processor means is preferably arranged iteratively to calculate the reset prediction value used to calculate the prediction residual by repeating steps b) and c).

This invention relates to apparatus for compressing and expanding video data.

Existing video compression standards are all based on block discrete cosine transform (DCT) transform. The picture is divided into square blocks consisting of 8×8 pixels. The blocks may contain the actual pixels or the prediction residual, which is the difference between the actual and motion compensated bock pixels. Each block is transformed into DCT domain, which results in 8×8 coefficients.

The DCT process is used to remove the spatial redundancy between the pixels in the same block. However, it does not consider the redundancy between the pixels from different blocks. The first versions of the standards did not use any technique to exploit the correlation between different blocks. Recently, MPEG-4 and H.263+ have added tools/options to exploit this redundancy to certain extent. At present, MPEG-4 predicts the DC coefficient (first coefficient, which is actually the block average) of the current block by using the DC coefficients of the neighbouring blocks. H.263+ does this, and in addition, it also predicts the first row or column of the DCT coefficients in some cases if there is any benefit.

In brief, existing compression algorithms exploit the fact that the DCT coefficients in the neighbouring blocks are sometimes similar to those in the current block. This means that if the blocks contain completely different coefficients, the prediction will not work.

Yuuji Izawa Et Al: ‘Improvement of Picture Quality and Coding Efficiency Using Discrete Cosine Transform’ Electronics & Communications in Japan, Part 1—Communications, US, Scripta Technica, New York, vol. 73, no. 6, 1 Jun. 1990 (1990-06-01), pages 12–21, XP000170744 ISSN: 8756–6621 discloses apparatus for coding video data, comprising means for receiving pixel values organised in frames each comprising a matrix of video blocks, each video block comprising a video matrix of N pixel values, and processor means arranged to perform the following steps:a) to set each element in a prediction matrix to an initial prediction value;b) in the prediction matrix, to apply a smoothing transform to the values along rows and then along columns, or vice versa, to obtain interpolated values;c) to set the prediction values to the interpolated values;d) to calculate the differences between the prediction values and corresponding received pixel values to produce a residual prediction matrix containing prediction residuals.

The present invention is characterised over the disclosure of the Yuuji Izawa et al. paper mentioned above in that the processor means is also arrangede) to perform a discrete cosine transform on the prediction residuals to obtain elements of a compressed video data matrix, wherein the processor means is arranged iteratively to calculate the prediction values used to calculate the prediction residuals by repeating steps b) and c.

The number of iterations may be predetermined or, in an alternative, the iterations may be repeated until the change in the prediction value between one iteration and the next, is less than a predetermined threshold.

Step a) is most preferably performed by performing a discrete cosine transform on the video matrix to obtain a transform video matrix of N coefficients, selecting n of the coefficients, setting the N-n remaining coefficients to zero to obtain an initial prediction transform matrix of initial prediction coefficients, and performing an inverse discrete cosine transform on the initial prediction transform matrix to obtain a matrix of N initial prediction values.

In that case, the processor is preferably arranged to set n of the elements in the compressed video data matrix equal to the n coefficients selected from the transform video matrix, and to select the remaining N-n coefficients from the prediction residuals.

The processor is further preferably arranged to adjust the prediction residuals before selecting the remaining N-n elements, by:f) performing a discrete cosine transform on the reset prediction value matrix to obtain a prediction transform matrix,g) selecting n coefficients from the transform prediction matrix,g) selecting n coefficients from the transform prediction matrix,h) subtracting the selected n transform prediction matrix coefficients from the selected n transform video coefficients to obtain n residual coefficients;i) setting n elements of an adjustment transform matrix to the values of the n residual coefficients and setting N-n remaining elements to zero;j) performing an inverse discrete cosine transform on the adjustment transform matrix to obtain an adjustment value matrix; andk) subtracting the adjustment value matrix from the reset prediction value matrix.

The apparatus may include means for processing pixels in a current and a previous frame to produce pixel values which are the prediction residual between the actual pixel and a motion compensated pixel.

The invention extends to apparatus for expanding video data compressed by apparatus as claimed in any preceding claim, comprising means for receiving the compressed video matrix, and processor means arranged to perform the following steps:a) to perform an inverse discrete cosine transform on received compressed video data to obtain a prediction residual matrix;b) to set each element in a prediction matrix to the initial prediction value;c) in the prediction matrix, to apply a smoothing transform to the values along the rows and then along the columns, or vice versa, to obtain interpolated values;d) to reset the prediction value to the interpolated value; ande) to calculate the sum of the reset prediction values and the prediction residual in corresponding positions in the received coded block matrix to produce an expanded video data matrix.

A frame of quantised and digitised pixel values is divided into video matrices comprising blocks of N pixels where as an example N=8×8. With a switches1a,1bset to “intra” as illustrated, a video matrix2is discrete cosine transformed in step4to produce a video transform matrix6comprising a block of N discrete cosine transform (DCT) coefficients where in the example N=8×8. Of these a square of n coefficients are selected in step8, essentially the DC coefficient and optionally other coefficients.

In step10, the remaining N-n (i.e. 8×8-n) coefficients are set to zero to obtain an initial prediction transform matrix12. The coefficients are inverse discrete cosine transformed in step14to obtain an initial prediction matrix16.

In step18interpolation is performed between the initial prediction values of matrix16and the values in the neighbouring preceding blocks to reset the prediction matrix. Values in a row20, spatially nearest to the video matrix2, are used in the interpolation process. Linear interpolation is performed between the value in a row/column position in the initial prediction matrix and the value in a corresponding column in row20weighted according to the distance in rows from the row20.

Similarly values in a column22, spatially nearest the video matrix2, are used in the interpolation process. Linear interpolation is also performed between the value in a row/column position in the initial prediction matrix and the value in a corresponding row in column22, weighted by the distance in columns from the column22.
Vinterpolated={1Vr,c+V20,c/r+Vr,22/C}¼

Where,Vinterpolatedis the interpolated prediction value, Vr,cis the value at row r column c of the initial prediction matrix16, V20,cis the value in column c of row20, r is the distance in rows of the position r,c from row20, Vr,22is the value at row r in column22, and c is the distance in columns of the position r,c from the column22.

The interpolation step18is performed iteratively until, in one example, the change in values in one step is less than a predetermined threshold. In another example, a predetermined fixed number of iterations is performed.

When the iterations are complete, the reset prediction values are discrete cosine transformed in step24to obtain 8×8 coefficients of a transform prediction matrix26. In step28n coefficients are selected and, in step30subtracted from the n video transform coefficients previously selected in step8to produce n residual coefficients. In step32the remaining 8×8-n coefficients are set to zero to obtain 8×8 adjustment coefficients34. These are inverse discrete cosine transformed to produce 8×8 adjustment values.

The values of the reset prediction matrix are adjusted by subtracting from them the adjustment values. The values in the video matrix are subtracted from the adjusted reset prediction values to obtain a prediction residual matrix34of 8×8 values. In step36, the prediction residual values are discrete cosine transformed to produce a transform residual matrix having 8×8 coefficients. Of these n will be zero because of the adjustment made to the reset prediction matrix.

The remaining 8×8-n coefficients are selected in step38and assembled with the n video transform coefficients previously selected in step8to provide a compressed video matrix of 8×8 coefficients. These are channel coded in step40and transmitted through a medium42.

In the apparatus shown inFIGS. 2A and 2B, the signal received from the medium42is channel decoded in step44to produce a decoded compressed video data matrix46of 8×8 coefficients. Of these, n are selected in step48and the remaining 8×8-n are set to zero in step50to obtain a decoded initial prediction transform matrix52having 8×8 coefficients. The coefficients are inverse discrete cosine transformed to produce a+decoded initial prediction matrix54having 8×8 initial prediction values.

In step56, interpolation is performed iteratively on the initial prediction matrix in exactly the same manner as was performed in step18on the prediction matrix16using the (decoded) neighbouring row20and column22to obtain a matrix58of reset prediction values.

In step60, the remaining 8×8-n coefficients of matrix46are selected and n coefficients are set to zero in step62to obtain a decoded transform residual matrix64having 8×8 coefficients. These coefficients are inverse discrete cosine transformed in step66to obtain a decoded prediction residual matrix having 8×8 residual values. In step68these are added to the reset prediction values in matrix58to produce a decoded video matrix70containing 8×8 pixel values corresponding to those of matrix2.

Putting the switches1a,1bin their “inter” position, rearranges the apparatus to operate not on the current frame video matrix, but on the residual produced by subtracting the values in a motion compensated block of a previous frame, from the values in the current frame video matrix2in step74. The motion compensated values are added back in step76to produce the initial prediction matrix16values, and subtracted in step78from the reset prediction values.

In the expander shown inFIG. 2, motion compensated values obtained in a decoded motion compensated video matrix80from a previously decoded frame, are added back in step82to produce the initial prediction matrix.