Linear Scale-Space Theory from Physical Principles

In the past decades linear scale-space theory was derived on the basis of various axiomatics. In this paper we revisit these axioms and show that they merely coincide with the following physical principles, namely that the image domain is a Galilean space, that the total energy exchange between a region and its surrounding is preserved under linear filtering and that the physical observables should be invariant under the group of similarity transformations. These observables are elements of the similarity jet spanned by natural coordinates and differential energies read out by a vision system.Furthermore, linear scale-space theory is extended to spatio-temporal images on bounded and curved domains. Our theory permits a delay-operation at the present moment which is in agreement with the motion detection model of Reichardt. In this respect our theory deviates from that of Koenderink which requires additional syntactical operators to realise such a delay-operation.Finally, the semi-discrete and discrete linear scale-space theories are derived by discretising the continuous theories following the theory of stochastic processes. The relation and difference between our stochastic approach and that of Lindeberg is pointed out. The connection between continuous and (semi-)discrete sale-space theory for infinitely high scales observed by Lindeberg is refined by applying appropriate scaling limits. It is shown that Lindeberg's requirement of normalisation for one-dimensional discrete Green's functions can be incorporated into our theory for arbitrary dimensional discrete Green's functions, parameter determination can be avoided, and the requirement of operation at even and odd coordinates sum can be guaranteed simultaneously by taking a normalised linear combination of the identity operator and the first step discrete Green's functions. The new discrete Green's functions are still intimately related to the continuous Green's functions and appear to coincide with pyramidal discrete Green's functions.     

Generalized Gaussian Scale-Space Axiomatics Comprising Linear Scale-Space,Affine Scale-Space and Spatio-Temporal Scale-Space

This paper describes a generalized axiomatic scale-space theory that makes it possible to derive the notions of linear scale-space, affine Gaussian scale-space and linear spatio-temporal scale-space using a similar set of assumptions (scale-space axioms).     

Time-Causal and Time-Recursive Spatio-Temporal Receptive Fields

We present an improved model and theory for time-causal and time-recursive spatio-temporal receptive fields, obtained by a combination of Gaussian receptive fields over the spatial domain and first-order integrators or equivalently truncated exponential filters coupled in cascade over the temporal domain. Compared to previous spatio-temporal scale-space formulations in terms of non-enhancement of local extrema or scale invariance, these receptive fields are based on different scale-space axiomatics over time by ensuring non-creation of new local extrema or zero-crossings with increasing temporal scale. Specifically, extensions are presented about (i) parameterizing the intermediate temporal scale levels, (ii) analysing the resulting temporal dynamics, (iii) transferring the theory to a discrete implementation in terms of recursive filters over time, (iv) computing scale-normalized spatio-temporal derivative expressions for spatio-temporal feature detection and (v) computational modelling of receptive fields in the lateral geniculate nucleus (LGN) and the primary visual cortex (V1) in biological vision. We show that by distributing the intermediate temporal scale levels according to a logarithmic distribution, we obtain a new family of temporal scale-space kernels with better temporal characteristics compared to a more traditional approach of using a uniform distribution of the intermediate temporal scale levels. Specifically, the new family of time-causal kernels has much faster temporal response properties (shorter temporal delays) compared to the kernels obtained from a uniform distribution. When increasing the number of temporal scale levels, the temporal scale-space kernels in the new family do also converge very rapidly to a limit kernel possessing true self-similar scale-invariant properties over temporal scales. Thereby, the new representation allows for true scale invariance over variations in the temporal scale, although the underlying temporal scale-space representation is based on a discretized temporal scale parameter. We show how scale-normalized temporal derivatives can be defined for these time-causal scale-space kernels and how the composed theory can be used for computing basic types of scale-normalized spatio-temporal derivative expressions in a computationally efficient manner.     

Fast implementation of scale-space by interpolatory subdivisionscheme

While the scale-space approach has been widely used in computer vision, there has been a great interest in fast implementation of scale-space filtering. We introduce an interpolatory subdivision scheme (ISS) for this purpose. In order to extract the geometric features in a scale-space representation, discrete derivative approximations are usually needed. Hence, a general procedure is also introduced to derive exact formulae for numerical differentiation with respect to this ISS. Then, from ISS, an algorithm is derived for fast approximation of scale-space filtering. Moreover, the relationship between the ISS and the Whittaker-Shannon sampling theorem and the commonly used spline technique is discussed. As an example of the application of ISS technique, we present some examples on fast implementation of λτ-spaces as introduced by Gokmen and Jain (1997), which encompasses various famous edge detection filters. It is shown that the ISS technique demonstrates high performance in fast implementation of the scale-space filtering and feature extraction     

