Wavelet Families of Increasing Order in Arbitrary Dimensions

Nonlinear wavelet transform for image coding

Abstract: We examine the central issues of invertibility, stability, artifacts, and frequency-domain characteristics in the construction of non-linear analogs of the wavelet transform. The lifting framework for wavelet construction motivates our analysis and provides new insight into the problem. We describe a new type of non-linearity for use in constructing non-linear transforms: a set of linear predictors that are chosen adaptively using a non-linear selection function. We also describe how earlier families of non-linear filter banks can be extended through the use of prediction functions operating on a causal neighborhood. We present preliminary results for a synthetic test image.

Status: Proceedings of the 31st Asilomar Conference on Signals, Systems, and Computers, Volume 1, pp 662-667, 1997.

BiBTeX entry:

   @inproceedings{cdsb:asil97,
    author = {R. Claypoole and G. Davis and W. Sweldens and R. Baraniuk},
    title = {Nonlinear wavelet transform for image coding},
    booktitle = {Proceedings of the 31st Asilomar Conference on
                 Signals, Systems, and Computers, Volume 1},
    pages = {662-667},
    year = {1997}		  
   }

Losless Image Compression using Integer to Integer Wavelet Transforms

Abstract: Invertible wavelet transforms that map integers to integers are important for lossless representations. In this paper, we present an approach to build integer to integer wavelet transforms based up on the idea of factoring wavelet transforms into lifting steps. This allows the construction of an integer version of every wavelet transform. We demonstrate the use of these transforms in lossless image compression.

Status: International Conference on Image Processing (ICIP), Vol. I, pp. 596-599.

Note: This is a short conference version of the paper ``Wavelet Transforms that Map Integers to Integers.''

BiBTeX entry:

   @inproceedings{cdsy:icip97,
    author = {R. Calderbank and I. Daubechies and W. Sweldens and B.-L. Yeo},
    title = {Losless Image Compression using Integer to Integer
             Wavelet Transforms},
    booktitle = {International Conference on Image Processing (ICIP), Vol. I},
    publisher = {IEEE Press},
    pages = {596-599},
    year = {1997}		  
   }

Regularity of Irregular Subdivision

Abstract: We study the smoothness of the limit function for one dimensional unequally spaced interpolating subdivision schemes. The new grid points introduced at every level can lie in irregularly spaced locations between old, adjacent grid points and not only midway as is usually the case. For the natural generalization of the four point scheme introduced by Dubuc and Dyn, Levin, and Gregory, we show that, under some geometric restrictions, the limit function is always C¹; under slightly stronger restrictions we show that the limit function is almost C², the same regularity as in the regularly spaced case.

Status: Preprint, Department of Mathematics, Princeton University, 1997. (to appear in Constructive Approximation)

BiBTeX entry:

   @article{dgs:regir,
    author = {I. Daubechies and I. Guskov and W. Sweldens},
    title = {Regularity of Irregular Subdivision},
    journal = {Constructive Approximation},
    volume = 15,
    pages = {381-426},
    year = 1999
   }

Applet: Igor wrote an applet to illustrate irregular interpolating subdivision.

Interactive Multiresolution Mesh Editing

Abstract: We describe a multiresolution representation for meshes based on subdivision. Subdivision is a natural extension of the existing patch-based surface representations. At the same time subdivision algorithms can be viewed as operating directly on polygonal meshes, which makes them a useful tool for mesh manipulation. Combination of subdivision and smoothing algorithms of Taubin allows us to construct a set of algorithms for interactive multiresolution editing of complex meshes of arbitrary topology. Simplicity of the essential algorithms for refinement and coarsification allows to make them local and adaptive, considerably improving their efficiency. We have built a scalable interactive multiresolution editing system based on such algorithms.

Status: Computer Graphics Proceedings (SIGGRAPH 97), pp 259-268, 1997.

