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.     

Free knot splines for logistic models and threshold selection

The logistic regression model has been in use in statistical analysis for many years. The paper introduces a spline model to remove the linear restriction on logit function. By considering knot locations as free variables, spline approximation of data is improved. The number of knots and the degree of the spline functions can still be determined by using a model selection procedure. Moreover, a knot, seen as a free parameter for a piecewise linear spline, represents a break point in the logit function which may be interpreted as a threshold value. This method is applied to a clinical trial for an in vitro fertilization program.     

Surface reconstruction using bivariate simplex splines on Delaunay configurations

Recently, a new bivariate simplex spline scheme based on Delaunay configuration has been introduced into the geometric computing community, and it defines a complete spline space that retains many attractive theoretic and computational properties. In this paper, we develop a novel shape modeling framework to reconstruct a closed surface of arbitrary topology based on this new spline scheme. Our framework takes a triangulated set of points, and by solving a linear least-square problem and iteratively refining parameter domains with newly added knots, we can finally obtain a continuous spline surface satisfying the requirement of a user-specified error tolerance. Unlike existing surface reconstruction methods based on triangular B-splines (or DMS splines), in which auxiliary knots must be explicitly added in advance to form a knot sequence for construction of each basis function, our new algorithm completely avoids this less-intuitive and labor-intensive knot generating procedure. We demonstrate the efficacy and effectiveness of our algorithm on real-world, scattered datasets for shape representation and computing.     

Shape-preserving knot removal

Starting with a shape-preserving C¹ quadratic spline, we show how knots can be removed to produce a new spline which is within a specified tolerance of the original one, and which has the same shape properties. We give specific algorithms and some numerical examples, and also show how the method can be used to compute approximate best free-knot splines. Finally, we discuss how to handle noisy data, and develop an analogous knot removal algorithm for a monotonicity preserving surface method.     

Knot removal for parametric B-spline curves and surfaces

This paper is the third in a sequence of papers in which a knot removal strategy for splines, based on certain discrete norms, is developed. In the first paper, approximation methods defined as best approximations in these norms were discussed, while in the second paper a knot removal strategy for spline functions was developed. In this paper the knot removal strategy is extended to parametric spline curves and tensor product surfaces. The method has been implemented and thoroughly tested on a computer. We illustrate with several examples and applications.     

Subdivision Surfaces with Creases and Truncated Multiple Knot Lines

We deal with subdivision schemes based on arbitrary degree B‐splines. We focus on extraordinary knots which exhibit various levels of complexity in terms of both valency and multiplicity of knot lines emanating from such knots. The purpose of truncated multiple knot lines is to model creases which fair out. Our construction supports any degree and any knot line multiplicity and provides a modelling framework familiar to users used to B‐splines and NURBS systems.     

Image approximation by variable knot bicubic splines

This paper presents a degree of freedom or information content analysis of images in the context of digital image processing. As such it represents an attempt to quantify the number of truly independent samples one gathers with imaging devices. The degrees of freedom of a sampled image itself are developed as an approximation problem. Here, bicubic splines with variable knots are employed in an attempt to answer the question as to what extent images are finitely representable in the context of digital sensors and computers. Relatively simple algorithms for good knot placement are given and result in spline approximations that achieve significant parameter reductions at acceptable error levels. The knots themselves are shown to be useful as an indicator of image activity and have potential as an image segmentation device, as well as easy implementation in CCD signal processing and focal plane smart sensor arrays. Both mathematical and experimental results are presented.     

Manifold-valued Thin-Plate Splines with Applications in Computer Graphics

We present a generalization of thin‐plate splines for interpolation and approximation of manifold‐valued data, and demonstrate its usefulness in computer graphics with several applications from different fields. The cornerstone of our theoretical framework is an energy functional for mappings between two Riemannian manifolds which is independent of parametrization and respects the geometry of both manifolds. If the manifolds are Euclidean, the energy functional reduces to the classical thin‐plate spline energy. We show how the resulting optimization problems can be solved efficiently in many cases. Our example applications range from orientation interpolation and motion planning in animation over geometric modelling tasks to color interpolation.     

B样条曲线节点插入和升阶的统一方法

利用 B样条基转换矩阵的有关结果 ,本文给出了 B样条曲线插入节点和升阶的统一方法及算法 .本文方法建立在严密的数学背景上 ,以简洁严谨的递推公式给出其算法的数学模型 ,相应的算法效率高且易实现 ,算法的时间复杂性为 O((k- k 1) kn) ,其中 k,k分别为升阶前后曲线的阶 ,n k 1为插入节点和升阶后的节点数 .而且 ,本文方法及算法使用灵活 ,适用范围广 ,可用于同时插入任意个相同的或不同的节点并升任意阶 ,也可用于只插入节点或只升阶 .Cohen等的 Oslo算法、升阶方法都是本文方法的特例 ,而且本文方法效率更高     

高精度三次参数样条曲线的构造

构造参数样条曲线的关键是选取节点，该文讨论了GC^2三次参数样条曲线需满足的连续性方程，提出了构造GC^2三次参数样条曲线的新方法，在讨论了平面有序五点确定一组三次多项式函数曲线，平面有序六点唯一确定一条三次多项式函数曲线的基础上，提出了计算相邻两区间上的节点的算法，构造的插值曲线具有三次多项式函数精,该文还以实例对新方法与其它方法构造的插值曲线的精度进行了比较。     

Suboptimal Robot Joint Interpolation Within User-Specified Knot Tolerances

