US5640159A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Quantization method for image data compression employing context modeling algorithm
Assignee: International Business Machines Corp
•
Filing: 1996-05-06
•
Granted: 1997-06-17
•
Expires: 2016-05-06
Abstract
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.
Inventors
- 👤 Gilbert Furlan
- 👤 Jorma Johannes Rissanen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 03:45
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/005; G11; G11B; G11B20/00; G11B20/00007; H; H03; H03M; H03M7/00; H03M7/30; H03M7/3053; H03M7/40; H03M7/4006; H04; H04N; H04N19/00; H04N19/10; H04N19/102; H04N19/124; H04N19/126; H04N19/134; H04N19/136; H04N19/90
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
130 words
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.
Claim 2
Independent Claim
130 words
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.
Claim 3
Dependent Claim
82 words
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.
Claim 4
Dependent Claim
28 words
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.
Claim 5
Dependent Claim
31 words
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.
Claim 6
Dependent Claim
66 words
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.
Claim 7
Dependent Claim
40 words
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.
Claim 8
Independent Claim
139 words
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.
Claim 9
Independent Claim
139 words
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.
Claim 10
Dependent Claim
66 words
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.
Claim 11
Dependent Claim
31 words
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.
Claim 12
Dependent Claim
34 words
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.
Claim 13
Dependent Claim
70 words
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.
Claim 14
Dependent Claim
43 words
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.
Claim 15
Dependent Claim
208 words
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.
Claim 16
Dependent Claim
208 words
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.
Claim 17
Dependent Claim
99 words
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.
Claim 18
Dependent Claim
46 words
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.
Claim 19
Dependent Claim
49 words
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.
Claim 20
Dependent Claim
97 words
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.
Claim 21
Dependent Claim
57 words
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.
References Cited (Backward Citations)
US4652856A
Cited
US5122873A
Cited
US5136663A
Cited
US5067152A
Cited
US5124791A
Cited
US5450132A
Cited
US5136374A
Cited
US5134478A
Cited
US5121191A
Cited
US5323187A
Cited
US5363099A
Cited
US5379355A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-06-16 | 2000-12-16 | 2001-06-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-06-16 | 2004-12-16 | 2005-06-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-06-16 | 2008-12-16 | 2009-06-17 | $7700.00 | Window Closed / Lapsed |