Methods and apparatus for encoding a video signal

• US 7,295,614 B1
• Filed: 08/31/2001
• Issued: 11/13/2007
• Est. Priority Date: 09/08/2000
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Shen, Jiandong, Chan, Wai-Yip
• Primary Examiner(s): Vo; Tung
• Assistant Examiner(s): SENFI, BEHROOZ M
• Application Number:
  US09/945,116
• Time in Patent Office: 2,265 Days
• Field of Search: 348/405, 348/408, 348/407, 348/415, 348/401, 348/397, 348/398, 348/423, 348/409, 348/402, 348/422, 348/412, 348/413, 348/414, 348/416, 348/400, 348/417, 375/240, 375/240.16, 375/240.15, 375/240.18, 375/240.25, 375/240.12, 375/240.2, 375/240.24, 375/240.22, 382/238, 382/239, 382/173, 382/253, 382/240, 382/251, 382/270, 382/236, 382/232, 382/235, 340/401, 340/397, 340/398, 340/423, 340/409, 340/408, 340/407, 340/415, 340/402, 340/422, 340/405
• US Class Current: 375/240.25
• CPC Class Codes: H04N 19/103 Selection of coding mode or of prediction mode
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

The present invention relates to systems and methods for compressing, decompressing, and transmitting video data. The systems and methods include pixel by pixel motion estimation and compensation and efficient quantization of residual errors. The present invention applies block estimation of the residual error produced by motion compensation. The block estimation is applied by a local decoder to generate synthesized blocks of video data. The block estimation approximated uses a set of predetermined motion estimation errors that are stored as error vectors in a codebook. The codebook is included in an encoder of the present invention and converts an error vector for each block to an error vector index. The error vector index, which introduces minimal transmission burden, is then sent from the encoder to a target decoder. A receiving decoder also includes a copy of the codebook and converts the error vector index to its associated error vector for reconstruction of video data.

Claims

1. A system for providing video data, the system comprising:

a decoder apparatus configured to receive a bitstream comprising compressed video data and a residual error vector index, and configured to output the video data in an uncompressed format; and

a residual error codebook comprising a set of residual error vectors and a residual error vector index associated with each residual error vector, each residual error vector in the set of residual error vectors comprising an array of predetermined motion compensation errors.

2. The system of claim 1 wherein the decoder apparatus performs motion estimation and compensation on a pixel by pixel basis.

3. The system of claim 2 wherein the decoder apparatus performs pel-recursive motion estimation to produce motion vectors for each pixel in a block.

4. The system of claim 3 wherein the decoder apparatus generates reconstructed video data using the motion vectors for each pixel in the block and using the error vector provided by the codebook.

5. The system of claim 1 wherein the array of predetermined motion compensation errors include a predetermined motion compensation error for each pixel in the block.

6. The system of claim 1 further comprising a codeword decoder that decodes a codeword for the residual error vector index.

7. A method for decoding video data, the method comprising:

receiving a compressed bitstream containing the video data and a residual error vector index;

converting the residual error vector index to a residual error vector, the residual error vector comprising an array of predetermined motion compensation errors;

decoding a portion of the video data into an uncompressed format using the residual error vector; and

outputting the video data in the uncompressed format.

8. The method of claim 7 wherein the residual error vector is selected from a codebook comprising a set of residual error vectors using the residual error vector index.

9. The method of claim 7 further comprising repeating converting the residual error vector index to a residual error vector for each block in a frame of video.

10. The method of claim 7 wherein generating the video data portion includes performing motion estimation on each pixel in a block.

11. The method of claim 10 wherein the motion estimation is pel-recursive motion estimation.

12. The method of claim 7 wherein the portion is a block of pixels.

13. The method of claim 7 further comprising decoding a codeword associated with the residual error vector index from the compressed bitstream.

14. A system for providing a bitstream having compressed video data, the system comprising:

an encoder apparatus that receives uncompressed video data and outputs compressed video data, the encoder apparatus comprising;

