US5504591A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for compressing graphic images
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1994-04-25
•
Granted: 1996-04-02
•
Expires: 2014-04-25
Abstract
Abstract A system and method for compressing raster graphic or bit-map data reduces the storage requirements for the bit-map data. The system divides the bit-map data into one or more chaingons, which are a series of pixels that are contiguous in either the horizontal direction, the vertical direction, or diagonally. Each chaingon is defined by its starting location in the bit-map, and its length. Each chaingon is encoded separately using delta encoding with respect to the starting location of the chaingon. The delta encoding uses variable length data codes where the most common delta values are assigned the fewer data bits and the less common delta values are assigned more data bits. The delta encoded chaingons may be compressed to save additional storage space. The system may be readily used in any computer system where bit-map data files are stored or transmitted to a second computer. The invention is particularly useful in printers or facsimile machines where character fonts are transmitted along with text data. The character fonts may be processed using the present invention prior to transmission.
Inventors
- 👤 Rajeev Dujari
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 19:41
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 37
Claim 1
Independent Claim
227 words
A system for the compression of a bit-map data file representing an orthogonal array of pixels having a series of pixels arranged in a first dimension and a plurality of the series of pixels arranged in a second dimension, each of said pixels having first and second logic states, the system comprising: a data file storage area containing the bit-map data file in uncompressed form; a change vector generator coupled to said data file storage area for sequentially analyzing each of the plurality of series of pixels to determine locations in the first dimension at which the pixels in the series of pixels change from the first logic state to the second logic state and from the second logic state to the first logic state, said change vector generator creating a change vector data table for each of the plurality of series of pixels; a chaingon generator coupled to said change vector generator to analyze said change vector data tables to apportion the bit-map data file into a plurality of chaingon regions, each of said chaingon regions comprising adjacent pixels having the first logic state; an encoding analyzer to analyze each of said plurality of chaingon regions to encode the pixels in each of said chaingon regions and generate encoded data for each of said chaingon regions; and a data storage area for storing said encoded data.
Claim 2
Independent Claim
227 words
A system for the compression of a bit-map data file representing an orthogonal array of pixels having a series of pixels arranged in a first dimension and a plurality of the series of pixels arranged in a second dimension, each of said pixels having first and second logic states, the system comprising: a data file storage area containing the bit-map data file in uncompressed form; a change vector generator coupled to said data file storage area for sequentially analyzing each of the plurality of series of pixels to determine locations in the first dimension at which the pixels in the series of pixels change from the first logic state to the second logic state and from the second logic state to the first logic state, said change vector generator creating a change vector data table for each of the plurality of series of pixels; a chaingon generator coupled to said change vector generator to analyze said change vector data tables to apportion the bit-map data file into a plurality of chaingon regions, each of said chaingon regions comprising adjacent pixels having the first logic state; an encoding analyzer to analyze each of said plurality of chaingon regions to encode the pixels in each of said chaingon regions and generate encoded data for each of said chaingon regions; and a data storage area for storing said encoded data.
Claim 3
Dependent Claim
12 words
The system of claim 1 wherein said encoding analyzer uses delta coding.
Claim 4
Dependent Claim
18 words
The system of claim 1, further including a compressor receiving said encoded data and generating compressed encoded data.
Claim 5
Dependent Claim
16 words
The system of claim 3 wherein said compressor uses RLE compression to compress said encoded data.
Claim 6
Dependent Claim
16 words
The system of claim 3 wherein said compressor uses LZ compression to compress said encoded data.
Claim 7
Dependent Claim
16 words
The system of claim 3 wherein said compressor uses Huffman compression to compress said encoded data.
Claim 8
Dependent Claim
96 words
The system of claim 1 wherein said chaingon generator creates a chaingon list for each of said chaingon regions using said change vector tables, said chaingon generator analyzing said change vector tables for a first and second sequential ones of the plurality of series of pixels and assigning pixels from said first and second adjacent series of pixels to a first chaingon list if pixels in said first adjacent series of pixels have the first logic state and are adjacent to pixels in said second adjacent series of pixels that also have the first logic state.
Claim 9
Independent Claim
127 words
A system for the compression of a bit-map data file representing an orthogonal array of pixels having a series of pixels arranged in a first dimension and a plurality of the series of pixels arranged in a second dimension, each of said pixels having first and second logic states, the system comprising: a chaingon generator for analyzing the bit-map data file to apportion the bit-map data file into a plurality of chaingon regions, each of said chaingon regions comprising adjacent pixels having the first logic state; an encoding analyzer analyzing each of said plurality of chaingon regions and encoding the pixels in each of said chaingon regions to generate encoded data for each of said chaingon regions; and a data storage area for storing said encoded data.
Claim 10
Independent Claim
127 words
A system for the compression of a bit-map data file representing an orthogonal array of pixels having a series of pixels arranged in a first dimension and a plurality of the series of pixels arranged in a second dimension, each of said pixels having first and second logic states, the system comprising: a chaingon generator for analyzing the bit-map data file to apportion the bit-map data file into a plurality of chaingon regions, each of said chaingon regions comprising adjacent pixels having the first logic state; an encoding analyzer analyzing each of said plurality of chaingon regions and encoding the pixels in each of said chaingon regions to generate encoded data for each of said chaingon regions; and a data storage area for storing said encoded data.
Claim 11
Dependent Claim
12 words
The system of claim 8 wherein said encoding analyzer uses delta coding.
Claim 12
Dependent Claim
18 words
The system of claim 8, further including a compressor receiving said encoded data and generating compressed encoded data.
Claim 13
Dependent Claim
30 words
The system of claim 10 wherein said compressor compresses said encoded data using a predetermined compression format comprising at least one of a RLE compression, LZ compression, and Huffman compression.
Claim 14
Dependent Claim
91 words
The system of claim 8 wherein said chaingon generator creates a chaingon list for each of said chaingon regions, said chaingon generator analyzing the bit-map data file for a first and second sequential ones of the plurality of series of pixels and assigning pixels from said first and second adjacent series of pixels to a first chaingon list if pixels in said first adjacent series of pixels have the first logic state and are adjacent to pixels in said second adjacent series of pixels that also have the first logic state.
Claim 15
Independent Claim
187 words
A system for the generation of an encoded data file from a bit-map data file representing an orthogonal array of pixels having a series of pixels arranged in a first dimension and a plurality of the series of pixels arranged in a second dimension, each of said pixels having first and second logic states, the system comprising: a change vector generator to sequentially analyze each of the plurality of series of pixels in the bit-map data file to determine locations in the first dimension at which the pixels in the series of pixels change from the first logic state to the second logic state and from the second logic state to the first logic state, said change vector generator creating a change vector data table for each of the plurality of series of pixels; and a chaingon generator coupled to said change vector generator to analyze said change vector data tables to apportion the bit-map data file into a plurality of chaingon regions, each of said chaingon regions comprising adjacent pixels having the first logic state, whereby the bit-map data file is encoded into said chaingon regions.
Claim 16
Independent Claim
187 words
A system for the generation of an encoded data file from a bit-map data file representing an orthogonal array of pixels having a series of pixels arranged in a first dimension and a plurality of the series of pixels arranged in a second dimension, each of said pixels having first and second logic states, the system comprising: a change vector generator to sequentially analyze each of the plurality of series of pixels in the bit-map data file to determine locations in the first dimension at which the pixels in the series of pixels change from the first logic state to the second logic state and from the second logic state to the first logic state, said change vector generator creating a change vector data table for each of the plurality of series of pixels; and a chaingon generator coupled to said change vector generator to analyze said change vector data tables to apportion the bit-map data file into a plurality of chaingon regions, each of said chaingon regions comprising adjacent pixels having the first logic state, whereby the bit-map data file is encoded into said chaingon regions.
Claim 17
Dependent Claim
38 words
The system of claim 13, further including an encoding analyzer analyzing each of said plurality of chaingon regions and encoding the pixels in each of said chaingon regions to generate encoded data for each of said chaingon regions.
Claim 18
Dependent Claim
18 words
The system of claim 14, further including a compressor receiving said encoded data and generating compressed encoded data.
Claim 19
Dependent Claim
30 words
The system of claim 15 wherein said compressor compresses said encoded data using a predetermined compression format comprising at least one of a RLE compression, LZ compression, and Huffman compression.
Claim 20
Dependent Claim
38 words
The system of claim 13 wherein said chaingon generator generates first and second offset data values for each of said chaingon regions indicating a location of each of said chaingon regions in the first and second dimensions, respectively.
Claim 21
Dependent Claim
27 words
The system of claim 17 wherein said chaingon generator generates a length data value indicating a length of each of said chaingon regions in said second dimension.
Claim 22
Independent Claim
190 words
A method using a computer for compressing a bit-map data file representing an orthogonal array of pixels having a series of pixels arranged in a first dimension and a plurality of the series of pixels arranged in the second dimension, each of the pixels having first and second logic states, the method comprising the steps of: (a) sequentially analyzing each of the plurality of series of pixels to determine locations in the first dimension at which the pixels in the series of pixels change from the first logic state to the second logic state and from the second logic state to the first logic state; (b) storing the value of said locations for each of the series of pixels in the second dimension in a change vector table; (c) analyzing said change vector data table to apportion the bit-map data file into a plurality of chaingon regions, each of said chaingon regions comprising adjacent pixels having the first logic state; and (d) analyzing each of said plurality of chaingon regions and encoding the pixels in each of said chaingon regions to generate encoded data for each of said chaingon regions.
Claim 23
Independent Claim
190 words
A method using a computer for compressing a bit-map data file representing an orthogonal array of pixels having a series of pixels arranged in a first dimension and a plurality of the series of pixels arranged in the second dimension, each of the pixels having first and second logic states, the method comprising the steps of: (a) sequentially analyzing each of the plurality of series of pixels to determine locations in the first dimension at which the pixels in the series of pixels change from the first logic state to the second logic state and from the second logic state to the first logic state; (b) storing the value of said locations for each of the series of pixels in the second dimension in a change vector table; (c) analyzing said change vector data table to apportion the bit-map data file into a plurality of chaingon regions, each of said chaingon regions comprising adjacent pixels having the first logic state; and (d) analyzing each of said plurality of chaingon regions and encoding the pixels in each of said chaingon regions to generate encoded data for each of said chaingon regions.
Claim 24
Dependent Claim
19 words
The method of claim 19 wherein said step (d) of encoding each of said chaingon regions uses delta coding.
Claim 25
Dependent Claim
14 words
The method of claim 19, further including the step of compressing said encoded data.
Claim 26
Dependent Claim
33 words
The method of claim 21 wherein said step of compressing uses a predetermined compression format comprising at least one of a RLE compression, LZ compression, and Huffman compression to compress said encoded data.
Claim 27
Dependent Claim
89 words
The method of claim 19 wherein said step (c) of analyzing said change vector data table, further includes the steps of: analyzing said change vector table for first and second sequential ones of the plurality of series of pixels; and assigning pixels from said first and second adjacent series of pixels to a first chaingon list if pixels in said first adjacent series of pixels have the first logic state and are adjacent to pixels in said second adjacent series of pixels that also have the first logic state.
Claim 28
Independent Claim
114 words
A method using a computer for generating an encoded data file from a bit-map data file representing an orthogonal array of pixels having a series of pixels arranged in a first dimension and a plurality of the series of pixels arranged in a second dimension, each of the pixels having first and second logic states, the method comprising the steps of: apportioning the bit-map data file into a plurality of chaingon regions, each of said chaingon regions comprising adjacent pixels having the first logic state; and analyzing each of said plurality of chaingon regions and encoding the pixels in each of said chaingon regions to generate encoded data for each of said chaingon regions.
Claim 29
Independent Claim
114 words
A method using a computer for generating an encoded data file from a bit-map data file representing an orthogonal array of pixels having a series of pixels arranged in a first dimension and a plurality of the series of pixels arranged in a second dimension, each of the pixels having first and second logic states, the method comprising the steps of: apportioning the bit-map data file into a plurality of chaingon regions, each of said chaingon regions comprising adjacent pixels having the first logic state; and analyzing each of said plurality of chaingon regions and encoding the pixels in each of said chaingon regions to generate encoded data for each of said chaingon regions.
Claim 30
Dependent Claim
18 words
The method of claim 24 wherein said step of encoding each of said chaingon regions uses delta coding.
Claim 31
Dependent Claim
14 words
The method of claim 24, further including the step of compressing said encoded data.
Claim 32
Dependent Claim
33 words
The method of claim 26 wherein said step of compressing uses a predetermined compression format comprising at least one of a RLE compression, LZ compression, and Huffman compression to compress said encoded data.
Claim 33
Independent Claim
95 words
A method using a computer for generating an encoded data file from a bit-map data file representing an orthogonal array of pixels having a series of pixels arranged in a first dimension and a plurality of the series of pixels arranged in a second dimension, each of the pixels having first and second logic states, the method comprising the steps of: retrieving the bit-map data file from a storage location; and apportioning the bit-map data file into a plurality of chaingon regions, each of said chaingon regions comprising adjacent pixels having the first logic state.
Claim 34
Independent Claim
95 words
A method using a computer for generating an encoded data file from a bit-map data file representing an orthogonal array of pixels having a series of pixels arranged in a first dimension and a plurality of the series of pixels arranged in a second dimension, each of the pixels having first and second logic states, the method comprising the steps of: retrieving the bit-map data file from a storage location; and apportioning the bit-map data file into a plurality of chaingon regions, each of said chaingon regions comprising adjacent pixels having the first logic state.
Claim 35
Dependent Claim
38 words
The method of claim 28, further including the step of analyzing each of said plurality of chaingon regions and encoding the pixels in each of said chaingon regions to generate encoded data for each of said chaingon regions.
Claim 36
Dependent Claim
14 words
The method of claim 29, further including the step of compressing said encoded data.
Claim 37
Dependent Claim
33 words
The method of claim 30 wherein said step of compressing uses a predetermined compression format comprising at least one of a RLE compression, LZ compression, and Huffman compression to compress said encoded data.
References Cited (Backward Citations)
US4053930A
Cited
US4097903A
Cited
US4470073A
Cited
US4539587A
Cited
US4701803A
Cited
US4783828A
Cited
US4982293A
Cited
US5067023A
Cited
US5305111A
Cited
US5414526A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-04-02 | 1999-10-02 | 2000-04-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-04-02 | 2003-10-02 | 2004-04-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-04-02 | 2007-10-02 | 2008-04-02 | $7700.00 | Window Closed / Lapsed |