Distributional approximation is a fundamental problem in machine learning with numerous applications across all fields of science and engineering and beyond. The key challenge in most approximation methods is the need to tackle the intractable normalization constant present in the candidate distributions used to model the data. This intractability is especially common in distributions of manifold-valued random variables such as rotation matrices, orthogonal matrices etc. In this paper, we focus on the distributional approximation problem in Lie groups since they are frequently encountered in many applications including but not limited to, computer vision, robotics, medical imaging and many more. We present a novel Stein’s operator on Lie groups leading to a kernel Stein discrepancy (KSD), which is a normalization-free loss function. We present several theoretical results characterizing the properties of this new KSD on Lie groups and its minimizer namely, the minimum KSD estimator (MKSDE). Properties of MKSDE are presented and proved, including strong consistency, CLT and a closed form of the MKSDE for the von Mises-Fisher and in general, the exponential family on$\mathop {\mathrm {SO}}\nolimits (N)$. Finally, we present several experimental results depicting advantages of MKSDE over maximum likelihood estimation.

Hyperbolic spaces have been quite popular in the recent past for representing hierarchically organized data. Further, several classification algorithms for data in these spaces have been proposed in the literature. These algorithms mainly use either hyperplanes or geodesics for decision boundaries in a large margin classifiers setting leading to a non-convex optimization problem. In this paper, we propose a novel large margin classifier based on horospherical decision boundaries that leads to a geodesically convex optimization problem that can be optimized using any Riemannian gradient descent technique guaranteeing a globally optimal solution. We present several experiments depicting the competitive performance of our classifier in comparison to SOTA.

Hyperbolic neural networks have been popular in the recent past due to their ability to represent hierarchical data sets effectively and efficiently. The challenge in developing these networks lies in the nonlinearity of the embedding space namely, the Hyperbolic space. Hyperbolic space is a homogeneous Riemannian manifold of the Lorentz group which is a semi-Riemannian manifold, i.e. a manifold equipped with an indefinite metric. Most existing methods (with some exceptions) use local linearization to define a variety of operations paralleling those used in traditional deep neural networks in Euclidean spaces. In this paper, we present a novel fully hyperbolic neural network which uses the concept of projections (embeddings) followed by an intrinsic aggregation and a nonlinearity all within the hyperbolic space. The novelty here lies in the projection which is designed to project data on to a lower-dimensional embedded hyperbolic space and hence leads to a nested hyperbolic space representation independently useful for dimensionality reduction. The main theoretical contribution is that the proposed embedding is proved to be isometric and equivariant under the Lorentz transformations, which are the natural isometric transformations in hyperbolic spaces. This projection is computationally efficient since it can be expressed by simple linear operations, and, due to the aforementioned equivariance property, it allows for weight sharing. The nested hyperbolic space representation is the core component of our network and therefore, we first compare this representation - independent of the network - with other dimensionality reduction methods such as tangent PCA, principal geodesic analysis (PGA) and HoroPCA. Based on this equivariant embedding, we develop a novel fully hyperbolic graph convolutional neural network architecture to learn the parameters of the projection. Finally, we present experiments demonstrating comparative performance of our network on several publicly available data sets.

Convolutional neural networks have been highly successful in image-based learning tasks due to their translation equivariance property. Recent work has generalized the traditional convolutional layer of a convolutional neural network to non-euclidean spaces and shown group equivariance of the generalized convolution operation. In this paper, we present a novel higher order Volterra convolutional neural network (VolterraNet) for data defined as samples of functions on Riemannian homogeneous spaces. Analagous to the result for traditional convolutions, we prove that the Volterra functional convolutions are equivariant to the action of the isometry group admitted by the Riemannian homogeneous spaces, and under some restrictions, any non-linear equivariant function can be expressed as our homogeneous space Volterra convolution, generalizing the non-linear shift equivariant characterization of Volterra expansions in euclidean space. We also prove that second order functional convolution operations can be represented as cascaded convolutions which leads to an efficient implementation. Beyond this, we also propose a dilated VolterraNet model. These advances lead to large parameter reductions relative to baseline non-euclidean CNNs. To demonstrate the efficacy of the VolterraNet performance, we present several real data experiments involving classification tasks on spherical-MNIST, atomic energy, Shrec17 data sets, and group testing on diffusion MRI data. Performance comparisons to the state-of-the-art are also presented.

Geometric deep learning is a relatively nascent field that has attracted significant attention in the past few years. This is partly due to the availability of data acquired from non-euclidean domains or features extracted from euclidean-space data that reside on smooth manifolds. For instance, pose data commonly encountered in computer vision reside in Lie groups, while covariance matrices that are ubiquitous in many fields and diffusion tensors encountered in medical imaging domain reside on the manifold of symmetric positive definite matrices. Much of this data is naturally represented as a grid of manifold-valued data. In this paper we present a novel theoretical framework for developing deep neural networks to cope with these grids of manifold-valued data inputs. We also present a novel architecture to realize this theory and call it the ManifoldNet. Analogous to vector spaces where convolutions are equivalent to computing weighted sums, manifold-valued data 'convolutions' can be defined using the weighted Fréchet Mean ([Formula: see text]). (This requires endowing the manifold with a Riemannian structure if it did not already come with one.) The hidden layers of ManifoldNet compute [Formula: see text]s of their inputs, where the weights are to be learnt. This means the data remain manifold-valued as they propagate through the hidden layers. To reduce computational complexity, we present a provably convergent recursive algorithm for computing the [Formula: see text]. Further, we prove that on non-constant sectional curvature manifolds, each [Formula: see text] layer is a contraction mapping and provide constructive evidence for its non-collapsibility when stacked in layers. This captures the two fundamental properties of deep network layers. Analogous to the equivariance of convolution in euclidean space to translations, we prove that the [Formula: see text] is equivariant to the action of the group of isometries admitted by the Riemannian manifold on which the data reside. To showcase the performance of ManifoldNet, we present several experiments using both computer vision and medical imaging data sets.

Principal component analysis (PCA) and Kernel principal component analysis (KPCA) are fundamental methods in machine learning for dimensionality reduction. The former is a technique for finding this approximation in finite dimensions and the latter is often in an infinite dimensional reproducing Kernel Hilbert-space (RKHS). In this paper, we present a geometric framework for computing the principal linear subspaces in both (finite and infinite) situations as well as for the robust PCA case, that amounts to computing the intrinsic average on the space of all subspaces: the Grassmann manifold. Points on this manifold are defined as the subspaces spanned by K-tuples of observations. The intrinsic Grassmann average of these subspaces are shown to coincide with the principal components of the observations when they are drawn from a Gaussian distribution. We show similar results in the RKHS case and provide an efficient algorithm for computing the projection onto the this average subspace. The result is a method akin to KPCA which is substantially faster. Further, we present a novel online version of the KPCA using our geometric framework. Competitive performance of all our algorithms are demonstrated on a variety of real and synthetic data sets.

In a number of disciplines, the data (e.g., graphs, manifolds) to be analyzed are non-Euclidean in nature. Geometric deep learning corresponds to techniques that generalize deep neural network models to such non-Euclidean spaces. Several recent papers have shown how convolutional neural networks (CNNs) can be extended to learn with graph-based data. In this work, we study the setting where the data (or measurements) are ordered, longitudinal or temporal in nature and live on a Riemannian manifold -- this setting is common in a variety of problems in statistical machine learning, vision and medical imaging. We show how recurrent statistical recurrent network models can be defined in such spaces. We give an efficient algorithm and conduct a rigorous analysis of its statistical properties. We perform extensive numerical experiments demonstrating competitive performance with state of the art methods but with significantly less number of parameters. We also show applications to a statistical analysis task in brain imaging, a regime where deep neural network models have only been utilized in limited ways.

The Riemannian geometry of covariance matrices has been essential to several successful applications, in computer vision, biomedical signal and image processing, and radar data processing. For these applications, an important ongoing challenge is to develop Riemannian-geometric tools which are adapted to structured covariance matrices. This paper proposes to meet this challenge by introducing a new class of probability distributions, Gaussian distributions of structured covariance matrices. These are Riemannian analogs of Gaussian distributions, which only sample from covariance matrices having a preassigned structure, such as complex, Toeplitz, or block-Toeplitz. The usefulness of these distributions stems from three features: 1) they are completely tractable, analytically, or numerically, when dealing with large covariance matrices; 2) they provide a statistical foundation to the concept of structured Riemannian barycentre (i.e., Fréchet or geometric mean); and 3) they lead to efficient statistical learning algorithms, which realise, among others, density estimation and classification of structured covariance matrices. This paper starts from the observation that several spaces of structured covariance matrices, considered from a geometric point of view, are Riemannian symmetric spaces. Accordingly, it develops an original theory of Gaussian distributions on Riemannian symmetric spaces, of their statistical inference, and of their relationship to the concept of Riemannian barycentre. Then, it uses this original theory to give a detailed description of Gaussian distributions of three kinds of structured covariance matrices, complex, Toeplitz, and block-Toeplitz. Finally, it describes algorithms for density estimation and classification of structured covariance matrices, based on Gaussian distribution mixture models.

Principal Component Analysis (PCA) is a fundamental method for estimating a linear subspace approximation to high-dimensional data. Many algorithms exist in literature to achieve a statistically robust version of PCA called RPCA. In this paper, we present a geometric framework for computing the principal linear subspaces in both situations that amounts to computing the intrinsic average on the space of all subspaces (the Grassmann manifold). Points on this manifold are defined as the subspaces spanned by K-tuples of observations. We show that the intrinsic Grassmann average of these subspaces coincide with the principal components of the observations when they are drawn from a Gaussian distribution. Similar results are also shown to hold for the RPCA. Further, we propose an efficient online algorithm to do subspace averaging which is of linear complexity in terms of number of samples and has a linear convergence rate. When the data has outliers, our proposed online robust subspace averaging algorithm shows significant performance (accuracy and computation time) gain over a recently published RPCA methods with publicly accessible code. We have demonstrated competitive performance of our proposed online subspace algorithm method on one synthetic and two real data sets. Experimental results depicting stability of our proposed method are also presented. Furthermore, on two real outlier corrupted datasets, we present comparison experiments showing lower reconstruction error using our online RPCA algorithm. In terms of reconstruction error and time required, both our algorithms outperform the competition.

