Shape of Elastic Strings in Euclidean Space

We construct a 1-parameter family of geodesic shape metrics on a space of closed parametric curves in Euclidean space of any dimension. The curves are modeled on homogeneous elastic strings whose elasticity properties are described in terms of their tension and rigidity coefficients. As we change the elasticity properties, we obtain the various elastic models. The metrics are invariant under reparametrizations of the curves and induce metrics on shape space. Analysis of the geometry of the space of elastic strings and path spaces of elastic curves enables us to develop a computational model and algorithms for the estimation of geodesics and geodesic distances based on energy minimization. We also investigate a curve registration procedure that is employed in the estimation of shape distances and can be used as a general method for matching the geometric features of a family of curves. Several examples of geodesics are given and experiments are carried out to demonstrate the discriminative quality of the elastic metrics.     

Affine connections, midpoint formation, and point reflection

We describe some differential-geometric structures in combinatorial terms: namely affine connections and their torsion and curvature, and we show that torsion free affine connections may equivalently be presented in terms of some simpler combinatorial structure: midpoint formation, and point reflection (geodesic symmetry). The method employed is that of synthetic differential geometry, which is briefly explained.     

Crest lines for surface segmentation and flattening

We present a method for extracting feature curves called crest lines from a triangulated surface. Then, we calculate the geodesic Voronoi diagram of crest lines to segment the surface into several regions. Afterward, barycentric surface flattening using theory from graph embeddings is implemented and, using the geodesic Voronoi diagram, we develop a faster surface flattening algorithm.     

Geodesic Distance and Curves Through Isotropic and Anisotropic Heat Equations on Images and Surfaces

This paper proposes a method to extract geodesic distance and geodesic curves using heat diffusion. The method is based on Varadhan’s formula that helps to obtain a numerical approximation of geodesic distance according to metrics based on different heat flows. The heat equation can be utilized by regarding an image or a surface as a medium for heat diffusion and letting the user set at least one source point in the domain. Both isotropic and anisotropic diffusions are considered here to obtain geodesics according to their respective metrics. (1) In the part of the paper where we deal with the isotropic case, we use gray-level intensity to compute the conductivity, i.e., those pixels with gray-levels similar to the source point would have higher conductivity. The model of Perona and Malik, which inhibits heat from diffusing out of homogeneous regions, is also used for geodesic computations in this paper. The two methods are combined and used for more complicated cases. We can also use the norm of the gradient of an image as the feature in the Perona and Malik model to make the heat diffuse along boundaries and edges. (2) For the anisotropic case, we use different eigenvectors and eigenvalues to compose the diffusion tensors to concentrate heat flow along chosen directions. Furthermore, to automate the process of extracting geodesic lines, we propose two automatic methods: a new voting method and a key point method, which are both especially designed for the heat-based method. Our algorithms are tested on synthetic and real images as well as on a mesh. The results are very promising and demonstrate the robustness of the algorithms.     

Heat method of non-uniform diffusion for computing geodesic distance on images and surfaces

This paper presents a non-uniform heat method to calculate geodesic distance and geodesic curves on the images and surfaces. Different from the varadhan’s formula-based heat method, our non-uniform heat method first finds the direction of distance increases by heat diffusion, and then recovers the geodesic distance by solving a Poisson equation. Various heat diffusion metrics obtained from different potentials and tensors, such as intensity-based metrics, gradient-based metrics, and anisotropy metrics et., describe the differences of geodesic distances in various regions. Combined with automatic geodesic segmentation technology, our heat method can be effectively and quickly applied to centerlines extraction and salient curves detection in images, skeleton extraction of shapes, and 3D path planning on surfaces. Two categories of discretization algorithms on scattered points and triangle meshes are more flexible and can often be used to more complicated cases. The algorithm is robust and simple to implement since it is based on solving a pair of standard sparse linear systems. Pre-calculation also greatly reduces time consumption and memory footprint.

     

GACV: Geodesic-Aided C-V method

A novel algorithm for image segmentation is proposed. The proposed method incorporates geodesic curves and C-V method to raise active contours’ performance on image segmentation. Moreover, we extend our method to color images. By practical experiments, it is verified that our model obtains better results than original methods, especially with respect to images within holes, complex background, weak edges, and noise.     

A Reparameterisation Based Approach to Geodesic Constrained Solvers for Curve Matching

