Processing of performance sensitive transforms

• US 7,558,815 B2
• Filed: 01/24/2005
• Issued: 07/07/2009
• Est. Priority Date: 10/08/2004
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Infoprint Solutions Company LLC (Ricoh Company Limited)
• Inventors: Mitchell, Joan LaVerne, Hinds, Arianne Therese
• Primary Examiner(s): Ngo; Chuong D
• Application Number:
  US11/041,666
• Publication Number:
  US 20060080374A1
• Time in Patent Office: 1,625 Days
• Field of Search: 708/400, 708/550, 708/551, 708/402
• US Class Current: 708/402
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence

Abstract

The present invention provides a method, apparatus, and article of manufacture for controlling truncation error which is introduced when performing a transform equation as a result of lowering the precision of elements of the equation using shift right operations. This is achieved by associating a predetermined truncation amount with a plurality of operations of the transform equation and defining an ordered set of the operations to perform the transform which control the truncation error in the result if each operation introduced the predetermined truncation amount associated with it. Accordingly the transform is performed using the defined ordered set. For example the pre-determined truncation error could be an average truncation error.

Claims

1. A computer implemented method of reducing an error in an output of a digital image processed using a discrete cosine transform equation, the method comprising:

receiving the digital image for processing using the discrete cosine transform equation;

determining integer numerators and floating point denominators to approximate floating point coefficients of sub-transforms of the discrete cosine transform equation;

determining truncation errors generated from performing multiplication operations using the integer numerators, wherein the multiplication operations are implemented as shift right bit operations;

approximating a cumulative error in an output of the discrete cosine transform equation based on the truncation errors generated from performing the multiplication operations in the sub-transforms;

modifying at least one of the sub-transforms in the discrete cosine transform equation by changing at least one of an addition operation to a subtraction operation and a subtraction operation to an addition operation performed within the at least one of the sub-transforms to reduce the cumulative error in the output of the discrete cosine transform equation;

generating a modified discrete cosine transform equation including the modified at least one sub-transform; and

processing the digital image using the modified discrete cosine transform equation to generate the output.

2. The computer implemented method of claim 1 wherein determining the truncation errors further comprises using a probability distribution of a value of the floating point coefficients of the sub-transforms.

3. The computer implemented method of claim 1 further comprising:

receiving a digital image having known cumulative errors; and

modifying at least one of the sub-transforms in the discrete cosine transform equation based on the known cumulative errors in the digital image.

4. The computer implemented method of claim 1 wherein the discrete cosine transform equation is at least one of a forward discrete cosine transform and an inverse discrete cosine transform.

5. The computer implemented method of claim 1 wherein processing the digital image further comprises:

processing the digital image using the modified discrete cosine transform equation to generate an intermediate output; and

truncating the intermediate output to an integer value based on the approximated cumulative error to generate the output.

6. The computer implemented method of claim 1 wherein processing the digital image further comprises:

processing the digital image using the modified discrete cosine transform equation to generate an intermediate output;

quantizing the intermediate output to generate a quantized output; and

truncating the quantized output to an integer value based on the approximated cumulative error and a quantization value to generate the output.

7. An apparatus for reducing an error in an output of a digital image processed using a discrete cosine transform equation, the apparatus comprising:

a processor configured to receive the digital image for processing using the discrete cosine transform equation to determine integer numerators and floating point denominators to approximate floating point coefficients of sub-transforms of the discrete cosine transform equation, and to determine truncation errors generated from performing multiplication operations using the integer numerators, wherein the multiplication operations are implemented as shift right bit operations; and

a transformer configured to approximate a cumulative error in an output of the discrete cosine transform equation based on the truncation errors generated from performing the multiplication operations in the sub-transforms, to modify at least one of the sub-transforms in the discrete cosine transform equation by changing at least one of an addition operation to a subtraction operation and a subtraction operation to an addition operation performed within the at least one of the sub-transforms to reduce the cumulative error in the output of the discrete cosine transform equation, to generate a modified discrete cosine transform equation including the modified at least one sub-transform, and to process the digital image using the modified discrete cosine transform equation to generate the output.

8. The apparatus of claim 7 wherein the processor is farther operable to use a probability distribution of a value of the floating point coefficients of the sub-transforms.

9. The apparatus of claim 7 wherein:

the processor is further operable to receive a digital image having known cumulative errors; and

the transformer is further operable to modify at least one of the sub-transforms in the discrete cosine transform equation based on the known cumulative errors in the digital image.

10. The apparatus of claim 7 wherein the discrete cosine transform equation is at least one of a forward discrete cosine transform and an inverse discrete cosine transform.

11. The apparatus of claim 7 wherein the transformer is further operable to:

process the digital image using the modified discrete cosine transform equation to generate an intermediate output; and

truncate the intermediate output to an integer value based on the approximated cumulative error to generate the output.

12. The apparatus of claim 7 wherein the transformer is further operable to:

process the digital image using the modified discrete cosine transform equation to generate an intermediate output;

quantize the intermediate output to generate a quantized output; and

truncate the quantized output to an integer value based on the approximated cumulative error and a quantization value to generate the output.

13. A computer readable storage medium tangibly embodying programmed instructions which, when executed by a computer system, are operable for performing a method of reducing an error in an output of a digital image processed using a discrete cosine transform, the method comprising:

receiving the digital image for processing using the discrete cosine transform equation;

determining integer numerators and floating point denominators to approximate floating point coefficients of sub-transforms of the discrete cosine transform equation;

determining truncation errors generated from performing multiplication operations using the integer numerators, wherein the multiplication operations are implemented as shift right bit operations;

approximating a cumulative error in an output of the discrete cosine transform equation based on the truncation errors generated from performing the multiplication operations in the sub-transforms;

modifying at least one of the sub-transforms in the discrete cosine transform equation by changing at least one of an addition operation to a subtraction operation and a subtraction operation to an addition operation performed within the at least one of the sub-transforms to reduce the cumulative error in the output of the discrete cosine transform equation;

generating a modified discrete cosine transform equation including the modified at least one sub-transform; and

processing the digital image using the modified discrete cosine transform equation to generate the output.

14. The computer readable storage medium of claim 13 wherein determining the truncation errors further comprises using a probability distribution of a value of the floating point coefficients of the sub-transforms.

15. The computer readable storage medium of claim 13 further comprising:

receiving a digital image having known cumulative errors; and

modifying at least one of the sub-transforms in the discrete cosine transform equation based on the known cumulative errors in the digital image.

16. The computer readable storage medium of claim 13 wherein the discrete cosine transform equation is at least one of a forward discrete cosine transform and an inverse discrete cosine transform.

17. The computer readable storage medium of claim 13 wherein processing the digital image further comprises:

processing the digital image using the modified discrete cosine transform equation to generate an intermediate output; and

truncating the intermediate output to an integer value based on the approximated cumulative error to generate the output.

18. The computer readable storage medium of claim 13 wherein processing the digital image further comprises:

processing the digital image using the modified discrete cosine transform equation to generate an intermediate output;

quantizing the intermediate output to generate a quantized output; and

truncating the quantized output to an integer value based on the approximated cumulative error and a quantization value to generate the output.