US5596659A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Preprocessing and postprocessing for vector quantization
Assignee: Apple Inc
•
Filing: 1992-09-01
•
Granted: 1997-01-21
•
Expires: 2012-09-01
Abstract
Abstract Improved proprecessing and postprocessing for vector quantization, for example, for encoding an image. In one embodiment, the luminosity of the vectors in an image are used to determine the codes for vector quantization. In another embodiment, a median filter is performed to eliminate motion artifacts. In another embodiment, temporal filtering is applied once the difference between an earlier frame and a current frame exceeds a threshold. Embodiments are also provided for adaptive temporal filtering based on temporal "no change" blocks and their errors. Embodiments are provided for different regions of images which reference different codebooks, and regions of variable size. Embodiments are also provided for shared and variable size codebooks for different images or other data.
Inventors
- 👤 James O. Normile
- 👤 Katherine S. Wang
- 👤 Hsi-Jung Wu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 22:06
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/008
Claims Analysis
Total Claims: 58
Claim 1
Independent Claim
158 words
A method of encoding an image comprising the following steps: a. adaptively preprocessing a first bitstream representative of said image in order to eliminate spatial redundancy by selectively subsampling individual vectors in said image based upon luminance of said individual vectors, reduce noise and control data rate, and generate a second bitstream on which to perform vector quantization, wherein said individual vectors include a block of adjacent pixels in said image; b. applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and c. performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.
Claim 2
Independent Claim
158 words
A method of encoding an image comprising the following steps: a. adaptively preprocessing a first bitstream representative of said image in order to eliminate spatial redundancy by selectively subsampling individual vectors in said image based upon luminance of said individual vectors, reduce noise and control data rate, and generate a second bitstream on which to perform vector quantization, wherein said individual vectors include a block of adjacent pixels in said image; b. applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and c. performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.
Claim 3
Dependent Claim
28 words
The method of claim 1 wherein said selective subsampling is performed according to a different weight assigned to different positions of the subsampled individual vectors in said image.
Claim 4
Dependent Claim
56 words
The method of claim 2 wherein said weight assigned to central regions of said image is less than said weight assigned to border regions of said image such that said border regions of said image are subsampled prior to said central regions of said image given similar characteristics of said central border regions of said image.
Claim 5
Dependent Claim
30 words
The method of claim 1 wherein said selective subsampling is performed according to a different weight assigned to different magnitudes of luminance of the subsampled individual vectors in said image.
Claim 6
Dependent Claim
23 words
The method of claim 4 wherein said weight increases as the magnitude of luminance of the individual subsampled vectors in said image increases.
Claim 7
Dependent Claim
16 words
The method of claim 5 wherein said different weight is generated by a rate control mechanism.
Claim 8
Dependent Claim
16 words
The method of claim 4 wherein said different weight is generated by a rate control mechanism.
Claim 9
Dependent Claim
30 words
The method of claim 1 wherein said selective subsampling is performed on individual vectors having edge transitions less than a first luminance threshold to preserve edge detail in said image.
Claim 10
Dependent Claim
16 words
The method of claim 8 wherein the first threshold is generated by a rate control mechanism.
Claim 11
Dependent Claim
27 words
The method of claim 1 further comprising the step of limiting the number of vectors chosen for subsampling in said image to a first number of vectors.
Claim 12
Dependent Claim
26 words
The method of claim 10 wherein the first number of vectors may be a value ranging from zero to the number of vectors in said image.
Claim 13
Independent Claim
145 words
A method of encoding an image comprising the following steps: a. adaptively preprocessing a first bitstream representative of said image in order to eliminate temporal redundancy by adaptively adjusting a difference threshold to determine whether blocks in said bitstream should be encoded according to rate control demands, and generate a second bitstream on which to perform vector quantization; b. applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and c. performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.
Claim 14
Independent Claim
145 words
A method of encoding an image comprising the following steps: a. adaptively preprocessing a first bitstream representative of said image in order to eliminate temporal redundancy by adaptively adjusting a difference threshold to determine whether blocks in said bitstream should be encoded according to rate control demands, and generate a second bitstream on which to perform vector quantization; b. applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and c. performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.
Claim 15
Dependent Claim
95 words
The method of claim 12 wherein said preprocessing step comprises determining whether a difference between a first vector in said image and a second vector in a previous image at a same spatial position as said first vector is less than a first threshold, then tagging said first vector as a no-change block, said tagging indicating that said vector quantization should not be performed on said first vector, said first threshold being adaptively adjusted based upon rate control demands determined by examining said fourth bitstream and errors in encoding previous vectors in said first bitstream.
Claim 16
Dependent Claim
73 words
The method of claim 13 wherein said preprocessing step further includes the step of determining whether said first vector in said image has been tagged as a no-change block for a first interval of time from previous images, and if so, then determining whether said difference is less than a second threshold, said second threshold being less than said first threshold, and if so, then tagging said fast vector as a no-change block.
Claim 17
Dependent Claim
30 words
The method of claim 14 wherein the first interval of time comprises a number of frames that said first vector has been tagged as a no-change block from previous images.
Claim 18
Dependent Claim
58 words
The method of claim 14 wherein the fast interval of time is determined based upon a fast age associated with the fast vector, said first age having an initial value which is pseudo-randomly generated and associated with said first vector upon an initial determination in a previous image that said vector should be tagged as a no-change block.
Claim 19
Independent Claim
170 words
A method of encoding an image comprising the following steps: a. based upon local image characteristics of said image, adaptively determining which filtering method in a first set of filtering methods best preserves detail in said image given rate control demands and which eliminates spatial redundancy in said image to generate a first bitstream on which to perform vector quantization; b. preprocessing said first bitstream using said filtering method in order to generate a second bitstream which is free of said spatial redundancy; c. applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and d. performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.
Claim 20
Independent Claim
170 words
A method of encoding an image comprising the following steps: a. based upon local image characteristics of said image, adaptively determining which filtering method in a first set of filtering methods best preserves detail in said image given rate control demands and which eliminates spatial redundancy in said image to generate a first bitstream on which to perform vector quantization; b. preprocessing said first bitstream using said filtering method in order to generate a second bitstream which is free of said spatial redundancy; c. applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and d. performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.
Claim 21
Dependent Claim
17 words
The method of claim 17 wherein said first set of filtering methods comprises a horizontal filtering method.
Claim 22
Dependent Claim
17 words
The method of claim 17 wherein said first set of filtering methods comprises a vertical filtering method.
Claim 23
Dependent Claim
18 words
The method of claim 17 wherein said first set of filtering methods comprises a upward diagonal filtering method.
Claim 24
Dependent Claim
18 words
The method of claim 17 wherein said first set of filtering methods comprises a downward diagonal filtering method.
Claim 25
Independent Claim
133 words
An apparatus for encoding an image comprising: a. means for adaptively preprocessing a first bitstream representative of said image in order to eliminate spatial redundancy, reduce noise and control data rate and generate a second bitstream on which to perform vector quantization; b. means for applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and c. means for performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.
Claim 26
Independent Claim
133 words
An apparatus for encoding an image comprising: a. means for adaptively preprocessing a first bitstream representative of said image in order to eliminate spatial redundancy, reduce noise and control data rate and generate a second bitstream on which to perform vector quantization; b. means for applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and c. means for performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.
Claim 27
Independent Claim
131 words
An apparatus for encoding an image comprising: a. means for adaptively preprocessing a first bitstream representative of said image in order to eliminate temporal redundancy reduce noise and control data rate, and generate a second bitstream on which to perform vector quantization; b. means for applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and c. means for performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a Single base address into said codebook for a plurality of said packed indices in said third bitstream and an associated offset value each for each packed index from said single base address to reference entries in said codebook.
Claim 28
Independent Claim
131 words
An apparatus for encoding an image comprising: a. means for adaptively preprocessing a first bitstream representative of said image in order to eliminate temporal redundancy reduce noise and control data rate, and generate a second bitstream on which to perform vector quantization; b. means for applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and c. means for performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a Single base address into said codebook for a plurality of said packed indices in said third bitstream and an associated offset value each for each packed index from said single base address to reference entries in said codebook.
Claim 29
Independent Claim
177 words
An apparatus for encoding an image comprising: a. means for adaptively determining based upon local image characteristics of said image a filter in a first set of filters which yields a minimum absolute error compared to vectors in a first bitstream representative of said image in order to eliminate spatial redundancy to generate a first bitstream on which to perform vector quantization; b. means for preprocessing said first bitstream using said filter in order to generate a second bitstream which is free of said spatial redundancy; c. means for applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and d. means for performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.
Claim 30
Independent Claim
177 words
An apparatus for encoding an image comprising: a. means for adaptively determining based upon local image characteristics of said image a filter in a first set of filters which yields a minimum absolute error compared to vectors in a first bitstream representative of said image in order to eliminate spatial redundancy to generate a first bitstream on which to perform vector quantization; b. means for preprocessing said first bitstream using said filter in order to generate a second bitstream which is free of said spatial redundancy; c. means for applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and d. means for performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.
Claim 31
Independent Claim
247 words
An apparatus for decoding an image comprising: a. means for creating a current codebook from a previous codebook including: i. means for detecting a reference to a first codebook entry which should be updated in a previous codebook; ii. means for updating said first codebook entry in said previous codebook from a received codebook entry to transform said previous codebook into said current codebook; b. means for receiving a coded bitstream including block header identifiers in said coded bitstream, each said block header identifier including one of the following: i. a first value indicating that subsequent blocks in said coded bitstream have not changed from a previous image; ii. a second value indicating that subsequent blocks in said coded bitstream have been subsampled and been vector quantized; or iii. a third value indicating that subsequent blocks in said coded bitstream have been vector quantized; c. means for receiving codebook indices in said coded bitstream, said codebook indices referencing entries in said current codebook; d. means for retrieving entries from said current codebook based upon said codebook indices received by said codebook receiving means; e. means for determining whether said codebook indices refer to vectors which have been subsampled according to said block header identifiers; f. means for upsampling said retrieved codebook entries for said vectors determined to be subsampled by said subsampling determining means; and g. means for displaying each of the vectors contained in said codebook entries retrieved by said retrieving means on a display means.
Claim 32
Independent Claim
247 words
An apparatus for decoding an image comprising: a. means for creating a current codebook from a previous codebook including: i. means for detecting a reference to a first codebook entry which should be updated in a previous codebook; ii. means for updating said first codebook entry in said previous codebook from a received codebook entry to transform said previous codebook into said current codebook; b. means for receiving a coded bitstream including block header identifiers in said coded bitstream, each said block header identifier including one of the following: i. a first value indicating that subsequent blocks in said coded bitstream have not changed from a previous image; ii. a second value indicating that subsequent blocks in said coded bitstream have been subsampled and been vector quantized; or iii. a third value indicating that subsequent blocks in said coded bitstream have been vector quantized; c. means for receiving codebook indices in said coded bitstream, said codebook indices referencing entries in said current codebook; d. means for retrieving entries from said current codebook based upon said codebook indices received by said codebook receiving means; e. means for determining whether said codebook indices refer to vectors which have been subsampled according to said block header identifiers; f. means for upsampling said retrieved codebook entries for said vectors determined to be subsampled by said subsampling determining means; and g. means for displaying each of the vectors contained in said codebook entries retrieved by said retrieving means on a display means.
Claim 33
Dependent Claim
36 words
The apparatus of claim 25 wherein the means for detecting the reference to the first codebook entry in the previous codebook includes means for detecting a bitmap referencing said first codebook entry in said previous codebook.
Claim 34
Dependent Claim
21 words
The apparatus of claim 25 wherein the means for upsampling codebook entries comprises means for replicating pixels from a codebook entry.
Claim 35
Dependent Claim
21 words
The apparatus of claim 25 wherein the means for upsampling codebook entries comprises means for interpolating pixels from a codebook entry.
Claim 36
Dependent Claim
29 words
The apparatus of claim 25 wherein the means for retrieving entries from said current codebook comprises means for using one index of said indices to reference said current codebook.
Claim 37
Dependent Claim
46 words
The apparatus of claim 29 wherein the means for using the index to reference said current codebook comprises means for adding said one index to a base address to calculate an actual index and using said actual index to reference said entry in said current codebook.
Claim 38
Independent Claim
187 words
An apparatus for decoding an image comprising: a. means for creating a current codebook from codebook entries transmitted by an encoding means; b. means for receiving a ceded bitstream including block header identifiers in said coded bitstream each said block head identifier including one of the following: i. a first value indicating that subsequent blocks in said coded bitstream have not changed from a previous image: ii. a second value indicating that subsequent blocks in said coded bitstream have been subsampled and been vector quantized: or iii. a third value indicating that subsequent block in said coded bitstream have been only vector quantized with no subsampling: c. means for receiving codebook indices in said coded bitstream, said codebook indices referencing entries in said current codebook; d. means for retrieving entries from said current codebook based upon said codebook indices received by said codebook receiving means; e. means for determining whether said codebook indices refer to vectors which have been subsampled according to said block header identifiers; and f. means for upsampling said retrieved codebook entries for said vectors determined to be subsampled by said subsampling determining means.
Claim 39
Independent Claim
187 words
An apparatus for decoding an image comprising: a. means for creating a current codebook from codebook entries transmitted by an encoding means; b. means for receiving a ceded bitstream including block header identifiers in said coded bitstream each said block head identifier including one of the following: i. a first value indicating that subsequent blocks in said coded bitstream have not changed from a previous image: ii. a second value indicating that subsequent blocks in said coded bitstream have been subsampled and been vector quantized: or iii. a third value indicating that subsequent block in said coded bitstream have been only vector quantized with no subsampling: c. means for receiving codebook indices in said coded bitstream, said codebook indices referencing entries in said current codebook; d. means for retrieving entries from said current codebook based upon said codebook indices received by said codebook receiving means; e. means for determining whether said codebook indices refer to vectors which have been subsampled according to said block header identifiers; and f. means for upsampling said retrieved codebook entries for said vectors determined to be subsampled by said subsampling determining means.
Claim 40
Dependent Claim
22 words
The apparatus of claim 31 further comprising means for displaying vectors comprising an image based upon entries retrieved from said current codebook.
Claim 41
Dependent Claim
23 words
The apparatus of claim 31 wherein said upsampling means comprises means for interpolating pixel values from said entries received from said current codebook.
Claim 42
Dependent Claim
23 words
The apparatus of claim 31 wherein said upsampling means comprises means for replicating pixel values from said entries received from said current codebook.
Claim 43
Dependent Claim
15 words
The apparatus of claim 31 wherein said vector is represented using luminance and chrominance information.
Claim 44
Dependent Claim
20 words
The apparatus of claim 31 wherein said vector is represented using a block of luminance and a single chrominance value.
Claim 45
Independent Claim
145 words
An apparatus for decoding an image comprising: a. means for receiving a reference to a previous codebook, wherein said reference to a previous codebook refers to one of a plurality of codebooks in said apparatus and each of said plurality of codebooks is used for decoding different spatial regions of said image; b. means for creating a current codebook from said previous codebook including: i. means for detecting a reference to a first codebook entry which should be updated in a previous codebook; ii. means for updating said first codebook entry in said previous codebook from a received codebook entry to transform said previous codebook into said current codebook; c. means for receiving codebook indices, said codebook indices referencing entries in said current codebook; and d. means for retrieving entries from said current codebook based upon said codebook indices received by said codebook receiving means.
Claim 46
Independent Claim
145 words
An apparatus for decoding an image comprising: a. means for receiving a reference to a previous codebook, wherein said reference to a previous codebook refers to one of a plurality of codebooks in said apparatus and each of said plurality of codebooks is used for decoding different spatial regions of said image; b. means for creating a current codebook from said previous codebook including: i. means for detecting a reference to a first codebook entry which should be updated in a previous codebook; ii. means for updating said first codebook entry in said previous codebook from a received codebook entry to transform said previous codebook into said current codebook; c. means for receiving codebook indices, said codebook indices referencing entries in said current codebook; and d. means for retrieving entries from said current codebook based upon said codebook indices received by said codebook receiving means.
Claim 47
Independent Claim
154 words
A method of encoding an image comprising the following steps: a. adaptively preprocessing a first bitstream representative of said image in order to eliminate redundancy by selectively subsampling individual vectors in said image based upon data rate demands and the luminance of each of said vectors, and generate a second bitstream on which to perform vector quantization, wherein said individual vectors include a block of adjacent pixels in said image; b. applying vector quantization to said second bitstream in order to create a third bitstream comprising indices referencing a codebook; and c. performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.
Claim 48
Independent Claim
154 words
A method of encoding an image comprising the following steps: a. adaptively preprocessing a first bitstream representative of said image in order to eliminate redundancy by selectively subsampling individual vectors in said image based upon data rate demands and the luminance of each of said vectors, and generate a second bitstream on which to perform vector quantization, wherein said individual vectors include a block of adjacent pixels in said image; b. applying vector quantization to said second bitstream in order to create a third bitstream comprising indices referencing a codebook; and c. performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.
Claim 49
Dependent Claim
28 words
The method of claim 38 wherein said selective subsampling is performed according to a different weight assigned to different positions of the subsampled individual vectors in said image.
Claim 50
Dependent Claim
57 words
The method of claim 39 wherein said weight assigned to central regions of said image is less than said weight assigned to border regions of said image such that said border regions of said image are subsampled prior to said central regions of said image given similar characteristics of said central and border regions of said image.
Claim 51
Dependent Claim
30 words
The method of claim 38 wherein said selective subsampling is performed according to a different weight assigned to different magnitudes of luminanee of the subsampled individual vectors in said image.
Claim 52
Dependent Claim
23 words
The method of claim 41 wherein said weight increases as the magnitude of luminanee of the individual subsampled vectors in said image increases.
Claim 53
Dependent Claim
29 words
The method of claim 38 wherein said selective subsampling is performed on individual vectors having edge transitions less than a first threshold to preserve edge detail in said image.
Claim 54
Dependent Claim
16 words
The method of claim 43 wherein the first threshold is generated by a rate control mechanism.
Claim 55
Dependent Claim
29 words
The method of claim 38 further comprising the step of limiting the numbers of vectors chosen for subsampling in said image is limited to a first number of vectors.
Claim 56
Dependent Claim
26 words
The method of claim 45 wherein the first number of vectors may be a value ranging from zero to the number of vectors in said image.
Claim 57
Independent Claim
120 words
An apparatus for encoding an image comprising: a. preprocessing circuitry for adaptively preprocessing a first bitstream representative of said image in order to eliminate redundancy based upon data rate demands, and generate a second bitstream on which to perform vector quantization; b. vector quantization circuitry for encoding said second bitstream in order to create a third bitstream comprising indices referencing a codebook; and c. index packing circuitry for processing said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality said indices in said third bitstream and a plurality of associated offset values from said single base address to reference entries in said codebook.
Claim 58
Independent Claim
120 words
An apparatus for encoding an image comprising: a. preprocessing circuitry for adaptively preprocessing a first bitstream representative of said image in order to eliminate redundancy based upon data rate demands, and generate a second bitstream on which to perform vector quantization; b. vector quantization circuitry for encoding said second bitstream in order to create a third bitstream comprising indices referencing a codebook; and c. index packing circuitry for processing said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality said indices in said third bitstream and a plurality of associated offset values from said single base address to reference entries in said codebook.
References Cited (Backward Citations)
US4733298A
Cited
US4941194A
Cited
US4807298A
Cited
US5194950A
Cited
US5086439A
Cited
US5068723A
Cited
US5124791A
Cited
US4987480A
Cited
US5241395A
Cited
US5142362A
Cited
US5046119A
Cited
US5121191A
Cited
US5313534A
Cited
US5231485A
Cited
US5278647A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-01-21 | 2000-07-22 | 2001-01-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-01-21 | 2004-07-22 | 2005-01-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-01-21 | 2008-07-22 | 2009-01-21 | $7700.00 | Window Closed / Lapsed |