We present a numerical algorithm for a new matching approach for parameterisation independent diffeomorphic registration of curves in the plane, targeted at robust registration between curves that require large deformations. This condition is particularly useful for the geodesic constrained approach in which the matching functional is minimised subject to the constraint that the evolving diffeomorphism satisfies the Hamiltonian equations of motion; this means that each iteration of the nonlinear optimisation algorithm produces a geodesic (up to numerical discretisation). We ensure that the computed solutions correspond to geodesics in the shape space by enforcing the horizontality condition (conjugate momentum is normal to the curve). Explicitly introducing and solving for a reparameterisation variable allows the use of a point-to-point matching condition. The equations are discretised using the variational particle-mesh method. We provide comprehensive numerical convergence tests and benchmark the algorithm in the context of large deformations, to show that it is a viable, efficient and accurate method for obtaining geodesics between curves.     

An optimization-driven approach for computing geodesic paths on triangle meshes

There are many application scenarios where we need to refine an initial path lying on a surface to be as short as possible. A typical way to solve this problem is to iteratively shorten one segment of the path at a time. As local approaches, they are conceptually simple and easy to implement, but they converge slowly and have poor performance on large scale models. In this paper, we develop an optimization driven approach to improve the performance of computing geodesic paths. We formulate the objective function as the total length and adopt the L-BFGS solver to minimize it. Computational results show that our method converges with super-linear rate, which significantly outperforms the existing methods. Moreover, our method is flexible to handle anisotropic metric, non-uniform density function, as well as additional user-specified constraints, such as coplanar geodesics and equally-spaced geodesic helical curves, which are challenging to the existing local methods.     

Modeling on triangulations with geodesic curves

This paper discusses the problem of modeling on triangulated surfaces with geodesic curves. In the first part of the paper we define a new class of curves, called geodesic Bézier curves, that are suitable for modeling on manifold triangulations. As a natural generalization of Bézier curves, the new curves are as smooth as possible. In the second part we discuss the construction of C ⁰ and C ¹ piecewise Bézier splines. We also describe how to perform editing operations, such as trimming, using these curves. Special care is taken to achieve interactive rates for modeling tasks. The third part is devoted to the definition and study of convex sets on triangulated surfaces. We derive the convex hull property of geodesic Bézier curves.

Geodesic Curves on Patched Polynomial Surfaces

A method is described for tracing geodesic curves across patched surfaces. Two techniques are discussed for constructing the curves - an initial value problem and a boundary value problem. Arc lengths are computed, as well as the enclosed area of an arbitrary region on the surface.     

基于Level Set方法的点采样曲面测地线计算及区域分解

点采样物体的几何处理是当前造型领域中的研究热点之一,如何有效地对点采样曲面进行区域分解是几何处理的基础性工作．该文首先提出了一种基于Level Set方法的点采样曲面上两点间最短路径的计算方法,用以解决区域分解中的边界曲线生成问题．为了保证求解Level Set微分方程的稳定性,文章采用移动最小平方(MLS)方法对点采样曲面进行均匀重采样和去噪音处理．在此基础上,又进一步提出了一个基于Level Set方法的点采样曲面区域拾取算法．最后给出了上述算法在点采样物体的几何处理中的应用实例．实验结果表明该文提出的算法稳定、快速且容易实现。     

流形网格上Bézier曲线的生成*

针对在流形网格上已有经典的简单割角法不能使用的问题,提出一种流形网格上的简单割角法,此算法使用的边是离散测地线,而经典的简单割角法使用的边是直线段,此算法收敛于网格模型上的Bézier曲线。用几何化生成曲线而不是参数化是研究的主要方法。此Bézier曲线特别适合于网格模型上自由曲线的设计。最后通过实例表明提出的算法正确、稳定、快速且容易实现,具有较好的仿真效果。     

Construction of Bézier surface patches with Bézier curves as geodesic boundaries

Given four polynomial or rational Bézier curves defining a curvilinear rectangle, we consider the problem of constructing polynomial or rational tensor-product Bézier patches bounded by these curves, such that they are geodesics of the constructed surface. The existence conditions and interpolation scheme, developed in a general context in earlier studies, are adapted herein to ensure that the geodesic-bounded surface patches are compatible with the usual polynomial/rational representation schemes of CAD systems. Precise conditions for four Bézier curves to constitute geodesic boundaries of a polynomial or rational surface patch are identified, and an interpolation scheme for the construction of such surfaces is presented when these conditions are satisfied. The method is illustrated with several computed examples.     

Fast Constrained Surface Extraction by Minimal Paths

