Method, system and computer program product for optimization of data compression with iterative cost function

1. A method of compressing a sequence of N coefficients, N being a positive integer, 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 i th index value minus an (i−1) th index value, i being greater than 0 and less than N−1, the method comprising the steps of:

(a) using the given quantization step size and the given size distribution to formulate a cost function for a plurality of possible sequences of differences, wherein for one possible sequence of differences the value of an index in the corresponding sequence of indices defined by the one possible sequence of differences is neither the value of the corresponding index resulting from quantizing the sequence of N coefficients using the given quantization step size nor the value of an immediately preceding index in the corresponding sequence of indices;

(b) applying the cost function to each possible sequence in the plurality of possible sequences of differences to determine an associated cost; and

(c) 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.

2. The method as defined in claim 1 wherein step (b) comprises, for each possible sequence in the plurality of possible differences:

determining a corresponding sequence of N indices;

determining a corresponding sequence of N quantized coefficients using the given quantization step size and the corresponding sequence of N indices;

determining a distortion between the sequence of N coefficients and the corresponding sequence of N quantized coefficients;

determining a total compression rate resulting from using the given size distribution to encode the sequence of possible differences; and

determining the associated cost as a function of the distortion and the total compression rate.

3. The method according to claim 1 wherein

each index in the N indices is selected from a set of M possible indices;

step (b) comprises:

providing a sequence of N stages in one-to-one relation with the sequence of N coefficients, wherein N is an integer greater than 2 and the sequence of N stages are ordered from a zero stage to an (N−1) th stage such that (i) the zero stage is adjacent to a first stage, (ii) the (N−1) th stage is adjacent to (N−2) th stage, (iii) each i th stage, i being an integer between 1 and N−2 inclusive, is adjacent to an (i−1) th stage and an (i+1) th stage;

providing a plurality of nodes in each stage in the sequence of N stages, wherein each node in each stage represents a possible index in the set of M possible indices for encoding an associated coefficient in the sequence of N coefficients;

providing an initial stage preceding the zero node, wherein the initial stage comprises a single node;

providing a plurality of connections for connecting each pair of nodes in adjacent stages;

determining the associated cost as an associated incremental cost for each connection in the plurality of connections; and

step (c) further comprises

determining the associated cost as a least-cost sequence of connections in the plurality of connections, wherein the least-cost sequence of connections extends from the initial stage through each stage in the sequence of N stages; and

determining the cost-determined sequence of N indices from the least-cost sequence of connections.

4. The method as defined in claim 3 , wherein step (c) further comprises using dynamic programming to find the least cost sequence of connections in the plurality of connections.

5. The method as defined in claim 3 wherein the method further comprises, for each stage in the sequence of N stages,

determining a hard-decision index using a hard-decision quantizer defined by the given quantization table to quantize the corresponding coefficient in the sequence of N coefficients; and,

selecting each node to represent a selected possible index within a selected difference of the hard-decision index such that the stage is a reduced stage having fewer than M nodes.

6. The method as defined in claim 5 , wherein step (c) further comprises using dynamic programming to find the least cost sequence of connections in the plurality of connections.

7. The method as defined in claim 1 , wherein the sequence of N coefficients are one of DC coefficients and quantized DC coefficients derived from an image in JPEG and MPEG.

8. A data processing system for compressing a sequence of N coefficients, N being a positive integer, 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 i th index value minus an (i−1) th index value, i being greater than 0 and less than N−1, the data processing system comprising a memory configured to store programs; a microprocessor configured to execute the stored programs to:

(a) use the given quantization step size and the given size distribution to formulate a cost function for a plurality of possible sequences of differences, wherein for one possible sequence of differences the value of an index in the corresponding sequence of indices defined by the one possible sequence of differences is neither the value of the corresponding index resulting from quantizing the sequence of N coefficients using the given quantization step size nor the value of an immediately preceding index in the corresponding sequence of indices; and,

(b) apply the cost function to each possible sequence in the plurality of possible sequences of differences to determine an associated cost; and 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.

9. The data processing system as defined in claim 8 wherein the microprocessor is operable to, for each possible sequence in the plurality of possible differences:

determine a corresponding sequence of N indices;

determine a corresponding sequence of N quantized coefficients using the given quantization step size and the corresponding sequence of N indices;

determine a distortion between the sequence of N coefficients and the corresponding sequence of N quantized coefficients;

determine a total compression rate resulting from using the given size distribution to encode the sequence of possible differences; and

determine the associated cost as a function of the distortion and the total compression rate.

10. The data processing system according to claim 8 wherein

each index in the N indices is selected from a set of M possible indices;

the microprocessor is operable to

provide a sequence of N stages in one-to-one relation with the sequence of N coefficients, wherein N is an integer greater than 2 and the sequence of N stages are ordered from a zero stage to an (N−1) th stage such that (i) the zero stage is adjacent to a first stage, (ii) the (N−1) th stage is adjacent to (N−2) th stage, (iii) each i th stage, i being an integer between 1 and N−2 inclusive, is adjacent to an (i−1) th stage and an (i+1) th stage;