Scale-space for discrete signals

A basic and extensive treatment of discrete aspects of the scale-space theory is presented. A genuinely discrete scale-space theory is developed and its connection to the continuous scale-space theory is explained. Special attention is given to discretization effects, which occur when results from the continuous scale-space theory are to be implemented computationally. The 1D problem is solved completely in an axiomatic manner. For the 2D problem, the author discusses how the 2D discrete scale space should be constructed. The main results are as follows: the proper way to apply the scale-space theory to discrete signals and discrete images is by discretization of the diffusion equation, not the convolution integral; the discrete scale space obtained in this way can be described by convolution with the kernel, which is the discrete analog of the Gaussian kernel, a scale-space implementation based on the sampled Gaussian kernel might lead to undesirable effects and computational problems, especially at fine levels of scale; the 1D discrete smoothing transformations can be characterized exactly and a complete catalogue is given; all finite support 1D discrete smoothing transformations arise from repeated averaging over two adjacent elements (the limit case of such an averaging process is described); and the symmetric 1D discrete smoothing kernels are nonnegative and unimodal, in both the spatial and the frequency domain     

Morphological Counterparts of Linear Shift-Invariant Scale-Spaces

It is well-known that there are striking analogies between linear shift-invariant systems and morphological systems for image analysis. So far, however, the relations between both system theories are mainly understood on a pure convolution / erosion level. A formal connection on the level of differential or pseudodifferential equations and their induced scale-spaces is still missing. The goal of our paper is to close this gap. We present a simple and fairly general dictionary that allows to translate any linear shift-invariant evolution equation into its morphological counterpart and vice versa. It is based on a scale-space representation by means of the symbol of its (pseudo)differential operator. Introducing a novel transformation, the Cramér–Fourier transform, puts us in a position to relate the symbol to the structuring function of a morphological scale-space of Hamilton–Jacobi type. As an application of our general theory, we derive the morphological counterparts of many linear shift-invariant scale-spaces, such as the Poisson scale-space, \(\alpha \)-scale-spaces, summed \(\alpha \)-scale-spaces, relativistic scale-spaces, and their anisotropic variants. Our findings are illustrated by experiments.     

Differential and Integral Geometry of Linear Scale-Spaces

Linear scale-space theory provides a useful framework to quantify the differential and integral geometry of spatio-temporal input images. In this paper that geometry comes about by constructing connections on the basis of the similarity jets of the linear scale-spaces and by deriving related systems of Cartan structure equations. A linear scale-space is generated by convolving an input image with Green's functions that are consistent with an appropriate Cauchy problem. The similarity jet consists of those geometric objects of the linear scale-space that are invariant under the similarity group. The constructed connection is assumed to be invariant under the group of Euclidean movements as well as under the similarity group. This connection subsequently determines a system of Cartan structure equations specifying a torsion two-form, a curvature two-form and Bianchi identities. The connection and the covariant derivatives of the curvature and torsion tensor then completely describe a particular local differential geometry of a similarity jet. The integral geometry obtained on the basis of the chosen connection is quantified by the affine translation vector and the affine rotation vectors, which are intimately related to the torsion two-form and the curvature two-form, respectively. Furthermore, conservation laws for these vectors form integral versions of the Bianchi identities. Close relations between these differential geometric identities and integral geometric conservation laws encountered in defect theory and gauge field theories are pointed out. Examples of differential and integral geometries of similarity jets of spatio-temporal input images are treated extensively.     

Regularization, Scale-Space, and Edge Detection Filters

Computational vision often needs to deal with derivatives ofdigital images. Such derivatives are not intrinsic properties ofdigital data; a paradigm is required to make them well-defined.Normally, a linear filtering is applied. This can be formulated interms of scale-space, functional minimization, or edge detectionfilters. The main emphasis of this paper is to connect these theoriesin order to gain insight in their similarities and differences. We donot want, in this paper, to take part in any discussion of how edgedetection must be performed, but will only link some of the current theories. We take regularization (or functional minimization) as astarting point, and show that it boils down to Gaussian scale-space ifwe require scale invariance and a semi-group constraint to besatisfied. This regularization implies the minimization of afunctional containing terms up to infinite order of differentiation.If the functional is truncated at second order, the Canny-Deriche filter arises. It is also shown that higher dimensional regularizationboils down to a rotated version of the one dimensional case, whenCartesian invariance is imposed and the image is vanishing at theborders. This means that the results from 1D regularization can beeasily generalized to higher dimensions. Finally we show how anefficient implementation of regularization of order n can be made byrecursive filtering using 2n multiplications and additions peroutput element without introducing any approximation.     

