Processing of performance sensitive transforms
View Patent ↗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.
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.