Statistical machine learning models that operate on manifold-valued data are being extensively studied in vision, motivated by applications in activity recognition, feature tracking and medical imaging. While non-parametric methods have been relatively well studied in the literature, efficientformulations for parametric models (which may offer benefits in small sample size regimes) have only emerged recently. Sofar, manifold-valued regression models (such as geodesic regression) are restricted to the analysis of crosssectional data, i.e., the so-called “fixed effects” in statistics. But in most “longitudinal analysis” (e.g., when a participant provides multiple measurements, over time) the application offixed effects models is problematic. In an effort to answer this need, this paper generalizes non-linear mixed effects model to the regime where the response variable is manifold-valued, i.e., f : Rd→ M. We derive the underlying model and estimation schemes and demonstrate the immediate benefits such a model can provide - both for group level and individual level analysis - on longitudinal brain imaging data. The direct consequence of our results is that longitudinal analysis of manifold-valued measurements (especially, the symmetric positive definite manifold) can be conducted in a computationally tractable manner.

Principal Component Analysis (PCA) is a widely popular dimensionality reduction technique for vector-valued inputs. In the past decade, a nonlinear generalization of PCA, called the Principal Geodesic Analysis (PGA) was developed to tackle data that lie on a smooth manifold. PGA suffers from the same problem as PCA in that, in both the methods, each Principal Component (PC) is a linear combination of the original variables. This makes it very difficult to interpret the PCs especially in high dimensions. This lead to the introduction of sparse PCA (SPCA) in the vector-space input case. In this paper, we present a novel generalization of SPCA, called sparse exact PGA (SEPGA) that can cope with manifold-valued input data and respect the intrinsic geometry of the underlying manifold. Sparsity has the advantage of not only easy interpretability but also computational efficiency. We achieve this by formulating the PGA problem as a minimization of the projection error in conjunction with sparsity constraints enforced on the principal vectors post isomorphic mapping to Rm, where m is the dimension of the manifold on which the data reside. Further, for constant curvature smooth manifolds, we use analytic formulae for the projection error leading to an efficient solution to the SEPGA problem. We present extensive experimental results demonstrating the performance of SEPGA in achieving very good sparse principal components without sacrificing the accuracy of reconstruction. This makes SEPGA accurate and efficient in representing manifold-valued data.

Analyzing data representing multifarious trajectories is central to the many fields in Science and Engineering; for example, trajectories representing a tennis serve, a gymnast's parallel bar routine, progression/remission of disease and so on. We present a novel geometric algorithm for performing statistical analysis of trajectories with distinct number of samples representing longitudinal (or temporal) data. A key feature of our proposal is that unlike existing schemes, our model is deployable in regimes where each participant provides a different number of acquisitions (trajectories have different number of sample points or temporal span). To achieve this, we develop a novel method involving the parallel transport of the tangent vectors along each given trajectory to the starting point of the respective trajectories and then use the span of the matrix whose columns consist of these vectors, to construct a linear subspace in Rm. We then map these linear subspaces (possibly of distinct dimensions) of Rm on to a single high dimensional hypersphere. This enables computing group statistics over trajectories by instead performing statistics on the hypersphere (equipped with a simpler geometry). Given a point on the hypersphere representing a trajectory, we also provide a “reverse mapping” algorithm to uniquely (under certain assumptions) reconstruct the subspace that corresponds to this point. Finally, by using existing algorithms for recursive Fŕechet mean and exact principal geodesic analysis on the hypersphere, we present several experiments on synthetic and real (vision and medical) data sets showing how group testing on such diversely sampled longitudinal data is possible by analyzing the reconstructed data in the subspace spanned by the first few principal components.

Longitudinal data analysis is an often encountered problem in Medical Image Analysis. A differential geometric treatment of such problems has been reported in literature in the recent past. However, most of these methods require that the trajectory characterizing the evolution of features over time lie on a geodesic emanating from the initial time point on the manifold containing the trajectory. This is a stringent and not necessarily a meaningful requirement. Further, most of these methods impose the restriction that the number of samples on a trajectory be the same across the members of a group of trajectories. At times, this restriction is hard to meet from a practical view point. In this paper, we present a novel formulation of the trajectory analysis problem that overcomes the aforementioned limitations. We represent the trajectories by embedding them in a product Riemannian manifold and endowing it with a Riemannian metric, thereby facilitating the statistical analysis. Finally, we present real data (from MR brain scans of dementia patients) examples depicting the performance of our algorithms.

Regression is an essential tool in Statistical analysis of data with many applications in Computer Vision, Machine Learning, Medical Imaging and various disciplines of Science and Engineering. Linear and nonlinear regression in a vector space setting has been well studied in literature. However, generalizations to manifold-valued data are only recently gaining popularity. With the exception of a few, most existing methods of regression for manifold valued data are limited to geodesic regression which is a generalization of the linear regression in vector-spaces. In this paper, we present a novel nonlinear kernel-based regression method that is applicable to manifold valued data. Our method is applicable to cases when the independent and dependent variables in the regression model are both manifold-valued or one is manifold-valued and the other is vector or scalar valued. Further, unlike most methods, our method does not require any imposed ordering on the manifold-valued data. The performance of our model is tested on a large number of real data sets acquired from Alzhiemers and movement disorder (Parkinsons and Essential Tremor) patients. We present an extensive set of results along with statistical validation and comparisons.

Manifold-valued datasets are widely encountered in many computer vision tasks. A non-linear analog of the PCA algorithm, called the Principal Geodesic Analysis (PGA) algorithm suited for data lying on Riemannian manifolds was reported in literature a decade ago. Since the objective function in the PGA algorithm is highly non-linear and hard to solve efficiently in general, researchers have proposed a linear approximation. Though this linear approximation is easy to compute, it lacks accuracy especially when the data exhibits a large variance. Recently, an alternative called the exact PGA was proposed which tries to solve the optimization without any linearization. For general Riemannian manifolds, though it yields a better accuracy than the original (linearized) PGA, for data that exhibit large variance, the optimization is not computationally efficient. In this paper, we propose an efficient exact PGA algorithm for constant curvature Riemannian manifolds (CCM-EPGA). The CCM-EPGA algorithm differs significantly from existing PGA algorithms in two aspects, (i) the distance between a given manifold-valued data point and the principal submanifold is computed analytically and thus no optimization is required as in the existing methods. (ii) Unlike the existing PGA algorithms, the descent into codimension-1 submanifolds does not require any optimization but is accomplished through the use of the Rimeannian inverse Exponential map and the parallel transport operations. We present theoretical and experimental results for constant curvature Riemannian manifolds depicting favorable performance of the CCM-EPGA algorithm compared to existing PGA algorithms. We also present data reconstruction from the principal components which has not been reported in literature in this setting.

In the past decade, Grassmann manifolds (Grassmannian) have been commonly used in mathematical formulations of many Computer Vision tasks. Averaging points on a Grassmann manifold is a very common operation in many applications including but not limited to, tracking, action recognition, video-face recognition, face recognition, etc. Computing the intrinsic/Fréchet mean (FM) of a set of points on the Grassmann can be cast as finding the global optimum (if it exists) of the sum of squared geodesic distances cost function. A common approach to solve this problem involves the use of the gradient descent method. An alternative way to compute the FM is to develop a recursive/inductive definition that does not involve optimizing the aforementioned cost function. In this paper, we propose one such computationally efficient algorithm called the Grassmann inductive Fréchet mean estimator (GiFME). In developing the recursive solution to find the FM of the given set of points, GiFME exploits the fact that there is a closed form solution to find the FM of two points on the Grassmann. In the limit as the number of samples tends to infinity, we prove that GiFME converges to the FM (this is called the weak consistency result on the Grassmann manifold). Further, for the finite sample case, in the limit as the number of sample paths (trials) goes to infinity, we show that GiFME converges to the finite sample FM. Moreover, we present a bound on the geodesic distance between the estimate from GiFME and the true FM. We present several experiments on synthetic and real data sets to demonstrate the performance of GiFME in comparison to the gradient descent based (batch mode) technique. Our goal in these applications is to demonstrate the computational advantage and achieve comparable accuracy to the state-of-the-art.

Probability density functions (PDFs) are fundamental objects in mathematics with numerous applications in computer vision, machine learning and medical imaging. The feasibility of basic operations such as computing the distance between two PDFs and estimating a mean of a set of PDFs is a direct function of the representation we choose to work with. In this paper, we study the Gaussian mixture model (GMM) representation of the PDFs motivated by its numerous attractive features. (1) GMMs are arguably more interpretable than, say, square root parameterizations (2) the model complexity can be explicitly controlled by the number of components and (3) they are already widely used in many applications. The main contributions of this paper are numerical algorithms to enable basic operations on such objects that strictly respect their underlying geometry. For instance, when operating with a set of K component GMMs, a first order expectation is that the result of simple operations like interpolation and averaging should provide an object that is also a K component GMM. The literature provides very little guidance on enforcing such requirements systematically. It turns out that these tasks are important internal modules for analysis and processing of a field of ensemble average propagators (EAPs), common in diffusion weighted magnetic resonance imaging. We provide proof of principle experiments showing how the proposed algorithms for interpolation can facilitate statistical analysis of such data, essential to many neuroimaging studies. Separately, we also derive interesting connections of our algorithm with functional spaces of Gaussians, that may be of independent interest.

Statistical models for manifold-valued data permit capturing the intrinsic nature of the curved spaces in which the data lie and have been a topic of research for several decades. Typically, these formulations use geodesic curves and distances defined locally for most cases - this makes it hard to design parametric models globally on smooth manifolds. Thus, most (manifold specific) parametric models available today assume that the data lie in a small neighborhood on the manifold. To address this ’locality’ problem, we propose a novel nonparametric model which unifies multivariate general linear models (MGLMs) using multiple tangent spaces. Our framework generalizes existing work on (both Euclidean and non-Euclidean) general linear models providing a recipe to globally extend the locally-defined parametric models (using a mixture of local models). By grouping observations into sub-populations at multiple tangent spaces, our method provides insights into the hidden structure (geodesic relationships) in the data. This yields a framework to group observations and discover geodesic relationships between covariates X and manifold-valued responses Y, which we call Dirichlet process mixtures of multivariate general linear models (DP-MGLM) on Riemannian manifolds. Finally, we present proof of concept experiments to validate our model.

A novel adaptation of the unscented Kalman filter (UKF) was recently introduced in literature for simultaneous multitensor estimation and fiber tractography from diffusion MRI. This technique has the advantage over other tractography methods in terms of computational efficiency, due to the fact that the UKF simultaneously estimates the diffusion tensors and propagates the most consistent direction to track along. This UKF and its variants reported later in literature however are not intrinsic to the space of diffusion tensors. Lack of this key property can possibly lead to inaccuracies in the multitensor estimation as well as in the tractography. In this paper, we propose a novel intrinsic unscented Kalman filter (IUKF) in the space of diffusion tensors which are symmetric positive definite matrices, that can be used for simultaneous recursive estimation of multitensors and propagation of directional information for use in fiber tractography from diffusion weighted MR data. In addition to being more accurate, IUKF retains all the advantages of UKF mentioned above. We demonstrate the accuracy and effectiveness of the proposed method via experiments publicly available phantom data from the fiber cup-challenge (MICCAI 2009) and diffusion weighted MR scans acquired from human brains and rat spinal cords.

