 Scale space implementation

Scalespace Scalespace axioms Scalespace implementation Feature detection Edge detection Blob detection Corner detection Ridge detection Interest point detection Scale selection Affine shape adaptation Scalespace segmentation The linear scale space representation of an Ndimensional continuous signal is obtained by convolving f_{C} with an Ndimensional Gaussian kernel
However, for implementation, this definition is impractical, since it is continuous. When applying the scale space concept to a discrete signal f_{D}, different approaches can be taken. This article is a brief summary of some of the most frequently used methods.
Contents
Separability
Using the separability property of the Gaussian kernel
the Ndimensional convolution operation can be decomposed into a set of separable smoothing steps with a onedimensional Gaussian kernel G along each dimension
where
and the standard deviation of the Gaussian σ is related to the scale parameter t according to t = σ^{2}.
Separability will be assumed in all that follows, even when the kernel is not exactly Gaussian, since separation of the dimensions is the most practical way to implement multidimensional smoothing, especially at larger scales. Therefore, the rest of the article focuses on the onedimensional case.
The sampled Gaussian kernel
When implementing the onedimensional smoothing step in practice, the presumably simplest approach is to convolve the discrete signal f_{D} with a sampled Gaussian kernel:
where
(with t = σ^{2}) which in turn is truncated at the ends to give a filter with finite impulse response
for M chosen sufficiently large (see error function) such that
 .
A common choice is to set M to a constant C times the standard deviation of the Gaussian kernel
where C is often chosen somewhere between 3 and 6.
Using the sampled Gaussian kernel can, however, lead to implementation problems, in particular when computing higherorder derivatives at finer scales by applying sampled derivatives of Gaussian kernels. When accuracy and robustness are primary design criteria, alternative implementation approaches should therefore be considered.
For small values of ε (10 ^{− 6} to 10 ^{− 8}) the errors introduced by truncating the Gaussian are usually negligible. For larger values of ε, however, there are many better alternatives to a rectangular window function. For example, for a given number of points, a Hamming window, Blackman window, or Kaiser window will do less damage to the spectral and other properties of the Gaussian than a simple truncation will. Nonwithstanding this, since the Gaussian kernel decreases rapidly at the tails, the main recommendation is still to use a sufficiently small value of ε such that the truncation effects are no longer important.
The discrete Gaussian kernel
A more refined approach is to convolve the original signal by the discrete Gaussian kernel T(n,t)^{[1]}^{[2]}
where
and I_{n}(t) denotes the modified Bessel functions of integer order. This is the discrete analog of the continuous Gaussian in that it is the solution to the discrete diffusion equation (discrete space, continuous time), just as the continuous Gaussian is the solution to the continuous diffusion equation.
This filter can be truncated in the spatial domain as for the sampled Gaussian
or can be implemented in the Fourier domain using a closedform expression for its discretetime Fourier transform:
 .
With this frequencydomain approach, the scalespace properties transfer exactly to the discrete domain, or with excellent approximation using periodic extension and a suitably long discrete Fourier transform to approximate the discretetime Fourier transform of the signal being smoothed. Moreover, higherorder derivative approximations can be computed in a straightforward manner (and preserving scalespace properties) by applying small support central difference operators to the discrete scalespace representation.^{[3]}
As with the sampled Gaussian, a plain truncation of the infinite impulse response will in most cases be a sufficient approximation for small values of ε, while for larger values of ε it is better to use either a decomposition of the discrete Gaussian into a cascade of generalized binomial filters or alternatively to construct a finite approximate kernel by multiplying by a window function. If ε has been chosen too large such that effects of the truncation error begin to appear (for example as spurious extrema or spurious responses to higherorder derivative operators), then the options are to decrease the value of ε such that a larger finite kernel is used, with cutoff where the support is very small, or to use a tapered window.
Recursive filters
Since computational efficiency is often important, loworder recursive filters are often used for scalespace smoothing. For example, Young and van Vliet^{[4]} use a thirdorder recursive filter with one real pole and a pair of complex poles, applied forward and backward to make a sixthorder symmetric approximation to the Gaussian with low computational complexity for any smoothing scale.
By relaxing a few of the axioms, Lindeberg^{[1]} concluded that good smoothing filters would be "normalized Pólya frequency sequences", a family of discrete kernels that includes all filters with real poles at 0 < Z < 1 and/or Z > 1, as well as with real zeros at Z < 0. For symmetry, which leads to approximate directional homogeneity, these filters must be further restricted to pairs of poles and zeros that lead to zerophase filters.
To match the transfer function curvature at zero frequency of the discrete Gaussian, which ensures an approximate semigroup property of additive t, two poles at can be applied forward and backwards, for symmetry and stability. This filter is the simplest implementation of a normalized Pólya frequency sequence kernel that works for any smoothing scale, but it is not as excellent an approximation to the Gaussian as Young and van Vliet's filter, which is not normalized Pólya frequency sequence, due to its complex poles.
The transfer function H_{1} of a symmetric polepair recursive filter is closely related to the discretetime Fourier transform of the discrete Gaussian kernel via firstorder approximation of the exponential:

 where the t parameter here is related to the stable pole position Z = p via t = 2p / (1 − p)^{2}.
