EP1075146A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method and apparatus for compressing and storing image data
Assignee: ATI Technologies ULC
•
Filing: 2000-07-06
•
Granted: —
•
Expires: 2020-07-06
Abstract
Abstract A method and apparatus for compressing image data for storage in a memory device is presented. This is accomplished by separating the image data into a plurality of pixel sets where each pixel set is of a predetermined pixel set size. A discrete cosine transform is then performed on each of the pixel sets to produce a plurality of transform coefficients. These transform coefficients are then compressed to produce a compressed data set. Compressing the transform coefficients preferably includes determining a coefficient set that includes a portion of the transform coefficients that reasonably approximate the pixel set. These coefficients are then mapped to known ranges such that a limited number of bits can encode values throughout these predetermined ranges. The mapped coefficients resulting from the mapping step are then manipulated to fit within a limited number of bits assigned to each coefficient. The limited number of bits is determined partially based on the coefficient set to be compressed. The manipulation of these mapped coefficients is preferably accomplished by shifting, rounding, and truncating the mapped coefficients. The coefficients resulting from these operations are then packed along with coefficient identifying information to form the compressed data set.
Inventors
- 👤 Edward G. Callway
- 👤 Oscar Y.C. Chiu
- 👤 Paul Chow
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-09 15:01
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/10; H04N19/169; H04N19/182; H04N19/102; H04N19/115; H04N19/134; H04N19/146; H04N19/149; H04N19/152; H04N19/17; H04N19/176; H04N19/18; H04N19/189; H04N19/196; H04N19/46; H04N19/463; H04N19/60; H04N19/90; H04N19/91
Claims Analysis
Total Claims: 51
Claim 1
Independent Claim
94 words
A method for compressing image data comprising: separating the image data into a plurality of pixel sets, wherein each
pixel set is a predetermined pixel set size; and for each pixel set of the plurality of pixel sets: performing a discrete cosine transformation of the pixel set to produce
a plurality of transform coefficients; and compressing the transform coefficients for the pixel set to produce a
compressed data set, wherein the compressed data set is a predetermined
compressed data set size, wherein the compressed data set size is less than
the pixel set size.
Claim 2
Dependent Claim
54 words
The method of Claim 1, wherein compressing further comprises: determining a coefficient set, wherein the coefficient set indicates
which of the transform coefficients are represented in the compressed data
set; compressing values corresponding to coefficients included in the
coefficient set to produce compressed coefficients; and combining the compressed coefficients to produce the compressed set.
Claim 3
Dependent Claim
37 words
The method of Claim 2, wherein combining further comprises
combining the compressed coefficients with a compressed coefficient
identifier to produce the compressed set, wherein the compressed coefficient
identifier identifies the transform coefficients represented in the compressed
set.
Claim 4
Dependent Claim
49 words
The method of Claim 3, wherein the compressed coefficient identifier is
an R-bit identifier, wherein R is a number, wherein the R-bit identifier identifies
a highest order coefficient in a 2R range of coefficients, wherein the highest
order coefficient and lower order coefficients are included in the coefficient
set.
Claim 5
Independent Claim
153 words
The method of any one of Claims 2 to 4, wherein compressing values
further comprises, for each coefficient to be included in the compressed set: mapping a value of the coefficient to a predetermined range for the
coefficient to produce a mapped value, wherein when a bit width of a
compressed coefficient corresponding to the coefficient is equal to a bit width
of the mapped value for the coefficient, the mapped value is the compressed
coefficient for the coefficient; and when the bit width of the compressed coefficient corresponding to the
coefficient is less than the bit width of the mapped value for the coefficient,
discarding a discard quantity of low order bits of the mapped value to produce
the compressed coefficient for the coefficient, wherein the discard quantity is
equal to a difference between the bit width of the mapped value for the
coefficient and the bit width for the compressed coefficient.
Claim 6
Dependent Claim
40 words
The method of Claim 5, wherein mapping to a predetermined range
further comprises mapping to a predetermined range that corresponds to a
power of two such that a set of range bits can be used to represent the
mapped value.
Claim 7
Dependent Claim
31 words
The method of Claim 5 or Claim 6, wherein mapping further comprises
multiplying the value of the coefficient by a mapping multiplier to produce a
mapped value within the predetermined range.
Claim 8
Independent Claim
30 words
The method of any one of Claims 5 to 7, wherein mapping further
comprises utilizing a look up function to produce the mapped value from the
value of the coefficient.
Claim 9
Independent Claim
32 words
The method of any one of Claims 5 to 7, wherein mapping further
comprises performing a compand operation on the value of the coefficient to
produce the mapped value for the coefficient.
Claim 10
Independent Claim
57 words
The method of any one of Claims 5 to 9, wherein discarding low order
bits of the mapped value further comprises: shifting the mapped value such that lower order bits are shifted into
higher order bit locations to produce a shifted mapped value; and discarding the discard quantity of low order bits of the shifted mapped
value.
Claim 11
Dependent Claim
38 words
The method of Claim 10 further comprising determining the discard
quantity for each compressed coefficient from a selected table, wherein the
selected table is selected from a plurality of tables corresponding to a plurality
of potential coefficient sets.
Claim 12
Dependent Claim
40 words
The method of Claim 3 or any claim dependent thereon, wherein
determining the coefficient set further comprises: comparing values of the transform coefficients with threshold values;
and including in the coefficient set transform coefficients whose values
exceed corresponding threshold values.
Claim 13
Dependent Claim
61 words
The method of Claim 12, wherein comparing values of the transform
coefficients further comprises: comparing values of a predetermined portion of the transform
coefficients with the threshold values; including a highest order coefficient that exceeds a corresponding
threshold value in the coefficient set; and including coefficients of a lower order as compared to the highest order
coefficient in the coefficient set.
Claim 14
Independent Claim
135 words
A method for storing and retrieving video data, comprising: receiving uncompressed video data for storage; arranging the uncompressed video data in sets of pixels of a
predetermined size; performing a discrete time transform of the sets to produce coefficients
for each of the sets of pixels; compressing the coefficients to produce compressed data; storing the compressed data in a memory; retrieving at least a portion of the compressed data from the memory; decompressing the at least a portion of the compressed data to
produce at least a portion of the coefficients; and performing an inverse discrete time transform on the at least a portion
of the coefficients to produce at least a portion of the sets, wherein the at least
a portion of the sets constitutes at least a portion of the uncompressed video
data.
Claim 15
Dependent Claim
49 words
The method of Claim 14, wherein compressing the coefficients further
comprises: selecting a subset of the coefficients for compressing based on values
of the coefficients; determining bit widths for each coefficient included in the subset; and adjusting the coefficients included in the subset to fit within the bit
widths.
Claim 16
Dependent Claim
24 words
The method of Claim 15, wherein adjusting the coefficients further
comprises mapping values of the coefficients to a predetermined range
corresponding to each coefficient.
Claim 17
Independent Claim
17 words
The method of any one of the preceding claims, wherein the image
data is MPEG video data.
Claim 18
Independent Claim
34 words
The method of any one of the preceding claims, wherein separating
further comprises separating the image data into a plurality of 8-by-1 pixel
sets, wherein each 8-by-1 pixel set includes eight consecutive horizontal
pixels.
Claim 19
Independent Claim
24 words
The method of any one of the preceding claims, wherein the pixel set
size is twice as large as the compressed data set size.
Claim 20
Dependent Claim
112 words
An image data compression block comprising: a pixel grouping block, wherein the pixel grouping block receives image
data that includes a plurality of pixels and groups the pixels into a plurality of
pixel sets of a predetermined size; a transform block operably coupled to the pixel grouping block, wherein
the transform block receives a pixel set and performs a discrete cosine
transformation of the pixel set to produce a transform data set, wherein the
transform data set includes a plurality of coefficients; and a compression block operably coupled to the transform block, wherein
the compression block compresses at least a portion of the transform data set
to produce a compressed data set.
Claim 21
Dependent Claim
133 words
The image data compression block of Claim 20, wherein the
compression block further comprises: a mapping block operably coupled to the transform block, wherein the
mapping block maps each coefficient of the plurality of coefficients to a
predetermined range corresponding to each coefficient to produce mapped
coefficients; a coefficient selection block operably coupled to the transform block,
wherein the coefficient selection block determines selected coefficients from
the plurality of coefficients; and a packing block operably coupled to the mapping block and the
coefficient selection block, wherein the packing block packs the mapped
coefficients corresponding to the selected coefficients to produce the
compressed data set, wherein the packing block includes a compressed
coefficient identifier in the compressed data set, wherein the compressed
coefficient identifier identifies the selected coefficients represented in the
compressed data set.
Claim 22
Dependent Claim
83 words
The image data compression block of Claim 21, wherein the
compression block further comprises a packing configuration block operably
coupled to the coefficient selection block and the packing block, wherein the
packing configuration block determines a bit quantity to include in the
compressed data set for each of the selected coefficients, wherein the
determination is based on the selected coefficients, wherein the packing block
performs the packing of the compressed data set based on the bit quantity for
each of the selected coefficients.
Claim 23
Dependent Claim
35 words
The image data compression block of Claim 22, wherein the mapping
block further comprises a multiplier, wherein the multiplier multiplies each
coefficient by a mapping multiplier corresponding to the coefficient to produce
a mapped coefficient.
Claim 24
Dependent Claim
53 words
The image data compression block of Claim 22, wherein the mapping
block further comprises a lookup block, wherein the lookup block stores
mapped values within the predetermined range for each coefficient and
provides a mapped value as one of the mapped coefficients in response to a
received coefficients received from the transform block.
Claim 25
Dependent Claim
38 words
The image data compression block of Claim 22, wherein the mapping
block further comprises a companding block, wherein the companding block
produces the mapped coefficients from received coefficients based on
companding functions corresponding to each of the coefficients.
Claim 26
Dependent Claim
113 words
The image data compression block of any one of Claims 22 to 25, wherein the compression block further comprises: a shifting block operably coupled to the mapping block, wherein the
shifting block shifts mapped coefficients such that lower order bits are shifted
into higher order bit locations to produce shifted mapped coefficients; and a truncation block operably coupled to the shifting block, the packing
configuration block, and the packing block, wherein the truncation block
truncates the shifted mapped coefficients based on bit quantities determined
by the packing configuration block to produce truncated coefficients; and wherein the packing block packs the truncated coefficients with the
compressed coefficient identifier to produce the compressed data set.
Claim 27
Dependent Claim
20 words
The image data compression block of Claim 26, wherein the truncation
block rounds the shifted mapped coefficients prior to truncation.
Claim 28
Dependent Claim
54 words
The image data compression block of Claim 26 or Claim 27, wherein
the compression block further comprises a clip monitor block operably
coupled to the truncation block, the mapping block, the shifting block, and the
packing configuration block, wherein the clip monitor block adjusts packing
parameters based on clip occurrences in the truncated coefficients.
Claim 29
Dependent Claim
37 words
The image data compression block of any one of Claims 21 to 28,
wherein the coefficient selection block compares at least a portion of the
plurality of coefficients with corresponding threshold values to determine the
selected coefficients.
Claim 30
Dependent Claim
137 words
A video data circuit, comprising: at least one memory client, wherein the at least one memory client
performs at least one of reading operations and writing operations, wherein
the reading operations retrieve video data from a memory, wherein writing
operation store video data in the memory; and a memory controller operably coupled to the at least one memory client
and adapted to couple to the memory, wherein the memory controller includes
a compression block and a decompression block, wherein the compression
block receives video data for writing operations and compresses the video
data to produce compressed video data for storage in the memory, wherein
the decompression block fetches compressed video data from the memory
and decompresses the compressed video data to produce video data
provided to the at least one memory client in response to reading operations.
Claim 31
Dependent Claim
18 words
The video data circuit of Claim 30, wherein the at least one memory
client includes an image processor.
Claim 32
Dependent Claim
15 words
The video data circuit of Claim 31, wherein the image processor
processes MPEG image data.
Claim 33
Dependent Claim
55 words
The video data circuit of Claim 32, wherein the image processor
receives an MPEG data stream, wherein the image processor combines data
in the MPEG data stream with data retrieved via the memory controller to
produce images, wherein data from at least a portion of the images is stored
in the memory via write operations.
Claim 34
Dependent Claim
31 words
The video data circuit of any one of Claims 30 to 33, wherein the
compression block of the memory controller is in accordance with any one of
Claims 20 to 29.
Claim 35
Dependent Claim
112 words
The video data circuit of Claim 34, wherein the decompression block
further comprises: an unpacking block, wherein the unpacking block receives the
compressed data from the memory, wherein the unpacking block separates
the compressed coefficients based on the coefficient identifier to produce the
mapped coefficients; an inverse mapping block operably coupled to the unpacking block,
wherein the inverse mapping block maps the mapped coefficients based on
an inverse mapping function to produce the plurality of coefficients; and an inverse discrete cosine transform block operably coupled to the
inverse mapping block, wherein the inverse discrete cosine transform block
performs an inverse cosine transform on the plurality of coefficients to
produce the pixel set.
Claim 36
Dependent Claim
116 words
An image data storage processor, comprising: a processing module; and memory operably coupled to the processing module, wherein the
memory includes operating instructions that cause the processing module to: separate the image data into a plurality of pixel sets, wherein each
pixel set is a predetermined pixel set size; and for each pixel set of the plurality of pixel sets: perform a discrete cosine transformation of the pixel set to produce a
plurality of transform coefficients; and compress the transform coefficients for the pixel set to produce a
compressed data set, wherein the compressed data set is a predetermined
compressed data set size, wherein the compressed data set size is less than
the pixel set size.
Claim 37
Dependent Claim
66 words
The image data storage processor of Claim 36, wherein the memory
further comprises operating instructions that cause the processing module to: determine a coefficient set, wherein the coefficient set indicates which
of the transform coefficients are represented in the compressed data set; compress values corresponding to coefficients included in the
coefficient set to produce compressed coefficients; and combine the compressed coefficients to produce the compressed set.
Claim 38
Dependent Claim
49 words
The image data storage processor of Claim 37, wherein the memory
further comprises operating instructions that cause the processing module to: combine the compressed coefficients with a compressed coefficient
identifier to produce the compressed set, wherein the compressed coefficient
identifier identifies the transform coefficients represented in the compressed
set.
Claim 39
Dependent Claim
54 words
The image data storage processor of Claim 38, wherein the
compressed coefficient identifier is an N-bit identifier, wherein N is a number,
wherein the N-bit identifier identifies a highest order coefficient in a (2 N ) range
of coefficients, wherein the highest order coefficient and lower order
coefficients are included in the coefficient set.
Claim 40
Dependent Claim
150 words
The image data storage processor of Claim 38, wherein the memory
further comprises instructions such that the processing module compresses
values by: mapping a value of the coefficient to a predetermined range for the
coefficient to produce a mapped value, wherein when a bit width of a
compressed coefficient corresponding to the coefficient is equal to a bit width
of the mapped value for the coefficient, the mapped value is the compressed
coefficient for the coefficient; and when the bit width of the compressed coefficient corresponding to the
coefficient is less than the bit width of the mapped value for the coefficient,
discarding a discard quantity of low order bits of the mapped value to produce
the compressed coefficient for the coefficient, wherein the discard quantity is
equal to a difference between the bit width of the mapped value for the
coefficient and the bit width for the compressed coefficient.
Claim 41
Dependent Claim
49 words
The image data storage processor of Claim 40, wherein the memory
further comprises operating instructions such that the processing module
maps each value to a predetermined range that corresponds to a power of
two such that a set of range bits can be used to represent the mapped value.
Claim 42
Dependent Claim
39 words
The image data storage processor of Claim 40, wherein the memory
further comprises operating instructions such that the processing module
maps the value of the coefficient by a mapping multiplier to produce a
mapped value within the predetermined range.
Claim 43
Dependent Claim
43 words
The image data storage processor of Claim 40, wherein the memory
further comprises operating instructions such that the processing module
maps the value of the coefficient by utilizing a look up function to produce the
mapped value from the value of the coefficient.
Claim 44
Dependent Claim
45 words
The image data storage processor of Claim 40, wherein the memory
further comprises operating instructions such that the processing module
maps the value of the coefficient by performing a compand operation on the
value of the coefficient to produce the mapped value for the coefficient.
Claim 45
Dependent Claim
65 words
The image data storage processor of Claim 40, wherein the memory
further comprises operating instructions such that the processing module
discards low order bits of the mapped value by: shifting the mapped value such that lower order bits are shifted into
higher order bit locations to produce a shifted mapped value; and discarding the discard quantity of low order bits of the shifted mapped
value.
Claim 46
Dependent Claim
51 words
The image data storage processor of Claim 45, wherein the memory
further comprises operating instructions such that the processing module
determines the discard quantity for each compressed coefficient from a
selected table, wherein the selected table is selected from a plurality of tables
corresponding to a plurality of potential coefficient sets.
Claim 47
Dependent Claim
53 words
The image data storage processor of any one of Claims 38 to 46,
wherein the memory further comprises operating instructions such that the
processing module determines the coefficient set by: comparing values of the transform coefficients with threshold values;
and including in the coefficient set transform coefficients whose values
exceed corresponding threshold values.
Claim 48
Dependent Claim
74 words
The image data storage processor of Claim 47, wherein the memory
further comprises operating instructions such that the processing module
compares values of the transform coefficients by: comparing values of a predetermined portion of the transform
coefficients with the threshold values; including a highest order coefficient that exceeds a corresponding
threshold value in the coefficient set; and including coefficients of a lower order as compared to the highest order
coefficient in the coefficient set.
Claim 49
Dependent Claim
21 words
The image data storage processor of any one of Claims 36 to 48,
wherein the image data is MPEG video data.
Claim 50
Dependent Claim
46 words
The image data storage processor of any one of Claims 36 to 48,
wherein the memory further comprises operation instruction such that the
processing module separates the image data into a plurality of 8-by-1 pixel
sets, wherein each 8-by-1 pixel set includes eight consecutive horizontal
pixels.
Claim 51
Dependent Claim
28 words
The image data storage processor of any one of Claims 36 to 50,
wherein the pixel set size is twice as large as the compressed data set size.
References Cited (Backward Citations)
US5126842A
Cited
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.