In this paper, we cast the problem of point cloud matching as a shape matching problem by transforming each of the given point clouds into a shape representation called the Schrödinger distance transform (SDT) representation. This is achieved by solving a static Schrödinger equation instead of the corresponding static Hamilton-Jacobi equation in this setting. The SDT representation is an analytic expression and following the theoretical physics literature, can be normalized to have unit 2 norm - making it a square-root density, which is identified with a point on a unit Hilbert sphere, whose intrinsic geometry is fully known. The Fisher-Rao metric, a natural metric for the space of densities leads to analytic expressions for the geodesic distance between points on this sphere. In this paper, we use the well known Riemannian framework never before used for point cloud matching, and present a novel matching algorithm. We pose point set matching under rigid and non-rigid transformations in this framework and solve for the transformations using standard nonlinear optimization techniques. Finally, to evaluate the performance of our algorithm - dubbed SDTM - we present several synthetic and real data examples along with extensive comparisons to state-of-the-art techniques. The experiments show that our algorithm outperforms state-of the-art point set registration algorithms on many quantitative metrics.

Tractography refers to the process of tracing out the nerve fiber bundles from diffusion Magnetic Resonance Images (dMRI) data acquired either in vivo or ex-vivo. Tractography is a mature research topic within the field of diffusion MRI analysis, nevertheless, several new methods are being proposed on a regular basis thereby justifying the need, as the problem is not fully solved. Tractography is usually applied to the model (used to represent the diffusion MR signal or a derived quantity) reconstructed from the acquired data. Separating shape and orientation of these models was previously shown to approximately preserve diffusion anisotropy (a useful bio-marker) in the ubiquitous problem of interpolation. However, no further intrinsic geometric properties of this framework were exploited to date in literature. In this paper, we propose a new intrinsic recursive filter on the product manifold of shape and orientation. The recursive filter, dubbed IUKFPro, is a generalization of the unscented Kalman filter (UKF) to this product manifold. The salient contributions of this work are: (1) A new intrinsic UKF for the product manifold of shape and orientation. (2) Derivation of the Riemannian geometry of the product manifold. (3) IUKFPro is tested on synthetic and real data sets from various tractography challenge competitions. From the experimental results, it is evident that IUKFPro performs better than several competing schemes in literature with regards to some of the error measures used in the competitions and is competitive with respect to others.

This paper studies a form of law of large numbers on Pn, the space of nxn symmetric positive-definite matrices equipped with Fisher-Rao metric. Specifically, we propose a recursive algorithm for estimating the Karcher expectation of an arbitrary distribution defined on Pn, and we show that the estimates computed by the recursive algorithm asymptotically converge in probability to the correct Karcher expectation. The steps in the recursive algorithm mainly consist of making appropriate moves on geodesics in Pn, and the algorithm is simple to implement and it offers a tremendous gain in computation time of several orders in magnitude over existing non-recursive algorithms. We elucidate the connection between the more familiar law of large numbers for real-valued random variables and the asymptotic convergence of the proposed recursive algorithm, and our result provides an example of a new form of law of large numbers for random variables taking values in a Riemannian manifold. From the practical side, the computation of the mean of a collection of symmetric positive-definite (SPD) matrices is a fundamental ingredient in many algorithms in machine learning, computer vision and medical imaging applications. We report an experiment using the proposed recursive algorithm for K-means clustering, demonstrating the algorithm’s efficiency, accuracy and stability.

In this paper, we introduce a novel framework for computing a path of diffeomorphisms between a pair of input diffeomorphisms. Direct computation of a geodesic path on the space of diffeomorphisms Diff(Ω) is difficult, and it can be attributed mainly to the infinite dimensionality of Diff(Ω). Our proposed framework, to some degree, bypasses this difficulty using the quotient map of Diff(Ω) to the quotient space Diff(M)/Diff(M)μobtained by quotienting out the subgroup of volume-preserving diffeomorphisms Diff(M)μ. This quotient space was recently identified as the unit sphere in a Hilbert space in mathematics literature, a space with well-known geometric properties. Our framework leverages this recent result by computing the diffeomorphic path in two stages. First, we project the given diffeomorphism pair onto this sphere and then compute the geodesic path between these projected points. Second, we lift the geodesic on the sphere back to the space of diffeomerphisms, by solving a quadratic programming problem with bilinear constraints using the augmented Lagrangian technique with penalty terms. In this way, we can estimate the path of diffeomorphisms, first, staying in the space of diffeomorphisms, and second, preserving shapes/volumes in the deformed images along the path as much as possible. We have applied our framework to interpolate intermediate frames of frame-sub-sampled video sequences. In the reported experiments, our approach compares favorably with the popular Large Deformation Diffeomorphic Metric Mapping framework (LDDMM).

Symmetric positive-definite (SPD) matrices are ubiquitous in Computer Vision, Machine Learning and Medical Image Analysis. Finding the center/average of a population of such matrices is a common theme in many algorithms such as clustering, segmentation, principal geodesic analysis, etc. The center of a population of such matrices can be defined using a variety of distance/divergence measures as the minimizer of the sum of squared distances/divergences from the unknown center to the members of the population. It is well known that the computation of the Karcher mean for the space of SPD matrices which is a negatively-curved Riemannian manifold is computationally expensive. Recently, the LogDet divergence-based center was shown to be a computationally attractive alternative. However, the LogDet-based mean of more than two matrices can not be computed in closed form, which makes it computationally less attractive for large populations. In this paper we present a novel recursive estimator for center based on the Stein distance - which is the square root of the LogDet divergence - that is significantly faster than the batch mode computation of this center. The key theoretical contribution is a closed-form solution for the weighted Stein center of two SPD matrices, which is used in the recursive computation of the Stein center for a population of SPD matrices. Additionally, we show experimental evidence of the convergence of our recursive Stein center estimator to the batch mode Stein center. We present applications of our recursive estimator to K-means clustering and image indexing depicting significant time gains over corresponding algorithms that use the batch mode computations. For the latter application, we develop novel hashing functions using the Stein distance and apply it to publicly available data sets, and experimental results have shown favorable comparisons to other competing methods.

Existing dictionary learning algorithms are based on the assumption that the data are vectors in an Euclidean vector space, and the dictionary is learned from the training data using the vector space structure and its Euclidean metric. However, in many applications, features and data often originated from a Riemannian manifold that does not support a global linear (vector space) structure. Furthermore, the extrinsic viewpoint of existing dictionary learning algorithms becomes inappropriate for modeling and incorporating the intrinsic geometry of the manifold that is potentially important and critical to the application. This paper proposes a novel framework for sparse coding and dictionary learning for data on a Riemannian manifold, and it shows that the existing sparse coding and dictionary learning methods can be considered as special (Euclidean) cases of the more general framework proposed here. We show that both the dictionary and sparse coding can be effectively computed for several important classes of Riemannian manifolds, and we validate the proposed method using two well-known classification problems in computer vision and medical imaging analysis.

In this paper, we address the problem of video tracking using covariance descriptors constructed from simple features extracted from the given image sequence. Theoretically, this can be posed as a tracking problem in the space of ($n \times n$) symmetric positive definite (SPD) matrices denoted by $P_n$. A novel probabilistic dynamic model in $P_n$ based on Riemannian geometry and probability theory is presented in conjunction with a geometric (intrinsic) recursive filter for tracking a time sequence of SPD matrix measurements in a Bayesian framework. This newly developed filtering method can be used for the covariance descriptor updating problem in covariance tracking, leading to new and efficient video tracking algorithms. To show the accuracy and efficiency of our tracker in comparison to the state-of-the-art, we present synthetic experiments on $P_n$ and several real data experiments for tracking in video sequences.

In this paper, we propose a novel framework for computing single or multiple atlases (templates) from a large population of images. Unlike many existing methods, our proposed approach is distinguished by its emphasis on the sharpness of the computed atlases and the requirement of rotational invariance. In particular, we argue that sharp atlas images that retain crucial and important anatomical features with high fidelity are more useful for many medical imaging applications when compared with the blurry and fuzzy atlas images computed by most existing methods. The geometric notion that underlies our approach is the idea of manifold learning in a quotient space, the quotient space of the image space by the rotations. We present an extension of the existing manifold learning approach to quotient spaces by using invariant metrics, and utilizing the manifold structure for partitioning the images into more homogeneous sub-collections, each of which can be represented by a single atlas image. Specifically, we propose a three-step algorithm. First, we partition the input images into subgroups using unsupervised or semi-supervised learning methods on manifolds. Then we formulate a convex optimization problem in each subgroup to locate the atlases and determine the crucial neighbors that are used in the realization step to form the template images. We have evaluated our algorithm using whole brain MR volumes from OASIS database. Experimental results demonstrate that the atlases computed using the proposed algorithm not only discover the brain structural changes in different age groups but also preserve important structural details and generally enjoy better image quality.

In this paper, we present a novel image classification system that is built around a core of trainable filter ensembles that we call Volterra kernel classifiers. Our system treats images as a collection of possibly overlapping patches and is composed of three components: (1) A scheme for a single patch classification that seeks a smooth, possibly nonlinear, functional mapping of the patches into a range space, where patches of the same class are close to one another, while patches from different classes are far apart-in the L_2 sense. This mapping is accomplished using trainable convolution filters (or Volterra kernels) where the convolution kernel can be of any shape or order. (2) Given a corpus of Volterra classifiers with various kernel orders and shapes for each patch, a boosting scheme for automatically selecting the best weighted combination of the classifiers to achieve higher per-patch classification rate. (3) A scheme for aggregating the classification information obtained for each patch via voting for the parent image classification. We demonstrate the effectiveness of the proposed technique using face recognition as an application area and provide extensive experiments on the Yale, CMU PIE, Extended Yale B, Multi-PIE, and MERL Dome benchmark face data sets. We call the Volterra kernel classifiers applied to face recognition Volterrafaces. We show that our technique, which falls into the broad class of embedding-based face image discrimination methods, consistently outperforms various state-of-the-art methods in the same category.

