Mechanism for processing order-16 discrete cosine transforms

• US 8,417,045 B2
• Filed: 07/29/2010
• Issued: 04/09/2013
• Est. Priority Date: 07/29/2010
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Infoprint Solutions Company LLC (Ricoh Company Limited)
• Inventors: Hinds, Arianne Therese
• Primary Examiner(s): Do, Anh Hong
• Application Number:
  US12/846,502
• Publication Number:
  US 20120027318A1
• Time in Patent Office: 985 Days
• Field of Search: 382/232, 382/236, 382/240, 382/244, 382/250, 348/193, 375/E7.03, 375/E7.093, 708/203, 708/401, 708/402
• US Class Current: 382/250
• CPC Class Codes: H04N 19/439 using cascaded computational arrangements for performing a single operation, e.g. filtering
• CPC Class Codes: H04N 19/625 using discrete cosine transform [DCT]

Abstract

A computer generated method is disclosed. The method includes receiving data values and performing a 1-D 16×16 discrete cosine transform (DCT) on the data values by replacing each irrational constant used in multiplication operations with a rational dyadic constant that approximates the irrational constant. The output of the DCT is then scaled by a set of scale factors that refine the precision of the approximations used for the 16×16 DCT.

Claims

1. A data system comprising a processor having a transformer to receive data values and perform a 1-D 16×

16 discrete cosine transform (DCT) on the data values by replacing each irrational constant used in multiplication operations with a rational dyadic constant that approximates the irrational constant.

2. The system of claim 1 wherein replacing the irrational constants comprises replacing a first set of irrational constants in a second stage of the 1-D 16×

16 DCT with a first set of rational dyadic constants, replacing a second set of irrational constants in a third stage of the 1-D 16×

16 DCT with a second set of rational dyadic constants and replacing a third set of irrational constants in fourth and fifth stages of the 1-D 16×

16 DCT with a third set of rational dyadic constants.

3. The system of claim 2 wherein each of the first set of rational dyadic constants is scaled by a first common factor, the second set of rational dyadic constants is scaled by a second common factor and the third set of rational dyadic constants is scaled by a third common factor.

4. The system of claim 3 further comprising logic to pre-compute floating point scale factors.

5. The system of claim 4 wherein the floating point scale factors computed using the common factors reduces a number of multiplication operations to be performed in the 1-D 16×

16 DCT.

6. The system of claim 4 further comprising logic to convert the floating point scale factors to integer values.

7. A computer generated method comprising:

receiving data values;

performing a 1-D 16×

16 discrete cosine transform (DCT) on the data values by replacing each irrational constant used in multiplication operations with a rational dyadic constant that approximates the irrational constant; and

scaling the output of the 1-D 16×

16 DCT by a set of scale factors to refine precision of the approximations.

8. The method of claim 7 wherein replacing the irrational constants comprises:

replacing a first set of irrational constants in a second stage of the 1-D 16×

16 DCT with a first set of rational dyadic constants;

replacing a second set of irrational constants in a third stage of the 1-D 16×

16 DCT with a second set of rational dyadic constants; and

replacing a third set of irrational constants in fourth and fifth stages of the 1-D 16×

16 DCT with a third set of rational dyadic constants.

9. The method of claim 8 wherein each of the first set of rational dyadic constants is scaled by a first common factor, the second set of rational dyadic constants is scaled by a second common factor and the third set of rational dyadic constants is scaled by a third common factor.

10. The method of claim 9 further comprising pre-computing floating point scale factors prior to receiving the data values.

11. The method of claim 10 further wherein the floating point scale factors are converted to fixed-point factors by multiplying the floating point scale factors with some power of two.

12. The method of claim 10 wherein the floating point scale factors are adjusted based on available processing complexity.

13. The method of claim 12 wherein the floating point scale factors are adjusted using a power of two.

14. The method of claim 10 wherein the floating point scale factors computed using the common factors reduces a number of multiplication operations to be performed in the 1-D 16×

16 DCT.

15. An article of manufacture comprising a machine-readable medium including data that, when accessed by a machine, cause the machine to perform operations comprising:

receiving data values;

performing a 1-D 16×

16 discrete cosine transform (DCT) on the data values by replacing each irrational constant used in multiplication operations with a rational dyadic constant that approximates the irrational constant; and

scaling the output of the 1-D 16×

16 DCT by a set of scale factors that refine the precision of the approximations.

16. The article of manufacture of claim 15 wherein replacing the irrational constants comprises:

replacing a first set of irrational constants in a second stage of the 1-D 16×

16 DCT with a first set of rational dyadic constants;

replacing a second set of irrational constants in a third stage of the 1-D 16×

16 DCT with a second set of rational dyadic constants; and

replacing a third set of irrational constants in fourth and fifth stages of the 1-D 16×

16 DCT with a third set of rational dyadic constants.

17. The article of manufacture of claim 16 wherein each of the first set of rational dyadic constants is scaled by a first common factor, the second set of rational dyadic constants is scaled by a second common factor and the third set of rational dyadic constants is scaled by a third common factor.

18. The article of manufacture of claim 17 comprising a machine-readable medium including data that, when accessed by a machine, further cause the machine to perform operations comprising further comprising computing floating point scale factors prior to receiving the data values.

19. The article of manufacture of claim 18 wherein the floating point scale factors computed using the third common factor reduces a number of multiplication operations to be performed in the 1-D 16×

16 DCT.

20. The article of manufacture of claim 18 comprising a machine-readable medium including data that, when accessed by a machine, further cause the machine to perform operations comprising converting the floating point scale factors to integer values.

21. A printer comprising:

a transformer to receive data values and perform a 1-D 16×

16 discrete cosine transform (DCT) on the data values by replacing each irrational constant used in multiplication operations with a rational dyadic constant that approximates the irrational constant.

22. The printer of claim 21 further comprising a quantizer to reduce a number of bits needed to store transformed data by reducing the precision of transformed data values.

23. The printer of claim 22 further comprising an encoder to compress values received from the quantizer.