Optimal Spline Approximation via ℓ0‐Minimization

Splines are part of the standard toolbox for the approximation of functions and curves in ?^d. Still, the problem of finding the spline that best approximates an input function or curve is ill‐posed, since in general this yields a “spline” with an infinite number of segments. The problem can be regularized by adding a penalty term for the number of spline segments. We show how this idea can be formulated as an ?₀‐regularized quadratic problem. This gives us a notion of optimal approximating splines that depend on one parameter, which weights the approximation error against the number of segments. We detail this concept for different types of splines including B‐splines and composite Bézier curves. Based on the latest development in the field of sparse approximation, we devise a solver for the resulting minimization problems and show applications to spline approximation of planar and space curves and to spline conversion of motion capture data.     

The visualization of knots and braids

We describe a new method for modelling braids and certain classes of knots and links, and how they may be visualized. The method uses generalized cylinders built around a bicubic spline centre line. We also show how multi-stranded, recursive, hawser laid ropes can be modelled using related techniques.     

The theoretical analysis for an iterative envelope algorithm

Cubic spline interpolating the local maximal/minimal points is often employed to calculate the envelopes of a signal approximately. However, the undershoots occur frequently in the cubic spline envelopes. To improve them, in our previous paper we proposed a new envelope algorithm, which is an iterative process by using the Monotone Piecewise Cubic Interpolation. Experiments show very satisfying results. But the theoretical analysis on why and how it works well was not given there. This paper establishes the theoretical foundation for the algorithm. We will study the structure of undershoots, prove rigorously that the algorithm converges to an envelope without undershoots with exponential rate of convergence, which can be used to determine the number of iterations needed in the algorithm for a good envelope in applications.     

Knot calculation for spline fitting via sparse optimization

Curve fitting with splines is a fundamental problem in computer-aided design and engineering. However, how to choose the number of knots and how to place the knots in spline fitting remain a difficult issue. This paper presents a framework for computing knots (including the number and positions) in curve fitting based on a sparse optimization model. The framework consists of two steps: first, from a dense initial knot vector, a set of active knots is selected at which certain order derivative of the spline is discontinuous by solving a sparse optimization problem; second, we further remove redundant knots and adjust the positions of active knots to obtain the final knot vector. Our experiments show that the approximation spline curve obtained by our approach has less number of knots compared to existing methods. Particularly, when the data points are sampled dense enough from a spline, our algorithm can recover the ground truth knot vector and reproduce the spline.     

Dual bases for spline spaces on cells

The purpose of this paper is twofold. First, we extend the basic dimension result for spline spaces on simple cells to a class of spline spaces which satisfy additional smoothness conditions at the interior vertex. This extension is useful for the study of super spline spaces. Secondly, and more importantly, we show how to choose minimal determining sets of Bézier coordinates for these spaces. These in turn are useful for constructing explicit locally supported bases for spline spaces on general triangulations.     

Curve fitting and fairing using conic splines

We present an efficient geometric algorithm for conic spline curve fitting and fairing through conic arc scaling. Given a set of planar points, we first construct a tangent continuous conic spline by interpolating the points with a quadratic Bézier spline curve or fitting the data with a smooth arc spline. The arc spline can be represented as a piecewise quadratic rational Bézier spline curve. For parts of the G¹ conic spline without an inflection, we can obtain a curvature continuous conic spline by adjusting the tangent direction at the joint point and scaling the weights for every two adjacent rational Bézier curves. The unwanted curvature extrema within conic segments or at some joint points can be removed efficiently by scaling the weights of the conic segments or moving the joint points along the normal direction of the curve at the point. In the end, a fair conic spline curve is obtained that is G² continuous at convex or concave parts and G¹ continuous at inflection points. The main advantages of the method lies in two aspects, one advantage is that we can construct a curvature continuous conic spline by a local algorithm, the other one is that the curvature plot of the conic spline can be controlled efficiently. The method can be used in the field where fair shape is desired by interpolating or approximating a given point set. Numerical examples from simulated and real data are presented to show the efficiency of the new method.     

Pseudo‐Spline Subdivision Surfaces

