改进的三角网格表面近似测地线算法

三角网格表面的测地线计算问题可转化为三角网格表面两点间的最短路径计算问题,为了快速地计算三角网格表面测地线,提出一种基于缩小最短路径搜索区域的三角网格表面近似测地线算法。将三角网格沿坐标系三坐标轴方向进行空间单元划分,使用A*算法求出两点间的最短路径盒子序列,进而得到新的搜索区域,计算三角网格上两点间的最短路径,迭代细分最短路径邻域内的边以构造新的网格求解测地线。实验结果表明,该算法能够快速准确地计算出三角网格表面任意两点间的近似测地线,有效解决大型三角网格上最短路径计算速度慢的问题,计算速度较改进前的算法提高了10倍~59倍。将该算法应用到虚拟肝脏手术系统的区域标定中,可满足虚拟场景中对计算实时性和效果真实性的要求。     

点云模型上近似测地线的计算

为了有效计算点云模型上任意两点间的近似测地线,将点云模型沿着直角坐标系中三坐标轴方向进行空间栅格划分后,建立表示点云模型的带权图,采用Dijkstra算法计算带权图上任意给定两点间的最短路径作为初始测地线;然后通过使能量函数最小化,用共轭梯度方法对初始测地线迭代优化,计算得到点云模型上任意给定两点间的近似测地线。该算法无需对点云模型进行网格化,无需对点云模型进行局部或全局的曲面重建,适合大规模点云模型上测地线的计算。     

基于信息几何的图像去噪

提出一种基于信息几何的图像去噪方法,与传统的欧氏空间中去噪方法不同,基于信息几何的图像去噪方法是在流形上利用两点间的测地线距离的大小来衡量图像中两像素点之间的相似性。流形中的点是通过图像中某区域构建的高斯模型,模型间的测地线距离表示两图像区域平均灰度强度和细节丰富程度的差别。这样将区域的平均灰度强度和细节丰富程度的差别作为像素点间的相似性,能够更加准确地衡量像素点间相似性的差异。实验表明,该算法提高了图像去噪效果,能够很好地保持图像细节。     

基于邻域保持的流形学习算法评价模型

应力函数和残差只适合于评价距离严格保持的流形学习算法,dy-dx表示法又是一个定性模型。虽然距离比例方差可以比较和评价大多数的流形学习算法,但其需要计算测地线距离,具有较高的计算复杂度。为此,提出一种基于邻域保持的流形学习算法定量评价模型,该模型仅仅需要确定两个空间中每个对象的k个近邻,并计算出每个点在低维空间中的近邻保持情况,不用计算测地线距离。理论分析表明,邻域保持模型的计算复杂度远远低于距离比例方差的复杂度。在三个数据集上比较了两个模型的性能,实验结果表明,利用邻域保持模型不但可以评价同一算法在不同邻域参数下的嵌入效果,而且可以在不同的流形学习算法之间进行比较,并且其评价流形学习算法的性能优于距离比例方差。     

三角网格表面任意两点间并行近似测地线算法

为降低求解三角网格表面任意两点间近似测地线长度和路径问题的时间开销,提出一种基于局部细分法的并行近似测地线算法。采用类矩阵乘最短路径并行算法求解点对间初始最短路径,并用源分割法映射子网格数据;所有处理器并行执行,对其所拥有点对之间的初始最短路径周围三角面片上的边进行细分操作;最后基于局部细化后的细分图并行,求得所有点对间的近似测地线长度和路径。实验结果表明,该并行近似测地线算法能够有效降低求解该类问题的计算时间,计算效率大大提高。     

三角网格表面近似测地线的计算

为了有效地计算三角网格表面任意两点间的近似测地线,将三角网格模型表示成带权图,计算带权图上两点间的最短路径,并迭代细分最短路径邻域内的边以构造新的带权图求解.改进了细分顶点的生成策略,提出了邻域扩展的方法,提高了迭代运算速度,有效地解决了迭代细分算法容易陷入局部最优的问题;并把测地线距离应用于径向基函数,实现了一种曲面变形算法.实验表明该算法达到了较好的效果.     

