SMID research project

SMID: Stability of Multiscale Transforms on Irregular Data (01-01-2005 - 31-12-2008). Wavelet theory was first developed for analogue data and for samples at equidistant points. Although a bunch of interesting pre- or postprocessing methods, such as interpolations or projections onto regular data have been proposed for irregular samples, the lifting scheme is probably the most natural extension of multiscale decompositions towards the irregular setting. Lifting was first introduced as a method to ‘enhance’ a given wavelet transform in order to add properties (typically vanishing moments for better approximation and compression) to it while preserving the existing ones. It also proved an excellent tool for the construction of wavelet transforms from scratch. All existing (standard) wavelet transform can be decomposed into lifting steps, and new transforms can be constructed based on intuitive ideas. In its simplest form, a lifting wavelet transform starts with splitting the input data into two groups, for instance (but not necessarily) even and odd indexed samples. The idea is that the odd samples can be well predicted by the even ones. The difference between these predictions and the actual values of the odd samples are typically small, they are stored as detail or wavelet coefficients. The prediction is often some polynomial or spline interpolation-like operation.

If the input is a polynomial, the details are zero, so this stage of the transform controls the compression characteristics of the transform. These characteristics are reflected in the analysing or dual wavelet basis function, and is therefore called the dual lifting step. A lifting scheme needs at least one additional step in order to obtain a stable transform. Indeed, the even input samples have only been downsampled so far. Without further update, the values would proceed untouched to the next, coarser scale. Some of these values would therefore proceed unchanged to the coarsest scales. Consequently, small perturbations on these values would have an overall impact. The subsequent update, or primal lifting, step changes the even samples by adding some linear or nonlinear function of the detail values. The dual lifting step thereby implicitly creates the actual wavelet basis functions. (This is a nontrivial statement, for readers familiar with wavelet theory, it is best seen by running the inverse wavelet transform (subdivision) with a single nonzero coefficient on the detail branch.) The effect of this update can also be described as anti-aliasing, since no update means simple downsampling, thereby introducing aliasing.

Previous research on this subject

Classical wavelet theory is embedded within the framework of multiresolution analysis. This concept requires stable (‘Riesz’) basis and imposes conditions on wavelet transforms. These conditions for the existence of a wavelet basis function coincide with the conditions for stable transforms. As a consequence, stability is a relatively easy issue in classical wavelet theory. This theory therefore concentrates on issues like smoothness and approximation power.

So did the initial version of the lifting scheme. The prediction operation was primely motivated by vanishing moments. While on regular samples this works as in the classical setting, it fails on irregular grids. It is necessary to reserve some of the degrees of freedom in the consecutive lifting steps for stability:

1. Inspired by the fact that the update lifting step is a necessary stabilising stage in any wavelet transform, a first class of methods concentrates on a careful design of this update step. Update coefficients can be chosen such that the resulting lifted wavelets are as orthogonal as possible (in a least squares sense) to overlapping scaling functions. An alternative is a local orthogonalisation w.r.t. a limited number of scaling functions. Minimum norm update coefficients can be seen as a simple, pure algebraic implementation avoiding unstable bases.
2. Also in the prediction step, not all degrees of freedom should be spent on vanishing moments, especially not in 2-D.
3. The stabilising effect of the update step is limited by the homogeneity of the mesh (maximum ratio of neighbouring intervals in 1-d, most narrow triangle in 2-D triangular mesh). Working on inhomogeneous grids may result in ‘mixing of scales’, i.e., incorporating phenomena at coarse and fine scale within a single level of the transform. This is a source of instabilities. This motivates a careful splitting scheme, instead of just even-odd splitting.

Topics and methodology of this proposal

This project wants to investigate three topics within the area of stable lifting schemes:

1. Starting from the existing results, we want to extend and complete the analysis of our previous stabilising methods. The stability analysis of multiresolution transforms on nonequispaced data is more complex than on equispaced data, since Fourier techniques no longer apply. Checking the conditions may require slightly different techniques for every choice of prediction and update. We also want to investigate the impact of nonclassical splitting on the basis functions. Given these results, we will proceed to a synthesis of techniques and investigate how their performances mutually interact.
2. Simultaneously with this first topic, we also plan to investigate new implementations.
   • In the prediction step, we could adopt a weighted least squares operation to predict odd samples from even ones. If the weights depend on the intersample distance, such that they become infinite when samples are arbitrarily close to each other, this additionally undoes unpleasant scale mixing effects.
   • We will study the applicability of simple alternatives for the even-odd splitting. First, we introduce the idea of one predicted value in each step into 1-d schemes. We already use this splitting scheme in 2-D. Second, instead of the present scale by scale approach, we want to develop a preprocessing step which fixes the order in which points are split by running bottom-up through the samples, i.e., by starting from coarse scales and progressively adding samples. In 2-D, we plan to study ‘mesh simplification’ procedures as they are used in computer graphics applications.
3. In a following stage, we want to investigate adaptive, nonlinear schemes. We focus on the ‘normal offset’ scheme, presented by Jansen. This scheme has no update step, and it is not trivial to construct one, since the linear framework with basis functions no longer applies.

This project will have interactions with three research groups at the department: numerical approximation and linear algebra, scientific computing and computer graphics. Collaboration with other institutes: UCL at Louvain-La-Neuve, Bristol University, KIM at Den Helder (Netherlands), will also take place within the framework of this project. Joint publications with those groups have been submitted or are in preparation. There are concrete plans to elaborate on applications of this project, which will result in new joint publications.