Vector data compression

• US 5,760,716 A
• Filed: 08/21/1996
• Issued: 06/02/1998
• Est. Priority Date: 08/21/1996
• Status: Expired due to Term

• Current Assignee: Autodesk, Inc.
• Original Assignee: Autodesk, Inc.
• Inventors: Mathews, Brian P., Covey, Robert D.
• Primary Examiner(s): Gaffin, Jeffrey A.
• Assistant Examiner(s): KOST, JASON L
• Application Number:
  US08/701,042
• Time in Patent Office: 650 Days
• Field of Search: 341/50, 341/51, 341/106, 341/107, 341/65
• US Class Current: 341/50
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

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.

Claims

1. 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.

2. 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.

3. 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.

4. The method of claim 1, wherein the substitution code further comprises a denormalization function.

5. 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.

6. The method of claim 1, wherein the step of encoding further comprises the step of storing the substitution code in the history buffer.

7. The method of claim 1, wherein the normalizing step further comprises the step of scaling the vector data to a unit square.

8. The method of claim 1, wherein the history buffer has a plurality of entries for storing vector data and coded vector data.

9. 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.

10. 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.

11. 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.

12. The apparatus of claim 9, wherein the substitution code further comprises a denormalization function.

13. 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.

14. The apparatus of claim 9, wherein the encoding means further comprises means for storing the substitute code in the history buffer.

15. The apparatus of claim 9, wherein the normalizing means further comprises means for scaling the vector data to a unit square.

16. The apparatus of claim 9, wherein the history buffer has a plurality of entries for storing vector data and coded vector data.

17. 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.

18. 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.

19. 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.

20. The program storage device of claim 17, wherein the substitution code further comprises a denormalization function.

21. 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.

22. 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.

23. 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.

24. The program storage device of claim 17, wherein the normalizing step further comprises the step of scaling the vector data to a unit square.

25. The program storage device of claim 17, wherein the history buffer has a plurality of entries for storing vector data and coded vector data.