provide a plurality of nodes in each stage in the sequence of N stages, wherein each node in each stage represents a possible index in the set of M possible indices for encoding an associated coefficient in the sequence of N coefficients;

provide an initial stage preceding the zero node, wherein the initial stage comprises a single node;

provide a plurality of connections for connecting each pair of nodes in adjacent stages;

determine the associated cost as an associated incremental cost for each connection in the plurality of connections;

determine the associated cost as a least-cost sequence of connections in the plurality of connections, wherein the least-cost sequence of connections extends from the initial stage through each stage in the sequence of N stages; and

determine the cost-determined sequence of N indices from the least-cost sequence of connections.

11. The data processing system as defined in claim 10 , wherein the microprocessor is operable to, use dynamic programming to find the least cost sequence of connections in the plurality of connections.

12. The data processing system as defined in claim 10 wherein the microprocessor is further operable to, for each stage in the sequence of N stages,

determine a hard-decision index using a hard-decision quantizer defined by the given quantization table to quantize the corresponding coefficient in the sequence of N coefficients; and,

select each node to represent a selected possible index within a selected difference of the hard-decision index such that the stage is a reduced stage having fewer than M nodes.

13. The data processing system as defined in claim 12 , wherein the microprocessor uses dynamic programming to find the least cost sequence of connections in the plurality of connections.

14. The data processing system as defined in claim 8 , wherein the sequence of N coefficients are one of DC coefficients and quantized DC coefficients derived from an image in JPEG and MPEG.

15. A computer program product for use on a computer system to compress a sequence of N coefficients, N being a positive integer, 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 i th index value minus an (i−1) th index value, i being greater than 0 and less than N−1, the computer program product comprising a non-transitory computer-readable medium, and means recorded on the medium to instruct the computer system to perform the steps of:

(a) using the given quantization step size and the given size distribution to formulate a cost function for a plurality of possible sequences of differences, wherein for one possible sequence of differences the value of an index in the corresponding sequence of indices defined by the one possible sequence of differences is neither the value of the corresponding index resulting from quantizing the sequence of N coefficients using the given quantization step size nor the value of an immediately preceding index in the corresponding sequence of indices;

(b) applying the cost function to each possible sequence in the plurality of possible sequences of differences to determine an associated cost; and

(c) 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.

16. The computer program product as defined in claim 15 wherein step (b) comprises, for each possible sequence in the plurality of possible differences:

determining a corresponding sequence of N indices;

determining a corresponding sequence of N quantized coefficients using the given quantization step size and the corresponding sequence of N indices;

determining a distortion between the sequence of N coefficients and the corresponding sequence of N quantized coefficients;

determining a total compression rate resulting from using the given size distribution to encode the sequence of possible differences; and

determining the associated cost as a function of the distortion and the total compression rate.

17. The computer program product according to claim 15 wherein

each index in the N indices is selected from a set of M possible indices;

step (b) comprises:

providing a sequence of N stages in one-to-one relation with the sequence of N coefficients, wherein N is an integer greater than 2 and the sequence of N stages are ordered from a zero stage to an (N−1) th stage such that (i) the zero stage is adjacent to a first stage, (ii) the (N−1) th stage is adjacent to (N−2) th stage, (iii) each i th stage, i being an integer between 1 and N−2 inclusive, is adjacent to an (i−1) th stage and an (i+1) th stage;

providing a plurality of nodes in each stage in the sequence of N stages, wherein each node in each stage represents a possible index in the set of M possible indices for encoding an associated coefficient in the sequence of N coefficients;

providing an initial stage preceding the zero node, wherein the initial stage comprises a single node;

providing a plurality of connections for connecting each pair of nodes in adjacent stages;

determining the associated cost as an associated incremental cost for each connection in the plurality of connections; and

step (c) further comprises

determining the associated cost as a least-cost sequence of connections in the plurality of connections, wherein the least-cost sequence of connections extends from the initial stage through each stage in the sequence of N stages; and

determining the cost-determined sequence of N indices from the least-cost sequence of connections.

18. The computer program product as defined in claim 17 , wherein step (c) further comprises using dynamic programming to find the least cost sequence of connections in the plurality of connections.

19. The computer program product as defined in claim 17 wherein the computer program product further comprises, for each stage in the sequence of N stages,

determining a hard-decision index using a hard-decision quantizer defined by the given quantization table to quantize the corresponding coefficient in the sequence of N coefficients; and,

selecting each node to represent a selected possible index within a selected difference of the hard-decision index such that the stage is a reduced stage having fewer than M nodes.

20. The computer program product as defined in claim 19 , wherein step (c) further comprises using dynamic programming to find the least cost sequence of connections in the plurality of connections.

21. The computer program product as defined in claim 15 , wherein the sequence of N coefficients are one of DC coefficients and quantized DC coefficients derived from an image in JPEG and MPEG.