Patent US6597739B1 successfully refreshed from Google Patents.
US6597739B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Three-dimensional shape-adaptive wavelet transform for efficient object-based video coding
Assignee: Microsoft Technology Licensing LLC
•
Filing: 2000-06-20
•
Granted: 2003-07-22
•
Expires: 2020-06-20
Abstract
Abstract A three-dimensional (3D) shape-adaptive discrete wavelet transform (SA-DWT) is provided for efficient object-based video coding. In a first stage, a one-dimensional SA-DWT is performed along the temporal direction among pixels that have temporal correspondence. The correspondence can be established by motion estimation or other matching approaches. SA-DWT in the temporal direction is used to treat emerging pixels, terminating pixels or pixels that have colliding correspondence pixels. After the temporal SA-DWT transform, the resulting temporal wavelet coefficients are placed in the spatial positions corresponding to the original pixels to maintain the spatial correlation within each frame. Then, in a second stage, a two-dimensional SA-DWT is applied to the temporal SA-DWT coefficients within each frame. The 3D SA-DWT can handle arbitrarily shaped video objects while providing flexible spatial and temporal scalability as in any wavelet-based coding scheme. The 3D SA-DWT can also track the video object motion and perform the wavelet transform among corresponding pixels for that object while keeping the spatial correlation within a frame.
Inventors
- 👤 Shipeng Li
- 👤 Ya-Qin Zhang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 20:43
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/60; H04N19/649; H04N19/20; H04N19/50; H04N19/503; H04N19/51; H04N19/577; H04N19/61; H04N19/615; H04N19/62; H04N19/63; H04N19/10; H04N19/102; H04N19/13
Claims Analysis
Total Claims: 65
Claim 1
Independent Claim
80 words
A video coding method comprising: wavelet transforming a one-dimensional array of pixel values selected from a sequence of video frames to produce a corresponding one-dimensional array of temporal wavelet coefficients; arranging the temporal wavelet coefficients within a plurality of two-dimensional coefficient arrays substantially corresponding to a spatial arrangement of the pixel values within the sequence of video frames; and wavelet transforming each of the two-dimensional coefficient arrays to produce corresponding three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 2
Dependent Claim
80 words
A video coding method comprising: wavelet transforming a one-dimensional array of pixel values selected from a sequence of video frames to produce a corresponding one-dimensional array of temporal wavelet coefficients; arranging the temporal wavelet coefficients within a plurality of two-dimensional coefficient arrays substantially corresponding to a spatial arrangement of the pixel values within the sequence of video frames; and wavelet transforming each of the two-dimensional coefficient arrays to produce corresponding three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 3
Dependent Claim
35 words
The method as recited in claim 1 , wherein wavelet transforming the one-dimensional array of pixel values further includes using a shape-adaptive discrete wavelet transform to produce the corresponding one-dimensional array of temporal wavelet coefficients.
Claim 4
Dependent Claim
39 words
The method as recited in claim 1 , wherein wavelet transforming each of the two-dimensional coefficient arrays further includes using a shape-adaptive discrete wavelet transform to produce the corresponding three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 5
Dependent Claim
78 words
The method as recited in claim 1 , wherein wavelet transforming the one-dimensional array of pixel values further includes: selectively associating pixel values with a pixel thread that runs in a temporal direction associated with the sequence of video frames; aligning spatially corresponding pixel values in the temporal direction; and identifying each pixel value as either a continuing pixel, an emerging pixel, a terminating pixel, or a colliding pixel within the pixel thread, or otherwise an isolated pixel.
Claim 6
Dependent Claim
34 words
The method as recited in claim 4 , wherein selectively associating pixel values with the pixel thread includes estimating a motion of at least one pixel with respect to the sequence of video frames.
Claim 7
Dependent Claim
31 words
The method as recited in claim 5 , wherein the one-dimensional array of pixel values includes at least one pixel thread that logically extends through at least two sequential video frames.
Claim 8
Dependent Claim
62 words
The method as recited in claim 4 , wherein wavelet transforming the one-dimensional array of pixel values further includes: determining a boundary for an arbitrarily shaped object image within at least a portion of the sequence of video frames, the boundary having at least one pixel value therein; and wavelet transforming each of the pixel values within an arbitrarily shaped object image.
Claim 9
Dependent Claim
46 words
The method as recited in claim 1 , wherein arranging the temporal wavelet coefficients within the plurality of two-dimensional coefficient arrays further includes: maintaining spatial alignment information for each pixel value; and redistributing the resulting temporal wavelet coefficients to corresponding spatial positions in each video frame.
Claim 10
Dependent Claim
54 words
The method as recited in claim 4 , wherein wavelet transforming the one-dimensional array of pixel values further includes: applying a lowpass filter to the pixel values to produce a corresponding lowpass thread having lowpass coefficients; and applying a highpass filter to the pixel values to produce a corresponding highpass thread having highpass coefficients.
Claim 11
Dependent Claim
26 words
The method as recited in claim 9 , wherein wavelet transforming the one-dimensional array of pixel values further includes: applying a lowpass filter to lowpass coefficients.
Claim 12
Dependent Claim
44 words
The method as recited in claim 9 , wherein wavelet transforming the one-dimensional array of pixel values further includes: sampling even frames in the lowpass thread to obtain the lowpass coefficients; and sampling odd frames in the highpass thread to obtain the highpass coefficients.
Claim 13
Dependent Claim
69 words
The method as recited in claim 7 , wherein wavelet transforming the one-dimensional array of pixel values further includes: identifying video frames as either even frames or odd frames; determining a motion vector for each isolated pixel within the object; and if a given isolated pixel is in an even frame, scaling the temporal wavelet coefficient related to the given isolated pixel by the square root of two (sqrt(2)).
Claim 14
Dependent Claim
109 words
The method as recited in claim 7 , wherein wavelet transforming the one-dimensional array of pixel values further includes: identifying video frames as either even frames or odd frames; determining a motion vector for each isolated pixel within the object; if a given isolated pixel is in an odd frame and the motion vector for the given isolated pixel points to a pixel position in a previous even frame that is not within the object, scaling the wavelet coefficient related to the given isolated pixel by the square root of two (sqrt(2)); and assigning the scaled wavelet coefficient to the spatial pixel position pointed to by the motion vector.
Claim 15
Dependent Claim
134 words
The method as recited in claim 7 , wherein wavelet transforming the one-dimensional array of pixel values further includes: identifying video frames as either even frames or odd frames; determining a motion vector for each isolated pixel within the object; if a given pixel is in an odd frame and the motion vector for the given isolated pixel points to a pixel position in a previous even frame that is within the object, scaling the wavelet coefficient related to the given isolated pixel by sqrt(2)/2(P is −P pre ), where P is is the temporal wavelet coefficient of the given isolated pixel and P pre is the wavelet coefficient of the pixel pointed to by the motion vector; and assigning the scaled wavelet coefficient to the pixel position pointed to by the motion vector.
Claim 16
Dependent Claim
128 words
The method as recited in claim 7 , wherein wavelet transforming the one-dimensional array of pixel values further includes: identifying video frames as either even frames or odd frames; determining a motion vector for each isolated pixel within the object; determining a motion vector for each isolated pixel within the object, wherein each object is positioned within a bounding box; and if a given pixel is in an even frame and the motion vector for the given isolated pixel points to a pixel position in a previous even frame that is outside of the bounding box, assigning the pixels in each layer a wavelet coefficient having a constant value, P con , and scaling the wavelet coefficient for the given isolated pixel by sqrt(2)/2(P is −P con ).
Claim 17
Dependent Claim
22 words
The method as recited in claim 1 , further comprising: scaling the three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 18
Dependent Claim
22 words
The method as recited in claim 1 , further comprising: encoding the three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 19
Dependent Claim
22 words
The method as recited in claim 1 , further comprising: storing the three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 20
Dependent Claim
22 words
The method as recited in claim 1 , further comprising: transmitting the three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 21
Dependent Claim
22 words
The method as recited in claim 1 , further comprising: selectively rendering the sequence of video frames using the three-dimensional wavelet coefficients.
Claim 22
Dependent Claim
85 words
A computer-readable medium having computer-executable instructions for performing steps comprising: wavelet transforming a one-dimensional array of pixel values selected from a sequence of video frames to produce a corresponding one-dimensional array of temporal wavelet coefficients; arranging the temporal wavelet coefficients within a plurality of two-dimensional coefficient arrays substantially corresponding to a spatial arrangement of the pixel values within the sequence of video frames; and wavelet transforming each of the two-dimensional coefficient arrays to produce corresponding three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 23
Dependent Claim
85 words
A computer-readable medium having computer-executable instructions for performing steps comprising: wavelet transforming a one-dimensional array of pixel values selected from a sequence of video frames to produce a corresponding one-dimensional array of temporal wavelet coefficients; arranging the temporal wavelet coefficients within a plurality of two-dimensional coefficient arrays substantially corresponding to a spatial arrangement of the pixel values within the sequence of video frames; and wavelet transforming each of the two-dimensional coefficient arrays to produce corresponding three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 24
Dependent Claim
36 words
The computer-readable medium as recited in claim 21 , wherein wavelet transforming the one-dimensional array of pixel values further includes using a shape-adaptive discrete wavelet transform to produce the corresponding one-dimensional array of temporal wavelet coefficients.
Claim 25
Dependent Claim
40 words
The computer-readable medium as recited in claim 21 , wherein wavelet transforming each of the two-dimensional coefficient arrays further includes using a shape-adaptive discrete wavelet transform to produce the corresponding three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 26
Dependent Claim
79 words
The computer-readable medium as recited in claim 21 , wherein wavelet transforming the one-dimensional array of pixel values further includes: selectively associating pixel values with a pixel thread that runs in a temporal direction associated with the sequence of video frames; aligning spatially corresponding pixel values in the temporal direction; and identifying each pixel value as either a continuing pixel, an emerging pixel, a terminating pixel, or a colliding pixel within the pixel thread, or otherwise an isolated pixel.
Claim 27
Dependent Claim
35 words
The computer-readable medium as recited in claim 24 , wherein selectively associating pixel values with the pixel thread includes estimating a motion of at least one pixel with respect to the sequence of video frames.
Claim 28
Dependent Claim
32 words
The computer-readable medium as recited in claim 25 , wherein the one-dimensional array of pixel values includes at least one pixel thread that logically extends through at least two sequential video frames.
Claim 29
Dependent Claim
63 words
The computer-readable medium as recited in claim 24 , wherein wavelet transforming the one-dimensional array of pixel values further includes: determining a boundary for an arbitrarily shaped object image within at least a portion of the sequence of video frames, the boundary having at least one pixel value therein; and wavelet transforming each of the pixel values within an arbitrarily shaped object image.
Claim 30
Dependent Claim
47 words
The computer-readable medium as recited in claim 21 , wherein arranging the temporal wavelet coefficients within the plurality of two-dimensional coefficient arrays further includes: maintaining spatial alignment information for each pixel value; and redistributing the resulting temporal wavelet coefficients to corresponding spatial positions in each video frame.
Claim 31
Dependent Claim
55 words
The computer-readable medium as recited in claim 24 , wherein wavelet transforming the one-dimensional array of pixel values further includes: applying a lowpass filter to the pixel values to produce a corresponding lowpass thread having lowpass coefficients; and applying a highpass filter to the pixel values to produce a corresponding highpass thread having highpass coefficients.
Claim 32
Dependent Claim
27 words
The computer-readable medium as recited in claim 29 , wherein wavelet transforming the one-dimensional array of pixel values further includes: applying a lowpass filter to lowpass coefficients.
Claim 33
Dependent Claim
45 words
The computer-readable medium as recited in claim 29 , wherein wavelet transforming the one-dimensional array of pixel values further includes: sampling even frames in the lowpass thread to obtain the lowpass coefficients; and sampling odd frames in the highpass thread to obtain the highpass coefficients.
Claim 34
Dependent Claim
70 words
The computer-readable medium as recited in claim 27 , wherein wavelet transforming the one-dimensional array of pixel values further includes: identifying video frames as either even frames or odd frames; determining a motion vector for each isolated pixel within the object; and if a given isolated pixel is in an even frame, scaling the temporal wavelet coefficient related to the given isolated pixel by the square root of two (sqrt(2)).
Claim 35
Dependent Claim
110 words
The computer-readable medium as recited in claim 27 , wherein wavelet transforming the one-dimensional array of pixel values further includes: identifying video frames as either even frames or odd frames; determining a motion vector for each isolated pixel within the object; if a given isolated pixel is in an odd frame and the motion vector for the given isolated pixel points to a pixel position in a previous even frame that is not within the object, scaling the wavelet coefficient related to the given isolated pixel by the square root of two (sqrt(2)); and assigning the scaled wavelet coefficient to the spatial pixel position pointed to by the motion vector.
Claim 36
Dependent Claim
135 words
The computer-readable medium as recited in claim 27 , wherein wavelet transforming the one-dimensional array of pixel values further includes: identifying video frames as either even frames or odd frames; determining a motion vector for each isolated pixel within the object; if a given pixel is in an odd frame and the motion vector for the given isolated pixel points to a pixel position in a previous even frame that is within the object, scaling the wavelet coefficient related to the given isolated pixel by sqrt(2)/2(P is −P pre ), where P is is the temporal wavelet coefficient of the given isolated pixel and P pre is the wavelet coefficient of the pixel pointed to by the motion vector; and assigning the scaled wavelet coefficient to the pixel position pointed to by the motion vector.
Claim 37
Dependent Claim
129 words
The computer-readable medium as recited in claim 27 , wherein wavelet transforming the one-dimensional array of pixel values further includes: identifying video frames as either even frames or odd frames; determining a motion vector for each isolated pixel within the object; determining a motion vector for each isolated pixel within the object, wherein each object is positioned within a bounding box; and if a given pixel is in an even frame and the motion vector for the given isolated pixel points to a pixel position in a previous even frame that is outside of the bounding box, assigning the pixels in each layer a wavelet coefficient having a constant value, P con , and scaling the wavelet coefficient for the given isolated pixel by sqrt(2)/2(P is −P con ).
Claim 38
Dependent Claim
23 words
The computer-readable medium as recited in claim 21 , further comprising: scaling the three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 39
Dependent Claim
26 words
The computer-readable medium as recited in claim 21 , further comprising computer-executable instructions for: encoding the three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 40
Dependent Claim
26 words
The computer-readable medium as recited in claim 21 , further comprising computer-executable instructions for: storing the three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 41
Dependent Claim
26 words
The computer-readable medium as recited in claim 21 , further comprising computer-executable instructions for: transmitting the three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 42
Dependent Claim
26 words
The computer-readable medium as recited in claim 21 , further comprising computer-executable instructions for: selectively rendering the sequence of video frames using the three-dimensional wavelet coefficients.
Claim 43
Dependent Claim
85 words
An arrangement comprising logic configured to wavelet transform a one-dimensional array of pixel values selected from a sequence of video frames to produce a corresponding one-dimensional array of temporal wavelet coefficients, arrange the resulting temporal wavelet coefficients within a plurality of two-dimensional coefficient arrays in positions that substantially correspond to a spatial arrangement of the pixel values within the sequence of video frames, and wavelet transform each of the two-dimensional coefficient arrays to produce corresponding three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 44
Dependent Claim
85 words
An arrangement comprising logic configured to wavelet transform a one-dimensional array of pixel values selected from a sequence of video frames to produce a corresponding one-dimensional array of temporal wavelet coefficients, arrange the resulting temporal wavelet coefficients within a plurality of two-dimensional coefficient arrays in positions that substantially correspond to a spatial arrangement of the pixel values within the sequence of video frames, and wavelet transform each of the two-dimensional coefficient arrays to produce corresponding three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 45
Dependent Claim
27 words
The arrangement as recited in claim 41 , wherein the logic uses a shape-adaptive discrete wavelet transform to produce the corresponding one-dimensional array of temporal wavelet coefficients.
Claim 46
Dependent Claim
31 words
The arrangement as recited in claim 41 , wherein the logic uses a shape-adaptive discrete wavelet transform to produce the corresponding three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 47
Dependent Claim
74 words
The arrangement as recited in claim 41 , wherein the logic is further configured to selectively associate pixel values with a pixel thread that runs in a temporal direction associated with the sequence of video frames, align spatially corresponding pixel values in the temporal direction, and identify each pixel value as either a continuing pixel, an emerging pixel, a terminating pixel, or a colliding pixel within the pixel thread, or otherwise an isolated pixel.
Claim 48
Dependent Claim
32 words
The arrangement as recited in claim 44 , wherein the logic is further configured to estimate a motion vector of at least one pixel with respect to the sequence of video frames.
Claim 49
Dependent Claim
31 words
The arrangement as recited in claim 45 , wherein the one-dimensional array of pixel values includes at least one pixel thread that logically extends through at least two sequential video frames.
Claim 50
Dependent Claim
58 words
The arrangement as recited in claim 44 , wherein the logic is further configured to determine a boundary for an arbitrarily shaped object image within at least a portion of the sequence of video frames, the boundary having at least one pixel value therein, and wavelet transform each of the pixel values within an arbitrarily shaped object image.
Claim 51
Dependent Claim
38 words
The arrangement as recited in claim 41 , wherein the logic is further configured to maintain spatial alignment information for each pixel value and redistribute the resulting temporal wavelet coefficients to corresponding spatial positions in each video frame.
Claim 52
Dependent Claim
49 words
The arrangement as recited in claim 44 , wherein the logic is further configured to apply a lowpass filter to the pixel values to produce a corresponding lowpass thread having lowpass coefficients, and a highpass filter to the pixel values to produce a corresponding highpass thread having highpass coefficients.
Claim 53
Dependent Claim
22 words
The arrangement as recited in claim 49 , wherein the logic is further configured to apply a lowpass filter to lowpass coefficients.
Claim 54
Dependent Claim
39 words
The arrangement as recited in claim 49 , wherein the logic is further configured to sample even frames in the lowpass thread to obtain the lowpass coefficients and odd frames in the highpass thread to obtain the highpass coefficients.
Claim 55
Dependent Claim
65 words
The arrangement as recited in claim 47 , wherein the logic is further configured to identify video frames as either even frames or odd frames, determine a motion vector for each isolated pixel within the object, and if a given isolated pixel is in an even frame, scale the temporal wavelet coefficient related to the given isolated pixel by the square root of two (sqrt(2)).
Claim 56
Dependent Claim
105 words
The arrangement as recited in claim 47 , wherein the logic is further configured to identify video frames as either even frames or odd frames, determine a motion vector for each isolated pixel within the object, if a given isolated pixel is in an odd frame and the motion vector for the given isolated pixel points to a pixel position in a previous even frame that is not within the object, scale the wavelet coefficient related to the given isolated pixel by the square root of two (sqrt(2)), and assign the scaled wavelet coefficient to the spatial pixel position pointed to by the motion vector.
Claim 57
Dependent Claim
130 words
The arrangement as recited in claim 47 , wherein the logic is further configured to identify video frames as either even frames or odd frames, determine a motion vector for each isolated pixel within the object, if a given pixel is in an odd frame and the motion vector for the given isolated pixel points to a pixel position in a previous even frame that is within the object, scale the wavelet coefficient related to the given isolated pixel by sqrt(2)/2(P is −P pre ), where P is is the temporal wavelet coefficient of the given isolated pixel and P pre is the wavelet coefficient of the pixel pointed to by the motion vector, and assign the scaled wavelet coefficient to the pixel position pointed to by the motion vector.
Claim 58
Dependent Claim
123 words
The arrangement as recited in claim 47 , wherein the logic is further configured to identify video frames as either even frames or odd frames, determine a motion vector for each isolated pixel within the object, determine a motion vector for each isolated pixel within the object, wherein each object is positioned within a bounding box, if a given pixel is in an even frame and the motion vector for the given isolated pixel points to a pixel position in a previous even frame that is outside of the bounding box, assign the pixels in each layer a wavelet coefficient having a constant value, P con , and scale the wavelet coefficient for the given isolated pixel by sqrt(2)/2(P is −P pre ).
Claim 59
Dependent Claim
27 words
The arrangement as recited in claim 41 , wherein the logic is further configured to scale the three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 60
Dependent Claim
27 words
The arrangement as recited in claim 41 , wherein the logic is further configured to encode the three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 61
Dependent Claim
35 words
The arrangement as recited in claim 41 , further comprising: memory operatively coupled to the logic and configured to allow the logic to store the three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 62
Dependent Claim
36 words
The arrangement as recited in claim 41 , further comprising: an interface operatively coupled to the logic and configured to allow the logic to output the three-dimensional wavelet coefficients associated with the sequence of video frames.
Claim 63
Dependent Claim
43 words
The arrangement as recited in claim 41 , further comprising: rendering logic operatively coupled to receive the three-dimensional wavelet coefficients associated with the sequence of video frames from the logic and selectively render the sequence of video frames using the three-dimensional wavelet coefficients.
Claim 64
Independent Claim
83 words
A method of processing a video signal that represents a video, the video including a plurality of frames organized in a temporal dimension, each frame including a two dimensional image, each image including an object, the method comprising: determining a boundary for the object; matching corresponding pixels within the boundary, each corresponding pixel being positioned in a different frame, and each pixel containing information that is embodied in the video signal; and processing the video signal with a shape-adaptive, three-dimensional discrete wavelet transform.
Claim 65
Independent Claim
83 words
A method of processing a video signal that represents a video, the video including a plurality of frames organized in a temporal dimension, each frame including a two dimensional image, each image including an object, the method comprising: determining a boundary for the object; matching corresponding pixels within the boundary, each corresponding pixel being positioned in a different frame, and each pixel containing information that is embodied in the video signal; and processing the video signal with a shape-adaptive, three-dimensional discrete wavelet transform.
References Cited (Backward Citations)
US6393060B1
Cited
US6215916B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-07-21 | 2007-01-20 | 2007-07-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-07-21 | 2011-01-20 | 2011-07-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-07-21 | 2015-01-20 | 2015-07-22 | $7700.00 | Window Closed / Lapsed |