Discrete surface Ricci flow

This work introduces a unified framework for discrete surface Ricci flow algorithms, including spherical, Euclidean, and hyperbolic Ricci flows, which can design Riemannian metrics on surfaces with arbitrary topologies by user-defined Gaussian curvatures. Furthermore, the target metrics are conformal (angle-preserving) to the original metrics. A Ricci flow conformally deforms the Riemannian metric on a surface according to its induced curvature, such that the curvature evolves like a heat diffusion process. Eventually, the curvature becomes the user defined curvature. Discrete Ricci flow algorithms are based on a variational framework. Given a mesh, all possible metrics form a linear space, and all possible curvatures form a convex polytope. The Ricci energy is defined on the metric space, which reaches its minimum at the desired metric. The Ricci flow is the negative gradient flow of the Ricci energy. Furthermore, the Ricci energy can be optimized using Newton's method more efficiently. Discrete Ricci flow algorithms are rigorous and efficient. Our experimental results demonstrate the efficiency, accuracy and flexibility of the algorithms. They have the potential for a wide range of applications in graphics, geometric modeling, and medical imaging. We demonstrate their practical values by global surface parameterizations.     

Model-based classification with dissimilarities: a maximum likelihood approach

Most of classification problems concern applications with objects lying in an Euclidean space, but, in some situations, only dissimilarities between objects are known. We are concerned with supervised classification analysis from an observed dissimilarity table, which task is classifying new unobserved or implicit objects (only known through their dissimilarity measures with previously classified ones forming the training data set) into predefined classes. This work concentrates on developing model-based classifiers for dissimilarities which take into account the measurement error w.r.t. Euclidean distance. Basically, it is assumed that the unobserved objects are unknown parameters to estimate in an Euclidean space, and the observed dissimilarity table is a random perturbation of their Euclidean distances of gaussian type. Allowing the distribution of these perturbations to vary across pairs of classes in the population leads to more flexible classification methods than usual algorithms. Model parameters are estimated from the training data set via the maximum likelihood (ML) method, and allocation is done by assigning a new implicit object to the group in the population and positioning in the Euclidean space maximizing the conditional group likelihood with the estimated parameters. This point of view can be expected to be useful in classifying dissimilarity tables that are no longer Euclidean due to measurement error or instabilities of various types. Two possible structures are postulated for the error, resulting in two different model-based classifiers. First results on real or simulated data sets show interesting behavior of the two proposed algorithms, ant the respective effects of the dissimilarity type and of the data intrinsic dimension are investigated. For these latter two aspects, one of the constructed classifiers appears to be very promising. Interestingly, the data intrinsic dimension seems to have a much less adverse effect on our classifiers than initially feared, at least for small to moderate dimensions.     

Generalized Discrete Ricci Flow

Surface Ricci flow is a powerful tool to design Riemannian metrics by user defined curvatures. Discrete surface Ricci flow has been broadly applied for surface parameterization, shape analysis, and computational topology. Conventional discrete Ricci flow has limitations. For meshes with low quality triangulations, if high conformality is required, the flow may get stuck at the local optimum of the Ricci energy. If convergence to the global optimum is enforced, the conformality may be sacrificed. This work introduces a novel method to generalize the traditional discrete Ricci flow. The generalized Ricci flow is more flexible, more robust and conformal for meshes with low quality triangulations. Conventional method is based on circle packing, which requires two circles on an edge intersect each other at an acute angle. Generalized method allows the two circles either intersect or separate from each other. This greatly improves the flexibility and robustness of the method. Furthermore, the generalized Ricci flow preserves the convexity of the Ricci energy, this ensures the uniqueness of the global optimum. Therefore the algorithm won't get stuck at the local optimum. Generalized discrete Ricci flow algorithms are explained in details for triangle meshes with both Euclidean and hyperbolic background geometries. Its advantages are demonstrated by theoretic proofs and practical applications in graphics, especially surface parameterization.     

Robust fuzzy clustering of relational data

