Patent US5659631A successfully refreshed from Google Patents.
US5659631A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data compression for indexed color image data
Assignee: Ricoh Co Ltd
•
Filing: 1995-02-21
•
Granted: 1997-08-19
•
Expires: 2015-02-21
Abstract
Abstract A data compression system separates input data into color planes prior to compression. If needed for legacy game consoles, compression is performed by a game cartridge transparent to the console. To minimize the number of passes required of a coder/decoder, color planes are ordered by density and the densest color plane is coded first. After the first color plane is coded, other color planes are coded, but pixels which are known to have colors from previously coded color planes are not coded. The last color plane is not coded, but is deduced from all the other color planes. Alternatively, pixel color values are represented by vectors with components thereof separately coded by subcolor planes. Also, each color plane can be coded until a threshold number of pixels are coded, and the remaining pixels coded by bit plane. The image data could be coded using pixel position information as context.
Inventors
- 👤 Michael J. Gormish
- 👤 Edward L. Schwartz
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 21:47
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H04; H04N; H04N11/00; H04N11/04; H04N11/042; H04N1/00; H04N1/46; H04N1/64; H04N1/644; H04N19/00; H04N19/50; H04N19/593
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
153 words
A method of compressing an array of pixel values, wherein the array collectively forms an image and each pixel is characterized by a color value and a location within the image, the method comprising the steps of: separating pixels of the image into color planes, wherein a color plane is a two-dimensional array of binary values indicating whether a color value for a pixel is a color value corresponding to a color value for that color plane; coding a first color plane; identifying a set of remaining pixels, the set of the remaining pixels being those pixels coded in the step of coding the first color plane; coding those pixels of the set of remaining pixels which are in a second color plane which are not found in the first color plane; and repetitively coding, for subsequent color plane, pixels which are not of a color corresponding to a previously coded color plane.
Claim 2
Independent Claim
153 words
A method of compressing an array of pixel values, wherein the array collectively forms an image and each pixel is characterized by a color value and a location within the image, the method comprising the steps of: separating pixels of the image into color planes, wherein a color plane is a two-dimensional array of binary values indicating whether a color value for a pixel is a color value corresponding to a color value for that color plane; coding a first color plane; identifying a set of remaining pixels, the set of the remaining pixels being those pixels coded in the step of coding the first color plane; coding those pixels of the set of remaining pixels which are in a second color plane which are not found in the first color plane; and repetitively coding, for subsequent color plane, pixels which are not of a color corresponding to a previously coded color plane.
Claim 3
Dependent Claim
59 words
The method of claim 1, further comprising a step of ordering the color planes by frequency of color, a color plane with a color which is a most frequent color in the image being a first color and a color plane corresponding to the first color being the first color plane, thereby coding the color planes in frequency order.
Claim 4
Dependent Claim
22 words
The method of claim 1, where a color plane corresponding to color which is not present in the image is not coded.
Claim 5
Dependent Claim
15 words
The method of claim 1, wherein the steps of coding are steps of entropy coding.
Claim 6
Dependent Claim
21 words
The method of claim 4, wherein the steps of entropy coding are steps of coding using a high-speed binary entropy coder.
Claim 7
Dependent Claim
18 words
The method of claim 4, wherein the steps of entropy coding are steps of coding using a Q-coder.
Claim 8
Dependent Claim
18 words
The method of claim 4, wherein the steps of entropy coding are steps of coding using a B-coder.
Claim 9
Dependent Claim
26 words
The method of claim 4, wherein entropy coding is performed with a context including at least a value of one pixel near the pixel being coded.
Claim 10
Dependent Claim
26 words
The method of claim 4, wherein entropy coding is performed with a context including at least a value of a position of the pixel being coded.
Claim 11
Dependent Claim
37 words
The method of claim 4, wherein entropy coding further comprises a step of determining a context for a current pixel and the context is an indication of which neighboring pixels are in the color plane being coded.
Claim 12
Independent Claim
96 words
A method of decompressing an array of pixel values from a compressed data set comprising the steps of: identifying, from a priori information and previously decompressed pixel values, a current color plane for a current pixel being decoded; determining, from previously decoded pixels in previously decoded color planes, a position within the array of the current pixel being decoded, wherein the position of the current pixel is assumed to be a position other than a position of the previously decoded pixels in the previously decoded color planes; and repetitively decoding subsequent pixels in subsequent color planes.
Claim 13
Independent Claim
96 words
A method of decompressing an array of pixel values from a compressed data set comprising the steps of: identifying, from a priori information and previously decompressed pixel values, a current color plane for a current pixel being decoded; determining, from previously decoded pixels in previously decoded color planes, a position within the array of the current pixel being decoded, wherein the position of the current pixel is assumed to be a position other than a position of the previously decoded pixels in the previously decoded color planes; and repetitively decoding subsequent pixels in subsequent color planes.
Claim 14
Dependent Claim
42 words
The method of claim 11 wherein the step of decoding a pixel is done according to an adaptive entropy code, where the adaptive entropy code is determined by reference to a context for the determined location for the current pixel being decoded.
Claim 15
Dependent Claim
33 words
The method of claim 11, wherein a final color plane is not decoded and pixel locations which do not contain a pixel value are assigned a pixel value for the last color plane.
Claim 16
Independent Claim
174 words
A method of compressing an array of element values, wherein the array of element values collectively forms a data set and each element is characterized by an element value and a location within the array, the method comprising the steps of: separating the elements into sparse arrays, wherein a sparse array contains the elements having element values equal to an array value associated with that sparse array, wherein a sparse array is an array of binary values with a one-to-one correspondence to the array of elements; coding a first sparse array; identifying a set of uncoded element locations corresponding to positions in the first sparse array which reference elements with element values other than the array value for the first sparse array; coding a portion of a second sparse array, the portion coded being the bits in element locations corresponding to the element locations in the set of uncoded element locations; and repetitively coding, for subsequent sparse arrays, elements in element locations which are not element locations for elements in previously coded sparse arrays.
Claim 17
Independent Claim
174 words
A method of compressing an array of element values, wherein the array of element values collectively forms a data set and each element is characterized by an element value and a location within the array, the method comprising the steps of: separating the elements into sparse arrays, wherein a sparse array contains the elements having element values equal to an array value associated with that sparse array, wherein a sparse array is an array of binary values with a one-to-one correspondence to the array of elements; coding a first sparse array; identifying a set of uncoded element locations corresponding to positions in the first sparse array which reference elements with element values other than the array value for the first sparse array; coding a portion of a second sparse array, the portion coded being the bits in element locations corresponding to the element locations in the set of uncoded element locations; and repetitively coding, for subsequent sparse arrays, elements in element locations which are not element locations for elements in previously coded sparse arrays.
Claim 18
Independent Claim
245 words
A method of decompressing an element array from a compressed data file, wherein the element array collectively forms a data set with elements each characterized by an element value and a location within the element array, the method comprising the steps of: identifying a first range of the compressed data file, wherein the first range represents compressed information content of a first sparse array and the first sparse array is an array of binary values indicating which elements of the element array have element values equal to a first sparse array element value; decoding the first sparse array from the first range; identifying a second range of the compressed data file, wherein the second range represents compressed information content of a second sparse array of binary values each indicating whether an element of the element array has an element value equal to a second sparse array element value or has an element value different from the first sparse array element value and the second sparse array element value, and wherein the second range includes less than all element value information for elements found in the first sparse army; decoding the second sparse array from the second range; and repeating the steps of identifying a range and decoding a sparse array until a threshold number of sparse arrays are decoded, wherein each subsequent sparse array identifies, for each element not yet decoded, whether the element has an element value equal to the sparse array element value.
Claim 19
Independent Claim
245 words
A method of decompressing an element array from a compressed data file, wherein the element array collectively forms a data set with elements each characterized by an element value and a location within the element array, the method comprising the steps of: identifying a first range of the compressed data file, wherein the first range represents compressed information content of a first sparse array and the first sparse array is an array of binary values indicating which elements of the element array have element values equal to a first sparse array element value; decoding the first sparse array from the first range; identifying a second range of the compressed data file, wherein the second range represents compressed information content of a second sparse array of binary values each indicating whether an element of the element array has an element value equal to a second sparse array element value or has an element value different from the first sparse array element value and the second sparse array element value, and wherein the second range includes less than all element value information for elements found in the first sparse army; decoding the second sparse array from the second range; and repeating the steps of identifying a range and decoding a sparse array until a threshold number of sparse arrays are decoded, wherein each subsequent sparse array identifies, for each element not yet decoded, whether the element has an element value equal to the sparse array element value.
Claim 20
Dependent Claim
35 words
The method of claim 15, further comprising the steps of decoding, using bit plane decoding, the element values for sparse arrays which have not been decoded when the threshold number of sparse arrays are decoded.
Claim 21
Dependent Claim
47 words
The method of claim 15, wherein the threshold number of sparse arrays is one less than the number of different element values, the method further comprising the step of assigning a default element value to elements not decoded in the threshold number of decodings of sparse arrays.
Claim 22
Dependent Claim
44 words
The method of claim 15, wherein each element is characterized by the element value decoded in the decoding steps and the method further comprises steps of decoding subvalues for each element using bit plane decoding after the threshold number of sparse arrays are decoded.
Claim 23
Dependent Claim
289 words
An image compressor for compressing an image to form a compressed data set, comprising: an image storage memory for storing pixel values collectively representing the image to be compressed, wherein each pixel of the image is characterized by a pixel value and a pixel location within the image; a pixel value reader, coupled to the image storage memory, which reads pixel values from the image storage memory and out-puts binary representations of pixels in color plane order, wherein a binary representation of a pixel in a current color plane indicates whether or not the pixel is in the current color plane, a pixel being in a color plane if and only if its pixel value is in a set of pixel values associated with the color plane; a color plane coder, coupled to the pixel value reader, for coding yet uncoded pixels in the current color plane, the color plane coder comprising: a context modeller which identifies, from previously coded pixels drawn from at least one of the current color plane and previously coded color planes, a context for a current pixel in a current color plane, wherein the context modeller includes a first output indicating a result of a comparison of the current pixel's pixel value and the color of the current color plane and a second output indicating the context for the current pixel; and a binary entropy encoder coupled to the context modeller, which encodes the current pixel into a bit stream output by the binary entropy encoder based on the result and the context output by the context modeller; and a bit stream collection means, coupled to the binary entropy encoder, for collecting the output of the binary entropy encoder into the compressed data set.
Claim 24
Dependent Claim
289 words
An image compressor for compressing an image to form a compressed data set, comprising: an image storage memory for storing pixel values collectively representing the image to be compressed, wherein each pixel of the image is characterized by a pixel value and a pixel location within the image; a pixel value reader, coupled to the image storage memory, which reads pixel values from the image storage memory and out-puts binary representations of pixels in color plane order, wherein a binary representation of a pixel in a current color plane indicates whether or not the pixel is in the current color plane, a pixel being in a color plane if and only if its pixel value is in a set of pixel values associated with the color plane; a color plane coder, coupled to the pixel value reader, for coding yet uncoded pixels in the current color plane, the color plane coder comprising: a context modeller which identifies, from previously coded pixels drawn from at least one of the current color plane and previously coded color planes, a context for a current pixel in a current color plane, wherein the context modeller includes a first output indicating a result of a comparison of the current pixel's pixel value and the color of the current color plane and a second output indicating the context for the current pixel; and a binary entropy encoder coupled to the context modeller, which encodes the current pixel into a bit stream output by the binary entropy encoder based on the result and the context output by the context modeller; and a bit stream collection means, coupled to the binary entropy encoder, for collecting the output of the binary entropy encoder into the compressed data set.
Claim 25
Dependent Claim
31 words
The image compressor of claim 19, wherein each set of pixel values includes only one pixel value, thereby resulting in each color plane containing pixels all having a common pixel value.
Claim 26
Dependent Claim
55 words
The image compressor of claim 19, wherein at least one set of pixel values comprises a plurality of pixel values, the image compressor further comprising a bit plane coder for coding information indicating which of the plurality of pixel values is the pixel value for pixels in color planes having sets of plural pixel values.
Claim 27
Dependent Claim
30 words
The image compressor of claim 19, wherein the context modeller provides a context based on whether or not neighboring pixels around the current pixel are in the current color plane.
Claim 28
Dependent Claim
188 words
An image decompressor for decompressing an image from a compressed data set to form an uncompressed image, wherein each pixel of the uncompressed image is characterized by a pixel value and a pixel location within the uncompressed image, the image decompressor comprising: a compressed data set storage memory for storing the compressed data set; a color plane decoder, for decoding pixels from the compressed data set in color plane order, the color plane decoder comprising: a context modeller which identifies, from previously decoded pixels drawn from at least one of a current color plane and previously decoded color planes, a context for a current pixel in a current color plane being decoded, the context indicating the color planes for pixels neighboring the current pixel; a binary entropy decoder, coupled to the context modeller and the compressed data set, which decodes the current pixel based on the context for the current pixel identified by the context modeller; and a color plane accumulator which accumulates pixels decoded by color plane by the binary entropy decoder into an image storage memory, thereby forming the uncompressed image in the image storage memory.
Claim 29
Dependent Claim
188 words
An image decompressor for decompressing an image from a compressed data set to form an uncompressed image, wherein each pixel of the uncompressed image is characterized by a pixel value and a pixel location within the uncompressed image, the image decompressor comprising: a compressed data set storage memory for storing the compressed data set; a color plane decoder, for decoding pixels from the compressed data set in color plane order, the color plane decoder comprising: a context modeller which identifies, from previously decoded pixels drawn from at least one of a current color plane and previously decoded color planes, a context for a current pixel in a current color plane being decoded, the context indicating the color planes for pixels neighboring the current pixel; a binary entropy decoder, coupled to the context modeller and the compressed data set, which decodes the current pixel based on the context for the current pixel identified by the context modeller; and a color plane accumulator which accumulates pixels decoded by color plane by the binary entropy decoder into an image storage memory, thereby forming the uncompressed image in the image storage memory.
Claim 30
Dependent Claim
32 words
The image decompressor of claim 23, wherein the context for the current pixel is a context indicating whether or not the pixels neighboring the current pixel are in the current color plane.
Claim 31
Dependent Claim
22 words
The method of claim 1, where a color plane corresponding to one color which is present in the image is not coded.
Claim 32
Dependent Claim
22 words
The method of claim 3, where a color plane corresponding to one color which is present in the image is not coded.
References Cited (Backward Citations)
US4868773A
Cited
US4943937A
Cited
DE3804175A1
Cited
US5463702A
Cited
US5381145A
Cited
US5471207A
Cited
US5471320A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-08-18 | 2001-02-17 | 2001-08-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-08-18 | 2005-02-17 | 2005-08-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-08-18 | 2009-02-17 | 2009-08-19 | $7700.00 | Window Closed / Lapsed |