×
Calderbank, A. R.; Daubechies, Ingrid; Sweldens, Wim; Yeo, Boon-Lock

Wavelet transforms that map integers to integers. (English) Zbl 0941.42017

Appl. Comput. Harmon. Anal. 5, No. 3, 332-369 (1998).
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)].
Reviewer: A.Bultheel (Leuven)

Cited in 1 Review
Cited in 33 Documents

MSC:

42C40 Nontrigonometric harmonic analysis involving wavelets and other special systems
68U10 Computing methodologies for image processing

Keywords:

wavelet transform; precoding; lifting scheme; lossless image coding
Cite Review PDF
Full Text: DOI Link

References:

[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: 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
[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. Ten Lectures on Wavelets, CBMS-NSF Regional Conf. Series in Appl. Math., 61 (1992), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia · Zbl 0776.42018
[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
[12] Donoho, D. L., Smooth wavelet decompositions with blocky coefficient kernels, (Schumaker, L. L.; Webb, G., Recent Advances in Wavelet Analysis (1993), Academic Press: Academic Press New York), 259-308 · Zbl 0813.42020
[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: 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: SPIE Bellingham), 307-316
[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: 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
[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: 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: 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: 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: 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: Prentice Hall Englewood Cliffs · Zbl 0885.94002
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.