In this paper, we consider the family of total Bregman divergences (tBDs) as an efficient and robust "distance" measure to quantify the dissimilarity between shapes. We use the tBD-based ℓ₁-norm center as the representative of a set of shapes, and call it the t-center. First, we briefly present and analyze the properties of the tBDs and t-centers following our previous work in. Then, we prove that for any tBD, there exists a distribution which belongs to the lifted exponential family (lEF) of statistical distributions. Further, we show that finding the maximum a posteriori (MAP) estimate of the parameters of the lifted exponential family distribution is equivalent to minimizing the tBD to find the t-centers. This leads to a new clustering technique, namely, the total Bregman soft clustering algorithm. We evaluate the tBD, t-center, and the soft clustering algorithm on shape retrieval applications. Our shape retrieval framework is composed of three steps: 1) extraction of the shape boundary points, 2) affine alignment of the shapes and use of a Gaussian mixture model (GMM) to represent the aligned boundaries, and 3) comparison of the GMMs using tBD to find the best matches given a query shape. To further speed up the shape retrieval algorithm, we perform hierarchical clustering of the shapes using our total Bregman soft clustering algorithm. This enables us to compare the query with a small subset of shapes which are chosen to be the cluster t-centers. We evaluate our method on various public domain 2D and 3D databases, and demonstrate comparable or better results than state-of-the-art retrieval techniques.

Tensors of various orders can be used for modeling physical quantities such as strain and diffusion as well as curvature and other quantities of geometric origin. Depending on the physical properties of the modeled quantity, the estimated tensors are often required to satisfy the positivity constraint, which can be satisfied only with tensors of even order. Although the space [Formula: see text] of 2m(th)-order symmetric positive semi-definite tensors is known to be a convex cone, enforcing positivity constraint directly on [Formula: see text] is usually not straightforward computationally because there is no known analytic description of [Formula: see text] for m > 1. In this paper, we propose a novel approach for enforcing the positivity constraint on even-order tensors by approximating the cone [Formula: see text] for the cases 0 < m < 3, and presenting an explicit characterization of the approximation Σ(2) (m) ⊂ Ω(2) (m) for m ≥ 1, using the subset [Formula: see text] of semi-definite tensors that can be written as a sum of squares of tensors of order m. Furthermore, we show that this approximation leads to a non-negative linear least-squares (NNLS) optimization problem with the complexity that equals the number of generators in Σ(2) (m). Finally, we experimentally validate the proposed approach and we present an application for computing 2m(th)-order diffusion tensors from Diffusion Weighted Magnetic Resonance Images.

In this paper, we propose an interlaced multi-shell sampling scheme for the reconstruction of the diffusion propagator from diffusion weighted magnetic resonance imaging (DW-MRI). In standard multi-shell sampling schemes, sample points are uniformly distributed on several spherical shells in q-space. The distribution of sample points is the same for all shells, and is determined by the vertices of a selected polyhedron. We propose a more efficient interlaced scheme where sample points are different on alternating shells and are determined by the vertices of a pair of dual polyhedra. Since it samples more directions than the standard scheme, this method offers increased angular discrimination. Another contribution of this work is the application of optimal sampling lattices to q-space data acquisition and the proposal of a model-free reconstruction algorithm, which uses the lattice dependent sinc interpolation function. It is shown that under this reconstruction framework, the body centered cubic (BCC) lattice provides increased accuracy. The sampling scheme and the reconstruction algorithms were evaluated on simulated data as well as rat brain data collected on a 600 MHz (14.1T) Bruker imaging spectrometer.

Boosting is a well known machine learning technique used to improve the performance of weak learners and has been successfully applied to computer vision, medical image analysis, computational biology and other fields. A critical step in boosting algorithms involves update of the data sample distribution, however, most existing boosting algorithms use updating mechanisms that lead to overfitting and instabilities during evolution of the distribution which in turn results in classification inaccuracies. Regularized boosting has been proposed in literature as a means to overcome these difficulties. In this paper, we propose a novel total Bregman divergence (tBD) regularized LPBoost, termed tBRLPBoost. tBD is a recently proposed divergence in literature, which is statistically robust and we prove that tBRLPBoost requires a constant number of iterations to learn a strong classifier and hence is computationally more efficient compared to other regularized Boosting algorithms. Also, unlike other boosting methods that are only effective on a handful of datasets, tBRLPBoost works well on a variety of datasets. We present results of testing our algorithm on many public domain databases and comparisons to several other state-of-the-art methods. Numerical results show that the proposed algorithm has much improved performance in efficiency and accuracy over other methods.

We present two theses in this paper: First, performance of most existing face recognition algorithms improves if instead of the whole image, smaller patches are individually classified followed by label aggregation using voting. Second, weighted plurality1voting outperforms other popular voting methods if the weights are set such that they maximize the victory margin for the winner with respect to each of the losers. Moreover, this can be done while taking higher order relationships among patches into account using kernels. We call this scheme Kernel Plurality. We verify our proposals with detailed experimental results and show that our framework with Kernel Plurality improves the performance of various face recognition algorithms beyond what has been previously reported in the literature. Furthermore, on five different benchmark datasets - Yale A, CMU PIE, MERL Dome, Extended Yale B and Multi-PIE, we show that Kernel Plurality in conjunction with recent face recognition algorithms can provide state-of-the-art results in terms of face recognition rates.

In this paper, we present a unified framework for the rigid and nonrigid point set registration problem in the presence of significant amounts of noise and outliers. The key idea of this registration framework is to represent the input point sets using Gaussian mixture models. Then, the problem of point set registration is reformulated as the problem of aligning two Gaussian mixtures such that a statistical discrepancy measure between the two corresponding mixtures is minimized. We show that the popular iterative closest point (ICP) method [1] and several existing point set registration methods [2], [3], [4], [5], [6], [7] in the field are closely related and can be reinterpreted meaningfully in our general framework. Our instantiation of this general framework is based on the the L2 distance between two Gaussian mixtures, which has the closed-form expression and in turn leads to a computationally efficient registration algorithm. The resulting registration algorithm exhibits inherent statistical robustness, has an intuitive interpretation, and is simple to implement. We also provide theoretical and experimental comparisons with other robust methods for point set registration.

Modeling illumination effects and pose variations of a face is of fundamental importance in the field of facial image analysis. Most of the conventional techniques that simultaneously address both of these problems work with the Lambertian assumption and thus fall short of accurately capturing the complex intensity variation that the facial images exhibit or recovering their 3D shape in the presence of specularities and cast shadows. In this paper, we present a novel Tensor-Spline-based framework for facial image analysis. We show that, using this framework, the facial apparent BRDF field can be accurately estimated while seamlessly accounting for cast shadows and specularities. Further, using local neighborhood information, the same framework can be exploited to recover the 3D shape of the face (to handle pose variation). We quantitatively validate the accuracy of the Tensor Spline model using a more general model based on the mixture of single-lobed spherical functions. We demonstrate the effectiveness of our technique by presenting extensive experimental results for face relighting, 3D shape recovery, and face recognition using the Extended Yale B and CMU PIE benchmark data sets.

Divergence measures provide a means to measure the pairwise dissimilarity between "objects," e.g., vectors and probability density functions (pdfs). Kullback-Leibler (KL) divergence and the square loss (SL) function are two examples of commonly used dissimilarity measures which along with others belong to the family of Bregman divergences (BD). In this paper, we present a novel divergence dubbed the Total Bregman divergence (TBD), which is intrinsically robust to outliers, a very desirable property in many applications. Further, we derive the TBD center, called the t-center (using the l(1)-norm), for a population of positive definite matrices in closed form and show that it is invariant to transformation from the special linear group. This t-center, which is also robust to outliers, is then used in tensor interpolation as well as in an active contour based piecewise constant segmentation of a diffusion tensor magnetic resonance image (DT-MRI). Additionally, we derive the piecewise smooth active contour model for segmentation of DT-MRI using the TBD and present several comparative results on real data.

Shape database search is ubiquitous in the world of bio-metric systems, CAD systems etc. Shape data in these domains is experiencing an explosive growth and usually requires search of whole shape databases to retrieve the best matches with accuracy and efficiency for a variety of tasks. In this paper, we present a novel divergence measure between any two given points in Rnor two distribution functions. This divergence measures the orthogonal distance between the tangent to the convex function (used in the definition of the divergence) at one of its input arguments and its second argument. This is in contrast to the ordinate distance taken in the usual definition of the Bregman class of divergences. We use this orthogonal distance to redefine the Bregman class of divergences and develop a new theory for estimating the center of a set of vectors as well as probability distribution functions. The new class of divergences are dubbed the total Bregman divergence (TBD). We present the l\-norm based TBD center that is dubbed the t-center which is then used as a cluster center of a class of shapes The t-center is weighted mean and this weight is small for noise and outliers. We present a shape retrieval scheme using TBD and the t-center for representing the classes of shapes from the MPEG-7 database and compare the results with other state-of-the-art methods in literature.

In this paper, we propose a novel algorithm for computing an atlas from a collection of images. In the literature, atlases have almost always been computed as some types of means such as the straightforward Euclidean means or the more general Karcher means on Riemannian manifolds. In the context of images, the paper's main contribution is a geometric framework for computing image atlases through a two-step process: the localization of mean and the realization of it as an image. In the localization step, a few nearest neighbors of the mean among the input images are determined, and the realization step then proceeds to reconstruct the atlas image using these neighbors. Decoupling the localization step from the realization step provides the flexibility that allows us to formulate a general algorithm for computing image atlas. More specifically, we assume the input images belong to some smooth manifold M modulo image rotations. We use a graph structure to represent the manifold, and for the localization step, we formulate a convex optimization problem in ℝ(k) (k the number of input images) to determine the crucial neighbors that are used in the realization step to form the atlas image. The algorithm is both unbiased and rotation-invariant. We have evaluated the algorithm using synthetic and real images. In particular, experimental results demonstrate that the atlases computed using the proposed algorithm preserve important image features and generally enjoy better image quality in comparison with atlases computed using existing methods.

In this paper we address the problem of relighting faces in presence of cast shadows and specularities. We present a solution to this problem by capturing the spatially varying Apparent Bidirectional Reflectance Functions (ABRDF) fields of human faces using Spline Modulated Spherical Harmonics and representing them using a few salient spherical functions called Eigenbubbles. Through extensive experiments on the Extended Yale B and the CMU PIE benchmark datasets we demonstrate that the proposed method clearly outperforms the state-of-the-art techniques in synthesized image quality. Furthermore, we show that our framework allows for ABDRF field compression and can also be used to enhance performance of face recognition algorithms.

