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.     

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.     

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.     

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.     

基于离散粒子群算法的矩形件优化排样

目前,粒子群算法在连续问题优化上的应用已经很广泛,然而在离散问题优化方面仍处在尝试阶段.提出了一种改进粒子群算法来解决矩形件排样优化问题(离散优化问题).该算法融合了遗传算法中的交叉和变异思想,采用了信息交流策略,使其达到快速优化目的.算法也对"最低水平线法"解码方式进行了改进.实验结果表明,该算法具有快速,高效特点,与现有同类算法比较,在解决矩形件排样问题方面的优势明显.     

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.     

Gradient descent learning algorithm overview: a general dynamicalsystems perspective

Gives a unified treatment of gradient descent learning algorithms for neural networks using a general framework of dynamical systems. This general approach organizes and simplifies all the known algorithms and results which have been originally derived for different problems (fixed point/trajectory learning), for different models (discrete/continuous), for different architectures (forward/recurrent), and using different techniques (backpropagation, variational calculus, adjoint methods, etc.). The general approach can also be applied to derive new algorithms. The author then briefly examines some of the complexity issues and limitations intrinsic to gradient descent learning. Throughout the paper, the author focuses on the problem of trajectory learning.     

Design and development of a unified framework towards swarm intelligence

The application of swarm intelligence (SI) in the optimization field has been gaining much popularity, and various SI algorithms have been proposed in last decade. However, with the increased number of SI algorithms, most research focuses on the implementation of a specific choice of SI algorithms, and there has been rare research analyzing the common features among SI algorithms coherently. More importantly, no general principles for the implementation and improvement of SI algorithms exist for solving various optimization problems. In this research, aiming to cover such a research gap, a unified framework towards SI is proposed inspired by the in-depth analysis of SI algorithms. The unified framework consists of the most frequently used operations and strategies derived from typical examples of SI algorithms. Following the proposed unified framework, the intrinsic features of SI algorithms can be understood straightforwardly and the implementation and improvement of SI algorithms can be achieved effortlessly, which is of great importance in practice. The numerical experiments examine the effects of the possible strategies employed in the unified framework, and provide pilot attempts to validate the performance of different combinations of strategies, which can not only facilitate specific SI algorithm application, but also can motivate SI algorithm innovation.     

Notes on averaging over acyclic digraphs and discrete coverage control

In this paper we study averaging algorithms and coverage control laws in a unified light. First, we characterize the convergence properties of averaging algorithms over acyclic digraphs with fixed and controlled-switching topology. Second, we introduce and study novel discrete coverage control laws, which are useful in practical implementations of coverage strategies. We characterize the close relationship of the novel discrete control laws with continuous coverage control laws and with averaging algorithms over a class of acyclic digraphs, that we term discrete Voronoi graphs. These results provide a unified framework to model a vast class of distributed optimization problems.     

非对称AdaBoost算法及其在目标检测中的应用

针对目标检测中的非对称分类问题,在分析现有的由离散AdaBoost算法扩展得到的代价敏感(即非对称)学习算法的基础上,提出了以三个不同的非对称错误率上界为核心的推导非对称AdaBoost算法的统一框架. 在该框架下, 不仅现有离散型非对称AdaBoost算法之间的关系非常清晰, 而且其中不符合理论推导的部分可以很容易得到修正. 同时, 利用不同的优化方法, 最小化这三个不同上界, 推出了连续型AdaBoost算法的非对称扩展(用Asym-Real AdaBoost和Asym-Gentle AdaBoost 表示). 新的算法不仅在弱分类器组合系数的计算上比现有离散型算法更加方便, 而且实验证明, 在人脸检测和行人检测两方面都获得了比传统对称AdaBoost算法和离散型非对称AdaBoost算法更好的性能.     

Fast solver for some computational imaging problems: A regularized weighted least-squares approach

In this paper we propose to solve a range of computational imaging problems under a unified perspective of a regularized weighted least-squares (RWLS) framework. These problems include data smoothing and completion, edge-preserving filtering, gradient-vector flow estimation, and image registration. Although originally very different, they are special cases of the RWLS model using different data weightings and regularization penalties. Numerically, we propose a preconditioned conjugate gradient scheme which is particularly efficient in solving RWLS problems. We provide a detailed analysis of the system conditioning justifying our choice of the preconditioner that improves the convergence. This numerical solver, which is simple, scalable and parallelizable, is found to outperform most of the existing schemes for these imaging problems in terms of convergence rate.     

