Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
1999-03-09
2002-07-02
Couso, Jose L. (Department: 2721)
Image analysis
Image compression or coding
Adaptive coding
C348S390100, C348S475000, C375S240030, C382S239000, C382S251000
Reexamination Certificate
active
06415059
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to data compression.
2. Description of the Prior Art
Some data compression systems, such as image data compression systems, use trial compressions to try to arrive at the most appropriate quantisation factor to achieve a desired output bit rate.
In one previously proposed system, trial quantisations are carried out at, say, ten possible quantisation values spread across the available range of quantisation values. The two trial quantisation values which provide an output bit rate falling either side of the desired value are identified, and a more detailed trial carried out in the reduced range between those two values. This can identify the quantisation value corresponding to the least harsh quantisation of the data which still complies with the target bit rate of the system.
However, it has been established that for some classes of data—for example, image data and/or data which has previously been compressed and decompressed—this arrangement does not necessarily provide the best quantisation value. A process sometimes referred to as “backsearch” has been devised to alleviate this problem.
The backsearch process starts with the quantisation value identified by the trial quantisations referred to above, and then tests that value and a number of adjacent values providing successively harsher degrees of quantisation. The test used is to apply quantisation followed immediately by dequantisation to the input data using each of the values under test and, in each case, to compare the resultant data with a delayed (i.e. not quantised) version of the input data. The quantisation value (of those tested) giving the fewest errors is then selected for the final, output stage of quantisation.
However, like many aspects of data compression, this additional test requires a large amount of fast processing circuitry in order to apply test quantisations and dequantisations to the input data at several quantisation values in parallel. This is a particular problem when the compression circuitry is to be implemented as an integrated circuit such as an ASIC (application specific integrated circuit).
SUMMARY OF THE INVENTION
This invention provides data compression apparatus in which input data is compressed according to a target output data quantity using a stage of data quantisation, the apparatus comprising:
one or more trial quantisers for selecting a degree of quantisation so that the target output data quantity is not exceeded;
a data selector for selecting a subset of the current data to be quantised;
a data store for storing the subset of data;
a backsearch quantiser and dequantiser for sequentially quantising and dequantising the subset of data at a plurality of degrees of quantisation including the degree of quantisation selected by the trial quantiser(s) and one or more harsher degrees of quantisation;
a comparator for comparing data quantised and dequantised by the backsearch quantiser with the stored subset of data, to detect errors introduced by the quantisation and dequantisation by the backsearch quantiser; and
a quantisation selector for selecting a final degree of quantisation for use in compression of the current data, the final degree of quantisation being that degree detected by the comparator to introduce the fewest errors during quantisation and dequantisation of the subset of data by the backsearch quantiser.
The invention recognises that the backsearch process can be performed and a useful result achieved using only a subset of the data to be quantised. This can dramatically reduce the amount of hardware needed to implement this function.
In a preferred embodiment, instead of being performed in parallel, the backsearch process can be performed in a time-division-multiplexed fashion using just a single set of quantiser and dequantiser.
The above, and other objects, features and advantages of this invention will be apparent from the following detailed description of illustrative embodiments which is to be read in connection with the accompanying drawings.
REFERENCES:
patent: 5249053 (1993-09-01), Jain
patent: 5461421 (1995-10-01), Moon
patent: 5481553 (1996-01-01), Suzuki et al.
patent: 5537215 (1996-07-01), Niimura et al.
patent: 5838826 (1998-11-01), Enari et al.
patent: 5889561 (1999-03-01), Kwok et al.
patent: 5892545 (1999-04-01), Saunders et al.
patent: 5930398 (1999-07-01), Watney
patent: 5956429 (1999-09-01), Burns
patent: 6014493 (2000-01-01), Shimoda
patent: 6147627 (2000-11-01), Vogel
patent: 6266447 (2001-07-01), Hoshi et al.
patent: 0 469 648 (1992-02-01), None
patent: 0 509 576 (1992-10-01), None
patent: 0 742 674 (1996-11-01), None
Couso Jose L.
Desire Gregory
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-2881425