US5450130A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for cell based image data compression
Assignee: Autodesk Inc
•
Filing: 1994-03-30
•
Granted: 1995-09-12
•
Expires: 2014-03-30
Abstract
Abstract A method and system for compressing color video or other image data for transmission over a low cost, low bandwidth bus (or other transmission link). Preferred embodiments implement lossless compression and include a frame buffer for storing data compressed in accordance with the invention, and circuitry for decompressing and transforming compressed data read from the frame buffer. The image data are typically organized as a sequence of frames, each comprising a sequence of pixels. Data compressed in accordance with the invention are stored in cells in memory, with each cell storing the same number of pixels. The inventive method is denoted as "cell based image compression" ("CBC"). Advantages of CBC include increasing available data transmission bandwidth and lowering required system power as a result of minimizing transfer of redundant color information to and from memory as well as fast random single pixel reads and writes. Some embodiments interface with a fast, narrow, single ported frame buffer, such as a RAMBUS or SDRAM memory, and compress image data not to minimize memory requirements, but to minimize bus bandwidth requirements for transferring data to and from memory. With this type of memory, all frame buffer accesses, such as host access, display refresh, and BLIT (Block Image Transfer) operations, compete on the same bus for frame buffer memory bandwidth. CBC allows frame buffers of acceptable BLIT performance whose available bandwidth is no more than slightly larger than the worst case bandwidth required to support display refresh (the worst case being no image compression). The amount of additional bandwidth available for BLIT operations and host access is variable, and depends on the compression rate of the data being transferred.
Inventors
- 👤 Peter F. Foley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 20:58
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/42; H04N19/423; H04N19/426; H04N19/428; H04N19/60; H04N19/61
Claims Analysis
Total Claims: 55
Claim 1
Independent Claim
148 words
A method for compressing image data, wherein the image data comprise pixels of at least one frame of pixels, the method including the steps of: (a) receiving a set of N of the pixels, where N is an integer greater than one, and selecting one of the pixels in the set as an uncompressed anchor pixel; (b) generating compressed pixels by compressing N-1 others of the pixels in the set in accordance with one or more selected ones of at least two compression schemes, so as to reduce transmission bandwidth requirements for the compressed pixels; and (c) generating marked compressed pixels by marking each of the compressed pixels with a tag identifying the one of the compression schemes in accordance with which said each of the compressed pixels is compressed, wherein the anchor pixel and the marked compressed pixels together comprise a first group of N compressed pixels.
Claim 2
Independent Claim
148 words
A method for compressing image data, wherein the image data comprise pixels of at least one frame of pixels, the method including the steps of: (a) receiving a set of N of the pixels, where N is an integer greater than one, and selecting one of the pixels in the set as an uncompressed anchor pixel; (b) generating compressed pixels by compressing N-1 others of the pixels in the set in accordance with one or more selected ones of at least two compression schemes, so as to reduce transmission bandwidth requirements for the compressed pixels; and (c) generating marked compressed pixels by marking each of the compressed pixels with a tag identifying the one of the compression schemes in accordance with which said each of the compressed pixels is compressed, wherein the anchor pixel and the marked compressed pixels together comprise a first group of N compressed pixels.
Claim 3
Dependent Claim
12 words
The method of claim 1, wherein the image data are video data.
Claim 4
Dependent Claim
22 words
The method of claim 1, wherein the image data are color video data, and each of the pixels includes three color components.
Claim 5
Dependent Claim
24 words
The method of claim 1, wherein the anchor pixel consists of twenty-four bits, and each of the compression schemes is a lossless compression scheme.
Claim 6
Dependent Claim
20 words
The method of claim 1, wherein step (a) includes the step of marking the anchor pixel with a first tag.
Claim 7
Dependent Claim
41 words
The method of claim 1, wherein the compressed pixels include a first compressed pixel compressed in accordance with a first one of the compression schemes, and a second compressed pixel compressed in accordance with a second one of the compression schemes.
Claim 8
Dependent Claim
90 words
The method of claim 1, wherein the compression schemes include: a full precision scheme in accordance with which no compression is performed, wherein each of the compressed pixels compressed in accordance with the full precision scheme is marked with said first tag; and an offset value compression scheme in accordance with which a compressed pixel's value is encoded as an offset value relative to the value of a reference pixel, where the reference pixel is the nearest preceding one of the compressed pixels that is marked with said first tag.
Claim 9
Dependent Claim
35 words
The method of claim 7, wherein the compression schemes also include: a run length pixel encoding scheme in accordance with which a number of compressed pixels having identical value to a preceding pixel is identified.
Claim 10
Dependent Claim
61 words
The method of claim 7, wherein the compression schemes also include: a second offset value compression scheme in accordance with which a compressed pixel's value is encoded as a limited range offset value relative to the value of a reference pixel, where the reference pixel is the nearest preceding one of the compressed pixels that is marked with said first tag.
Claim 11
Dependent Claim
85 words
The method of claim 9, wherein each of the pixels consists of P bits indicative of three different color components, each said offset value consists of Y bits of a first color component concatenated with Z bits of a second color component concatenated with Y bits of a third color component, and each said limited range offset value consists of Y' bits of the first color component concatenated with Z' bits of the second color component concatenated with Y' bits of the third color component.
Claim 12
Dependent Claim
11 words
The method of claim 10, wherein P=24, Y=4, Z=5, and Y'=Z'=2.
Claim 13
Dependent Claim
58 words
The method of claim 1, also including the step of: (d) repeating steps (a), (b), and (c) for a second set of N of the pixels to generate a second group of N compressed pixels, where none of the pixels in the second set was compressed or marked during a previous performance of steps (a), (b), and (c).
Claim 14
Dependent Claim
80 words
The method of claim 12, also including the step of: (e) storing the first group in a first cell of a memory, and storing the second group in a second cell of the memory, wherein each of the first cell and the second cell consists of M bits, where each of the set of N of the pixels and the second set of N of the pixels consists of P bits, where P is a number not greater than M.
Claim 15
Dependent Claim
31 words
The method of claim 13, wherein after step (e), each of the first cell and the second cell contains a sequence of bits beginning with bits of one said anchor pixel.
Claim 16
Dependent Claim
7 words
The method of claim 13, wherein M=P.
Claim 17
Dependent Claim
22 words
The method of claim 15, wherein each of the pixels consists of 24 bits, and M=24 R, where R is an integer.
Claim 18
Dependent Claim
15 words
The method of claim 13, wherein the memory is a fast, narrow, single ported memory.
Claim 19
Dependent Claim
58 words
The method of claim 17, wherein the step of storing the first group in the memory includes the step of transmitting said first group over a bus having a one pixel width, and the step of storing the second group the memory includes the step of transmitting said second group over said bus having a one pixel width.
Claim 20
Dependent Claim
58 words
The method of claim 17, wherein the step of storing the first group in the memory includes the step of transmitting said first group over a bus having a two pixel width, and the step of storing the second group the memory includes the step of transmitting said second group over said bus having a two pixel width.
Claim 21
Independent Claim
164 words
A system for processing image data, including: compression means for compressing a stream of pixels of the image data by selecting one of the pixels to be an uncompressed anchor pixel of a set of N of the pixels, where N is an integer greater than one, generating compressed pixels by compressing N-1 others of the pixels in accordance with one or more selected ones of at least two compression schemes, so as to reduce transmission bandwidth requirements for the compressed pixels, and generating marked compressed pixels by marking each of the compressed pixels with a tag identifying the one of the compression schemes in accordance with which said each of the compressed pixels is compressed, wherein the anchor pixel and the marked compressed pixels together comprise a group of N compressed pixels; and bus interface means for writing the group of N compressed pixels, in burst fashion, to a narrow bus of a type capable of interfacing with a narrow single ported memory.
Claim 22
Independent Claim
164 words
A system for processing image data, including: compression means for compressing a stream of pixels of the image data by selecting one of the pixels to be an uncompressed anchor pixel of a set of N of the pixels, where N is an integer greater than one, generating compressed pixels by compressing N-1 others of the pixels in accordance with one or more selected ones of at least two compression schemes, so as to reduce transmission bandwidth requirements for the compressed pixels, and generating marked compressed pixels by marking each of the compressed pixels with a tag identifying the one of the compression schemes in accordance with which said each of the compressed pixels is compressed, wherein the anchor pixel and the marked compressed pixels together comprise a group of N compressed pixels; and bus interface means for writing the group of N compressed pixels, in burst fashion, to a narrow bus of a type capable of interfacing with a narrow single ported memory.
Claim 23
Dependent Claim
20 words
The system of claim 20, wherein the compression means is programmed to mark the anchor pixel with a first tag.
Claim 24
Dependent Claim
28 words
The system of claim 20, wherein the means for writing includes: a write buffer memory connected for receiving said group of N compressed pixels from the compression means.
Claim 25
Dependent Claim
12 words
The system of claim 20, wherein the image data are video data.
Claim 26
Dependent Claim
22 words
The system of claim 20, wherein the image data are color video data, and each of the pixels includes three color components.
Claim 27
Dependent Claim
28 words
The system of claim 20, also including: a narrow single ported memory; and a narrow bus connected between the narrow single ported memory and the bus interface means.
Claim 28
Dependent Claim
26 words
The system of claim 20, also including: means for controlling early termination of a write of said group of N compressed pixels to the narrow bus.
Claim 29
Dependent Claim
57 words
The system of claim 20, also including: pixel buffer means for receiving a stream of compressed pixels of the image data from a bus; decompression means for receiving the compressed pixels from the pixel buffer means and decompressing said compressed pixels to generate said stream of pixels, and supplying said stream of pixels to the compression means.
Claim 30
Dependent Claim
35 words
The system of claim 27, also including: arithmetic logic means connected between the decompression means and the compression means for transforming said stream of pixels before supplying said stream of pixels to the compression means.
Claim 31
Dependent Claim
57 words
The system of claim 27, also including a display refresh means, said display refresh means including: scanline buffer means for receiving said stream of compressed pixels of the image data from the bus; and display refresh decompression means for receiving the compressed pixels from the scanline buffer means, and decompressing said compressed pixels to generate display pixels.
Claim 32
Dependent Claim
30 words
The system of claim 29, also including: display means for receiving the display pixels from the display refresh decompression means, and converting said display pixels to analog form for display.
Claim 33
Independent Claim
201 words
A system for processing image data, including: a frame buffer controller; a narrow single ported frame buffer memory; and a narrow bus connected between the frame buffer controller with the narrow single ported frame buffer memory, wherein the frame buffer controller includes: compression means for compressing pixels of the image data by selecting one of the pixels to be an uncompressed anchor pixel of a set of N of the pixels, where N is an integer greater than one, generating compressed pixels by compressing N-1 others of the pixels in accordance with one or more selected ones of at least two compression schemes, so as to reduce bandwidth requirements for transmitting the compressed pixels from the frame buffer controller over the narrow bus to the narrow single ported frame buffer memory, and generating marked compressed pixels by marking each of the compressed pixels with a tag identifying the one of the compression schemes in accordance with which said each of the compressed pixels is compressed, wherein the anchor pixel and the marked compressed pixels together comprise a group of N compressed pixels; and bus interface means for writing the group of N compressed pixels, in burst fashion, to the narrow bus.
Claim 34
Independent Claim
201 words
A system for processing image data, including: a frame buffer controller; a narrow single ported frame buffer memory; and a narrow bus connected between the frame buffer controller with the narrow single ported frame buffer memory, wherein the frame buffer controller includes: compression means for compressing pixels of the image data by selecting one of the pixels to be an uncompressed anchor pixel of a set of N of the pixels, where N is an integer greater than one, generating compressed pixels by compressing N-1 others of the pixels in accordance with one or more selected ones of at least two compression schemes, so as to reduce bandwidth requirements for transmitting the compressed pixels from the frame buffer controller over the narrow bus to the narrow single ported frame buffer memory, and generating marked compressed pixels by marking each of the compressed pixels with a tag identifying the one of the compression schemes in accordance with which said each of the compressed pixels is compressed, wherein the anchor pixel and the marked compressed pixels together comprise a group of N compressed pixels; and bus interface means for writing the group of N compressed pixels, in burst fashion, to the narrow bus.
Claim 35
Dependent Claim
20 words
The system of claim 31, wherein the compression means is programmed to mark the anchor pixel with a first tag.
Claim 36
Dependent Claim
25 words
The system of claim 31, also including: a system bus connected to the frame buffer controller; and a host processor connected along the system bus.
Claim 37
Dependent Claim
58 words
The system of claim 31, wherein the frame buffer controller also includes a display refresh means, said display refresh means including: buffer means for receiving compressed pixels of the image data from the narrow bus; and display refresh decompression means for receiving the compressed pixels from the buffer means and decompressing said compressed pixels to generate display pixels.
Claim 38
Dependent Claim
30 words
The system of claim 34, also including: display means for receiving the display pixels from the display refresh decompression means, and converting said display pixels to analog form for display.
Claim 39
Dependent Claim
41 words
The system of claim 31, wherein said compressed pixels include a first compressed pixel compressed in accordance with a first one of the compression schemes, and a second compressed pixel compressed in accordance with a second one of the compression schemes.
Claim 40
Dependent Claim
90 words
The system of claim 36, wherein the compression schemes include: a full precision scheme in accordance with which no compression is performed, wherein each of the compressed pixels compressed in accordance with the full precision scheme is marked with said first tag; and an offset value compression scheme in accordance with which a compressed pixel's value is encoded as an offset value relative to the value of a reference pixel, where the reference pixel is the nearest preceding one of the compressed pixels that is marked with said first tag.
Claim 41
Dependent Claim
35 words
The system of claim 37, wherein the compression schemes also include: a run length pixel encoding scheme in accordance with which a number of compressed pixels having identical value to a preceding pixel is identified.
Claim 42
Dependent Claim
61 words
The system of claim 37, wherein the compression schemes also include: a second offset value compression scheme in accordance with which a compressed pixel's value is encoded as a limited range offset value relative to the value of a reference pixel, where the reference pixel is the nearest preceding one of the compressed pixels that is marked with said first tag.
Claim 43
Dependent Claim
85 words
The system of claim 39, wherein each of the pixels consists of P bits indicative of three different color components, each said offset value consists of Y bits of a first color component concatenated with Z bits of a second color component concatenated with Y bits of a third color component, and each said limited range offset value consists of Y' bits of the first color component concatenated with Z' bits of the second color component concatenated with Y' bits of the third color component.
Claim 44
Dependent Claim
11 words
The system of claim 40, wherein P=24, Y=4, Z=5, and Y'=Z'=2.
Claim 45
Independent Claim
228 words
A method for compressing pixels of image data, including the steps of: (a) receiving a set of N of the pixels, where N is an integer greater than one, and selecting one of the pixels in the set as an uncompressed anchor pixel; (b) generating compressed pixels by compressing N-1 others of the pixels in the set in accordance with a compression scheme by which each of said N-1 others of the pixels is compressed by a selected one of at least two lossless compression methods, to reduce transmission bandwidth requirements for the compressed pixels; (c) generating marked compressed pixels by applying a marking scheme to mark each of the compressed pixels with a tag identifying which of the lossless compression methods was employed to compress said each of the compressed pixels, where the anchor pixel and the marked compressed pixels together comprise a first group of N compressed pixels and the first group consists of P bits; and (d) storing the first group in a first cell of a frame buffer memory, and storing a cell tag in a first location of a cache memory, where the first location corresponds to the first cell, the first cell has capacity to store M bits, where M is an integer not less than P, and the cell tag consists of least one tag bit and characterizes the first group.
Claim 46
Independent Claim
228 words
A method for compressing pixels of image data, including the steps of: (a) receiving a set of N of the pixels, where N is an integer greater than one, and selecting one of the pixels in the set as an uncompressed anchor pixel; (b) generating compressed pixels by compressing N-1 others of the pixels in the set in accordance with a compression scheme by which each of said N-1 others of the pixels is compressed by a selected one of at least two lossless compression methods, to reduce transmission bandwidth requirements for the compressed pixels; (c) generating marked compressed pixels by applying a marking scheme to mark each of the compressed pixels with a tag identifying which of the lossless compression methods was employed to compress said each of the compressed pixels, where the anchor pixel and the marked compressed pixels together comprise a first group of N compressed pixels and the first group consists of P bits; and (d) storing the first group in a first cell of a frame buffer memory, and storing a cell tag in a first location of a cache memory, where the first location corresponds to the first cell, the first cell has capacity to store M bits, where M is an integer not less than P, and the cell tag consists of least one tag bit and characterizes the first group.
Claim 47
Dependent Claim
22 words
The method of claim 42, wherein the image data are color video data, and each of the pixels includes three color components.
Claim 48
Dependent Claim
134 words
The method of claim 42, also including the steps of: (e) storing a second set of Q of the pixels in a second cell of the frame buffer memory, said second cell having capacity to store M bits, without having compressed the second set, but after determining that a marked and compressed version of the second set would consist of more than M bits if each pixel of the marked and compressed version of the second set were compressed in accordance with the compression scheme and marked in accordance with the marking scheme; and (f) storing a second cell tag in a second location of the cache memory, where the second location corresponds to the second cell, and where the second cell tag consists of least one tag bit and characterizes the second set.
Claim 49
Dependent Claim
27 words
The method of claim 44, wherein the second cell tag indicates a cell containing uncompressed pixels that have not been compressed in accordance with the compression scheme.
Claim 50
Dependent Claim
24 words
The method of claim 42, wherein each of the anchor pixel and each of the pixels in the second set consists of twenty-four bits.
Claim 51
Dependent Claim
9 words
The method of claim 46, wherein Q=16, and M=384.
Claim 52
Dependent Claim
49 words
The method of claim 47, wherein step (d) includes the step of transferring the first group to the frame buffer memory over a bus having sixteen-bit width, and step (e) includes the step of transferring the second set to the frame buffer memory over said bus having sixteen-bit width.
Claim 53
Independent Claim
256 words
A system for compressing pixels of image data, said system including: means for receiving a set of N of the pixels, where N is an integer greater than one; compression means for selecting one of the pixels in the set as an uncompressed anchor pixel, for generating compressed pixels by compressing N-1 others of the pixels in the set in accordance with a compression scheme by which each of said N-1 others of the pixels is compressed by a selected one of at least two lossless compression methods, to reduce transmission bandwidth requirements for the compressed pixels, and for generating marked compressed pixels by applying a marking scheme to mark each of the compressed pixels with a tag identifying which of the lossless compression methods was employed to compress said each of the compressed pixels, where the anchor pixel and the marked compressed pixels together comprise a first group of N compressed pixels and the first group consists of P bits; a frame buffer memory connected to the compression means; and a cache memory connected to the compression means, and wherein said compression means also includes: means for storing the first group in a first cell of the frame buffer memory, and storing a cell tag in a first location of the cache memory, where the first location corresponds to the first cell, the first cell has capacity to store M bits, where M is an integer not less than P, and the cell tag consists of least one tag bit and characterizes the first group.
Claim 54
Independent Claim
256 words
A system for compressing pixels of image data, said system including: means for receiving a set of N of the pixels, where N is an integer greater than one; compression means for selecting one of the pixels in the set as an uncompressed anchor pixel, for generating compressed pixels by compressing N-1 others of the pixels in the set in accordance with a compression scheme by which each of said N-1 others of the pixels is compressed by a selected one of at least two lossless compression methods, to reduce transmission bandwidth requirements for the compressed pixels, and for generating marked compressed pixels by applying a marking scheme to mark each of the compressed pixels with a tag identifying which of the lossless compression methods was employed to compress said each of the compressed pixels, where the anchor pixel and the marked compressed pixels together comprise a first group of N compressed pixels and the first group consists of P bits; a frame buffer memory connected to the compression means; and a cache memory connected to the compression means, and wherein said compression means also includes: means for storing the first group in a first cell of the frame buffer memory, and storing a cell tag in a first location of the cache memory, where the first location corresponds to the first cell, the first cell has capacity to store M bits, where M is an integer not less than P, and the cell tag consists of least one tag bit and characterizes the first group.
Claim 55
Dependent Claim
137 words
The system of claim 49, wherein the compression means also includes: means for storing a second set of Q of the pixels in a second cell of the frame buffer memory, said second cell having capacity to store M bits, without having compressed the second set, but after determining that a marked and compressed version of the second set would consist of more than M bits if each pixel of the marked and compressed version of the second set were compressed in accordance with the compression scheme and marked in accordance with the marking scheme; and means for storing a second cell tag in a second location of the cache memory, where the second location corresponds to the second cell, and where the second cell tag consists of least one tag bit and characterizes the second set.
References Cited (Backward Citations)
US4855825A
Cited
US4703350A
Cited
US4663660A
Cited
US4849810A
Cited
US5179651A
Cited
US5150209A
Cited
US5155594A
Cited
WO1992015986A1
Cited
US5164819A
Cited
US5237397A
Cited
US5319793A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-09-11 | 1999-03-13 | 1999-09-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-09-11 | 2003-03-13 | 2003-09-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-09-11 | 2007-03-13 | 2007-09-12 | $7700.00 | Window Closed / Lapsed |