Methods for calculating video inverse transform
Inverse transforms used in video and image compression/decompression, such as DCT/IDCT used in MPEG-2 and MPEG-4, or the integer transforms used in H.264, are usually calculated with fast algorithms, which only take advantage of the symmetry existing in the transform matrix but ignores the peculiarities in the input data. While these kind of fast algorithms can apply to both forward and inverse transforms, they tend to be inefficient in calculating inverse transforms. In inverse transforms, most of the coefficients become zero after quantization, this invention takes advantage of this fact to further simplify the general fast algorithm and speed up the calculation.
1. A method for calculating an inverse transform of input data, wherein said input data having a plurality of coefficients, comprising the steps of:
determining a plurality of computation modes;
representing said computation modes by a plurality of representative computation modes as a function of the non-zero coefficients of the input data;
selecting one of the representative computation modes as a function of the input data;
inverse transforming the input data using said selected representative computation mode; wherein said representative computation modes are a reduced set of said computation modes; and wherein said representing step is performed as a function of zi=(˜xi+yi), where ˜xi means the logical negation of xi and the “+” sign means the logical OR operation, where a computation mode x is mapped to a representative computation mode y if at every bit location zi is true.
2. The method of claim 1 wherein in determining the plurality of computation modes, each of the coefficients of the input data are converted into a single binary value wherein non-zero-valued coefficients are converted to “1” and zero-valued coefficients are converted to “0”.
3. The method of claim 2 wherein said input data is determined into a particular computation mode as a function of the zero or non-zero binary value of the coefficients.
4. The method of claim 1 wherein a computation mode x is mapped to a single representative computation mode y, if a computation mode x can be mapped to more than one computation mode y.
5. The method of claim 1 wherein in said representing step, one or more frequently occurring modes are selected as representative computation modes by using statistical analysis.
6. The method of claim 5 wherein a number of frequently occurring modes as representative computation modes is determined based upon the number of trailing zeros in the coefficients in the input data.
7. The method of claim 5 wherein a number of frequently occurring modes as representative computation modes is determined based upon decimating the coefficients into multiple frequency groups.
8. The method of claim 5 wherein in said selecting step, the representative computation mode used to calculate the inverse transform is selected as a function of a respective computational cost.
9. The method of claim 1 wherein in said representing step, one or more frequently occurring modes are selected as representative computation modes based upon the number of trailing zeros in the coefficients in the input data.
10. The method of claim 1 wherein in said representing step, one or more frequently occurring modes are selected as representative computation modes based upon decimating the coefficients into multiple frequency groups.
11. The method of claim 1 wherein in said selecting step, the representative computation mode used to calculate the inverse transform is selected as a function of a respective computational cost.
12. A method for calculating an inverse transform of input data, wherein said input data having a plurality of coefficients, comprising the steps of: determining a plurality of computation modes, wherein each of the coefficients of the input data are converted into a single binary value wherein non-zero-valued coefficients are converted to “1” and zero-valued coefficients are converted to “0”; selecting one or more frequently occurring modes; representing said computation modes by a plurality of representative computation modes wherein zi=(˜xi+yi), where ˜xi means the logical negation of xi and the “+” sign means the logical OR operation, where a computation mode x is mapped to a representative computation mode y if at every bit location zi is true, and wherein said one or more frequently occurring modes are selected as one or more representative computation modes; selecting one of the representative computation modes as a function of the input data and as a function of the respective computational cost for the representative computation modes; and inverse transforming the input data using said selected representative computation mode.
13. The method of claim 12 wherein in said selecting frequently occurring modes step, one or more frequently occurring modes are selected by using statistical analysis.
14. The method of claim 12 wherein in said selecting frequently occurring modes step, one or more frequently occurring modes are selected based upon the number of trailing zeros in the coefficients in the input data.
15. The method of claim 12 wherein in said selecting frequently occurring modes step, one or more frequently occurring modes are selected based upon decimating the coefficients into multiple frequency groups.
16. The method of claim 12 wherein said representative computation modes are a reduced set of said computation modes.
17. A method for calculating an inverse transform of input data, wherein said input data having a plurality of coefficients, comprising the steps of: determining a plurality of computation modes, wherein each of the coefficients of the input data are converted into a single binary value wherein non-zero-valued coefficients are converted to “1” and zero-valued coefficients are converted to “0”; selecting frequently occurring modes; representing said computation modes by a plurality of representative computation modes as a function of the non-zero coefficients of the input data wherein zi=(˜xi+yi), where ˜xi means the logical negation of xi and the “+” sign means the logical OR operation, where a computation mode x is mapped to a representative computation mode y if at every bit location zi is true, wherein said representative computation modes are a reduced set of said computation modes, and wherein said one or more frequently occurring modes are selected as representative computation modes; selecting one of the representative computation modes as a function of zero or non-zero coefficients of the input data and as a function of the respective computational cost for the representative computation modes; and inverse transforming the input data using said selected representative computation mode.
18. The method of claim 16 wherein a number of frequently occurring modes is determined by using statistical analysis, based upon the number of trailing zeros in the coefficients in the input data, or based upon decimating the coefficients into multiple frequency groups.