Fast DCT domain downsampling and inverse motion compensation

• US 5,708,732 A
• Filed: 03/06/1996
• Issued: 01/13/1998
• Est. Priority Date: 03/06/1996
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Bhaskaran, Vasudev, Merhav, Neri
• Primary Examiner(s): Coles, Sr., Edward L.
• Assistant Examiner(s): Wallerson, Mark
• Application Number:
  US08/611,922
• Time in Patent Office: 678 Days
• Field of Search: 382/232, 382/248, 382/250, 382/233, 382/234, 382/239, 358/261.3, 358/426, 358/427, 358/432, 358/433, 358/443, 358/445, 358/448, 348/398, 348/399, 341/65, 395/109, 395/115, 364/725
• US Class Current: 382/232
• CPC Class Codes: G06T 3/4084 in the transform domain, e.g. fast Fourier transform [FFT] domain scaling
• CPC Class Codes: G11B 27/034 on discs G11B27/036, G11B27/038 take precedence
• CPC Class Codes: H04N 19/40 using video transcoding, i.e. partial or full decoding of a coded input stream followed by re-encoding of the decoded output stream
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/48 using compressed domain processing techniques other than decoding, e.g. modification of transform coefficients, variable length coding [VLC] data or run-length data motion estimation in a transform domain H04N19/547; processing of decoded motion vectors H04N19/513
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/59 involving spatial sub-sampling or interpolation, e.g. alteration of picture size or resolution
• CPC Class Codes: H04N 19/61 in combination with predictive coding

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.

Claims

1. 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.

2. The method of claim 1, said processing step further comprising the step of:

using partially factorized operators.

3. 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₁ and X₂, where X has a plurality of components, each of which is an average of related components in x₁ and x₂, where x₁ =S_-1 X₁ and x₂ =S^-1 X₂, and where S is an N-point DCT matrix.

4. 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₁ and Q₂ are N×

N DCT-based matrices;

where matrices U₁ =SQ₁ S^-1 and U₂ =SQ₂ S^-1 ;

where a factorization S is represented as follows;

space="preserve" listing-type="equation">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₁ B₂ MA₁ A₂ A₃ are N×

N fixed matrices; and

where products;

space="preserve" listing-type="equation">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₁ +F₂ and a difference F_- =F₁ -F₂.

5. 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₁ and Q₂ are N×

N DCT-based matrices;

where matrices U₁ =SQ₁ S^-1 and U₂ =SQ₂ S^-1 ;

where a factorization S is represented as follows;

space="preserve" listing-type="equation">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₁ B₂ MA₁ A₂ A₃ are N×

N fixed matrices; and

where products;

space="preserve" listing-type="equation">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₁ +F₂ and a difference F_- =F₁ -F₂.

6. 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₁ and Q₂ are N×

N DCT-based matrices;

where matrices U₁ =SQ₁ S^-1 and U₂ =SQ₂ S^-1 ;

where a factorization S is represented as follows;

space="preserve" listing-type="equation">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₁ B₂ MA₁ A₂ A₃ are N×

N fixed matrices; and

where products;

space="preserve" listing-type="equation">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₁ +F₂ and a difference F_- =F₁ -F₂.

7. 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;

space="preserve" listing-type="equation">T=T.sub.1 +T.sub.2 +T.sub.3,

space="preserve" listing-type="equation">T.sub.+ =T.sub.1 +T.sub.3,

space="preserve" listing-type="equation">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₁ B₂ MA₁ A₂ A₃ are fixed N×

N matrices.

8. The method of claim 7, where:

##EQU30##

9. 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.

10. The method of claim 9, said processing step further comprising the step of:

using partially factorized operators.

11. 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₁, . . . , X₄ of x₁, . . . , x₄ respectively, where X=X+E, and X is a DCT of x, such that X is determined directly from X₁, . . . , X₄.

12. The method of claim 9, further comprising the step of:

precomputing fixed matrices;

space="preserve" listing-type="equation">J.sub.i Δ

U.sub.i (MA.sub.1 A.sub.2 A.sub.3).sup.t, i=1,2, . . . ,8

and

space="preserve" listing-type="equation">K.sub.i Δ

