Spline Pyramids Software English only BIG > Algorithms > Spline Pyramids Software
CONTENTS

Spline Pyramids Software

 This software package implements the basic REDUCE and EXPAND operators for the reduction and enlargement of signals and images by factors of two based on polynomial spline representation of the signal. 1. Download Michael Unser Patrick Brigger Daniel Sage

The source code (ANSI C) is available in the following archive formats:

You are free to use these routines as long as you provide the adequate references.

2. Explanation

Software for generating spline pyramids

This software package implements the basic REDUCE and EXPAND operators for the reduction and enlargement of signals and images by factors of two. A signal is represented by a polynomial spline which is a continuously-defined function [1]; the model is interpolating and is unambiguously defined by the sample values. The spline model specifies the enlargement mechanism (spline interpolation), as well as the reduction algorithm which is optimal in the least squares sense.

Model specification

The user specifies the underlying spline model and error criterion by selecting the appropriate filters using the GetPyramidFilter subroutine. He can choose the degree of the spline (typ. n=3), and the type of error measure (discrete -norm [2] or continuous -norm [3]). Note that the differences between the two types of filters tend to vanish as the degree increases. The user also has the choice between a standard pyramid where the coarser grid points are at the even integers, and a centered one where the coarser grid points are placed in-between their two closest finer grid predecessors [4].

REDUCE operator

It is implemented by the function Reduce_1D which filters and downsamples a signal by a factor of two. The reduction filter is designed such that the approximation error is minimized. For digital images or volumes, the function must be applied successively along the various dimensions of the data. A multiresolution decomposition (or pyramid) may be generated by repeated application of the REDUCE operator. Note that the evaluation of centered pyramids requires the use of the function ReduceCentered_1D instead. In all cases, the signals are extended using mirror boundary conditions to minimize border artifacts.

EXPAND operator

It is implemented by the function Expand_1D which up-samples a signal by a factor of two and then fills-in the missing samples by application of a suitable interpolation filter. The interpolation filter is specified by the underlying spline model; for a given order n, it is the same irrespective of the type of criterion used to specify the REDUCE function. The expand operator uses boundary conditions that are compatible with the reduce operation. In the case of a centered pyramid, the interpolation is achieved by the ExpandCentered_1D, since the samples on the finer grid are shifted by half a sampling step.

Error pyramid

The loss of information due to image/signal reduction can be visualized in the error pyramid. The error signal is computed as follows: error = signal – EXPAND(REDUCE(signal)). In the present design, the REDUCE and EXPAND filters are biorthogonal and the system acts like a projector. This explains why the error is usually much smaller then the one obtained by using the Burt and Adelson filters associated with the Gaussian/Laplacian pyramid [5]. Also note that there is a close connection between these spline pyramids and wavelets as explained in [1].

3. References

[1] M. Unser, "Splines: A Perfect Fit for Signal and Image Processing," IEEE Signal Processing Magazine, vol. 16, no. 6, pp. 22-38, November 1999.

[2] M. Unser, A. Aldroubi, M. Eden, "B-Spline Signal Processing: Part II--Efficient Design and Applications," IEEE Transactions on Signal Processing, vol. 41, no. 2, pp. 834-848, February 1993.

[3] M. Unser, A. Aldroubi, M. Eden, "The L2-Polynomial Spline Pyramid," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 15, no. 4, pp. 364-379, April 1993.

[4] P. Brigger, F. Müller, K. Illgner, M. Unser, "Centered Pyramids," IEEE Transactions on Image Processing, vol. 8, no. 9, pp. 1254-1264, September 1999.

[5] P.J. Burt and E.H. Adelson, "The Laplacian Pyramid as a Compact Code," IEEE Transactions on Commununication, vol. COM-31, no. 4, pp. 337-345, April 1983.