Popular relational-data clustering algorithms, relational dual of fuzzy c-means (RFCM), non-Euclidean RFCM (NERFCM) (both by Hathaway et al), and FANNY (by Kaufman and Rousseeuw) are examined. A new algorithm, which is a generalization of FANNY, called the fuzzy relational data clustering (FRC) algorithm, is introduced, having an identical objective functional as RFCM. However, the FRC does not have the restriction of RFCM, which is that the relational data is derived from Euclidean distance as the measure of dissimilarity between the objects, and it also does not have limitations of FANNY, including the use of a fixed membership exponent, or a fuzzifier exponent, m. The FRC algorithm is further improved by incorporating the concept of Dave's object data noise clustering (NC) algorithm, done by proposing a concept of noise-dissimilarity. Next, based on the constrained minimization, which includes an inequality constraint for the memberships and corresponding Kuhn-Tucker conditions, a noise resistant, FRC algorithm is derived which works well for all types of non-Euclidean dissimilarity data. Thus it is shown that the extra computations for data expansion (/spl beta/-spread transformation) required by the NERFCM algorithm are not necessary. This new algorithm is called robust non-Euclidean fuzzy relational data clustering (robust-NE-FRC), and its robustness is demonstrated through several numerical examples. Advantages of this new algorithm are: faster convergence, robustness against outliers, and ability to handle all kinds of relational data, including non-Euclidean. The paper also presents a new and better interpretation of the noise-class.     

A New Framework for Multiscale Saliency Detection Based on Image Patches

In this paper, we propose a new multiscale saliency detection algorithm based on image patches. To measure saliency of pixels in a given image, we segment the image into patches by a fixed scale and then use principal component analysis to reduce the dimensions which are noises with respect to the saliency calculation. The dissimilarities between a patch and other patches, which indicate the patch’s saliency, are computed based on the dissimilarity of colors and the spatial distance. Finally, we implement our algorithm through multiple scales that further decrease the saliency of background. Our method is compared with other saliency detection approaches on two public image datasets. Experimental results show that our method outperforms the state-of-the-art methods on predicting human fixations and salient object segmentation.     

Manifold splines with a single extraordinary point

This paper develops a novel computational technique to define and construct manifold splines with only one singular point by employing the rigorous mathematical theory of Ricci flow. The central idea and new computational paradigm of manifold splines are to systematically extend the algorithmic pipeline of spline surface construction from any planar domain to an arbitrary topology. As a result, manifold splines can unify planar spline representations as their special cases. Despite its earlier success, the existing manifold spline framework is plagued by the topology-dependent, large number of singular points (i.e., |2g−2| for any genus-g surface), where the analysis of surface behaviors such as continuity remains extremely difficult. The unique theoretical contribution of this paper is that we devise new mathematical tools so that manifold splines can now be constructed with only one singular point, reaching their theoretic lower bound of singularity for real-world applications. Our new algorithm is founded upon the concept of discrete Ricci flow and associated techniques. First, Ricci flow is employed to compute a special metric of any manifold domain (serving as a parametric domain for manifold splines), such that the metric becomes flat everywhere except at one point. Then, the metric naturally induces an affine atlas covering the entire manifold except this singular point. Finally, manifold splines are defined over this affine atlas. The Ricci flow method is theoretically sound, and practically simple and efficient. We conduct various shape experiments and our new theoretical and algorithmic results alleviate the modeling difficulty of manifold splines, and hence, promote the widespread use of manifold splines in surface and solid modeling, geometric design, and reverse engineering.     

Ricci flow-based spherical parameterization and surface registration

This paper presents an improved Euclidean Ricci flow method for spherical parameterization. We subsequently invent a scale space processing built upon Ricci energy to extract robust surface features for accurate surface registration. Since our method is based on the proposed Euclidean Ricci flow, it inherits the properties of Ricci flow such as conformality, robustness and intrinsicalness, facilitating efficient and effective surface mapping. Compared with other surface registration methods using curvature or sulci pattern, our method demonstrates a significant improvement for surface registration. In addition, Ricci energy can capture local differences for surface analysis as shown in the experiments and applications.     

Computing general geometric structures on surfaces using Ricci flow

