Search

This paper introduces Fourier-approximated Lie algebras for shooting (FLASH), a fast geodesic shooting algorithm for diffeomorphic image registration. We approximate the infinite-dimensional Lie algebra of smooth vector fields, i.e., the tangent space at the identity of the diffeomorphism group, with a low-dimensional, bandlimited space. We show that most of the computations for geodesic shooting can be carried out entirely in this low-dimensional space. Our algorithm results in dramatic savings in time and memory over traditional large-deformation diffeomorphic metric mapping algorithms, which require dense spatial discretizations of vector fields. To validate the effectiveness of FLASH, we run pairwise image registration on both 2D synthetic data and real 3D brain images and compare with the state-of-the-art geodesic shooting methods. Experimental results show that our algorithm dramatically reduces the computational cost and memory footprint of diffemorphic image registration with little or no loss of accuracy. [ABSTRACT FROM AUTHOR]

For over 30 years, Blum's Medial Axis Transform (MAT) has proven to be an intriguing tool for analyzing and computing with form, but it is one that is notoriously difficult to apply in a robust and stable way. It is well documented how a tiny change to an object's boundary can cause a large change in its MAT. There has also been great difficulty in using the MAT to decompose an object into a hierarchy of parts reflecting the natural parts-hierarchy that we perceive. This paper argues that the underlying cause of these problems is that medial representations embody both the substance of each part of an object and the connections between adjacent parts. A small change in an object's boundary corresponds to a small change in its substance but may involve a large change in its connection information. The problems with Blum's MAT are generated because it does not explicitly represent this dichotomy of information. To use the Blum MAT to it's full potential, this paper presents a method for separating the substance and connection information of an object. This provides a natural parts-hierarchy while eliminating instabilities due to small boundary changes. The method also allows for graded, fuzzy classifications of object parts to match the ambiguity in human perception of many objects. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of fast and efficient indexing techniques for sequences evolving in non-Euclidean spaces. This problem has several applications in the areas of human activity analysis, where there is a need to perform fast search, and recognition in very high dimensional spaces. The problem is made more challenging when representations such as landmarks, contours, and human skeletons etc. are naturally studied in a non-Euclidean setting where even simple operations are much more computationally intensive than their Euclidean counterparts. We propose a geometry and data adaptive symbolic framework that is shown to enable the deployment of fast and accurate algorithms for activity recognition, dynamic texture recognition, motif discovery. Toward this end, we present generalizations of key concepts of piece-wise aggregation and symbolic approximation for the case of non-Euclidean manifolds. We show that one can replace expensive geodesic computations with much faster symbolic computations with little loss of accuracy in activity recognition and discovery applications. The framework is general enough to work across both Euclidean and non-Euclidean spaces, depending on appropriate feature representations without compromising on the ultra-low bandwidth, high speed and high accuracy. The proposed methods are ideally suited for real-time systems and low complexity scenarios. [ABSTRACT FROM AUTHOR]

This paper presents a generalized version of the classic projective reconstruction theorem which helps to choose or assess depth constraints for projective depth estimation algorithms. The theorem shows that projective reconstruction is possible under a much weaker constraint than requiring all estimated projective depths to be nonzero. This result enables us to present classes of depth constraints under which any reconstruction of cameras and points projecting into given image points is projectively equivalent to the true camera-point configuration. It also completely specifies the possible wrong configurations allowed by other constraints. We demonstrate the application of the theorem by analysing several constraints used in the literature, as well as presenting new constraints with desirable properties. We mention some of the implications of our results on iterative depth estimation algorithms and projective reconstruction via rank minimization. Our theory is verified by running experiments on both synthetic and real data. [ABSTRACT FROM AUTHOR]