Pseudo‐splines provide a rich family of subdivision schemes with a wide range of choices that meet various demands for balancing the approximation power, the length of the support, and the regularity of the limit functions. Special cases of pseudo‐splines include uniform odd‐degree B‐splines and the interpolatory 2n‐point subdivision schemes, and the other pseudo‐splines fill the gap between these two families. In this paper we show how the refinement step of a pseudo‐spline subdivision scheme can be implemented efficiently using repeated local operations, which require only the data in the direct neighbourhood of each vertex, and how to generalize this concept to quadrilateral meshes with arbitrary topology. The resulting pseudo‐spline surfaces can be arbitrarily smooth in regular mesh regions and C¹ at extraordinary vertices as our numerical analysis reveals.     

Bending analysis of rectangular moderately thick plates using spline finite element method

A bending analysis of rectangular, moderately thick plates with general boundary conditions is presented using the spline element method. The cubic B spline interpolate functions are used to construct the field function of generalized displacements w, φ_itxand φ_ity. The spline finite element equations are derived based on the potential energy principle. For simplicity, the boundary conditions, which consist of three local spline points, are amended to fit specified boundary conditions. The shear effect is considered in the formulations. A number of numerical examples are described for rectangular, moderately thick plates. Since the cubic B spline interpolate functions have sufficient continuity and are piecewise polynomial, so the present numerical solutions show not only that the method gives accurate results, but also that the unified solutions of thick and thin plates can be directly obtained; the trouble with the so-called shear locking phenomenon does not occur here.     

基于方向微分和加权平均的运动模糊方向鉴别

在曝光的瞬间,造成图像模糊的运动,可近似作为直线运动来处理,但在像平面中的运动模糊方向未知。将原图像视为各向同性的一阶马尔科夫过程,提出了一种新的运动模糊方向鉴别方法,即方向微分鉴别方法,可以高精度鉴别匀速运动、加速运动、振动等各种运动的模糊方向,具有鉴别范围大、稳定性好的优点,克服了Y.Yitzhaky方法的不足。高精度估计出运动模糊方向,则可以通过图像旋转将运动模糊方向旋转到水平轴,图像恢复因此由二维问题转化为一维问题,大大降低了图像恢复的难度,且为图像恢复的并行计算打下基础。文章给出了采用双线性插值或三次C样条插值进行方向微分的详细计算方法,其中双线性插值方法计算量小,而三次C样条插值方法鉴别精度比双线性插值方法高。采用加权平均措施,平均了引起鉴别误差的各种随机因素,提高了鉴别精度,增强了运动模糊方向鉴别的稳定性。     

Construction and properties of spline dyadic wavelet filters

This paper focuses on the construction and properties of spline dyadic wavelet that equals its reconstruction wavelet. A general construction method of finite spline dyadic low-pass and high-pass filters is given. It proves that finite spline dyadic low-pass filters are symmetric about 0 or 1/2, but there are no finite spline high-pass filters possessing symmetry with respect to 0 or 1/2. It further shows that there exist infinite spline high-pass filters possessing symmetry with respect to 0 or 1/2, which can be constructed. Their energy is concentrated and so finite symmetric spline dyadic wavelet filter that equals its reconstruction filter can be obtained approximately. Construction examples for quadratic and cubic spline dyadic wavelet filters are given.     

Spline multiresolution and wavelet-like decompositions

Splines are useful tools to represent, modify and analyze curves and they play an important role in various practical applications. We present a multiresolution approach to spline curves with arbitrary knots that provides good feature detection and localization properties for non-equally distributed geometric data. In addition, we show how equidistributed data and knot sequences can be efficiently handled using signal processing techniques.     

一种B样条表面插值控制点的缩减方法

研究了从给定节点向量中选择节点进行B样条曲线插值的方法，并将此方法应用到行数据点不相同的B样条曲面插值，得到了一个通过对行节点矢量调整传递的曲面插值方法，理论分析和实验表明该方法可大量减少曲面控制点的数目．     

基于B样条模型的曲线特征点检测法

提出了一种基于B样条模型的曲线特征点检测法。该方法首先用B样条函数对原始曲线进行副近,得到原始曲线的分段解析表达式,然后利用曲线曲率分布来确定其特征点。B样条曲线分段解析的特点提出了曲率估计的精度,进而使特征点检测的准确度也得到提高,同时B样曲线拟合过程在一定程度上起到了对原始曲线的平滑作用,可抑制噪声对特征点检测的影响,并且这种平滑不具有常规高斯平滑的萎缩效应。实验结果证明了本文方法的有效性。     

Efficient circular arc interpolation based on active tolerance control

