Scale space
Encyclopedia
Scale-space theory is a framework for multi-scale
signal representation
developed by the computer vision
, image processing
and signal processing
communities with complementary motivations from physics and biological vision. It is a formal theory for handling image structures at different scale
s, by representing an image as a one-parameter family of smoothed images, the scale-space representation, parametrized by the size of the smoothing kernel used for suppressing fine-scale structures. The parameter
in this family is referred to as the scale parameter, with the interpretation that image structures of spatial size smaller than about 
have largely been smoothed away in the scale-space level at scale 
.
The main type of scale-space is the linear (Gaussian) scale-space, which has wide applicability as well as the attractive property of being possible to derive from a small set of scale-space axioms
. The corresponding scale-space framework encompasses a theory for Gaussian derivative operators, which can be used as a basis for expressing a large class of visual operations for computerized systems that process visual information. This framework also allows visual operations to be made scale invariant, which is necessary for dealing with the size variations that may occur in image data, because real-world objects may be of different sizes and in addition the distance between the object and the camera may be unknown and may vary depending on the circumstances.
, its linear (Gaussian) scale-space representation is a family of derived signals 
defined by the convolution
of
with the Gaussian kernel
such that
where the semicolon in the argument of
implies that the convolution is performed only over the variables 
, while the scale parameter 
after the semicolon just indicates which scale level is being defined. This definition of 
works for a continuum of scales 
, but typically only a finite discrete set of levels in the scale-space representation would be actually considered.
is the variance
of the Gaussian filter and as a limit for
the filter 
becomes an impulse function such that 
that is, the scale-space representation at scale level 
is the image 
itself. As 
increases, 
is the result of smoothing 
with a larger and larger filter, thereby removing more and more of the details which the image contains. Since the standard deviation of the filter is 
, details which are significantly smaller than this value are to a large extent removed from the image at scale parameter 
, see the following figure and for graphical illustrations.
The conclusion from several different axiomatic derivations that have been presented is that the Gaussian scale-space constitutes the canonical way to generate a linear scale-space, based on the essential requirement that new structures must not be created when going from a fine scale to any coarser scale.
Conditions, referred to as scale-space axioms
, that have been used for deriving the uniqueness of the Gaussian kernel include linearity, shift invariance, semi-group structure, non-enhancement of local extrema, scale invariance
and rotational invariance
.
Equivalently, the scale-space family can be defined as the solution of the diffusion equation (for example in terms of the heat equation
),
with initial condition
. This formulation of the scale-space representation L means that it is possible to interpret the intensity values of the image f as a "temperature distribution" in the image plane and that the process which generates the scale-space representation as a function of t corresponds to heat diffusion in the image plane over time t (assuming the thermal conductivity of the material equal to the arbitrarily chosen constant ½). Although this connection may appear superficial for a reader not familiar with differential equation
s, it is indeed the case that the main scale-space formulation in terms of non-enhancement of local extrema is expressed in terms of a sign condition on partial derivative
s in the 2+1-D volume generated by the scale-space, thus within the framework of partial differential equation
s. Furthermore, a detailed analysis of the discrete case shows that the diffusion equation provides a unifying link between continuous and discrete scale-spaces, which also generalizes to non-linear scale-spaces, for example, using anisotropic diffusion
. Hence, one may say that the primary way to generate a scale-space is by the diffusion equation, and that the Gaussian kernel arises as the Green's function
of this specific partial differential equation.
. This implies that real-world objects, in contrast to idealized mathematical entities such as points
or line
s, may appear in different ways depending on the scale of observation.
For example, the concept of a "tree" is appropriate at the scale of meters, while concepts such as leaves and molecules are more appropriate at finer scales.
For a computer vision
system analysing an unknown scene, there is no way to know a priori what scales
are appropriate for describing the interesting structures in the image data.
Hence, the only reasonable approach is to consider descriptions at multiple scales in order to be able to capture the unknown scale variations that may occur.
Taken to the limit, a scale-space representation considers representations at all scales.
Another motivation to the scale-space concept originates from the process of performing a physical measurement on real-world data. In order to extract any information from a measurement process, one has to apply operators of non-infinitesimal size to the data. In many branches of computer science and applied mathematics, the size of the measurement operator is disregarded in the theoretical modelling of a problem. The scale-space theory on the other hand explicitly incorporates the need for a non-infinitesimal size of the image operators as an integral part of any measurement as well as any other operation that depends on a real-world measurement.
There is a close link between scale-space theory and biological vision. Many scale-space operations show a high degree of similarity with receptive field profiles recorded from the mammalian retina and the first stages in the visual cortex.
In these respects, the scale-space framework can be seen as a theoretically well-founded paradigm for early vision, which in addition has been thoroughly tested by algorithms and experiments.
Due to the commutative property between the derivative operator and the Gaussian smoothing operator, such scale-space derivatives can equivalently be computed by convolving the original image with Gaussian derivative operators. For this reason they are often also referred to as Gaussian derivatives:
Interestingly, the uniqueness of the Gaussian derivative operators as local operations derived from a scale-space representation can be obtained by similar axiomatic derivations as are used for deriving the uniqueness of the Gaussian kernel for scale-space smoothing.
These Gaussian derivative operators can in turn be combined by linear or non-linear operators into a larger variety of different types of feature detectors, which in many cases can be well modelled by differential geometry. Specifically, invariance (or more appropriately covariance) to local geometric transformations, such as rotations or local affine transformations, can be obtained by considering differential invariants under the appropriate class of transformations or alternatively by normalizing the Gaussian derivative operators to a locally determined coordinate frame determined from e.g. a preferred orientation in the image domain or by applying a preferred local affine transformation to a local image patch (see the article on affine shape adaptation
for further details).
When Gaussian derivative operators and differential invariants are used in this way as basic feature detectors at multiple scales, the uncommitted first stages of visual processing are often referred to as a visual front-end. This overall framework has been applied to a large variety of problems in computer vision, including feature detection
, feature classification, image segmentation
, image matching
, motion estimation
, computation of shape
cues and object recognition
. The set of Gaussian derivative operators up to a certain order is often referred to as the N-jet
and constitutes a basic type of feature within the scale-space framework.
from the set of points that satisfy the requirement that the gradient magnitude
should assume a local maximum in the gradient direction
.
By working out the differential geometry, it can be shown that this differential edge detector can equivalently be expressed from the zero-crossings of the second-order differential invariant
that satisfy the following sign condition on a third-order differential invariant:
Similarly, multi-scale blob detectors
at any given fixed scale can be obtained from local maxima and local minima of either the Laplacian operator (also referred to as the Laplacian of Gaussian)
or the determinant of the Hessian matrix
.
In an analogous fashion, corner detectors and ridge and valley detectors can be expressed as local maxima, minima or zero-crossings of multi-scale differential invariants defined from Gaussian derivatives. The algebraic expressions for the corner and ridge detection operators are, however, somewhat more complex and the reader is referred to the articles on corner detection
and ridge detection
for further details.
Scale-space operations have also been frequently used for expressing coarse-to-fine methods, in particular for tasks such as image matching
and for multi-scale image segmentation
.
A highly useful property of scale-space representation is that image representations can be made invariant to scales, by performing automatic local scale selection based on local maxima
(or minima) over scales of normalized derivative
s
where
is a parameter that is related to the dimensionality of the image feature. This algebraic expression for scale normalized Gaussian derivative operators originates from the introduction of 
-normalized derivatives according to
and 
.
It can be theoretically shown that a scale selection module working according to this principle will satisfy the following scale invariance property: if for a certain type of image feature a local maximum is assumed in a certain image at a certain scale
, then under a rescaling of the image by a scale factor 
the local maximum over scales in the rescaled image will be transformed to the scale level 
.
Following this approach of gamma-normalized derivatives, it can be shown that different types of scale adaptive and scale invariant feature detectors
can be expressed for tasks such as blob detection
, corner detection
, ridge detection
and edge detection
(see the specific articles on these topics for in-depth descriptions of how these scale-invariant feature detectors are formulated).
Furthermore, the scale levels obtained from automatic scale selection can be used for determining regions of interest for subsequent affine shape adaptation
to obtain affine invariant interest points or for determining scale levels for computing associated image descriptors, such as locally scale adapted N-jet
s.
Recent work has shown that also more complex operations, such as scale-invariant object recognition
can be performed in this way,
by computing local image descriptors (N-jets or local histograms of gradient directions) at scale-adapted interest points obtained from scale-space maxima of the normalized Laplacian operator (see also scale-invariant feature transform
).
is a discrete representation in which a scale space is sampled in both space and scale. For scale invariance, the scale factors should be sampled exponentially, for example as integer powers of 2 or root 2. When properly constructed, the ratio of the sample rates in space and scale are held constant so that the impulse response is identical in all levels of the pyramid.
Fast, O(N), algorithms exist for computing a scale invariant image pyramid in which the image or signal is repeatedly smoothed then subsampled.
Values for scale space between pyramid samples can easily be estimated using interpolation within and between scales.
In a scale-space representation, the existence of a continuous scale parameter makes it possible to track zero crossings over scales leading to so-called deep structure.
For features defined as zero-crossings of differential invariant
s, the implicit function theorem
directly defines trajectories
across scales, and at those scales where bifurcation
s occur, the local behaviour can be modelled by singularity theory
.
Extensions of linear scale-space theory concern the formulation of non-linear scale-space concepts more committed to specific purposes. These non-linear scale-spaces often start from the equivalent diffusion formulation of the scale-space concept, which is subsequently extended in a non-linear fashion. A large number of evolution equations have been formulated in this way, motivated by different specific requirements (see the abovementioned book references for further information). It should be noted, however, that not all of these non-linear scale-spaces satisfy similar "nice" theoretical requirements as the linear Gaussian scale-space concept. Hence, unexpected artifacts may sometimes occur and one should be very careful of not using the term "scale-space" for just any type of one-parameter family of images.
A first-order extension of the isotropic Gaussian scale-space is provided by the affine (Gaussian) scale-space. One motivation for this extension originates from the common need for computing image descriptors subject for real-world objects that are viewed under a perspective camera model. To handle such non-linear deformations locally, partial invariance (or more correctly covariance
) to local affine deformations can be achieved by considering affine Gaussian kernels with their shapes determined by the local image structure, see the article on affine shape adaptation
for theory and algorithms. Indeed, this affine scale-space can also be expressed from a non-isotropic extension of the linear (isotropic) diffusion equation, while still being within the class of linear partial differential equation
s.
There are strong relations between scale-space theory and wavelet theory, although these two notions of multi-scale representation have been developed from somewhat different premises.
There has also been work on other multi-scale approaches
, such as pyramids and a variety of other kernels, that do not exploit or require the same requirements as true scale-space descriptions do.
Neurophysiological studies have shown that there are receptive field
profiles in the mammalian retina
and visual cortex
,
which can be well modelled by linear Gaussian derivative operators, in some cases also complemented by a non-isotropic affine scale-space model and/or non-linear combinations of such linear operators.
Multi-scale feature detection within the scale-space framework:
The Gaussian function and other smoothing or multi-scale approaches:
More general articles on feature detection, computer vision and image processing:
Scale model
A scale model is a physical model, a representation or copy of an object that is larger or smaller than the actual size of the object, which seeks to maintain the relative proportions of the physical size of the original object. Very often the scale model is used as a guide to making the object in...
signal representation
Knowledge representation
Knowledge representation is an area of artificial intelligence research aimed at representing knowledge in symbols to facilitate inferencing from those knowledge elements, creating new elements of knowledge...
developed by the computer vision
Computer vision
Computer vision is a field that includes methods for acquiring, processing, analysing, and understanding images and, in general, high-dimensional data from the real world in order to produce numerical or symbolic information, e.g., in the forms of decisions...
, image processing
Image processing
In electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...
and signal processing
Signal processing
Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...
communities with complementary motivations from physics and biological vision. It is a formal theory for handling image structures at different scale
Scale (ratio)
The scale ratio of some sort of model which represents an original proportionally is the ratio of a linear dimension of the model to the same dimension of the original. Examples include a 3-dimensional scale model of a building or the scale drawings of the elevations or plans of a building. In such...
s, by representing an image as a one-parameter family of smoothed images, the scale-space representation, parametrized by the size of the smoothing kernel used for suppressing fine-scale structures. The parameter
in this family is referred to as the scale parameter, with the interpretation that image structures of spatial size smaller than about have largely been smoothed away in the scale-space level at scale .The main type of scale-space is the linear (Gaussian) scale-space, which has wide applicability as well as the attractive property of being possible to derive from a small set of scale-space axioms
Scale-space axioms
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...
. The corresponding scale-space framework encompasses a theory for Gaussian derivative operators, which can be used as a basis for expressing a large class of visual operations for computerized systems that process visual information. This framework also allows visual operations to be made scale invariant, which is necessary for dealing with the size variations that may occur in image data, because real-world objects may be of different sizes and in addition the distance between the object and the camera may be unknown and may vary depending on the circumstances.
Definition
The notion of scale-space applies to signals of arbitrary numbers of variables. The most common case in the literature applies to two-dimensional images, which is what is presented here. For a given image, its linear (Gaussian) scale-space representation is a family of derived signals defined by the convolutionConvolution
In mathematics and, in particular, functional analysis, convolution is a mathematical operation on two functions f and g, producing a third function that is typically viewed as a modified version of one of the original functions. Convolution is similar to cross-correlation...
of
with the Gaussian kernelsuch that
where the semicolon in the argument of
implies that the convolution is performed only over the variables , while the scale parameter after the semicolon just indicates which scale level is being defined. This definition of works for a continuum of scales , but typically only a finite discrete set of levels in the scale-space representation would be actually considered. is the varianceVariance
In probability theory and statistics, the variance is a measure of how far a set of numbers is spread out. It is one of several descriptors of a probability distribution, describing how far the numbers lie from the mean . In particular, the variance is one of the moments of a distribution...
of the Gaussian filter and as a limit for
the filter becomes an impulse function such that that is, the scale-space representation at scale level is the image itself. As increases, is the result of smoothing with a larger and larger filter, thereby removing more and more of the details which the image contains. Since the standard deviation of the filter is , details which are significantly smaller than this value are to a large extent removed from the image at scale parameter , see the following figure and for graphical illustrations.Why a Gaussian filter?
When faced with the task of generating a multi-scale representation one may ask: Could any filter g of low-pass type and with a parameter t which determines its width be used to generate a scale-space? The answer is no, as it is of crucial importance that the smoothing filter does not introduce new spurious structures at coarse scales that do not correspond to simplifications of corresponding structures at finer scales. In the scale-space literature, a number of different ways have been expressed to formulate this criterion in precise mathematical terms.The conclusion from several different axiomatic derivations that have been presented is that the Gaussian scale-space constitutes the canonical way to generate a linear scale-space, based on the essential requirement that new structures must not be created when going from a fine scale to any coarser scale.
Conditions, referred to as scale-space axioms
Scale-space axioms
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...
, that have been used for deriving the uniqueness of the Gaussian kernel include linearity, shift invariance, semi-group structure, non-enhancement of local extrema, scale invariance
Scale invariance
In physics and mathematics, scale invariance is a feature of objects or laws that do not change if scales of length, energy, or other variables, are multiplied by a common factor...
and rotational invariance
Rotational invariance
In mathematics, a function defined on an inner product space is said to have rotational invariance if its value does not change when arbitrary rotations are applied to its argument...
.
Equivalently, the scale-space family can be defined as the solution of the diffusion equation (for example in terms of the heat equation
Heat equation
The heat equation is an important partial differential equation which describes the distribution of heat in a given region over time...
),
with initial condition
. This formulation of the scale-space representation L means that it is possible to interpret the intensity values of the image f as a "temperature distribution" in the image plane and that the process which generates the scale-space representation as a function of t corresponds to heat diffusion in the image plane over time t (assuming the thermal conductivity of the material equal to the arbitrarily chosen constant ½). Although this connection may appear superficial for a reader not familiar with differential equationDifferential equation
A differential equation is a mathematical equation for an unknown function of one or several variables that relates the values of the function itself and its derivatives of various orders...
s, it is indeed the case that the main scale-space formulation in terms of non-enhancement of local extrema is expressed in terms of a sign condition on partial derivative
Partial derivative
In mathematics, a partial derivative of a function of several variables is its derivative with respect to one of those variables, with the others held constant...
s in the 2+1-D volume generated by the scale-space, thus within the framework of partial differential equation
Partial differential equation
In mathematics, partial differential equations are a type of differential equation, i.e., a relation involving an unknown function of several independent variables and their partial derivatives with respect to those variables...
s. Furthermore, a detailed analysis of the discrete case shows that the diffusion equation provides a unifying link between continuous and discrete scale-spaces, which also generalizes to non-linear scale-spaces, for example, using anisotropic diffusion
Anisotropic diffusion
In image processing and computer vision, anisotropic diffusion, also called Perona–Malik diffusion, is a technique aiming at reducing image noise without removing significant parts of the image content, typically edges, lines or other details that are important for the interpretation of the image...
. Hence, one may say that the primary way to generate a scale-space is by the diffusion equation, and that the Gaussian kernel arises as the Green's function
Green's function
In mathematics, a Green's function is a type of function used to solve inhomogeneous differential equations subject to specific initial conditions or boundary conditions...
of this specific partial differential equation.
Motivations
The motivation for generating a scale-space representation of a given data set originates from the basic observation that real-world objects are composed of different structures at different scalesScale (ratio)
The scale ratio of some sort of model which represents an original proportionally is the ratio of a linear dimension of the model to the same dimension of the original. Examples include a 3-dimensional scale model of a building or the scale drawings of the elevations or plans of a building. In such...
. This implies that real-world objects, in contrast to idealized mathematical entities such as points
Point (geometry)
In geometry, topology and related branches of mathematics a spatial point is a primitive notion upon which other concepts may be defined. In geometry, points are zero-dimensional; i.e., they do not have volume, area, length, or any other higher-dimensional analogue. In branches of mathematics...
or line
Line (geometry)
The notion of line or straight line was introduced by the ancient mathematicians to represent straight objects with negligible width and depth. Lines are an idealization of such objects...
s, may appear in different ways depending on the scale of observation.
For example, the concept of a "tree" is appropriate at the scale of meters, while concepts such as leaves and molecules are more appropriate at finer scales.
For a computer vision
Computer vision
Computer vision is a field that includes methods for acquiring, processing, analysing, and understanding images and, in general, high-dimensional data from the real world in order to produce numerical or symbolic information, e.g., in the forms of decisions...
system analysing an unknown scene, there is no way to know a priori what scales
Scale (ratio)
The scale ratio of some sort of model which represents an original proportionally is the ratio of a linear dimension of the model to the same dimension of the original. Examples include a 3-dimensional scale model of a building or the scale drawings of the elevations or plans of a building. In such...
are appropriate for describing the interesting structures in the image data.
Hence, the only reasonable approach is to consider descriptions at multiple scales in order to be able to capture the unknown scale variations that may occur.
Taken to the limit, a scale-space representation considers representations at all scales.
Another motivation to the scale-space concept originates from the process of performing a physical measurement on real-world data. In order to extract any information from a measurement process, one has to apply operators of non-infinitesimal size to the data. In many branches of computer science and applied mathematics, the size of the measurement operator is disregarded in the theoretical modelling of a problem. The scale-space theory on the other hand explicitly incorporates the need for a non-infinitesimal size of the image operators as an integral part of any measurement as well as any other operation that depends on a real-world measurement.
There is a close link between scale-space theory and biological vision. Many scale-space operations show a high degree of similarity with receptive field profiles recorded from the mammalian retina and the first stages in the visual cortex.
In these respects, the scale-space framework can be seen as a theoretically well-founded paradigm for early vision, which in addition has been thoroughly tested by algorithms and experiments.
Gaussian derivatives and the notion of a visual front end
At any scale in scale-space, we can apply local derivative operators to the scale-space representation:Due to the commutative property between the derivative operator and the Gaussian smoothing operator, such scale-space derivatives can equivalently be computed by convolving the original image with Gaussian derivative operators. For this reason they are often also referred to as Gaussian derivatives:
Interestingly, the uniqueness of the Gaussian derivative operators as local operations derived from a scale-space representation can be obtained by similar axiomatic derivations as are used for deriving the uniqueness of the Gaussian kernel for scale-space smoothing.
These Gaussian derivative operators can in turn be combined by linear or non-linear operators into a larger variety of different types of feature detectors, which in many cases can be well modelled by differential geometry. Specifically, invariance (or more appropriately covariance) to local geometric transformations, such as rotations or local affine transformations, can be obtained by considering differential invariants under the appropriate class of transformations or alternatively by normalizing the Gaussian derivative operators to a locally determined coordinate frame determined from e.g. a preferred orientation in the image domain or by applying a preferred local affine transformation to a local image patch (see the article on affine shape adaptation
Affine shape adaptation
Affine shape adaptation is a methodology for iteratively adapting the shape of the smoothing kernels in an affine group of smoothing kernels to the local image structure in neighbourhood region of a specific image point...
for further details).
When Gaussian derivative operators and differential invariants are used in this way as basic feature detectors at multiple scales, the uncommitted first stages of visual processing are often referred to as a visual front-end. This overall framework has been applied to a large variety of problems in computer vision, including feature detection
Feature detection
In computer vision and image processing the concept of feature detection refers to methods that aim at computing abstractions of image information and making local decisions at every image point whether there is an image feature of a given type at that point or not...
, feature classification, image segmentation
Scale-space segmentation
Scale-space segmentation or multi-scale segmentation is a general framework for signal and image segmentation, based on the computation of image descriptors at multiple scales of smoothing.-One-dimensional hierarchical signal segmentation:...
, image matching
Image registration
Image registration is the process of transforming different sets of data into one coordinate system. Data may be multiple photographs, data from different sensors, from different times, or from different viewpoints. It is used in computer vision, medical imaging, military automatic target...
, motion estimation
Motion estimation
Motion estimation is the process of determining motion vectors that describe the transformation from one 2D image to another; usually from adjacent frames in a video sequence. It is an ill-posed problem as the motion is in three dimensions but the images are a projection of the 3D scene onto a 2D...
, computation of shape
Shape
The shape of an object located in some space is a geometrical description of the part of that space occupied by the object, as determined by its external boundary – abstracting from location and orientation in space, size, and other properties such as colour, content, and material...
cues and object recognition
Object recognition
Object recognition in computer vision is the task of finding a given object in an image or video sequence. Humans recognize a multitude of objects in images with little effort, despite the fact that the image of the objects may vary somewhat in different view points, in many different sizes / scale...
. The set of Gaussian derivative operators up to a certain order is often referred to as the N-jet
N-jet
An N-jet is the set of derivatives of a function f up to order N.Specifically, in the area of computer vision, the N-jet is usually computed from a scale-space representation L of the input image f, and the partial derivatives of L are used as a basis for expressing various types of visual modules...
and constitutes a basic type of feature within the scale-space framework.
Examples of multi-scale feature detectors expressed within the scale-space framework
Following the idea of expressing visual operation in terms of differential invariants computed at multiple scales using Gaussian derivative operators, we can express an edge detectorEdge detection
Edge detection is a fundamental tool in image processing and computer vision, particularly in the areas of feature detection and feature extraction, which aim at identifying points in a digital image at which the image brightness changes sharply or, more formally, has discontinuities...
from the set of points that satisfy the requirement that the gradient magnitude
should assume a local maximum in the gradient direction
.By working out the differential geometry, it can be shown that this differential edge detector can equivalently be expressed from the zero-crossings of the second-order differential invariant
that satisfy the following sign condition on a third-order differential invariant:
Similarly, multi-scale blob detectors
Blob detection
In the area of computer vision, blob detection refers to visual modules that are aimed at detecting points and/or regions in the image that differ in properties like brightness or color compared to the surrounding...
at any given fixed scale can be obtained from local maxima and local minima of either the Laplacian operator (also referred to as the Laplacian of Gaussian)
or the determinant of the Hessian matrix
.In an analogous fashion, corner detectors and ridge and valley detectors can be expressed as local maxima, minima or zero-crossings of multi-scale differential invariants defined from Gaussian derivatives. The algebraic expressions for the corner and ridge detection operators are, however, somewhat more complex and the reader is referred to the articles on corner detection
Corner detection
Corner detection is an approach used within computer vision systems to extract certain kinds of features and infer the contents of an image. Corner detection is frequently used in motion detection, image registration, video tracking, image mosaicing, panorama stitching, 3D modelling and object...
and ridge detection
Ridge detection
The ridges of a smooth function of two variables is a set of curves whose points are, in one or more ways to be made precise below, local maxima of the function in at least one dimension. For a function of N variables, its ridges are a set of curves whose points are local maxima in N-1 dimensions...
for further details.
Scale-space operations have also been frequently used for expressing coarse-to-fine methods, in particular for tasks such as image matching
Image registration
Image registration is the process of transforming different sets of data into one coordinate system. Data may be multiple photographs, data from different sensors, from different times, or from different viewpoints. It is used in computer vision, medical imaging, military automatic target...
and for multi-scale image segmentation
Scale-space segmentation
Scale-space segmentation or multi-scale segmentation is a general framework for signal and image segmentation, based on the computation of image descriptors at multiple scales of smoothing.-One-dimensional hierarchical signal segmentation:...
.
Automatic scale selection and scale invariant feature detection
The theory presented so far describes a well-founded framework for representing image structures at multiple scales. In many cases it is, however, also necessary to select locally appropriate scales for further analysis. This need for scale selection originates from two major reasons; (i) real-world objects may have different size, and this size may be unknown to the vision system, and (ii) the distance between the object and the camera can vary, and this distance information may also be unknown a priori.A highly useful property of scale-space representation is that image representations can be made invariant to scales, by performing automatic local scale selection based on local maxima
Maxima and minima
In mathematics, the maximum and minimum of a function, known collectively as extrema , are the largest and smallest value that the function takes at a point either within a given neighborhood or on the function domain in its entirety .More generally, the...
(or minima) over scales of normalized derivative
Derivative
In calculus, a branch of mathematics, the derivative is a measure of how a function changes as its input changes. Loosely speaking, a derivative can be thought of as how much one quantity is changing in response to changes in some other quantity; for example, the derivative of the position of a...
s
where
is a parameter that is related to the dimensionality of the image feature. This algebraic expression for scale normalized Gaussian derivative operators originates from the introduction of -normalized derivatives according to and .It can be theoretically shown that a scale selection module working according to this principle will satisfy the following scale invariance property: if for a certain type of image feature a local maximum is assumed in a certain image at a certain scale
, then under a rescaling of the image by a scale factor the local maximum over scales in the rescaled image will be transformed to the scale level .Following this approach of gamma-normalized derivatives, it can be shown that different types of scale adaptive and scale invariant feature detectors
Feature detection
In computer vision and image processing the concept of feature detection refers to methods that aim at computing abstractions of image information and making local decisions at every image point whether there is an image feature of a given type at that point or not...
can be expressed for tasks such as blob detection
Blob detection
In the area of computer vision, blob detection refers to visual modules that are aimed at detecting points and/or regions in the image that differ in properties like brightness or color compared to the surrounding...
, corner detection
Corner detection
Corner detection is an approach used within computer vision systems to extract certain kinds of features and infer the contents of an image. Corner detection is frequently used in motion detection, image registration, video tracking, image mosaicing, panorama stitching, 3D modelling and object...
, ridge detection
Ridge detection
The ridges of a smooth function of two variables is a set of curves whose points are, in one or more ways to be made precise below, local maxima of the function in at least one dimension. For a function of N variables, its ridges are a set of curves whose points are local maxima in N-1 dimensions...
and edge detection
Edge detection
Edge detection is a fundamental tool in image processing and computer vision, particularly in the areas of feature detection and feature extraction, which aim at identifying points in a digital image at which the image brightness changes sharply or, more formally, has discontinuities...
(see the specific articles on these topics for in-depth descriptions of how these scale-invariant feature detectors are formulated).
Furthermore, the scale levels obtained from automatic scale selection can be used for determining regions of interest for subsequent affine shape adaptation
Affine shape adaptation
Affine shape adaptation is a methodology for iteratively adapting the shape of the smoothing kernels in an affine group of smoothing kernels to the local image structure in neighbourhood region of a specific image point...
to obtain affine invariant interest points or for determining scale levels for computing associated image descriptors, such as locally scale adapted N-jet
N-jet
An N-jet is the set of derivatives of a function f up to order N.Specifically, in the area of computer vision, the N-jet is usually computed from a scale-space representation L of the input image f, and the partial derivatives of L are used as a basis for expressing various types of visual modules...
s.
Recent work has shown that also more complex operations, such as scale-invariant object recognition
Object recognition
Object recognition in computer vision is the task of finding a given object in an image or video sequence. Humans recognize a multitude of objects in images with little effort, despite the fact that the image of the objects may vary somewhat in different view points, in many different sizes / scale...
can be performed in this way,
by computing local image descriptors (N-jets or local histograms of gradient directions) at scale-adapted interest points obtained from scale-space maxima of the normalized Laplacian operator (see also scale-invariant feature transform
Scale-invariant feature transform
Scale-invariant feature transform is an algorithm in computer vision to detect and describe local features in images. The algorithm was published by David Lowe in 1999....
).
Related multi-scale representations
An image pyramidPyramid (image processing)
Pyramid or pyramid representation is a type of multi-scale signal representation developed by the computer vision, image processing and signal processing communities, in which a signal or an image is subject to repeated smoothing and subsampling...
is a discrete representation in which a scale space is sampled in both space and scale. For scale invariance, the scale factors should be sampled exponentially, for example as integer powers of 2 or root 2. When properly constructed, the ratio of the sample rates in space and scale are held constant so that the impulse response is identical in all levels of the pyramid.
Fast, O(N), algorithms exist for computing a scale invariant image pyramid in which the image or signal is repeatedly smoothed then subsampled.
Values for scale space between pyramid samples can easily be estimated using interpolation within and between scales.
In a scale-space representation, the existence of a continuous scale parameter makes it possible to track zero crossings over scales leading to so-called deep structure.
For features defined as zero-crossings of differential invariant
Differential invariant
In mathematics, a differential invariant is an invariant for the action of a Lie group on a space that involves the derivatives of graphs of functions in the space. Differential invariants are fundamental in projective differential geometry, and the curvature is often studied from this point of view...
s, the implicit function theorem
Implicit function theorem
In multivariable calculus, the implicit function theorem is a tool which allows relations to be converted to functions. It does this by representing the relation as the graph of a function. There may not be a single function whose graph is the entire relation, but there may be such a function on...
directly defines trajectories
Trajectory
A trajectory is the path that a moving object follows through space as a function of time. The object might be a projectile or a satellite, for example. It thus includes the meaning of orbit—the path of a planet, an asteroid or a comet as it travels around a central mass...
across scales, and at those scales where bifurcation
Bifurcation
Bifurcation means the splitting of a main body into two parts.Bifurcation or Bifurcated may refer to:*Bifurcation , the division of issues in a trial for example the division of a page into two parts....
s occur, the local behaviour can be modelled by singularity theory
Singularity theory
-The notion of singularity:In mathematics, singularity theory is the study of the failure of manifold structure. A loop of string can serve as an example of a one-dimensional manifold, if one neglects its width. What is meant by a singularity can be seen by dropping it on the floor...
.
Extensions of linear scale-space theory concern the formulation of non-linear scale-space concepts more committed to specific purposes. These non-linear scale-spaces often start from the equivalent diffusion formulation of the scale-space concept, which is subsequently extended in a non-linear fashion. A large number of evolution equations have been formulated in this way, motivated by different specific requirements (see the abovementioned book references for further information). It should be noted, however, that not all of these non-linear scale-spaces satisfy similar "nice" theoretical requirements as the linear Gaussian scale-space concept. Hence, unexpected artifacts may sometimes occur and one should be very careful of not using the term "scale-space" for just any type of one-parameter family of images.
A first-order extension of the isotropic Gaussian scale-space is provided by the affine (Gaussian) scale-space. One motivation for this extension originates from the common need for computing image descriptors subject for real-world objects that are viewed under a perspective camera model. To handle such non-linear deformations locally, partial invariance (or more correctly covariance
Covariance
In probability theory and statistics, covariance is a measure of how much two variables change together. Variance is a special case of the covariance when the two variables are identical.- Definition :...
) to local affine deformations can be achieved by considering affine Gaussian kernels with their shapes determined by the local image structure, see the article on affine shape adaptation
Affine shape adaptation
Affine shape adaptation is a methodology for iteratively adapting the shape of the smoothing kernels in an affine group of smoothing kernels to the local image structure in neighbourhood region of a specific image point...
for theory and algorithms. Indeed, this affine scale-space can also be expressed from a non-isotropic extension of the linear (isotropic) diffusion equation, while still being within the class of linear partial differential equation
Partial differential equation
In mathematics, partial differential equations are a type of differential equation, i.e., a relation involving an unknown function of several independent variables and their partial derivatives with respect to those variables...
s.
There are strong relations between scale-space theory and wavelet theory, although these two notions of multi-scale representation have been developed from somewhat different premises.
There has also been work on other multi-scale approaches
Multi-scale approaches
The scale-space representation of a signal obtained by Gaussian smoothing satisfies a number of special properties, scale-space axioms, which make it into a special form of multi-scale representation. There are, however, also other types of multi-scale approaches in the areas of computer vision,...
, such as pyramids and a variety of other kernels, that do not exploit or require the same requirements as true scale-space descriptions do.
Relations to biological vision
There are interesting relations between scale-space representation and biological vision.Neurophysiological studies have shown that there are receptive field
Receptive field
The receptive field of a sensory neuron is a region of space in which the presence of a stimulus will alter the firing of that neuron. Receptive fields have been identified for neurons of the auditory system, the somatosensory system, and the visual system....
profiles in the mammalian retina
Retina
The vertebrate retina is a light-sensitive tissue lining the inner surface of the eye. The optics of the eye create an image of the visual world on the retina, which serves much the same function as the film in a camera. Light striking the retina initiates a cascade of chemical and electrical...
and visual cortex
Visual cortex
The visual cortex of the brain is the part of the cerebral cortex responsible for processing visual information. It is located in the occipital lobe, in the back of the brain....
,
which can be well modelled by linear Gaussian derivative operators, in some cases also complemented by a non-isotropic affine scale-space model and/or non-linear combinations of such linear operators.
Implementation issues
When implementing scale-space smoothing in practice there are a number of different approaches that can be taken in terms of continuous or discrete Gaussian smoothing, implementation in the Fourier domain, in terms of pyramids based on binomial filters that approximate the Gaussian or using recursive filters. More details about this are given in a separate article on scale-space implementation.See also
Complementary articles on specific sub-topics of scale-space:- scale-space axiomsScale-space axiomsIn 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...
- scale-space implementation
- scale-space segmentationScale-space segmentationScale-space segmentation or multi-scale segmentation is a general framework for signal and image segmentation, based on the computation of image descriptors at multiple scales of smoothing.-One-dimensional hierarchical signal segmentation:...
- multi-scale approachesMulti-scale approachesThe scale-space representation of a signal obtained by Gaussian smoothing satisfies a number of special properties, scale-space axioms, which make it into a special form of multi-scale representation. There are, however, also other types of multi-scale approaches in the areas of computer vision,...
Multi-scale feature detection within the scale-space framework:
- edge detectionEdge detectionEdge detection is a fundamental tool in image processing and computer vision, particularly in the areas of feature detection and feature extraction, which aim at identifying points in a digital image at which the image brightness changes sharply or, more formally, has discontinuities...
- blob detectionBlob detectionIn the area of computer vision, blob detection refers to visual modules that are aimed at detecting points and/or regions in the image that differ in properties like brightness or color compared to the surrounding...
- corner detectionCorner detectionCorner detection is an approach used within computer vision systems to extract certain kinds of features and infer the contents of an image. Corner detection is frequently used in motion detection, image registration, video tracking, image mosaicing, panorama stitching, 3D modelling and object...
- ridge detectionRidge detectionThe ridges of a smooth function of two variables is a set of curves whose points are, in one or more ways to be made precise below, local maxima of the function in at least one dimension. For a function of N variables, its ridges are a set of curves whose points are local maxima in N-1 dimensions...
- affine shape adaptationAffine shape adaptationAffine shape adaptation is a methodology for iteratively adapting the shape of the smoothing kernels in an affine group of smoothing kernels to the local image structure in neighbourhood region of a specific image point...
- interest point detectionInterest point detectionInterest point detection is a recent terminology in computer vision that refers to the detection of interest points for subsequent processing...
The Gaussian function and other smoothing or multi-scale approaches:
- Gaussian function
- Gaussian filterGaussian filterIn electronics and signal processing, a Gaussian filter is a filter whose impulse response is a Gaussian function. Gaussian filters are designed to give no overshoot to a step function input while minimizing the rise and fall time. This behavior is closely connected to the fact that the Gaussian...
- multi-scale approachesMulti-scale approachesThe scale-space representation of a signal obtained by Gaussian smoothing satisfies a number of special properties, scale-space axioms, which make it into a special form of multi-scale representation. There are, however, also other types of multi-scale approaches in the areas of computer vision,...
- wavelets
- anisotropic diffusionAnisotropic diffusionIn image processing and computer vision, anisotropic diffusion, also called Perona–Malik diffusion, is a technique aiming at reducing image noise without removing significant parts of the image content, typically edges, lines or other details that are important for the interpretation of the image...
- nonlinear scale space
- smoothingSmoothingIn statistics and image processing, to smooth a data set is to create an approximating function that attempts to capture important patterns in the data, while leaving out noise or other fine-scale structures/rapid phenomena. Many different algorithms are used in smoothing...
- pyramid (image processing)Pyramid (image processing)Pyramid or pyramid representation is a type of multi-scale signal representation developed by the computer vision, image processing and signal processing communities, in which a signal or an image is subject to repeated smoothing and subsampling...
- mipmapMipmapIn 3D computer graphics texture filtering, MIP maps are pre-calculated, optimized collections of images that accompany a main texture, intended to increase rendering speed and reduce aliasing artifacts. They are widely used in 3D computer games, flight simulators and other 3D imaging systems. The...
ping
More general articles on feature detection, computer vision and image processing:
- feature detection (computer vision)
- computer visionComputer visionComputer vision is a field that includes methods for acquiring, processing, analysing, and understanding images and, in general, high-dimensional data from the real world in order to produce numerical or symbolic information, e.g., in the forms of decisions...
- image processingImage processingIn electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...
External links
- Lindeberg, Tony, "Scale-space: A framework for handling image structures at multiple scales", In: Proc. CERN School of Computing, Egmond aan Zee, The Netherlands, 8-21 September, 1996 (online web tutorial)
- Lindeberg, Tony: Scale-space theory: A basic tool for analysing structures at different scales, in J. of Applied Statistics, 21(2), pp. 224–270, 1994 (longer pdf tutorial on scale-space)
- Lindeberg, Tony, "Principles for automatic scale selection", In: B. Jähne (et al., eds.), Handbook on Computer Vision and Applications, volume 2, pp 239--274, Academic Press, Boston, USA, 1999. (tutorial on approaches to automatic scale selection)
- Lindeberg, Tony: "Scale-space theory" In: Encyclopedia of Mathematics, (Michiel Hazewinkel, ed) Kluwer, 1997
- Powers of ten interactive Java tutorial at Molecular Expressions website
- On-line resource with space-time receptive fields of visual neurons provided by Izumi Ohzawa at Osaka University
- Web archive backup: Lecture on scale-space at the University of Massachusetts (pdf)
- Multiscale analysis for optimized vessel segmentation of fundus retina images Ph.D Thesis