## 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.

### MSC:

 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

binDCT
Full Text:

### References:

  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  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  Brislawn, C., Classification of nonexpansive symmetric extension transforms for multirate filter banks, Appl. comput. harmon. anal., 3, 337-357, (1996) · Zbl 0874.94006  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  Cham, W.K.; Yip, P.C., Integer sinusoidal transforms for image processing, Int. J. electron., 70, 1015-1030, (1991)  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  Y.-J. Chen, S. Oraintara, T.Q. Nguyen, Integer discrete cosine transform (IntDCT), Preprint, 2000  Cheng, L.Z.; Xu, H.; Luo, Y., Integer discrete cosine transform and its fast algorithm, Electron. lett., 37, 64-65, (2001)  Daubechies, I., Ten lectures on wavelets, (1992), SIAM Philadelphia · Zbl 0776.42018  Daubechies, I.; Sweldens, W., Factoring wavelet transforms into lifting steps, J. Fourier anal. appl., 4, 247-269, (1998) · Zbl 0913.42027  Dewitte, S.; Cornelis, J., Lossless integer wavelet transform, IEEE signal process. lett., 4, 6, 158-160, (1997)  Hao, P.; Shi, Q., Matrix factorizations for reversible integer mapping, IEEE trans. signal process., 49, 10, 2314-2324, (2001) · Zbl 1369.94025  J.J. Hong, Discrete Fourier, Hartley and cosine transforms in signal processing, PhD thesis, Columbia University, 1994  Jung, H.Y.; Prost, R., Lossless subband coding system based on rounding transform, IEEE trans. signal process., 46, 6, 2535-2540, (1998)  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  Komatsu, K.; Sezaki, K., Reversible discrete cosine transform, Proc. IEEE ICASSP98, 1769-1772, (1998)  M. Lange, Von Wavelets abgeleitete Algorithmen zur Transformation auf ganzen Zahlen, Diplomarbeit, Institute of Mathematics, University of Duisburg-Essen, 2003  Li, X.; Tao, B.; Orchard, M.T., On implementing transforms from integers to integers, (), 881-885  Liang, J.; Tran, T.D., Fast multiplierless approximations of the DCT: the lifting scheme, IEEE trans. signal process., 49, 3032-3044, (2001)  Loeffler, C.; Lightenberg, A.; Moschytz, G., Practical fast 1-D DCT algorithms with 11 multiplications, (), 988-991  Oraintara, S.; Chen, Y.J.; Nguyen, T.Q., Integer fast Fourier transform, IEEE trans. signal process., 50, 3, 607-618, (2002) · Zbl 1369.65189  Philips, W., Lossless DCT for combined lossy/lossless image coding, (), 871-875  G. Plonka, M. Tasche, Split – radix algorithms for discrete trigonometric transforms, Preprint, Gerhard-Mercator-Univ. Duisburg, 2002  Plonka, G.; Tasche, M., Invertible integer DCT algorithms, Appl. comput. harmon. anal., 15, 70-88, (2003) · Zbl 1030.65144  Plonka, G.; Tasche, M., Integer DCT-II by lifting steps, (), 235-252 · Zbl 1036.65118  M. Primbs, Integer DCT Algorithmen, Diplomarbeit, Institute of Mathematics, University of Duisburg-Essen, 2003  Rabbani, M.; Jones, P.W., Digital image compression techniques, (1991), SPIE Bellingham, WA  Said, A.; Pearlman, W.A., An image multiresolution representation for lossless and lossy compression, IEEE trans. image process., 5, 9, 1303-1310, (1996)  Sweldens, W., The lifting scheme: A custom-design construction of biorthogonal wavelets, Appl. comput. harmon. anal., 3, 186-200, (1996) · Zbl 0874.65104  Strang, G.; Nguyen, T., Wavelets and filter banks, (1996), Wellesley/Cambridge Press Wellesley, MA · Zbl 1254.94002  Tran, T.D., The bindct: fast multiplierless approximation of the DCT, IEEE signal process. lett., 7, 141-144, (2000)  Van Loan, C.F., Computational framework for the fast Fourier transform, (1992), SIAM Philadelphia · Zbl 0757.65154  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.