A common assumption in semi-supervised learning is that the class label function has a slow variation on the data graph, while in many problems, the label function may vary abruptly in certain graph regions, resulting in high-frequency components. Although semi-supervised learning is an ill-posed problem, it is often possible to find a source graph on which the label function has similar frequency content to the target graph where the actual classification problem is defined. In this paper, we propose a method for domain adaptation on graphs based on learning the spectrum of the label function in a source graph with many labels, and transferring the spectrum information to the target graph. When transferring the frequency content, it is not easy to share graph Fourier coefficients directly between the two independently constructed graphs, since no match exists between their Fourier bases. We solve this by learning a transformation between the Fourier bases of the two graphs that flexibly “aligns” them. The unknown class label function on the target graph is then reconstructed from the learnt spectrum while retaining consistency with the available labels. Comparative experiments suggest that the proposed algorithm often outperforms recent domain adaptation methods in various data classification applications.

While many approaches exist in the literature to learn low-dimensional representations for data collections in multiple modalities, the generalizability of multi-modal nonlinear embeddings to previously unseen data is a rather overlooked subject. In this work, we first present a theoretical analysis of learning multi-modal nonlinear embeddings in a supervised setting. Our performance bounds indicate that for successful generalization in multi-modal classification and retrieval problems, the regularity of the interpolation functions extending the embedding to the whole data space is as important as the between-class separation and cross-modal alignment criteria. We then propose a multi-modal nonlinear representation learning algorithm that is motivated by these theoretical findings, where the embeddings of the training samples are optimized jointly with the Lipschitz regularity of the interpolators. Experimental comparison to recent multi-modal and single-modal learning algorithms suggests that the proposed method yields promising performance in multi-modal image classification and cross-modal image-text retrieval applications.

In practical machine learning settings, there often exist relations or links between data from different modalities. The goal of multi-modal learning algorithms is to efficiently use the information available in different modalities to solve multi-modal classification or retrieval problems. In this study, we propose a multi-modal supervised representation learning algorithm based on nonlinear dimensionality reduction. Nonlinear embeddings often yield more flexible representations compared to linear counterparts especially in case of high dissimilarity between the data geometries in different modalities. Based on recent performance bounds on nonlinear dimensionality reduction, we propose an optimization objective aiming to improve the intra- and inter-modal within-class compactness and between-class separation, as well as the Lipschitz regularity of the interpolator that generalizes the embedding to the whole data space. Experiments in multi-view face recognition and image-text retrieval applications show that the proposed method yields promising performance in comparison with state-of-the-art multi-modal learning methods.

Separation of ground and nonground measurements is an essential task in the analysis of light detection and ranging (LiDAR) point clouds; however, it is challenge to implement a LiDAR filtering algorithm that integrates the mathematical definition of various landforms. In this letter, we propose a novel LiDAR filtering algorithm that adapts to the irregular structure and 3-D geometry of LiDAR point clouds. We exploit weighted graph representations to analyze the 3-D point cloud on its original domain. Then, we consider airborne LiDAR data as an irregular elevation signal residing on graph vertices. Based on a spectral graph approach, we introduce a new filtering algorithm that distinguishes ground and nonground points in terms of their spectral characteristics. Our complete filtering framework consists of outlier removal, iterative graph signal filtering, and erosion steps. Experimental results indicate that the proposed framework achieves a good accuracy on the scenes with data gaps and classifies the nonground points on bridges and complex shapes satisfactorily, while those are usually not handled well by the state-of-the-art filtering methods.

Local learning of sparse image models has proved to be very effective to solve inverse problems in many computer vision applications. To learn such models, the data samples are often clustered using the K-means algorithm with the Euclidean distance as a dissimilarity metric. However, the Euclidean distance may not always be a good dissimilarity measure for comparing data samples lying on a manifold. In this paper, we propose two algorithms for determining a local subset of training samples from which a good local model can be computed for reconstructing a given input test sample, where we consider the underlying geometry of the data. The first algorithm, called adaptive geometry-driven nearest neighbor search (AGNN), is an adaptive scheme, which can be seen as an out-of-sample extension of the replicator graph clustering method for local model learning. The second method, called geometry-driven overlapping clusters (GOCs), is a less complex nonadaptive alternative for training subset selection. The proposed AGNN and GOC methods are evaluated in image superresolution and shown to outperform spectral clustering, soft clustering, and geodesic distance-based subset selection in most settings.

Supervised manifold learning methods for data classification map high-dimensional data samples to a lower dimensional domain in a structure-preserving way while increasing the separation between different classes. Most manifold learning methods compute the embedding only of the initially available data; however, the generalization of the embedding to novel points, i.e., the out-of-sample extension problem, becomes especially important in classification applications. In this paper, we propose a semi-supervised method for building an interpolation function that provides an out-of-sample extension for general supervised manifold learning algorithms studied in the context of classification. The proposed algorithm computes a radial basis function interpolator that minimizes an objective function consisting of the total embedding error of unlabeled test samples, defined as their distance to the embeddings of the manifolds of their own class, as well as a regularization term that controls the smoothness of the interpolation function in a direction-dependent way. The class labels of test data and the interpolation function parameters are estimated jointly with an iterative process. Experimental results on face and object images demonstrate the potential of the proposed out-of-sample extension algorithm for the classification of manifold-modeled data sets.