模拟退火法在钟手表机芯布局中的应用

布局问题,特别是三维物体的布局问题在工业界有着广泛的用途,由于该问题在理论上已属于ＮＰ完全问题,很难用传统优化算法求解,钟手表机芯设计中的传动件布局是具有强约束的三维物体布局问题,根据退火法是一种用于解决连续,有序离散和多模态优化问题的随机优化技术,本文利用根据退火法成功地解决了钟手表机芯设计中的难题,该文还提供了解决一般物体布局问题的框架。     

Curvature estimation scheme for triangle meshes using biquadratic Bézier patches

When dealing with triangle meshes, it is often important to compute curvature information for the purposes of feature recognition, segmentation, or shape analysis. Since a triangle mesh is a piecewise linear surface, curvature has to be estimated. Several different schemes have been proposed, both discrete and continuous, i.e. based on fitting surfaces locally. This paper compares commonly used discrete and continuous curvature estimation schemes. We also present a novel method which uses biquadratic Bézier patches as a local surface fitting technique.     

简述公钥密码加密体制

在安全系统中信息安全问题是非常重要问题,然而,在信息安全中密码技术是信息安全的基础,也是最常用的安全手段,公钥加密是密码加密方法中的一种。目前,流行的公钥密码主要基于3类困难问题:基于大整数因式分解的RSA方案,离散对数问题的EIGamal方案,以及基于椭圆曲线离散对数的椭圆曲线方案。但是以上的这些方案都存在威胁,随着因式分解和离散对数的求解技术的不断提高,特别是量子算法的出现都可以解决上述问题。结合已经有的加密技术简略介绍了公钥加密算法的发展情况。     

Circle detection using discrete differential evolution optimization

This paper introduces a circle detection method based on differential evolution (DE) optimization. Just as circle detection has been lately considered as a fundamental component for many computer vision algorithms, DE has evolved as a successful heuristic method for solving complex optimization problems, still keeping a simple structure and an easy implementation. It has also shown advantageous convergence properties and remarkable robustness. The detection process is considered similar to a combinational optimization problem. The algorithm uses the combination of three edge points as parameters to determine circle candidates in the scene yielding a reduction of the search space. The objective function determines if some circle candidates are actually present in the image. This paper focuses particularly on one DE-based algorithm known as the discrete differential evolution (DDE), which eventually has shown better results than the original DE in particular for solving combinatorial problems. In the DDE, suitable conversion routines are incorporated into the DE, aiming to operate from integer values to real values and then getting integer values back, following the crossover operation. The final algorithm is a fast circle detector that locates circles with sub-pixel accuracy even considering complicated conditions and noisy images. Experimental results on several synthetic and natural images with varying range of complexity validate the efficiency of the proposed technique considering accuracy, speed, and robustness.     

求解矩形和圆形装填问题的最大穴度算法

在超大规模集成电路设计，裁缝裁剪布料，玻璃切割等工作中提出了矩形和圆形装填问题，即把不同大小的矩形块和圆饼装入一个矩形容器中，以最大化容器的面积利用率为优化目标。对这一问题，可采用模拟退火，遗传算法等国际流行算法进行求解，但这些方法计算时间较长，计算结果的优度也不甚理想。利用人类的智慧和经验，提出了一种求解此问题的最大穴度算法。并对3个随机生成的测试实例进行了实算测试。所得结果的平均面积利用率为90．80％，平均计算时阊为8．38s。测试结果表明，算法对求解矩形和圆形装填问题是行之有效的。     

A unified operator splitting approach for multi-scale fluid–particle coupling in the lattice Boltzmann method

A unified framework to derive discrete time-marching schemes for the coupling of immersed solid and elastic objects to the lattice Boltzmann method is presented. Based on operator splitting for the discrete Boltzmann equation, second-order time-accurate schemes for the immersed boundary method, viscous force coupling and external boundary force are derived. Furthermore, a modified formulation of the external boundary force is introduced that leads to a more accurate no-slip boundary condition. The derivation also reveals that the coupling methods can be cast into a unified form, and that the immersed boundary method can be interpreted as the limit of force coupling for vanishing particle mass. In practice, the ratio between fluid and particle mass determines the strength of the force transfer in the coupling. The integration schemes formally improve the accuracy of first-order algorithms that are commonly employed when coupling immersed objects to a lattice Boltzmann fluid. It is anticipated that they will also lead to superior long-time stability in simulations of complex fluids with multiple scales.