In this paper we consider a new approach for single object segmentation in 3D images. Our method improves the classical geodesic active surface model. It greatly simplifies the model initialization and naturally avoids local minima by incorporating user extra information into the segmentation process. The initialization procedure is reduced to introducing 3D curves into the image. These curves are supposed to belong to the surface to extract and thus, also constitute user given information. Hence, our model finds a surface that has these curves as boundary conditions and that minimizes the integral of a potential function that corresponds to the image features. Our goal is achieved by using globally minimal paths. We approximate the surface to extract by a discrete network of paths. Furthermore, an interpolation method is used to build a mesh or an implicit representation based on the information retrieved from the network of paths. Our paper describes a fast construction obtained by exploiting the Fast Marching algorithm and a fast analytical interpolation method. Moreover, a Level set method can be used to refine the segmentation when higher accuracy is required. The algorithm has been successfully applied to 3D medical images and synthetic images.     

Gradient geodesic and Newton geodesic HMP algorithms for the optimization of hybrid systems

This paper provides algorithms for the optimization of autonomous hybrid systems based on the geometrical properties of switching manifolds. By employing the notion of geodesic curves on switching manifolds, the Hybrid Maximum Principle (HMP) algorithm introduced in Shaikh and Caines (2007) is extended to the so-called gradient geodesic and Newton geodesic algorithms. The convergence analysis for the algorithms is based upon the Lasalle Invariance Principle and simulation results illustrate their efficacy.     

Isometric 3D Shape Partial Matching Using GD-DNA

Isometric 3D shape partial matching has attracted a great amount of interest, with a plethora of applications ranging from shape recognition to texture mapping. In this paper, we propose a novel isometric 3D shape partial matching algorithm using the geodesic disk Laplace spectrum (GD-DNA). It transforms the partial matching problem into the geodesic disk matching problem. Firstly, the largest enclosed geodesic disk extracted from the partial shape is matched with geodesic disks from the full shape by the Laplace spectrum of the geodesic disk. Secondly, Generalized Multi-Dimensional Scaling algorithm (GMDS) and Euclidean embedding are conducted to establish final point correspondences between the partial and the full shape using the matched geodesic disk pair. The proposed GD-DNA is discriminative for matching geodesic disks, and it can well solve the anchor point selection problem in challenging partial shape matching tasks. Experimental results on the Shape Retrieval Contest 2016 (SHREC’16) benchmark validate the proposed method, and comparisons with isometric partial matching algorithms in the literature show that our method has a higher precision.     

Fractal initialization for high-quality mapping with self-organizing maps

Initialization of self-organizing maps is typically based on random vectors within the given input space. The implicit problem with random initialization is the overlap (entanglement) of connections between neurons. In this paper, we present a new method of initialization based on a set of self-similar curves known as Hilbert curves. Hilbert curves can be scaled in network size for the number of neurons based on a simple recursive (fractal) technique, implicit in the properties of Hilbert curves. We have shown that when using Hilbert curve vector (HCV) initialization in both classical SOM algorithm and in a parallel-growing algorithm (ParaSOM), the neural network reaches better coverage and faster organization.     

The curvature of characteristic curves on surfaces

Analyzing and interrogating designed surfaces remains an important and widely researched issue in computer-aided geometric design (CAGD). Treating families of characteristic curves on the surface proves a popular method of doing this. We show how to compute the curvature and geodesic curvature of characteristic curves on surfaces, such as contour lines, lines of curvature, asymptotic lines, isophotes, and reflection lines     

G 2 interpolation and blending on surfaces

We introduce a method for curvature-continuous (G ²) interpolation of an arbitrary sequence of points on a surface (implicit or parametric) with prescribed tangent and geodesic curvature at every point. The method can also be used forG ² blending of curves on surfaces. The interpolation/blending curve is the intersection curve of the given surface with a functional spline (implicit) surface. For the construction of blending curves, we derive the necessary formulas for the curvature of the surfaces. The intermediate results areG ² interpolation/blending methods in IR².     

Fast approximate geodesic paths on triangle mesh

We present a new algorithm to compute a geodesic path over a triangle mesh.Based on Novotni's propagating wavefront method which is similar to the well known Dijkstra algorithm,we made some improvements which Novotni had missed and we also gave the method to find out the geodesic path which Novotni had not.It can handle both convex and non-convex surfaces or even with boundaries.Experiment results show that our method works very well both in efficiency and precision.