Patent US5708732A successfully refreshed from Google Patents.
US5708732A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fast DCT domain downsampling and inverse motion compensation
Assignee: Hewlett Packard Development Co LP
•
Filing: 1996-03-06
•
Granted: 1998-01-13
•
Expires: 2016-03-06
Abstract
Abstract Downsampling and inverse motion compensation are performed on compressed domain representations for video. By directly manipulating the compressed domain representation instead of the spatial domain representation, computational complexity is significantly reduced. For downsampling, the compressed stream is processed in the compressed (DCT) domain without explicit decompression and spatial domain downsampling so that the resulting compressed stream corresponds to a scaled down image, ensuring that the resulting compressed stream conforms to the standard syntax of 8×8 DCT matrices. For typical data sets, this approach of downsampling in the compressed domain results in computation savings around 80% compared with traditional spatial domain methods for downsampling from compressed data. For inverse motion compensation, motion compensated compressed video is converted into a sequence of DCT domain blocks corresponding to the spatial domain blocks in the current picture alone. By performing inverse motion compensation directly in the compressed domain, the reduction in computation complexity is around 68% compared with traditional spatial domain methods for inverse motion compensation from compressed data. The techniques for downsampling and inverse motion compensation can be used in a variety of applications, such as multipoint video conferencing and video editing.
Inventors
- 👤 Neri Merhav
- 👤 Vasudev Bhaskaran
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 10:30
CPC Classifications
G; G11; G11B; G11B27/00; G11B27/02; G11B27/031; G11B27/034; G06; G06T; G06T3/00; G06T3/40; G06T3/4084; H; H04; H04N; H04N19/00; H04N19/40; H04N19/42; H04N19/48; H04N19/50; H04N19/503; H04N19/51; H04N19/59; H04N19/60; H04N19/61
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
93 words
A method for downsampling image information in the compressed domain, where such information has been compressed in accordance with a discrete cosine transform (DCT) based compression scheme, the method comprising the steps of: Huffman decoding a compressed bitstream to extract a plurality of N×N DCT-based data blocks; processing n of said data blocks in accordance with at least one sampling matrix to extract a single N×N DCT-based data block, wherein n is determined by a desired downsampling factor, and wherein said single data block is a determined average of said N data blocks.
Claim 2
Independent Claim
93 words
A method for downsampling image information in the compressed domain, where such information has been compressed in accordance with a discrete cosine transform (DCT) based compression scheme, the method comprising the steps of: Huffman decoding a compressed bitstream to extract a plurality of N×N DCT-based data blocks; processing n of said data blocks in accordance with at least one sampling matrix to extract a single N×N DCT-based data block, wherein n is determined by a desired downsampling factor, and wherein said single data block is a determined average of said N data blocks.
Claim 3
Dependent Claim
17 words
The method of claim 1, said processing step further comprising the step of: using partially factorized operators.
Claim 4
Dependent Claim
80 words
The method of claim 1, said processing step further comprising the step of: determining X, a DCT of an N×N vector x, from at least two N-dimensional vectors X 1 and X 2 , where X has a plurality of components, each of which is an average of related components in x 1 and x 2 , where x 1 =S -1 X 1 and x 2 =S -1 X 2 , and where S is an N-point DCT matrix.
Claim 5
Dependent Claim
133 words
The method of claim 3, said determining step further comprising the steps of: performing a one-dimensional decimation by a factor of two in accordance with the relationship: ##EQU25## where Q 1 and Q 2 are N×N DCT-based matrices; where matrices U 1 =SQ 1 S -1 and U 2 =SQ 2 S -1 ; where a factorization S is represented as follows: S=DPB.sub.1 B.sub.2 MA.sub.1 A.sub.2 A.sub.3, where D is a fixed diagonal matrix, where P is a fixed permutation matrix; where B 1 B 2 MA 1 A 2 A 3 are N×N fixed matrices; and where products: F.sub.i =MA.sub.1 A.sub.2 A.sub.3 Q.sub.i A.sub.3.sup.-1 A.sub.2.sup.-1 A.sub.1.sup.-1 M.sup.-1 i=1,2 are sparse matrices, said matrix having a sum F + =F 1 +F 2 and a difference F - =F 1 -F 2 .
Claim 6
Dependent Claim
130 words
The method of claim 3, said determining step further comprising the steps of: downsampling by a factor of two in accordance with the relationship: ##EQU26## where Q 1 and Q 2 are N×N DCT-based matrices; where matrices U 1 =SQ 1 S -1 and U 2 =SQ 2 S -1 ; where a factorization S is represented as follows: S=DPB.sub.1 B.sub.2 MA.sub.1 A.sub.2 A.sub.3, where D is a fixed diagonal matrix, where P is a fixed permutation matrix; where B 1 B 2 MA 1 A 2 A 3 are N×N fixed matrices; and where products: F.sub.i =MA.sub.1 A.sub.2 A.sub.3 Q.sub.i A.sub.3.sup.-1 A.sub.2.sup.-1 A.sub.1.sup.-1 M.sup.-1 i=1,2 are sparse matrices, said matrix having a sum F + =F 1 +F 2 and a difference F - =F 1 -F 2 .
Claim 7
Dependent Claim
130 words
The method of claim 3, said determining step further comprising the steps of: downsampling by a factor of four in accordance with the relationship: ##EQU27## where Q 1 and Q 2 are N×N DCT-based matrices; where matrices U 1 =SQ 1 S -1 and U 2 =SQ 2 S -1 ; where a factorization S is represented as follows: S=DPB.sub.1 B.sub.2 MA.sub.1 A.sub.2 A.sub.3, where D is a fixed diagonal matrix, where P is a fixed permutation matrix; where B 1 B 2 MA 1 A 2 A 3 are N×N fixed matrices; and where products: F.sub.i =MA.sub.1 A.sub.2 A.sub.3 Q.sub.i A.sub.3.sup.-1 A.sub.2.sup.-1 A.sub.1.sup.-1 M.sup.-1 i=1,2 are sparse matrices, said matrix having a sum F + =F 1 +F 2 and a difference F - =F 1 -F 2 .
Claim 8
Dependent Claim
79 words
The method of claim 3, said determining step further comprising the steps of: downsampling by a factor of three in accordance with the relationship: ##EQU28## based on the fact that the matrices: T=T.sub.1 +T.sub.2 +T.sub.3, T.sub.+ =T.sub.1 +T.sub.3, T.sub.- =(T.sub.1 -T.sub.3)/2 are relatively sparse, and on the identity: ##EQU29## where D is a fixed diagonal matrix, where P is a fixed permutation matrix; and where B 1 B 2 MA 1 A 2 A 3 are fixed N×N matrices.
Claim 9
Dependent Claim
7 words
The method of claim 7, where: ##EQU30##
Claim 10
Independent Claim
127 words
A method for achieving inverse motion compensation in the compressed domain, where such information has been compressed in accordance with a discrete cosine transform (DCT) based compression scheme, the method comprising the steps of: Huffman decoding a compressed bitstream to extract a plurality of N×N DCT-based data blocks defining a picture T-1, and to extract a motion vector h,w; processing n of said data blocks in accordance with at least one sampling matrix and with said motion vector to produce a single N×N DCT-based data block corresponding to a picture T, wherein n is used to define a region occupied by said picture T-1, and wherein said single data block is a combination of a data block consisting of a determined average of said n data blocks.
Claim 11
Independent Claim
127 words
A method for achieving inverse motion compensation in the compressed domain, where such information has been compressed in accordance with a discrete cosine transform (DCT) based compression scheme, the method comprising the steps of: Huffman decoding a compressed bitstream to extract a plurality of N×N DCT-based data blocks defining a picture T-1, and to extract a motion vector h,w; processing n of said data blocks in accordance with at least one sampling matrix and with said motion vector to produce a single N×N DCT-based data block corresponding to a picture T, wherein n is used to define a region occupied by said picture T-1, and wherein said single data block is a combination of a data block consisting of a determined average of said n data blocks.
Claim 12
Dependent Claim
17 words
The method of claim 9, said processing step further comprising the step of: using partially factorized operators.
Claim 13
Dependent Claim
84 words
The method of claim 9, said processing step further comprising the step of: determining a DCT X of a current block x=x+e from a given DCT E of a prediction error e of the current block, and DCTs X 1 , . . . , X 4 of x 1 , . . . , x 4 respectively, where X=X+E, and X is a DCT of x, such that X is determined directly from X 1 , . . . , X 4 .
Claim 14
Dependent Claim
103 words
The method of claim 9, further comprising the step of: precomputing fixed matrices: J.sub.i ΔU.sub.i (MA.sub.1 A.sub.2 A.sub.3).sup.t, i=1,2, . . . ,8 and K.sub.i ΔL.sub.i (MA.sub.1 A.sub.2 A.sub.3).sup.t, i=1,2, . . . ,8, where Q 1 and Q 2 are N×N DCT-based matrices; where matrices U 1 =SQ 1 S -1 and K 1 =SQ 2 S -1 ; where a factorization S is represented as follows: S=DPB.sub.1 B.sub.2 MA.sub.1 A.sub.2 A.sub.3, where D is a fixed diagonal matrix, where P is a fixed permutation matrix; and where B 1 B 2 MA 1 A 2 A 3 are fixed N×N matrices.
Claim 15
Dependent Claim
16 words
The method of claim 12, further comprising the step of: determining X in accordance with: ##EQU31##
Claim 16
Dependent Claim
16 words
The method of claim 12, further comprising the step of: determining X in accordance with: ##EQU32##
Claim 17
Dependent Claim
23 words
The method of claim 12, further comprising the step of: determining X in accordance with: X=(X.sub.1 DPB.sub.1 B.sub.2 J.sub.w.sup.t +X.sub.2 DPB.sub.1 B.sub.2 J.sub.8-w.sup.t)S.sup.t.
Claim 18
Independent Claim
96 words
An apparatus for downsampling image information in the compressed domain, where such information has been compressed in accordance with a discrete cosine transform (DCT) based compression scheme, the apparatus comprising: a Huffman decoder for decoding a compressed bitstream to extract a plurality of N×N DCT-based data blocks; a processor for processing n of said data blocks in accordance with at least one sampling matrix to produce a single N×N DCT-based data block, wherein n is determined by a desired downsampling factor, and wherein said single data block is a determined average of said n data blocks.
Claim 19
Independent Claim
96 words
An apparatus for downsampling image information in the compressed domain, where such information has been compressed in accordance with a discrete cosine transform (DCT) based compression scheme, the apparatus comprising: a Huffman decoder for decoding a compressed bitstream to extract a plurality of N×N DCT-based data blocks; a processor for processing n of said data blocks in accordance with at least one sampling matrix to produce a single N×N DCT-based data block, wherein n is determined by a desired downsampling factor, and wherein said single data block is a determined average of said n data blocks.
Claim 20
Dependent Claim
15 words
The apparatus of claim 16, said processor further comprising: means for using partially factorized operators.
Claim 21
Dependent Claim
78 words
The apparatus of claim 16, said processing further comprising: means for determining X, a DCT of an N×N vector x, from at least two N-dimensional vectors X 1 and X 2 , where X has a plurality of components, each of which is an average of related components in x 1 and x 2 , where x 1 =S -1 X 1 and x 2 =S -1 X 2 , and where S is an N-point DCT matrix.
Claim 22
Dependent Claim
130 words
The apparatus of claim 18, said means for determining further comprising: means for performing a one-dimensional decimation by a factor of two in accordance with the relationship: ##EQU33## where Q 1 and Q 2 are N×N DCT-based matrices; where matrices U 1 =SQ 1 S -1 and U 2 =SQ 2 S -1 ; where a factorization S is represented as follows: S=DPB.sub.1 B.sub.2 MA.sub.1 A.sub.2 A.sub.3, where D is a diagonal matrix, where P is a permutation matrix; where B 1 B 2 MA 1 A 2 A 3 are N×N matrices; and where products: F.sub.i =MA.sub.1 A.sub.2 A.sub.3 Q.sub.i A.sub.3.sup.-1 A.sub.2.sup.-1 A.sub.1.sup.-1 M.sup.-1 i=1,2 are sparse matrices, said matrix having a sum F + =F 1 +F 2 and a difference F - =F 1 -F 2 .
Claim 23
Dependent Claim
130 words
The apparatus of claim 18, said means for determining further comprising: means for downsampling by a factor of two in accordance with the relationship: ##EQU34## where Q 1 and Q 2 are N×N DCT-based matrices; where matrices U 1 =SQ 1 S -1 and U 2 =SQ 2 S -1 ; where a factorization S is represented as follows: S=DPB.sub.1 B.sub.2 MA.sub.1 A.sub.2 A.sub.3, where D is a fixed diagonal matrix, where P is a fixed permutation matrix; where B 1 B 2 MA 1 A 2 A 3 are N×N fixed matrices; and where products: F.sub.i =MA.sub.1 A.sub.2 A.sub.3 Q.sub.i A.sub.3.sup.-1 A.sub.2.sup.-1 A.sub.1.sup.-1 M.sup.-1 i=1,2 are sparse matrices, said matrix having a sum F + =F 1 +F 2 and a difference F - =F 1 -F 2 .
Claim 24
Dependent Claim
130 words
The apparatus of claim 18, said means for determining further comprising: means for downsampling by a factor of four in accordance with the relationship: ##EQU35## where Q 1 and Q 2 are N×N DCT-based matrices; where matrices U 1 =SQ 1 S -1 and U 2 =SQ 2 S -1 ; where a factorization S is represented as follows: S=DPB.sub.1 B.sub.2 MA.sub.1 A.sub.2 A.sub.3, where D is a fixed diagonal matrix, where P is a fixed permutation matrix; where B 1 B 2 MA 1 A 2 A 3 are N×N fixed matrices; and where products: F.sub.i =MA.sub.1 A.sub.2 A.sub.3 Q.sub.i A.sub.3.sup.-1 A.sub.2.sup.-1 A.sub.1.sup.-1 M.sup.-1 i=1,2 are sparse matrices, said matrix having a sum F + =F 1 +F 2 and a difference F - =F 1 -F 2 .
Claim 25
Dependent Claim
79 words
The apparatus of claim 18, said means for determining further comprising: means for downsampling by a factor of three in accordance with the relationship: ##EQU36## based on the fact that the matrices: T=T.sub.1 +T.sub.2 +T.sub.3, T.sub.+ =T.sub.1 +T.sub.3, T.sub.- =(T.sub.1 -T.sub.3)/2 are relatively sparse, and on the identity: ##EQU37## where D is a fixed diagonal matrix, where P is a fixed permutation matrix; and where B 1 B 2 MA 1 A 2 A 3 are N×N fixed matrices.
Claim 26
Dependent Claim
7 words
The apparatus of claim 22, where: ##EQU38##
Claim 27
Independent Claim
129 words
An apparatus for achieving inverse motion compensation in the compressed domain, where such information has been compressed in accordance with a discrete cosine transform (DCT) based compression scheme, the apparatus comprising: a Huffman decoder for decoding a compressed bitstream to produce a plurality of N×N DCT-based data blocks defining a picture T-1 and to produce a motion vector h,w; a processor processing n of said data blocks in accordance with at least one sampling matrix and with said motion vector to produce a single N×N DCT-based data block corresponding to a frame T, wherein n is used to define a region occupied by said frame T-1, and wherein said single data block is a combination of a data block consisting of a determined average of said n data blocks.
Claim 28
Independent Claim
129 words
An apparatus for achieving inverse motion compensation in the compressed domain, where such information has been compressed in accordance with a discrete cosine transform (DCT) based compression scheme, the apparatus comprising: a Huffman decoder for decoding a compressed bitstream to produce a plurality of N×N DCT-based data blocks defining a picture T-1 and to produce a motion vector h,w; a processor processing n of said data blocks in accordance with at least one sampling matrix and with said motion vector to produce a single N×N DCT-based data block corresponding to a frame T, wherein n is used to define a region occupied by said frame T-1, and wherein said single data block is a combination of a data block consisting of a determined average of said n data blocks.
Claim 29
Dependent Claim
15 words
The apparatus of claim 24, said processor further comprising: means for using partially factorized operators.
Claim 30
Dependent Claim
78 words
The apparatus of claim 24, said processor further comprising: means for determining a DCT X of a current block x=x+e from a given DCT E of a prediction error e, and DCTs X 1 , . . . , X 4 of x 1 , . . . , x 4 respectively, where X=X+E, and X is a DCT of x, such that X is determined directly from X 1 , . . . , X 4 .
Claim 31
Dependent Claim
102 words
The apparatus of claim 26, further comprising: means for precomputing fixed matrices: J.sub.i ΔU.sub.i (MA.sub.1 A.sub.2 A.sub.3).sup.t, i=1,2, . . . ,8 and K.sub.i ΔL.sub.i (MA.sub.1 A.sub.2 A.sub.3).sup.t, i=1,2, . . . ,8, where Q 1 and Q 2 are N×N DCT-based matrices; where matrices U 1 =SQ 1 S -1 and K 1 =SQ 2 S -1 ; where a factorization S is represented as follows: S=DPB.sub.1 B.sub.2 MA.sub.1 A.sub.2 A.sub.3, where D is a fixed diagonal matrix, where P is a fixed permutation matrix; and where B 1 B 2 MA 1 A 2 A 3 are N×N fixed matrices.
Claim 32
Dependent Claim
15 words
The apparatus of claim 27, further comprising: means for determining X in accordance with: ##EQU39##
Claim 33
Dependent Claim
15 words
The apparatus of claim 27, further comprising: means for determining X in accordance with: ##EQU40##
Claim 34
Dependent Claim
22 words
The apparatus of claim 27, further comprising: means for determining X in accordance with: X=(X.sub.1 DPB.sub.1 B.sub.2 J.sub.w.sup.t +X.sub.2 DPB.sub.1 B.sub.2 J.sub.8-w.sup.t)S.sup.t.
References Cited (Backward Citations)
US5168375A
Cited
US5412428A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-01-12 | 2001-07-14 | 2002-01-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-01-12 | 2005-07-14 | 2006-01-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-01-12 | 2009-07-14 | 2010-01-13 | $7700.00 | Window Closed / Lapsed |