A global method for invertible integer DCT and integer wavelet algorithms. (English) Zbl 1053.65103

The author presents a new global approach to derive integers transforms from given linear transforms. More specifically, for a given linear transform \( \hat{F}: \mathbb{R} ^{n}\longrightarrow \mathbb{R} ^{n}\) given by \(\hat{F}\left( x\right) =H_{n}X\), where \(H_{n}\in \mathbb{R} ^{n}\) is an invertible matrix, one can find an invertible integer transform \( F: \mathbb{Z} ^{n}\longrightarrow \mathbb{Z} ^{n}\) approximating \(\hat{F}\) by \(F\left( x\right) =\text{rd}\left( H_{n}X\right) \) if \(H_{n}\) satisfies this condition. Since \(H_{n}\) does not satisfy this condition, one can blow up the matrix \(H_{n}\) with a suitable expansion factor \(a_{n}>1\) such that \(a_{n}H_{n}\left( \left( -1/2,1/2\right] ^{n}\right) \) completely covers the unit cube \(\left[ -1/2,1/2\right) ^{n}\). An invertible mapping \(F: \mathbb{Z} ^{n}\longrightarrow \mathbb{Z} ^{n}\) can now simply be defined by \(F\left( x\right) =\text{rd}\left( a_{n}H_{n}X\right) \), and is very close to the exact (scaled) transform \( a_{n}H_{n}X\) since the error \(a_{n}H_{n}X-F\left( x\right) \) is at most 1/2 in each component. This idea is applied in order to derive a new integer discrete cosine transform (DCT)-II algorithm of radix-\(2\) length and new integer wavelet algorithms.


65T50 Numerical methods for discrete and fast Fourier transforms
65G50 Roundoff error
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
65T60 Numerical methods for wavelets


Full Text: DOI


[1] M.D. Adams, Reversible integer-to-integer wavelet transforms for image coding, PhD thesis, Department of Electrical and Computer Engineering, The University of British Columbia, 2002
[2] Adams, M.D.; Kossentini, F., Reversible integer-to-integer wavelet transforms for image compression: performance evaluation and analysis, IEEE trans. image process., 9, 6, 1010-1024, (2000) · Zbl 0962.94023
[3] Brislawn, C., Classification of nonexpansive symmetric extension transforms for multirate filter banks, Appl. comput. harmon. anal., 3, 337-357, (1996) · Zbl 0874.94006
[4] Calderbank, A.R.; Daubechies, I.; Sweldens, W.; Yeo, B.L., Wavelet transforms that map integers to integers, Appl. comput. harmon. anal., 5, 332-369, (1998) · Zbl 0941.42017
[5] Cham, W.K.; Yip, P.C., Integer sinusoidal transforms for image processing, Int. J. electron., 70, 1015-1030, (1991)
[6] Chao, H.; Fisher, P.; Hua, Z., An approach to integer wavelet transformations for lossless image compression, Lecture notes pure appl. math., 202, 19-38, (1998) · Zbl 0931.65146
[7] Y.-J. Chen, S. Oraintara, T.Q. Nguyen, Integer discrete cosine transform (IntDCT), Preprint, 2000
[8] Cheng, L.Z.; Xu, H.; Luo, Y., Integer discrete cosine transform and its fast algorithm, Electron. lett., 37, 64-65, (2001)
[9] Daubechies, I., Ten lectures on wavelets, (1992), SIAM Philadelphia · Zbl 0776.42018
[10] Daubechies, I.; Sweldens, W., Factoring wavelet transforms into lifting steps, J. Fourier anal. appl., 4, 247-269, (1998) · Zbl 0913.42027
[11] Dewitte, S.; Cornelis, J., Lossless integer wavelet transform, IEEE signal process. lett., 4, 6, 158-160, (1997)
[12] Hao, P.; Shi, Q., Matrix factorizations for reversible integer mapping, IEEE trans. signal process., 49, 10, 2314-2324, (2001) · Zbl 1369.94025
[13] J.J. Hong, Discrete Fourier, Hartley and cosine transforms in signal processing, PhD thesis, Columbia University, 1994
[14] Jung, H.Y.; Prost, R., Lossless subband coding system based on rounding transform, IEEE trans. signal process., 46, 6, 2535-2540, (1998)
[15] Kim, H.; Li, C.C., Lossless and lossy image compression using biorthogonal wavelet transforms with multiplierless operations, IEEE trans. circuits systems II, 45, 8, 1113-1118, (1998) · Zbl 0998.94508
[16] Komatsu, K.; Sezaki, K., Reversible discrete cosine transform, Proc. IEEE ICASSP98, 1769-1772, (1998)
[17] M. Lange, Von Wavelets abgeleitete Algorithmen zur Transformation auf ganzen Zahlen, Diplomarbeit, Institute of Mathematics, University of Duisburg-Essen, 2003
[18] Li, X.; Tao, B.; Orchard, M.T., On implementing transforms from integers to integers, (), 881-885
[19] Liang, J.; Tran, T.D., Fast multiplierless approximations of the DCT: the lifting scheme, IEEE trans. signal process., 49, 3032-3044, (2001)
[20] Loeffler, C.; Lightenberg, A.; Moschytz, G., Practical fast 1-D DCT algorithms with 11 multiplications, (), 988-991
[21] Oraintara, S.; Chen, Y.J.; Nguyen, T.Q., Integer fast Fourier transform, IEEE trans. signal process., 50, 3, 607-618, (2002) · Zbl 1369.65189
[22] Philips, W., Lossless DCT for combined lossy/lossless image coding, (), 871-875
[23] G. Plonka, M. Tasche, Split – radix algorithms for discrete trigonometric transforms, Preprint, Gerhard-Mercator-Univ. Duisburg, 2002
[24] Plonka, G.; Tasche, M., Invertible integer DCT algorithms, Appl. comput. harmon. anal., 15, 70-88, (2003) · Zbl 1030.65144
[25] Plonka, G.; Tasche, M., Integer DCT-II by lifting steps, (), 235-252 · Zbl 1036.65118
[26] M. Primbs, Integer DCT Algorithmen, Diplomarbeit, Institute of Mathematics, University of Duisburg-Essen, 2003
[27] Rabbani, M.; Jones, P.W., Digital image compression techniques, (1991), SPIE Bellingham, WA
[28] Said, A.; Pearlman, W.A., An image multiresolution representation for lossless and lossy compression, IEEE trans. image process., 5, 9, 1303-1310, (1996)
[29] Sweldens, W., The lifting scheme: A custom-design construction of biorthogonal wavelets, Appl. comput. harmon. anal., 3, 186-200, (1996) · Zbl 0874.65104
[30] Strang, G.; Nguyen, T., Wavelets and filter banks, (1996), Wellesley/Cambridge Press Wellesley, MA · Zbl 1254.94002
[31] Tran, T.D., The bindct: fast multiplierless approximation of the DCT, IEEE signal process. lett., 7, 141-144, (2000)
[32] Van Loan, C.F., Computational framework for the fast Fourier transform, (1992), SIAM Philadelphia · Zbl 0757.65154
[33] Zeng, Y.; Cheng, L.; Bi, G.; Kot, A.C., Integer DCTs and fast algorithms, IEEE trans. signal process., 49, 2774-2782, (2001) · Zbl 1369.65195
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.