In this paper, we propose a complete framework for 3D geometry modeling and processing that uses only fast geodesic computations. The basic building block for these techniques is a novel greedy algorithm to perform a uniform or adaptive remeshing of a triangulated surface. Our other contributions include a parameterization scheme based on barycentric coordinates, an intrinsic algorithm for computing geodesic centroidal tessellations, and a fast and robust method to flatten a genus-0 surface patch. On large meshes (more than 500,000 vertices), our techniques speed up computation by over one order of magnitude in comparison to classical remeshing and parameterization methods. Our methods are easy to implement and do not need multilevel solvers to handle complex models that may contain poorly shaped triangles. [ABSTRACT FROM AUTHOR]

The problem of projective reconstruction by minimization of the 2D reprojection error in multiple images is considered. Although bundle adjustment techniques can be used to minimize the 2D reprojection error, these methods being based on nonlinear optimization algorithms require a good starting point. Quasi-linear algorithms with better global convergence properties can be used to generate an initial solution before submitting it to bundle adjustment for refinement. In this paper, we propose a factorization-based method to integrate the initial search as well as the bundle adjustment into a single algorithm consisting of a sequence of weighted least-squares problems, in which a control parameter is initially set to a relaxed state to allow the search of a good initial solution, and subsequently tightened up to force the final solution to approach a minimum point of the 2D reprojection error. The proposed algorithm is guaranteed to converge. Our method readily handles images with missing points. [ABSTRACT FROM AUTHOR]

In this paper we discuss how to define a scale space suitable for temporal measurements. We argue that such a temporal scale space should possess the properties of: temporal causality, linearity, continuity, positivity, recursitivity as well as translational and scaling covariance. It is shown that these requirements imply a one parameter family of convolution kernels. Furthermore it is shown that these measurements can be realized in a time recursive way, with the current data as input and the temporal scale space as state, i.e. there is no need for storing earlier input. This family of measurement processes contains the diffusion equation on the half line (that represents the temporal scale) with the input signal as boundary condition on the temporal axis. The diffusion equation is unique among the measurement processes in the sense that it is preserves positivity (in the scale domain) and is locally generated. A numerical scheme is developed and relations to other approaches are discussed. [ABSTRACT FROM AUTHOR]

Local image features or interest points provide compact and abstract representations of patterns in an image. In this paper, we extend the notion of spatial interest points into the spatio-temporal domain and show how the resulting features often reflect interesting events that can be used for a compact representation of video data as well as for interpretation of spatio-temporal events. To detect spatio-temporal events, we build on the idea of the Harris and Förstner interest point operators and detect local structures in space-time where the image values have significant local variations in both space and time. We estimate the spatio-temporal extents of the detected events by maximizing a normalized spatio-temporal Laplacian operator over spatial and temporal scales. To represent the detected events, we then compute local, spatio-temporal, scale-invariant N-jets and classify each event with respect to its jet descriptor. For the problem of human motion analysis, we illustrate how a video representation in terms of local space-time features allows for detection of walking people in scenes with occlusions and dynamic cluttered backgrounds. [ABSTRACT FROM AUTHOR]

We study the connections between discrete one-dimensional schemes for nonlinear diffusion and shift-invariant Haar wavelet shrinkage. We show that one step of a (stabilised) explicit discretisation of nonlinear diffusion can be expressed in terms of wavelet shrinkage on a single spatial level. This equivalence allows a fruitful exchange of ideas between the two fields. In this paper we derive new wavelet shrinkage functions from existing diffusivity functions, and identify some previously used shrinkage functions as corresponding to well known diffusivities. We demonstrate experimentally that some of the diffusion-inspired shrinkage functions are among the best for translation-invariant multiscale wavelet denoising. Moreover, by transferring stability notions from diffusion filtering to wavelet shrinkage, we derive conditions on the shrinkage function that ensure that shift invariant single-level Haar wavelet shrinkage is maximum–minimum stable, monotonicity preserving, and variation diminishing. [ABSTRACT FROM AUTHOR]

