Scale-space axioms

Scale-space
Scale-space axioms
Scale-space implementation
Feature detection
Edge detection
Blob detection
Corner detection
Ridge detection
Interest point detection
Scale selection
Affine shape adaptation
Scale-space segmentation

In image processing and computer vision, a scale-space framework can be used to represent an image as a family of gradually smoothed images. This framework is very general and a variety of scale-space representations exist. A typical approach for choosing a particular type of scale-space representation is to establish a set of scale-space axioms, describing basic properties of the desired scale-space representation and often chosen so as to make the representation useful in practical applications. Once established, the axioms narrow the possible scale-space representations to a smaller class, typically with only a few free parameters.

A set of standard scale space axioms, discussed below, leads to the linear Gaussian scale-space, which is the most common type of scale space used in image processing and computer vision.

Scale space axioms for the linear scale-space representation

The linear scale-space representation L(x, y, t) = (T_t f)(x, y) = g(x, y, t)*f(x, y) of signal f(x, y) obtained by smoothing with the Gaussian kernel g(x, y, t) satisfies a number of properties 'scale-space axioms' that make it a special form of multi-scale representation:

  • linearity
T_t(a f %2B b h) = a T_t f %2B b T_t h
where f and h are signals while a and b are constants,
  • shift invariance'
T_t S_{(\Delta x, \Delta_y)} f = S_{(\Delta x, \Delta_y)} T_t f
where S_{(\Delta x, \Delta_y)} denotes the shift (translation) operator (S_{(\Delta x, \Delta_y)} f)(x, y) = f(x-\Delta x, y - \Delta y)
  • the semi-group structure
g(x, y, t_1) * g(x, y, t_2) = g(x, y, t_1 %2B t_2)
with the associated cascade smoothing property
L(x, y, t_2) = g(x, y, t_2 - t_1) * L(x, y, t_1)
  • existence of an infinitesimal generator A
\partial_t L(x, y, t) = (A L)(x, y, t)
  • non-creation of local extrema (zero-crossings) in one dimension,
  • non-enhancement of local extrema in any number of dimensions
\partial_t L(x, y, t) \leq 0 at spatial maxima and \partial_t L(x, y, t) \geq 0 at spatial minima,
  • rotational symmetry
g(x, y, t) = h(x^2%2By^2, t) for some function h,
  • scale invariance
\hat{g}(\omega_x, \omega_y, t) = \hat{h}(\frac{\omega_x}{\varphi(t)}, \frac{\omega_x}{\varphi(t)})
for some functions \varphi and \hat{h} where \hat{g} denotes the Fourier transform of g,
  • positivity:
g(x, y, t) \geq 0 ,
  • normalization:
\int_{x=-\infty}^{\infty} \int_{y=-\infty}^{\infty} g(x, y, t) \, dx \, dy = 1 .

In fact, it can be shown that the Gaussian kernel is a unique choice given several different combinations of subsets of these scale-space axioms:[1][2][3][4][5][6][7][8][9] most of the axioms (linearity, shift-invariance, semigroup) correspond to scaling being a semigroup of shift-invariant linear operator, which is satisfied by a number of families integral transforms, while "non-creation of local extrema" is the crucial axiom which related scale-spaces to smoothing (formally, parabolic partial differential equations), and hence selects for the Gaussian.

The Gaussian kernel is also separable in Cartesian coordinates, i.e. g(x, y, t) = g(x, t) \, g(y, t). Separability is, however, not counted as a scale-space axiom, since it is a coordinate dependent property related to issues of implementation. In addition, the requirement of separability in combination with rotational symmetry per se fixates the smoothing kernel to be a Gaussian.

In the computer vision, image processing and signal processing literature there are many other multi-scale approaches, using wavelets and a variety of other kernels, that do not exploit or require the same requirements as scale-space descriptions do; please see the article on related multi-scale approaches. There has also been work on discrete scale-space concepts that carry the scale-space properties over to the discrete domain; see the article on scale-space implementation for examples and references.

See also

References

  1. ^ Koenderink, Jan "The structure of images", Biological Cybernetics, 50:363–370, 1984
  2. ^ J. Babaud, A. P. Witkin, M. Baudin, and R. O. Duda, Uniqueness of the Gaussian kernel for scale-space filtering. IEEE Trans. Pattern Anal. Machine Intell. 8(1), 26–33, 1986.
  3. ^ A. Yuille, T.A. Poggio: Scaling theorems for zero crossings. IEEE Trans. Pattern Analysis & Machine Intelligence, Vol. PAMI-8, no. 1, pp. 15–25, Jan. 1986.
  4. ^ Lindeberg, T., "Scale-space for discrete signals," PAMI(12), No. 3, March 1990, pp. 234–254.
  5. ^ Lindeberg, Tony, Scale-Space Theory in Computer Vision, Kluwer, 1994,
  6. ^ Pauwels, E., van Gool, L., Fiddelaers, P. and Moons, T.: An extended class of scale-invariant and recursive scale space filters, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 17, No. 7, pp. 691–701, 1995.
  7. ^ Lindeberg, T.: On the axiomatic foundations of linear scale-space: Combining semi-group structure with causailty vs. scale invariance. In: J. Sporring et al. (eds.) Gaussian Scale-Space Theory: Proc. PhD School on Scale-Space Theory , (Copenhagen, Denmark, May 1996), pages 75–98, Kluwer Academic Publishers, 1997.
  8. ^ Florack, Luc, Image Structure, Kluwer Academic Publishers, 1997.
  9. ^ Weickert, J. Linear scale space has first been proposed in Japan. Journal of Mathematical Imaging and Vision, 10(3):237–252, 1999.