Systematically generalizing planar geometric algorithms to manifold domains is of fundamental importance in computer aided design field. This paper proposes a novel theoretic framework, geometric structure, to conquer this problem. In order to discover the intrinsic geometric structures of general surfaces, we developed a theoretic rigorous and practical efficient method, Discrete Variational Ricci flow.Different geometries study the invariants under the corresponding transformation groups. The same geometry can be defined on various manifolds, whereas the same manifold allows different geometries. Geometric structures allow different geometries to be defined on various manifolds, therefore algorithms based on the corresponding geometric invariants can be applied on the manifold domains directly.Surfaces have natural geometric structures, such as spherical structure, affine structure, projective structure, hyperbolic structure and conformal structure. Therefore planar algorithms based on these geometries can be defined on surfaces straightforwardly.Computing the general geometric structures on surfaces has been a long lasting open problem. We solve the problem by introducing a novel method based on discrete variational Ricci flow.We thoroughly explain both theoretical and practical aspects of the computational methodology for geometric structures based on Ricci flow, and demonstrate several important applications of geometric structures: generalizing Voronoi diagram algorithms to surfaces via Euclidean structure, cross global parametrization between high genus surfaces via hyperbolic structure, generalizing planar splines to manifolds via affine structure. The experimental results show that our method is rigorous and efficient and the framework of geometric structures is general and powerful.     

Generalised Nonlocal Image Smoothing

We propose a discrete variational approach for image smoothing consisting of nonlocal data and smoothness constraints that penalise general dissimilarity measures defined on image patches. One of such dissimilarity measures is the weighted L ₂ distance between patches. In such a case we derive an iterative neighbourhood filter that induces a new similarity measure in the photometric domain. It can be regarded as an extended patch similarity measure that evaluates not only the patch similarity of two chosen pixels, but also the similarity of their corresponding neighbours. This leads to a more robust smoothing process since the pixels selected for averaging are more coherent with the local image structure. By slightly modifying the way the similarities are computed we obtain two related filters: The NL-means filter of Buades et al. (SIAM Multiscale Model. Simul. 4(2):490–530, 2005b) and the NDS filter of Mrázek et al. (Geometric Properties for Incomplete Data, Computational Imaging and Vision, vol. 31, pp. 335–352, Springer, Dordrecht, 2006). In fact, the proposed approach can be considered as a generalisation of the latter filter to the space of patches. We also provide novel insights into relations of the NDS filter with diffusion/regularisation methods as well as with some recently proposed graph regularisation techniques. We evaluate our method for the task of denoising greyscale and colour images degraded with Gaussian and salt-and-pepper noise, demonstrating that it compares very well to other more sophisticated approaches.     

Linear discriminant projection embedding based on patches alignment

Dimensionality reduction is often required as a preliminary stage in many data analysis applications. In this paper, we propose a novel supervised dimensionality reduction method, called linear discriminant projection embedding (LDPE), for pattern recognition. LDPE first chooses a set of overlapping patches which cover all data points using a minimum set cover algorithm with geodesic distance constraint. Then, principal component analysis (PCA) is applied on each patch to obtain the data's local representations. Finally, patches alignment technique combined with modified maximum margin criterion (MMC) is used to yield the discriminant global embedding. LDPE takes both label information and structure of manifold into account, thus it can maximize the dissimilarities between different classes and preserve data's intrinsic structures simultaneously. The efficiency of the proposed algorithm is demonstrated by extensive experiments using three standard face databases (ORL, YALE and CMU PIE). Experimental results show that LDPE outperforms other classical and state of art algorithms.     

Surface parameterization in volumetric images for curvature-based feature classification

Curvature-based surface features are well suited for use in multimodal medical image registration. The accuracy of such feature-based registration techniques is dependent upon the reliability of the feature computation. The computation of curvature features requires second derivative information that is best obtained from a parametric surface representation. We present a method of explicitly parameterizing surfaces from volumetric data. Surfaces are extracted, without a global thresholding, using active contour models. A monge/spl acute/ basis for each surface patch is estimated and used to transform the patch into local, or parametric, coordinates. Surface patches are fit to a bicubic polynomial in local coordinates using least squares solved by singular value decomposition. We tested our method by reconstructing surfaces from the surface model and analytically computing Gaussian and mean curvatures. The model was tested on analytical and medical data.     

A Differential Geometric Approach to Multiple View Geometry in Spaces of Constant Curvature

