Quantization method for image data compression employing context modeling algorithm

• US 5,640,159 A
• Filed: 05/06/1996
• Issued: 06/17/1997
• Est. Priority Date: 01/03/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rissanen, Jorma Johannes, Furlan, Gilbert
• Primary Examiner(s): Gaffin, Jeffrey A.
• Assistant Examiner(s): JEAN PIERRE, PEGUY
• Application Number:
  US08/643,201
• Time in Patent Office: 407 Days
• Field of Search: 341/107, 341/51
• US Class Current: 341/51
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: G11B 20/00007 Time or data compression or expansion audio compression based on psychoacoustics G10L19/00; data processing for reproducing audio data at different playback speeds G10L21/04; video compression H04N19/00; data compression per se H03M7/30
• CPC Class Codes: H03M 7/3053 Block-companding PCM systems
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code
• CPC Class Codes: H04N 19/126 Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
• CPC Class Codes: H04N 19/136 Incoming video signal characteristics or properties
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

Abstract

A method, system, and manufacture are provided, for use in connection with data processing and compression, for quantizing a string of data values, such as image data pixel values. The quantization is achieved by grouping the data values, based on their values, into a predetermined number of categories, each category containing the same total number of values. For each category, a value, preferably a mean value of those in the category, is selected as a quantization value. All of the data values in the category arc then represented by the selected quantization value. For data strings having a dependency (that is, the values of one or more of the data values provide information about values of other of the data values), the dependency is modeled by a method in which a modeling algorithm defines contexts in terms of a tree structure, and the basic method of grouping into categories and selecting a quantization value for each category is performed on a per node (i.e., per context) basis.

Claims

1. A method for performing data compression on data elements of a body of input data, each data element having a respective context, the method comprising the steps of:

quantizing each of the data elements separately, based on the context of that data element, thereby performing a lossy data compression of the data elements;

dividing the quantized data elements, by value, into a predetermined number of categories;

for each of the categories, selecting a respective value as a single quantized value to represent each of the data elements of the category;

determining whether the body of input data to be compressed has a dependency; and

,

responsive to a determination by the step of determining that the body of input data has a dependency, constructing a model to account for the dependency.

2. A method as recited in claim 1, wherein the step of dividing includes dividing the data elements such that, for each of the categories, a total probability of occurrence of all of the data elements within the category is the same, the total probability for each category being a sum of occurrence probabilities for each of the respective data elements within the category, the occurrence probability for each data clement being related to a number of past occurrences of the data clement.

3. A method as recited in claim 1 wherein the step of selecting includes, for each category, selecting the quantization value from among the data elements within the category.

4. A method as recited in claim 1 wherein the step of selecting includes, for each category, selecting the quantization value as a mean value of the data elements within the category.

5. A data compression method as recited in claim 1, wherein the step of constructing a model includes:

building a data tree made up of nodes which correspond with respective values of the data elements, and

selecting a respective context for each of the data elements, the step of selecting including obtaining a probability distribution for the data elements based on prior occurrences of the data elements.

6. A method as recited in claim 5, wherein the step of obtaining a probability distribution includes one of (i) obtaining a probability distribution for the data, and (ii) where the probability distribution is not known, using a predetermined probability distribution.

7. A system for performing data compression on data elements of a body of input data, each data element having a respective context, the system comprising:

means for quantizing each of the data elements separately, based on the context of that data element, thereby performing a lossy data compression of the data elements;

means for dividing the quantized data elements, by value, into a predetermined number of categories;

means, operable for each of the categories, for selecting a respective value as a single quantized value to represent each of the data elements of the category;

means for determining whether the body of input data to be compressed has a dependency; and

means operable responsive to a determination by the step of determining that the body of input date has a dependency, for constructing a model to account for the dependency.

8. A system as recited in claim 7, wherein the means for dividing includes means for dividing the data elements within the category is the same, the total probability for each category being a sum of occurrence probabilities for each of the respective data elements within the category, the occurrence probability for each data element being related to a number of past occurrences of the data element.

9. A system as recited in claim 7 wherein the means for selecting includes means, operable for each category, for selecting the quantization value from among the data elements within the category.

10. A system as recited in claim 7 wherein the means for selecting includes means, operable for each category, for selecting the quantization value as a mean value of the data elements within the category.

11. A system as recited in claim 7, wherein the means for constructing a model includes:

means for building a data tree made up of nodes which correspond with respective values of the data elements, and

means for selecting a respective context for each of the data elements, the means for selecting including means for obtaining a probability distribution for the data elements based on prior occurrences of the data elements.

12. A system as recited in claim 11, wherein the means for obtaining a probability distribution includes means, operable for one of (i) obtaining a probability distribution for the data, and (ii) where the probability distribution is not known, using a predetermined probability distribution.

13. A computer program product, for use with a data processing system, for performing data compression on data elements of a body of input data, each data element having a respective context, the computer program product comprising:

a computer-usable medium;

means, provided on the computer-usable medium, for directing the data processing system to quantize each of the data elements separately, based on the context of that data element, thereby performing a lossy data compression of the data elements;

means, provided on the computer-usable medium, for directing the data processing system to divide the quantized data elements, by value, into a predetermined number of categories;

means, provided on the computer-usable medium, operable for each of the categories, for directing the data processing system to select a respective value as a single quantized value to represent each of the data elements of the category;

means, provided on the computer-usable medium for directing the data processing system to determine whether the body of input data to be compressed has a dependency; and

,

means operable responsive to a determination by the step of determining that the body of input date has a dependency, provided on the computer-usable medium for directing the data processing system to construct a model to account for the dependency.

14. A computer program product as recited in claim 13, wherein the means for directing to divide includes means, provided on the computer-usable medium, for directing the data processing system to divide the data elements such that, for each of the categories, a total probability of occurrence of all of the data elements within the category is the same, the total probability for each category being a sum of occurrence probabilities for each of the respective data elements within the category, the occurrence probability for each data element being related to a number of past occurrences of the data element.

15. A computer program product as recited in claim 13 wherein the means for directing to select includes means, operable for each category, provided on the computer-usable medium, for directing the data processing system to select the quantization value from among the data elements within the category.

16. A computer program product as recited in claim 13 wherein the means for directing to select includes means, operable for each category, provided on the computer-usable medium, for directing the data processing system to select the quantization value as a mean value of the data elements within the category.

17. A computer program product as recited in claim 13, wherein the means for directing to construct a model includes:

means provided on the computer-usable medium, for directing the data processing system to build a data tree made up of nodes which correspond with respective values of the data elements, and selecting a respective context for each of the data elements; and

the means for directing to select including means, provided on the computer-usable medium, for directing the data processing system to obtain a probability distribution for the data elements based on prior occurrences of the data elements.

18. A computer program product as recited in claim 17, wherein the means for directing to obtain a probability distribution includes means, provided on the computer-usable medium, for directing the data processing system to one of (i) obtain a probability distribution for the data, and (ii) where the probability distribution is not known, use a predetermined probability distribution.