Graphic STI
logo EPFL
text EPFL
english only
Biomedical Imaging Group
BIG > Tutorials, Reviews and Recent Talks
CONTENTS

Home page

News & Events

Seminars

People

Research

Publications

Tutorials & Reviews

Recent Talks

Demos

Download Algorithms

Jobs and Trainees

Teaching

Student Projects

Intranet

 

DOCUMENTS

Tutorials

Reviews

Recent Talks

Splines

Wavelets

Sparsity

Sampling

Bio-imaging

All

Beyond the digital divide: Ten good reasons for using splines

M. Unser

full size

Seminars of Numerical Analysis, EPFL, May 9, 2010.

"Think analog, act digital" is a motto that is relevant to scientific computing and algorithm design in a variety of disciplines, including numerical analysis, image/signal processing, and computer graphics.
Here, we will argue that cardinal splines constitute a theoretical and computational framework that is ideally matched to this philosophy, especially when the data is available on a uniform grid.
We show that multidimensional spline interpolation or approximation can be performed most efficiently using recursive digital filtering techniques. We highlight a number of "optimal" aspects of splines (in particular, polynomial ones) and discuss fundamental relations with: (1) Shannon's sampling theory, (2) linear system theory, (3) wavelet theory, (4) regularization theory, (5) estimation theory, and (6) stochastic processes (in particular, fractals). The practicality of the spline framework is illustrated with concrete image processing examples; these include derivative-based feature extraction, high-quality rotation and scaling, and (rigid body or elastic) image registration.

Splines: A Unifying Framework for Image Processing

M. Unser

slide

