Method and apparatus for implementing motion detection in video compression

• US 6,639,945 B2
• Filed: 01/12/2001
• Issued: 10/28/2003
• Est. Priority Date: 03/14/1997
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gupta, Anoop, Wang, Albert, Chaddha, Navin
• Primary Examiner(s): Le, Vu
• Application Number:
  US09/759,408
• Publication Number:
  US 20020106019A1
• Time in Patent Office: 1,019 Days
• Field of Search: 375/240.23, 375/240.02, 375/240.18, 375/240.24, 375/240.25, 375/240.29, 348/420.1, 348/393.1, 348/571, 348/577, 348/630, 302/246, 302/245, 302/248, 358/426.12, 358/426.13
• US Class Current: 375/240.23
• CPC Class Codes: H04N 19/107 between spatial and temporal predictive coding, e.g. picture refresh
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/154 Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion use of rate-distortion criteria H04N19/147
• CPC Class Codes: H04N 19/184 the unit being bits, e.g. of the compressed video stream
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

The present invention relates, in one aspect, to a method for processing video data that is divided into frames. The video data includes a current frame, which has an associated current macroblock, and an adjacent frame, which also has an associated macroblock. The method for processing video data involves obtaining an uncompressed current block that is a part of the current macroblock and an adjacent block that is part of the adjacent macroblock, and calculating a distance between the uncompressed current block and the adjacent block. It is determined whether the distance between the uncompressed current block and the adjacent block is acceptable. If the distance is unacceptable, then the current block is adoptively compressed.

Claims

1. A method for color space conversion, comprising:

partitioning components of a YUV color space value to designate high bits and low bits of each component;

combining the high bits of each component to form one or more high YUV indexes in a high YUV table;

combining the low bits of each component to form one or more low YUV indexes in a low YUV table;

converting the one or more high YUV indexes into corresponding one or more high RGB values of a high RGB table;

converting the one or more low YUV indexes into corresponding one or more low RGB values of a low RGB table; and

combining the one or more high RGB values with the one or more low RGB values to generate an RGB color space value.

2. A method as recited in claim 1, wherein partitioning the components includes:

partitioning a Y-component of the YUV color space value into high Y-bits and low Y-bits;

partitioning a U-component of the YUV color space value into high U-bits and low U-bits; and

partitioning a V-component of the YUV color space value into high V-bits and low V-bits.

3. A method as recited in claim 1, wherein:

the one or more high RGB values are each generated as high R-bits, high G-bits, and high B-bits in the high RGB table; and

the one or more low RGB values are each generated as low R-bits, low G-bits, and low B-bits in the low RGB table.

4. A method as recited in claim 1, wherein combining the one or more high RGB values with the one or more low RGB values includes:

combining high R-bits with low R-bits to form an R-component of the RGB color space value;

combining high G-bits with low G-bits to form a G-component of the RGB color space value; and

combining high B-bits with low B-Bits to form a B-component of the RGB color space value.

5. A method as recited in claim 1, wherein:

the one or more high RGB values are each generated as high R-bits, high G-bits, and high B-bits in the high RGB table;

the one or more low RGB values are each generated as low R-bits, low G-bits, and low B-bits in the low RGB table; and

combining the one or more high RGB values with the one or more low RGB values includes;

combining the high R-bits with the low R-bits to form an R-component of the RGB color space value;

combining the high G-bits with the low G-bits to form a G-component of the RGB color space value; and

combining the high B-bits with the low B-Bits to form a B-component of the RGB color space value.

6. A method as recited in claim 5, further comprising clipping the high R-bits, the high G-bits, and the high B-bits in the high RGB table to avoid bit overflow when said combining the one or more high RGB values with the one or more low RGB values.

7. A method as recited in claim 1, further comprising:

dithering the one or more high YUV indexes in the high YUV table; and

dithering the one or more low YUV indexes in the low YUV table.

8. A method as recited in claim 7, further comprising:

clipping the one or more high YUV indexes in the high YUV table; and

clipping the one or more low YUV indexes in the low YUV table.

9. A method as recited in claim 1, further comprising clipping the one or more high RGB values in the high RGB table to avoid bit overflow when said combining the one or more high RGB values with the one or more low RGB values.

10. A system, comprising:

a memory component configured to maintain a high YUV table, a low YUV table, a high RGB table, and a low RGB table;

a color space conversion application configured to;

partition components of a YUV color space value to designate high bits and low bits of each component;

combine the high bits of each component to form one or more high YUV indexes in the high YUV table;

combine the low bits of each component to form one or more low YL indexes in the low YUV table;

convert the one or more high YUV indexes into corresponding one or more high RGB values of the high RGB table;

convert the one or more low YUV indexes into corresponding one or more low RGB values of the low RGB table; and

combine the one or more high RGB values with the one or more low RGB values to generate an RGB color space value.

11. A system as recited in claim 10, wherein the color space conversion application is further configured to:

partition a Y-component of the YUV color space value into high Y-bits and low Y-bits;

partition a U-component of the YUV color space value into high U-bits and low U-bits; and

partition a V-component of the YUV color space value into high V-bits and low V-bits.

12. A system as recited in claim 10, wherein the color space conversion application is further configured to:

generate the one or more high RGB values as high R-bits, high G-bits, and high B-bits in the high RGB table; and

generate the one or more low RGB values as low R-bits, low G-bits, and low B-bits in the low RGB table.

13. A system as recited in claim 10, wherein the color space conversion application is further configured to:

combine high R-bits with low R-bits to form an R-component of the RGB color space value;

combine high G-bits with low G-bits to form a G-component of the RGB color space value; and

combine high B-bits with low B-Bits to form a B-component of the RGB color space value.

