# US 2013/0336595 A1 · Method, system and computer program product for optimization of data compression with iterative cost function

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2013/0336595 A1
- Document ID: US20130336595A1
- Status: Published application
- Kind: A1
- Application number: 13/950,326
- Filed: 2013-07-25
- Published: 2013-12-19
- Earliest claimed: 2004-07-14
- Assignees: Slipstream Data Inc.
- Applicants: Slipstream Data Inc.
- Inventors: En-hui Yang; Longji Wang
- Web page: https://patentgrep.com/patent/US20130336595A1

## CPC

- H04N 1/415: in which the picture-elements are subdivided or grouped into fixed one-dimensional [1D] or two-dimensional [2D] blocks
- G06T 9/008: {Vector quantisation}
- H04N 19/126: Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
- H04N 19/13: Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
- H04N 19/147: according to rate distortion criteria (rate-distortion as a criterion for motion estimation H04N19/567)
- H04N 19/19: using optimisation based on Lagrange multipliers
- H04N 19/192: the adaptation method, adaptation tool or adaptation type being iterative or recursive
- H04N 19/60: using transform coding
- H04N 19/90: using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals
- H04N 19/93: Run-length coding
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## 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.

## Claims

### Claim 1

A method of compressing a sequence of N coefficients 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−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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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, (N) the (N−1)th stage is adjacent to (N−2)th stage, (iii) each ith 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.

### Claim 4 (depends on 3)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 3)

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.

### Claim 7 (depends on 6)

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

### Claim 8

A data processing system for compressing a sequence of N coefficients 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−1, the data processing system comprising:
(a) initialization means for 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; and,
(b) calculation means for applying 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.

### Claim 9 (depends on 8)

The data processing system as defined in claim 8 wherein the calculation means 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.

### Claim 10 (depends on 8)

The data processing system according to claim 8 wherein
each index in the N indices s selected from a set of M possible indices;
the calculation means 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, (i) each ith 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.

### Claim 11 (depends on 10)

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

### Claim 12 (depends on 8)

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 n JPEG and MPEG.

### Claim 13 (depends on 10)

The data processing system as defined in claim 10 wherein the calculation means 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.

### Claim 14 (depends on 13)

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

### Claim 15

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 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−1, the computer program product comprising a recording medium, and means recorded on the recording 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.

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 15)

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 ith stage, i being an integer between 1 and N−2 inclusive, is adjacent to an (i−1)th stage and an (i+1)th a 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.

### Claim 18 (depends on 17)

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.

### Claim 19 (depends on 15)

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.

### Claim 20 (depends on 17)

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.

### Claim 21 (depends on 20)

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