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.     

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.     

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.     

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.     

Polycube splines

This paper proposes a new concept of polycube splines and develops novel modeling techniques for using the polycube splines in solid modeling and shape computing. Polycube splines are essentially a novel variant of manifold splines which are built upon the polycube map, serving as its parametric domain. Our rationale for defining spline surfaces over polycubes is that polycubes have rectangular structures everywhere over their domains, except a very small number of corner points. The boundary of polycubes can be naturally decomposed into a set of regular structures, which facilitate tensor-product surface definition, GPU-centric geometric computing, and image-based geometric processing. We develop algorithms to construct polycube maps, and show that the introduced polycube map naturally induces the affine structure with a finite number of extraordinary points. Besides its intrinsic rectangular structure, the polycube map may approximate any original scanned data-set with a very low geometric distortion, so our method for building polycube splines is both natural and necessary, as its parametric domain can mimic the geometry of modeled objects in a topologically correct and geometrically meaningful manner. We design a new data structure that facilitates the intuitive and rapid construction of polycube splines in this paper. We demonstrate the polycube splines with applications in surface reconstruction and shape computing.     

Discrete Distortion in Triangulated 3‐Manifolds

We introduce a novel notion, that we call discrete distortion, for a triangulated 3‐manifold. Discrete distortion naturally generalizes the notion of concentrated curvature defined for triangulated surfaces and provides a powerful tool to understand the local geometry and topology of 3‐manifolds. Discrete distortion can be viewed as a discrete approach to Ricci curvature for singular flat manifolds. We distinguish between two kinds of distortion, namely, vertex distortion, which is associated with the vertices of the tetrahedral mesh decomposing the 3‐manifold, and bond distortion, which is associated with the edges of the tetrahedral mesh. We investigate properties of vertex and bond distortions. As an example, we visualize vertex distortion on manifold hypersurfaces in R⁴ defined by a scalar field on a 3D mesh. distance fields.     

一种基于全局和局部特征匹配的流形对齐算法

不同流形样本点之间的关联性挖掘是决定流形对齐算法效率的关键问题。提出了一种新的思路,利用测地距离初步构造不同流形样本点之间的关联性,再利用样本点之间局部几何结构的相似性进行修正,以更为准确地挖掘不同流形样本点之间的关联性。进一步提出一种新的半监督流形对齐算法,利用已知对应点信息和所挖掘样本点之间的关联性,将多个流形数据投影到共同的低维空间。与传统的半监督流形对齐算法相比,本算法在先验信息不充分的情况下,能更准确地联结不同流形数据集。最后通过在实际数据集上的实验验证了算法的有效性。     

On differential invariants of planar curves and recognizing partially occluded planar shapes

Viewing transformations like similarity, affine and projective maps may distort planar shapes considerably. However, it is possible to associate local invariant signature functions to smooth boundaries that enable recognition of distorted shapes even in the case of partial occlusion. The derivation of signature functions, generalizing the intrinsic curvature versus arc-length representation in the case of rigid motions in the plane, is based on differential invariants associated to viewing transformation.     

Fun sheet matching: towards automatic block decomposition for hexahedral meshes

Depending upon the numerical approximation method that may be implemented, hexahedral meshes are frequently preferred to tetrahedral meshes. Because of the layered structure of hexahedral meshes, the automatic generation of hexahedral meshes for arbitrary geometries is still an open problem. This layered structure usually requires topological modifications to propagate globally, thus preventing the general development of meshing algorithms such as Delaunay??s algorithm for tetrahedral meshes or the advancing-front algorithm based on local decisions. To automatically produce an acceptable hexahedral mesh, we claim that both global geometric and global topological information must be taken into account in the mesh generation process. In this work, we propose a theoretical classification of the layers or sheets participating in the geometry capture procedure. These sheets are called fundamental, or fun-sheets for short, and make the connection between the global layered structure of hexahedral meshes and the geometric surfaces that are captured during the meshing process. Moreover, we propose a first generation algorithm based on fun-sheets to deal with 3D geometries having 3- and 4-valent vertices.     

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.     

n-dimensional moment invariants and conceptual mathematical theoryof recognition n-dimensional solids

The proof of the generalized fundamental theorem of moment invariants (GFTMI) is presented for n-dimensional pattern recognition. On the basis of GFTMI, the moment invariants of affine transformation and subgroups of affine transformation are constructed. Using these invariants, the conceptual mathematical theory of recognition of geometric figures, solids, and their n-dimensional generalizations is worked out. By means of this theory, it is possible for the first time to analyze scenes consisting not only of polygons and polyhedra, but also scenes consisting of geometric figures and solids with curved contours and surfaces, respectively. In general, it is the author's opinion that this theory is a useful step toward the essential development of robot vision and toward creating machine intelligence-to make machines able to think by means of geometric concepts of different generalities and dimensions, and by associations of these concepts     

一种基于流形拓扑结构的轴承故障分类方法

根据不同故障类型的轴承信号在高维相空间中呈现不同结构的流形形态,提出了基于流形拓扑结构的轴承故障无监督分类方法.新方法首先将反映轴承状态的一维振动信号重构到高维相空间中,利用相点邻域的切空间信息逼近流形的局部几何结构,从而得到描述流形拓扑结构的矩阵;对所有样本构成的流形拓扑结构作多向主元分析后,将获得的主元信息作为特征集输入到C-均值分类器中进行轴承的状态识别.用轴承在正常状态、内圈故障、外圈故障的试验数据进行验证,结果表明,与传统的利用振动统计量为特征输入的方法相比,新方法能够更完整地刻画信号特征,获得更准确的分类识别率.     