A common problem in image analysis is the transformation-invariant estimation of the similarity between a query image and a set of reference images representing different classes. This typically requires the comparison of the distance between the query image and the transformation manifolds of the reference images. The tangent distance algorithm is a popular method that estimates the manifold distance by employing a linear approximation of the transformation manifolds. In this paper, we present a performance analysis of the tangent distance method in image classification applications for general transformation models. In particular, we characterize the misclassification error in terms of the geometric properties of the individual manifolds such as their curvature, as well as their relative properties such as the separation between them. We then extend our results to a multi-scale analysis where the images are smoothed with a low-pass filter and study the effect of smoothing on the misclassification error. Our theoretical results are confirmed by experiments and may find use in the selection of algorithm parameters in multiscale transformation-invariant image analysis methods.

Sparse representations of images in well-designed dictionaries can be used for effective classification. Meanwhile, training data available in most realistic settings are likely to be exposed to geometric transformations, which poses a challenge for the design of good dictionaries. In this work, we study the problem of learning class-representative dictionaries from geometrically transformed image sets. In order to efficiently take account of arbitrary geometric transformations in the learning, we adopt a representation of the dictionaries in an analytic basis. Then, the proposed algorithm learns atoms that are attracted to the samples of their own class while being repelled from the samples of other classes so that the discrimination between different classes is promoted. The dictionary learning objective is formulated such that it enhances the class-discrimination capabilities of individual atoms rather than the ones of the subspaces they generate, which renders the designed dictionaries especially suitable for fast classification of query images with very sparse approximations. Experimental results demonstrate the performance of the proposed method in handwritten digit recognition applications.

The computation of the geometric transformation between a reference and a target image, known as registration or alignment, corresponds to the projection of the target image onto the transformation manifold of the reference image (the set of images generated by its geometric transformations). However, it often takes a nontrivial form such that the exact computation of projections on the manifold is difficult. The tangent distance method is an effective algorithm for solving this problem by exploiting a linear approximation of the transformation manifold of the reference image. As theoretical studies about the tangent distance algorithm have been largely overlooked, we present in this work a detailed performance analysis of this useful algorithm, which can eventually help its implementation and the selection of its parameters. We consider a popular image registration setting using a multiscale pyramid of low-pass filtered versions of the (possibly noisy) reference and target images, which is particularly useful for recovering large transformations. We first show that the alignment error has a nonmonotonic variation with the filter size, due to the opposing effects of filtering on both manifold nonlinearity and image noise. We then study the convergence of the multiscale tangent distance method to the optimal solution. Our theoretical findings are confirmed by experiments on image transformation models involving translations, rotations, and scalings. Our study is the first detailed study of the tangent distance algorithm that leads to a better understanding of its efficacy and to the proper selection of its design parameters.

We present a performance analysis for image registration with gradient descent. We consider a typical multiscale registration setting where the global two-dimensional translation between a pair of images is estimated by smoothing the images and minimizing the distance between them with gradient descent. Our study particularly concentrates on the effect of noise and low-pass filtering on the alignment accuracy. We analyze the well-behavedness of the image distance function by estimating the neighborhood of translations for which it is free of undesired local minima. This is the neighborhood of translations that are correctly computable with a simple gradient descent minimization. We show that the area of this neighborhood increases at least quadratically with the smoothing filter size. We then examine the effect of noise on the alignment accuracy and derive an upper bound for the alignment error in terms of the noise properties and filter size. Our main finding is that the error increases at a rate that is at least linear with respect to the filter size. Therefore, smoothing improves the well-behavedness of the distance function; however, this comes at the cost of amplifying the alignment error in noisy settings. Our results provide a mathematical insight into why hierarchical techniques are effective in image registration, suggesting that the multiscale alignment strategy of these techniques is very suitable from the perspective of the tradeoff between the well-behavedness of the objective function and the registration accuracy. To the best of our knowledge, this is the first such study for descent-based image registration.

Manifold models provide low-dimensional representations that are useful for processing and analyzing data in a transformation-invariant way. In this paper, we study the problem of learning smooth pattern transformation manifolds from image sets that represent observations of geometrically transformed signals. To construct a manifold, we build a representative pattern whose transformations accurately fit various input images. We examine two objectives of the manifold-building problem, namely, approximation and classification. For the approximation problem, we propose a greedy method that constructs a representative pattern by selecting analytic atoms from a continuous dictionary manifold. We present a dc optimization scheme that is applicable to a wide range of transformation and dictionary models, and demonstrate its application to the transformation manifolds generated by the rotation, translation, and anisotropic scaling of a reference pattern. Then, we generalize this approach to a setting with multiple transformation manifolds, where each manifold represents a different class of signals. We present an iterative multiple-manifold-building algorithm such that the classification accuracy is promoted in the learning of the representative patterns. The experimental results suggest that the proposed methods yield high accuracy in the approximation and classification of data compared with some reference methods, while the invariance to geometric transformations is achieved because of the transformation manifold model.