In this paper we present a novel method to implement the monogenic scale space on a rectangular domain. The monogenic scale space is a vector valued scale space based on the Poisson scale space, which establishes a sophisticated alternative to the Gaussian scale space. Previous implementations of the monogenic scale space are Fourier transform based, and therefore suffer from the implicit periodicity in case of finite domains. The features of the monogenic scale space, including local amplitude, local phase, local orientation, local frequency, and phase congruency, are much easier to interpret in terms of image features evolving through scale than in the Gaussian case. Furthermore, applying results from harmonic analysis, relations between the features are obtained which improve the understanding of image analysis. As applications, we present a very simple but still accurate approach to image reconstruction from local amplitude and local phase and a method for extracting the evolution of lines and edges through scale. [ABSTRACT FROM AUTHOR]

Linear scale space methodology uses Gaussian probes at scale s to observe the differential structure. In observing the differential image structure through the Gaussian derivative probes at scale s we implicitly construct the Taylor series expansion of the smoothed image. The Gaussian facet model, as a generalization of the classic Haralick facet model, constructs a polynomial approximation of the unsmoothed image. The measured differential structure therefore is closer to the ‘real’ structure than the differential structure measured using Gaussian derivatives. At the points in an image where the differential structure changes abruptly (because of discontinuities in the imaging conditions, e.g. a material change, or a depth discontinuity) both the Gaussian derivatives and the Gaussian facet model diffuse the information from both sides of the discontinuity (smoothing across the edge). Robust estimators that are classically meant to deal with statistical outliers can also be used to deal with these ‘mixed model distributions’. In this paper we introduce the robust estimators of local image structure. Starting with the Gaussian facet model where we replace the quadratic error norm with a robust (Gaussian) error norm leads to a robust Gaussian facet model. We will show examples of using the robust differential structure estimators for luminance and color images, for zero and higher order differential structure. Furthermore we look at a ‘robustified’ structure tensor that forms the basis of robust orientation estimation. [ABSTRACT FROM AUTHOR]

In Part I of this paper we developed the theory and algorithms for performing Shape-From-Silhouette (SFS) across time. In this second part, we show how our temporal SFS algorithms can be used in the applications of human modeling and markerless motion tracking. First we build a system to acquire human kinematic models consisting of precise shape (constructed using the temporal SFS algorithm for rigid objects), joint locations, and body part segmentation (estimated using the temporal SFS algorithm for articulated objects). Once the kinematic models have been built, we show how they can be used to track the motion of the person in new video sequences. This marker-less tracking algorithm is based on the Visual Hull alignment algorithm used in both temporal SFS algorithms and utilizes both geometric (silhouette) and photometric (color) information. [ABSTRACT FROM AUTHOR]

Following a recent work by Y. Meyer, decomposition models into a geometrical component and a textured component have recently been proposed in image processing. In such approaches, negative Sobolev norms have seemed to be useful to modelize oscillating patterns. In this paper, we compare the properties of various norms that are dual of Sobolev or Besov norms. We then propose a decomposition model which splits an image into three components: a first one containing the structure of the image, a second one the texture of the image, and a third one the noise. Our decomposition model relies on the use of three different semi-norms: the total variation for the geometrical component, a negative Sobolev norm for the texture, and a negative Besov norm for the noise. We illustrate our study with numerical examples. [ABSTRACT FROM AUTHOR]

Blum's medial axes have great strengths, in principle, in intuitively describing object shape in terms of a quasi-hierarchy of figures. But it is well known that, derived from a boundary, they are damagingly sensitive to detail in that boundary. The development of notions of spatial scale has led to some definitions of multiscale medial axes different from the Blum medial axis that considerably overcame the weakness. Three major multiscale medial axes have been proposed: iteratively pruned trees of Voronoi edges (Ogniewicz, 1993; Székely, 1996; Näf, 1996), shock loci of reaction-diffusion equations (Kimia et al., 1995; Siddiqi and Kimia, 1996), and height ridges of medialness (cores) (Fritsch et al., 1994; Morse et al., 1993; Pizer et al., 1998). These are different from the Blum medial axis, and each has different mathematical properties of generic branching and ending properties, singular transitions, and geometry of implied boundary, and they have different strengths and weaknesses for computing object descriptions from images or from object boundaries. These mathematical properties and computational abilities are laid out and compared and contrasted in this paper. [ABSTRACT FROM AUTHOR]