A class of template splines

A common frame of template splines that unifies the definitions of various spline families, such as smoothing, regression or penalized splines, is considered. The nonlinear nonparametric regression problem that defines the template splines can be reduced, for a large class of Hilbert spaces, to a parameterized regularized linear least squares problem, which leads to an important computational advantage. Particular applications of template splines include the commonly used types of splines, as well as other atypical formulations. In particular, this extension allows an easy incorporation of additional constraints, which is generally not possible in the context of classical spline families.     

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.     

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.     

Least Committed Splines in 3D Modelling of Free Form Objects from Intensity Images

Generating 3D models of objects from video sequences is an important problem in many multimedia applications ranging from teleconferencing to virtual reality. In this paper, we present a method of estimating the 3D face model from a monocular image sequence, using a few standard results from the affine camera geometry literature in computer vision, and spline fitting techniques using a modified non parametric regression technique. We use the bicubic spline functions to model the depth map, given a set of observation depth maps computed from frame pairs in a video sequence. The minimal number of splines are chosen on the basis of the Schwartz's Criterion. We extend the spline fitting algorithm to hierarchical splines. Note that the camera calibration parameters and the prior knowledge of the object shape is not required by the algorithm. The system has been successfully demonstrated to extract 3D face structure of humans as well as other objects, starting from their image sequences.     

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.     

Feature-based spline optimization in CAD

In this paper, an advanced method for CAD-based spline structure optimization is investigated. The method is based on the combination of the commonly known parameter-based spline shape optimization and a recently presented feature-based structure variation concept for commercial CAD tools. The aim is to extend common parameter-based spline shape variation by the additional possibility to automatically add and remove control points or entire splines directly in CAD space. Such advanced spline modification provides a new level of flexibility in general geometry-based structural optimization. Using these splines to build CAD models, entirely new structures may be automatically generated during an optimization run through this newly gained flexibility in spline manipulation. The idea is to roughly define a continuous design space by basic splines and to gradually increase their shape complexity by control point number variation during optimization. Thus, operating on a knowledge-lean initialization—a design space bounded by basic splines and filled with material—this combination further extends the search and solution spaces of CAD-based structural optimization. The paper provides an outlook towards automated geometry-based structure creation combining nowadays commercial CAD software and a dedicated variation and optimization framework for geometry-based structural optimization.     

High accuracy spline interpolation for 5-axis machining

This article presents a new algorithm for simultaneous 5-axis spline interpolation. The algorithm basically merges two concepts: (1) the interpolation of the toolpath with Pythagorean Hodograph (PH) curves and (2) the analytic solution of the inverse kinematic problem using the template equation method. The first method allows one to obtain a analytic relation between the arclength and the parameter of the toolpath curve. This one enables one to control the velocity of the tool on the workpiece. The second method allows one to determine the analytic solution of the parameterized inverse kinematic problem that permits us to introduce arbitrary number of geometric parameters. A natural selection of the possible parameters can be the parameters of tool geometry and the workpiece placement. This way, the off-line generated inverse solutions—that transform the cutter contact curve into axis values—can be online compensated, as soon as the exact parameter values are become known. Based on these two approaches, a robust and fast method for the simultaneous 5-axis spline interpolation is developed. The result of this new algorithm is time-dependent axis splines which represent the given toolpath with high accuracy.     

Translational Covering of Closed Planar Cubic B-Spline Curves

Spline curves are useful in a variety of geometric modeling and graphics applications and covering problems abound in practical settings. This work defines a class of covering decision problems for shapes bounded by spline curves. As a first step in addressing these problems, this paper treats translational spline covering for planar, uniform, cubic B‐splines. Inner and outer polygonal approximations to the spline regions are generated using enclosures that are inside two different types of piecewise‐linear envelopes. Our recent polygonal covering technique is then applied to seek translations of the covering shapes that allow them to fully cover the target shape. A feasible solution to the polygonal instance provides a feasible solution to the spline instance. We use our recent proof that 2D translational polygonal covering is NP‐hard to establish NP‐hardness of our planar translational spline covering problem. Our polygonal approximation strategy creates approximations that are tight, yet the number of vertices is only a linear function of the number of control points. Using recent results on B‐spline curve envelopes, we bound the distance from the spline curve to its approximation. We balance the two competing objectives of tightness vs. number of points in the approximation, which is crucial given the NP‐hardness of the spline problem. Examples of the results of our spline covering work are provided for instances containing as many as six covering shapes, including both convex and nonconvex regions. Our implementation uses the LEDA and CGAL C++ libraries of geometric data structures and algorithms.     

Envelopes and tubular splines

Envelopes of monoparametric families of spheres determine canal surfaces. In the particular case of a quadratic family of spheres the envelope is an algebraic surface of degree four that is composed of circles. We are interested in the construction of smooth tubular splines with pieces of envelopes of quadratic families of spheres. We present a scheme for the construction of a tubular spline that interpolates a sequence of circles in 3D. We control the shape near each circle by prescribing a sphere that contains it and is tangent to the spline. We offer further shape handles for local control through weights that are assigned to the controlling spheres.     

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.     

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.     

Local control of interval tension using weighted splines

