Polynomial-based non-uniform interpolatory subdivision with features control

Starting from a well-known construction of polynomial-based interpolatory 4-point schemes, in this paper we present an original affine combination of quadratic polynomial samples that leads to a non-uniform 4-point scheme with edge parameters. This blending-type formulation is then further generalized to provide a powerful subdivision algorithm that combines the fairing curve of a non-uniform refinement with the advantages of a shape-controlled interpolation method and an arbitrary point insertion rule. The result is a non-uniform interpolatory 4-point scheme that is unique in combining a number of distinctive properties. In fact it generates visually-pleasing limit curves where special features ranging from cusps and flat edges to point/edge tension effects may be included without creating undesired undulations. Moreover such a scheme is capable of inserting new points at any positions of existing intervals, so that the most convenient parameter values may be chosen as well as the intervals for insertion.Such a fully flexible curve scheme is a fundamental step towards the construction of high-quality interpolatory subdivision surfaces with features control.     

Exponentials Reproducing Subdivision Schemes

This paper is concerned with a family of nonstationary, interpolatory subdivision schemes that have the capability of reproducing functions in a finite-dimensional subspace of exponential polynomials. We give conditions for the existence and uniqueness of such schemes, and analyze their convergence and smoothness. It is shown that the refinement rules of an even-order exponentials reproducing scheme converge to the Dubuc—Deslauriers interpolatory scheme of the same order, and that both schemes have the same smoothness. Unlike the stationary case, the application of a nonstationary scheme requires the computation of a different rule for each refinement level. We show that the rules of an exponentials reproducing scheme can be efficiently derived by means of an auxiliary orthogonal scheme , using only linear operations. The orthogonal schemes are also very useful tools in fitting an appropriate space of exponential polynomials to a given data sequence.     

Subdivision Schemes of Sets and the Approximation of Set-Valued Functions in the Symmetric Difference Metric

In this work we construct subdivision schemes refining general subsets of ? ⁿ and study their applications to the approximation of set-valued functions. Differently from previous works on set-valued approximation, our methods are developed and analyzed in the metric space of Lebesgue measurable sets endowed with the symmetric difference metric. The construction of the set-valued subdivision schemes is based on a new weighted average of two sets, which is defined for positive weights (corresponding to interpolation) and also when one weight is negative (corresponding to extrapolation). Using the new average with positive weights, we adapt to sets spline subdivision schemes computed by the Lane–Riesenfeld algorithm, which requires only averages of pairs of numbers. The averages of numbers are then replaced by the new averages of pairs of sets. Among other features of the resulting set-valued subdivision schemes, we prove their monotonicity preservation property. Using the new weighted average of sets with both positive and negative weights, we adapt to sets the 4-point interpolatory subdivision scheme. Finally, we discuss the extension of the results obtained in metric spaces of sets, to general metric spaces endowed with an averaging operation satisfying certain properties.     

A geometric approach for Hermite subdivision

We present a non-stationary, non-uniform scheme for two-point Hermite subdivision. The novelty of this approach relies on a geometric interpretation of the subdivision steps—related to generalized Bernstein bases—which permits to overcome the usually unavoidable analytical difficulties. The main advantages consist in extra smoothness conditions, which in turn produce highly regular limit curves, and in an elegant structure of the subdivision—described by three de Casteljau type matrices. As a by-product, the scheme is inherently shape preserving.     

Modified form of binary and ternary 3-point subdivision schemes

Binary 3-point scheme, developed by Hormann and Sabin [Hormann, K. and Sabin, Malcolm A., 2008, A family of subdivision schemes with cubic precision, Computer Aided Geometric Design, 25, 41-52], has been modified by introducing a tension parameter which generates a family of C¹ limiting curves for certain range of tension parameter. Ternary 3-point scheme, introduced by Siddiqi and Rehan [Siddiqi, Shahid S. and Rehan, K., 2009, A ternary three point scheme for curve designing, International Journal of Computer Mathematics, In Press, DOI: 10.1080/00207160802428220], has also been modified by introducing a tension parameter which generates family of C¹ and C² limiting curves for certain range of tension parameter. Laurent polynomial method is used to investigate the continuity of the subdivision schemes. The performance of modified schemes has been demonstrated by considering different examples along with its comparison with the established subdivision schemes.     

Stationary binary subdivision schemes using radial basis function interpolation