改进的局部线性嵌入算法及其应用

局部线性嵌入算法（LLE）中常用欧氏距离来度量样本间相似度,而对于具有低维流形结构的高维数据,欧氏距离不能衡量流形上两点间相对位置关系。提出基于Geodesic Rank-order距离的局部线性嵌入算法（简称GRDLLE）。应用最短路径算法（Dijkstra算法）找到最短路径长度来近似计算任意两个样本间的测地线距离,计算Rank-order距离用于LLE算法的相似性度量。将GRDLLE算法、其他改进LLE的流形学习算法及2DPCA算法在ORL与Yale数据集上进行对比实验,对数据用GRDLLE算法进行降维后人脸识别率有所提高,结果表明GRDLLE算法具有很好的降维效果。     

点云模型上测地线的计算

给定点云模型上2点,将点云数据沿与xyz三坐标轴垂直方向进行单元剖分后,采用Dijkstra算法求出2点间的最短路径作为初始测地线;然后通过带弧长最短约束的平方距离最小化方法对初始测地线进行迭代优化,计算得到点云模型上给定2点间的一条样条表示的精确测地线．文中算法只需局部拟合抛物曲面,无需对点云模型进行三角化或曲面重建,适合大规模点云数据模型上测地线的计算．     

李群均值学习算法

首先分析李群均值的计算方法,在此基础上,进一步提出李群均值学习算法,其思想是在李群流形上寻找一个由总体样本内均值的李代数元素决定的单参数子群,这个单参数子群是原李群上的一条测地线,定义样本到测地线投影的概念,同时将李群样本向该测地线投影,并尽可能使投影后各类别间的散度与类内散度比值最大化,从而实现非线性李群空间的类别判别。实验表明,基于李群均值的学习算法和KNN、FLDA算法相比,具有较好的分类效果。     

基于测地线距离的广义高斯型Laplacian 特征映射

传统的Laplacian 特征映射是基于欧氏距离的近邻数据点的保持,近邻的高维数据点映射到内在低维空间后仍为近邻点,高维数据点的近邻选取最终将影响全局低维坐标.将测地线距离和广义高斯函数融合到传统的Laplacian 特征映射算法中,首先提出了一种基于测地线距离的广义高斯型Laplacian 特征映射算法(geodesicdistance-based generalized Gaussian LE,简称GGLE),该算法在用不同的广义高斯函数度量高维数据点间的相似度时,获得的全局低维坐标呈现出不同的聚类特性;然后,利用这种特性进一步提出了它的集成判别算法,该集成判别算法的主要优点是:近邻参数K 固定,邻接图和测地线距离矩阵都只构造一次.在木纹数据集上的识别实验结果表明,这是一种有效的基于流形的集成判别算法.     

基于测地距离逼近的降维算法

TRIMAP算法可以较好地解决一个“将处于某一不明确的黎曼流形上的高维张量数据投影到一低维子空间,而不改变原流形中任一对数据点的测地距离,同时保留识别能力”的问题。但发现了TRIMAP算法中对于图上距离定义的不足,并对其做出了新的定义,重新定义了图上距离的TRIMAP算法,不仅汲取了原算法的优点,并考虑到了不同类之间的大小及各类的疏密程度对属于不同类的样本点之间的距离的影响,可以更有效地识别出待识别样本的类别,提高识别率。经初步的实验验证,在ORL人脸图像的分类问题中获得了比原TRIMAP算法更好的识别性能。     

非线性控制系统与状态空间的几何结构

首行从整体化的观点定义了一种建立在黎曼流形上的非线性控制系统,给出了系统的状态方程在黎曼流形的局部坐标系下的表达式,讨论了黎曼流形的几何结构对非线性系统的影响,研究了非线性系统的能控性和能观测性,其次,利用对合分布与全测地子流形的性质,给出了建立在黎曼流形上的非线性系统的局部能控结构分解,局部能观结构分解和Kalman分解,第三,分别利用彼此正交的对合分布族和递增对合分布族与全测地子流形族的性质。研究了建立在黎曼流形上的非线性控制系统平等解耦问题和级联解耦问题,以及仿射非线性控制系统的局部干扰解耦问题。     

