×

zbMATH — the first resource for mathematics

Wavelet transforms that map integers to integers. (English) Zbl 0941.42017
The wavelet transforms described in this paper do not use integer arithmetic, but the floating point filtering operations are arranged in such a way that they map integer data to integer wavelet transforms and they are still invertible. Two approaches to solve the problem are described. The first is an adaptation of the precoder of Laroia, Tretter, and Farvardin, used in information transmission. The non-integers appear in the Haar transform because of a division by 2. These factors can be removed by using expansion coefficients for the filters. A more complicated but similar idea is used for more general wavelet filters. The result of the analysis is that expansion coefficients are used for high and low-pass filters and that the integer data are changed to compensate for the non-integer mapping of the filters, so that the result is again integer. A second approach is conceptually much simpler and is based on the lifting scheme for wavelet transforms. The decomposition into lifting steps allows for an easy and lossless inversion, even if the lifting steps are rounded to integers. The two approaches are essentially different and need not lead to the same algorithms. Several examples are given and they are applied to a set of test images to be compared with other transforms and coding methods given in the literature. Similar results were obtained in [S. Dewitte and J. Cornelis, IEEE Signal Proc. Lett. 4, No. 6, 158-160 (1997)] and [H. Chao, P. Fisher and Z. Hua, Lect. Notes Pure Appl. Math. 202, 19-38 (1998)]. For a software implementation, see for example [G. Uytterhoeven et al., “WAILI: A software library for image processing using integer wavelet transforms”, In ‘Medical Imaging 1998: Image Processing’, K. M. Hanson (ed.), SPIE Proceedings, Vol. 3338, International Society for Optical Engineering, 1490-1501 (1998)].

