Given a map $f:X \to M$ from a topological space $X$ to a metric space $M$, a decorated Reeb space consists of the Reeb space, together with an attribution function whose values recover geometric information lost during the construction of the Reeb space. For example, when $M=\mathbb{R}$ is the real line, the Reeb space is the well-known Reeb graph, and the attributions may consist of persistence diagrams summarizing the level set topology of $f$. In this paper, we introduce decorated Reeb spaces in various flavors and prove that our constructions are Gromov-Hausdorff stable. We also provide results on approximating decorated Reeb spaces from finite samples and leverage these to develop a computational framework for applying these constructions to point cloud data.

Understanding the underlying mechanisms that enable the empirical successes of deep neural networks is essential for further improving their performance and explaining such networks. Towards this goal, a specific question is how to explain the "surprising" behavior of the same over-parametrized deep neural networks that can generalize well on real datasets and at the same time "memorize" training samples when the labels are randomized. In this paper, we demonstrate that deep ReLU networks generalize from training samples to new points via piece-wise linear interpolation. We provide a quantified analysis on the generalization ability of a deep ReLU network: Given a fixed point x and a fixed direction in the input space $\mathcal{S}$, there is always a segment such that any point on the segment will be classified the same as the fixed point x. We call this segment the generalization interval. We show that the generalization intervals of a ReLU network behave similarly along pairwise directions between samples of the same label in both real and random cases on the MNIST and CIFAR-10 datasets. This result suggests that the same interpolation mechanism is used in both cases. Additionally, for datasets using real labels, such networks provide a good approximation of the underlying manifold in the data, where the changes are much smaller along tangent directions than along normal directions. Our systematic experiments demonstrate for the first time that such deep neural networks generalize through the same interpolation and explain the differences between their performance on datasets with real and random labels.

We present a novel framework for image segmentation based on the maximum likelihood estimator. A common hypothesis for explaining the differences among image regions is that they are generated by sampling different likelihood functions called models. In this work, we construct on last hypothesis and, additionally, we assume that such samples come from independent and identically distributed random variables. Thus, the probability (likelihood) that a particular model generates the observed value (at a given pixel) is estimated by computing the likelihood of the sample composed with the surrounding pixels. This simple approach allows us to propose efficient segmentation methods able to deal with textured images. Our approach is naturally extended for combining different features. Experiments in interactive image segmentation, automatic stereo analysis and denoising of brain water diffusion multi-tensor fields demonstrate the capabilities of our approach.

Several variants of Linear Discriminant Analysis (LDA) have been investigated to address the vanishing of the within-class scatter under projection to a low-dimensional subspace in LDA. However, some of these proposals are ad hoc and some others do not address the problem of generalization to new data. Meanwhile, even though LDA is preferred in many application of dimension reduction, it does not always outperform Principal Component Analysis (PCA). In order to optimize discrimination performance in a more generative way, a hybrid dimension reduction model combining PCA and LDA is proposed in this paper. We also present a dimension reduction algorithm correspondingly and illustrate the method with several experiments. Our results have shown that the hybrid model outperform PCA, LDA and the combination of them in two separate stages.

We construct a scale space of shape of closed Riemannian manifolds, equipped with metrics derived from spectral representations and the Hausdorff distance. The representation depends only on the intrinsic geometry of the manifolds, making it robust to pose and articulation. The computation of shape distance involves an optimization problem over the 2p-element group of all p-bit strings, which is approached with Markov chain Monte Carlo techniques. The methods are applied to cluster surfaces in 3D space.

We propose a family of shape metrics that generalize the classical Procrustes distance by attributing weights to general linear combinations of landmarks. We develop an algorithm to learn a metric that is optimally suited to a given shape classification problem. Shape discrimination experiments are carried out with phantom data, as well as landmark data representing the shape of the wing of different species of fruit flies.