基于多层次特征结构的二维形状渐变

二维形状渐变在二维角色动画、模式匹配、几何造型中有着重要的应用.已有方法大多根据边长、角度、面积等局部几何属性来完成形状之间的最佳对应和渐变,忽略了形状的内在特征结构.为此,提出一种基于多层次特征结构的二维形状渐变方法,首先将源形状和目标形状分解为若干个视觉显著性特征,并通过一种用户启发式的半自动方法建立2个形状的特征对应关系;然后根据形状的特征信息构建源形状和目标形状的多层次特征结构,分别表示形状特征的整体位置和朝向、形状特征的局部朝向和形状特征的局部细节;最后组合不同特征层次上的插值结果,重构出中间形状.在源形状到目标形状的渐变过程中,针对不同层次上的特征信息分别使用近似保刚性插值、边角插值以及弹性线性插值方法进行过渡.实验结果表明,该方法简单高效,有效地避免了形状的内部扭曲,保持了形状的局部特征,可产生自然、光滑且视觉真实的形状渐变序列.     

Quasi-Invariant Parameterisations and Matching of Curves in Images

In this paper, we investigate quasi-invariance on a smooth manifold, and show that there exist quasi-invariant parameterisations which are not exactly invariant but approximately invariant under group transformations and do not require high order derivatives. The affine quasi-invariant parameterisation is investigated in more detail and exploited for defining general affine semi-local invariants from second order derivatives only. The new invariants are implemented and used for matching curve segments under general affine motions and extracting symmetry axes of objects with 3D bilateral symmetry.     

基于边界检测的多流形学习算法*

已知流形学习算法都假设数据分布于一个单流形,而现实中大部分数据都分布在多流形上,因此限制算法的实际应用.基于此种情况,文中提出基于边界检测的多流形学习算法,通过检测流形的边界处理分布于多流形的数据,并且可以较好地保持流形内、流形间的测地距离.算法首先检测流形边界,再分别降维处理各流形,最后将各低维坐标重置于一个全局坐标系中.在人工数据集和真实数据集上的对比实验表明文中算法的可行性和有效性.     

A Riemannian Framework for Tensor Computing

Tensors are nowadays a common source of geometric information. In this paper, we propose to endow the tensor space with an affine-invariant Riemannian metric. We demonstrate that it leads to strong theoretical properties: the cone of positive definite symmetric matrices is replaced by a regular and complete manifold without boundaries (null eigenvalues are at the infinity), the geodesic between two tensors and the mean of a set of tensors are uniquely defined, etc. We have previously shown that the Riemannian metric provides a powerful framework for generalizing statistics to manifolds. In this paper, we show that it is also possible to generalize to tensor fields many important geometric data processing algorithms such as interpolation, filtering, diffusion and restoration of missing data. For instance, most interpolation and Gaussian filtering schemes can be tackled efficiently through a weighted mean computation. Linear and anisotropic diffusion schemes can be adapted to our Riemannian framework, through partial differential evolution equations, provided that the metric of the tensor space is taken into account. For that purpose, we provide intrinsic numerical schemes to compute the gradient and Laplace-Beltrami operators. Finally, to enforce the fidelity to the data (either sparsely distributed tensors or complete tensors fields) we propose least-squares criteria based on our invariant Riemannian distance which are particularly simple and efficient to solve.     

Intrinsic Statistics on Riemannian Manifolds: Basic Tools for Geometric Measurements

In medical image analysis and high level computer vision, there is an intensive use of geometric features like orientations, lines, and geometric transformations ranging from simple ones (orientations, lines, rigid body or affine transformations, etc.) to very complex ones like curves, surfaces, or general diffeomorphic transformations. The measurement of such geometric primitives is generally noisy in real applications and we need to use statistics either to reduce the uncertainty (estimation), to compare observations, or to test hypotheses. Unfortunately, even simple geometric primitives often belong to manifolds that are not vector spaces. In previous works [1, 2], we investigated invariance requirements to build some statistical tools on transformation groups and homogeneous manifolds that avoids paradoxes. In this paper, we consider finite dimensional manifolds with a Riemannian metric as the basic structure. Based on this metric, we develop the notions of mean value and covariance matrix of a random element, normal law, Mahalanobis distance and χ² law. We provide a new proof of the characterization of Riemannian centers of mass and an original gradient descent algorithm to efficiently compute them. The notion of Normal law we propose is based on the maximization of the entropy knowing the mean and covariance of the distribution. The resulting family of pdfs spans the whole range from uniform (on compact manifolds) to the point mass distribution. Moreover, we were able to provide tractable approximations (with their limits) for small variances which show that we can effectively implement and work with these definitions.     

平稳小波变换在仿射不变性目标识别中的应用

寻找相对于平移、尺度、旋转、扭曲不变的仿射不变量是现今多尺度分析在模式识别中应用的关键性问题。以文献[4]定义的仿射不变量为基础,构造了基于平稳小波变换的仿射不变量。通过分析,指出原文中所给绝对仿射不变量存在的缺陷,定义了一种新的绝对仿射不变量。试验结果和分析表明,构造的仿射不变量可以更好地用于目标物体识别。