Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
2000-11-17
2004-05-25
Boudreau, Leo (Department: 2621)
Image analysis
Image compression or coding
Adaptive coding
C382S251000, C382S252000
Reexamination Certificate
active
06741747
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to data compression. At least preferred embodiments of the invention relate to video 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 non-linear and difficult to predict effect on the resulting bit rate.
These characteristics are 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 so-called “Test Model 5” of the MPEG 2 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 quantisation parameters 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. This system can, however, be slow to react to changes in image type during the compression of a picture and cannot predict the presence of difficult-to-encode image portions (requiring a higher bit rate) towards the end of a particular picture. Also, it is difficult for such a system to react to a rapidly changing picture content, such as that caused by a scene change.
Another previously proposed system described in GB-A-2 306 831 uses a system of trial encoding of at least part of a picture or group of pictures in order to assess the most appropriate degree of compression for use with those pictures. In particular, a “binary search” technique is proposed whereby an multi-stage process is used to iterate towards the required quantisation factor. However, such a multi-stage process to narrow the search down to the required quantisation factor is expensive in terms of the delay it adds to the processing chain as well as the actual processing overhead involved.
SUMMARY OF THE INVENTION
This invention provides data compression apparatus for compressing an input data unit to produce an output data unit in accordance with a desired data quantity of the output data unit, the degree of compression applied by the apparatus being determined by a compression control variable having a range of possible values;
the apparatus comprising:
a trial encoder for compressing successive sections of the input data unit in accordance with a trial group of two or more values of the compression control variable, the trial group being a subset of the range of possible values of the compression control variable;
a data quantity detector for detecting the trial data quantities generated by each trial encoding of the sections of the input data unit and for selecting a base compression control variable applicable to the input data unit on the basis of the detected trial data quantities, in order to comply with the desired data quantity; and
an allocator for allocating a compression control variable for use in final-encoding each section of the input data unit to generate the output data unit, the allocator being operable to determine whether to use the base compression control variable or another possible value of the compression control variable for a current section by a comparison between (a) the increase in data quantity determined for compression of the current section using a next less harsh compression value from the trial group; and (b) the maximum possible increase in data quantity, while still complying with the desired data quantity, over that obtained if the remainder of the input data unit were compressed using the base compression control variable.
The invention provides a data compression apparatus which addresses the shortcomings of both the predictive and the “full” trial encoding systems outlined above.
The invention operates to trial encode a current input data unit (e.g. an image) and so avoids the lack of responsiveness which can be experienced by the TM5 type of technique, particularly at scene changes. However, by deliberately trial-encoding at only a subset (and preferably a non-adjacent subset) of the possible values of the compression control variable (e.g. the quantisation factor Q) and then subsequently deriving a decision on which value to use based on the trial group of values, the invention alleviates the processing overhead and delay of the system of GB-A-2 306 831.
REFERENCES:
patent: 5768431 (1998-06-01), Saunders et al.
patent: 5892545 (1999-04-01), Saunders et al.
patent: 0 540 961 (1993-05-01), None
patent: 0 772 362 (1997-05-01), None
patent: 2 335 815 (1999-09-01), None
Burns James Edward
Saunders Nicholas Ian
Boudreau Leo
Dang Duy M.
Frommer William S.
Frommer & Lawrence & Haug LLP
Sony United Kingdom Limited
LandOfFree
Data compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3222314