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.
Claims51
A method of compressing a sequence of N+M coefficients, N and M being two positive integers, by determining a cost-determined sequence of N indices represented by a corresponding cost-determined sequence of differences under a given quantization step size and a given size distribution, wherein a sequence of differences defines a corresponding sequence of N indices such that each difference in the sequence of differences is a digital number equaling an ith index value minus an (i−1)th index value, i being greater than 0 and less than N, and a cost-determined sequence of (run, index derivative) pairs under a given quantization table and context model distribution, wherein each sequence of (run, index derivative) pairs defines a corresponding sequence of M coefficient indices such that each index in the corresponding sequence of coefficient indices is a digital number, the corresponding sequence of coefficient indices includes a plurality of values including a special value, and 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:
- (a) using the given quantization table and context model distribution to formulate a first cost function for a plurality of possible sequences of (run, index derivative) pairs;
- (b) applying the first 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;
- (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,
- (d) using the given quantization step size and the given size distribution to formulate a second cost function for a plurality of possible sequences of N differences;
- (e) applying the second cost function to each possible sequence in the plurality of possible sequences of differences to determine an associated cost;
- and
- (f) selecting the corresponding cost-determined sequence of differences from the plurality of possible sequences of differences based on the associated cost, and determining the cost-determined sequence of N indices from the corresponding cost-determined sequence of differences.
A data processing system for compressing a sequence of N+M coefficients, N and M being two positive integers, by determining a cost-determined sequence of N indices represented by a corresponding cost-determined sequence of differences under a given quantization step size and a given size distribution, wherein a sequence of differences defines a corresponding sequence of N indices such that each difference in the sequence of differences is a digital number equaling an ith index value minus an (i−1)th index value, i being greater than 0 and less than N, and a cost-determined sequence of (run, index derivative) pairs under a given quantization table and context model distribution, wherein each sequence of (run, index derivative) pairs defines a corresponding sequence of M coefficient indices such that each index in the corresponding sequence of coefficient indices is a digital number, the corresponding sequence of coefficient indices includes a plurality of values including a special value, and 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 microprocessor configured:
- (a) to use the given quantization table and context model distribution to formulate a first cost function for a plurality of possible sequences of (run, index derivative) pairs, and to use the given quantization step size and the given size distribution to formulate a second cost function for a plurality of possible sequences of N differences;
- (b) to apply the first 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, to select 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, to apply the second cost function to each possible sequence in the plurality of possible sequences of differences to determine an associated cost, and to select the corresponding cost-determined sequence of differences from the plurality of possible sequences of differences based on the associated cost, and to determine the cost-determined sequence of N indices from the corresponding cost-determined sequence of differences.
A computer program product for use on a computer system to compress a sequence of N+M coefficients, N and M being two positive integers, by determining a cost-determined sequence of N indices represented by a corresponding cost-determined sequence of differences under a given quantization step size and a given size distribution, wherein a sequence of differences defines a corresponding sequence of N indices such that each difference in the sequence of differences is a digital number equaling an ith index value minus an (i−1)th index value, i being greater than 0 and less than N, and a cost-determined sequence of (run, index derivative) pairs under a given quantization table and context model distribution, wherein each sequence of (run, index derivative) pairs defines a corresponding sequence of M coefficient indices such that each index in the corresponding sequence of coefficient indices is a digital number, the corresponding sequence of coefficient indices includes a plurality of values including a special value, and 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 non-transitory 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 context model distribution to formulate a first cost function for a plurality of possible sequences of (run, index derivative) pairs;
- (b) applying the first 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
- (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,
- (d) using the given quantization step size and the given size distribution to formulate a second cost function for a plurality of possible sequences of N differences;
- (e) applying the second cost function to each possible sequence in the plurality of possible sequences of differences to determine an associated cost;
- and
- (f) selecting the corresponding cost-determined sequence of differences from the plurality of possible sequences of differences based on the associated cost, and determining the cost-determined sequence of N indices from the corresponding cost-determined sequence of differences.
Dependencies are inferred from the claim text.