We develop a computational model of shape that extends existing Riemannian models of curves to multidimensional objects of general topological type. We construct shape spaces equipped with geodesic metrics that measure how costly it is to interpolate two shapes through elastic deformations. The model employs a representation of shape based on the discrete exterior derivative of parametrizations over a finite simplicial complex. We develop algorithms to calculate geodesics and geodesic distances, as well as tools to quantify local shape similarities and contrasts, thus obtaining a formulation that accounts for regional differences and integrates them into a global measure of dissimilarity. The Riemannian shape spaces provide a common framework to treat numerous problems such as the statistical modeling of shapes, the comparison of shapes associated with different individuals or groups, and modeling and simulation of shape dynamics. We give multiple examples of geodesic interpolations and illustrations of the use of the models in brain mapping, particularly, the analysis of anatomical variation based on neuroimaging data.

Representation learning is a fundamental challenge for feature selection and plays an important role in applications such as dimension reduction, data mining and object recognition. Traditional linear representation methods, such as principal component analysis (PCA), independent component analysis (ICA) and linear discriminate analysis (LDA), have good performance on certain applications based on corresponding criteria. However, these linear representation methods are not optimal in general. Sphere factor analysis (SFA) is a recently proposed method which provides a general framework for optimization problems. In term of object recognition, SFA seeks to optimize the discriminant ability of the nearest neighbor classifier for data classification and labeling. Based on the geometry structure of the search space, a gradient search algorithms have been applied to obtain an optimal basis. A detail presentation of these algorithm is given in this paper. Furthermore, to speed up the search procedure of SFA, a two-stage strategy is proposed, which we called two-stage SFA. We illustrate the effectiveness of the original SFA and two-stage SFA methods on UCI data sets and two face data sets.

The spectral histogram features are not invariant to images' scale transformation. We investigate in the technique of scale-invariant feature extraction. An approach is proposed to get the characteristic scales based on the reliable keypoints which are detected as local extrema in combination of normalized derivatives. Making use of characteristic scale of image content, which reflects characteristic length of a corresponding image structure, we are able to contribute in eliminating the effect of image transformation. In our content based image retrieval process, images are firstly resized by the characteristic scale and then represented based on the statistics of their spectral components and a linear dimension reduction technique optimizing class differentiation with respect to cross-correlation metrics of spectral histograms. Our retrieval consists of a preliminary classification step to index images in dataset and a following step of class by class retrieval. Experiments are performed on the Corel database and the outcome is compared with those of some existing work.

We investigate content-based image retrieval employing a representation of images based on the statistics of their spectral components and a new linear dimension reduction technique. This linear dimension reduction technique is designed to optimize class separation with respect to metrics derived from cross-correlation of spectral histograms. Our approach to retrieval involves a preliminary classification step to index images in a database followed by a class-by-class retrieval step. We carry out several experiments with the Corel database and compare the outcome with several results previously reported in the literature.

Registration of 3D surfaces is a critical step for shape analysis. Recent studies show that spectral representations based on intrinsic pairwise geodesic distances between points on surfaces are effective for registration and alignment due to their invariance under rigid transformations and articulations. Kernel functions are often applied to the pairwise geodesic distances to make the registration process based on spectral embedding robust to elastic deformations. The Gaussian kernel is most commonly used, but the effect of the choice of the kernel function has not been studied in the previous works. In this paper, we compare the results obtained with several different choices and show empirically that significant improvements can be achieved in shape registration with appropriate choices.

We propose a new transductive learning algorithm for learning optimal linear representations that utilizes unlabeled data. We pose the problem of learning linear representations as an optimization one on the underlying nonlinear manifold. An additional term is used to prefer representations with large ldquomarginsrdquo when classifying unlabeled data in the nearest classifier sense, a generalization of transductive support vector machines to learning representations. Experimental results of the proposed algorithm on face recognition data sets show the potential significant improvement for classification accuracy on test sets.