Manifold models provide low-dimensional representations that are useful for analyzing and classifying data in a transformation-invariant way. In this paper we study the problem of jointly building multiple pattern transformation manifolds from a collection of image sets, where each set consists of observations from a class of geometrically transformed signals. We build the manifolds such that each manifold approximates a different signal class. Each manifold is characterized by a representative pattern that consists of a linear combination of analytic atoms selected from a continuous dictionary manifold. We propose an iterative algorithm for jointly building multiple manifolds such that the classification accuracy is promoted in the learning of the representative patterns. We present a DC (Difference-of-Convex) optimization scheme that is applicable to a wide range of transformation and dictionary models, and demonstrate its application to transformation manifolds generated by the rotation, translation and scaling of a reference image. Experimental results suggest that the proposed method yields a high classification accuracy compared to reference methods based on individual manifold building or locally linear manifold approximations.

The construction of low-dimensional models explaining high-dimensional signal observations provides concise and efficient data representations. In this paper, we focus on pattern transformation manifold models generated by in-plane geometric transformations of 2D visual patterns. We propose a method for computing a manifold by building a representative pattern such that its transformation manifold accurately fits a set of given observations. We present a solution for the progressive construction of the representative pattern with the aid of a parametric dictionary, which in turn provides an analytical representation of the data and the manifold. Experimental results show that the patterns learned with the proposed algorithm can efficiently capture the main characteristics of the input data with high approximation accuracy, where the invariance to the geometric transformations of the data is accomplished due to the transformation manifold model.

Efficient solutions for the classification of multi-view images can be built on graph-based algorithms when little information is known about the scene or cameras. Such methods typically require a pair-wise similarity measure between images, where a common choice is the Euclidean distance. However, the accuracy of the Euclidean distance as a similarity measure is restricted to cases where images are captured from nearby viewpoints. In settings with large transformations and viewpoint changes, alignment of images is necessary prior to distance computation. We propose a method for the registration of uncalibrated images that capture the same 3D scene or object. We model the depth map of the scene as an algebraic surface, which yields a warp model in the form of a rational function between image pairs. The warp model is computed by minimizing the registration error, where the registered image is a weighted combination of two images generated with two different warp functions estimated from feature matches and image intensity functions in order to provide robust registration. We demonstrate the flexibility of our alignment method by experimentation on several wide-baseline image pairs with arbitrary scene geometries and texture levels. Moreover, the results on multi-view image classification suggest that the proposed alignment method can be effectively used in graph-based classification algorithms for the computation of pairwise distances where it achieves significant improvements over distance computation without prior alignment.

Transformation-invariant analysis of signals often requires the computation of the distance from a test pattern to a transformation manifold. In particular, the estimation of the distances between a transformed query signal and several transformation manifolds representing different classes provides essential information for the classification of the signal. In many applications, the computation of the exact distance to the manifold is costly, whereas an efficient practical solution is the approximation of the manifold distance with the aid of a manifold grid. In this paper, we consider a setting with transformation manifolds of known parameterization. We first present an algorithm for the selection of samples from a single manifold that permits to minimize the average error in the manifold distance estimation. Then we propose a method for the joint discretization of multiple manifolds that represent different signal classes, where we optimize the transformation-invariant classification accuracy yielded by the discrete manifold representation. Experimental results show that sampling each manifold individually by minimizing the manifold distance estimation error outperforms baseline sampling solutions with respect to registration and classification accuracy. Performing an additional joint optimization on all samples improves the classification performance further. Moreover, given a fixed total number of samples to be selected from all manifolds, an asymmetric distribution of samples to different manifolds depending on their geometric structures may also increase the classification accuracy in comparison with the equal distribution of samples.

The characterization of signals and images in manifolds often lead to efficient dimensionality reduction algorithms based on manifold distance computation for analysis or classification tasks. We propose in this paper a method for the discretization of signal manifolds given in a parametric form. We present an iterative algorithm for the selection of samples on the manifold that permits to minimize the average error in the manifold distance computation. Experimental results with image appearance manifolds demonstrate that the proposed discretization algorithm outperforms baseline solutions based on random or regular sampling, both in terms of projection accuracy and image registration.

Transformation manifolds are quite attractive for image analysis applications that require transformation invariance properties. The geometric structure of a transformation manifold has a profound influence on the design of processing algorithm, and the curvature is a major parameter in the characterization of the manifold geometry. We propose here a procedure for the computation of an upper bound for the maximum principal curvature of a pattern transformation manifold. We provide an analytical formulation of the curvature bound and show that the numerical computation of this bound is mostly dependent on the rotation parameters. Experimental results indicate that the curvature bound of the manifold has considerable dependence on the spatial complexity and smoothness of the generating pattern. Moreover, experiments with discretization of manifolds suggest that the curvature of the manifold is likely to affect the accuracy of compact representation and sampling algorithms.