Scale-Space for Discrete Signals

Tony Lindeberg

IEEE Transactions of Pattern Analysis and Machine Intelligence, 12(3), 234--254, 1990.


This article addresses the formulation of a scale-space theory for discrete signals. In one dimension it is possible to characterize the smoothing transformations completely and an exhaustive treatment is given, answering the following two main questions:
  • Which linear transformations remove structure in the sense that the number of local extrema (or zero-crossings) in the output signal does not exceed the number of local extrema (or zero-crossings) in the original signal?
  • How should one create a multi-resolution family of representations with the property that a signal at a coarser level of scale never contains more structure than a signal at a finer level of scale?
It is proposed that there is only one reasonable way to define a scale-space for 1D discrete signals comprising a continuous scale parameter, namely by (discrete) convolution with the family of kernels T(n; t) = e^{-t} I_n(t), where I_n are the modified Bessel functions of integer order. Similar arguments applied in the continuous case uniquely lead to the Gaussian kernel.

Some obvious discretizations of the continuous scale-space theory are discussed in view of the results presented. It is shown that the kernel T(n; t) arises naturally in the solution of a discretized version of the diffusion equation. The commonly adapted technique with a sampled Gaussian can lead to undesirable effects since scale-space violations might occur in the corresponding representation. The result exemplifies the fact that properties derived in the continuous case might be violated after discretization.

A two-dimensional theory, showing how the scale-space should be constructed for images, is given based on the requirement that local extrema must not be enhanced, when the scale parameter is increased continuously. In the separable case the resulting scale-space representation can be calculated by separated convolution with the kernel T(n; t).

The presented discrete theory has computational advantages compared to a scale-space implementation based on the sampled Gaussian, for instance concerning the Laplacian of the Gaussian. The main reason is that the discrete nature of the implementation has been taken into account already in the theoretical formulation of the scale-space representation.

PDF: (421 kb)

Further work: (Extension to arbitrary dimensions) (Discrete derivative approximations) (Other publications on scale-space theory) (Encyclopedia entry on scale-space theory)