Fast compressed domain processing using orthogonality

• US 6,490,323 B1
• Filed: 06/17/1999
• Issued: 12/03/2002
• Est. Priority Date: 06/17/1999
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Bhaskaran, Vasudev, Shen, Bo
• Primary Examiner(s): Lee, Richard
• Application Number:
  US09/335,464
• Time in Patent Office: 1,265 Days
• Field of Search: H04/N.712, H04/N.730, 375/240.01, 375/240-2-2, 375/240.18, 375/240.2, 375/240.24, 382/232, 382/236, 382/238, 382/248, 382/250, 382/254, 708/400-402
• US Class Current: 375/240.2
• 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/60 using transform coding
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

Abstract

A method and apparatus for receiving and processing digitized video data in a discrete cosine transform (DCT) domain exploits the orthogonality of a convolution function along with the data sparseness present in the DCT domain. In a preferred method, the convolution function is applied to vectors associated with a plurality of input video data frames in consideration of an orthogonal characteristic of the convolution function. More specifically, cross-products of the input vectors which would yield non-zero output vectors are identified and weighting factors for the cross-products are determined in consideration of this orthogonality. An output video data frame is generated from the non-zero output vectors and the weighting factors. A convolution operation based upon the disclosed method and aparatus is suitable for chroma-keying as well as other video or audio blending applications.

Claims

1. A method for receiving and processing digitized video data in a transform domain, the method comprising the steps of:

providing a plurality of input video data frames in a transform domain;

identifying input vectors associated with the input video data frames, the input vectors all being in the transform domain;

using an orthogonal characteristic of a convolution function to determine which cross-products of the input vectors yield non-zero output vectors in the transform domain and determining weighting factors for the cross-products; and

generating an output video data frame by determining the cross-products of only the input vectors which yield non-zero output vectors in the transform domain and by applying the weighting factors to the cross-products.

2. The method of claim 1 wherein the transform domain is associated with an orthogonal transform.

3. The method of claim 1 wherein the input video data frames comprise blocks that do not depend upon data from other frames.

4. The method of claim 1 wherein the input video data frames comprise blocks that correspond to spatial domain blocks in only a current picture.

5. The method of claim 1 wherein the input vectors are discrete cosine transform (DCT) vectors.

6. The method of claim 1 wherein at least one of the input vectors is associated with an alpha channel.

7. The method of claim 1 wherein the output video data frame represents a chroma-keying operation associated with the input video data frames.

8. The method of claim 1 wherein the output video data frame represents an alpha blending operation associated with the input video data frames.

9. The method of claim 1 wherein the step of generating an output video data frame includes a discrete cosine transform (DCT) convolution.

10. The method of claim 1 wherein the step of generating an output video data frame includes a plurality of discrete cosine transform (DCT) convolutions.

11. A method for receiving and processing digitized video data in a transform domain, the method comprising the steps of:

providing a plurality of compressed input video data frames;

identifying input vectors associated with the input video data frames, the input vectors all being in a transform domain;

calculating a cross product of at least two of the input vectors;

using an orthogonal characteristic of a convolution function to determine which cross-products of the input vectors yield non-zero output vectors in the transform domain and determining weighting factors for the cross-products; and

generating an output video data frame.

12. A method for receiving and processing digitized video data in a transform domain, the method comprising the steps of:

providing a plurality of input video data frames in a transform domain;

identifying input vectors associated with the input video data frames, the input vectors all being in the transform domain;

using an orthogonal characteristic of a convolution function to determine which cross-products of the input vectors yield non-zero output vectors in the transform domain; and

generating an output video data frame.

13. The method of claim 12 further comprising the step of determining weighting factors for the cross-products.

14. The method of claim 13 further comprising the step of applying the same weighting factor to two cross products.

15. The method of claim 13 further comprising the step of obtaining a value of a weighting factor from a table of weighting factors.

16. The method of claim 15 wherein the table is at least a two-dimensional table having at least some of the weighting factors arranged in the table symmetrically about a line.

17. The method of claim 12 wherein the step of generating an output video data frame includes the step of determining the cross-products of only the input vectors which yield non-zero output vectors in the transform domain and by applying the weighting factors to the cross-products.

18. An apparatus, comprising:

means for receiving a plurality of input video data frames;

means for identifying input vectors associated with a transform representation of the input video data frames; and

means for determining which cross-products of the input vectors yield non-zero output vectors and for determining weighting factors for the cross-products using an orthogonal property associated with a convolution operation.

19. The apparatus of claim 18 wherein the convolution operation is used to generate the output data frame.

20. The apparatus of claim 18 wherein the convolution operation comprises performing cross-product multiplication on two discrete cosine transform (DCT) data.

21. An apparatus operative to receive, process and output digitized data frames, comprising:

machine readable media; and

instructions stored on the machine readable media that instruct a machine to

receive a plurality of static input data frames associated with an orthogonal transform,

identify input vectors associated with the static input data frames,

determine contributions of cross-products of the input vectors to output vectors and determine weighting factors for the cross-products using an orthogonal characteristic of a convolution operation, and

generate an output data frame associated with the cross-products and weighting factors.