In this paper, we propose a Riemannian framework for statistical analysis of tensor fields. Existing approaches to this problem have been mainly voxel-based that overlook the correlation between tensors at different voxels. In our approach, the tensor fields are considered as points in a high-dimensional Riemannian product space and accordingly, we extend Principal Geodesic Analysis (PGA) to the product space. This provides us with a principled method for linearizing the problem, and coupled with the usual log-exp maps that relate points on manifold to tangent vectors, the global correlation of the tensor field can be captured using Principal Component Analysis in a tangent space. Using the proposed method, the modes of variation of tensor fields can be efficiently determined, and dimension reduction of the data is also easily implemented. Experimental results on characterizing the variation of a large set of tensor fields are presented in the paper, and results on classifying tensor fields using the proposed method are also reported. These preliminary experimental results demonstrate the advantages of our method over the voxel-based approach.

The Laplacian raised to fractional powers can be used to generate scale spaces as was shown in recent literature by Duits, Felsberg, Florack, and Platel [$\alpha$ scale spaces on a bounded domain, in Scale Space Methods in Computer Vision, L. D. Griffin and M. Lillholm, eds., Lecture Notes in Comput. Sci. 2695, Springer, Berlin, Heidelberg, 2003, pp. 494–510] and Duits, Florack, de Graaf, and ter Haar Romeny [J. Math. Imaging Vision, 20 (2004), pp. 267–298]. In this paper, we study the anisotropic diffusion processes by defining new generators that are fractional powers of an anisotropic scale space generator. This is done in a general framework that allows us to explain the relation between a differential operator that generates the flow and the generators that are constructed from its fractional powers. We then generalize this to any other function of the operator. We discuss important issues involved in the numerical implementation of this framework and present several examples of fractional versions of the Perona–Malik and Beltrami flows along with their properties.

In this paper we present a novel face classification system where we represent face images as a spatial arrangement of image patches, and seek a smooth nonlinear functional mapping for the corresponding patches such that in the range space, patches of the same face are close to one another, while patches from different faces are far apart, in L2sense. We accomplish this using Volterra kernels, which can generate successively better approximations to any smooth nonlinear functional. During learning, for each set of corresponding patches we recover a Volterra kernel by minimizing a goodness functional defined over the range space of the sought functional. We show that for our definition of the goodness functional, which minimizes the ratio between intraclass distances and interclass distances, the problem of generating Volterra approximations, to any order, can be posed as a generalized eigenvalue problem. During testing, each patch from the test image that is classified independently, casts a vote towards image classification and the class with the maximum votes is chosen as the winner. We demonstrate the effectiveness of the proposed technique in recognizing faces by extensive experiments on Yale, CMU PIE and Extended Yale B benchmark face datasets and show that our technique consistently outperforms the state-of-the-art in learning based face discrimination.

Complex diffusion was introduced in image processing literature as a means to achieve simultaneous denoising and enhancement of scalar valued images. In this paper, we present a novel geometric framework for achieving complex diffusion on color images expressed as image graphs. In this framework, we develop a new variational formulation for achieving complex diffusion. This formulation involves a modified harmonic map functional and is quite distinct from the Polyakov action described in earlier work by Sochen et al. Our formulation provides a framework for simultaneous (feature preserving) denoising and enhancement. We present results of comparison between the complex diffusion, and Beltrami flow all in the image graph framework.

Human faces are neither exactly Lambertian nor entirely convex and hence most models in literature which make the Lambertian assumption, fall short when dealing with specularities and cast shadows. In this paper, we present a novel anti-symmetric tensor spline (a spline for tensor-valued functions) based method for the estimation of the Apparent BRDF (ABRDF) field for human faces that seamlessly accounts for specularities and cast shadows. Furthermore, unlike other methods, it does not require any 3D information to build the model and can work with as few as 9 images. In order to validate the accuracy of our anti-symmetric tensor spline model, we present a novel approximation of the ABRDF using a continuous mixture of single-lobed spherical functions. We demonstrate the effectiveness of our anti-symmetric tensor-spline model in comparison to other popular models in the literature, by presenting extensive results for face relighting and face recognition using the Extended Yale B database.

Learning a discriminant becomes substantially more difficult when the datasets are high-dimensional and the available samples are few. This is often the case in computer vision and medical diagnosis applications. A novel Conic Section classifier (CSC) was recently introduced in the literature to handle such datasets, wherein each class was represented by a conic section parameterized by its focus, directrix and eccentricity. The discriminant boundary was the locus of all points that are equi-eccentric relative to each class-representative conic section. Simpler boundaries were preferred for the sake of generalizability.In this paper, we improve the performance of the two-class classifier via a large margin pursuit. When formulated as a non-linear optimization problem, the margin computation is demonstrated to be hard, especially due to the high dimensionality of the data. Instead, we present a geometric algorithm to compute the distance of a point to the nonlinear discriminant boundary generated by the CSC in the input space. We then introduce a large margin pursuit in the learning phase so as to enhance the generalization capacity of the classifier. We validate the algorithm on real datasets and show favorable classification rates in comparison to many existing state-of-the-art binary classifiers as well as the CSC without margin pursuit.

Image segmentation is a fundamental task in Computer Vision and there are numerous algorithms that have been successfully applied in various domains. There are still plenty of challenges to be met with. In this paper, we consider one such challenge, that of achieving segmentation while preserving complicated and detailed features present in the image, be it a gray level or a textured image. We present a novel approach that does not make use of any prior information about the objects in the image being segmented. Segmentation is achieved using local orientation information, which is obtained via the application of a steerable Gabor filter bank, in a statistical framework. This information is used to construct a spatially varying kernel called the Rigaut Kernel, which is then convolved with the signed distance function of an evolving contour (placed in the image) to achieve segmentation. We present numerous experimental results on real images, including a quantitative evaluation. Superior performance of our technique is depicted via comparison to the state-of-the-art algorithms in literature.

Groupwise registration of a set of shapes represented by unlabeled point sets is a challenging problem since, usually, this involves solving for point correspondence in a nonrigid motion setting. In this paper, we propose a novel and robust algorithm that is capable of simultaneously computing the mean shape, represented by a probability density function, from multiple unlabeled point sets(represented by finite-mixture models), and registering them nonrigidly to this emerging mean shape. This algorithm avoids the correspondence problem by minimizing the Jensen-Shannon (JS) divergence between the point sets represented as finite mixtures of Gaussian densities. We motivate the use of the JS divergence by pointing out its close relationship to hypothesis testing. Essentially,minimizing the JS divergence is asymptotically equivalent to maximizing the likelihood ratio formed from a probability density of the pooled point sets and the product of the probability densities of the individual point sets. We derive the analytic gradient of the cost function, namely, the JS-divergence, in order to efficiently achieve the optimal solution. The cost function is fully symmetric, with no bias toward any of the given shapes to be registered and whose mean is being sought. A by-product of the registration process is a probabilistic atlas, which is defined as the convex combination of the probability densities of the input point sets being aligned. Our algorithm can be especially useful for creating atlases of various shapes present in images and for simultaneously (rigidly or nonrigidly)registering 3D range data sets (in vision and graphics applications), without having to establish any correspondence. We present experimental results on nonrigidly registering 2D and 3D real and synthetic data (point sets).

Finding a good metric over the input space plays a fundamental role in machine learning. Most existing techniques use the Mahalanobis metric without incorporating the geometry of positive matrices and experience difficulties in the optimization procedure. In this paper we introduce the use of Iwasawa decomposition, a unique and effective parametrization of symmetric positive definite (SPD) matrices, for performing metric learning tasks. Unlike other previously employed factorizations, the use of the Iwasawa decomposition is able to reformulate the semidefinite programming (SDP) problems as smooth convex nonlinear programming (NLP) problems with much simpler constraints. We also introduce a modified Iwasawa coordinates for rank-deficient positive semidefinite (PSD) matrices which enables the unifying of the metric learning and linear dimensionality reduction. We show that the Iwasawa decomposition can be easily used in most recent proposed metric learning algorithms and have applied it to the Neighbourhood Components Analysis (NCA). The experimental results on several public domain datasets are also presented.

Image smoothing, segmentation and registration are three key processing steps in many computer vision applications. In this paper, we present a novel framework for achieving all three seemingly disparate goals simultaneously across multiple images in a unified framework via a single variational principle. The proposed method ensures that the estimated registration is unbiased and all compositions of registration maps are compatible. The solution to the variational problem is achieved efficiently by solving a coupled system of partial differential equations over the common domain on which the registration maps are defined. The effectiveness of the proposed framework is demonstrated on sets of real images.

Many computer vision and image processing tasks require the preservation of local discontinuities, terminations and bifurcations. Denoising with feature preservation is a challenging task and in this paper, we present a novel technique for preserving complex oriented structures such as junctions and corners present in images. This is achieved in a two stage process namely, (1) All image data are pre-processed to extract local orientation information using a steerable Gabor filter bank. The orientation distribution at each lattice point is then represented by a continuous mixture of Gaussians. The continuous mixture representation can be cast as the Laplace transform of the mixing density over the space of positive definite (covariance) matrices. This mixing density is assumed to be a parameterized distribution, namely, a mixture of Wisharts whose Laplace transform is evaluated in a closed form expression called the Rigaut type function, a scalar-valued function of the parameters of the Wishart distribution. Computation of the weights in the mixture Wisharts is formulated as a sparse deconvolution problem. (2) The feature preserving denoising is then achieved via iterative convolution of the given image data with the Rigaut type function. We present experimental results on noisy data, real 2D images and 3D MRI data acquired from plant roots depicting bifurcating roots. Superior performance of our technique is depicted via comparison to the state-of-the-art anisotropic diffusion filter.

We propose a novel affine registration algorithm for matching 2D feature points. Unlike many previously published work on affine point matching, the proposed algorithm does not require any optimization and in the absence of data noise, the algorithm will recover the exact affine transformation and the unknown correspondence. The two-step algorithm first reduces the general affine case to the orthogonal case, and the unknown rotation is computed as the roots of a low-degree polynomial with complex coefficients. The algebraic and geometric ideas behind the proposed method are both clear and transparent, and its implementation is straightforward. We validate the algorithm on a variety of synthetic 2D point sets as well as feature points on images of real-world objects

In this paper, we present novel algorithms for statistically robust interpolation and approximation of diffusion tensors-which are symmetric positive definite (SPD) matrices-and use them in developing a significant extension to an existing probabilistic algorithm for scalar field segmentation, in order to segment diffusion tensor magnetic resonance imaging (DT-MRI) datasets. Using the Riemannian metric on the space of SPD matrices, we present a novel and robust higher order (cubic) continuous tensor product of B-splines algorithm to approximate the SPD diffusion tensor fields. The resulting approximations are appropriately dubbed tensor splines. Next, we segment the diffusion tensor field by jointly estimating the label (assigned to each voxel) field, which is modeled by a Gauss Markov measure field (GMMF) and the parameters of each smooth tensor spline model representing the labeled regions. Results of interpolation, approximation, and segmentation are presented for synthetic data and real diffusion tensor fields from an isolated rat hippocampus, along with validation. We also present comparisons of our algorithms with existing methods and show significantly improved results in the presence of noise as well as outliers.

