US5734744A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for compression and decompression of color data
Assignee: Pixar
•
Filing: 1995-06-07
•
Granted: 1998-03-31
•
Expires: 2015-06-07
Abstract
Abstract The present invention is a method and apparatus for compressing and decompressing data. In particular, the present invention provides a method for compressing color video data for storage on a CD-ROM for later playback on a computer system. The present invention uses an asymmetrical compression-decompression scheme that provides color compression, temporal compression, and spatial compression. In the preferred embodiment of the invention, the color compression is accomplished in three stages. In the first stage, the colors are sampled from the source data. This generates a histogram that contains the colors of the source material. Next, these colors are quantized into the target colors. In the third step of the color compression, the actual colors on the film are mapped to the quantized colors. The temporal compression step specifies a target display rate. Only those pixels that have changed significantly from frame to frame are updated. A bit mask is generated for each frame and is used to target those pixels that will be updated for each frame. The spatial compression step is used to further reduce storage requirements by dividing data into pixel "tiles." The CD-ROM stores an index into the table so that when data is required only the index need be provided, not the tile.
Inventors
- 👤 Andreas Wittenstein
- 👤 Loren Carpenter
- 👤 Leo Hourvitz
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 19:50
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/10; H04N19/102; H04N19/124; H04N19/126; H04N19/50; H04N19/503; H04N19/60
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
251 words
A computer system for compressing color images comprised of a plurality of sequenced frames, said computer system comprising: a first memory for storing a source image, said source image comprised of a plurality of sequenced frames, each of said frames comprised of an array of pixels having associated color of a first number of bits; a processor coupled to said first memory for sampling said source image and generating a histogram of a first plurality of colors found in said source image, said histogram containing a number of pixels associated with each of said first plurality of colors, said histogram stored in a second memory coupled to said processor; said processor for quantizing said first plurality of colors into a second plurality of colors, said second plurality of colors being less than said first plurality of colors; said processor for assigning one of said second plurality of colors to each of said pixels in said source image; said processor for comparing a color of each pixel of each frame to a color of a previously displayed pixel at a location associated with said each pixel to determine a salience, said salience being weighted by a lapsed time since said previously displayed pixel was last updated; said processor for marking said previously displayed pixel for display when said salience is less than a predetermined difference; and said processor for generating a tile table of n×n tiles of pixels of said frames where tiles to be displayed are copied from said tile table.
Claim 2
Dependent Claim
251 words
A computer system for compressing color images comprised of a plurality of sequenced frames, said computer system comprising: a first memory for storing a source image, said source image comprised of a plurality of sequenced frames, each of said frames comprised of an array of pixels having associated color of a first number of bits; a processor coupled to said first memory for sampling said source image and generating a histogram of a first plurality of colors found in said source image, said histogram containing a number of pixels associated with each of said first plurality of colors, said histogram stored in a second memory coupled to said processor; said processor for quantizing said first plurality of colors into a second plurality of colors, said second plurality of colors being less than said first plurality of colors; said processor for assigning one of said second plurality of colors to each of said pixels in said source image; said processor for comparing a color of each pixel of each frame to a color of a previously displayed pixel at a location associated with said each pixel to determine a salience, said salience being weighted by a lapsed time since said previously displayed pixel was last updated; said processor for marking said previously displayed pixel for display when said salience is less than a predetermined difference; and said processor for generating a tile table of n×n tiles of pixels of said frames where tiles to be displayed are copied from said tile table.
Claim 3
Dependent Claim
56 words
The computer system of claim 1, wherein said processor generates a compressed movie comprising said tile table, a plurality of tile codes, a color quantizer defining an assignment relationship between said first plurality of colors and said second plurality of colors, and a plurality of skip codes generated from said marking of said previously displayed pixel.
Claim 4
Dependent Claim
11 words
The computer system of claim 1, wherein said histogram is decimated.
Claim 5
Dependent Claim
36 words
The computer system of claim 1, further comprising a spatial cache, said spatial cache comprising nearby pixel color values from said first plurality of colors and respective quantized color values from said second plurality of colors.
Claim 6
Dependent Claim
19 words
The computer system of claim 1, further comprising a table containing precalculated distances between possible pairs of color values.
Claim 7
Dependent Claim
39 words
The computer system of claim 1, wherein said tile table is a dynamic tile table with updates of said tile table scheduled by examining a compressed image sequence backward to determine when updates of said tile table are needed.
Claim 8
Dependent Claim
25 words
The computer system of claim 6, wherein updates of said tile table are scheduled to appear as late as possible within an available remaining bandwidth.
Claim 9
Dependent Claim
51 words
The computer system of claim 1, further comprising a temporal cache for each pixel location in a frame, said temporal cache comprising in each pixel location of said frame a previous color value from said first plurality of colors and a respective quantized color value from said second plurality of colors.
Claim 10
Dependent Claim
24 words
The computer system of claim 8, wherein said temporal cache further comprises color values and respective quantized color values associated with a background image.
Claim 11
Dependent Claim
94 words
The computer system of claim 1, further comprising a set of color centroids determined by said processor calculating a distance metric between a color in said histogram and a plurality of current centroids, said plurality of current centroids residing in an immediate neighborhood of a Voronoi region of a centroid to which said color was assigned in a prior iteration, said processor assigning each color in said histogram to a closest current centroid and adjusting said current centroids based on an accumulation of deviations between each current centroid and a plurality of assigned colors.
Claim 12
Dependent Claim
24 words
The computer system of claim 10, wherein said set of color centroids is initialized from a plurality of most populous colors in said histogram.
Claim 13
Dependent Claim
24 words
The computer system of claim 10, wherein said immediate neighborhood comprises a plurality of centroids containing a closest neighboring centroid in each axis-aligned octant.
Claim 14
Dependent Claim
18 words
The computer system of claim 10, wherein noise is added to each current centroid on a decreasing schedule.
Claim 15
Dependent Claim
27 words
The computer system of claim 10, wherein said processor terminates a distance calculation if a partial distance in one dimension is greater than a current closest distance.
Claim 16
Dependent Claim
14 words
The computer system of claim 1, wherein said tiles are quantized by said processor.
Claim 17
Dependent Claim
38 words
The computer system of claim 15, wherein a current tile from said tiles is added to said tile table if a distance between said current tile and tiles in said tile table is greater than a threshold distance.
Claim 18
Dependent Claim
15 words
The computer system of claim 16, further comprising a temporal tile cache of quantized tiles.
Claim 19
Dependent Claim
15 words
The computer system of claim 16, further comprising a spatial tile cache of quantized tiles.
Claim 20
Dependent Claim
33 words
The computer system of claim 16, further comprising a distance cache containing a plurality of cache tiles and calculated distances between said plurality of cache tiles and each tile in said tile table.
References Cited (Backward Citations)
US4654720A
Cited
US5049986A
Cited
US5067152A
Cited
US5263100A
Cited
US5508822A
Cited
US5467413A
Cited
US5506624A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-03-30 | 2001-09-29 | 2002-03-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-03-30 | 2005-09-29 | 2006-03-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-03-30 | 2009-09-29 | 2010-03-31 | $7700.00 | Window Closed / Lapsed |