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.     

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.     

Ricci flow embedding for rectifying non-Euclidean dissimilarity data

Pairwise dissimilarity representations are frequently used as an alternative to feature vectors in pattern recognition. One of the problems encountered in the analysis of such data is that the dissimilarities are rarely Euclidean, while statistical learning algorithms often rely on Euclidean dissimilarities. Such non-Euclidean dissimilarities are often corrected or a consistent Euclidean geometry is imposed on them via embedding. This paper commences by reviewing the available algorithms for analysing non-Euclidean dissimilarity data. The novel contribution is to show how the Ricci flow can be used to embed and rectify non-Euclidean dissimilarity data. According to our representation, the data is distributed over a manifold consisting of patches. Each patch has a locally uniform curvature, and this curvature is iteratively modified by the Ricci flow. The raw dissimilarities are the geodesic distances on the manifold. Rectified Euclidean dissimilarities are obtained using the Ricci flow to flatten the curved manifold by modifying the individual patch curvatures. We use two algorithmic components to implement this idea. Firstly, we apply the Ricci flow independently to a set of surface patches that cover the manifold. Second, we use curvature regularisation to impose consistency on the curvatures of the arrangement of different surface patches. We perform experiments on three real world datasets, and use these to determine the importance of the different algorithmic components, i.e. Ricci flow and curvature regularisation. We conclude that curvature regularisation is an essential step needed to control the stability of the piecewise arrangement of patches under the Ricci flow.     

Brain morphometry on congenital hand deformities based on Teichmüller space theory

Congenital Hand Deformities (CHD) usually occurred between the fourth and the eighth week after the embryo is formed. Failure of the transformation from arm bud cells to upper limb can lead to an abnormal appearing/functioning upper extremity which is presented at birth. Some causes are linked to genetics while others are affected by the environment, and the rest have remained unknown. CHD patients develop prehension through the use of their hands, which affects the brain as time passes. In recent years, CHD have gained increasing attention and researches have been conducted on CHD, both surgically and psychologically. However, the impacts of CHD on the brain structure are not well-understood so far. Here, we propose a novel approach to apply Teichmüller space theory and conformal welding method to study brain morphometry in CHD patients. Conformal welding signature reflects the geometric relations among different functional areas on the cortex surface, which is intrinsic to the Riemannian metric, invariant under conformal deformation, and encodes complete information of the functional area boundaries. The computational algorithm is based on discrete surface Ricci flow, which has theoretic guarantees for the existence and uniqueness of the solutions. In practice, discrete Ricci flow is equivalent to a convex optimization problem, therefore has high numerically stability. In this paper, we compute the signatures of contours on general 3D surfaces with the surface Ricci flow method, which encodes both global and local surface contour information. Then we evaluated the signatures of pre-central and post-central gyrus on healthy control and CHD subjects for analyzing brain cortical morphometry. Preliminary experimental results from 3D MRI data of CHD/control data demonstrate the effectiveness of our method. The statistical comparison between left and right brain gives us a better understanding on brain morphometry of subjects with Congenital Hand Deformities, in particular, missing the distal part of the upper limb.     

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.     

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.     

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.     

联合弯曲能量和标志点对应约束的非刚性医学图像配准

由于缺乏图像几何空间约束,基于互信息的非刚性医学图像配准常常产生不合理的形变。提出一种联合弯曲能量和标志点对应约束的非刚性医学图像配准方法,在互信息配准目标函数中添加弯曲能量惩罚和对应标志点间欧氏距离2个正则项,约束医学图像软组织不合理形变。脑部MRI、头颈部CT、胸部CBCT影像配准实验结果表明,该方法可有效提高配准质量。     

Modeling smooth shape using subdivision on differential coordinates

Traditional subdivision schemes are applied on Euclidean coordinates (the spatial geometry of the control mesh). Although the subdivision limit surfaces are almost everywhere C² continuous, their mean-curvature normals are only C⁰. In order to generate higher quality surfaces with better-distributed mean-curvature normals, we propose a novel framework to apply subdivision for shape modeling, which combines subdivision with differential shape processing. Our framework contains two parts: subdivision on differential coordinates (a kind of differential geometry of the control mesh), and mutual conversions between Euclidean coordinates and differential coordinates. Further discussions about various strategies in both parts include a special subdivision method for mean-curvature normals, additional surface editing options, and a version of our framework for curve design. Finally, we demonstrate the improvement on surface quality by comparing the results between our framework and traditional subdivision methods.     

