US5760716A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Vector data compression
Assignee: Autodesk Inc
•
Filing: 1996-08-21
•
Granted: 1998-06-02
•
Expires: 2016-08-21
Abstract
Abstract The present invention discloses a method, apparatus, and article of manufacture for compressing vector data. The vector data is normalized to create normalized vector data. A history buffer is searched for a longest matching vector data that matches the normalized vector data. The longest matching vector data is encoded by assigning a substitution code. The vector data is normalized by translating the vector data to an origin and scaling the vector data to a unit square. The substitution code includes a denormalization function, which converts the normalized vector data to vector data.
Inventors
- 👤 Brian P. Mathews
- 👤 Robert D. Covey
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:31
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3086; G; G06; G06T; G06T9/00; G06T9/005; G06T9/008
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
119 words
A method of compressing vector data using a history buffer, comprising the steps of: normalizing the vector data, wherein the vector data is comprised of one or more primitives representing one or more graphics objects and one or more coordinate values indicating locations for each of the graphics object, and the normalizing step comprises the steps of translating the locations of the graphics objects to an origin and scaling the coordinate values of the graphic objects; searching the history buffer for a longest matching vector data that matches the normalized vector data; and when the searching step finds the longest matching vector data, encoding the longest matching vector data found in the history buffer by assigning a substitution code.
Claim 2
Independent Claim
119 words
A method of compressing vector data using a history buffer, comprising the steps of: normalizing the vector data, wherein the vector data is comprised of one or more primitives representing one or more graphics objects and one or more coordinate values indicating locations for each of the graphics object, and the normalizing step comprises the steps of translating the locations of the graphics objects to an origin and scaling the coordinate values of the graphic objects; searching the history buffer for a longest matching vector data that matches the normalized vector data; and when the searching step finds the longest matching vector data, encoding the longest matching vector data found in the history buffer by assigning a substitution code.
Claim 3
Dependent Claim
74 words
The method of claim 1, wherein the step of searching in the history buffer further comprises the steps of: storing a hashing function of the history buffer vector data in a hash table, the hash table having a plurality of entries, the entries having a pointer to a location in the history buffer; and searching in the hash table entries by comparing the hash table entries to a hashing function of the vector data.
Claim 4
Dependent Claim
27 words
The method of claim 2, further comprising the step of comparing the vector data to the history buffer vector data pointed to by the hash table entry.
Claim 5
Dependent Claim
14 words
The method of claim 1, wherein the substitution code further comprises a denormalization function.
Claim 6
Dependent Claim
36 words
The method of claim 1, wherein the substitution code further comprises an operation code, a length of the matching vector data, and a pointer indicating the position within the history buffer of the matching vector data.
Claim 7
Dependent Claim
23 words
The method of claim 1, wherein the step of encoding further comprises the step of storing the substitution code in the history buffer.
Claim 8
Dependent Claim
22 words
The method of claim 1, wherein the normalizing step further comprises the step of scaling the vector data to a unit square.
Claim 9
Dependent Claim
22 words
The method of claim 1, wherein the history buffer has a plurality of entries for storing vector data and coded vector data.
Claim 10
Independent Claim
145 words
An apparatus for compressing vector data, comprising: a computer having a memory, a monitor, and a data storage device; means, performed by the computer, for normalizing the vector data, wherein the vector data is comprised of one or more primitives representing one or more graphics object and one or more coordinate values indicating locations for each of the graphics object, and the means for normalizing comprises means for translating the locations of the graphics objects to an origin and for scaling the coordinate values of the graphic objects; means, performed by the computer, for searching in a history buffer for a longest matching vector data that matches the normalized vector data; and means, performed by the computer, for encoding the longest matching vector data found in the history buffer, when the means for searching finds the longest matching vector data, by assigning a substitution code.
Claim 11
Independent Claim
145 words
An apparatus for compressing vector data, comprising: a computer having a memory, a monitor, and a data storage device; means, performed by the computer, for normalizing the vector data, wherein the vector data is comprised of one or more primitives representing one or more graphics object and one or more coordinate values indicating locations for each of the graphics object, and the means for normalizing comprises means for translating the locations of the graphics objects to an origin and for scaling the coordinate values of the graphic objects; means, performed by the computer, for searching in a history buffer for a longest matching vector data that matches the normalized vector data; and means, performed by the computer, for encoding the longest matching vector data found in the history buffer, when the means for searching finds the longest matching vector data, by assigning a substitution code.
Claim 12
Dependent Claim
75 words
The apparatus of claim 9, wherein the means for searching in the history buffer further comprises: means for storing a hashing function of the history buffer vector data in a hash table, the hash table having a plurality of entries, the entries having a pointer to a location in the history buffer; and means for searching in the hash table entries by comparing the hash table entries to a hashing function of the vector data.
Claim 13
Dependent Claim
26 words
The apparatus of claim 10, further comprising means for comparing the vector data to the history buffer vector data pointed to by the hash table entry.
Claim 14
Dependent Claim
14 words
The apparatus of claim 9, wherein the substitution code further comprises a denormalization function.
Claim 15
Dependent Claim
36 words
The apparatus of claim 9, wherein the substitution code further comprises an operation code, a length of the matching vector data, and a pointer indicating the position within the history buffer of the matching vector data.
Claim 16
Dependent Claim
21 words
The apparatus of claim 9, wherein the encoding means further comprises means for storing the substitute code in the history buffer.
Claim 17
Dependent Claim
21 words
The apparatus of claim 9, wherein the normalizing means further comprises means for scaling the vector data to a unit square.
Claim 18
Dependent Claim
22 words
The apparatus of claim 9, wherein the history buffer has a plurality of entries for storing vector data and coded vector data.
Claim 19
Dependent Claim
155 words
A program storage device, readable by a computer having a memory and coupled to a data storage device, tangibly embodying one or more programs of instructions executable by the computer to perform method steps for compressing vector data stored in the data storage device, the method comprising the steps of: normalizing the vector data, wherein the vector data is comprised of one or more primitives representing one or more graphics object and one or more coordinate values indicating locations for each of the graphics object, and the normalizing step comprises the steps of translating the locations of the graphics objects to an origin and scaling the coordinate values of the graphic objects; searching a history buffer for a longest matching vector data that matches the normalized vector data; and when the searching step finds the longest matching vector data, encoding the longest matching vector data found in the history buffer by assigning a substitution code.
Claim 20
Dependent Claim
155 words
A program storage device, readable by a computer having a memory and coupled to a data storage device, tangibly embodying one or more programs of instructions executable by the computer to perform method steps for compressing vector data stored in the data storage device, the method comprising the steps of: normalizing the vector data, wherein the vector data is comprised of one or more primitives representing one or more graphics object and one or more coordinate values indicating locations for each of the graphics object, and the normalizing step comprises the steps of translating the locations of the graphics objects to an origin and scaling the coordinate values of the graphic objects; searching a history buffer for a longest matching vector data that matches the normalized vector data; and when the searching step finds the longest matching vector data, encoding the longest matching vector data found in the history buffer by assigning a substitution code.
Claim 21
Dependent Claim
76 words
The program storage device of claim 17, wherein the step of searching in the history buffer further comprises the steps of: storing a hashing function of the history buffer vector data in a hash table, the hash table having a plurality of entries, the entries having a pointer to a location in the history buffer; and searching in the hash table entries by comparing the hash table entries to a hashing function of the vector data.
Claim 22
Dependent Claim
29 words
The program storage device of claim 18, further comprising the step of comparing the vector data to the history buffer vector data pointed to by the hash table entry.
Claim 23
Dependent Claim
16 words
The program storage device of claim 17, wherein the substitution code further comprises a denormalization function.
Claim 24
Dependent Claim
38 words
The program storage device of claim 17, wherein the substitution code further comprises an operation code, a length of the matching vector data, and a pointer indicating the position within the history buffer of the matching vector data.
Claim 25
Dependent Claim
38 words
The program storage device of claim 17, wherein the substitution code further comprises an operation code, a length of the matching vector data, and a pointer indicating the position within the history buffer of the matching vector data.
Claim 26
Dependent Claim
25 words
The program storage device of claim 17, wherein the step of encoding further comprises the step of storing the substitute code in the history buffer.
Claim 27
Dependent Claim
24 words
The program storage device of claim 17, wherein the normalizing step further comprises the step of scaling the vector data to a unit square.
Claim 28
Dependent Claim
24 words
The program storage device of claim 17, wherein the history buffer has a plurality of entries for storing vector data and coded vector data.
References Cited (Backward Citations)
US4464650A
Cited
US4814746A
Cited
US4558302A
Cited
US4558302B1
Cited
US4701745A
Cited
US5144679A
Cited
US5300931A
Cited
US4906991A
Cited
US5003307A
Cited
US5016009A
Cited
US5126739A
Cited
US4979039A
Cited
US5247357A
Cited
US5124791A
Cited
US5450132A
Cited
US4955066A
Cited
US5001478A
Cited
US5049881A
Cited
US5051745A
Cited
US5140321A
Cited
US5281967A
Cited
US5155484A
Cited
US5229768A
Cited
US5371499A
Cited
US5406278A
Cited
US5406279A
Cited
US5577135A
Cited
US5524182A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-06-01 | 2001-12-01 | 2002-06-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-06-01 | 2005-12-01 | 2006-06-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-06-01 | 2009-12-01 | 2010-06-02 | $7700.00 | Window Closed / Lapsed |