# US 7,978,923 B2 · Method, system and computer program product for optimization of data compression > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,978,923 B2 - Document ID: US7978923B2 - Status: Granted - Kind: B2 - Application number: 12/774,313 - Filed: 2010-05-05 - Published: 2010-10-28 - Granted: 2011-07-12 - Earliest claimed: 2004-07-14 - Assignees: Slipstream Data Inc. - Inventors: En-hui Yang; Longji Wang - Web page: https://patentgrep.com/patent/US7978923B2 ## CPC - H03M 7/4006: {Conversion to or from arithmetic code} - H03M 7/46: Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind - H04N 19/124: Quantisation - 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/176: the region being a block, e.g. a macroblock - H04N 19/19: using optimisation based on Lagrange multipliers - H04N 19/60: using transform coding - H04N 19/91: Entropy coding, e.g. variable length coding [VLC] or arithmetic coding - H04N 19/93: Run-length coding - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION ## 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. ## Claims ### Claim 1 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 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 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; 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 a run-index derivative coding distribution, wherein selecting the cost-determined sequence of (run, index derivative) pairs comprises: (i) providing a sequence of n super nodes, each super node comprising at least one node, in one-to-one relation with the sequence of n coefficients, such that each coefficient Ci has a corresponding ith super node wherein i is greater than or equal to 1 and less than or equal to n; (ii) providing an initial node preceding and an end node following the sequence of n super nodes; (iii) providing a plurality of connections between pairs of nodes including the initial node, super nodes, and the end node to represent a plurality of possible (run, index derivative) pairs; (iv) determining the associated cost of each of the plurality of possible sequences of (run, index derivative) pairs by determining an associated incremental cost for each connection in the plurality of connections; (v) determining a least cost sequence of connections from the plurality of connections, wherein the least cost sequence of connections extends from the initial node to the end node via at least one super node; and, (vi) determining the cost-determined sequence of (run, index derivative) pairs from the least cost sequence of connections. ### Claim 2 (depends on 1) The method as defined in claim 1, wherein step (c)(v) further comprises using dynamic programming to find the least cost sequence of connections in the plurality of connections, wherein the least cost sequence of connections extends from the initial node to the end node via at least one super node. ### Claim 3 (depends on 1) The method as defined in claim 1, wherein step (c)(iv) further comprises: defining an incremental rate cost, for each connection, representing an associated (run, index derivative) pair, from one of the initial node and an (i−r−1)th super node to an ith super node, as a number of bits needed to encode the run value of the associated (run, index derivative) pair and the index-based value derived from the associated (run, index derivative) pair; defining an incremental distortion cost, for each connection from one of the initial node and the (i−r−1)th super node to the ith super node, as a distortion incurred when the coefficient Ci is quantized to a value associated with the index-based value derived from the associated (run, index derivative) pair and all r coefficients appearing from coefficient Ci-r to coefficient Ci-1 are quantized to the special value; and defining the associated incremental cost, for each connection from one of the initial node and the (i−r−1)th super node to the ith super node, as a function of the incremental distortion cost and the incremental rate cost. ### Claim 4 (depends on 1) The method as defined in claim 1, wherein each (run, index derivative) pair is a (run, level) pair such that the index-based value is defined to be a level value defined as the value of the index following the number of consecutive indices of the special value. ### Claim 5 (depends on 4) The method as defined in claim 4 wherein providing the plurality of connections between the pairs of nodes including the initial node, the super nodes, and the end node comprises: for each super node in the sequence of n super nodes, and for each predecessor node including the initial node preceding that super node in the sequence of n super nodes and the initial node, wherein that super node and that predecessor node are separated by a number of intermediary nodes not exceeding a maximum run value in the plurality of possible (run, level) pairs, establishing a number of connections connecting that super node to that predecessor node equaling up to four times a maximum level of magnitude in the plurality of possible (run, level) pairs, wherein each connection between a pair of connected nodes corresponds to a different level value; for each super node other than the last super node in the sequence of n super nodes, and for each predecessor node including the initial node preceding that super node in the sequence of n super nodes, wherein the number of intermediary nodes separating that super node and that predecessor node equals the maximum run value in the plurality of (run, level) pairs, establishing up to two further connections connecting that super node to that predecessor node; and, for each node in the sequence of n super nodes and the initial node, establishing a single connection to the end node. ### Claim 6 (depends on 5) The method as defined in claim 5 wherein the run value and the level value of each (run, level) pair in the cost-determined sequence of (run, level) pairs are separately encoded. ### Claim 7 (depends on 6) The method as defined in claim 6 wherein the sequence of n coefficients comprises a first group of coefficients and a second group of coefficients disjoint from the first group of coefficients; and encoding the cost-determined sequence of (run, level) pairs comprises encoding the run value of each (run, level) pair in the cost-determined sequence of (run, level) pairs based on both the level value and an ordered location of the index preceding the number of consecutive indices of the special value associated with the run in the sequence of n coefficients, if the coefficient corresponding to the index preceding the number of consecutive indices of the special value associated with the run is in the first group of coefficients, and the ordered location of the index preceding the number of consecutive indices of the special value associated with the run in the sequence of n coefficients, if the coefficient corresponding to the index preceding the number of consecutive indices of the special value associated with the run is in the second group of coefficients. ### Claim 8 (depends on 7) The method as defined in claim 7 wherein each super node having a corresponding coefficient in the first group of coefficients comprises two associated nodes; each super node having a corresponding coefficient in the second group of coefficients comprises a single associated node; and, the plurality of connections between pairs of super nodes comprises a plurality of connections between non-associated pairs of nodes representing the plurality of possible (run, level) pairs. ### Claim 9 (depends on 8) The method as defined in claim 8 wherein providing the plurality of connections between pairs of super nodes further comprises: for each super node in the sequence of n super nodes, determining an output level using a hard-decision quantizer defined by the given quantization table to quantize the corresponding coefficient in the sequence of n coefficients; and for each super node in the sequence of n super nodes, and for each predecessor node preceding that super node in the sequence of n super nodes, the predecessor node being the initial node or a super node, wherein the number of intermediary nodes separating that super node and that predecessor node does not exceed the maximum run value in the plurality of possible (run, level) pairs, establishing a reduced number of connections connecting a node in that super node to that predecessor node, wherein each connection between a pair of connected nodes in the reduced number of connections corresponds to a different level value within a selected difference of the output level determined for that super node. ### Claim 10 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 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) 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; (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 a run-index derivative coding distribution, wherein the calculation means is further operable to perform the steps of: (i) providing a sequence of n super nodes, each super node comprising at least one node, in one-to-one relation with the sequence of n coefficients, such that each coefficient Ci has a corresponding ith super node wherein i is greater than or equal to 1 and less than or equal to n; (ii) providing an initial node preceding and an end node following the sequence of n super nodes; (iii) providing a plurality of connections between pairs of nodes including the initial node, super nodes, and the end node to represent a plurality of possible (run, index derivative) pairs; (iv) determining the associated cost of each of the plurality of possible sequences of (run, index derivative) pairs by determining an associated incremental cost for each connection in the plurality of connections; (v) determining a least cost sequence of connections from the plurality of connections, wherein the least cost sequence of connections extends from the initial node to the end node via at least one super node; and, (vi) determining the cost-determined sequence of (run, index derivative) pairs 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 further operable to use dynamic programming to find the least cost sequence of connections in the plurality of connections, wherein the least cost sequence of connections extends from the initial node to the end node via at least one super node. ### Claim 12 (depends on 10) The data processing system as defined in claim 10, wherein the calculation means is further operable to perform the steps of: (vii) defining an incremental rate cost, for each connection, representing an associated (run, index derivative) pair, from one of the initial node and an (i−r−1)th super node to an ith super node, as a number of bits needed to encode the run value of the associated (run, index derivative) pair and the index-based value derived from the associated (run, index derivative) pair; (viii) defining an incremental distortion cost, for each connection from one of the initial node and the (i−r−1)th super node to the ith super node, as a distortion incurred when the coefficient Ci is quantized to a value associated with the index-based value derived from the associated (run, index derivative) pair and all r coefficients appearing from the coefficient Ci-r to the coefficient Ci-1 are quantized to the special value; and (ix) defining the associated incremental cost, for each connection from one of the initial node and the (i−r−1)th super node to the ith super node, as a function of the incremental distortion cost and the incremental rate cost. ### Claim 13 (depends on 10) The data processing system as defined in claim 10, wherein each (run, index derivative) pair is a (run, level) pair such that the index-based value is defined to be a level value defined as the value of the index following the number of consecutive indices of the special value. ### Claim 14 (depends on 13) The data processing system as defined in claim 13 wherein providing the pairs of connections between the pairs of nodes including the initial node, the super nodes, and the end node comprises: for each super node in the sequence of n super nodes, and for each predecessor node including the initial node preceding that super node in the sequence of n super nodes and the initial node, wherein that super node and that predecessor node are separated by a number of intermediary nodes not exceeding a maximum run value in the plurality of possible (run, level) pairs, establishing a number of connections connecting that super node to that predecessor node equaling up to four times a maximum level of magnitude in the plurality of possible (run, level) pairs, wherein each connection between a pair of connected nodes corresponds to a different level value; for each super node other than the last super node in the sequence of n super nodes, and for each predecessor node including the initial node preceding that super node in the sequence of n super nodes, wherein the number of intermediary nodes separating that super node and that predecessor node equals the maximum run value in the plurality of (run, level) pairs, establishing up to two further connections connecting that super node to that predecessor node; and, for each node in the sequence of n super nodes and the initial node, establishing a single connection to the end node. ### Claim 15 (depends on 14) The data processing system as defined in claim 14 wherein the run value and the level value of each (run, level) pair in the cost-determined sequence of (run, level) pairs are separately encoded. ### Claim 16 (depends on 14) The data processing system as defined in claim 14 wherein the sequence of n coefficients comprises a first group of coefficients and a second group of coefficients disjoint from the first group of coefficients; and the calculation means is operable to encode the run value of each (run, level) pair in the cost-determined sequence of (run, level) pairs based on both the level value and an ordered location of the index preceding the number of consecutive indices of the special value associated with the run in the sequence of n coefficients, if the coefficient corresponding to the index preceding the number of consecutive indices of the special value associated with the run is in the first group of coefficients, and the ordered location of the index preceding the number of consecutive indices of the special value associated with the run in the sequence of n coefficients, if the coefficient corresponding to the index preceding the number of consecutive indices of the special value associated with the run is in the second group of coefficients. ### Claim 17 (depends on 16) The data processing system as defined in claim 16 wherein each super node having a corresponding coefficient in the first group of coefficients comprises two associated nodes; each super node having a corresponding coefficient in the second group of coefficients comprises a single associated node; and, the plurality of connections between pairs of super nodes comprises a plurality of connections between non-associated pairs of nodes representing the plurality of possible (run, level) pairs. ### Claim 18 (depends on 17) The data processing system as defined in claim 17 wherein providing the plurality of connections between the plurality of super nodes further comprises: for each super node in the sequence of n super nodes, determining an output level using a hard-decision quantizer defined by the given quantization table to quantize the corresponding coefficient in the sequence of n coefficients; and for each super node in the sequence of n super nodes, and for each predecessor node preceding that super node in the sequence of n super nodes, the predecessor node being the initial node or a super node, wherein the number of intermediary nodes separating that super node and that predecessor node does not exceed the maximum run value in the plurality of possible (run, level) pairs, establishing a reduced number of connections connecting a node in that super node to that predecessor node, wherein each connection between a pair of connected nodes in the reduced number of connections corresponds to a different level value within a selected difference of the output level determined for that super node. ### Claim 19 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 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 means 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; 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 a run-index derivative coding distribution, wherein selecting the cost-determined sequence of (run, index derivative) pairs comprises: (i) providing a sequence of n super nodes, each super node comprising at least one node, in one-to-one relation with the sequence of n coefficients, such that each coefficient Ci has a corresponding ith super node wherein i is greater than or equal to 1 and less than or equal to n; (ii) providing an initial node preceding and an end node following the sequence of n super nodes; (iii) providing a plurality of connections between pairs of nodes including the initial node, super nodes, and the end node to represent a plurality of possible (run, index derivative) pairs; (iv) determining the associated cost of each of the plurality of possible sequences of (run, index derivative) pairs by determining an associated incremental cost for each connection in the plurality of connections; (v) determining a least cost sequence of connections from the plurality of connections, wherein the least cost sequence of connections extends from the initial node to the end node via at least one super node; and, (vi) determining the cost-determined sequence of (run, index derivative) pairs from the least cost sequence of connections. ### Claim 20 (depends on 19) The computer program product as defined in claim 19, wherein step (c)(v) further comprises using dynamic programming to find the least cost sequence of connections in the plurality of connections, wherein the least cost sequence of connections extends from the initial node to the end node via at least one super node. ### Claim 21 (depends on 19) The computer program product as defined in claim 19, wherein step (c)(iv) further comprises: defining an incremental rate cost, for each connection, representing an associated (run, index derivative) pair, from one of the initial node and an (i−r−1)th super node to an ith super node, as a number of bits needed to encode the run value of the associated (run, index derivative) pair and the index-based value derived from the associated (run, index derivative) pair; defining an incremental distortion cost, for each connection from one of the initial node and the (i−r−1)th super node to the ith super node, as a distortion incurred when the coefficient Ci is quantized to a value associated with the index-based value derived from the associated (run, index derivative) pair and all r coefficients appearing from the coefficient Ci-r to the coefficient Ci-1 are quantized to the special value; and defining an associated incremental cost, for each connection from one of the initial node and the (i−r−1)th super node to the ith super node, as a function of the incremental distortion cost and the incremental rate cost. ### Claim 22 (depends on 19) The computer program product as defined in claim 19, wherein each (run, index derivative) pair is a (run, level) pair such that the index-based value is defined to be a level value defined as the value of the index following the number of consecutive indices of the special value. ### Claim 23 (depends on 22) The computer program product as defined in claim 22 wherein providing the plurality of connections between the plurality of nodes including the initial node, the super nodes, and the end node comprises: for each super node in the sequence of n super nodes, and for each predecessor node including the initial node preceding that super node in the sequence of n super nodes and the initial node, wherein that super node and that predecessor node are separated by a number of intermediary nodes not exceeding a maximum run value in the plurality of possible (run, level) pairs, establishing a number of connections connecting that super node to that predecessor node equaling up to four times a maximum level of magnitude in the plurality of possible (run, level) pairs, wherein each connection between a pair of connected nodes corresponds to a different level value; for each super node other than the last super node in the sequence of n super nodes, and for each predecessor node including the initial node preceding that super node in the sequence of n super nodes, wherein the number of intermediary nodes separating that super node and that predecessor node equals the maximum run value in the plurality of (run, level) pairs, establishing up to two further connections connecting that super node to that predecessor node; and, for each node in the sequence of n super nodes and the initial node, establishing a single connection to the end node. ### Claim 24 (depends on 23) The computer program product as defined in claim 23 wherein the run value and the level value of each (run, level) pair in the cost-determined sequence of (run, level) pairs are separately encoded. ### Claim 25 (depends on 24) The computer program product as defined in claim 24 wherein the sequence of n coefficients comprises a first group of coefficients and a second group of coefficients disjoint from the first group of coefficients; and encoding the cost-determined sequence of (run, level) pairs comprises encoding the run value of each (run, level) pair in the corresponding cost-determined sequence of (run, level) pairs based on both the level value and an ordered location of the index preceding the number of consecutive indices of the special value associated with the run in the sequence of n coefficients, if the coefficient corresponding to the index preceding the number of consecutive indices of the special value associated with the run is in the first group of coefficients, and the ordered location of the index preceding the number of consecutive indices of the special value associated with the run in the sequence of n coefficients, if the coefficient corresponding to the index preceding the number of consecutive indices of the special value associated with the run is in the second group of coefficients. ### Claim 26 (depends on 25) The computer program product as defined in claim 25 wherein each super node having a corresponding coefficient in the first group of coefficients comprises two associated nodes; each super node having a corresponding coefficient in the second group of coefficients comprises a single associated node; and, the plurality of connections between pairs of super nodes comprises a plurality of connections between non-associated pairs of nodes representing the plurality of possible (run, level) pairs. ### Claim 27 (depends on 26) The computer program product as defined in claim 26 wherein providing the plurality of connections between the pairs of super nodes further comprises: for each super node in the sequence of n super nodes, determining an output level using a hard-decision quantizer defined by the given quantization table to quantize the corresponding coefficient in the sequence of n coefficients; and for each super node in the sequence of n super nodes, and for each predecessor node preceding that super node in the sequence of n super nodes, the predecessor node being the initial node or a super node, wherein the number of intermediary nodes separating that super node and that predecessor node does not exceed the maximum run value in the plurality of possible (run, level) pairs, establishing a reduced number of connections connecting a node in that super node to that predecessor node, wherein each connection between a pair of connected nodes in the reduced number of connections corresponds to a different level value within a selected difference of the output level determined for that super node.