In this paper, we present an efficient sub-optimal algorithm for fitting smooth planar parametric curves by G¹ arc splines. To fit a parametric curve by an arc spline within a prescribed tolerance, we first sample a set of points and tangents on the curve adaptively as well as with enough density, so that an interpolation biarc spline curve can be with any desired high accuracy. Then, we construct new biarc curves interpolating local triarc spirals explicitly based on the control of permitted tolerances. To reduce the segment number of fitting arc spline as much as possible, we replace the corresponding parts of the spline by the new biarc curves and compute active tolerances for new interpolation steps. By applying the local biarc curve interpolation procedure recursively and sequentially, the result circular arcs with no radius extreme are minimax-like approximation to the original curve while the arcs with radius extreme approximate the curve parts with curvature extreme well too, and we obtain a near optimal fitting arc spline in the end. Even more, the fitting arc spline has the same end points and end tangents with the original curve, and the arcs will be jointed smoothly if the original curve is composed of several smooth connected pieces. The algorithm is easy to be implemented and generally applicable to circular arc interpolation problem of all kinds of smooth parametric curves. The method can be used in wide fields such as geometric modeling, tool path generation for NC machining and robot path planning, etc. Several numerical examples are given to show the effectiveness and efficiency of the method.     

异构CAD 数据交换中样条草图的处理方法

针对现有异构CAD 系统间的产品数据交换方法对样条草图处理不足问题,提出了 支持样条草图参数化交换的草图数据交换构架。将草图数据交换分为简单参数草图数据交换和 复杂参数草图数据交换。重点分析了复杂参数草图数据交换问题,通过引入Hausdorff 距离作 为适应度评价方法,构建了基于粒子群优化求解的样条草图参数化交换算法,利用曲率自适应 学习因子来避免局部最优解,使得不同曲率区域的参数点位置合理分布。所提方法在异构CAD 系统间进行了实验测试,结果证明了本方法的有效性。     

具有局部性质的球面插值样条曲线的构造

高维球面样条曲线拟合技术在计算机动画和惯性导航等领域都受到广泛地关注.实际中常需球面曲线插值给定的数据点,并要求曲线具有一定的连续性和良好的局部性质.此前的方法存在一定的局限性.为此,基于球面Bézier曲线,提出了一种仅利用插值点位置信息便可在任意维空间中构造C 2球面插值样条曲线的新方法.首先,通过映射拟合出了插值...     

Subdivision algorithms for the generation of box spline surfaces

This paper proposes a general approach to subdivision algorithms used in interactive computer aided design for splines which are linear combinations of translates of any box splines. We show how these algorithms can be used for efficient generation of the corresponding spline surfaces. Our results extend several known special cases.     

样条插值算法在耦合地球系统模式中的应用

为满足耦合地球系统模式应用的需求, 提出了一种二维样条插值算法, 并将其有效地实现成插值模块封装进地球系统建模框架（earth system modeling framework, ESMF）。该算法基于经典样条算法, 根据地球系统模式特点进行修改, 用两次一维插值扩张成二维插值, 引入极点区域外插处理, 将插值权重生成与插值结果计算两部分分离。实验结果表明, 该算法能获得高精度的插值结果, 模块化的设计使得用户可通过统一的接口来使用插值算法从而完成插值计算。     

基于AIWCPSO算法的三次样条气动参数插值方法

针对飞行仿真建模过程中气动参数以矩阵的形式给出, 大都存在着非线性关系, 提出一种基于自适应惯性权重的混沌粒子群优化(AIWCPSO) 算法的三次样条气动参数插值方法. 首先建立粒子与三次样条插值函数中系数的映射关系; 然后利用AIWCPSO 算法对三次样条插值函数的系数进行寻优, 将获得的最优解近似看作三次样条插值函数的系数; 最后计算得到离散点的气动参数. 仿真实验结果表明, 所提出的方法能有效地解决飞行气动参数插值问题.     

Surface modeling with polynomial splines over hierarchical T-meshes

Computer graphics and computer-aided design communities prefer piecewise spline patches to represent surfaces. But keeping the smoothness between the adjacent patches is a challenging task. In this paper, we present a method for stitching several surface patches, which is a key step in complicated surface modeling, with polynomial splines over hierarchical T-meshes (PHT-spline for short). The method is simple and can be easily applied to complex surface modeling. With the method, spline surfaces can be constructed efficiently and adaptively to fit genus-zero meshes after their spherical parameterization is obtained, where only small sized linear systems of equations are involved.