Method of reducing computations in intra-prediction and mode decision processes in a digital video encoder

• US 20070237224A1
• Filed: 03/28/2006
• Published: 10/11/2007
• Est. Priority Date: 03/28/2006
• Status: Active Grant

• Current Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Inventors: Krishnan, Rathish
• Granted Patent: US 7,929,608 B2
• Time in Patent Office: Days
• US Class Current: 375/240.120
• CPC Class Codes: H04N 19/11 among a plurality of spatial predictive coding modes
• CPC Class Codes: H04N 19/122 Selection of transform size, e.g. 8x8 or 2x4x8 DCT; Selection of sub-band transforms of varying structure or type
• 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/176 the region being a block, e.g. a macroblock
• 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/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

A method of improving the computation speed of the sum of absolute transformed distances (SATD) for different intra-prediction modes is described. Determining the SATD quicker provides the benefits of better coding performance without suffering the drawbacks of longer computation times. The method of reducing intra-prediction and mode decision processes in a video encoder, implements Hadamard transforms with improvements. Hadamard transforms are performed on an original block and predicted blocks and calculations are only performed where coefficients are non-zero thus skipping the coefficients that are zero. Using such an approach, the calculations required for the Vertical Prediction, Horizontal Prediction and DC Prediction are reduced significantly. Thus, the best intra-prediction mode is able to be determined very efficiently.

Claims

1. A method of reducing computations in intra-prediction and mode decision processes in video encoding processes, comprising:

a. calculating one or more absolute sums;

b. calculating one or more Hadamard transforms; and

c. obtaining one or more sums of absolute transformed differences using the one or more absolute sums and the one or more Hadamard transforms.

2. The method as claimed in claim 1 wherein the one or more absolute sums include common transformed coefficients, coefficients for vertical prediction and coefficients for horizontal prediction.

3. The method as claimed in claim 1 wherein calculating the one or more Hadamard transforms includes calculating a Hadamard transform for an original block.

4. The method as claimed in claim 1 wherein calculating the one or more Hadamard transforms includes calculating a Hadamard transform for vertical prediction.

5. The method as claimed in claim 1 wherein calculating the one or more Hadamard transforms includes calculating a Hadamard transform for horizontal prediction.

6. The method as claimed in claim 1 wherein calculating the one or more Hadamard transforms includes calculating a Hadamard transform for DC prediction.

7. The method as claimed in claim 1 further comprising reducing calculations by skipping the calculations with coefficients that are zero.

8. The method as claimed in claim 1 wherein obtaining the one or more sums of absolute transformed differences is for vertical prediction, horizontal prediction, DC prediction and plane prediction.

9. The method as claimed in claim 1 wherein the method results in determining a best intra-prediction mode.

10. The method as claimed in claim 1 wherein the computations are reduced to less than 4000.

11. The method as claimed in claim 1 wherein the computations are reduced in a video encoder.

12. The method as claimed in claim 11 wherein the video encoder utilizes H.264 standard protocol.

13. A method of obtaining a sum of absolute transformed differences for low-complexity mode decision, comprising:

a. computing a first Hadamard transform of an original block;

b. determining a first absolute sum of common transformed coefficients;

c. determining a second absolute sum of coefficients for prediction;

d. computing a second Hadamard transform of a predicted block;

e. computing a difference between the first Hadamard transform and the second Hadamard transform;

f. determining a third absolute sum of non-zero coefficients; and

g. obtaining the sum of absolute transformed differences by summing the first absolute sum, the second absolute sum and the third absolute sum.

14. The method as claimed in claim 13 wherein the prediction is vertical prediction.

15. The method as claimed in claim 13 wherein the prediction is horizontal prediction.

16. The method as claimed in claim 13 wherein the prediction is DC prediction.

17. The method as claimed in claim 13 wherein the predicted block is for vertical prediction.

18. The method as claimed in claim 13 wherein the predicted block is for horizontal prediction.

