Method, system and computer program product for optimization of data compression with iterative cost function
AssigneeSlipstream Data Inc.
InventorsEn-hui Yang, Longji Wang
Life of this patent
Estimating the term…
Abstract
A method, system and computer software product for improving rate-distortion performance while remaining faithful to JPEG/MPEG syntax, involving joint optimization of Huffman tables, quantization step sizes and quantized coefficients of a JPEG/MPEG encoder. This involves finding the optimal coefficient indices in the form of (run, size) pairs. By employing an interative process including this search for optimal coefficient indices, joint improvement of run-length coding, Huffman coding and quantization table selection may be achieved. Additionally, the compression of quantized DC coefficients may also be improved using a trellis-structure.
Claims36
A method of compressing a sequence of n coefficients by jointly determining an output quantization table, a cost-determined sequence of coefficient indices represented by a cost-determined sequence of (run, size, ID) triples, and a run-size distribution, wherein each sequence of (run, size, ID) triples defines a corresponding sequence of coefficient indices such that (i) each index in the corresponding sequence of coefficient indices is a digital number, (ii) the corresponding sequence of coefficient indices includes a plurality of values including a special value, and (iii) each (run, size, ID) triple defines a run value representing a number of consecutive indices of the special value, an integer value ID specifying the amplitude of the index following the number of consecutive indices of the special value, and a size value defining a number of bits required to store an index within a category specified by the ID value, and wherein a sequence of coefficient indices together with a quantization table determines a sequence of n soft-decision quantized coefficients, n being a positive integer, the method comprising:
- (a) determining a 0th quantization table;
- (b) determining a 0th run-size distribution;
- (c) setting a counter t equal to 0;
- (d) applying a tth quantization table and tth run-size distribution to each possible sequence in a tth plurality of possible sequences of (run, size, ID) triples to determine an associated cost;
- (e) determining a tth cost-determined sequence of (run, size, ID) triples from the tth plurality of possible sequences of (run, size, ID) triples based on the associated cost;
- (f) if the tth cost-determined sequence of (run, size, ID) triples, together with the tth quantization table and run-size distribution, meets a selection criterion, selecting the tth cost-determined sequence of (run, size, ID) triples as the cost-determined sequence of (run, size, ID) triples, and the tth quantization table as the output quantization table;
- otherwise determining a (t+1)th quantization table and run-size distribution from the tth cost-determined sequence of (run, size, ID) triples, increasing t by one, and returning to step (d);
- and
- (g) encoding the corresponding selected sequence of (run, size, ID) triples using Huffman coding.
A data processing system for compressing a sequence of n coefficients by jointly determining an output quantization table, a cost-determined sequence of coefficient indices represented by a cost-determined sequence of (run, size, ID) triples, and a run-size distribution, wherein each sequence of (run, size, ID) triples defines a corresponding sequence of coefficient indices such that (i) each index in the corresponding sequence of coefficient indices is a digital number, (ii) the corresponding sequence of coefficient indices includes a plurality of values including a special value, and (iii) each (run, size, ID) triple defines a run value representing a number of consecutive indices of the special value, an integer value ID specifying the amplitude of the index following the number of consecutive indices of the special value, and a size value defining a number of bits required to store an index within a category specified by the ID value, and wherein a sequence of coefficient indices together with a quantization table determines a sequence of n soft-decision quantized coefficients, n being a positive integer, the data processing system comprising a microprocessor configured to:
- (a) determine a 0th quantization table and a 0th run-size distribution, and for setting a counter t equal to 0;
- (b) (i) apply a tth quantization table and tth run-size distribution to each possible sequence in a tth plurality of possible sequences of (run, size, ID) triples to determine an associated cost;
- (ii) determine a tth cost-determined sequence of (run, size, ID) triples from the tth plurality of possible sequences of (run, size, ID) triples based on the associated cost;
- (iii) if the th cost-determined sequence of (run, size, ID) triples, together with the tth quantization table and run-size distribution, meets a selection criterion, select the tth cost-determined sequence of (run, size, ID) triples as the cost-determined sequence of (run, size, ID) triples, and the tth quantization table as the output quantization table;
- otherwise determining a (t+1)th quantization table and run-size distribution from the tth cost-determined sequence of (run, size, ID) triples, increasing t by one, and returning to step (i);
- and (iv) encode the corresponding selected sequence of (run, size, ID) triples using Huffman coding.
A computer program product for use on a computer system to compress a sequence of n coefficients by jointly determining an output quantization table, a cost-determined sequence of coefficient indices represented by a cost-determined sequence of (run, size, ID) triples, and a run-size distribution, wherein each sequence of (run, size, ID) triples defines a corresponding sequence of coefficient indices such that (i) each index in the corresponding sequence of coefficient indices is a digital number, (ii) the corresponding sequence of coefficient indices includes a plurality of values including a special value, and (iii) each (run, size, ID) triple defines a run value representing a number of consecutive indices of the special value, an integer value ID specifying the amplitude of the index following the number of consecutive indices of the special value, and a size value defining a number of bits required to store an index within a category specified by the ID value, and wherein a sequence of coefficient indices together with a quantization table determines a sequence of n soft-decision quantized coefficients n being a positive integer, the computer program product comprising a non-transitory computer-readable medium and means recorded on the medium for instructing the computer to perform the steps of:
- (a) determining a 0th quantization table;
- (b) determining a 0th run-size distribution;
- (c) setting a counter t equal to 0;
- (d) applying a tth quantization table and tth run-size distribution to each possible sequence in a tth plurality of possible sequences of (run, size, ID) triples to determine an associated cost;
- (e) determining a tth cost-determined sequence of (run, size, ID) triples from the tth plurality of possible sequences of (run, size, ID) triples based on the associated cost;
- (f) if the tth cost-determined sequence of (run, size, ID) triples, together with the tth quantization table and run-size distribution, meets a selection criterion, selecting the tth cost-determined sequence of (run, size, ID) triples as the cost-determined sequence of (run, size, ID) triples, and the tth quantization table as the output quantization table;
- otherwise determining a (t+1)th quantization table and run-size distribution from the tth cost-determined sequence of (run, size, ID) triples, increasing t by one, and returning to step (d);
- and
- (g) encoding the corresponding selected sequence of (run, size, ID) triples using Huffman coding.
Dependencies are inferred from the claim text.