Approximation of a desired robot path can be accomplished by interpolating a curve through a sequence of joint-space knots. A smooth interpolated trajectory can be realized by using trigonometric splines. But, sometimes the joint trajectory is not required to exactly pass through the given knots. The knots may rather be centers of tolerances near which the trajectory is required to pass. In this article, we optimize trigonometric splines through a given set of knots subject to user-specified knot tolerances. The contribution of this article is the straightforward way in which intermediate constraints (i.e., knot angles) are incorporated into the parameter optimization problem. Another contribution is the exploitation of the decoupled nature of trigonometric splines to reduce the computational expense of the problem. The additional freedom of varying the knot angles results in a lower objective function and a higher computational expense compared to the case in which the knot angles are constrained to exact values. The specific objective functions considered are minimum jerk and minimum torque. In the minimum jerk case, the optimization problem reduces to a quadratic programming problem. Simulation results for a two-link manipulator are presented to support the results of this article.     

A class of general quartic spline curves with shape parameters

With a support on four consecutive subintervals, a class of general quartic splines are presented for a non-uniform knot vector. The splines have C² continuity at simple knots and include the cubic non-uniform B-spline as a special case. Based on the given splines, piecewise quartic spline curves with three local shape parameters are given. The given spline curves can be C²∩G³ continuous by fixing some values of the curve?s parameters. Without solving a linear system, the spline curves can also be used to interpolate sets of points with C² continuity. The effects of varying the three shape parameters on the shape of the quartic spline curves are determined and illustrated.     

对流-扩散方程数值解的四次 B 样条方法

基于四次 B 样条函数，提出一种求解一类对流-扩散方程的四次 B 样条方法。首 先利用光滑余因子协调法，得到有界闭区间上具有均匀节点的一元四次 B 样条基函数表达式。 接着计算在有界闭区间两端点处具有重节点的几种不同情况下的 B 样条基函数表达式，这些样 条基函数具有非负性、单位分解性等良好的性质。然后将一元四次 B 样条函数应用于求解一类 一维对流-扩散方程，其中对于对流-扩散方程的离散过程，对于时间变量的离散采用向前有限 差分，而对于空间变量的离散，引入参数 δ，建立四次样条逼近格式。之后利用四次 B 样条函 数去求解该对流-扩散方程。最后通过具体算例，将四次样条逼近方法与有限差分方法进行比较， 且给出直观的数值误差对比，由此说明样条逼近方法更加简便实用。     

Free knot splines for biochemical data

The use of spline functions in the analysis of empirical two-dimensional (2-D) data (y(i), x(i)) is described. Spline functions are excellent empirical functions, which can be used with advantage instead of other ones, such as polynomials or exponentials. The knot location seen as variable value corresponds to classical parameter used to describe oxidation curves. An application on characterization of LDL oxidability shows free knot splines in a regression context.     

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.     

多层积分值三次样条拟插值

目的 在实际问题中,某些插值问题结点处的函数值往往是未知的,而仅仅知道一些连续等距区间上的积分值。为此提出了一种基于未知函数在连续等距区间上的积分值和多层样条拟插值技术来解决函数重构。该方法称之为多层积分值三次样条拟插值方法。方法 首先,利用积分值的线性组合来逼近结点处的函数值;然后,利用传统的三次B-样条拟插值和相应的误差函数来实现多层三次样条拟插值;最后,给出两层积分值三次样条拟插值算子的多项式再生性和误差估计。结果 选取无穷次可微函数对多层积分值三次样条拟插值方法和已有的积分值三次样条拟插值方法进行对比分析。数值实验印证了本文方法在逼近误差和数值收敛阶均稍占优。结论本文多层三次样条拟插值函数能够在整体上很好的逼近原始函数,一阶和二阶导函数。本文方法较之于已有的积分值三次样条拟插值方法具有更好的逼近误差和数值收敛阶。该方法对连续等距区间上积分值的函数重构具有普适性。     

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

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

带参数的多结点样条

多结点样条函数是在通常样条函数中引入更多的附加结点，其优越性表现在使插值过程无须求解任何方程组，而且有局部性，对多结点样条函数做进一步研究，构造了一类带参数的多结点样条基本函数．该类函数不仅保持了一般多结点样条函数的优点，而且由于参数的引进，使得基数型的插值公式可形成一族，可以根据实际问题的需要在函数(曲线)族中作出最优选择．文中研究的带参数的多结点样条函数，除了能用于表达平滑的数据及几何造型之外。尤其能适应波动较大、频率较高的数据拟合问题，有助于解决信号处理及非规则几何造型的一些问题。     

Allgemeine interpolierende Splines vom Grade 3

Choosing a special case of a general Hermitian interpolating operator, an interpolating spline is constructed with respect to the usual transient-conditions within the knots of the spline. The resulting spline in general is not a polynomial spline. The polynomial spline is contained as a special case as well as e. g. rational, trigonometrical, and exponential splines. A sufficient criterion for existence and uniqueness is given for general interpolating splines of third degree. A statement concerning convergence is added.     

Splines in Higher Order TV Regularization

Splines play an important role as solutions of various interpolation and approximation problems that minimize special functionals in some smoothness spaces. In this paper, we show in a strictly discrete setting that splines of degree m−1 solve also a minimization problem with quadratic data term and m-th order total variation (TV) regularization term. In contrast to problems with quadratic regularization terms involving m-th order derivatives, the spline knots are not known in advance but depend on the input data and the regularization parameter λ. More precisely, the spline knots are determined by the contact points of the m–th discrete antiderivative of the solution with the tube of width 2λ around the m-th discrete antiderivative of the input data. We point out that the dual formulation of our minimization problem can be considered as support vector regression problem in the discrete counterpart of the Sobolev space W _2,0 ^m . From this point of view, the solution of our minimization problem has a sparse representation in terms of discrete fundamental splines.