US 7,742,643 B2 · Method, system and computer program product for optimization of data compression

Abstract

A sequence of n coefficients is compressed by determining a cost-determined sequence of n coefficient indices represented by a cost-determined sequence of (run, index derivative) pairs under a given quantization table and run-index derivative coding distribution, wherein each sequence of (run, index derivative) pairs 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, index derivative) pair defines a run value representing a number of consecutive indices of the special value, and an index-based value derived from a value of the index following the number of consecutive indices of the special value. This involves (a) using the given quantization table and run-index derivative coding distribution to formulate a cost function for a plurality of possible sequences of (run, index derivative) pairs; (b) applying the cost function to each possible sequence in the plurality of possible sequences of (run, index derivative) pairs to determine an associated cost; and, (c) selecting the cost-determined sequence of (run, index derivative) pairs from the plurality of possible sequences of (run, index derivative) pairs based on the associated cost of each of the plurality of possible sequences of (run, index derivative) pairs; and encoding the corresponding selected cost-determined sequence of (run, index derivative) pairs using entropy coding based on a run-index derivative coding distribution.

Claims114

Dependent claims

A method of compressing a sequence of n coefficients by determining a cost-determined sequence of n coefficient indices represented by a cost-determined sequence of (run, index derivative) pairs under a given quantization table and run-index derivative coding distribution, wherein each sequence of (run, index derivative) pairs 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, index derivative) pair defines a run value representing a number of consecutive indices of the special value, and an index-based value derived from a value of the index following the number of consecutive indices of the special value, the method comprising the steps of:

(a) using the given quantization table and run-index derivative coding distribution to formulate a cost function for a plurality of possible sequences of (run, index derivative) pairs;
(b) applying the cost function to each possible sequence in the plurality of possible sequences of (run, index derivative) pairs to determine an associated cost of each of the plurality of possible sequences of (run, index derivative) pairs, wherein determining an associated cost comprises, for each possible sequence of (run, index derivative) pairs in the plurality of possible sequences of (run, index derivative) pairs:
(i) determining a corresponding sequence of n coefficient indices;
(ii) determining a corresponding sequence of n quantized coefficients using the given quantization table and the corresponding sequence of n coefficient indices;
(iii) determining a distortion between the sequence of n coefficients and the corresponding sequence of n quantized coefficients;
(iv) determining a total compression rate resulting from using the given run-index derivative coding distribution to encode the sequence of (run, index derivative) pairs;
and
(v) determining the associated cost of the sequence of (run, index derivative) pairs as a function of the distortion and the total compression rate;
and,
(c) selecting the cost-determined sequence of (run, index derivative) pairs from the plurality of possible sequences of (run, index derivative) pairs based on the associated cost of each of the plurality of possible sequences of (run, index derivative) pairs;
and encoding the cost-determined sequence of (run, index derivative) pairs using entropy coding based on the given run-index derivative coding distribution.

8 more elements

A method of compressing a sequence of n coefficients by determining an output quantization table, a final cost-determined sequence of n coefficient indices represented by a final cost-determined sequence of (run, index derivative) pairs, and a run-index derivative coding distribution, wherein each sequence of (run, index derivative) pairs 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, index derivative) pair defines a run value representing a number of consecutive indices of the special value, and an index-based value derived from a value of the index following the number of consecutive indices of the special value, and wherein a sequence of n coefficient indices, together with a given quantization table, determines a sequence of n soft-decision quantized coefficients, the method comprising the steps of:

(a) selecting a 0th quantization table;
(b) selecting a 0th run-index derivative coding distribution
(c) setting a counter t equal to 0;
(d) using a tth quantization table and run-index derivative coding distribution to formulate a tth cost function for a tth plurality of possible sequences of (run, index derivative) pairs;
(e) applying the tth cost function to each possible sequence in the tth plurality of possible sequences of (run, index derivative) pairs to determine a tth associated cost of each of the tth plurality of possible sequences of (run, index derivative) pairs;
(f) selecting a tth cost-determined sequence of (run, index derivative) pairs from the tth plurality of possible sequences of (run, index derivative) pairs based on the tth associated cost of each of the tth plurality of possible sequences of (run, index derivative) pairs;
(g) if the tth cost-determined sequence of (run, index derivative) pairs together with the tth quantization table and run-index derivative coding distribution, meets a selection criterion, selecting the tth cost-determined sequence of (run, index derivative) pairs as the final cost-determined sequence of (run, index derivative) pairs and the tth quantization table as the output quantization table, otherwise determining a (t+1)th quantization table and run-index derivative coding distribution from the tth cost-determined sequence of (run, index derivative) pairs, increasing t by one, and returning to step (d);
and
(h) encoding the final cost-determined sequence of (run, index derivative) pairs using entropy coding based on the tth run-index derivative coding distribution.

6 more elements

A method of compressing a sequence of sequences of n coefficients by jointly determining an output quantization table, an output run-index derivative coding distribution, and, for each sequence of n coefficients in the sequence of sequences of n coefficients, a final cost-determined sequence of coefficient indices represented by a final cost-determined sequence of (run, index derivative) pairs, wherein each sequence of (run, index derivative) pairs 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, index derivative) pair defines a run value representing a number of consecutive indices of the special value, and an index-based value derived from a value of the index following the number of consecutive indices of the special value, and wherein a sequence of n coefficient indices together with a given quantization table determines a sequence of n soft-decision quantized coefficients, the method comprising:

(a) selecting a 0th quantization table;
(b) selecting a 0th run-index derivative coding distribution
(c) setting a counter t equal to 0;
(d) selecting a sequence of tth cost-determined sequences of (run, index derivative) pairs by, for each sequence of n coefficients in the sequence of sequences of n coefficients,
(i) using a tth quantization table and run-index derivative coding distribution to formulate a tth cost function for an associated tth plurality of possible sequences of (run, index derivative) pairs;
(ii) applying the tth cost function to each possible sequence in the associated tth plurality of possible sequences of (run, index derivative) pairs to determine an associated cost of each of the associated tth plurality of possible sequences of (run, index derivative) pairs;
(iii) selecting an associated tth cost-determined sequence of (run, index derivative) pairs from the associated tth plurality of possible sequences of (run, index derivative) pairs based on the associated cost of each of the associated tth plurality of possible sequences of (run, index derivative) pairs;
(e) after step (d), applying an aggregate cost function to the associated tth cost-determined sequence of (run, index derivative) pairs, for each sequence of n coefficients in the sequence of sequences of n coefficients, to determine a tth aggregate cost;
(f) if the tth aggregate cost meets a selection criterion, selecting the tth quantization table and run-index derivative coding distribution as the output quantization table and the output run-index derivative coding distribution, and, for each sequence of n coefficients in the sequence of sequences of n coefficients, the associated tth cost-determined sequence of (run, index derivative) pairs as the final cost-determined sequence of (run, index derivative) pairs;
otherwise determining a (t+1)th quantization table and run-index derivative coding distribution from the selected sequence of tth cost-determined sequences of (run, index derivative) pairs, increasing t by one, and returning to step (d);
and
(g) encoding each final cost-determined sequences of (run, index derivative) pairs using entropy coding based on the tth run-index derivative coding distribution.

9 more elements

A data processing system for compressing a sequence of n coefficients by determining a cost-determined sequence of n coefficient indices represented by a cost-determined sequence of (run, index derivative) pairs under a given quantization table and run-index derivative coding distribution, wherein each sequence of (run, index derivative) pairs 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, index derivative) pair defines a run value representing a number of consecutive indices of the special value, and an index-based value derived from a value of the index following the number of consecutive indices of the special value, the data processing system comprising:

(a) initialization means for using the given quantization table and run-index derivative coding distribution to formulate a cost function for a plurality of possible sequences of (run, index derivative) pairs;
and
(b) calculation means for applying the cost function to each possible sequence in the plurality of possible sequences of (run, index derivative) pairs to determine an associated cost of each of the plurality of possible sequences of (run, index derivative) pairs, and for selecting the cost-determined sequence of (run, index derivative) pairs from the plurality of possible sequences of (run, index derivative) pairs based on the associated cost of each of the plurality of possible sequences of (run, index derivative) pairs:
and encoding the cost-determined sequence of (run, index derivative) pairs using entropy coding based on the given run-index derivative coding distribution, wherein the calculation means is further operable to perform the steps of, for each possible sequence of (run, index derivative) pairs in the plurality of possible sequences of (run, index derivative) pairs:
(i) determining a corresponding sequence of n coefficient indices;
(ii) determining a corresponding sequence of n quantized coefficients using the given quantization table and the corresponding sequence of n coefficient indices;
(iii) determining a distortion between the sequence of n coefficients and the corresponding sequence of n quantized coefficients;
(iv) determining a total compression rate resulting from using the given run-index derivative coding distribution to encode the sequence of (run, index derivative) pairs;
and
(v) determining the associated cost of the sequence of (run, index derivative) pairs as a function of the distortion and the total compression rate.

7 more elements

A data processing system for compressing a sequence of n coefficients by determining an output quantization table, a final cost-determined sequence of n coefficient indices represented by a final cost-determined sequence of (run, index derivative) pairs, and a run-index derivative coding distribution, wherein each sequence of (run, index derivative) pairs 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, index derivative) pair defines a run value representing a number of consecutive indices of the special value, and an index-based value (derived from a value of the index following the number of consecutive indices of the special value, and wherein a sequence of n coefficient indices, together with a given quantization table, determines a sequence of n soft-decision quantized coefficients, the data processing system comprising:

(a) initialization means for selecting a 0th quantization table and a 0th run-index derivative coding distribution, and setting a counter t equal to 0;
(b) calculation means for (i) using a tth quantization table and run-index derivative coding distribution to formulate a tth cost function for a tth plurality of possible sequences of (run, index derivative) pairs;
(ii) applying the tth cost function to each possible sequence in the tth plurality of possible sequences of (run, index derivative) pairs to determine a tth associated cost of each of the tth plurality of possible sequences of (run, index derivative) pairs;
(iii) selecting a tth cost-determined sequence of (run, index derivative) pairs from the tth plurality of possible sequences of (run, index derivative) pairs based on the tth associated cost of each of the tth plurality of possible sequences of (run, index derivative) pairs;
(iv) if the tth cost-determined sequence of (run, index derivative) pairs together with the tth quantization table and run-index derivative coding distribution meets a selection criterion, selecting the tth cost-determined sequence of (run, index derivative) pairs as the final cost-determined sequence of (run, index derivative) pairs and the tth quantization table as the output quantization table, otherwise determining a (t+1)th quantization table and run-index derivative coding distribution from the tth cost-determined sequence of (run, index derivative) pairs, increasing t by one, and returning to step (i);
and (v) encoding the final cost-determined sequence of (run, index derivative) pairs using entropy coding based on the tth run-index derivative coding distribution.

3 more elements

A data processing system for compressing a sequence of sequences of n coefficients by jointly determining an output quantization table, an output run-index derivative coding distribution, and, for each sequence of n coefficients in the sequence of sequences of n coefficients, a final cost-determined sequence of coefficient indices represented by a final cost-determined sequence of (run, index derivative) pairs, wherein each sequence of (run, index derivative) pairs 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, index derivative) pair defines a run value representing a number of consecutive indices of the special value, and an index-based value derived from a value of the index following the number of consecutive indices of the special value, and wherein a sequence of n coefficient indices together with a given quantization table determines a sequence of n soft-decision quantized coefficients, the data processing system comprising:

(a) initialization means for selecting a 0th quantization table, selecting a 0th run-index derivative coding distribution and setting a counter t equal to 0;
(b) calculation means for selecting a sequence of tth cost-determined sequences of (run, index derivative) pairs by, for each sequence of n coefficients in the sequence of sequences of n coefficients, (i) using a tth quantization table and run-index derivative coding distribution to formulate a tth cost function for an associated tth plurality of possible sequences of (run, index derivative) pairs;
(ii) applying the tth cost function to each possible sequence in the associated tth plurality of possible sequences of (run, index derivative) pairs to determine an associated cost of each of the associated tth plurality of possible sequences of (run, index derivative) pairs;
(iii) selecting an associated tth cost-determined sequence of (run, index derivative) pairs from the associated tth plurality of possible sequences of (run, index derivative) pairs based on the associated cost of each of the associated tth plurality of possible sequences of (run, index derivative) pairs;
(iv) after steps (i) to (iii), applying an aggregate cost function to the associated tth cost-determined sequence of (run, index derivative) pairs for each sequence of n coefficients in the sequence of sequences of n coefficients, to determine a tth aggregate cost;
(v) if the tth aggregate cost meets a selection criterion, selecting the tth quantization table and run-index derivative coding distribution as the output quantization table and the output run-index derivative coding distribution, and, for each sequence of n coefficients in the sequence of sequences of n coefficients, the associated tth cost-determined sequence of (run, index derivative) pairs as the final cost-determined sequence of (run, index derivative) pairs;
otherwise determining a (t+1)th quantization table and run-index derivative coding distribution from the selected sequence of tth cost-determined sequences of (run, index derivative) pairs, increasing t by one, and returning to step (i);
and (vi) encoding each final cost-determined sequence of (run, index derivative) pairs using entropy coding based on the tth run-index derivative coding distribution.

5 more elements

A computer program product for use on a computer system to compress a sequence of n coefficients by determining a cost-determined sequence of n coefficient indices represented by a cost-determined sequence of (run, index derivative) pairs under a given quantization table and run-index derivative coding distribution, wherein each sequence of (run, index derivative) pairs 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, index derivative) pair defines a run value representing a number of consecutive indices of the special value, and an index-based value derived from a value of the index following the number of consecutive indices of the special value, the computer program product comprising a computer readable recording medium, and instructions recorded on the recording medium for instructing the computer system to perform the steps of:

(a) using the given quantization table and run-index derivative coding distribution to formulate a cost function for a plurality of possible sequences of (run, index derivative) pairs;
(b) applying the cost function to each possible sequence in the plurality of possible sequences of (run, index derivative) pairs to determine an associated cost of each of the plurality of possible sequences of (run, index derivative) pairs, wherein determining an associated cost comprises, for each possible sequence of (run, index derivative) pairs in the plurality of possible sequences of (run, index derivative) pairs:
(i) determining a corresponding sequence of n coefficient indices;
(ii) determining a corresponding sequence of n quantized coefficients using the given quantization table and the corresponding sequence of n coefficient indices;
(iii) determining a distortion between the sequence of n coefficients and the corresponding sequence of n quantized coefficients;
(iv) determining a total compression rate resulting from using the given run-index derivative coding distribution to encode the sequence of (run, index derivative) pairs;
and
(v) determining the associated cost of the sequence of (run, index derivative) pairs as a function of the distortion and the total compression rate;
and,
(c) selecting the cost-determined sequence of (run, index derivative) pairs from the plurality of possible sequences of (run, index derivative) pairs based on the associated cost of each of the plurality of possible sequences of (run, index derivative) pairs;
and encoding the cost-determined sequence of (run, index derivative) pairs using entropy coding based on the given run-index derivative coding distribution.

8 more elements