We employ 3D arrangements of curves to represent and analyze biological shapes, in particular, the anatomy of the human brain. The arrangements of curves may vary from fairly sparse - such as a collection of sulcal lines that coarsely approximates the global shape of the brain - to very dense decompositions of the cortical surface into space curves. A space of shapes of such arrangements is constructed equipped with geodesic metrics that can be used in conjunction with curve registration techniques to quantify shape resemblance or dissimilarity, as well as to identify the regions where anatomical differences are most pronounced. The metric is applied to the panellation and labeling of configurations associated with the left and right hemispheres of the brain. Examples are also given of geodesic interpolations between decompositions into space curves of surfaces representing the entire left hemisphere of the brain.

We propose a neural network based method for organizing images for content-based image retrieval. We use spectral histogram features, the histograms of filtered images to capture the spatial relationship among pixels as well as global appearance of images. We then find the optimal combination of spectral histogram features using optimal factor analysis to reduce the dimension of features and maximize the discrimination. The reduced features are then used as input to a multiple layer perceptron, which is trained to categorize images based on content using back propagation. For a query image, images are retrieved from different classes based on the categorization probability for the query image. Experimental results on a subset of Corel dataset demonstrate the effectiveness of the proposed method and comparisons show that the proposed method gives significant improvement over other methods.

Optimal component analysis (OCA) is a linear method for feature extraction and dimension reduction. It has been widely used in many applications such as face and object recognitions. The optimal basis of OCA is obtained through solving an optimization problem on a Grassmann manifold. However, one limitation of OCA is the computational cost becoming heavy when the number of training data is large, which prevents OCA from efficiently applying in many real applications. In this paper, a scalable OCA (S-OCA) that uses a two-stage strategy is developed to bridge this gap. In the first stage, we cluster the training data using K-means algorithm and the dimension of data is reduced into a low dimensional space. In the second stage, OCA search is performed in the reduced space and the gradient is updated using an numerical approximation. In the process of OCA gradient updating, instead of choosing the entire training data, S-OCA randomly chooses a small subset of the training images in each class to update the gradient. This achieves stochastic gradient updating and at the same time reduces the searching time of OCA in orders of magnitude. Experimental results on face and object datasets show efficiency of the S-OCA method, in term of both classification accuracy and computational complexity.

Optimal component analysis (OCA) uses a stochastic gradient optimization process to find optimal representations for general criteria and shows good performance in object recognition applications. However, OCA often requires extensive computation for gradient estimation and linear representation updating. To significantly reduce the required computation, in this paper, a multi-stage learning process is proposed which decomposes the original optimization problem into several levels. As the learning process at each level starts with a good initial point obtained from next level, the multistage OCA algorithm can speed up the original algorithm significantly and make OCA learning feasible for many applications. We illustrate the effectiveness of the proposed method on the application of face classification.

This paper proposes a method to achieve object classification with high throughput and accuracy using a rapid classification tree. To achieve this, we decouple the training and test stages. During the training stage, we learn optimal discriminatory features from the training set and then train a classifier with high accuracy. Then we create a classification tree, where each node uses a lookup table to store the solutions, resulting high throughput at the test stage. To make the lookup tables feasible for applications, we learn a projection matrix through stochastic optimization. We illustrate the effectiveness of the proposed method using several datasets; our results show the proposed method achieves often several orders of magnitudes of improvement in throughput while maintaining a similar accuracy.

We develop splitting factor analysis (SFA), a novel linear model selection technique for dimension reduction that seeks to optimize the discriminative ability of the nearest neighbor classifier for data classification and labeling. We also discuss methodology for data kernelization that can be used in conjunction with any model selection technique. Applied to SFA, it leads to KSFA, a powerful new technique for the analysis of datasets with essential nonlinearities underlying their structures. For computational efficiency in the analysis of large datasets, we combine weak KSFA classifiers with multi-class boosting techniques. Several applications to image-based classification are discussed.

We develop computational strategies to calculate geodesies and geodesic distances between plane shapes represented by mixture of Gaussians centered at landmark points with a fixed variance with respect to the information-theoretic Fisher-Rao metric. This representation and metric have been investigated recently by Peter and Rangarajan, but a feasible computational approach was not provided. The algorithms developed are applied to shape clustering and the results are compared to those obtained with other methods.

