SPLINE PYRAMIDS SOFTWARE IN ANSI C Michael Unser, Patrick Brigger and Daniel Sage Biomedical Imaging group Swiss Federal Institute of Technology Lausanne (EPFL), Switzerland. November 1999 A. TEST PROGRAM (1D SIGNAL AND 2D IMAGE) The file test_1d.c contains a short reduction and expansion example of a 1D signal. it is implemented as a main() function. The input data are created in the code. The program displays the result on the console. There is also a similar test program for a 2D image in test_2d.c. B. BASIC ROUTINES The Reduce_1D(), Reduce_2D(), Expand_1D() and Expand_2D() are in the pyramidtools.c file. The file pyramidfilters.c contains the generation of the filters. C. OTHER ROUTINES MessageDisplay.c contains a routine to print the string messsage on the console. Configs.h contains general definitions. D. 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]. E. 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.