A computer program product for use on a computer system to compress a sequence of n coefficients by determining an output quantization table, a final cost-determined sequence of n coefficient indices represented by a final cost-determined sequence of (run, index derivative) pairs, and a run-index derivative coding distribution, wherein each sequence of (run, index derivative) pairs 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, index derivative) pair defines a run value representing a number of consecutive indices of the special value, and an index-based value (derived from a value of the index following the number of consecutive indices of the special value, and wherein a sequence of n coefficient indices, together with a given quantization table, determines a sequence of n soft-decision quantized coefficients, the computer program product comprising a computer readable recording medium and instructions recorded on the recording medium to instruct the computer system to perform the steps of:

(a) selecting a 0th quantization table;
(b) selecting a 0th run-index derivative coding distribution
(c) setting a counter t equal to 0;
(d) using a tth quantization table and run-index derivative coding distribution to formulate a tth cost function for a tth plurality of possible sequences of (run, index derivative) pairs;
(e) applying the tth cost function to each possible sequence in the tth plurality of possible sequences of (run, index derivative) pairs to determine a tth associated cost of each of the tth plurality of possible sequences of (run, index derivative) pairs;
(f) selecting a tth cost-determined sequence of (run, index derivative) pairs from the tth plurality of possible sequences of (run, index derivative) pairs based on the tth associated cost of each of the tth plurality of possible sequences of (run, index derivative) pairs;
(g) if the tth cost-determined sequence of (run, index derivative) pairs together with the tth quantization table and run-index derivative coding distribution, meets a selection criterion, selecting the tth cost-determined sequence of (run, index derivative) pairs as the final cost-determined sequence of (run, index derivative) pairs and the tth quantization table as the output quantization table, otherwise determining a (t+1)th quantization table and run-index derivative coding distribution from the tth cost-determined sequence of (run, index derivative) pairs, increasing t by one, and returning to step (d);
and
(h) encoding the cost-determined sequence of (run, index derivative) pairs using entropy coding based on the tth run-index derivative coding distribution.

6 more elements

A computer program product for use on a computer system to compress a sequence of sequences of n coefficients by jointly determining an output quantization table, an output run-index derivative coding distribution, and, for each sequence of n coefficients in the sequence of sequences of n coefficients, a final cost-determined sequence of coefficient indices represented by a final cost-determined sequence of (run, index derivative) pairs, wherein each sequence of (run, index derivative) pairs 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, index derivative) pair defines a run value representing a number of consecutive indices of the special value, and an index-based value derived from a value of the index following the number of consecutive indices of the special value, and wherein a sequence of n coefficient indices together with a given quantization table determines a sequence of n soft-decision quantized coefficients, the computer program product comprising a computer readable recording medium and instructions recorded on the recording medium to instruct the computer system to perform the steps of:

(a) selecting a 0th quantization table;
(b) selecting a 0th run-index derivative coding distribution
(c) setting a counter t equal to 0;
(d) selecting a sequence of tth cost-determined sequences of (run, index derivative) pairs by, for each sequence of n coefficients in the sequence of sequences of n coefficients,
(i) using a tth quantization table and run-index derivative coding distribution to formulate a tth cost function for an associated tth plurality of possible sequences of (run, index derivative) pairs;
(ii) applying the tth cost function to each possible sequence in the associated tth plurality of possible sequences of (run, index derivative) pairs to determine an associated cost of each of the associated tth plurality of possible sequences of (run, index derivative) pairs;
(iii) selecting an associated tth cost-determined sequence of (run, index derivative) pairs from the associated tth plurality of possible sequences of (run, index derivative) pairs based on the associated cost of each of the associated tth plurality of possible sequences of (run, index derivative) pairs;
(e) after step (d), applying an aggregate cost function to the associated tth cost-determined sequence of (run, index derivative) pairs, for each sequence of n coefficients in the sequence of sequences of n coefficients, to determine a tth aggregate cost;
(f) if the tth aggregate cost meets a selection criterion, selecting the tth quantization table and run-index derivative coding distribution as the output quantization table and the output run-index derivative coding distribution, and, for each sequence of n coefficients in the sequence of sequences of n coefficients, the associated tth cost-determined sequence of (run, index derivative) pairs as the final cost-determined sequence of (run, index derivative) pairs;
otherwise determining a (t+1)th quantization table and run-index derivative coding distribution from the selected sequence of tth cost-determined sequences of (run, index derivative) pairs, increasing t by one, and returning to step (d);
and
(g) encoding each final cost-determined sequences of (run, index derivative) pairs using entropy coding based on the tth run-index derivative coding distribution.

9 more elements

Dependencies are inferred from the claim text.

Method, system and computer program product for optimization of data compression

Life of this patent

Method, system and computer program product for optimization of data compression

Life of this patent

Abstract

Claims114