Efficient scaling in transform domain

• US 20050069224A1
• Filed: 09/30/2003
• Published: 03/31/2005
• Est. Priority Date: 09/30/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Nowicki, Tomasz J., Mitchell, Joan L., Martens, Marco, Trelewicz, Jennifer Q., Brady, Michael T., Trenary, Timothy J.
• Granted Patent: US 7,298,925 B2
• Time in Patent Office: Days
• US Class Current: 382/298
• CPC Class Codes: G06T 3/4084 in the transform domain, e.g. fast Fourier transform [FFT] domain scaling

Abstract

A method and system for efficient scaling in the transform domain, wherein transform coefficient data is provided as an input to a data processing system and scaled in the transform domain by application of a combined matrix. Some embodiments utilize discrete cosine transform data. One embodiment of the invention generates a combined matrix for one-dimensional scaling by selecting a rational scaling factor and matrix dimension value, generating a matrix with some zero values, applying a one-dimensional inverse transform, regrouping, and applying a one-dimensional forward transform. One application of the invention performs up-scaling operations, and another performs down-scaling operations. The invention also provides for two-dimensional scaling by selecting horizontal and vertical scaling parameters and generating first and second combined matrices responsive to the parameters and combining them into a single combined matrix. The invention may also incorporate a predetermined cost function.

Claims

1. A method for efficient scaling in the transform domain when transform coefficient data is provided as an input to a data processing system, comprising the steps of:

providing transform coefficient data; and

scaling data represented by the transform coefficient data in the transform domain by application of a combined matrix to said transform coefficient data.

2. The method of claim 1, whereby the step of scaling the data by application of a combined matrix further comprises generating the combined matrix for one-dimensional scaling, wherein generating the combined matrix comprises the steps of:

(a) selecting a rational scaling factor F;

(b) selecting a matrix dimension value m; and

(c) selecting g as the smallest integer wherein (Fg)/m is an integer k;

(d) generating a first matrix operating on at least one (mg)×

(m) matrix by;

(d1) zeroing out at least one row or at least one column of said matrix;

or

(d2) inserting at least one row of zeros or at least one column of zeros into said matrix;

(e) generating a second matrix by applying a one-dimensional inverse transform to the first matrix; and

(f) generating a third matrix by regrouping said second matrix so that it is conceived of as being composed of k (m)×

(m) matrices; and

(g) generating the combined matrix by applying a one-dimensional forward transform to said third matrix.

3. The method of claim 2, further comprising the steps of:

(h) selecting at least one common denominator q; and

(i) representing at least two terms in the combined matrix by integers whose ratios with the common denominator q are scaled approximations of the terms.

4. The method of claim 2, wherein the step (g) forward transform is a discrete cosine transform, and the step (e) inverse transform is a discrete cosine transform.

5. The method of claim 1, whereby the step of scaling the data by application of a combined matrix further comprises the step of the combined matrix operating to scale simultaneously in two-dimensions.

6. The method of claim 5, wherein generating the combined matrix for two-dimensional scaling comprises the steps of:

(a) selecting horizontal scaling parameters Fh, mh and gh;

(b) selecting vertical scaling factors Fv, mv, and gv;

(c) generating a first combined matrix for horizontal scaling using parameters Fh, mh, and gh;

(c) generating a first combined matrix for horizontal scaling using parameters Fh, mh, and gh;

(d) generating a second combined matrix which operates on said first combined matrix using parameters Fv, mv, and gv; and

(e) combining the first and second matrices into a single combined matrix.

7. The method of claim 6, further comprising the steps of:

(f) selecting at least one common denominator q; and

(g) representing at least two terms in the combined matrix by integers whose ratios with the common denominator q are scaled approximations of the at least two terms.

8. The method of claim 3, wherein the step (h) of selecting the common denominator q comprises choosing q according to a predetermined cost function.

9. The method of claim 8, wherein the predetermined cost function comprises the step of selecting the common denominator q so that the largest error on any transform coefficient is no larger than a predetermined error percentage.

10. The method of claim 1, wherein the combined matrix operates according to the following steps:

(b1) determining first and second precisions to be allocated in a single register to hold respective first and second signed data elements;

(b2) packing the elements into the register;

(b3) operating on the elements;

(b4) determining third and fourth precisions to be allocated in the single register to hold respective third and fourth signed data elements, at least one of the first and third precision being different from each other, and the second and fourth precisions being different from each other;

(b5) packing the third and fourth elements into the register; and

(b6) operating on the third and fourth elements;

wherein the register sends plural data elements simultaneously to at least one computational subsystem.

11. The method of claim 10, wherein the operating steps (b3) and (b6) are a multiplication by a constant or by a variable of known precision, or an addition, or a shift-left logical, or a subtraction, or a bitwise AND, or a bitwise OR.

12. The method of claim 2 wherein the scaling is a down-scaling operation;

the step (a) comprises selecting a rational scaling factor F between 0 and 1; and

the step (d) is the step (d1) zeroing out at least one row or at least one column of said matrix.

13. The method of claim 2 wherein the scaling is an up-scaling operation;

the step (a) comprises selecting a rational scaling factor F larger than 1; and

the step (d) is the step (d2) inserting at least one row of zeros or at least one column of zeros into said matrix.

14. The method of claim 2 wherein the matrix dimension value m is 8.

15. A data processing system for efficient scaling in the transform domain when transform coefficient data is provided as an input, comprising:

transform coefficient data; and