Diffusion magnetic resonance imaging (MRI) is a relatively new imaging modality which is capable of measuring the diffusion of water molecules in biological systems noninvasively. The measurements from diffusion MRI provide unique clues for extracting orientation information of brain white matter fibers and can be potentially used to infer the brain connectivity in vivo using tractography techniques. Diffusion tensor imaging (DTI), currently the most widely used technique, fails to extract multiple fiber orientations in regions with complex microstructure. In order to overcome this limitation of DTI, a variety of reconstruction algorithms have been introduced in the recent past. One of the key ingredients in several model-based approaches is deconvolution operation which is presented in a unified deconvolution framework in this paper. Additionally, some important computational issues in solving the deconvolution problem that are not addressed adequately in previous studies are described in detail here. Further, we investigate several deconvolution schemes towards achieving stable, sparse, and accurate solutions. Experimental results on both simulations and real data are presented. The comparisons empirically suggest that nonnegative least squares method is the technique of choice for the multifiber reconstruction problem in the presence of intravoxel orientational heterogeneity.

In clinical applications where structural asymmetries between homologous shapes have been correlated with pathology, the questions of definition and quantification of "asymmetry" arise naturally. When not only the degree but the position of deformity is thought relevant, asymmetry localization must also be addressed. Asymmetries between paired shapes have already been formulated in terms of (nonrigid) diffeomorphisms between the shapes. For the infinity of such maps possible for a given pair, we define optimality as the minimization of deviation from isometry under the constraint of piecewise deformation homogeneity. We propose a novel variational formulation for segmenting asymmetric regions from surface pairs based on the minimization of a functional of both the deformation map and the segmentation boundary, which defines the regions within which the homogeneity constraint is to be enforced. The functional minimization is achieved via a quasi-simultaneous evolution of the map and the segmenting curve, conducted on and between two-dimensional surface parametric domains. We present examples using both synthetic data and pairs of left and right hippocampal structures and demonstrate the relevance of the extracted features through a clinical epilepsy classification analysis

In this paper, we present a new formulation for recovering the fiber tract geometry within a voxel from diffusion weighted magnetic resonance imaging (MRI) data, in the presence of single or multiple neuronal fibers. To this end, we define a discrete set of diffusion basis functions. The intravoxel information is recovered at voxels containing fiber crossings or bifurcations via the use of a linear combination of the above mentioned basis functions. Then, the parametric representation of the intravoxel fiber geometry is a discrete mixture of Gaussians. Our synthetic experiments depict several advantages by using this discrete schema: the approach uses a small number of diffusion weighted images (23) and relatively small b values (1250 s/mm2), i.e., the intravoxel information can be inferred at a fraction of the acquisition time required for datasets involving a large number of diffusion gradient orientations. Moreover our method is robust in the presence of more than two fibers within a voxel, improving the state-of-the-art of such parametric models. We present two algorithmic solutions to our formulation: by solving a linear program or by minimizing a quadratic cost function (both with non-negativity constraints). Such minimizations are efficiently achieved with standard iterative deterministic algorithms. Finally, we present results of applying the algorithms to synthetic as well as real data.

Many problems in computer vision involving recognition and/or classification can be posed in the general framework of supervised learning. There is however one aspect of image datasets, the high-dimensionality of the data points, that makes the direct application of off-the-shelf learning techniques problematic. In this paper, we present a novel concept class and a companion tractable algorithm for learning a suitable classifier from a given labeled dataset, that is particularly suited to high-dimensional sparse datasets. Each member class in the dataset is represented by a prototype conic section in the feature space, and new data points are classified based on a distance measure to each such representative conic section that is parameterized by its focus, directrix and eccentricity. Learning is achieved by altering the parameters of the conic section descriptor for each class, so as to better represent the data. We demonstrate the efficacy of the technique by comparing it to several well known classifiers on multiple public domain datasets.

In this paper, we propose a novel and robust algorithm for the groupwise non-rigid registration of multiple unlabeled point-sets with no bias toward any of the given point-sets. To quantify the divergence between multiple probability distributions each estimated from the given point sets, we develop a novel measure based on their cumulative distribution functions that we dub the CDF-JS divergence. The measure parallels the well known Jensen-Shannon divergence (defined for probability density functions) but is more regular than the JS divergence since its definition is based on CDFs as opposed to density functions. As a consequence, CDF-JS is more immune to noise and statistically more robust than the JS.We derive the analytic gradient of the CDF-JS divergence with respect to the non-rigid registration parameters for use in the numerical optimization of the groupwise registration leading a computationally efficient and accurate algorithm. The CDF-JS is symmetric and has no bias toward any of the given point-sets, since there is NO fixed reference data set. Instead, the groupwise registration takes place between the input data sets and an evolving target dubbed the pooled model. This target evolves to a fully registered pooled data set when the CDF-JS defined over this pooled data is minimized. Our algorithm is especially useful for creating atlases of various shapes (represented as point distribution models) as well as for simultaneously registering 3D range data sets without establishing any correspondence. We present experimental results on non-rigid registration of 2D/3D real point set data.

Image retrieval is a common problem in many computer vision applications and the literature abounds with techniques with impressive retrieval accuracies. Several of these techniques use probability distributions to represent the "objects" they intend to retrieve. We present a novel approach to search such collections of distributions efficiently. Like many standard data structures, our method uses an "average" to represent a large set (Le., cluster) of objects, thus allowing the search to disregard an unpromising subset with only one comparison to its average. Our contribution lies in choosing the average: Inspired by information theory, we choose a representative that is optimally "close" in a minimax sense to all members of its set when measured using the Kullback-Liebler (KL) divergence. We present a texture retrieval system and test it on the CUReT database, measuring accuracy and efficiency. We find that using the KL-center yields speed ups of more than a factor of three over an exhaustive search while guaranteeing identical accuracy. The KL-center also out-performs other commonly used representatives such as the arithmetic mean. Although we present results only in texture retrieval, our approach will likely aid image and shape retrieval as well.

This paper proposes a novel and robust approach to the point set registration problem in the presence of large amounts of noise and outliers. Each of the point sets is represented by a mixture of Gaussians and the point set registration is treated as a problem of aligning the two mixtures. We derive a closed-form expression for the L(2) distance between two Gaussian mixtures, which in turn leads to a computationally efficient registration algorithm. This new algorithm has an intuitive interpretation, is simple to implement and exhibits inherent statistical robustness. Experimental results indicate that our algorithm achieves very good performance in terms of both robustness and accuracy.

In recent years, diffusion tensor imaging (DTI) has become a popular in vivo diagnostic imaging technique in Radiological sciences. In order for this imaging technique to be more effective, proper image analysis techniques suited for analyzing these high dimensional data need to be developed. In this paper, we present a novel definition of tensor "distance" grounded in concepts from information theory and incorporate it in the segmentation of DTI. In a DTI, the symmetric positive definite (SPD) diffusion tensor at each voxel can be interpreted as the covariance matrix of a local Gaussian distribution. Thus, a natural measure of dissimilarity between SPD tensors would be the Kullback-Leibler (KL) divergence or its relative. We propose the square root of the J-divergence (symmetrized KL) between two Gaussian distributions corresponding to the diffusion tensors being compared and this leads to a novel closed form expression for the "distance" as well as the mean value of a DTI. Unlike the traditional Frobenius norm-based tensor distance, our "distance" is affine invariant, a desirable property in segmentation and many other applications. We then incorporate this new tensor "distance" in a region based active contour model for DTI segmentation. Synthetic and real data experiments are shown to depict the performance of the proposed model.

In this paper, we use the cumulative distribution of a random variable to define its information content and thereby develop an alternative measure of uncertainty that extends Shannon entropy to random variables with continuous distributions. We call this measure cumulative residual entropy (CRE). The salient features of CRE are as follows: 1) it is more general than the Shannon entropy in that its definition is valid in the continuous and discrete domains, 2) it possesses more general mathematical properties than the Shannon entropy, and 3) it can be easily computed from sample data and these computations asymptotically converge to the true values. The properties of CRE and a precise formula relating CRE and Shannon entropy are given in the paper. Finally, we present some applications of CRE to reliability engineering and computer vision.

In this paper, we present a novel constrained variational principle for simultaneous smoothing and estimation of the diffusion tensor field from complex valued diffusion-weighted images (DWI). The constrained variational principle involves the minimization of a regularization term of L(P) norms, subject to a nonlinear inequality constraint on the data. The data term we employ is the original Stejskal-Tanner equation instead of the linearized version usually employed in literature. The complex valued nonlinear form leads to a more accurate (when compared to the linearized version) estimate of the tensor field. The inequality constraint requires that the nonlinear least squares data term be bounded from above by a known tolerance factor. Finally, in order to accommodate the positive definite constraint on the diffusion tensor, it is expressed in terms of Cholesky factors and estimated. The constrained variational principle is solved using the augmented Lagrangian technique in conjunction with the limited memory quasi-Newton method. Experiments with complex-valued synthetic and real data are shown to depict the performance of our tensor field estimation and smoothing algorithm.

Diffusion tensor magnetic resonance imaging (DT-MRI) is a relatively new imaging modality in the field of medical imaging. This modality of imaging allows one to capture the structural connectivity if any between functionally meaningful regions for example, in the brain. The data however can be noisy and requires restoration. In this paper, we present a unified model for simultaneous smoothing and estimation of diffusion tensor field from DT-MRI. The diffusion tensor field is estimated directly from the raw data with L/sup P/ smoothness and positive definiteness constraints. The data term we employ is from the original Stejskal-Tanner equation instead of the linearized version as usually done in literature. In addition, we use Cholesky decomposition to ensure positive definiteness of the diffusion tensor. The unified model is discretized and solved numerically using limited memory quasi-Newton method. Both synthetic and real data experiments are shown to depict the algorithm performance.

