Patent ID: 7742643

Claim:
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.