US6208693B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Chroma-key for efficient and low complexity shape representation of coded arbitrary video objects
Assignee: AT&T Inc
•
Filing: 1998-07-09
•
Granted: 2001-03-27
•
Expires: 2018-07-09
Abstract
Abstract A technique for implicitly encoding shape information by using a chroma-key color. A bounding box is created enclosing the video object. The bounding box is extended to be of size of next integer multiple of macroblock size and divided into a plurality of macroblocks. For each boundary macroblock, each pixel outside the object is replaced with the chroma-key color to implicitly encode shape information. Pixel data for boundary macroblocks and macroblocks inside the object are DCT transformed, scaled and motion compensated. A finer quantizer (smaller quantizer) is used for boundary macroblocks to improve image quality. A first_shape_code can be used to identify each macroblock as either 1) inside the object; 2) outside the object; or 3) on the object boundary. To improve data compression and achieve low complexity shape extraction with DCT and motion compensation, a first_shape_code is sent for all macroblocks, and only macroblocks that are inside the object or on the object boundary are coded. The decoding system decodes the first_shape_code and, if necessary, the DCT and motion compensation information. The motion compensated luminance and chrominance pixel values of a reconstructed object at the decoding system are compared to the chroma-key color and thresholds to reconstruct the shape of the object, and to output texture information of the video object.
Inventors
- 👤 Tsuhan Chen
- 👤 Atul Puri
- 👤 Robert Lewis Schmidt
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:31
CPC Classifications
H; H04; H04N; H04N9/00; H04N9/64; H04N9/74; H04N9/75; G; G06; G06T; G06T9/00; G06T9/20; H04N19/00; H04N19/10; H04N19/169; H04N19/186; H04N19/20; H04N19/21
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
178 words
A method of implicitly encoding shape information for a video object, comprising the steps of: receiving a video frame, including a video object; creating a box bounding the video object, the bounding box divided into a plurality of macroblocks, each macroblock comprising a plurality of chrominance and luminance pixels; identifying which macroblocks are inside the object or on the object boundary; for each boundary macroblock, replacing each pixel outside the object with a key color; for boundary macroblocks and macroblocks inside the object, computing luminance and chrominance pixel difference values by subtracting motion compensated prediction signals from the corresponding luminance and chrominance pixel values; for boundary macroblocks and macroblocks inside the object, transforming the luminance and chrominance pixel difference values to frequency domain coefficients; scaling the coefficients for macroblocks inside the object using a first quantizer; scaling the coefficients for boundary macroblocks using a second quantizer to provide a finer level of quantization for said boundary macroblocks as compared to said macroblocks inside the object; and outputting a bitstream including the scaled coefficients and information identifying the quantizers.
Claim 2
Independent Claim
178 words
A method of implicitly encoding shape information for a video object, comprising the steps of: receiving a video frame, including a video object; creating a box bounding the video object, the bounding box divided into a plurality of macroblocks, each macroblock comprising a plurality of chrominance and luminance pixels; identifying which macroblocks are inside the object or on the object boundary; for each boundary macroblock, replacing each pixel outside the object with a key color; for boundary macroblocks and macroblocks inside the object, computing luminance and chrominance pixel difference values by subtracting motion compensated prediction signals from the corresponding luminance and chrominance pixel values; for boundary macroblocks and macroblocks inside the object, transforming the luminance and chrominance pixel difference values to frequency domain coefficients; scaling the coefficients for macroblocks inside the object using a first quantizer; scaling the coefficients for boundary macroblocks using a second quantizer to provide a finer level of quantization for said boundary macroblocks as compared to said macroblocks inside the object; and outputting a bitstream including the scaled coefficients and information identifying the quantizers.
Claim 3
Independent Claim
215 words
A method of implicitly encoding shape information for a video object comprising the steps of: receiving a video frame, including a video object; creating the tightest box bounding the video object, extending the box in horizontal and vertical directions to fit the next integer number of macroblocks in each direction, the extended bounding box divided into a plurality of macroblocks, each macroblock comprising a 16×16 array of luminance pixels in the form of 4, 8×8 blocks and the corresponding chrominance pixels; identifying which macroblocks are inside the object or on the object boundary; for each boundary macroblock, replacing each pixel outside the object with a key color; for boundary macroblocks and macroblocks inside the object, computing luminance and chrominance pixel difference values by subtracting motion compensated prediction signals from the corresponding luminance and chrominance pixel values; for boundary macroblocks and macroblocks inside the object, transforming the luminance and chrominance pixel difference values to frequency domain coefficients; scaling the coefficients for macroblocks inside the object using a first quantizer; scaling the coefficients for boundary macroblocks using a second quantizer, wherein the second quantizer is smaller than or equal to the first quantizer to provide a finer level of quantization for said boundary macroblocks; and outputting a bitstream including the scaled coefficients and information identifying the quantizers.
Claim 4
Independent Claim
215 words
A method of implicitly encoding shape information for a video object comprising the steps of: receiving a video frame, including a video object; creating the tightest box bounding the video object, extending the box in horizontal and vertical directions to fit the next integer number of macroblocks in each direction, the extended bounding box divided into a plurality of macroblocks, each macroblock comprising a 16×16 array of luminance pixels in the form of 4, 8×8 blocks and the corresponding chrominance pixels; identifying which macroblocks are inside the object or on the object boundary; for each boundary macroblock, replacing each pixel outside the object with a key color; for boundary macroblocks and macroblocks inside the object, computing luminance and chrominance pixel difference values by subtracting motion compensated prediction signals from the corresponding luminance and chrominance pixel values; for boundary macroblocks and macroblocks inside the object, transforming the luminance and chrominance pixel difference values to frequency domain coefficients; scaling the coefficients for macroblocks inside the object using a first quantizer; scaling the coefficients for boundary macroblocks using a second quantizer, wherein the second quantizer is smaller than or equal to the first quantizer to provide a finer level of quantization for said boundary macroblocks; and outputting a bitstream including the scaled coefficients and information identifying the quantizers.
Claim 5
Dependent Claim
29 words
The method of claim 1 wherein the key color is chosen to be from among the less saturated colors and the key color does not exist in the object.
Claim 6
Dependent Claim
39 words
The method of claim 1 wherein said bitstream further comprises a first_shape_code provided for at least some of the macroblocks and efficiently identifying which of the macroblocks are inside the object and identifying which macroblocks are outside the object.
Claim 7
Dependent Claim
37 words
The method of claim 1 wherein said bitstream further comprises a first_shape_code provided for each macroblock and efficiently identifying which of the macroblocks are inside the object, outside the object or on the boundary of the object.
Claim 8
Dependent Claim
20 words
The method of claim 1 and further comprising the step of variable length coding the scaled coefficients and said information.
Claim 9
Dependent Claim
45 words
The method of claim 1 wherein said bitstream comprises coded motion vectors, transformed and scaled luminance and chrominance pixel difference values, and codes indicating the quantizers for boundary macroblocks and other macroblocks inside the bounding box, and an identification of the macroblocks outside the object.
Claim 10
Dependent Claim
35 words
The method of claim 1 wherein said step of transforming comprises the step of discrete cosine transform (DCT) transforming the luminance and chrominance values to DCT coefficients for boundary macroblocks and macroblocks inside the object.
Claim 11
Dependent Claim
78 words
The method of claim 1 wherein: said step of scaling the coefficients for macroblocks inside the object using a first quantizer comprises the step of dividing the coefficients for macroblocks inside the object by the first quantizer; and said step of scaling the coefficients for boundary macroblocks using a second quantizer comprises the step of dividing the coefficients for boundary macroblocks by the second quantizer, wherein the second quantizer is less than or equal to the first quantizer.
Claim 12
Independent Claim
160 words
A method of decoding a video bitstream in which the shape of a video object has been implicitly encoded, comprising the steps of: receiving a bitstream representing a video object, the bitstream including scaled frequency domain coefficients for each of a plurality of macroblocks inside the object or on the object boundary; rescaling the coefficients for macroblocks inside the object using a first quantizer; rescaling the coefficients for macroblocks on the object boundary using a second quantizer wherein the second quantizer is smaller than or equal to the first quantizer; inverse transforming the frequency domain coefficients to obtain luminance and chrominance pixel difference values; adding a prediction signal generated by a motion compensator to the luminance and chrominance pixel difference values to obtain the luminance and chrominance pixel values of a reconstructed video object; and recovering the approximate shape of the object by analyzing the luminance and chrominance values of at least the boundary macroblocks of the reconstructed video object.
Claim 13
Independent Claim
160 words
A method of decoding a video bitstream in which the shape of a video object has been implicitly encoded, comprising the steps of: receiving a bitstream representing a video object, the bitstream including scaled frequency domain coefficients for each of a plurality of macroblocks inside the object or on the object boundary; rescaling the coefficients for macroblocks inside the object using a first quantizer; rescaling the coefficients for macroblocks on the object boundary using a second quantizer wherein the second quantizer is smaller than or equal to the first quantizer; inverse transforming the frequency domain coefficients to obtain luminance and chrominance pixel difference values; adding a prediction signal generated by a motion compensator to the luminance and chrominance pixel difference values to obtain the luminance and chrominance pixel values of a reconstructed video object; and recovering the approximate shape of the object by analyzing the luminance and chrominance values of at least the boundary macroblocks of the reconstructed video object.
Claim 14
Dependent Claim
27 words
The method of claim 10 wherein each macroblock comprises a 16×16 array of luminance pixels in the form of 4, 8×8 blocks and the corresponding chrominance pixels.
Claim 15
Dependent Claim
34 words
The method of claim 10 wherein said step of inverse transforming comprises the step of inverse discrete cosine transform (DCT) transforming the frequency domain coefficients to obtain the luminance and chrominance pixel difference values.
Claim 16
Dependent Claim
92 words
The method of claim 10 wherein said step of recovering the approximate shape of the object comprises the following steps: decoding the chroma-key value and a threshold from the bitstream; comparing each pixel value of the boundary macroblocks of the reconstructed object to the chroma-key value; if the pixel value is within a threshold of the chroma-key value, then the pixel is not included in the recovered video object; if the pixel is not within the predetermined threshold of the chroma-key value, then the pixel is included in the recovered video object.
Claim 17
Dependent Claim
83 words
The method of claim 10 wherein said step of recovering the approximate shape of the object comprises the following steps: decoding the chroma-key value and first and second thresholds T 1 and T 2 from the bitstream; calculating an alpha map based on the pixel luminance and chrominance pixel values of the reconstructed object, the chroma-key color and the first and second thresholds; and applying the alpha map to the pixel luminance and chrominance pixel values to obtain final luminance and chrominance values.
Claim 18
Dependent Claim
106 words
The method of claim 14 wherein said step of calculating an alpha map comprises the following steps applied either to object boundary macroblocks or to object boundary as well as inside the object macroblocks: A) Calculate an alpha value for a decoded pixel (X) by first computing the distortion measure: d=(K Y −X Y ) 2 +(K U −X U ) 2 +(K V −X V ) 2 ; wherein K Y , K U and K V represent luminance and chrominance values for the chroma-key color K, and wherein X Y , X U and X V represent luminance and chrominance values for a pixel.
Claim 19
Dependent Claim
110 words
The method of claim 14 wherein said step of calculating an alpha map comprises the following steps applied either to object boundary macroblocks or to object boundary as well as inside the object macroblocks: A) Calculate an alpha value for a decoded pixel (X) by first computing the distortion measure: d 1 =|K Y −X Y |+|K U −X U |+|K V −X V |; wherein K Y , K U and K V represent luminance and chrominance values for the chroma-key color K, and wherein X Y , X U and X V represent luminance and chrominance values for a pixel; and multiply d 1 by a scaling factor.
Claim 20
Dependent Claim
146 words
The method of claim 15 wherein said step of applying comprises the steps of: B) calculate the alpha value (α) for each pixel in the said macroblocks as a function of distance d between the reconstructed pixel luminance and chrominance values (YUV) and the chroma-key color K (using K y , K u , K v , and thresholds T 1 and T 2 ) if (d<T 1 ) then α=0; else if (T 1 <d<T 2 ) then α=(d−T 1 )/(T 2 −T 1 )×255; else if (d>T 2 ) then α=255; and assigning α=0 to pixels of macroblocks outside the object and α=255 to pixels of macroblocks inside the object if not already assigned a value by above equations; and C) calculate the final pixel luminance and chrominance values for the reconstructed object as follows: pixel value=[α·X+(255−α)·Z]/255 wherein Z is the corresponding background pixel.
Claim 21
Dependent Claim
67 words
The method of claim 10 wherein: said step of resealing the transformed coefficients for macroblocks inside the object using a first quantizer comprises the step of multiplying the transformed coefficients by the first quantizer; and said step of rescaling the transformed coefficients for macroblocks on the object boundary using a second quantizer comprises the step of multiplying the transformed coefficients for boundary macroblocks by the second quantizer.
References Cited (Backward Citations)
US4394680A
Cited
US5194941A
Cited
US5117283A
Cited
US5659490A
Cited
US5999219A
Cited
US5963257A
Cited
US5974172A
Cited
US6141442A
Cited
US6122014A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-03-26 | 2004-09-25 | 2005-03-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-03-26 | 2008-09-25 | 2009-03-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-03-26 | 2012-09-25 | 2013-03-27 | $7700.00 | Window Closed / Lapsed |