Scale-space from nonlinear filters

Decomposition by extrema is put into the context of linear vision systems and scale-space. It is proved that discrete one-dimensional, M- and N-sieves neither introduce new edges as the scale increases nor create new extrema. They share this property with diffusion based filters. They are robust and preserve edges of large scale features     

The Monogenic Scale-Space: A Unifying Approach to Phase-Based Image Processing in Scale-Space

In this paper we address the topics of scale-space and phase-based image processing in a unifying framework. In contrast to the common opinion, the Gaussian kernel is not the unique choice for a linear scale-space. Instead, we chose the Poisson kernel since it is closely related to the monogenic signal, a 2D generalization of the analytic signal, where the Riesz transform replaces the Hilbert transform. The Riesz transform itself yields the flux of the Poisson scale-space and the combination of flux and scale-space, the monogenic scale-space, provides the local features phase-vector and attenuation in scale-space. Under certain assumptions, the latter two again form a monogenic scale-space which gives deeper insight to low-level image processing. In particular, we discuss edge detection by a new approach to phase congruency and its relation to amplitude based methods, reconstruction from local amplitude and local phase, and the evaluation of the local frequency.     

Characterization of the linear weighted sum decision principle

Recently the multicriterion decision problem (MCDP) has attracted more and more attention, and many decision principles have been proposed for it, among which the linear weighted sum decision principle is the most widely used. This paper discusses an axiomatic characterization of that principle to find out its essential meaning. Firstly, we give an axiomatic system characterizing it. Secondly, we examine the meanings of the axioms. Thirdly, we try to give a logical explanation of why the linear weighted sum decision principle is so popular by comparing it with other decision principles for the MCDP and for decision making under uncertainty. Finally, we investigate whether or not decision principles for the MCDP are applicable to decision making under uncertainty and vice versa.     

Coherence-Enhancing Diffusion Filtering

The completion of interrupted lines or the enhancement of flow-like structures is a challenging task in computer vision, human vision, and image processing. We address this problem by presenting a multiscale method in which a nonlinear diffusion filter is steered by the so-called interest operator (second-moment matrix, structure tensor). An m-dimensional formulation of this method is analysed with respect to its well-posedness and scale-space properties. An efficient scheme is presented which uses a stabilization by a semi-implicit additive operator splitting (AOS), and the scale-space behaviour of this method is illustrated by applying it to both 2-D and 3-D images.     

Exploring and exploiting the structure of saddle points in Gaussian scale space

When an image is filtered with a Gaussian of width σ and σ is considered as an extra dimension, the image is extended to a Gaussian scale-space (GSS) image. In earlier work it was shown that the GSS-image contains an intensity-based hierarchical structure that can be represented as a binary ordered rooted tree. Key elements in the construction of the tree are iso-intensity manifolds and scale-space saddles.A scale-space saddle is a critical point in scale space. When it connects two different parts of an iso-intensity manifold, it is called “dividing”, otherwise it is called “void”. Each dividing scale-space saddle is connected to an extremum in the original image via a curve in scale space containing critical points. Using the nesting of the iso-intensity manifolds in the GSS-image and the dividing scale-space saddles, each extremum is connected to another extremum. In the tree structure, the dividing scale-space saddles form the connecting elements in the hierarchy: they are the nodes of the tree. The extrema of the image form the leaves, while the critical curves are represented as the edges.To identify the dividing scale-space saddles, a global investigation of the scale-space saddles and the iso-intensity manifolds through them is needed.In this paper an overview of the situations that can occur is given. In each case it is shown how to distinguish between void and dividing scale-space saddles. Furthermore, examples are given, and the difference between selecting the dividing and the void scale-space saddles is shown. Also relevant geometric properties of GSS images are discussed, as well as their implications for algorithms used for the tree extraction.As main result, it is not necessary to search through the whole GSS image to find regions related to each relevant scale-space saddle. This yields a considerable reduction in complexity and computation time, as shown in two examples.     

Linear Neural Circuitry Model for Visual Receptive Fields