L.sub.i (MA.sub.1 A.sub.2 A.sub.3).sup.t, i=1,2, . . . ,8,

where Q₁ and Q₂ are N×

N DCT-based matrices;

where matrices U₁ =SQ₁ S^-1 and K₁ =SQ₂ S^-1 ;

where a factorization S is represented as follows;

space="preserve" listing-type="equation">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₁ B₂ MA₁ A₂ A₃ are fixed N×

N matrices.

13. The method of claim 12, further comprising the step of:

determining X in accordance with;

##EQU31##

14. The method of claim 12, further comprising the step of:

determining X in accordance with;

##EQU32##

15. The method of claim 12, further comprising the step of:

determining X in accordance with;

space="preserve" listing-type="equation">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.

16. 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.

17. The apparatus of claim 16, said processor further comprising:

means for using partially factorized operators.

18. 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₁ and X₂, where X has a plurality of components, each of which is an average of related components in x₁ and x₂, where x₁ =S^-1 X₁ and x₂ =S^-1 X₂, and where S is an N-point DCT matrix.

19. 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₁ and Q₂ are N×

N DCT-based matrices;

where matrices U₁ =SQ₁ S^-1 and U₂ =SQ₂ S^-1 ;

where a factorization S is represented as follows;

space="preserve" listing-type="equation">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₁ B₂ MA₁ A₂ A₃ are N×

N matrices; and

where products;

space="preserve" listing-type="equation">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₁ +F₂ and a difference F_- =F₁ -F₂.

20. 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₁ and Q₂ are N×

N DCT-based matrices;

where matrices U₁ =SQ₁ S^-1 and U₂ =SQ₂ S^-1 ;

where a factorization S is represented as follows;

space="preserve" listing-type="equation">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₁ B₂ MA₁ A₂ A₃ are N×

N fixed matrices; and

where products;

space="preserve" listing-type="equation">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₁ +F₂ and a difference F_- =F₁ -F₂.

21. 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₁ and Q₂ are N×

N DCT-based matrices;

where matrices U₁ =SQ₁ S^-1 and U₂ =SQ₂ S^-1 ;

where a factorization S is represented as follows;

space="preserve" listing-type="equation">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₁ B₂ MA₁ A₂ A₃ are N×

N fixed matrices; and

where products;

space="preserve" listing-type="equation">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₁ +F₂ and a difference F_- =F₁ -F₂.

22. 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;

space="preserve" listing-type="equation">T=T.sub.1 +T.sub.2 +T.sub.3,

space="preserve" listing-type="equation">T.sub.+ =T.sub.1 +T.sub.3,

space="preserve" listing-type="equation">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₁ B₂ MA₁ A₂ A₃ are N×

N fixed matrices.

23. The apparatus of claim 22, where:

##EQU38##

24. 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.

25. The apparatus of claim 24, said processor further comprising:

means for using partially factorized operators.

26. 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₁, . . . , X₄ of x₁, . . . , x₄ respectively, where X=X+E, and X is a DCT of x, such that X is determined directly from X₁, . . . , X₄.

27. The apparatus of claim 26, further comprising:

means for precomputing fixed matrices;

space="preserve" listing-type="equation">J.sub.i Δ

U.sub.i (MA.sub.1 A.sub.2 A.sub.3).sup.t, i=1,2, . . . ,8

and

space="preserve" listing-type="equation">K.sub.i Δ

L.sub.i (MA.sub.1 A.sub.2 A.sub.3).sup.t, i=1,2, . . . ,8,

where Q₁ and Q₂ are N×

N DCT-based matrices;

where matrices U₁ =SQ₁ S^-1 and K₁ =SQ₂ S^-1 ;

where a factorization S is represented as follows;

space="preserve" listing-type="equation">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₁ B₂ MA₁ A₂ A₃ are N×

N fixed matrices.

28. The apparatus of claim 27, further comprising:

means for determining X in accordance with;

##EQU39##

29. The apparatus of claim 27, further comprising:

means for determining X in accordance with;

##EQU40##

30. The apparatus of claim 27, further comprising:

means for determining X in accordance with;

space="preserve" listing-type="equation">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.