a combined matrix means for scaling data represented by the transform coefficient data in the transform domain by application of said means to said transform coefficient data.

16. The data processing system of claim 15 wherein the combined matrix is configured for one-dimensional scaling, further comprising:

(a) a rational scaling factor F;

(b) a matrix dimension value m; and

(c) g, the smallest integer wherein (Fg)/m is an integer k;

(d) a first matrix formed from at least one (mg)×

(m) matrix by;

(d1) zeroing out at least one row or at least one column of said matrix;

or

(d2) inserting at least one row of zeros or at least one column of zeros into said matrix;

(e) a second matrix formed by applying a one-dimensional inverse transform to the first matrix; and

(f) a third matrix formed by regrouping said second matrix so that it is conceived of as being composed of k (m)×

(m) matrices; and

(g) wherein the combined matrix is generated by applying a one-dimensional forward transform to said third matrix.

17. The data processing system of claim 16, further comprising:

(h) at least one common denominator q; and

(i) wherein at least two terms in the combined matrix are represented by integers whose ratios with the common denominator q are scaled approximations of the at least two terms.

18. The data processing system of claim 16 wherein the second matrix forward transform is a discrete cosine transform, and the combined matrix inverse transform is a discrete cosine transform.

19. The data processing system of claim 15, wherein by the combined matrix is configured to scale the data simultaneously in two-dimensions.

20. The data processing system of claim 19, wherein the combined matrix for two-dimensional scaling further comprises:

(a) horizontal scaling parameters Fh, mh and gh;

(b) vertical scaling factors Fv, mv, and gv;

(c) a first combined matrix for horizontal scaling generated from parameters Fh, mh, and gh;

(d) a second combined matrix generated from operating on said first combined matrix using parameters Fv, mv, and gv; and

(e) a single combined matrix generated by combining the first and second matrices.

21. The data processing system of claim 20, further comprising:

(f) at least one common denominator q; and

(g) wherein at least two terms in the combined matrix are represented by integers whose ratios with the common denominator q are scaled approximations of the at least two terms.

22. The data processing system of claim 15, further comprising a cost function means configured to select the scaling term g according to a predetermined cost function.

23. The data processing system of claim 22, wherein the predetermined cost function means comprises means for selecting the scaling term g so that the largest error on any transform coefficient is no larger than a predetermined error percentage.

24. The data processing system of claim 23, further comprising:

a single register; and

a computational subsystem;

wherein the first, second, third and fourth transform means are configured to;

(b1) determine first and second precisions to be allocated in the single register to hold respective first and second signed data elements;

(b2) pack first and second signed data the elements into the register;

(b3) operate on the first and second signed data elements;

(b4) determine third and fourth precisions to be allocated in the single register to hold respective third and fourth signed data elements, at least one of the first and third precision being different from each other, and the second and fourth precisions being different from each other;

(b5) pack the third and fourth elements into the register; and

(b6) operate on the third and fourth elements;

wherein the register sends plural data elements simultaneously to the at least one computational subsystem.

25. The data processing system of claim 24, wherein the first, second, third and fourth transform means are further configured to operate on the first, second, third and fourth elements by multiplication by a constant or by a variable of known precision, or by an addition, or by a shift-left logical, or by a subtraction, or by a bitwise AND, or by a bitwise OR.

26. The data processing system of claim 16 wherein the scaling is a down-scaling operation;

the rational scaling factor F has a value between 0 and 1; and

wherein the first matrix step is formed by zeroing out at least one row or at least one column of said (mg)×

(m) matrix.

27. The data processing system of claim 16 wherein the scaling is an up-scaling operation;

the rational scaling factor F has a value larger than 1; and

wherein the first matrix step is formed by inserting at least one row of zeros or at least one column of zeros into said (mg)×

(m) matrix.

28. The data processing system of claim 16 wherein the matrix dimension value m is 8.

29. An article of manufacture comprising a computer usable medium having a computer readable program embodied in said medium, wherein the computer readable program, when executed on a computer, causes the computer to scale data represented by transform coefficient data in the transform domain by application of a combined matrix to said transform coefficient data.

30. The article of manufacture of claim 29, wherein the computer readable program, when executed on a computer, causes the computer to generate a combined matrix for one-dimensional scaling, by:

(a) selecting a rational scaling factor F;

(b) selecting a matrix dimension value m; and

(c) selecting g as the smallest integer wherein (Fg)/m is an integer k;

(d) generating a first matrix operating on at least one (mg)×

(m) matrix by;

(d1) zeroing out at least one row or at least one column of said matrix;

or

(d2) inserting at least one row of zeros or at least one column of zeros into said matrix;

(e) generating a second matrix by applying a one-dimensional inverse transform to the first matrix; and

(f) generating a third matrix by regrouping said second matrix so that it is conceived of as being composed of k (m)×

(m) matrices; and

(g) generating the combined matrix by applying a one-dimensional forward transform to said third matrix.

31. The article of manufacture of claim 29, wherein the computer readable program, when executed on a computer, causes the computer to generate a combined matrix for two-dimensional scaling, by:

(a) selecting horizontal scaling parameters Fh, mh and gh;

(b) selecting vertical scaling factors Fv, mv, and gv;

(c) generating a first combined matrix for horizontal scaling using parameters Fh, mh, and gh;

(d) generating a second combined matrix which operates on said first combined matrix using parameters Fv, mv, and gv; and

(e) combining the first and second matrices into a single combined matrix.