MISS research project

MISS: Multiresolution on arbitrary grids via subdivision and Powell-Sabin splines (01-01-2002 - 31-12-2005)

Subdivision and multiresolution:

Subdivision is in the first place a principle to generate a smooth curve (one dimension) or a surface (two dimensions) from a set of function values in a discrete point set. It is the basis for applications in computer graphics and CAGD. If a surface is given in a number of points, it allows for example to refine the surface and subsequently apply some local modifications. Well known examples are the algorithms of de Casteljau and de Boor for splines and the algorithms of Delauries-Dubuc for interpolating subdivision.

Subdivision is via the so called lifting scheme also the basis for multiresolution analyses. A multiresolution decomposition of a signal, image or surface starts from a fine grid and removes a number of points (subsampling or downsampling). In those points, the scheme tries to predict the function values on the basis of the remaining values on the coarser grid. This prediction can be seen as a subdivision step. The difference between the predicted and the actual values is the information at a certain scale. If the procedure is repeated on the remaining coarse grid, then details at the next (coarser) scale are obtained. These detail coefficients (wavelet coefficients) form a multi-scale analysis of the input. Such a data representation is extremely handy in all kinds of applications like signal processing because many phenomena have a natural multiresolution character. A multiresolution representation allows for a separate processing of each scale. The lifting scheme is the appropriate way to obtain a multiresolution on irregular point sets.

So, there are more or less two directions where subdivision shows up: the first is a synthesis of a surface on a fine grid starting from a coarse grid. Here the question is raised where points should be added to obtain a surface that is as smooth as possible. In practice this boils down to a semi-regular subdivision: the initial grid is arbitrary, but further refinements possess a certain regularity. In the second case the grid is fixed and subdivision is the basis of its multiresolution analysis. But because the grid can then be arbitrary irregular, it is much more difficult to guarantee good properties of the underlying basis functions.

Splines:

In geometric modeling and approximation applications, splines are well established. For different applications, the two-dimensional generalization is based on tensor-product splines. However splines are certainly much more advanced when irregular are involved. We mention here Powell-Sabin splines which combine a number of classical properties taht are advantageous for CAGD applications: they are invariant under affine transformations, they have convex hull properties (the spline function lies inside the convex hull of the measured data points) and they are local, so they can be easily manipulated (an advantage that is also important in wavelet analysis of signals).

On the other hand, the link between subdivision and multiresolution is relatively new. The space spanned by a spline function can be analysed at different scales. The corresponding wavelets (spline wavelets) inherit the interesting properties of the father spline wavelet and add to this the multiresolution analysis. The current results however are mainly involved with regular grids in one dimension or tensor product versions in two dimensions (think of the well known Cohen-Daubechies-Feauveau wavelets).

Proposed work:

With this project we want to bring together the research expertise from different domains. The project proposed is therefore a co-operation between two research groups: one working traditionally around splines and another working around wavelets.

• In our research around Powell-Sabin splines we have developed a subdivision algorithm for regular grids. Every kind of generalization towards irregular grids would obviously provide interesting opportunities. Experience with techniques for subdivision surfaces in other domains will be useful here.
• From our wavelet research we bumped into problems with subdivision and lifting from at least two different view points: data smoothing as well as for numerical applications give rise to problems concerning stability and smoothness of basis functions. We look for a solution for these problems and rely on our expertise about splines on irregular grids.

Specific topics to be worked on

At least four points should be kept in mind if one works with subdivision and lifting:

• Does the subdivision scheme converge and is it converging in a strict (not weak) sense?
• What are the continuity properties of the limit function: how smooth are the basis functions? The answer to this question determines how smooth the surface will be that is constructed.
• How well does the constructed surface approximate the given function? In terms of wavelets, this translates in the number of vanishing moments. Approximation properties are important in a number of applications.
• How stable is the algorithm?

Our experiments with interpolating and average interpolating subdivision have exposed serious problems with numerical conditioning if the classical wavelet transformation is applied without further precautions in the situation of irregular grids. The transition from one dimension to two dimensions seems to aggravate the problem.

Another problem that specifically shows up in higher dimensions is the problem of smoothness. Subsampling and subdivision are obvious operations in one dimension, but in two dimensions it is not so clear which points are the immediate neighbors of a given point. Therefore one works with triangulations. In the computer graphics world, much research is going on to refine given triangulations and to build a smooth function (with continuous derivatives everywhere) by subdivision. It is even more difficult to answer the question how a smooth function can be constructed on a given fine grid. The latter is important for example in data smoothing procedures.

We see that splines on irregular grids are much less affected by these difficulties. Therefore we want to construct wavelets on irregular grids via subdivision and starting from Powell-Sabin splines.