Based upon an axiomatic formulation of vision system in a general Riemannian manifold, this paper provides a unified framework for the study of multiple view geometry in three dimensional spaces of constant curvature, including Euclidean space, spherical space, and hyperbolic space. It is shown that multiple view geometry for Euclidean space can be interpreted as a limit case when (sectional) curvature of a non-Euclidean space approaches to zero. In particular, we show that epipolar constraint in the general case is exactly the same as that known for the Euclidean space but should be interpreted more generally when being applied to triangulation in non-Euclidean spaces. A special triangulation method is hence introduced using trigonometry laws from Absolute Geometry. Based on a common rank condition, we give a complete study of constraints among multiple images as well as relationships among all these constraints. This idealized geometric framework may potentially extend extant multiple view geometry to the study of astronomical imaging where the effect of space curvature is no longer negligible, e.g., the so-called gravitational lensing phenomenon, which is currently active study in astronomical physics and cosmology.     

New Riemannian techniques for directional and tensorial image data

This paper develops new geometrical filtering and edge detection algorithms for processing non-Euclidean image data. We view image data as residing on a Riemannian manifold, and we work with a representation based on the exponential map for this manifold together with the Riemannian weighted mean of image data. We show how the weighted mean can be efficiently computed using Newton's method, which converges faster than the gradient descent method described elsewhere in the literature. Based on geodesic distances and the exponential map, we extend the classical median filter and the Perona-Malik anisotropic diffusion technique to smooth non-Euclidean image data. We then propose an anisotropic Gaussian kernel for image filtering, and we also show how both the median filter and the anisotropic Gaussian filter can be combined to develop a new edge preserving filter, which is effective at removing both Gaussian noise and impulse noise. By using the intrinsic metric of the feature manifold, we also generalise Di Zenzo's structure tensor to non-Euclidean images for edge detection. We demonstrate the applications of our Riemannian filtering and edge detection algorithms both on directional and tensor-valued images.     

An empirical study on improving dissimilarity-based classifications using one-shot similarity measure

This paper reports an experimental result obtained by additionally using unlabeled data together with labeled ones to improve the classification accuracy of dissimilarity-based methods, namely, dissimilarity-based classifications (DBC) [25]. In DBC, classifiers among classes are not based on the feature measurements of individual objects, but on a suitable dissimilarity measure among the objects instead. In order to measure the dissimilarity distance between pairwise objects, an approach using the one-shot similarity (OSS) [30] measuring technique instead of the Euclidean distance is investigated in this paper. In DBC using OSS, the unlabeled set can be used to extend the set of prototypes as well as to compute the OSS distance. The experimental results, obtained with artificial and real-life benchmark datasets, demonstrate that designing the classifiers in the OSS dissimilarity matrices instead of expanding the set of prototypes can further improve the classification accuracy in comparison with the traditional Euclidean approach. Moreover, the results demonstrate that the proposed setting does not work with non-Euclidean data.     

Fuzzy multidimensional scaling

Multidimensional scaling (MDS) is a data analysis technique for representing measurements of (dis)similarity among pairs of objects as distances between points in a low-dimensional space. MDS methods differ mainly according to the distance model used to scale the proximities. The most usual model is the Euclidean one, although a spherical model is often preferred to represent correlation measurements. These two distance models are extended to the case where dissimilarities are expressed as intervals or fuzzy numbers. Each object is then no longer represented by a point but by a crisp or a fuzzy region in the chosen space. To determine these regions, two algorithms are proposed and illustrated using typical data sets. Experiments demonstrate the ability of the methods to represent both the structure and the vagueness of dissimilarity measurements.     

The unified discrete surface Ricci flow

Ricci flow deforms the Riemannian metric proportionally to the curvature, such that the curvature evolves according to a heat diffusion process and eventually becomes constant everywhere. Ricci flow has demonstrated its great potential by solving various problems in many fields, which can be hardly handled by alternative methods so far.This work introduces the unified theoretic framework for discrete surface Ricci flow, including all the common schemes: tangential circle packing, Thurston’s circle packing, inversive distance circle packing and discrete Yamabe flow. Furthermore, this work also introduces a novel schemes, virtual radius circle packing and the mixed type schemes, under the unified framework. This work gives explicit geometric interpretation to the discrete Ricci energies for all the schemes with all back ground geometries, and the corresponding Hessian matrices.The unified frame work deepens our understanding to the discrete surface Ricci flow theory, and has inspired us to discover the new schemes, improved the flexibility and robustness of the algorithms, greatly simplified the implementation and improved the efficiency. Experimental results show the unified surface Ricci flow algorithms can handle general surfaces with different topologies, and is robust to meshes with different qualities, and is effective for solving real problems.     