Plenary talk, 2005 IEEE International Conference on Image Processing (ICIP'05), Genova, Italy, September 11-14, 2005.

Our purpose is to justify the use splines in imaging applications, emphasizing their ease of use, as well as their fundamental properties. Modeling images with splines is painless: it essentially amounts to replacing the pixels by B-spline basis functions, which are piecewise polynomials with a maximum order of differentiability. The spline representation is flexible and provides the best cost/quality tradeoff among all interpolation methods: by increasing the degree, one shifts from a simple piecewise linear representation to a higher order one that gets closer and closer to being bandlimited. We will describe efficient digital filter-based algorithms for interpolating and processing images within this framework. We will also discuss the multiresolution properties of splines that make them especially attractive for multi-scale processing.
On the more fundamental front, we will show that splines are intimately linked to differentials; in fact, the B-splines are the exact mathematical translators between the discrete and continuous versions of the operator. This is probably the reason why these functions play such a fundamental role in wavelet theory. Splines may also be justified on variational or statistical grounds; in particular, they can be shown to be optimal for the representation of fractal-like signals.
We will illustrate spline processing with applications in biomedical imaging where its impact has been the greatest so far. Specific tasks include high-quality interpolation, image resizing, tomographic reconstruction and various types of image registration.

Calculer le charme discret de la continuité

P. Roth

slide

Horizon, le magazine suisse de la recherche scientifique, no. 79, Décembre 2008.

Le traitement des images médicales a pu être fortement amélioré et accéléré grâce à des fonctions mathématiques appelées splines. Michael Unser a apporté une contribution essentielle dans ce secteur, tant sur le plan de la théorie que des applications.

Full article ...

Splines, Noise, Fractals and Optimal Signal Reconstruction

M. Unser

slide

Plenary talk, Seventh International Workshop on Sampling Theory and Applications (SampTA'07), Thessaloniki, Greece, June 1-5, 2007.

We consider the generalized sampling problem with non-ideal acquisition device. The task is to “optimally” reconstruct a continuously-varying input signal from its discrete, noisy measurements in some integer-shift-invariant space. We propose three formulations of the problem—variational/Tikhonov, minimax, and minimum mean square error estimation—and derive the corresponding solutions for a given reconstruction space. We prove that these solutions are also globally-optimal, provided that the reconstruction space is matched to the regularization operator (deterministic signal) or, alternatively, to the whitening operator of the process (stochastic modeling). Moreover, the three formulations lead to the same generalized smoothing spline reconstruction algorithm, but only if the reconstruction space is chosen optimally. We then show that fractional splines and fractal processes (fBm) are solutions of the same type of differential equations, except that the context is different: deterministic versus stochastic. We use this link to provide a solid stochastic justification of spline-based reconstruction algorithms. Finally, we propose a novel formulation of vector-splines based on similar principles, and demonstrate their application to flow field reconstruction from non-uniform, incomplete ultrasound Doppler data.

This is joint work with Yonina Eldar, Thierry Blu, and Muthuvel Arigovindan.

Vers une théorie unificatrice pour le traitement numérique/analogique des signaux

M. Unser

slide

Twentieth GRETSI Symposium on Signal and Image Processing (GRETSI'05), Louvain-la-Neuve, Belgium, September 6-9, 2005.

We introduce a Hilbert-space framework, inspired by wavelet theory, that provides an exact link between the traditional—discrete and analog—formulations of signal processing. In contrast to Shannon's sampling theory, our approach uses basis functions that are compactly supported and therefore better suited for numerical computations. The underlying continuous-time signal model is of exponential spline type (with rational transfer function); this family of functions has the advantage of being closed under the basic signal-processing operations: differentiation, continuous-time convolution, and modulation. A key point of the method is that it allows an exact implementation of continuous-time operators by simple processing in the discrete domain, provided that one updates the basis functions appropriately. The framework is ideally suited for hybrid signal processing because it can jointly represent the effect of the various (analog or digital) components of the system. This point will be illustrated with the design of hybrid systems for improved A-to-D and D-to-A conversion. On the more fundamental front, the proposed formulation sheds new light on the striking parallel that exists between the basic analog and discrete operators in the classical theory of linear systems.

Splines: on Scale, Differential Operators and Fast Algorithms

M. Unser

slides

5th International Conference on Scale Space and PDE Methods in Computer Vision, Hofgeismar, Germany, April 6-10, 2005.

Think Analog, Act Digital

M. Unser

slide

Plenary talk, Seventh Biennial Conference, 2004 International Conference on Signal Processing and Communications (SPCOM'04), Bangalore, India, December 11-14, 2004.

By interpreting the Green-function reproduction property of exponential splines in signal-processing terms, we uncover a fundamental relation that connects the impulse responses of all-pole analog filters to their discrete counterparts. The link is that the latter are the B-spline coefficients of the former (which happen to be exponential splines). Motivated by this observation, we introduce an extended family of cardinal splines—the generalized E-splines—to generalize the concept for all convolution operators with rational transfer functions. We construct the corresponding compactly supported B-spline basis functions which are characterized by their poles and zeros, thereby establishing an interesting connection with analog-filter design techniques. We investigate the properties of these new B-splines and present the corresponding signal-processing calculus, which allows us to perform continuous-time operations such as convolution, differential operators, and modulation, by simple application of the discrete version of these operators in the B-spline domain. In particular, we show how the formalism can be used to obtain exact, discrete implementations of analog filters. We also apply our results to the design of hybrid signal-processing systems that rely on digital filtering to compensate for the non-ideal characteristics of real-world A-to-D and D-to-A conversion systems.

Splines: A Perfect Fit for Signal and Image Processing

M. Unser

slide

IEEE Signal Processing Magazine, vol. 16, no. 6, pp. 22-38, November 1999.

IEEE Signal Processing Society's 2000 Magazine Award

The goals of this article are three-fold:
  • To provide a tutorial on splines that is geared to a signal processing audience.
  • To gather all their important properties, and to provide an overview of the mathematical and computational tools available; i.e., a road map for the practitioner with references to the appropriate literature.
  • To review the primary applications of splines in signal and image processing.

Image Interpolation and Resampling

P. Thévenaz, T. Blu, M. Unser

full size

Handbook of Medical Imaging, Processing and Analysis, I.N. Bankman, Ed., Academic Press, San Diego CA, USA, pp. 393-420, 2000.

This chapter presents a survey of interpolation and resampling techniques in the context of exact, separable interpolation of regularly sampled data. In this context, the traditional view of interpolation is to represent an arbitrary continuous function as a discrete sum of weighted and shifted synthesis functions—in other words, a mixed convolution equation. An important issue is the choice of adequate synthesis functions that satisfy interpolation properties. Examples of finite-support ones are the square pulse (nearest-neighbor interpolation), the hat function (linear interpolation), the cubic Keys' function, and various truncated or windowed versions of the sinc function. On the other hand, splines provide examples of infinite-support interpolation functions that can be realized exactly at a finite, surprisingly small computational cost. We discuss implementation issues and illustrate the performance of each synthesis function. We also highlight several artifacts that may arise when performing interpolation, such as ringing, aliasing, blocking and blurring. We explain why the approximation order inherent in the synthesis function is important to limit these interpolation artifacts, which motivates the use of splines as a tunable way to keep them in check without any significant cost penalty.

© 2014 EPFL • webmaster.big@epfl.ch • 11.04.2014