Cubic spline interpolation and B-spline sums are useful and powerful tools in computer aided design. These are extended by weighted cubic splines which have tension controls that allow the user to tighten or loosen the curve on intervals between interpolation points. The weighted spline is a C¹ piecewise cubic that minimizes a variational problem similar to one that a C² cubic spline minimizes. A B-spline like basis is constructed for weighted splines where each basis function is nonnegative and nonzero only on four intervals. The basis functions sum up identically to one, thus curves generated by summing control points multiplied by the basis functions have the convex hull property. Different weights are built into the basis functions so that the control point curves are piecewise cubics with local control of interval tension. If all weights are equal, then the weighted spline is the C² cubic spline and the basis functions are B-splines.     

GeD spline estimation of multivariate Archimedean copulas

A new multivariate Archimedean copula estimation method is proposed in a non-parametric setting. The method uses the so-called Geometrically Designed splines (GeD splines) to represent the cdf of a random variable W_θ, obtained through the probability integral transform of an Archimedean copula with parameter θ. Sufficient conditions for the GeD spline estimator to possess the properties of the underlying theoretical cdf, K(θ,t), of W_θ, are given. The latter conditions allow for defining a three-step estimation procedure for solving the resulting non-linear regression problem with linear inequality constraints. In the proposed procedure, finding the number and location of the knots and the coefficients of the unconstrained GeD spline estimator and solving the constraint least-squares optimisation problem are separated. Thus, the resulting spline estimator is used to recover the generator and the related Archimedean copula by solving an ordinary differential equation. The proposed method is truly multivariate, it brings about numerical efficiency and as a result can be applied with large volumes of data and for dimensions d≥2, as illustrated by the numerical examples presented.     

Spatial interpolation of large climate data sets using bivariate thin plate smoothing splines

Thin plate smoothing splines are widely used to spatially interpolate surface climate, however, their application to large data sets is limited by computational efficiency. Standard analytic calculation of thin plate smoothing splines requires O(n³) operations, where n is the number of data points, making routine computation infeasible for data sets with more than around 2000 data points. An O(N) iterative procedure for calculating finite element approximations to bivariate minimum generalised cross validation (GCV) thin plate smoothing splines operations was developed, where N is the number of grid points. The key contribution of the method lies in the incorporation of an automatic procedure for optimising smoothness to minimise GCV. The minimum GCV criterion is commonly used to optimise thin plate smoothing spline fits to climate data. The method discretises the bivariate thin plate smoothing spline equations using hierarchical biquadratic B-splines, and uses a nested grid multigrid procedure to solve the system. To optimise smoothness, a double iteration is incorporated, whereby the estimate of the spline solution and the estimate of the optimal smoothing parameter are updated simultaneously. When the method was tested on temperature data from the African and Australian continents, accurate approximations to analytic solutions were obtained.     

Generalized taylor splines

A generalization of polynomial spline theory is presented which allows the construction of splines of any order. The kernel is based on a Taylor series expansion of the governing equations and Gaussian elimination is used for the numerical calculation of the splines coefficients. The general steps are described and tests are performed for the classical cubic and quintic splines and also for an unorthodox 25th order spline.     

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.     

Evolution-based least-squares fitting using Pythagorean hodograph spline curves

The problem of approximating a given set of data points by splines composed of Pythagorean hodograph (PH) curves is addressed. We discuss this problem in a framework that is not only restricted to PH spline curves, but can be applied to more general representations of shapes. In order to solve the highly non-linear curve fitting problem, we formulate an evolution process within the family of PH spline curves. This process generates a family of curves which depends on a time-like variable t. The best approximant is shown to be a stationary point of this evolution process, which is described by a differential equation. Solving it numerically by Euler's method is shown to be related to Gauss–Newton iterations. Different ways of constructing suitable initial positions for the evolution are suggested.     

Retailoring Box Splines to Lattices for Highly Isotropic Volume Representations

3D box splines are defined by convolving a 1D box function with itself along different directions. In volume visualization, box splines are mainly used as reconstruction kernels that are easy to adapt to various sampling lattices, such as the Cartesian Cubic (CC), Body‐Centered Cubic (BCC), and Face‐Centered Cubic (FCC) lattices. The usual way of tailoring a box spline to a specific lattice is to span the box spline by exactly those principal directions that span the lattice itself. However, in this case, the preferred directions of the box spline and the lattice are the same, amplifying the anisotropic effects of each other. This leads to an anisotropic volume representation with strongly preferred directions. Therefore, in this paper, we retailor box splines to lattices such that the sets of vectors that span the box spline and the lattice are disjoint sets. As the preferred directions of the box spline and the lattice compensate each other, a more isotropic volume representation can be achieved. We demonstrate this by comparing different combinations of box splines and lattices concerning their anisotropic behavior in tomographic reconstruction and volume visualization.     

Automatic G arc spline interpolation for closed point set

A method for generating an interpolation closed G¹ arc spline on a given closed point set is presented. For the odd case, i.e. when the number of the given points is odd, this paper disproves the traditional opinion that there is only one closed G¹ arc spline interpolating the given points. In fact, the number of the resultant closed G¹ arc splines fulfilling the interpolation condition for the odd case is exactly two. We provide an evaluation method based on the arc length as well such that the choice between those two arc splines is made automatically. For the even case, i.e. when the number of the given points is even, the points are automatically moved based on weight functions such that the interpolation condition for generating closed G¹ arc splines is satisfied, and that the adjustment is small. And then, the G¹ arc spline is constructed such that the radii of the arcs in the spline are close to each other. Examples are given to illustrate the method.