H2 optimal model order reduction by two-sided technique on Grassmann manifold via the cross-gramian of bilinear systems

In this paper, we discuss the optimal H₂ model order reduction (MOR) problem for bilinear systems. The H₂ optimal MOR problem of bilinear systems is considered as the minimisation problem on Grassmann manifold, which is stored as a quotient space of the noncompact Stifiel manifold. Grassmann manifold whose tangent space is endowed with a Riemannian metric is a Riemannian manifold. In its tangent space equipped with the Riemannian metric, we derive the negative gradients of the cost function, i.e. the steepest descent direction of the cost function. After that, the formulas of geodesic on Grassmann manifold are given. Then we perform linear searches along geodesics to obtain the optimal solutions. Thereby, a two-sided MOR iterative algorithm is proposed to construct an order-reduced bilinear system, which is used to simulate the output and input responses of the original bilinear system. Numerical examples demonstrate the effectiveness of our algorithm.     

Tools in the Riemannian geometry of quantum computation

An introduction is first given of recent developments in the Riemannian geometry of quantum computation in which the quantum evolution is represented in the tangent space manifold of the special unitary unimodular group for n qubits. The Riemannian right-invariant metric, connection, curvature, geodesic equation for minimal complexity quantum circuits, Jacobi equation, and the lifted Jacobi equation for varying penalty parameter are reviewed. Sharpened tools for calculating the geodesic derivative are presented. The geodesic derivative may facilitate the numerical investigation of conjugate points and the global characteristics of geodesic paths in the group manifold, the determination of optimal quantum circuits for carrying out a quantum computation, and the determination of the complexity of particular quantum algorithms.     

Riemannian manifold learning

Recently, manifold learning has been widely exploited in pattern recognition, data analysis, and machine learning. This paper presents a novel framework, called Riemannian manifold learning (RML), based on the assumption that the input high-dimensional data lie on an intrinsically low-dimensional Riemannian manifold. The main idea is to formulate the dimensionality reduction problem as a classical problem in Riemannian geometry, i.e., how to construct coordinate charts for a given Riemannian manifold? We implement the Riemannian normal coordinate chart, which has been the most widely used in Riemannian geometry, for a set of unorganized data points. First, two input parameters (the neighborhood size k and the intrinsic dimension d) are estimated based on an efficient simplicial reconstruction of the underlying manifold. Then, the normal coordinates are computed to map the input high-dimensional data into a low-dimensional space. Experiments on synthetic data as well as real world images demonstrate that our algorithm can learn intrinsic geometric structures of the data, preserve radial geodesic distances, and yield regular embeddings.     

Games of simple pursuit and approach on the manifolds

Two differential games in feedback strategies [1], [2] are considered, in which players are velocity-controlled points of a Riemannian manifold. The game of pursuit is formulated for the case when the pursuer has advantage in speed. Otherwise the game of approach is considered, i.e. the cost-function is the minimal distance between players during the infinite time-interval of motion. Since the restrictions for the velocities are homogenous, geodesic lines have an important role for optimal paths' construction. The main difference between manifold and Euclidean space is non-uniqueness of the minimal geodesic, connecting two points of the manifold. The analysis of this paper is restricted to the manifolds, which have no more than two minimal geodesics. This gives rise to the singularities of dispersal, equivocal and universal types. Local necessary optimality conditions are found. The players' optimal behaviour in general position is shown to be a (regular) motion along geodesics. The domain, where the latter lie on the geodesic curve, connecting the players, is called the primary domain. A sufficient condition is found for the whole game space to be the primary domain, as is the case in Euclidean space. Necessary conditions are formulated for the existence of singular paths, which are envelopes of the geodesics. The equations of singular motion are obtained and shown to be a generalized Hamiltonian type. An algorithm is suggested for the construction of the optimal paths in the vicinity of a singular surface, its efficiency is demonstrated by complete solutions of both games on a two-dimensional cone. For other approaches to similar game problems see [1]–[5].     