Surface registration using a dynamic genetic algorithm

Robust and fast free-form surface registration is a useful technique in various areas such as object recognition and 3D model reconstruction for animation. Notably, an object model can be constructed, in principle, by surface registration and integration of range images of the target object from different views. In this paper, we propose to formulate the surface registration problem as a high dimensional optimization problem, which can be solved by a genetic algorithm (GA) (Genetic Algorithms in Search Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989). The performance of the GA for surface registration is highly dependent on its speed in evaluating the fitness function. A novel GA with a new fitness function and a new genetic operator is proposed. It can compute an optimal registration 1000 times faster than a conventional GA. The accuracy, speed and the robustness of the proposed method are verified by a number of real experiments.     

Newton methods for parametric surface registration. Part II. Experimental validation

The first part of this paper introduced a new freeform surface registration algorithm whereby sets of points measured from a physical surface are aligned to the computer-aided design model of the surface. The algorithm is based on traditional Newton minimization techniques with the benefit of analytic formulas for derivatives. In the past, these techniques have been abandoned due to the inability to efficiently compute derivative information of the registration objective function. The result is a new method for parametric surface registration.In the second part, more specific implementation details are given such as the various types of Newton methods employed. In addition, experimental results are provided that compare these new methods to existing registration techniques such as ICP [IEEE Trans Pattern Anal Mach Intell 14 (1992) 239]. The results reveal the advantages and disadvantages characteristic of these new techniques.     

网格模型中直纹面的提取

提出一种基于直母线族提取与拟合的网格模型直纹面提取方法.首先通过集合误差权排序方法从模型中选择一个可信直母线种子,然后通过局部标架引导搜索邻接直母线,移动标架重复上述搜索过程,直到跨出网格边界或者开始循环搜索.利用"投影"光顺法对齐直母线段族首末端点,再通过定义欧氏6空间下的距离函数,将欧氏3空间下的直线族逼近直纹面问题转换成欧氏6空间下B样条曲线最小二乘拟合问题.为了使逼近的曲面光顺,在曲线拟合过程中引入了能量函数.与其他算法相比,文中方法获得了较强的直母线族的鲁棒性和精确性,并能有效、合理地拟合出光顺直纹面.     

Registering multiview range data to create 3D computer objects

Concerns the problem of range image registration for the purpose of building surface models of 3D objects. The registration task involves finding the translation and rotation parameters which properly align overlapping views of the object so as to reconstruct from these partial surfaces, an integrated surface representation of the object. The registration task is expressed as an optimization problem. We define a function which measures the quality of the alignment between the partial surfaces contained in two range images as produced by a set of motion parameters. This function computes a sum of Euclidean distances from control points on one surfaces to corresponding points on the other. The strength of this approach is in the method used to determine point correspondences. It reverses the rangefinder calibration process, resulting in equations which can be used to directly compute the location of a point in a range image corresponding to an arbitrary point in 3D space. A stochastic optimization technique, very fast simulated reannealing (VFSR), is used to minimize the cost function. Dual-view registration experiments yielded excellent results in very reasonable time. A multiview registration experiment took a long time. A complete surface model was then constructed from the integration of multiple partial views. The effectiveness with which registration of range images can be accomplished makes this method attractive for many practical applications where surface models of 3D objects must be constructed     

A Variational Approach to Video Registration with Subspace Constraints

This paper addresses the problem of non-rigid video registration, or the computation of optical flow from a reference frame to each of the subsequent images in a sequence, when the camera views deformable objects. We exploit the high correlation between 2D trajectories of different points on the same non-rigid surface by assuming that the displacement of any point throughout the sequence can be expressed in a compact way as a linear combination of a low-rank motion basis. This subspace constraint effectively acts as a trajectory regularization term leading to temporally consistent optical flow. We formulate it as a robust soft constraint within a variational framework by penalizing flow fields that lie outside the low-rank manifold. The resulting energy functional can be decoupled into the optimization of the brightness constancy and spatial regularization terms, leading to an efficient optimization scheme. Additionally, we propose a novel optimization scheme for the case of vector valued images, based on the dualization of the data term. This allows us to extend our approach to deal with colour images which results in significant improvements on the registration results. Finally, we provide a new benchmark dataset, based on motion capture data of a flag waving in the wind, with dense ground truth optical flow for evaluation of multi-frame optical flow algorithms for non-rigid surfaces. Our experiments show that our proposed approach outperforms state of the art optical flow and dense non-rigid registration algorithms.     