A new family of interpolatory stationary subdivision schemes is introduced by using radial basis function interpolation. This work extends earlier studies on interpolatory stationary subdivision schemes in two aspects. First, it provides a wider class of interpolatory schemes; each 2L-point interpolatory scheme has the freedom of choosing a degree (say, m) of polynomial reproducing. Depending on the combination (2L,m), the proposed scheme suggests different subdivision rules. Second, the scheme turns out to be a 2L-point interpolatory scheme with a tension parameter. The conditions for convergence and smoothness are also studied. Dedicated to Prof. Charles A. Micchelli on the occasion of his 60th birthday Mathematics subject classifications (2000) 41A05, 41A25, 41A30, 65D10, 65D17. Byung-Gook Lee: This work was done as a part of Information & Communication fundamental Technology Research Program supported by Ministry of the Information & Communication in Republic of Korea. Jungho Yoon: Corresponding author. Supported by the Korea Science and Engineering Foundation grant (KOSEF R06-2002-012-01001).     

An ideal spline-wavelet family for curve design and editing

Subdivision schemes provide the most efficient and effective way to design and render smooth spatial curves. It is well known that among the most popular schemes are the de Rham–Chaikin and Lane–Riesenfeld subdivision schemes, that can be readily formulated by direct applications of the two-scale (or refinement) sequences of the quadratic and cubic cardinal B-splines, respectively. In more recent works, semi-orthogonal and bi-orthogonal spline-wavelets have been integrated to curve subdivision schemes to add such powerful tools as automatic level-of-detail control algorithm for curve editing and rendering, and efficient simulation processing scheme for global graphic illumination and animation. The objective of this paper is to introduce and construct a family of spline-wavelets to overcome the limitations of semi-orthogonal and bi-orthogonal spline-wavelets for these and other applications, by adding flexibility to the enhancement of desirable characters without changing the sweep of the subdivision spline curve, by providing the shortest lowpass and highpass filter pairs without decreasing the discrete vanishing moments, and by assuring robust stability.     

Bivariate interpolation based on univariate subdivision schemes

The paper presents a bivariate subdivision scheme interpolating data consisting of univariate functions along equidistant parallel lines by repeated refinements. This method can be applied to the construction of a surface passing through a given set of parametric curves. Following the methodology of polysplines and tension surfaces, we define a local interpolator of four consecutive univariate functions, from which we sample a univariate function at the mid-point. This refinement step is the basis to an extension of the 4-point subdivision scheme to our setting. The bivariate subdivision scheme can be reduced to a countable number of univariate, interpolatory, non-stationary subdivision schemes. Properties of the generated interpolant are derived, such as continuity, smoothness and approximation order.     

Multivariate refinable Hermite interpolant

We introduce a general definition of refinable Hermite interpolants and investigate their general properties. We also study a notion of symmetry of these refinable interpolants. Results and ideas from the extensive theory of general refinement equations are applied to obtain results on refinable Hermite interpolants. The theory developed here is constructive and yields an easy-to-use construction method for multivariate refinable Hermite interpolants. Using this method, several new refinable Hermite interpolants with respect to different dilation matrices and symmetry groups are constructed and analyzed.

Some of the Hermite interpolants constructed here are related to well-known spline interpolation schemes developed in the computer-aided geometric design community (e.g., the Powell-Sabin scheme). We make some of these connections precise. A spline connection allows us to determine critical Hölder regularity in a trivial way (as opposed to the case of general refinable functions, whose critical Hölder regularity exponents are often difficult to compute).

While it is often mentioned in published articles that ``refinable functions are important for subdivision surfaces in CAGD applications", it is rather unclear whether an arbitrary refinable function vector can be meaningfully applied to build free-form subdivision surfaces. The bivariate symmetric refinable Hermite interpolants constructed in this article, along with algorithmic developments elsewhere, give an application of vector refinability to subdivision surfaces. We briefly discuss several potential advantages offered by such Hermite subdivision surfaces.

     

Analysis of stationary subdivision schemes for curve design based on radial basis function interpolation

This paper provides a large family of interpolatory stationary subdivision schemes based on radial basis functions (RBFs) which are positive definite or conditionally positive definite. A radial basis function considered in this study has a tension parameter λ>0 such that it provides design flexibility. We prove that for a sufficiently large , the proposed 2L-point (L∈N) scheme has the same smoothness as the well-known 2L-point Deslauriers-Dubuc scheme, which is based on 2L-1 degree polynomial interpolation. Some numerical examples are presented to illustrate the performance of the new schemes, adapting subdivision rules on bounded intervals in a way of keeping the same smoothness and accuracy of the pre-existing schemes on R. We observe that, with proper tension parameters, the new scheme can alleviate undesirable artifacts near boundaries, which usually appear to interpolatory schemes with irregularly distributed control points.     

Quasi-interpolatory refinable functions and construction of biorthogonal wavelet systems