Geodesic Regression and the Theory of Least Squares on Riemannian Manifolds

This paper develops the theory of geodesic regression and least-squares estimation on Riemannian manifolds. Geodesic regression is a method for finding the relationship between a real-valued independent variable and a manifold-valued dependent random variable, where this relationship is modeled as a geodesic curve on the manifold. Least-squares estimation is formulated intrinsically as a minimization of the sum-of-squared geodesic distances of the data to the estimated model. Geodesic regression is a direct generalization of linear regression to the manifold setting, and it provides a simple parameterization of the estimated relationship as an initial point and velocity, analogous to the intercept and slope. A nonparametric permutation test for determining the significance of the trend is also given. For the case of symmetric spaces, two main theoretical results are established. First, conditions for existence and uniqueness of the least-squares problem are provided. Second, a maximum likelihood criteria is developed for a suitable definition of Gaussian errors on the manifold. While the method can be generally applied to data on any manifold, specific examples are given for a set of synthetically generated rotation data and an application to analyzing shape changes in the corpus callosum due to age.     

Fuzzy Geodesics and Consistent Sparse Correspondences For: eformable Shapes

A geodesic is a parameterized curve on a Riemannian manifold governed by a second order partial differential equation. Geodesics are notoriously unstable: small perturbations of the underlying manifold may lead to dramatic changes of the course of a geodesic. Such instability makes it difficult to use geodesics in many applications, in particular in the world of discrete geometry. In this paper, we consider a geodesic as the indicator function of the set of the points on the geodesic. From this perspective, we present a new concept called fuzzy geodesics and show that fuzzy geodesics are stable with respect to the Gromov‐Hausdorff distance. Based on fuzzy geodesics, we propose a new object called the intersection configuration for a set of points on a shape and demonstrate its effectiveness in the application of finding consistent correspondences between sparse sets of points on shapes differing by extreme deformations.     

A Riemannian approach to graph embedding

In this paper, we make use of the relationship between the Laplace-Beltrami operator and the graph Laplacian, for the purposes of embedding a graph onto a Riemannian manifold. To embark on this study, we review some of the basics of Riemannian geometry and explain the relationship between the Laplace-Beltrami operator and the graph Laplacian. Using the properties of Jacobi fields, we show how to compute an edge-weight matrix in which the elements reflect the sectional curvatures associated with the geodesic paths on the manifold between nodes. For the particular case of a constant sectional curvature surface, we use the Kruskal coordinates to compute edge weights that are proportional to the geodesic distance between points. We use the resulting edge-weight matrix to embed the nodes of the graph onto a Riemannian manifold. To do this, we develop a method that can be used to perform double centring on the Laplacian matrix computed from the edge-weights. The embedding coordinates are given by the eigenvectors of the centred Laplacian. With the set of embedding coordinates at hand, a number of graph manipulation tasks can be performed. In this paper, we are primarily interested in graph-matching. We recast the graph-matching problem as that of aligning pairs of manifolds subject to a geometric transformation. We show that this transformation is Pro-crustean in nature. We illustrate the utility of the method on image matching using the COIL database.     

Constant cusp height tool paths as geodesic parallels on an abstract Riemannian manifold

In free-form surface milling, cusps on a part surface need to be regulated. They should be small enough for precision purposes. On the other hand, we should maintain high enough cusps so as not to waste effort making unnecessary cuts. A widely accepted practice is to maintain a constant cusp height over the surface. This paper introduces a new approach to generating constant cusp height tool paths. First, we define a Riemannian manifold by assigning a new metric to a part surface without embedding. This new metric is constructed from the curvature tensors of a part and a tool surface, which we refer to as a cusp-metric. Then, we construct geodesic parallels on the new Riemannian manifold. We prove that a selection from such a family of geodesic parallels constitutes a “rational” approximation of accurate constant cusp height tool paths.