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.     

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.     

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.     

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.     

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.     

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.     

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.     

Constrained curve drawing using trigonometric splines having shape parameters

The problem of drawing a smooth obstacle avoiding curve has attracted the attention of many people working in the area of CAD/CAM and its applications. In the present paper we propose a method of constrained curve drawing using certain C¹-quadratic trigonometric splines having shape parameters, which have been recently introduced in [Han X. Quadratic trigonometric polynomial curves with a shape parameter. Computer Aided Geometric Design 2002;19:503–12]. Besides this, we have also presented a simpler approach for studying the approximation properties of the trigonometric spline curves.     

A note on planar minimax arc splines

Arc splines are planar, tangent continuous, piecewise curves made of circular arcs and straight line segments. They are important because they can be used as the cutting paths for numerically controlled cutting machinery. This paper presents an algorithm for finding an arc spline that is a minimax approximation to discrete data.     

Optimal arc spline approximation

We present a method for approximating a point sequence of input points by a G¹$G^1$-continuous (smooth) arc spline with the minimum number of segments while not exceeding a user-specified tolerance. Arc splines are curves composed of circular arcs and line segments (shortly: segments). For controlling the tolerance we follow a geometric approach: We consider a simple closed polygon P and two disjoint edges designated as the start s and the destination d. Then we compute a SMAP (smooth minimum arc path), i.e. a smooth arc spline running from s to d in P with the minimally possible number of segments. In this paper we focus on the mathematical characterization of possible solutions that enables a constructive approach leading to an efficient algorithm.     

Analysis of switched quantizer based on the quadratic spline functions

In this paper, an approximation of the optimal compressor function using the quadratic spline functions with 2L?=?8 segments is described. Since the quadratic spline with 2L?=?8 segments provides better approximation of the optimal compression function than quadratic spline with 2L?=?4 segments, capitalizing on the benefits of the obtained spline approximation, quantizer designing process is firstly performed for the so assumed number of segments and the Laplacian source of a unit variance. Then, to enhance the usability of the proposed model, the switched quantization technique is applied and a beneficial analysis is derived, providing insight in the robustness of the proposed quantizer performances with respect to the mismatch in designed for and applied to variances. Reached quality has been compared to another model from the literature, and it has been shown that the proposed model outperforms the previous model by almost 1.3?dB.     

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.     

双曲抛物面上的一类G2连续逼近样条

在双曲抛物面上,仿射坐标系下,通过带逼近控制因子的双参数化方法,以及研究其参数间的函数关系构造出一类G2连续样条曲线。当控制多边形是平形四边形时,样条曲线段在逼近控制因子大于某个数时具有保形性质。对这类样条曲线段的逼近问题进行了一定的理论分析。     

Rational bi‐cubic G2 splines for design with basic shapes

The paper develops a rational bi‐cubic G² (curvature continuous) analogue of the non‐uniform polynomial C² cubic B‐spline paradigm. These rational splines can exactly reproduce parts of multiple basic shapes, such as cyclides and quadrics, in one by default smoothly‐connected structure. The versatility of this new tool for processing exact geometry is illustrated by conceptual design from basic shapes.     

On ℋ︁∞ model reduction for discrete‐time linear time‐invariant systems using linear matrix inequalities

In this paper, we address the ??_∞ model reduction problem for linear time‐invariant discrete‐time systems. We revisit this problem by means of linear matrix inequality (LMI) approaches and first show a concise proof for the well‐known lower bounds on the approximation error, which is given in terms of the Hankel singular values of the system to be reduced. In addition, when we reduce the system order by the multiplicity of the smallest Hankel singular value, we show that the ??_∞ optimal reduced‐order model can readily be constructed via LMI optimization. These results can be regarded as complete counterparts of those recently obtained in the continuous‐time system setting.     

Optimal polygonal approximation of digitized curves using the sum of square deviations criterion

We address the problem of finding an optimal polygonal approximation of digitized curves. Several optimal algorithms have already been proposed to determine the minimum number of points that define a polygonal approximation of the curve, with respect to a criterion error. We present a new algorithm with reasonable complexity to determine the optimal polygonal approximation using the mean square error norm. The idea is to estimate the remaining number of segments and to integrate the cost in the A^* algorithm. The solution is optimal in the minimum number of segments.     

二次Bézier曲线的双圆弧样条插值二分算法

在数控加工领域,通常需要用尽量少段数的圆弧样条来对曲线进行拟合。采用二分查找算法,用G1连续的双圆弧样条对二次Bézier曲线进行拟合。该算法在给定误差范围内所需的圆弧段数较少。最后给出了具体的实例说明。     

Approximation and estimation bounds for free knot splines

The fitting to data by splines has long been known to improve dramatically if the knots can be adjusted adaptively. To demonstrate the quality of the obtained free knot spline, it is essential to characterize its generalization ability. By utilizing the powerful techniques of the empirical process and approximation theory to address the estimation and approximation error bounds, respectively, the generalization ability of the free knot spline learning strategy is successfully characterized. We show that the Pseudo-dimension of free knot splines is essentially a linear function of the number of knots. A class of rather general loss functions is considered here and the squared loss is specially treated for its excellent property. We also provide some numerical results to demonstrate the utility of these theoretical results in guiding the process of choosing the appropriate knot numbers through the training data to avoid the overfitting/underfitting problem.     

C2 interpolation of spatial data subject to arc-length constraints using Pythagorean–hodograph quintic splines

In order to reconstruct spatial curves from discrete electronic sensor data, two alternative C² Pythagorean–hodograph (PH) quintic spline formulations are proposed, interpolating given spatial data subject to prescribed constraints on the arc length of each spline segment. The first approach is concerned with the interpolation of a sequence of points, while the second addresses the interpolation of derivatives only (without spatial localization). The special structure of PH curves allows the arc-length conditions to be expressed as algebraic constraints on the curve coefficients. The C² PH quintic splines are thus defined through minimization of a quadratic function subject to quadratic constraints, and a close starting approximation to the desired solution is identified in order to facilitate efficient construction by iterative methods. The C² PH spline constructions are illustrated by several computed examples.     

Sparse Non‐rigid Registration of 3D Shapes

Non‐rigid registration of 3D shapes is an essential task of increasing importance as commodity depth sensors become more widely available for scanning dynamic scenes. Non‐rigid registration is much more challenging than rigid registration as it estimates a set of local transformations instead of a single global transformation, and hence is prone to the overfitting issue due to underdetermination. The common wisdom in previous methods is to impose an ?₂‐norm regularization on the local transformation differences. However, the ?₂‐norm regularization tends to bias the solution towards outliers and noise with heavy‐tailed distribution, which is verified by the poor goodness‐of‐fit of the Gaussian distribution over transformation differences. On the contrary, Laplacian distribution fits well with the transformation differences, suggesting the use of a sparsity prior. We propose a sparse non‐rigid registration (SNR) method with an ?₁‐norm regularized model for transformation estimation, which is effectively solved by an alternate direction method (ADM) under the augmented Lagrangian framework. We also devise a multi‐resolution scheme for robust and progressive registration. Results on both public datasets and our scanned datasets show the superiority of our method, particularly in handling large‐scale deformations as well as outliers and noise.