We use the cumulative distribution of a random variable to define the information content in it and use it to develop a novel measure of information that parallels Shannon entropy, which we dub cumulative residual entropy (CRE). The key features of CRE may be summarized as, (1) its definition is valid in both the continuous and discrete domains, (2) it is mathematically more general than the Shannon entropy and (3) its computation from sample data is easy and these computations converge asymptotically to the true values. We define the cross-CRE (CCRE) between two random variables and apply it to solve the uni- and multimodal image alignment problem for parameterized (rigid, affine and projective) transformations. The key strengths of the CCRE over using the now popular mutual information method (based on Shannon's entropy) are that the former has significantly larger noise immunity and a much larger convergence range over the field of parameterized transformations. These strengths of CCRE are demonstrated via experiments on synthesized and real image data.

Automatic registration of multimodal images involves algorithmically estimating the coordinate transformation required to align the data sets. Most existing methods in the literature are unable to cope with registration of image pairs with large nonoverlapping field of view (FOV). We propose a robust algorithm, based on matching dominant local frequency image representations, which can cope with image pairs with large nonoverlapping FOV. The local frequency representation naturally allows for processing the data at different scales/resolutions, a very desirable property from a computational efficiency view point. Our algorithm involves minimizing-over all rigid/affine transformations--the integral of the squared error (ISE or L2 E) between a Gaussian model of the residual and its true density function. The residual here refers to the difference between the local frequency representations of the transformed (by an unknown transformation) source and target data. We present implementation results for image data sets, which are misaligned magnetic resonance (MR) brain scans obtained using different image acquisition protocols as well as misaligned MR-computed tomography scans. We experimently show that our L2E-based scheme yields better accuracy over the normalized mutual information.

Automatic three-dimensional (3-D) segmentation of the brain from magnetic resonance (MR) scans is a challenging problem that has received an enormous amount of attention lately. Of the techniques reported in the literature, very few are fully automatic. In this paper, we present an efficient and accurate, fully automatic 3-D segmentation procedure for brain MR scans. It has several salient features; namely, the following. 1) Instead of a single multiplicative bias field that affects all tissue intensities, separate parametric smooth models are used for the intensity of each class. 2) A brain atlas is used in conjunction with a robust registration procedure to find a nonrigid transformation that maps the standard brain to the specimen to be segmented. This transformation is then used to: segment the brain from nonbrain tissue; compute prior probabilities for each class at each voxel location and find an appropriate automatic initialization. 3) Finally, a novel algorithm is presented which is a variant of the expectation-maximization procedure, that incorporates a fast and accurate way to find optimal segmentations, given the intensity models along with the spatial coherence assumption. Experimental results with both synthetic and real data are included, as well as comparisons of the performance of our algorithm with that of other published methods.

We present a new algorithm for the efficient estimation of piecewise parametric models for image segmentation. This algorithm permits the simultaneous estimation of: the number of models; the parameters for each model and the regions where each model is applicable. It is based on Bayesian estimation theory, and is theoretically justified by the use of a specific cost function that decreases at every iteration and by a new model for the posterior marginal distributions which is amenable to the use of fast computational methods.

Fusing of multi-modal data involves automatically estimating the coordinate transformation required to align the multi-modal image data sets. Most existing methods in literature are not fast enough (take hours for estimating nonrigid deformations) for practical use. We propose a very fast algorithm, based on matching local-frequency image representations, which naturally allows for processing the data at different scales/resolutions, a very desirable property from a computational efficiency view point. This algorithm involves minimizing-over all affine transformations-the expectation of the squared difference between the local-frequency representations of the source and target images. In cases where fusing the multi-modal data requires estimating the non-rigid deformations, we propose a novel and fast PDE-based morphing technique that will estimate this non-rigid alignment. We present implementation results for synthesized and real misalignments between CT and MR brain scans. In both the cases, we validate our results against ground truth registrations which for the former case are known and for the latter are obtained from manual registration performed by an expert.

We introduce a geometric shape modeling scheme which allows for representation of global and local shape characteristics of an object. Geometric models are well-suited for representing global shapes without local detail, but we propose a scheme which represents global shapes with local detail and permits model shaping as well as topological changes via physics-based control. The scheme represents shapes by pedal curves and surfaces, i.e. the loci of the foot of perpendiculars to the tangents of a fixed curve/surface from a fixed point called the pedal point. By varying the location of the pedal point, one can synthesize a large class of shapes which exhibit both local and global deformations. We introduce physics-based control for shaping these geometric models by letting the pedal point vary and use a snake to represent the position of this varying point. The model, a "snake pedal", allows for interactive manipulation via forces applied to the snake. We develop a fast numerical iterative algorithm for shape recovery from image data using this scheme. The algorithm involves the Levenberg-Marquardt (LM) method in the outer loop for solving the global parameters and the alternating direction implicit (ADI) method in the inner loop for solving the local parameters of the model. The combination of the global and local scheme leads to an efficient numerical solution to the model fitting problem. We demonstrate the applicability of this modeling scheme via examples of shape synthesis and shape estimation from real image data.

The authors develop integrated techniques that unify physics based modeling with geometric subdivision methodology and present a scheme for dynamic manipulation of the smooth limit surface generated by the (modified) butterfly scheme using physics based "force" tools. This procedure based surface model obtained through butterfly subdivision does not have a closed form analytic formulation (unlike other well known spline based models), and hence poses challenging problems to incorporate mass and damping distributions, internal deformation energy, forces, and other physical quantities required to develop a physics based model. Our primary contributions to computer graphics and geometric modeling include: (1) a new hierarchical formulation for locally parameterizing the butterfly subdivision surface over its initial control polyhedron, (2) formulation of dynamic butterfly subdivision surface as a set of novel finite elements, and (3) approximation of this new type of finite elements by a collection of existing finite elements subject to implicit geometric constraints. Our new physics based model can be sculpted directly by applying synthesized forces and its equilibrium is characterized by the minimum of a deformation energy subject to the imposed constraints. We demonstrate that this novel dynamic framework not only provides a direct and natural means of manipulating geometric shapes, but also facilitates hierarchical shape and nonrigid motion estimation from large range and volumetric data sets using very few degrees of freedom (control vertices that define the initial polyhedron).

Image denoising and segmentation are fundamental problems in the field of image processing and computer vision with numerous applications. We propose a partial differential equation (PDE) based smoothing and segmentation framework wherein the image data are smoothed via an evolution equation that is controlled by a vector field describing a viscous fluid flow. Image segmentation in this framework is defined by locations in the image where the fluid velocity is a local maximum. The nonlinear image smoothing is selectively achieved to preserve edges in the image. The novelty of this approach lies in the fact that the selective term is derived from a nonlinearly regularized image gradient field unlike most earlier techniques which either used a constant (with respect to time) selective term or a time varying nonlinearly smoothed scalar valued term. Implementation results on synthetic and real images are presented to depict the performance of the technique in comparison to methods recently reported in literature.

A new dynamic subdivision surface model is proposed for shape recovery from 3D data sets. The model inherits the attractive properties of the Catmull-Clark subdivision scheme and is set in a physics-based modeling paradigm. Unlike other existing methods, our model does not require a parameterized input mesh to recover shapes of arbitrary topology, allows direct manipulation of the limit surface via application of forces and provides a fast, robust, and hierarchical approach to recover complex shapes from 3D data with very few degrees of freedom (control vertices). We provide an analytic formulation and introduce the physical quantities required to develop the dynamic subdivision surface model which can be deformed by applying forces synthesized from the data. Our experiments demonstrate that this new dynamic model has a promising future in shape recovery from volume and range data sets.

In this paper, we introduce a novel geometric shape modeling scheme which allows for representation, of global and local shape characteristics of an object. Geometric models are traditionally well suited for representing global shapes but not the local details. However, in this paper we propose a powerful geometric shape modeling scheme which allows for the representation of global shapes with local detail and permits model shaping as well as topological changes via physics-based control. The proposed modeling scheme consists of representing shapes by pedal curves and surfaces-pedal curves/surfaces are the loci of the foot of perpendiculars to the tangents of a fixed curve/surface from a fixed point called the pedal point. By varying the location of the pedal point, one can synthesize a large class of shapes which exhibit both local and global deformations. We introduce physics-based control for shaping these geometric models by letting the pedal point vary and use a dynamic spline to represent the position of this varying pedal point. The model dubbed as a "snake pedal" allows for interactive manipulation via forces applied to the snake. We demonstrate the applicability of this modeling scheme via examples of shape synthesis and shape estimation from real image data.

In this paper, we present efficient algorithms for collision detection of arbitrarily shaped rigid moving objects in a variety of interactive as well as non‐interactive environments. The algorithms primarily consist of two stages. The first stage involves finding candidate objects for possible collisions. The second stage involves detecting exact (within a prespecified tolerance) collision between these candidates. The primary data structure used in the algorithms is an octree. In the first stage, we build an octree for the enclosure containing the objects, which is used to detect possible collisions. Assuming spatial/temporal coherence i.e., that the particles move slowly or that the time sampling is fast enough, the average time complexity of this stage can be shown to be O(n) (excluding the time complexity for a one time octree construction), where n is the number of particles. In the second stage, we build a surface‐octree for each object. If the objects are convex and assuming coherence, the expected time complexity to detect precise (within a prespecified tolerance) collision for each pair is a constant (excluding the time complexity for a one time surface‐octree construction). Therefore, the overall expected time complexity for convex object collision detection is linear with respect to n. For the concave objects, complexity analysis is nontrivial to perform and instead we provide a very practical (almost linear time) algorithm. We apply our algorithms to particle flow simulations by simulating flow density conditions often arising in granular flows.

Recursive subdivision schemes have been extensively used in computer graphics, computer-aided geometric design, and scientific visualization for modeling smooth surfaces of arbitrary topology. Recursive subdivision generates a visually pleasing smooth surface in the limit from an initial user-specified polygonal mesh through the repeated application of a fixed set of subdivision rules. We present a new dynamic surface model based on the Catmull-Clark subdivision scheme, a popular technique for modeling complicated objects of arbitrary genus. Our new dynamic surface model inherits the attractive properties of the Catmull-Clark subdivision scheme, as well as those of the physics-based models. This new model provides a direct and intuitive means of manipulating geometric shapes, and an efficient hierarchical approach for recovering complex shapes from large range and volume data sets using very few degrees of freedom (control vertices). We provide an analytic formulation and introduce the "physical" quantities required to develop the dynamic subdivision surface model which can be interactively deformed by applying synthesized forces. The governing dynamic differential equation is derived using Lagrangian mechanics and the finite element method. Our experiments demonstrate that this new dynamic model has a promising future in computer graphics, geometric shape design, and scientific visualization.

Recursive subdivision schemes have been extensively used in computer graphics and scientific visualization for modeling smooth surfaces of arbitrary topology. Recursive subdivision generates a visually pleasing smooth surface in the limit from an initial user-specified polygonal mesh through the repeated application of a fixed set of subdivision rules. In this paper, we present a new dynamic surface model based on the Catmull-Clark (1978) subdivision scheme, which is a very popular method to model complicated objects of arbitrary genus because of many of its nice properties. Our new dynamic surface model inherits the attractive properties of the Catmull-Clark subdivision scheme as well as that of the physics-based modeling paradigm. This new model provides a direct and intuitive means of manipulating geometric shapes, a fast, robust and hierarchical approach for recovering complex geometric shapes from range and volume data using very few degrees of freedom (control vertices). We provide an analytic formulation and introduce the physical quantities required to develop the dynamic subdivision surface model which can be interactively deformed by applying synthesized forces in real time. The governing dynamic differential equation is derived using Lagrangian mechanics and a finite element discretization. Our experiments demonstrate that this new dynamic model has a promising future in computer graphics, geometric shape design and scientific visualization.