We present a new family of compactly supported and symmetric biorthogonal wavelet systems. Each refinement mask in this family has tension parameter ω. When ω = 0, it becomes the minimal length biorthogonal Coifman wavelet system (Wei et al., IEEE Trans Image Proc 7:1000–1013, 1998). Choosing ω away from zero, we can get better smoothness of the refinable functions at the expense of slightly larger support. Though the construction of the new biorthogonal wavelet systems, in fact, starts from a new class of quasi-interpolatory subdivision schemes, we find that the refinement masks accidently coincide with the ones by Cohen et al. (Comm Pure Appl Math 45:485–560, 1992, §6.C) (or Daubechies 1992, §8.3.5), which are designed for the purpose of generating biorthogonal wavelets close to orthonormal cases. However, the corresponding mathematical analysis is yet to be provided. In this study, we highlight the connection between the quasi-interpolatory subdivision schemes and the masks by Cohen, Daubechies and Feauveau, and then we study the fundamental properties of the new biorthogonal wavelet systems such as regularity, stability, linear independence and accuracy.     

A family of non-oscillatory 6-point interpolatory subdivision schemes

In this paper we propose and analyze a new family of nonlinear subdivision schemes which can be considered non-oscillatory versions of the 6-point Deslauries-Dubuc (DD) interpolatory scheme, just as the Power _p schemes are considered nonlinear non-oscillatory versions of the 4-point DD interpolatory scheme. Their design principle may be related to that of the Power _p schemes and it is based on a weighted analog of the Power _p mean. We prove that the new schemes reproduce exactly polynomials of degree three and stay ’close’ to the 6-point DD scheme in smooth regions. In addition, we prove that the first and second difference schemes are well defined for each member of the family, which allows us to give a simple proof of the uniform convergence of these schemes and also to study their stability as in [19, 22]. However our theoretical study of stability is not conclusive and we perform a series of numerical experiments that seem to point out that only a few members of the new family of schemes are stable. On the other hand, extensive numerical testing reveals that, for smooth data, the approximation order and the regularity of the limit function may be similar to that of the 6-point DD scheme and larger than what is obtained with the Power _p schemes.     

Stability of Manifold-Valued Subdivision Schemes and Multiscale Transformations

Linear subdivision schemes can be adapted in various ways so as to operate in nonlinear geometries such as Lie groups or Riemannian manifolds. It is well known that along with a linear subdivision scheme a multiscale transformation is defined. Such transformations can also be defined in a nonlinear setting. We show the stability of such nonlinear multiscale transforms. To do this we introduce a new kind of proximity condition which bounds the difference of the differential of a nonlinear subdivision scheme and a linear one. It turns out that—unlike the generic nonlinear case and modulo some minor technical assumptions—in the manifold-valued setting, convergence implies stability of the nonlinear subdivision scheme and associated nonlinear multiscale transformations.     

A constructive algebraic strategy for interpolatory subdivision schemes induced by bivariate box splines

This paper describes an algebraic construction of bivariate interpolatory subdivision masks induced by three-directional box spline subdivision schemes. Specifically, given a three-directional box spline, we address the problem of defining a corresponding interpolatory subdivision scheme by constructing an appropriate correction mask to convolve with the three-directional box spline mask. The proposed approach is based on the analysis of certain polynomial identities in two variables and leads to interesting new interpolatory bivariate subdivision schemes.     

Commutation for Irregular Subdivision

We present a generalization of the commutation formula to irregular subdivision schemes and wavelets. We show how, in the noninterpolating case, the divided differences need to be adapted to the subdivision scheme. As an example we include the construction of an entire family of biorthogonal compactly supported irregular knot B-spline wavelets starting from Lagrangian interpolation. September 4, 1998. Date revised: July 27, 1999. Date accepted: November 16, 2000.     

A ternary 4-point approximating subdivision scheme

In the implementation of subdivision scheme, three of the most important issues are smoothness, size of support, and approximation order. Our objective is to introduce an improved ternary 4-point approximating subdivision scheme derived from cubic polynomial interpolation, which has smaller support and higher smoothness, comparing to binary 4-point and 6-point schemes, ternary 3-point and 4-point schemes (see Table 2). The method is easily generalized to ternary (2n + 2)-point approximating subdivision schemes. We choose a ternary scheme because a way to get smaller support is to raise arity. And we use polynomial reproduction to get higher approximation order easily.     

Nonlinear Subdivision Schemes on Irregular Meshes