Furthermore, such filters with N pairs of poles, such as the two pole pairs illustrated in this section, are an even better approximation to the exponential:

 where the stable pole positions are adjusted by solving t / N = 2p / (1 − p)^{2}.
The impulse responses of these filters are not very close to gaussian unless more than two pole pairs are used. However, even with only one or two pole pairs per scale, a signal successively smoothed at increasing scales will be very close to a gaussiansmoothed signal. The semigroup property is poorly approximated when too few pole pairs are used.
Scalespace axioms that are still satisfied by these filters are:
 linearity
 shift invariance (integer shifts)
 noncreation of local extrema (zerocrossings) in one dimension
 nonenhancement of local extrema in any number of dimensions
 positivity
 normalization
The following are only approximately satisfied, the approximation being better for larger numbers of pole pairs:
 existence of an infinitesimal generator A (the infinitesimal generator of the discrete Gaussian, or a filter approximating it, approximately maps a recursive filter response to one of infinitesimally larger t )
 the semigroup structure with the associated cascade smoothing property (this property is approximated by considering kernels to be equivalent when they have the same t value, even if they are not quite equal)
 rotational symmetry
 scale invariance
This recursive filter method and variations to compute both the Gaussian smoothing as well as Gaussian derivatives has been described by several authors.^{[4]}^{[5]}^{[6]}^{[7]} Tan et al. have analyzed and compared some of these approaches, and have pointed out that the Young and van Vliet filters are a cascade (multiplication) of forward and backward filters, while the Deriche and the Jin et al. filters are sums of forward and backward filters.^{[8]}
At fine scales, the recursive filtering approach as well as other separable approaches are not guaranteed to give the best possible approximation to rotational symmetry, so nonseparable implementations for twodimensional images may be considered as an alternative.
When computing several derivatives in the Njet simultaneously, discrete scalespace smoothing with the discrete analogue of the Gaussian kernel, or with a recursive filter approximation, followed by small support difference operators, may be both faster and more accurate than computing recursive approximations of each derivative operator.
Finiteimpulseresponse (FIR) smoothers
For small scales, a loworder FIR filter may be a better smoothing filter than a recursive filter. The symmetric 3kernel , for smooths to a scale of t using a pair of real zeros at Z < 0, and approaches the discrete Gaussian in the limit of small t. In fact, with infinitesimal t, either this twozero filter or the twopole filter with poles at Z = t / 2 and Z = 2 / t can be used as the infinitesimal generator for the discrete Gaussian kernels described above.
The FIR filter's zeros can be combined with the recursive filter's poles to make a general highquality smoothing filter. For example, if the smoothing process is to always apply a biquadratic (twopole, twozero) filter forward then backwards on each row of data (and on each column in the 2D case), the poles and zeros can each do a part of the smoothing. The zeros limit out at t = 0.5 per pair (zeros at Z = –1), so for large scales the poles do most of the work. At finer scales, the combination makes an excellent approximation to the discrete Gaussian if the poles and zeros each do about half the smoothing. The t values for each portion of the smoothing (poles, zeros, forward and backward multiple applications, etc.) are additive, in accordance with the approximate semigroup property.
The FIR filter transfer function is closely related to the discrete Gaussian's DTFT, just as was the recursive filter's. For a single pair of zeros, the transfer function is

 where the t parameter here is related to the zero positions Z = z via t = − 2z / (1 − z)^{2}, and we require to keep the transfer function nonnegative.