Non-Euclidean spring embedders

We present a conceptually simple approach to generalizing force-directed methods for graph layout from Euclidean geometry to Riemannian geometries. Unlike previous work on non-Euclidean force-directed methods, ours is not limited to special classes of graphs, but can be applied to arbitrary graphs. The method relies on extending the Euclidean notions of distance, angle, and force-interactions to smooth non-Euclidean geometries via projections to and from appropriately chosen tangent spaces. In particular, we formally describe the calculations needed to extend such algorithms to hyperbolic and spherical geometries. We also study the theoretical and practical considerations that arise when working with non-Euclidean geometries.     

Robust image segmentation using FCM with spatial constraints based on new kernel-induced distance measure

Fuzzy c-means clustering (FCM) with spatial constraints (FCM_S) is an effective algorithm suitable for image segmentation. Its effectiveness contributes not only to the introduction of fuzziness for belongingness of each pixel but also to exploitation of spatial contextual information. Although the contextual information can raise its insensitivity to noise to some extent, FCM_S still lacks enough robustness to noise and outliers and is not suitable for revealing non-Euclidean structure of the input data due to the use of Euclidean distance (L2 norm). In this paper, to overcome the above problems, we first propose two variants, FCM_S1 and FCM_S2, of FCM_S to aim at simplifying its computation and then extend them, including FCM_S, to corresponding robust kernelized versions KFCM_S, KFCM_S1 and KFCM_S2 by the kernel methods. Our main motives of using the kernel methods consist in: inducing a class of robust non-Euclidean distance measures for the original data space to derive new objective functions and thus clustering the non-Euclidean structures in data; enhancing robustness of the original clustering algorithms to noise and outliers, and still retaining computational simplicity. The experiments on the artificial and real-world datasets show that our proposed algorithms, especially with spatial constraints, are more effective.     

Unsupervised manifold learning based on multiple feature spaces

Manifold learning is a well-known dimensionality reduction scheme which can detect intrinsic low-dimensional structures in non-linear high-dimensional data. It has been recently widely employed in data analysis, pattern recognition, and machine learning applications. Isomap is one of the most promising manifold learning algorithms, which extends metric multi-dimensional scaling by using approximate geodesic distance. However, when Isomap is conducted on real-world applications, it may have some difficulties in dealing with noisy data. Although many applications represent a special sample by multiple feature vectors in different spaces, Isomap employs samples in unique observation space. In this paper, two extended versions of Isomap to multiple feature spaces problem, namely fusion of dissimilarities and fusion of geodesic distances, are presented. We have employed the advantages of several spaces and depicted the Euclidean distance on learned manifold that is more compatible to the semantic distance. To show the effectiveness and validity of the proposed method, some experiments have been carried out on the application of shape analysis on MPEG7 CE Part B and Fish data sets.     

Locally affine patch mapping and global refinement for image super-resolution

This paper deals with the super-resolution (SR) problem based on a single low-resolution (LR) image. Inspired by the local tangent space alignment algorithm in [16] for nonlinear dimensionality reduction of manifolds, we propose a novel patch-learning method using locally affine patch mapping (LAPM) to solve the SR problem. This approach maps the patch manifold of low-resolution image to the patch manifold of the corresponding high-resolution (HR) image. This patch mapping is learned by a training set of pairs of LR/HR images, utilizing the affine equivalence between the local low-dimensional coordinates of the two manifolds. The latent HR image of the input (an LR image) is estimated by the HR patches which are generated by the proposed patch mapping on the LR patches of the input. We also give a simple analysis of the reconstruction errors of the algorithm LAPM. Furthermore we propose a global refinement technique to improve the estimated HR image. Numerical results are given to show the efficiency of our proposed methods by comparing these methods with other existing algorithms.