14. A system as recited in claim 10, wherein the color space conversion application is further configured to:

generate the one or more high RGB values as high R-bits, high G-bits, and high B-bits in the high RGB table;

generate the one or more low RGB values as low R-bits, low G-bits, and low B-bits in the low RGB table;

combine the high R-bits with the low R-bits to form an R-component of the RGB color space value;

combine the high G-bits with the low G-bits to form a G-component of the RGB color space value; and

combine the high B-bits with the low B-Bits to form a B-component of the RGB color space value.

15. A system as recited in claim 14, wherein the color space conversion application is further configured to clip the high R-bits, the high G-bits, and the high B-bits in the high RGB table to avoid bit overflow when the one or more high RGB values are combined with the one or more low RGB values.

16. A system as recited in claim 10, wherein the color space conversion application is further configured to:

dither the one or more high YUV indexes in the high YUV table; and

dither the one or more low YUV indexes in the low YUV table.

17. A system as recited in claim 16, wherein the color space conversion application is further configured to:

clip the one or more high YUV indexes in the high YUV table; and

clip the one or more low YUV indexes in the low YUV table.

18. A system as recited in claim 10, wherein the color space conversion application is further configured to clip the one or more high RGB values in the high RGB table to avoid bit overflow when the one or more high RGB values are combined with the one or more low RGB values.

19. One or more computer-readable media comprising computer executable instructions that, when executed, implement a color space conversion comprising:

partitioning components of a YUV color space value to designate high bits and low bits of each component;

combining the high bits of each component to form one or more high YUV indexes in a high YUV table;

combining the low bits of each component to form one or more low YUV indexes in a low YUV table;

converting the one or more high YUV indexes into corresponding one or more high RGB values of a high RGB table;

converting the one or more low YUV indexes into corresponding one or more low RGB values of a low RGB table; and

combining the one or more high RGB values with the one or more low RGB values to generate an RGB color space value.

20. One or more computer-readable media as recited in claim 19, further comprising computer executable instructions that, when executed, further implement the color space conversion by:

partitioning a Y-component of the YUV color space value into high Y-bits and low Y-bits;

partitioning a U-component of the YUV color space value into high U-bits and low U-bits; and

partitioning a V-component of the YUV color space value into high V-bits and low V-bits.

21. One or more computer-readable media as recited in claim 19, further comprising computer executable instructions that, when executed, further implement the color space conversion by:

generating the one or more high RGB values as high R-bits, high G-bits, and high B-bits in the high RGB table; and

generating the one or more low RGB values as low R-bits, low G-bits, and low B-bits in the low RGB table.

22. One or more computer-readable media as recited in claim 19, further comprising computer executable instructions that, when executed, further implement the color space conversion by:

combining high R-bits with low R-bits to form an R-component of the RGB color space value;

combining high G-bits with low G-bits to form a G-component of the RGB color space value; and

combining high B-bits with low B-Bits to form a B-component of the RGB color space value.

23. One or more computer-readable media as recited in claim 19, further comprising computer executable instructions that, when executed, further implement the color space conversion by:

dithering the one or more high YUV indexes in the high YUV table; and

dithering the one or more low YUV indexes in the low YUV table.

24. One or more computer-readable media as recited in claim 19, further comprising computer executable instructions that, when executed, further implement the color space conversion by clipping high R-bits, high G-bits, and high B-bits in the high RGB table to avoid bit overflow when said combining the one or more high RGB values with the one or more low RGB values.

25. A method for decoding a bit stream, comprising:

receiving the bit stream of data bits;

parsing a group of the data bits into a first stage table of first stage bits and at least a second stage table of second stage bits;

decoding the group of the data bits to determine a value corresponding to the group of the data bits, such that;

in an event that the value corresponding to the group of data bits is represented by the first stage bits, flushing one or more of the first stage bits that represent the value; and

in an event that the value corresponding to the group of data bits is represented by the first stage bits and the second stage bits, flushing the first stage bits and one or more of the second stage bits that, in combination, represent the value.

26. A method for decoding a bit stream as recited in claim 25, wherein parsing includes parsing the group of data bits into N-stage tables of N-stage bits.

27. A method for decoding a bit stream as recited in claim 25, wherein:

parsing includes parsing the group of data bits into N-stage tables of N-stage bits; and

decoding includes flushing the first stage bits, the second stage bits, and one or more of the N-stage bits that, in combination, represent the value.

28. One or more computer-readable media comprising computer executable instructions that, when executed, implement the method as recited in claim 25.

29. One or more computer-readable media comprising computer executable instructions that, when executed, implement the method as recited in claim 27.

30. A system, comprising:

a memory component configured to maintain N-stage tables of N-stage bits;

a table-based N-stage Huffman decoder configured to;

receive a bit stream of data bits;

parse a group of the data bits into a first stage table of first stage bits and at least a second stage table of second stage bits;

decode the group of the data bits to determine a value corresponding to the group of the data bits, such that;

in an event that the value corresponding to the group of data bits is represented by the first stage bits, the decoder is further

configured to flush one or more of the first stage bits that represent the value; and

in an event that the value corresponding to the group of data bits is represented by the first stage bits and the second stage bits, the decoder is further configured to flush the first stage bits and one or more of the second stage bits that, in combination, represent the value.

31. A system as recited in claim 30, wherein the table-based N-stage Huffman decoder is further configured to parse the group of the data bits into the N-stage tables of the N-stage bits.

32. A system as recited in claim 30, wherein the table-based N-stage Huffman decoder is further configured to:

parse the group of data bits into the N-stage tables of the N-stage bits; and

flush the first stage bits, the second stage bits, and one or more of the N-stage bits that, in combination, represent the value.