US6154572A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Table based compression with embedded coding
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-06-30
•
Granted: 2000-11-28
•
Expires: 2017-06-30
Abstract
Abstract An image compression system includes a vectorizer and a hierarchical vector quantization table that outputs embedded code. The vectorizer converts an image into image vectors representing respective blocks of image pixels. The table provides computation-free transformation and compression of the image vectors. Table design can be divided into codebook design and fill-in procedures for each stage. Codebook design for the preliminary stages uses a splitting generalized Lloyd algorithm (LBG/GLA) using a perceptually weighted distortion measure. Codebook design for the final stage uses a greedily-grown and then entropy-pruned tree-structure variation of GLA with an entropy-constrained distortion measure. Table fill-in for all stages uses an unweighted proximity measure for assigning inputs to codebook vectors. Transformations and compression are fast because they are computation free. The hierarchical, multi-stage, character of the table allow it to operate with low memory requirements. The embedded output allows convenient scalability suitable for collaborative video applications over heterogeneous networks.
Inventors
- 👤 Navin Chaddha
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:56
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3082; H04; H04N; H04N19/00; H04N19/10; H04N19/134; H04N19/146; H04N19/147; H04N19/189; H04N19/19; H04N19/48; H04N19/50; H04N19/593; H04N19/60; H04N19/61; H04N19/63; H04N19/90; H04N19/94; H04N19/96; H04N19/102; H04N19/115
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
166 words
A data compression system, comprising: a vectorizer configured to convert data into a series of data vectors; a predictor configured to make a prediction of a current data vector based on at least one previous data vector, the predictor being coupled to the vectorizer for receiving the data vectors; a hierarchical lookup table configured to map residuals to a set of codes so that one of the codes is generated in response to each of the data vectors, each of the residuals representing a difference between the current data vector and the prediction, the lookup table being coupled to the predictor for receiving the data vectors; and wherein the hierarchical lookup table comprises at least a first stage lookup table designed using a codebook design procedure incorporating block transforms and a final stage lookup table designed using a tree structured codebook design procedure such that the residuals are mapped to the set of codes by successive utilization of the first stage and final stage lookup tables.
Claim 2
Dependent Claim
166 words
A data compression system, comprising: a vectorizer configured to convert data into a series of data vectors; a predictor configured to make a prediction of a current data vector based on at least one previous data vector, the predictor being coupled to the vectorizer for receiving the data vectors; a hierarchical lookup table configured to map residuals to a set of codes so that one of the codes is generated in response to each of the data vectors, each of the residuals representing a difference between the current data vector and the prediction, the lookup table being coupled to the predictor for receiving the data vectors; and wherein the hierarchical lookup table comprises at least a first stage lookup table designed using a codebook design procedure incorporating block transforms and a final stage lookup table designed using a tree structured codebook design procedure such that the residuals are mapped to the set of codes by successive utilization of the first stage and final stage lookup tables.
Claim 3
Dependent Claim
23 words
The system of claim 1, wherein the at least one previous data vector is a neighboring data vector to the current data vector.
Claim 4
Dependent Claim
28 words
The system of claim 1, wherein the prediction is obtained through a prediction lookup table configured to map the at least one previous data vector to the prediction.
Claim 5
Dependent Claim
21 words
The system of claim 1, wherein the residuals are obtained through a residual lookup table configured to map predictions to residuals.
Claim 6
Dependent Claim
15 words
The system of claim 1, wherein the set of codes comprise codes of different lengths.
Claim 7
Dependent Claim
13 words
The system of claim 1, wherein the set of codes comprise non-embedded codes.
Claim 8
Dependent Claim
20 words
The system of claim 1, wherein the data vectors are blocks of pixels of an image represented by the data.
Claim 9
Dependent Claim
141 words
In a computer system, a method of compressing data, comprising: receiving data as input; converting the data into a series of data vectors; making a prediction of a current data vector based on at least one previous data vector; utilizing a hierarchical lookup table, mapping residuals to a set of codes so that one of the codes is generated in response to each of the data vectors, each of the residuals representing a difference between the current data vector and the prediction; and wherein the hierarchical lookup table comprises at least a first stage lookup table designed using a codebook design procedure incorporating block transforms and a final stage lookup table designed using a tree structured codebook design procedure such that residuals are mapped to the set of codes by successive utilization of the first stage and final stage lookup tables.
Claim 10
Dependent Claim
141 words
In a computer system, a method of compressing data, comprising: receiving data as input; converting the data into a series of data vectors; making a prediction of a current data vector based on at least one previous data vector; utilizing a hierarchical lookup table, mapping residuals to a set of codes so that one of the codes is generated in response to each of the data vectors, each of the residuals representing a difference between the current data vector and the prediction; and wherein the hierarchical lookup table comprises at least a first stage lookup table designed using a codebook design procedure incorporating block transforms and a final stage lookup table designed using a tree structured codebook design procedure such that residuals are mapped to the set of codes by successive utilization of the first stage and final stage lookup tables.
Claim 11
Dependent Claim
23 words
The method of claim 8, wherein the at least one previous data vector is a neighboring data vector to the current data vector.
Claim 12
Dependent Claim
30 words
The method of claim 8, further comprising obtaining the prediction is obtained through a prediction lookup table configured to map the at least one previous data vector to the prediction.
Claim 13
Dependent Claim
21 words
The method of claim 8, further comprising obtaining the residuals through a residual lookup table configured to map predictions to residuals.
Claim 14
Dependent Claim
15 words
The method of claim 8, wherein the set of codes comprise codes of different lengths.
Claim 15
Dependent Claim
13 words
The method of claim 8, wherein the set of codes comprise non-embedded codes.
Claim 16
Dependent Claim
20 words
The method of claim 8, wherein the data vectors are blocks of pixels of an image represented by the data.
References Cited (Backward Citations)
US5341441A
Cited
US5060285A
Cited
US4987480A
Cited
US5282255A
Cited
US5371544A
Cited
US5592228A
Cited
US5521988A
Cited
US5602589A
Cited
US5623312A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-11-28 | 2004-05-29 | 2004-11-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-11-28 | 2008-05-29 | 2008-11-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-11-28 | 2012-05-29 | 2012-11-28 | $7700.00 | Window Closed / Lapsed |