Furthermore, such filters with N pairs of zeros, are an even better approximation to the exponential and extend to higher values of t :

 where the stable zero positions are adjusted by solving t / N = − 2z / (1 − z)^{2}.
These FIR and polezero filters are valid scalespace kernels, satisfying the same axioms as the allpole recursive filters.
Realtime implementation within pyramids and discrete approximation of scalenormalized derivatives
Regarding the topic of automatic scale selection based on normalized derivatives, pyramid approximations are frequently used to obtain realtime performance^{[9]}^{[10]}^{[11]}. The appropriateness of approximating scalespace operations within a pyramid originates from the fact that repeated cascade smoothing with generalized binomial kernels leads to equivalent smoothing kernels that under reasonable conditions approach the Gaussian. Furthermore, the binomial kernels (or more generally the class of generalized binomial kernels) can be shown to constitute the unique class of finitesupport kernels that guarantee noncreation of local extrema or zerocrossings with increasing scale (see the article on multiscale approaches for details). Special care may, however, need to be taken to avoid discretization artifacts.
Other multiscale approaches
For onedimensional kernels, there is a welldeveloped theory of multiscale approaches, concerning filters that do not create new local extrema or new zerocrossings with increasing scales. For continuous signals, filters with real poles in the splane are within this class, while for discrete signals the abovedescribed recursive and FIR filters satisfy these criteria. Combined with the strict requirement of a continuous semigroup structure, the continuous Gaussian and the discrete Gaussian constitute the unique choice for continuous and discrete signals.
There are many other multiscale signal processing, image processing and data compression techniques, using wavelets and a variety of other kernels, that do not exploit or require the same requirements as scalespace descriptions do; that is, they do not depend on a coarser scale not generating a new extremum that was not present at a finer scale (in 1D) or nonenhancement of local extrema between adjacent scale levels (in any number of dimensions).
See also
References
 ^ ^{a} ^{b} Lindeberg, T., "Scalespace for discrete signals," PAMI(12), No. 3, March 1990, pp. 234254.
 ^ R.A. Haddad and A.N. Akansu, "A Class of Fast Gaussian Binomial Filters for Speech and Image Processing," IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 39, pp 723727, March 1991.
 ^ Lindeberg, T. Discrete derivative approximations with scalespace properties: A basis for lowlevel feature extraction, J. of Mathematical Imaging and Vision, 3(4), pp. 349376, 1993.
 ^ ^{a} ^{b} Ian T. Young and Lucas J. van Vliet (1995). "Recursive implementation of the Gaussian filter". Signal Processing (Elsevier) 44 (2): pp. 139–151. doi:10.1016/01651684(95)00020E. http://citeseer.ist.psu.edu/young95recursive.html.
 ^ Deriche, R: Recursively implementing the Gaussian and its derivatives, INRIA Research Report 1893, 1993.
 ^ Richard F. Lyon. "Speech recognition in scale space," Proc. of 1987 ICASSP. San Diego, March, pp. 29.3.14, 1987.
 ^ Jin, JS, Gao Y. "Recursive implementation of LoG Filtering". RealTime Imaging 1997;3:59–65.
 ^ . Sovira Tan, Jason L. Dale, and Alan Johnston (2003). "Performance of three recursive algorithms for fast spacevariant Gaussian filtering". RealTime Imaging 9 (3): 215–228. doi:10.1016/S10772014(03)000408.
 ^ Lindeberg, Tony and Bretzner, Lars (2003). "Realtime scale selection in hybrid multiscale representations". Proc. ScaleSpace'03, Springer Lecture Notes in Computer Science. Lecture Notes in Computer Science 2695: 148–163. doi:10.1007/3540449353_11. ISBN 9783540403685. http://www.nada.kth.se/cvap/abstracts/cvap279.html.
 ^ Crowley, J, Riff O: Fast computation of scale normalised Gaussian receptive fields, Proc. ScaleSpace'03, Isle of Skye, Scotland, Springer Lecture Notes in Computer Science, volume 2695, 2003.
 ^ Lowe, D. G., “Distinctive image features from scaleinvariant keypoints”, International Journal of Computer Vision, 60, 2, pp. 91110, 2004.
Categories:
Wikimedia Foundation. 2010.