Several problems in early vision have been formulated in the past in a regularization framework. These problems, when discretized, lead to large sparse linear systems. In this paper, we present a novel physically based adaptive preconditioning technique which can be used in conjunction with a conjugate gradient algorithm to dramatically improve the speed of convergence for solving the aforementioned linear systems. A preconditioner, based on the membrane spline, or the thin plate spline, or a convex combination of the two, is termed a physically based preconditioner for obvious reasons. The adaptation of the preconditioner to an early vision problem is achieved via the explicit use of the spectral characteristics of the regularization filter in conjunction with the data. This spectral function is used to modulate the frequency characteristics of a chosen wavelet basis, and these modulated values are then used in the construction of our preconditioner. We present the preconditioner construction for three different early vision problems namely, the surface reconstruction, the shape from shading, and the optical flow computation problems. Performance of the preconditioning scheme is demonstrated via experiments on synthetic and real data sets.

It is well known that the spatial frequency spectrum of membrane and thin plate splines exhibit self-affine characteristics and, hence, behave as fractals. This behavior was exploited in generating the constrained fractal surfaces, which were generated by using a Gibbs sampler algorithm in the work of Szeliski and Terzopoulos (1989). The algorithm involves locally perturbing a constrained spline surface with white noise until the spline surface reaches an equilibrium state. We introduce a fast generalized Gibbs sampler that combines two novel techniques, namely, a preconditioning technique in a wavelet basis for constraining the splines and a perturbation scheme in which, unlike the traditional Gibbs sampler, all sites (surface nodes) that do not share a common neighbor are updated simultaneously. In addition, we demonstrate the capability to generate arbitrary order fractal surfaces without resorting to blending techniques. Using this fast Gibbs sampler algorithm, we demonstrate the synthesis of realistic terrain models from sparse elevation data.

It is well known that the spatial frequency spectra of membrane and thin-plate splines exhibit self-affine characteristics and hence behave as fractals. This behavior was exploited in generating the constrained fractal surfaces in the work of Szeliski and Terzopoulos (1989), which were generated by using a Gibbs sampler algorithm. The algorithm involves locally perturbing a constrained spline surface with white noise until the spline surface reaches an equilibrium state. In this paper, we introduce a very fast generalized Gibbs sampler that combines two novel techniques, namely a preconditioning technique in a wavelet basis for constraining the splines and a perturbation scheme in which, unlike the traditional Gibbs sampler, all sites (surface nodes) that do not share a common neighbor are updated simultaneously. In addition, we demonstrate the capability to generate arbitrary-order fractal surfaces without resorting to blending techniques. Using this fast Gibbs sampler algorithm, we demonstrate the synthesis of realistic terrain models from sparse elevation data.

Shape modeling is an important constituent of computer vision as well as computer graphics research. Shape models aid the tasks of object representation and recognition. This paper presents a new approach to shape modeling which retains some of the attractive features of existing methods and overcomes some of their limitations. The authors' techniques can be applied to model arbitrarily complex shapes, which include shapes with significant protrusions, and to situations where no a priori assumption about the object's topology is made. A single instance of the authors' model, when presented with an image having more than one object of interest, has the ability to split freely to represent each object. This method is based on the ideas developed by Osher and Sethian (1988) to model propagating solid/liquid interfaces with curvature-dependent speeds. The interface (front) is a closed, nonintersecting, hypersurface flowing along its gradient field with constant speed or a speed that depends on the curvature. It is moved by solving a "Hamilton-Jacobi" type equation written for a function in which the interface is a particular level set. A speed term synthesized from the image is used to stop the interface in the vicinity of object boundaries. The resulting equation of motion is solved by employing entropy-satisfying upwind finite difference schemes. The authors present a variety of ways of computing the evolving front, including narrow bands, reinitializations, and different stopping criteria. The efficacy of the scheme is demonstrated with numerical experiments on some synthesized images and some low contrast medical images.>

In this paper, we present a novel iterative numerical solution to the Poisson equation whose solution is needed in a variety of low-level vision problems. Our algorithm is an O(N) (N being the number of discretization points) iterative technique and does not make any assumptions on the shape of the input domain unlike the polyhedral domain assumption in the proof of convergence of multigrid techniques. We present two major results namely, a generalized version of the capacitance matrix theorem and a theorem on O(N) convergence of the alternating direction implicit method (ADI) used in our algorithm. Using this generalized theorem, we express the linear system corresponding to the discretized Poisson equation as a Lyapunov and a capacitance matrix equation. The former is solved using the ADI method while the solution to the later is obtained using a modified bi-conjugate gradient algorithm. We demonstrate the algorithm performance on synthesized data for the surface reconstruction and the SFS problems.>

3D shape modeling has received enormous attention in computer graphics and computer vision over the past decade. Several shape modeling techniques have been proposed in literature, some are local (distributed parameter) while others are global (lumped parameter) in terms of the parameters required to describe the shape. Hybrid models that combine both ends of this parameter spectrum have been in vogue only recently. However, they do not allow a smooth transition between the two extremes of this parameter spectrum. We introduce a new shape-modeling scheme that can transform smoothly from local to global models or vice versa. The modeling scheme utilizes a hybrid primitive called the deformable superquadric constructed in an orthonormal wavelet basis . The multiresolution wavelet basis provides the power to continuously transform from local to global shape deformations and thereby allow for a continuum of shape models—from those with local to those with global shape descriptive power—to be created. The multiresolution wavelet basis allows us to generate fractal surfaces of arbitrary order that can be useful in describing natural detail. We embed these multiresolution shape models in a probabilistic framework and use them for recovery of anatomical structures in the human brain from MRI data. A salient feature of our modeling scheme is that it can naturally allow for the incorporation of prior statistics of a rich variety of shapes. This stems from the fact that, unlike other modeling schemes, in our modeling, we require relatively few parameters to describe a large class of shapes.

A new shape modeling scheme is introduced. It can transform smoothly from local (distributed parameter) to global (lumped parameter) models or vice-versa. The modeling scheme makes use of a hybrid primitive, called the deformable superquadric, constructed in an orthonormal wavelet basis. This multiresolution basis provides the power to continuously transform from local to global shape deformations, and thereby allow for a continuum of shape models-from those with local to those with global shape descriptive power-to be created. The characteristic of continuously transforming from local to global shape deformations allows the generation of fractal surfaces of arbitrary degree that can be useful in describing natural detail. These multiresolution shape models reembedded in a probabilistic framework and used for segmenting anatomical structures in the human brain from magnetic resonance imaging (MRI) data.>

A technique for constructing a canonical surface parameterization in terms of lines of curvature is presented. Two methods of computing the canonical invariant representation are also presented. In the first method, a static instance of the controlled continuity spline is used for the stabilizer. Ways to modify it to reflect a change of parameters to the lines of curvature are described. In the second method, the dynamic instance of the controlled continuity spline called the deformable model is used. A force field defined in terms of the principal vectors is synthesized and applied to the parameter curves of the deformable model to coerce them along the lines of curvature. In essence, any transformation of parameters requires a modification of the stabilizer in the first method, whereas in the second method, it is tantamount to synthesizing a new force field. Experimental results with real and synthetic range data are included.>

A canonical intrinsic parameterization that provides a consistent, invariant form for describing surfaces is defined and constructed using an elastically deformable model. The salient features of this method are that it provides a unified and general framework for reparameterization of a surface and easily allows for incorporation of multiview data sets. The canonical parameterization of the surface is defined in terms of the surface lines of curvature. Depth constraints are first imposed as an external force field on the deformable model that molds itself to be consistent with the data. Principal vectors computed from this conformed model surface are then imposed as a force field on the parameter curves of the model. The parameter curves deform to become tangential to the principal vectors thereby yielding an invariant surface parameterized by the lines of curvature. Extension of the canonical parametric grid to multiple views is demonstrated by incorporating depth and curvature constraints from multiple views.>

Describes techniques for stabilizing the implicit function fitting process. The key drawback of implicit function fitting methods described in literature thus far has been the stability with respect to outliners in the data. In this paper methods for stabilizing the implicit function fitting using additional constraints in the form of surface (curve) normals are described. These constraints eliminate the problem of sensitivity of the implicit function fitting method to outliners in the data. The authors demonstrate that in certain cases the fitting process can be reduced to a generalized eigenvalue problem that can be efficiently solved by standard numerical procedures. Preliminary experimental results with 2D curves consisting of point location and curve normal constraints as data are encouraging.>

A system is presented for the simultaneous estimation of surface and motion parameters of a free-flying object in a telerobotics experiment. The system consists of two main components, a vision-based invariant-surface and motion estimator, and a Kalman filter. An algorithm for invariant surface and motion estimation from sparse multi-sensor range data is presented. Motion estimates from the vision module are input to a Kalman filter (KF) for tracking a 'free-flying' object in space. The predicted motion parameters from the KF are fed back to the vision module and serve as an initial guess in the search for optimal motion.>

A survey is presented of some of the surface reconstruction methods that can be found in the literature; the focus is on a small, recent, and important subset of the published reconstruction techniques. The techniques are classified based on the surface representation used, implicit versus explicit functions. A study is made of the important aspects of the surface reconstruction techniques. One aspect is the viewpoint invariance of the methods. This is an important property if object recognition is the ultimate objective. The robustness of the various methods is examined. It is determined whether the parameter estimates are biased, and the sensitivity to obscuration is addressed. The latter two aspects are particularly important for fitting functions in the implicit form. A detailed description is given of a parametric reconstruction method for three-dimensional object surfaces that involves numeric grid generation techniques and variational principle formulations. This technique is invariant to rigid motion in dimensional space.>

A technique is presented for determining the orientation of an object from single-view range data. The objects and models are represented by regions that are a collection of surface patches homogeneous in curvature-based properties. Given exactly one point on the surface of the unknown view of an object and the corresponding point on the surface of the model of the object, the principal vectors (if unique) can be used to determine the 3-D rotation required to bring the model into the same orientation as that of the object. To determine this one-point correspondence, curves of constant principal curvature are extracted from the surfaces (corresponding to regions possessing the same sign of the principal curvatures) of the model and the unknown view of an object. Then, the local maxima in the curvature of these curves are utilized as a means to establish the one-point correspondence.>