The present article deals with convergence and smoothness analysis of geometric, nonlinear subdivision schemes in the presence of extraordinary points. We discuss when the existence of a proximity condition between a linear scheme and its nonlinear analogue implies convergence of the nonlinear scheme (for dense enough input data). Furthermore, we obtain C ¹ smoothness of the nonlinear limit function in the vicinity of an extraordinary point over Reif’s characteristic parametrization. The results apply to the geometric analogues of well-known subdivision schemes such as Doo–Sabin or Catmull–Clark schemes.     

Error bounds for a class of subdivision schemes based on the two-scale refinement equation

Subdivision schemes are iterative procedures for constructing curves and constitute fundamental tools in computer aided design. Starting with an initial control polygon, a subdivision scheme refines the values computed in the previous step according to some basic rules. The scheme is said to be convergent if there exists a limit curve. The computed values define a control polygon in each step. This paper is devoted to estimating error bounds between the limit curve and the control polygon defined after k subdivision stages. In particular, a stop criterion of convergence is obtained. The refinement rules considered in the paper are widely used in practice and are associated with the well known two-scale refinement equation including as particular examples the schemes based on Daubechies’ filters. Our results generalize the previous analysis presented by Mustafa et al. in [G. Mustafa, F. Chen, J. Deng, Estimating error bounds for binary subdivision curves/surfaces, J. Comput. Appl. Math. 193 (2006) 596-613] and [G. Mustafa and M.S. Hashmi Subdivision depth computation for n-ary subdivision curves/surfaces, Vis. Comput. 26 (6-8) (2010) 841-851].     

Matrix-valued symmetric templates for interpolatory surface subdivisions: I. Regular vertices

The objective of this paper is to introduce a general procedure for deriving interpolatory surface subdivision schemes with “symmetric subdivision templates” (SSTs) for regular vertices. While the precise definition of “symmetry” will be clarified in the paper, the property of SSTs is instrumental to facilitate application of the standard procedure for finding symmetric weights for taking weighted averages to accommodate extraordinary (or irregular) vertices in surface subdivisions, a topic to be studied in a continuation paper. By allowing the use of matrices as weights, the SSTs introduced in this paper may be constructed to overcome the size barrier limited to scalar-valued interpolatory subdivision templates, and thus avoiding the unnecessary surface oscillation artifacts. On the other hand, while the old vertices in a (scalar) interpolatory subdivision scheme do not require a subdivision template, we will see that this is not the case for the matrix-valued setting. Here, we employ the same definition of interpolation subdivisions as in the usual scalar consideration, simply by requiring the old vertices to be stationary in the definition of matrix-valued interpolatory subdivisions. Hence, there would be another complication when the templates are extended to accommodate extraordinary vertices if the template sizes are not small. In this paper, we show that even for C² interpolatory subdivisions, only one “ring” is sufficient in general, for both old and new vertices. For example, for 1-to-4 split C² interpolatory surface subdivisions, we obtain matrix-valued symmetric interpolatory subdivision templates (SISTs) for both triangular and quadrilateral meshes with sizes that agree with those of the Loop and Catmull–Clark schemes, respectively. Matrix-valued SISTs of similar sizes are also constructed for C² interpolatory and subdivision schemes in this paper. In addition to small template sizes, an obvious feature of matrix-valued weights is the flexibility for introducing shape-control parameters. Another significance is that, in contrast to the usual scalar setting, matrix-valued SISTs can be formulated in terms of the coefficient sequence of some vector refinement equation of interpolating bivariate C² splines with small support. For example, by modifying the spline function vectors introduced in our previous work [C.K. Chui, Q.T. Jiang, Surface subdivision schemes generated by refinable bivariate spline function vectors, Appl. Comput. Harmon. Anal. 15 (2003) 147–162; C.K. Chui, Q.T. Jiang, Refinable bivariate quartic and quintic C²-splines for quadrilateral subdivisions, Preprint, 2004], C² symmetric interpolatory subdivision schemes associated with refinement equations of C² cubic and quartic splines on the 6-directional and 4-directional meshes, respectively, are also constructed in this paper.     

Analysis of subdivision schemes for nets of functions by proximity and controllability

In this paper we develop tools for the analysis of net subdivision schemes, schemes which recursively refine nets of bivariate continuous functions defined on grids of lines, and generate denser and denser nets. Sufficient conditions for the convergence of such a sequence of refined nets, and for the smoothness of the limit function, are derived in terms of proximity to a bivariate linear subdivision scheme refining points, under conditions controlling some aspects of the univariate functions of the generated nets. Approximation orders of net subdivision schemes, which are in proximity with positive schemes refining points are also derived. The paper concludes with the construction of a family of blending spline-type net subdivision schemes, and with their analysis by the tools presented in the paper. This family is a new example of net subdivision schemes generating C¹ limits with approximation order 2.