Factoring wavelet transforms into lifting steps. (English) Zbl 0913.42027

Daubechies, Ingrid; Sweldens, Wim

J. Fourier Anal. Appl. 4, No. 3, 247-269 (1998).

Given a signal \((x_k)_{k \in Z}\), we may split it into even \(x_e = (x_{2k})\) and odd \(x_o = (x_{2k+1})\) components. A lifting step is defined to be a transformation of the form \(x \mapsto (x_o, x_e - P(x_o))\), where \(P(x_o)\) is a linear predictor for the even component based on the odd component. (For instance, one could take \(P(x_o)_{2k} = (x_{2k-1} + x_{2k+1})/2\)). A dual lifting step is a transformation of the form \((x_o,d) \mapsto (x_o + U(d), d)\), where \(U(d)\) is an update operator to the odd components based upon the detail \(d = x_e - P(x_o)\). (For instance, one can take \(U(d)_{2k} = (d_{2k-1} + d_{2k+1})/4)\). In this paper the authors show that any finite impulse response (FIR) filter bank or wavelet transform can be factored into a sequence of lifting steps and dual lifting steps, each of which is also given by an FIR filter. The method of proof relies upon the z-transform and then a factorization of a Laurent polynomial-valued matrix into elementary matrices by means of the Euclidean algorithm.

Reviewer: Terence Tao (Los Angeles)

MSC:

42C40

Nontrigonometric harmonic analysis involving wavelets and other special systems

Keywords:

wavelet transforms; lifting; elementary matrix; finite impulse response filter bank; FIR filter

References:

