Block-by-block data compression with quantization control

Coded data generation or conversion – Digital code to digital code converters

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C348S420100

Reexamination Certificate

active

06351226

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to data compression.
2. Description of the Prior Art
It has long been recognised that some video data compression systems, such as systems broadly defined by the MPEG-2 standard, use compression techniques in which the number of compressed data bits generated for a picture, or a part of a picture, depends on the nature of the image represented by that picture. Also, the main compression parameter which can be altered from block to block or picture to picture to change the bit rate, namely the degree of quantisation, has a somewhat nonlinear and difficult to predict effect on the resulting bit rate.
In MPEG encoders, the quantisation system operates broadly as follows. Coefficients representing a DCT-transformed version of each image block (there being many such blocks forming a single image) are divided by a variable referred to as the quantisation factor Q. A predetermined constant value between 0 and 1 is then added to each resulting data value, and the values are finally truncated down to the next lowest integer.
In the so-called “Test Model 5” (TM5) of the MPEG 2 system, the predetermined constant value added before truncation is ⅜. This means that if the fractional part of a DCT coefficient is between 0 and ⅝, that value will be rounded down. If the fractional part is between ⅝ and (very close to) 1, that value will be rounded up. The corresponding decoder is set up in the expectation that this predetermined constant value has been used as part of the rounding process in the encoder.
The non-linear and fairly unpredictable nature of the change in bit rate resulting from variation of the quantisation factor is of particular concern in systems such as video tape recorders, where there is generally a fixed allocation of bits for each picture or group of pictures (GOP) and little or no scope for exceeding that fixed allocation. As a result, techniques for bit rate control in video data compression are very important.
The TM5 system proposes a rate control algorithm that allocates bits between pictures in accordance with a “global complexity estimation” dependent upon the actual number of bits generated in respect of a preceding picture and the degree of quantisation used to achieve this.
The actual bit rate achieved during compression of a picture is then monitored and the degree of quantisation varied during compression to try to achieve the desired total bit rate for that picture.
A problem with this system is that when a change is made from one quantisation factor to an adjacent quantisation factor (i.e. if the quantisation factor is changed by the smallest amount allowable by the system), the change in the number of bits generated for a current image block can either be inconveniently large or inconveniently small, depending to some extent on whether the image has previously been encoded using a similar compression system.
If the image has not previously been compressed, then the change in bit rate on moving to an adjacent quantisation factor can be inconveniently large, so that the rate control system is denied a sufficiently fine control over the output bit rate. In these circumstances, there is a need to provide a finer variation of output bit rate than that provided by the set of quantisation factors normally available to an MPEG-type system.
In contrast, in a multi-generation system where the image data has been previously compressed and decompressed, there can tend to be too small a variation in output bit rate when the quantisation factor is changed to an adjacent value. This problem can arise because of previous quantisation processes applied to the image, so that the DCT coefficients representing the previously-compressed image will tend to include only a subset of the normal range of coefficient values. A small change in the quantisation factor may not change the final values obtained after addition of the constant value and subsequent truncation. So, in these circumstances, there is a need for the rate control algorithm to have access to a greater spread of possible output bit rates.
GB-A-2 323 493 and WO98/38800 disclose video data compression systems in which the rounding point in the compression process, as well as the quantisation factor, is varied. This can be a useful way of providing more possible output bit rates.
SUMMARY OF THE INVENTION
This invention provides data compression apparatus in which data are compressed on a block-by-block basis, the apparatus comprising:
a frequency-transformer for frequency-transforming blocks of data to generate corresponding groups of coefficient values representing respective frequency components of the data blocks;
a quantiser operable on the groups of coefficient values to map each of a contiguous plurality of ranges of coefficient values onto respective quantised data values, the extent of each range being controlled by a quantisation factor and the first non-zero range boundary being defined by a range boundary parameter; the quantiser being operable to vary the boundary parameter between data blocks by selecting from a range of boundary parameter regimes;
a detector operable:
(a) to trial-encode at least some of the data blocks using a range of at least one quantisation factor and at least a subset of the range of boundary parameter regimes available for use by the quantiser, in order to assess the quantity of compressed data produced with each quantisation factor/boundary parameter regime;
(b) to trial-decode the trial-encoded blocks using a corresponding quantisation factor;
(c) to compare the trial-decoded blocks with the data blocks before trial encoding, in order to assess data errors introduced by the trial-encoding and decoding;
(d) to detect whether the relationship between quantity of data produced by the trial-encoding and data errors introduced by the trial-encoding is substantially monotonic; and
a quantisation controller operable in response to a detection that the relationship between quantity of data produced by the trial-encoding and data errors introduced by the trial-encoding is not substantially monotonic, to vary the range of boundary parameter regimes available for use by the quantiser.
The invention builds on the system proposed by the two documents cited above, by recognising that the usefulness of a variation of the rounding point/boundary parameter is dependent upon there being a substantially monotonic relationship between the data quantity produced and the quality of the compressed data, as the boundary parameter is varied. If this relationship becomes non-monotonic, it can be better not to use that boundary parameter regime.
Further respective aspects and features of the present invention are defined in the appended claims.


REFERENCES:
patent: 5590139 (1996-12-01), Suzuki et al.
patent: 6064435 (2000-05-01), Iwamura
patent: 2 306 831 (1997-05-01), None
patent: 2 323 493 (1998-09-01), None

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Block-by-block data compression with quantization control does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Block-by-block data compression with quantization control, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Block-by-block data compression with quantization control will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-2960343

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.