a residual error codebook comprising a set of residual error vectors and a residual error vector index associated with each residual error vector, each residual error vector in the set of residual error vectors comprising an array of predetermined motion compensation errors;

a local decoder that generates synthesized video data according to a residual error vector provided by the residual error codebook.

15. The system of claim 14 further comprising a system encoder that embeds a selected residual error vector index in the compressed video data.

16. The system of claim 14 wherein the local decoder performs motion estimation and compensation on a pixel by pixel basis.

17. The system of claim 16 wherein the local decoder performs pel-recursive motion estimation to produce motion vectors for each pixel in a block.

18. The system of claim 17 wherein the local decoder generates synthesized video data using the motion vectors for each pixel in the block and using the residual error vector provided by the residual error codebook.

19. The system of claim 14 further comprising a residual error calculator that compares the synthesized video data produced by the local decoder with the uncompressed video data.

20. The system of claim 19 wherein the residual error calculator produces a measure of synthesis error for a block of video data.

21. The system of claim 14 further comprising a cost calculator that produces a synthesis cost based on a general distortion measurement.

22. The system of claim 14 further comprising an index selector that selects an output residual error vector index from the set of residual error vectors included in the residual error codebook based on the cost of synthesized video produced by the local decoder.

23. A method for encoding video data, the method comprising:

(a) generating synthesized video data for a portion of video data using predetermined motion compensation residual errors;

(b) comparing the synthesized video data with raw video data for the portion to generate a synthesis error for the portion; and

selecting a residual error vector index for the portion based on the synthesis error.

24. The method of claim 23 wherein the residual error vector index is selected from a residual error codebook comprising a set of residual error vectors, each residual error vector in the set of residual error vectors comprising an array of predetermined motion compensation errors.

25. The method of claim 24 further comprising repeating (a) and (b) for each residual error vector in the set of residual error vectors.

26. The method of claim 23 wherein generating synthesized video data includes performing motion estimation on each pixel in a block.

27. The method of claim 26 wherein the motion estimation is pel-recursive motion estimation.

28. The method of claim 23 wherein the portion is a block of pixels.

29. The method of claim 28 further comprising partitioning the video data into blocks.

30. The method of claim 28 wherein the block has a rectangular or square shape.

31. The method of claim 23 wherein the encoding is used within a multiple coding mode system.

32. The method of claim 23 further comprising quantifying the synthesis error for the portion.

33. The method of claim 23 further comprising embedding the residual error vector index into a compressed bitstream.

34. A method for constructing a residual error codebook, the residual error codebook comprising a set of residual error vectors and a residual error vector index associated with each residual error vector, each residual error vector in the set of residual error vectors comprising an array of predetermined motion compensation errors, the method comprising:

(a) generating a cluster center for each residual error vector in the residual error codebook;

(b) receiving a set of motion compensation error blocks;

(c) assigning each of the motion compensation error blocks to a cluster;

(d) updating the cluster center for residual each error vector in the residual error codebook to form a new cluster center for each residual error vector in the residual error codebook; and

(e) designating the new cluster center for each residual error vector in the residual error codebook as the array of predetermined motion compensation errors for each residual error vector in the residual error codebook.

35. The method of claim 34 wherein assigning each of the motion compensation error blocks to a cluster comprises determining a quantitative difference between a block of motion compensation errors and a cluster center.

36. The method of claim 34 wherein the cluster centers are generated randomly.

37. The method of claim 34 further including repeating (c) and (d).

38. A system for providing video data, the system comprising:

means for receiving a compressed bitstream containing the video data and a residual error vector index;

means for converting the error vector index to an error vector, the residual error vector comprising an array of predetermined motion compensation errors;

means for decoding a portion of the video data into an uncompressed format using the residual error vector; and

means for outputting the video data in the uncompressed format.

39. A system for encoding video data, the system comprising:

means for generating synthesized video data for a portion of video data using predetermined motion compensation errors;

means for comparing the synthesized video data with raw video data for the portion to generate a synthesis error for the portion; and

means for selecting a residual error vector index for the portion based on the synthesis error.