[1]	Aldroubi, A. and Unser, M. (1993). Families of multiresolution and wavelet spaces with optimal properties.Numer. Funct. Anal. Optim.,14, 417–446. · Zbl 0798.94007 · doi:10.1080/01630569308816532
[2]	Bass, H. (1968).Algebraic K-Theory, W. A. Benjamin, New York. · Zbl 0174.30302
[3]	Bellanger, M.G. and Daguet, J.L. (1974). TDM-FDM transmultiplexer: Digital polyphase and FFT.IEEE Trans. Commun.,22(9), 1199–1204. · doi:10.1109/TCOM.1974.1092391
[4]	Blahut, R.E. (1984).Fast Algorithms for Digital Signal Processing. Addison-Wesley, Reading, MA. · Zbl 0579.94001
[5]	Bruekens, A.A.M.L. and van den Enden, A.W.M. (1992). New networks for perfect inversion and perfect reconstruction.IEEE J. Selected Areas Commun.,10(1).
[6]	Calderbank, R., Daubechies, I., Sweldens, W., and Yeo, B.-L. Wavelet transforms that map integers to integers.Appl. Comput. Harmon. Anal., (to appear). · Zbl 0941.42017
[7]	Carnicer, J.M., Dahmen, W., and Peña, J.M. (1996). Local decompositions of refinable spaces.Appl. Comput. Harmon. Anal.,3, 127–153. · Zbl 0859.42025 · doi:10.1006/acha.1996.0012
[8]	Chui, C.K. (1992).An Introduction to Wavelets. Academic Press, San Diego, CA. · Zbl 0925.42016
[9]	Chui, C.K., Montefusco, L., and Puccio, L., Eds. (1994).Conference on Wavelets: Theory, Algorithms, and Applications. Academic Press, San Diego, CA. · Zbl 0816.00025
[10]	Chui, C.K. and Wang, J.Z. (1991). A cardinal spline approach to wavelets.Proc. Amer. Math. Soc.,113, 785–793. · Zbl 0755.41008 · doi:10.1090/S0002-9939-1991-1077784-X
[11]	Chui, C.K. and Wang, J.Z. (1992). A general framework of compactly supported splines and wavelets.J. Approx. Theory,71(3), 263–304. · Zbl 0774.41013 · doi:10.1016/0021-9045(92)90120-D
[12]	Cohen, A., Daubechies, I., and Feauveau, J. (1992). Bi-orthogonal bases of compactly supported wavelets.Comm. Pure Appl. Math.,45, 485–560. · Zbl 0776.42020 · doi:10.1002/cpa.3160450502
[13]	Combes, J.M., Grossmann, A., and Tchamitchian, Ph. Eds. (1989).Wavelets: Time-Frequency Methods and Phase Space. Inverse problems and Theoretical Imaging. Springer-Verlag, New York. · Zbl 0718.00009
[14]	Dahmen, W. and Micchelli, C.A. (1993). Banded matrices with banded inverses II: Locally finite decompositions of spline spaces.Constr. Approx.,9(2–3), 263–281. · Zbl 0784.15005 · doi:10.1007/BF01198006
[15]	Dahmen, W., Prössdorf, S., and Schneider, R. (1994). Multiscale methods for pseudo-differential equations on smooth manifolds. In [9], 385–424. · Zbl 0847.65081
[16]	Daubechies, I. (1988). Orthonormal bases of compactly supported wavelets.Comm. Pure Appl. Math.,41, 909–996. · Zbl 0644.42026 · doi:10.1002/cpa.3160410705
[17]	Daubechies, I. (1992).Ten Lectures on Wavelet. CBMS-NSF Regional Conf. Series in Appl. Math., vol. 61. Society for Industrial and Applied Mathematics, Philadelphia, PA.
[18]	Daubechies, I., Grossmann, A., and Meyer, Y. (1986). Painless nonorthogonal expansions.J. Math. Phys.,27(5), 1271–1283. · Zbl 0608.46014 · doi:10.1063/1.527388
[19]	Donoho, D.L. (1992). Interpolating wavelet transforms. Preprint, Department of Statistics, Stanford University.
[20]	Van Dyck, R.E., Marshall, T.G., Chine, M. and Moayeri, N. (1996). Wavelet video coding with ladder structures and entropy-constrained quantization.IEEE Trans. Circuits Systems Video Tech.,6(5), 483–495. · doi:10.1109/76.538930
[21]	Frazier, M. and Jawerth, B. (1985). Decomposition of Besov spaces.Indiana Univ. Math. J.,34 (4), 777–799. · Zbl 0551.46018 · doi:10.1512/iumj.1985.34.34041
[22]	Grossmann, A. and Morlet, J. (1984). Decomposition of Hardy functions into square integrable wavelets of constant shape.SIAM J. Math. Anal.,15(4), 723–736. · Zbl 0578.42007 · doi:10.1137/0515056
[23]	Harten, A. (1996). Multiresolution representation of data: A general framework.SIAM J. Numer. Anal.,33 (3), 1205–1256. · Zbl 0861.65130 · doi:10.1137/0733060
[24]	Hartley, B. and Hawkes, T.O. (1983).Rings, Modules and Linear Algebra. Chapman and Hall, New York. · Zbl 0527.20001
[25]	Herley, C. and Vetterli, M. (1993). Wavelets and recursive filter banks.IEEE Trans. Signal Process.,41(8), 2536–2556. · Zbl 0825.93871 · doi:10.1109/78.229887
[26]	Jain, A.K. (1989).Fundamentals of Digital Image Processing. Prentice Hall, Englewood Cliffs, NJ. · Zbl 0744.68134
[27]	Jayanat, N.S. and Noll, P. (1984).Digital Coding of Waveforms. Prentice Hall, Englewood Cliffs, NJ.
[28]	Kalker, T.A.C.M. and Shah, I. (1992). Ladder Structures for multidimensional linear phase perfect reconstruction filter banks and wavelets. InProceedings of the SPIE Conference on Visual Communications and Image Processing (Boston), 12–20.
[29]	Lounsbery, M., DeRose, T.D., and Warren, J. (1997). Multiresolution surfaces of arbitrary topological type.ACM Trans. on Graphics,16(1), 34–73. · doi:10.1145/237748.237750
[30]	Mallat, S.G. (1989). Multifrequency channel decompositions of images and wavelet models.IEEE Trans. Acoust. Speech Signal Process.,37(12), 2091–2110. · doi:10.1109/29.45554
[31]	Mallat, S.G. (1989). Multiresolution approximations and wavelet orthonormal bases of L2 (R).Trans. Amer. Math. Soc.,315(1), 69–87. · Zbl 0686.42018
[32]	Marshall, T.G. (1993). A fast wavelet transform based upon the Euclidean algorithm. InConference on Information Science and Systems, Johns Hopkins, Maryland.
[33]	Marshall, T.G. (1993). U-L block-triangular matrix and ladder realizations of subband coders. InProc. IEEE ICASSP, III: 177–180.
[34]	Meyer, Y. (1990).Ondelettes et Opérateurs, I:Ondelettes, II:Opérateurs de Calderón-Zygmund, III: (with R. Coifman),Opérateurs multilinéaires. Hermann, Paris. English translation of first volume,Wavelets and Operators, is published by Cambridge University Press, 1993.
[35]	Mintzer, F. (1985). Filters for distortion-free two-band multirate filter banks.IEEE Trans. Acoust. Speech Signal Process.,33, 626–630. · doi:10.1109/TASSP.1985.1164587
[36]	Nguyen, T.Q. and Vaidyanathan, P.P. (1989). Two-channel perfect-reconstruction FIR QMF structures which yield linear-phase analysis and synthesis filters.IEEE Trans. Acoust. Speech Signal Process.,37, 676–690. · doi:10.1109/29.17560
[37]	Park, H.-J..A computational theory of Laurent polynomial rings and multidimensional FIR systems. PhD thesis, University of California, Berkeley, May 1995.
[38]	Reissell, L.-M. (1996). Wavelet multiresolution representation of curves and surfaces.CVGIP: Graphical Models and Image Processing,58(2), 198–217. · doi:10.1006/gmip.1996.0017
[39]	Rioul, O. and Duhamel, P. (1992). Fast algorithms for discrete and continuous wavelet transforms.IEEE Trans. Inform. Theory,38(2), 569–586. · Zbl 0745.65086 · doi:10.1109/18.119724
[40]	Schröder, P. and Sweldens, W. (1995). Spherical wavelets: Efficiently representing functions on the sphere.Computer Graphics Proceedings, (SIGGRAPH 95), 161–172. · Zbl 0970.42024
[41]	Shah, I. and Kalker, T.A.C.M. (1994). On Ladder Structures and Linear Phase Conditions for Bi-Orthogonal Filter Banks. InProceedings of ICASSP-94,3, 181–184.
[42]	Smith, M.J.T. and Barnwell, T.P. (1986). Exact reconstruction techniques for tree-structured subband coders.IEEE Trans. Acoust. Speech Signal Process.,34(3), 434–441. · doi:10.1109/TASSP.1986.1164832
[43]	Strang, G. and Nguyen, T. (1996).Wavelets and Filter Banks. Wellesley, Cambridge, MA. · Zbl 1254.94002
[44]	Sweldens, W. (1996). The lifting scheme: A custom-design construction of biorthogonal wavelets.Appl. Comput. Harmon. Anal.,3(2), 186–200. · Zbl 0874.65104 · doi:10.1006/acha.1996.0015
[45]	Sweldens, W. (1997). The lifting scheme: A construction of second generation wavelets.SIAM J. Math. Anal.,29(2), 511–546. · Zbl 0911.42016 · doi:10.1137/S0036141095289051
[46]	Sweldens, W. and Schröder, P. (1996). Building your own wavelets at home. InWavelets in Computer Graphics, 15–87. ACM SIGGRAPH Course notes.
[47]	Tian, J. and Wells, R.O. (1996). Vanishing moments and biorthogonal wavelets systems. InMathematics in Signal Processing IV. Institute of Mathematics and Its Applications Conference Series, Oxford University Press.
[48]	Tolhuizen, L.M.G., Hollmann, H.D.L., and Kalker, T.A.C.M. (1995). On the realizability of bi-orthogonal M-dimensional 2-band filter banks.IEEE Trans. Signal Process.
[49]	Unser, M., Aldroubi, A., and Eden, M. (1993). A family of polynomial spline wavelet transforms.Signal Process.,30, 141–162. · Zbl 0768.41012 · doi:10.1016/0165-1684(93)90144-Y
[50]	Vaidyanathan, P.P. (1987). Theory and design of M-channel maximally decimated quadrature mirror filters with arbitrary M, having perfect reconstruction property.IEEE Trans. Acoust. Speech Signal Process.,35(2), 476–492. · Zbl 0641.94002 · doi:10.1109/TASSP.1987.1165155
[51]	Vaidyanathan, P.P. and Hoang, P.-Q. (1988). Lattice structures for optimal design and robust implementation of two-band perfect reconstruction QMF banks.IEEE Trans. Acoust. Speech Signal Process.,36, 81–94. · doi:10.1109/29.1491
[52]	Vaidyanathan, P.P., Nguyen, T.Q., Doĝanata, Z., and Saramäki, T. (1989). Improved technique for design of perfect reconstruction FIR QMF banks with lossless polyphase matrices.IEEE Trans. Acoust. Speech Signal Process.,37(7), 1042–1055. · doi:10.1109/29.32282
[53]	Vetterli, M. (1986). Filter banks allowing perfect reconstruction.Signal Process.,10, 219–244. · doi:10.1016/0165-1684(86)90101-5
[54]	Vetterli, M. (1988) Running FIR and IIR filtering using multirate filter banks.IEEE Trans. Signal Process.,36, 730–738. · Zbl 0709.94566 · doi:10.1109/29.1582
[55]	Vetterli, M. and Le Gall, D. (1989). Perfect reconstruction FIR filter banks: Some properties and factorizations.IEEE Trans. Acoust. Speech Signal Process.,37, 1057–1071. · doi:10.1109/29.32283
[56]	Vetterli, M. and Herley, C. (1992). Wavelets and filter banks: Theory and design.IEEE Trans. Acoust. Speech Signal Process.,40(9), 2207–2232. · Zbl 0825.94059
[57]	Vetterli, M. and Kovačević, J. (1995).Wavelets and Subband Coding. Prentice Hall, Englewood Cliffs, NJ. · Zbl 0885.94002
[58]	Wang, Y., M. Orchard, M., Reibman, A., and Vaishampayan, V. (1997). Redundancy rate-distortion analysis of multiple description coding using pairwise correlation transforms. InProc. IEEE ICIP, I, 608–611.
[59]	Woods, J.W. and O’Neil, S.D. (1986). Subband coding of images.IEEE Trans. Acoust. Speech Signal Process. 34(5), 1278–1288. · doi:10.1109/TASSP.1986.1164962