19. The method as claimed in claim 13 wherein the predicted block is for DC prediction.

20. The method as claimed in claim 13 wherein the method results in determining a best intra-prediction mode.

21. The method as claimed in claim 13 wherein the computations are reduced to less than 4000.

22. The method as claimed in claim 13 wherein the computations are reduced in a video encoder.

23. The method as claimed in claim 22 wherein the video encoder utilizes H.264 standard protocol.

24. A method of finding a best 16×

16 intra-prediction mode in video encoding processes, comprising;

a. obtaining a first sum of absolute transformed differences for vertical prediction;

b. obtaining a second sum of absolute transformed differences for horizontal prediction;

c. obtaining a third sum of absolute transformed differences for DC prediction; and

d. obtaining a fourth sum of absolute transformed differences for plane prediction.

25. The method as claimed in claim 24 wherein the first sum of absolute transformed differences is obtained by summing an absolute sum of common transformed coefficients, an absolute sum of coefficients for the vertical prediction and an absolute sum of non-zero coefficients for the vertical prediction.

26. The method as claimed in claim 24 wherein the second sum of absolute transformed differences is obtained by summing an absolute sum of common transformed coefficients, an absolute sum of coefficients for the horizontal prediction and an absolute sum of non-zero coefficients for the horizontal prediction.

27. The method as claimed in claim 24 wherein the third sum of absolute transformed differences is obtained by summing an absolute sum of common transformed coefficients, an absolute sum of coefficients for the vertical prediction, an absolute sum of coefficients for the horizontal prediction and an absolute sum of non-zero coefficients for the DC prediction.

28. The method as claimed in claim 24 further comprising reducing calculations by skipping the calculations with coefficients that are zero.

29. The method as claimed in claim 24 wherein the method results in determining a best intra-prediction mode.

30. The method as claimed in claim 24 wherein the computations are reduced to less than 4000.

31. The method as claimed in claim 24 wherein the computations are reduced in a video encoder.

32. The method as claimed in claim 31 wherein the video encoder utilizes H.264 standard protocol.

33. An apparatus for reducing computations in intra-prediction and mode decision processes in video encoding processes, comprising:

a. a program module for calculating a plurality of absolute sums, calculating a plurality of Hadamard transforms and obtaining one or more sums of absolute transformed differences using the plurality of Hadamard transforms; and

b. a processor for executing the program module.

34. The apparatus as claimed in claim 33 wherein the program module avoids computations where one or more coefficients are zero.

35. The apparatus as claimed in claim 33 wherein the computations are reduced to less than 4000.

36. The apparatus as claimed in claim 33 wherein the computations are reduced in a video encoder.

37. The apparatus as claimed in claim 36 wherein the video encoder utilizes H.264 standard protocol.

38. A video encoder comprising:

a. a component for intra-prediction, wherein the component for intra-prediction avoids computations where coefficients used are zero; and

b. an entropy coder coupled to the component for intra-prediction, wherein the entropy coder produces a plurality of compressed video bits.

39. The video encoder as claimed in claim 38 wherein the component for intra-prediction calculates a plurality of absolute sums, calculates a plurality of Hadamard transforms and obtains one or more sums of absolute transformed differences using the plurality of Hadamard transforms.

40. The video encoder as claimed in claim 38 wherein the computations are reduced to less than 4000.

41. The video encoder as claimed in claim 38 wherein the video encoder utilizes H.264 standard protocol.

42. A video capture and display device comprising:

a. a receiving unit for receiving video data;

b. a display unit coupled to the receiving unit for displaying video data; and

c. an encoder coupled to the receiving unit and the display unit for producing one or more compressed video bits,

wherein the encoder avoids computations where one or more coefficients are zero in intra-prediction and mode decision processes.

43. The video capture and display device as claimed in claim 42 wherein the computations are reduced to less than 4000.

44. The video capture and display device as claimed in claim 42 wherein the encoder utilizes H.264 standard protocol.