Linear representations are widely used to reduce dimension in applications involving high dimensional data. While specialized procedures exist for certain optimality criteria, such as principle component analysis (PCA) and Fisher discriminant analysis (FDA), they can not be generalized for more general criteria. To overcome this fundamental limitation, optimal component analysis (OCA) uses a stochastic gradient optimization procedure intrinsic to the manifold giving by the constraints of applications and therefore gives a procedure for finding optimal representations for general criteria. However, due to its generality nature, OCA often requires extensive computation for gradient estimation and updating. To significantly reduce the required computation, in this paper, we propose a two-stage method by first reducing the dimension of input to a smaller one (but larger than the final resulting dimension) using a computationally efficient method and then performing OCA in the reduced space. This reduces the computation time from days to minutes on widely used databases, making OCA learning feasible for many applications. Additionally, since the reduced space is much smaller, the stochastic gradient optimization tends to be more efficient. We illustrate the effectiveness of the proposed method on face classification.

Three dimensional objects viewed as surfaces or volumes embedded in /spl Ropf//sup 3/, are usually sampled along the z-dimension by planes for rendering or modeling purposes. The resulting intersections are curves or planar shapes which may in turn be modeled for parsimony of representation. Each curve or planar shape may be viewed as a point in a high dimensional manifold, thereby providing the notion of interpolation between two curves or two points on this manifold to reconstruct the subsurface that lies between the two slices. We exploit some recent results in formulating this interpolation problem as an optimization problem in /spl Ropf//sup 3/ to yield a simple interpolating spline, known as elasticae, which when evaluated at intermediate points yields curves which can in turn be instrumental in 3D reconstruction. The approach is particularly suited for interpolation between MRI slices and for modeling and reconstruction of 3D shapes.

Optimal component analysis (OCA) is a linear subspace technique for dimensionality reduction designed to optimize object classification and recognition performance in specific applications. The inherently linear nature of OCA often limits recognition performance, if the underlying data structure is nonlinear or cluster structures are complex. To address these problems, following a modern trend, we investigate kernel OCA (KOCA), which consists of applying OCA techniques to the data after it has been mapped nonlinearly into a new feature space, referred to in the literature as a reproducing kernel Hilbert space. In this paper, we study theoretical and algorithmic aspects of KOCA and report results obtained in several face recognition experiments using the ORL database.

Using a differential-geometric treatment of planar shapes, we present tools for: 1) hierarchical clustering of imaged objects according to the shapes of their boundaries, 2) learning of probability models for clusters of shapes, and 3) testing of newly observed shapes under competing probability models. Clustering at any level of hierarchy is performed using a mimimum variance type criterion criterion and a Markov process. Statistical means of clusters provide shapes to be clustered at the next higher level, thus building a hierarchy of shapes. Using finite-dimensional approximations of spaces tangent to the shape space at sample means, we (implicitly) impose probability models on the shape space, and results are illustrated via random sampling and classification (hypothesis testing). Together, hierarchical clustering and hypothesis testing provide an efficient framework for shape retrieval. Examples are presented using shapes and images from ETH, Surrey, and AMCOM databases.

For analyzing shapes of planar, closed curves, we propose differential geometric representations of curves using their direction functions and curvature functions. Shapes are represented as elements of infinite-dimensional spaces and their pairwise differences are quantified using the lengths of geodesics connecting them on these spaces. We use a Fourier basis to represent tangents to the shape spaces and then use a gradient-based shooting method to solve for the tangent that connects any two shapes via a geodesic. Using the Surrey fish database, we demonstrate some applications of this approach: 1) interpolation and extrapolations of shape changes, 2) clustering of objects according to their shapes, 3) statistics on shape spaces, and 4) Bayesian extraction of shapes in low-quality images.

We present a geometric approach to statistical shape analysis of closed curves in images. The basic idea is to specify a space of closed curves satisfying given constraints, and exploit the differential geometry of this space to solve optimization and inference problems. We demonstrate this approach by: (i) defining and computing statistics of observed shapes, (ii) defining and learning a parametric probability model on shape space, and (iii) designing a binary hypothesis test on this space.