The current state of art in the literature indicates that linear visual receptive fields are Gaussian or formed based on Gaussian kernels in biological visual systems. In this paper, by employing hypotheses based on the anatomy and physiology of vertebrate biological vision, we propose a neural circuitry possessing Gaussian-related visual receptive fields. Here, we present a plausible circuitry system matching the characteristic properties of an ideal visual front end of biological visual systems and then present a condition under which this circuit demonstrates a linear behaviour to model the linear receptive fields observed in the biological experimental data. The objective of this study is to understand the hardware circuitry from which various visual receptive fields in biological visual system can be deduced. In our model, a nonlinear neural network communicating with spikes is considered. The condition under which this neural network behaves linearly is discussed. The equivalent linear circuit proposed here employs some anatomical and physiological properties of the early biological visual pathway to derive the visual receptive field profiles for linear cells such as neurons with isotropic separable, non-isotropic separable and non-separable (velocity-adapted) Gaussian receptive fields in the LGN and striate cortex. In the model presented here, the theory of transmission lines for linear distributed electrical circuits is employed for two-dimensional transmission grids to model cell connectivities in a neural layer. The model presented here leads to a formulation similar to the Gaussian scale-space theory for the transmission of visual signals through various layers of neurons. Our model therefore presents a new insight on how the convolution process with Gaussian kernels can be implemented in vertebrate visual systems. The comparison of the numerical simulations of our model presented in this paper with the data analysis of receptive field profiles recorded in the biological literature demonstrates a complete agreement between our theoretical model and experimental data. Our model is also in good agreement with the numerical results of the Gaussian scale-space theory for the visual receptive fields.     

A Survey of Urban Reconstruction

This paper provides a comprehensive overview of urban reconstruction. While there exists a considerable body of literature, this topic is still under active research. The work reviewed in this survey stems from the following three research communities: computer graphics, computer vision and photogrammetry and remote sensing. Our goal is to provide a survey that will help researchers to better position their own work in the context of existing solutions, and to help newcomers and practitioners in computer graphics to quickly gain an overview of this vast field. Further, we would like to bring the mentioned research communities to even more interdisciplinary work, since the reconstruction problem itself is by far not solved.     

The convergence of graphics and vision

Computer graphics and computer vision are inverse problems. Traditional computer graphics starts with input geometric models and produces image sequences. Traditional computer vision starts with input image sequences and produces geometric models. Lately, there has been a meeting in the middle, and the center, the prize, is to create stunning images in real time. Vision researchers now work from images backward, just as far backward as necessary to create models that capture a scene without going to full geometric models. Graphics researchers now work with hybrid geometry and image models. Approaching similar problems from opposite directions, graphics and vision researchers are reaching a fertile middle ground. The goal is to find the best possible tools for the imagination. This overview describes cutting edge work, some of which will debut at Siggraph 98     

An axiomatic semantics for the synchronous language Gentzen

We propose an axiomatic semantics for the synchronous language Gentzen, which is an instantiation of the paradigm Timed Concurrent Constraint Programming proposed by Saraswat, Jagadeesan and Gupta. We view Gentzen as a prototype of the class of state-oriented synchronous languages, since it offers the basic constructs that are shared by the languages in the class. Since synchronous concurrency cannot be simulated by arbitrary interleaving, we cannot exploit “head normal forms”, on which axiomatic theories for asynchronous process calculi are based. We suggest how axiomatic semantics for other state-oriented synchronous languages can be obtained by expressing constructs of such languages in terms of Gentzen constructs.     

Rapid Anisotropic Diffusion Using Space-Variant Vision

Many computer and robot vision applications require multi-scale image analysis. Classically, this has been accomplished through the use of a linear scale-space, which is constructed by convolution of visual input with Gaussian kernels of varying size (scale). This has been shown to be equivalent to the solution of a linear diffusion equation on an infinite domain, as the Gaussian is the Green's function of such a system (Koenderink, 1984). Recently, much work has been focused on the use of a variable conductance function resulting in anisotropic diffusion described by a nonlinear partial differential equation (PDE). The use of anisotropic diffusion with a conductance coefficient which is a decreasing function of the gradient magnitude has been shown to enhance edges, while decreasing some types of noise (Perona and Malik, 1987). Unfortunately, the solution of the anisotropic diffusion equation requires the numerical integration of a nonlinear PDE which is a costly process when carried out on a uniform mesh such as a typical image. In this paper we show that the complex log transformation, variants of which are universally used in mammalian retino-cortical systems, allows the nonlinear diffusion equation to be integrated at exponentially enhanced rates due to the nonuniform mesh spacing inherent in the log domain. The enhanced integration rates, coupled with the intrinsic compression of the complex log transformation, yields a speed increase of between two and three orders of magnitude, providing a means of performing rapid image enhancement using anisotropic diffusion.