BiBTeX entry:

   @article{zss:sig97,
    author = {D. Zorin and P. Schr{\"o}der and W. Sweldens},
    title = {Interactive Multiresolution Mesh Editing},
    journal = {Computer Graphics Proceedings (SIGGRAPH 96)},
    publisher = {ACM Siggraph},
    pages = {259-269},
    year = {1997},
   }

Factoring Wavelet Transforms into Lifting Steps

Wavelet Transforms that Map Integers to Integers

Abstract: Invertible wavelet transforms that map integers to integers have important applications in lossless coding. In this paper we present two approaches to build integer to integer wavelet transforms. The first approach is to adapt the precoder of Laroia et al., which is used in information transmission; we combine it with expansion factors for the high and low pass band in subband filtering. The second approach builds upon the idea of factoring wavelet transforms into so-called lifting steps. This allows the construction of an integer version of every wavelet transform. Finally, we use these approaches in a lossless image coder and compare the results to the literature.

Status: Applied and Computational Harmonic Analysis (ACHA), Vol. 5, Nr. 3, pp. 332-369, 1998.

BiBTeX entry:

   @article{cdsy:integer,
    author = {R. Calderbank and I. Daubechies and W. Sweldens
                   and B.-L. Yeo},
    title = {Wavelet transforms that map integers to integers},
    journal = {Appl. Comput. Harmon. Anal.},
    volume = 5,
    number = 3,
    pages = {332-369},
    year = 1998
   }

LIFTPACK: A Software Package for Wavelet Transforms using Lifting

Abstract: We present LIFTPACK: A software package written in C for fast calculation of 2D biorthogonal wavelet transforms using the lifting scheme. The lifting scheme is a new approach for the construction of biorthogonal wavelets entirely in the spatial domain, i.e., independent of the Fourier Transform. Constructing wavelets using lifting consists of three simple phases: the first step or Lazy wavelet splits the data into two subsets, even and odd, the second step calculates the wavelet coefficients (high pass) as the failure to predict the odd set based on the even, and finally the third step updates the even set using the wavelet coefficients to compute the scaling function coefficients (low pass). The predict phase ensures polynomial cancelation in the high pass (vanishing moments of the dual wavelet) and the update phase ensures preservation of moments in the low pass (vanishing moments of the primal wavelet). By varying the order, an entire family of transforms can be built. The lifting scheme ensures fast calculation of the forward and inverse wavelet transforms that only involve FIR filters. The transform works for images of arbitrary size with correct treatment of the boundaries. Also, all computations can be done in-place.

Status: In M. Unser, A. Aldroubi, and A. F. Laine, editors, Wavelet Applications in Signal and Image Processing IV, pp. 396-408, Proc. SPIE 2825, 1996.

BiBTeX entry:

   @inproceedings{fps:spie96,
    author = {G. Fern\'{a}ndez and S. Periaswamy and Wim Sweldens},
    title = {{LIFTPACK}: {A} software package for wavelet transforms using lifting},
    booktitle = {Wavelet Applications in Signal and Image Processing IV},
    editor = {M. Unser and A. Aldroubi and A. F. Laine},
    publisher = {Proc.\ SPIE~2825},
    pages = {396-408},
    year = {1996}
   }

Interpolating Subdivision for Meshes with Arbitrary Topology

Abstract: Subdivision is a powerful paradigm for the generation of surfaces of arbitrary topology. Given an initial triangular mesh the goal is to produce a smooth and visually pleasing surface, whose shape is controlled by the initial mesh. Of particular interest are interpolating schemes since they match the original data exactly, and are crucial for fast multiresolution and wavelet techniques. Dyn, Gregory, and Levin introduced the Butterfly scheme, which is known to yield C1 surfaces in the topologically regular setting. Unfortunately it exhibits various degeneracies in case of an irregular topology, leading to undesirable artifacts. We examine these failures and derive an improved scheme, which retains the simplicity of the Butterfly scheme, is interpolating, and results in smoother surfaces.

Status: Computer Graphics Proceedings (SIGGRAPH 96), pp 189-192, 1996.

BiBTeX entry:

   @article{zss:sig96,
    author = {D. Zorin and P. Schr{\"o}der and W. Sweldens},
    title = {Interpolating Subdivision for Meshes with Arbitrary Topology},
    journal = {Computer Graphics Proceedings (SIGGRAPH 96)},
    publisher = {ACM Siggraph},
    pages = {189-192},
    year = {1996},
   }

Wavelets: What Next?

Abstract: In this concluding article, we want to look ahead and see what the future can bring to wavelet research. We try to find a common denominator for ``wavelets'' and identify promising research directions and challenging problems.

Status: Proc. of the IEEE, vol. 84, nr. 4, pp. 680-685, 1996.

BiBTeX entry:

   @article {swe:future,
    author = {W. Sweldens},
    title = {Wavelets: {W}hat Next?},
    journal = {Proc. IEEE},
    volume = 84,
    number = 4,
    pages = {680-685},
    year = {1996}
   }

The Lifting Scheme: A new philosophy in biorthogonal wavelet constructions

Abstract: In this paper we present the basic idea behind the lifting scheme, a new construction of biorthogonal wavelets which does not use the Fourier transform. In contrast with earlier papers we introduce lifting purely from a wavelet transform point of view and only consider the wavelet basis functions in a later stage. We show how lifting leads to a faster, fully in-place implementation of the wavelet transform. Moreover, it can be used in the construction of second generation wavelets, wavelets that are not necessarily translates and dilates of one function. A typical example of the latter are wavelets on the sphere.

Status: In A. F. Laine and M. Unser, editors, Wavelet Applications in Signal and Image Processing III, pp. 68-79, Proc. SPIE 2569, 1995.

BiBTeX entry:

   @inproceedings {swe:spie95,
    author = {W. Sweldens},
    title = {The Lifting Scheme: A New Philosophy in Biorthogonal Wavelet Constructions},
    booktitle = {Wavelet Applications in Signal and Image Processing III},
    editor = {A. F. Laine and M. Unser},
    publisher = {Proc.\ SPIE~2569},
    year = {1995},
    pages = {68-79}
   }

Wavelets and the lifting scheme: A 5 minute tour

Abstract: In this paper, we give a brief introductory tour to the lifting scheme, an new method to construct wavelets. We show its advantages over classical constructions and give pointers to the literature.

Status: Zeitschrift für Angewandte Mathematik und Mechanik, vol. 76 (Suppl. 2), pp. 41-44, 1996.

BiBTeX entry:

  @article {swe:iciam95,
   title = {Wavelets and the lifting scheme: {A} 5 minute tour},
   author = {W. Sweldens},
   journal = {Z. Angew. Math. Mech.},
   volume = {76 (Suppl. 2)},
   pages = {41-44},
   year = 1996
}

The lifting scheme: A construction of second generation wavelets

Abstract: We present the lifting scheme, a simple construction of second generation wavelets, wavelets that are not necessarily translates and dilates of one fixed function. Such wavelets can be adapted to intervals, domains, surfaces, weights, and irregular samples. We show how the lifting scheme leads to a faster, in-place calculation of the wavelet transform. Several examples are included.

Status: Siam J. Math. Anal, Vol. 29, Nr. 2, pp 511-546, 1997.

BiBTeX entry:

   @article {swe:lift2,
    author = {W. Sweldens},
    title = {The lifting scheme: {A} construction of second generation wavelets},
    journal = {SIAM J. Math. Anal.},
    number = 2,
    volume = 29,
    pages = {511-546},
    year = {1997}
   }

Spherical Wavelets: Texture Processing

Abstract: Wavelets are a powerful tool for planar image processing. The resulting algorithms are straightforward, fast, and efficient. With the recently developed spherical wavelets this framework can be transposed to spherical textures. We describe a class of processing operators which are diagonal in the wavelet basis and which can be used for smoothing and enhancement. Since the wavelets (filters) are local in space and frequency, complex localized constraints and spatially varying characteristics can be incorporated easily. Examples from environment mapping and the manipulation of topography/bathymetry data are given.

Status: In P. Hanrahan and W. Purgathofer, editors, Rendering Techniques '95, pp. 252-263, Springer Verlag, Wien, New York, 1995,

BiBTeX entry:

  @incollection {sch-swe:env,
   author = {P. Schr\"oder and W. Sweldens},
   title = {Spherical wavelets: {T}exture processing},
   booktitle = {Rendering Techniques '95},
   editor = {P. Hanrahan and W. Purgathofer},
   publisher = {Springer Verlag},
   address = {Wien, New York},
   month = {August},		   
   year = 1995,
   pp = {252-263}
  }

A new class of unbalanced Haar wavelets that form an unconditional basis for Lp on general measure spaces

Abstract: Given a complete separable sigma-finite measure space (X,Sigma,mu) and nested partitions of X, we construct unbalanced Haar-like wavelets on X that form an unconditional basis for Lp(X,Sigma,mu) where 1 < p < infinity. Our construction and proofs build upon ideas of Burkholder and Mitrea. We show that if (X,Sigma,mu) is not purely atomic, then the unconditional basis constant of our basis is (max(p,q)-1). We derive a fast algorithm to compute the coefficients.

Status: J. Fourier Anal. Appl., Vol. 3, Nr. 4, pp. 457-474, 1997.

BiBTeX entry:

   @article {gir-swe:haar,
    author = {M. Girardi and W. Sweldens},
    title = {A new class of unbalanced {H}aar wavelets that form an unconditional basis for ${L_p}$ on general measure spaces},
    journal = {J. Fourier Anal. Appl.},
    volume = 3,
    number = 4,
    page = {457-474},
    year = 1997
   }

Spherical wavelets: Efficiently representing functions on a sphere

Abstract: Wavelets have proven to be powerful bases for use in numerical analysis and signal processing. Their power lies in the fact that they only require a small number of coefficients to represent general functions and large data sets accurately. This allows compression and efficient computations. Classical constructions have been limited to simple domains such as intervals and rectangles. In this paper we present a wavelet construction for scalar functions defined on the sphere. We show how biorthogonal wavelets with custom properties can be constructed with the lifting scheme. The bases are extremely easy to implement and allofw fully adaptive subdivisions. We give examples of functions defined on the sphere, such as topographic data, bi-directional reflection distribution functions, and illumination, and show how they can be efficiently represented with spherical wavelets.

Status: Computer Graphics Proceedings (SIGGRAPH 95), pp. 161-172, 1995

BiBTeX entry:

   @article{sch-swe:sphere,
    author = 	{Peter Schr{\"o}der and Wim Sweldens},
    title = 	{Spherical Wavelets: {E}fficiently Representing Functions on the Sphere},
    journal =	{Computer Graphics Proceedings (SIGGRAPH 95)},
    year =	1995,
    publisher =	{ACM Siggraph},
    pages = {161-172}
  }

The lifting scheme: A custom-design construction of biorthogonal wavelets

Abstract: We present the lifting scheme, a new idea of constructing compactly supported wavelets with compactly supported duals. The lifting scheme provides a simple relationship between all multiresolution analyses with the same scaling function. It isolates the degrees of freedom remaining after fixing the biorthogonality relations. Then one has full control over these degrees of freedom to custom-design the wavelet for a particular application. It also leads to a faster implementation of the fast wavelet transform. We illustrate the use of the lifting scheme in the construction of wavelets with interpolating scaling functions.

Status: Appl. Comput. Harmon. Anal, vol. 3, nr. 2, pp. 186-200, 1996.

BiBTeX entry:

   @article{swe:lift1,
    author = {W. Sweldens},
    title = {The lifting scheme: {A} custom-design construction of biorthogonal wavelets},
    journal = {Appl. Comput. Harmon. Anal.}, 
    volume = 3,
    number = 2,
    pages = {186-200},
    year = 1996
   }

Biorthogonal smooth local trigonometric bases

Abstract: In this paper we discuss smooth local trigonometric bases. We present two generalizations of the orthogonal basis of Malvar and Coifman-Meyer: biorthogonal and equal parity bases. These allow natural representations of constant and, sometimes, linear components. We study and compare their approximation properties and applicability in data compression. This is illustrated with numerical examples.

Status: J. Fourier Anal. Appl., vol. 2, nr. 2, pp. 109-103, 1995.

BiBTeX entry:

   @article {jaw-swe:bio,
    author = {B. Jawerth and W. Sweldens},
    title = {Biorthogonal smooth local trigonometric bases},
    journal = {J. Fourier Anal. Appl.},
    volume = 2,
    number = 2,
    pages = {109-133},
    year = 1995
   }

Compactly supported wavelets which are biorthogonal with respect to a weighted inner product

Abstract: In this paper we show how to construct wavelets adapted to a weighted inner product.

Status: Proceedings of the 14th Imacs World Congress.

BiBTeX entry: Files: PostScript (147Kb) or Compressed PostScript (40Kb) or PDF (142Kb).

Signal Compression with Smooth Local Trigonometric Bases

Abstract: We discuss smooth local trigonometric bases and their applications to signal compression. In image compression, these bases can reduce the blocking effect that occurs in JPEG. We present and compare two generalizations of the original construction of Malvar, Coifman and Meyer: biorthogonal and equal parity bases. These have the advantage that constant and linear components, respectively, can be represented efficiently. We show how they reduce blocking effects and improve the signal to noise ratio.

Status: Optical Engineering, vol. 33, nr. 7, pp. 2125-2135, 1994.

BiBTeX entry:

  @article {jaw-liu-swe:signal,
   author = {B. Jawerth and Y. Liu and W. Sweldens},
   title = {Signal compression with smooth local trigonometric bases},
   journal = {Optical Engineering},
   volume = 33,
   number = 7,
   year = 1994,
   pages = {2125-2135}
 }

Wavelet sampling techniques

Abstract: In this paper we present several techniques to calculate the wavelet coefficients of a function from its samples. Interpolation, quadrature formulae and filtering methods are discussed and compared.

Status: 1993 Proceedings of the Statistical Computing Section, pp. 20-29, American Statistical Association, 1993.

BiBTeX entry:

  @inproceedings {swe-pie:sanf,
   author = {W. Sweldens and R. Piessens},
   title = {Wavelet Sampling Techniques},
   booktitle = {1993 Proceedings of the Statistical Computing Section},
   publisher = {American Statistical Association},		  
   pages = {20-29},		  
   year = 1993
  }

Wavelet Probing for Compression Based Segmentation

Abstract: In this paper we show how wavelets can be used for data segmentation. The basic idea is to split the data into smooth segments that can be compressed separately. A fast algorithm that uses wavelets on closed sets and wavelet probing is presented.

Status: In A. F. Laine, editor, Wavelet Applications in Signal and Image Processing, pp. 266-276, Proc. SPIE 2034, 1993.

BiBTeX entry:

  @inproceedings {den-jaw-pet-swe:segment,
   author = {B. Deng and B. Jawerth and G. Peters and W. Sweldens},
   title = {Wavelet probing for compression based segmentation},
   booktitle = {Wavelet Applications in Signal and Image Processing},
   editor = {A. F. Laine},
   publisher = {Proc.\ SPIE~2034},
   year = {1993},
   pages = {266-276}
  }

Wavelet Multiresolution Analysis adapted for the Fast Solution of Boundary Value Ordinary Equations

Abstract: We present ideas on how to use wavelets in the solution of boundary value ordinary differential equations. Rather than using classical wavelets, we adapt their construction so that they become (bi)orthogonal with respect to the inner product defined by the operator. The stiffness matrix in a Galerkin method then becomes diagonal and can thus be trivially inverted. We show how one can construct an O(N) algorithm for various constant and variable coefficient operators.

Status: In N. D. Melson et al., editors, Sixth Copper Mountain Conference on Multigrid Methods, NASA Conference Publication 3224, pp. 259-273, 1993.

BiBTeX entry:

  @inproceedings{jaw-swe:copper,
   author = {B. Jawerth and W. Sweldens},
   title = {Wavelet multiresolution analyses adapted for the fast solution of boundary value ordinary differential equations},
   editor = {N. D. Melson and T. A. Manteuffel and S. F. McCormick},
   booktitle = {Sixth Copper Mountain Conference on Multigrid Methods},
   publisher = {NASA Conference Publication 3224},
   pages = {259-273},
   year = {1993}
}

Asymptotic Error Expansion of Wavelet Approximations of Smooth Functions II

Authors: Wim Sweldens and Robert Piessens

Abstract: This paper deals with asymptotic error expansions of orthogonal wavelet approximations of smooth functions. Two formulae are derived and compared. As already known, the error decays as O(2^(-jN))$ where j is the multiresolution level and $N$ is the number of vanishing wavelet moments. It is shown that the most significant term of the error expansion is proportional to the N-th derivative of the function multiplied with an oscillating function. This result is used to derive asymptotic interpolating properties of the wavelet approximation. Also a numerical extrapolation scheme based on the multiresolution analysis is presented.

Status: Numer. Math., vol. 68, nr. 3, pp. 377-401, 1994.

BiBTeX entry:

  @article {swe-pie:error2,
   author = {W. Sweldens and R. Piessens},
   title = {Asymptotic error expansions of wavelet approximations of smooth functions {\rm {I}{I}}},
   journal = {Numer. Math.},
   volume = {68},
   number = 3,
   pages = {377-401},
   year = 1994,
  }

An Overview of Wavelet Based Multiresolution Analysis

Abstract: In this paper we present an overview of wavelet based multiresolution analyses. First, we briefly discuss the continuous wavelet transform in its simplest form. Then, we give the definition of a multiresolution analysis and show how wavelets fit into it. We take a closer look at orthogonal, biorthogonal and semiorthogonal wavelets. The fast wavelet transform, wavelets on an interval, multidimensional wavelets and wavelet packets are discussed. Several examples of wavelet families are introduced and compared. Finally, the essentials of two major applications are outlined: data compression and compression of linear operators.

Status: SIAM Rev., vol.36, nr.3, pp.377-412, 1994.

BiBTeX entry:

  @article {jaw-swe:overview,
   author = {B. Jawerth and W. Sweldens},
   title = {An overview of wavelet based multiresolution analyses},
   journal = SIAM Rev.,
   volume = 36,
   number = 3,
   pages = {377-412},
   year = 1994
  }

Quadrature Formulae and Asymptotic Error Expansions for Wavelet Approximations of Smooth Functions

Abstract: In many applications concerning wavelets, inner products of functions f(x) with wavelets and scaling functions have to be calculated. This paper involves the calculation of these inner products from function evaluations of f(x). Firstly, one point quadrature formulae are presented. Their accuracy is compared for different classes of wavelets. Therefore the relationship between the scaling function phi(x), its values at the integers and the scaling parameters h_k is investigated. Secondly, multiple point quadrature formulae are constructed. A method to solve the nonlinear system coming from this construction is presented. Since the construction of multiple point formulae using monomials is ill-conditioned, a modified, well-conditioned construction using Chebyshev polynomials is presented.

Status: SIAM J. Num. Anal., vol. 31, nr. 4, pp. 2140-2164, 1994.

BiBTeX entry:

  @article {swe-pie:quaderr,
   author = {W. Sweldens and R. Piessens},
   title = {Quadrature Formulae and Asymptotic Error Expansions for wavelet approximations of smooth functions},
   journal = SIAM J. Numer. Anal.,
   volume = 31,
   number = 4,
   pages = {1240-1264},
   year = {1994}
  }