Scan integration as a labelling problem

Integration is a crucial step in the reconstruction of complete 3D surface model from multiple scans. Ever-present registration errors and scanning noise make integration a nontrivial problem. In this paper, we propose a novel method for multi-view scan integration where we solve it as a labelling problem. Unlike previous methods, which have been based on various merging schemes, our labelling-based method is essentially a selection strategy. The overall surface model is composed of surface patches from selected input scans. We formulate the labelling via a higher-order Markov Random Field (MRF) which assigns a label representing an index of some input scan to every point in a base surface. Using a higher-order MRF allows us to more effectively capture spatial relations between 3D points. We employ belief propagation to infer this labelling and experimentally demonstrate that this integration approach provides significantly improved integration via both qualitative and quantitative comparisons.     

Robust 3D object registration without explicit correspondence using geometric integration

3D vision-guided manipulation of components is a key problem of industrial machine vision. In this paper, we focus on the localization and pose estimation of known industrial objects from 3D measurements delivered by a scanning sensor. Since local information extracted from these measurements is unreliable due to noise, spatially unstructured measurements and missing detections, we present a novel objective function for robust registration without using correspondence information, based on the likelihood of model points. Furthermore, by extending Runge–Kutta-type integration directly to the group of Euclidean transformation, we infer object pose by computing the gradient flow directly on the related manifold. Comparison of our approach to existing state of the art methods shows that our method is more robust against poor initializations while having comparable run-time performance.     

On bending invariant signatures for surfaces

Isometric surfaces share the same geometric structure, also known as the "first fundamental form." For example, all possible bendings of a given surface that includes all length preserving deformations without tearing or stretching the surface are considered to be isometric. We present a method to construct a bending invariant signature for such surfaces. This invariant representation is an embedding of the geometric structure of the surface in a small dimensional Euclidean space in which geodesic distances are approximated by Euclidean ones. The bending invariant representation is constructed by first measuring the intergeodesic distances between uniformly distributed points on the surface. Next, a multidimensional scaling technique is applied to extract coordinates in a finite dimensional Euclidean space in which geodesic distances are replaced by Euclidean ones. Applying this transform to various surfaces with similar geodesic structures (first fundamental form) maps them into similar signature surfaces. We thereby translate the problem of matching nonrigid objects in various postures into a simpler problem of matching rigid objects. As an example, we show a simple surface classification method that uses our bending invariant signatures.     

基于混合特征的非刚性点阵配准算法

提出一种基于混合特征的非刚性点阵配准算法.该算法包含了对应关系评估与空间变换更新两个相互交替的步骤.首先定义了两个特征描述法用于描述两个点阵之间的全局和局部几何结构特征差异,随后合并这两个特征描述法建立一个基于混合特征的能量优化方程.该能量优化方程可以利用线性分配技术进行求解,同时可以灵活地选择使用最小化全局结构特征差异或最小化局部结构特征差异来评估两个点阵之间的对应关系.为了增强前述两个步骤之间的协调性,我们利用能量权重调节在整个配准过程中控制能量优化从最小化局部结构特征差异逐步转变为最小化全局结构特征差异,同时控制用于空间变换的薄板样条函数（Thin plate spline）的更新从刚性变换逐步转变为非刚性变换.我们在二维轮廓配准、三维轮廓配准、序列图像配准和图像特征点配准下对本文算法进行了各项性能测试,同时也与当前8种流行算法进行了性能比较.本文算法展现了卓越的非刚性配准性能,并在大部分实验中超越了当前的相关算法.     

Robust surface registration using optimal mass transport and Teichmüller mapping

Surface registration plays a significant role in computer vision and engineering fields. One of the most challenging problems in surface registration, however, is to obtain a unique bijective registration for surfaces with large deformations and landmarks constraints. In this work, a novel surface registration framework is proposed to tackle this problem using optimal mass transport mapping (OMT-Map) and Teichmüller mapping (T-Map). All metric surfaces with the disk topology are mapped to the planar disk using OMT-Map, which avoids huge area distortion, thus rendering our method more robust. A landmark-constrained T-Map is then computed between two planar disks such that the maximal conformality distortion is minimized while the landmarks are matched. Compared with existing surface registration methods, our method is more advantageous in enforcing the robustness by avoiding large area distortion, and producing diffeomorphisms with all landmarks matched consistently. Numerical experiments on various surfaces demonstrate the efficiency, robustness of our method.