MSC:
42C40 Nontrigonometric harmonic analysis involving wavelets and other special systems
68U10 Computing methodologies for image processing
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Call for contributions—Lossless compression of continuous-tone still pictures, March 1994.
[2] Brislawn, C. M.; Bradley, J. N.; Onyshczak, R. J.; Hopper, T., The FBI compression standard for digitized fingerprint images, Applications of Digital Image Processing XIX, (1996), SPIE Bellingham
[3] Bruekens, A. A.M. L.; van den Enden, A. W.M., New networks for perfect inversion and perfect reconstruction, IEEE J. Selected Areas Comm., 10, (1992)
[4] Carnicer, J. M.; Dahmen, W.; Peña, J. M., Local decompositions of refinable spaces, Appl. Comput. Harmon. Anal., 3, 127-153, (1996) · Zbl 0859.42025
[5] H. Chao, P. Fisher, An approach of fast integer reversible wavelet transform for image compression, Infinop, Deaton, TX, 76208, 1996
[6] Cohen, A.; Daubechies, I.; Feauveau, J., Bi-orthogonal bases of compactly supported wavelets, Comm. Pure Appl. Math., 45, 485-560, (1992) · Zbl 0776.42020
[7] Dahmen, W.; Micchelli, C. A., Banded matrices with banded inverses. II. locally finite decompositions of spline spaces, Constr. Approx., 9, 263-281, (1993) · Zbl 0784.15005
[8] Daubechies, I., Ten Lectures on Wavelets, CBMS-NSF Regional Conf. Series in Appl. Math., 61, (1992), Society for Industrial and Applied Mathematics Philadelphia
[9] I. Daubechies, W. Sweldens, Factoring Wavelet and Subband Transforms into Lifting Steps, Bell Laboratories, Lucent Technologies, 1996 · Zbl 0963.65154
[10] DeVore, R. A.; Jawerth, B.; Lucier, B. J., Image compression through wavelet transform coding, IEEE Trans. Inform. Theory, 38, 719-746, (1992) · Zbl 0754.68118
[11] S. Dewitte, J. Cornelis, Lossless Integer Wavelet Transform, Royal Meteorological Institute Belgium, 1996
[12] Donoho, D. L., Smooth wavelet decompositions with blocky coefficient kernels, (Schumaker, L. L.; Webb, G., Recent Advances in Wavelet Analysis, (1993), Academic Press New York), 259-308 · Zbl 0813.42020
[13] D. L. Donoho, Interpolating wavelet transforms, Department of Statistics, Stanford University, 1992
[14] J. Gros, Binary friendly wavelets, Department of Electrical Engineering and Computer Sciences, UC Berkeley, 1995
[15] Harten, A., Multiresolution representation of data: A general framework, SIAM J. Numer. Anal., 33, 1205-1256, (1996) · Zbl 0861.65130
[16] Heer, V. K.; Reinfelder, H.-E., A comparison of reversible methods for data compression, Medical Imaging IV, (1990), SPIE Bellingham, p. 354-365
[17] Hong, J., Discrete Fourier, Hartley and Cosine Transforms in Signal Processing, (1993), Columbia UniversityDepartment of Electrical Engineering
[18] Johnston, C. P., The lifting scheme and finite-precision-error-free filter banks, (Unser, M.; Aldroubi, A.; Laine, A. F., Wavelet Applications in Signal and Image Processing IV, (1996), SPIE Bellingham), 307-316
[19] A. A. C. Kalker, I. A. Shah, On ladder structures and linear phase conditions for multidimensional biorthogonal filter banks, Philips research laboratories, Eindhoven
[20] Kalker, A. A.C.; Shah, I. A., Ladder structures for multidimensional linear phase perfect reconstruction filter banks and wavelets, Visual Communications, Boston, (1992), SPIE Bellingham, p. 711-722
[21] Kim, C. W.; Ansari, R.; Cetin, A. E., A class of linear-phase regular biorthogonal wavelets, Proc. IEEE Int. Conference on Acoustics, Speech, Signal Processing, (1992), p. 673-676
[22] Laroia, R.; Tretter, S. A.; Farvardin, N., A simple and effective precoding scheme for noise whitening on intersymbol interference channels, IEEE Trans. Comm., 41, 460-463, (1993) · Zbl 0800.94168
[23] M. Lounsbery, T. D. DeRose, J. Warren, Multiresolution surfaces of arbitrary topological type, Jan. 1994
[24] Memon, N.; Sippy, V.; Wu, X., A comparison of prediction schemes proposed for a new lossless image compression standard, IEEE International Symposium on Circuits and Systems, (May 1995), p. 309-312
[25] Rabbini, M.; Jones, P. W., Digital Image Compression Techniques, (1991), SPIE Bellingham
[26] Said, A.; Pearlman, W. A., An image multiresolution representation for lossless and lossy image compression, IEEE Trans. Image Process, 5, 1303-1310, (1996)
[27] Schröder, P.; Sweldens, W., Spherical wavelets: efficiently representing functions on the sphere, Computer Graphics Proceedings (SIGGRAPH 95), (1995), p. 161-172
[28] Schumaker, L. L.; Webb, G., Recent Advances in Wavelet Analysis, (1993), Academic Press New York · Zbl 0782.00090
[29] Shapiro, J. M., Embedded image coding using zerotrees of wavelet coefficients, IEEE Trans. Signal Process., 41, 3445-3462, (1993) · Zbl 0841.94020
[30] Strang, G.; Nguyen, T., Wavelets and Filter Banks, (1996), Wellesley Cambridge · Zbl 1254.94002
[31] Swanson, M. D.; Tewfix, A. H., A binary wavelet decomposition of binary images, IEEE Trans. Image Process., 5, 1637-1650, (1996)
[32] Sweldens, W., The lifting scheme: A construction of second generation wavelets, SIAM J. Math. Anal., 29, 511-546, (1997) · Zbl 0911.42016
[33] Sweldens, W., The lifting scheme: A custom-design construction of biorthogonal wavelets, Appl. Comput. Harmon. Anal., 3, 186-200, (1996) · Zbl 0874.65104
[34] Tolhuizen, L. M.G. M.; Shah, I. A.; Kalker, A. A.C., On constructing regular filter banks from domain bounded polynomials, IEEE Trans. Signal Process., 42, 451-456, (1994)
[35] Vaidyanathan, P. P., Multirate Systems and Filter Banks, (1992), Prentice Hall Englewood Cliffs · Zbl 0784.93096
[36] Vaidyanathan, P. P.; Hoang, P.-Q., Lattice structures for optimal design and robust implementation of two-band perfect reconstruction QMF banks, IEEE Trans. Acoust. Speech Signal Process., 36, 81-94, (1988)
[37] Vetterli, M.; Herley, C., Wavelets and filter banks: theory and design, IEEE Trans. Acoust. Speech Signal Process., 40, 2207-2232, (1992) · Zbl 0825.94059
[38] Vetterli, M.; Kovačević, J., Wavelets and Subband Coding, (1995), Prentice Hall Englewood Cliffs · Zbl 0885.94002
[39] A. Zandi, M. Boliek, E. L. Schwartz, M. J. Gormish, CREW Lossless/Lossy Medical Image Compression, RICOH California Research Center, 1995
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.