ABSTRACT

In this article, the objective is to introduce an algorithm to produce the quaternary m-point (for any integer) approximating subdivision schemes, which have smaller support and higher smoothness, comparing to binary and ternary schemes. The proposed algorithm has been derived from uniform B-spline basis function using the Cox-de Boor recursion formula. In order to determine the convergence and smoothness of the proposed schemes, the Laurent polynomial method has been used.

1. Introduction

Until a few years ago all the work in the area of univariate subdivision was limited to consider just binary (Chaikin [1]; Dyn et al. [2,3]; Siddiqi and Younis [4]; Beccari et al. [5]) and ternary (Hassan and Dodgson [6]; Hassan et al. [7]; Ko et al. [8]; Mustafa et al. [9]) scenarios. In recent time, some proposals of quaternary subdivision schemes have introduced new interest in the era of subdivision, showing the possibility of treating refinement schemes with arity other than two or three.

Since subdivision schemes propose efficient iterative algorithms to produce the smooth curves and surfaces from a discrete set of control points by subdividing them according to some refining rules, recursively. These refining rules are very helpful and useful for the creation of smooth curves and surfaces in computational geometry and geometric designing due to their wide range of applications in many areas like engineering, medical science and image processing etc.

In this article an algorithm has been introduced to produce the quaternary point (for any integer) approximating subdivision schemes. This algorithm has been developed using the Cox-de Boor recursion formula, in the form of uniform B-spline blending functions to produce piecewise polynomials of order over the interval (for detail, see Section 2).

The quaternary subdivision scheme can be defined in terms of a mask consisting of a finite set of non-zero coefficients as follows

The formal definitions and the notion for the convergence analysis of the quaternary subdivision scheme are as follows:

The quaternary convergent subdivision scheme with the corresponding mask necessarily satisfies

It follows that the symbol of a convergent subdivision scheme satisfies the conditions andfor.

Introducing a symbol called the Laurent polynomial

of a mask with finite support. In view of Dyn [3], the sufficient and necessary conditions for a uniform convergent scheme are defined as follows.

A subdivision scheme is uniform convergent if and only if there is an integer, such that

subdivision with symbol is related to S with symbol, where and satisfying the property

where and

The norm

of a subdivision scheme with a mask is defined by

and

where

where

and

The paper is organized as follows, in Section 2 the algorithm to construct -point (for any integer) quaternary schemes has been introduced. Three examples are considered to produce the masks of 2-point (corner cutting), 3-point and 4-point schemes in the same section. In Section 3, the polynomial reproduction property has been discussed. The conclusion is drawn in Section 4.

2. Construction of the Algorithm

In this section, an algorithm has been constructed to produce the quaternary -point approximating subdivision schemes using the uniform B-spline basis functions and the Cox-de Boor recursion relation. The Cox-de Boor recursion relation, in view of Buss [10], can be defined as follows:

The recursion relation is the generalization to B-spline of degree (or of order, i.e.,). For this, consider to be a set of non-decreasing real numbers in such a way that. The values’s, not necessarily uniformly spaced, are called knots of non-uniform spline and the set is called knot vector. The uniform B-splines are just the special case of non-uniform B-splines in which the knots are equally spaced such that is a constant for (i.e.,) . Note that the blending functions of order depend only on the knot positions and are defined by induction on as follows.

First, for let

Second for. Setting, is defined by the Cox-de Boor formula as,

(1)

The form of above recursive formulas for the blending function immediately implies that the functions are piecewise polynomials of degree and that the breaks between pieces occur at the knots.

In view of above recursion formula, the Uniform Bspline blending functions of order over the interval, together with the properties [10], can be defined in Equation (2).

The blending functions must satisfy the following properties:

• The blending functions are translates of each other, that is,.

• The blending functions are a partition of unity, that is,.

• for all t.

• The functions have continuous derivatives, that is, they are -continuous.

(2)

The masks of the proposed quaternary -point scheme can be calculated using the following recurrence relation

(3)

where is a uniform B-spline basis function of degree. In the following, some examples are considered to produce the masks of 2-point, 3-point and 4-point quaternary approximating schemes after setting and 4, respectively, in recurrence relation (3).

The 2-point scheme: To obtain the mask of quarternary 2-point scheme, set in above relation (3). It may be noted that the linear uniform B-spline basis function produces the mask of 2-point quarternary scheme (which is also called corner cutting scheme). Thus 2-point scheme (after adjusting the mask) to refine the control polygon is defined as follows:

(4)

Now, the convergence and smoothness of the proposed 2-point scheme can be analyzed using the Laurent polynomial method introduced by Tang et al. [11].

Theorem 2.1: The quaternary 2-point approximating subdivision scheme converges and has smoothness.

Proof. To prove that the subdivision scheme corresponding to the symbol is. So, the Laurent polynomial for the mask of the scheme can be written as

(5)

The Laurent polynomial method is used to prove the smoothness of the scheme to be. Taking

where

and

With a choice of and, it can be written as

Since the norm of subdivision is

therefore is contractive, by Theorem 3, and so

is convergent.

In order to prove the scheme developed to be, consider and; it can be written as

Since the norm of subdivision is

therefore is contractive. Consequently, is convergent and.

The 3-point scheme: To obtain the mask of quarternary univariate 3-point scheme, set in recursion relation (3). The quadratic uniform B-spline basis functions are obtained. The mask of the proposed quaternary 3-point scheme can be calculated from these basis functions. The 3-point scheme (after adjusting the mask), to refine the control polygon, is defined as:

(6)

Theorem 2.2: The quaternary 3-point approximating subdivision scheme converges and has smoothness.

Proof. The smoothness of the above subdivision scheme can be calculated following the same procedure.

The 4-point scheme: Now, a 4-point quaternary scheme is presented and masks of the scheme can be calculated from the cubic basis function. After setting in relation (3) the cubic B-spline basis functions can be calculated. Thus, 4-point scheme is defined as follows

(7)

Theorem 2.3: The quaternary 4-point approximating subdivision scheme converges and has smoothness.

Proof. The smoothness of the above subdivision scheme can be calculated following the same procedure.

In the following section the polynomial reproduction property has been discussed.

3. Properties

The polynomial reproduction property has its own importance. As, the reproduction property of the polynomials up to certain degree implies that the scheme has approximation order. For this, polynomial reproduction can be made from initial date which has been sampled from some polynomial function. In view of [12], the polynomial reproduction property of the proposed scheme can be obtained after having the parametrization and definitions in the following manner.

Definition 3.1: For quaternary subdivision scheme the parametrization the corresponding parametric shift and attach the data for to the parameter values

(8)

Definition 3.2: A quaternary subdivision scheme reproduces polynomial of degree if it is convergent and its continuous limit function (for any polynomial) is equal to and initial data

Theorem 3.3: A convergent quaternary subdivision scheme reproduces polynomials of degree with respect to the parametrization defined in (8) if and only if

Proof. The induction over can be performed to prove this theorem following [12].

In view of [12], the following proposition helps to find the necessary conditions defined in (9).

Proposition 3.4: Let and. Then a subdivision symbol satisfies

(9)

if and only if satisfies

(3)

(derivative of the symbol) which in turn is equivalent to require that for some c(z).

Proposition 3.5: Let a quaternary subdivision scheme that reproduces polynomial up to degree. Then the smoothed scheme with the symbol

satisfies the conditions

and hence generates polynomial of degree, but it has only linear reproduction.

Proof. Following [12], for some Laurent polynomial

with, we have

and the fact. Thus, the derivative of is

and correct parametric shift for is

The derivative of is

which produces

after simplification, it can be yielded that

.

Hence, it does not reproduce polynomials of degree.

4. Conclusion

A quaternary univariate point (for any integer) approximating subdivision scheme has been developed which generates the smooth limiting curves. The construction of the quaternary scheme is associated with an algorithm of uniform B-spline basis functions developed from the Cox-de Boor recursion formula. The objective is to introduce the quaternary subdivision schemes, which have smaller support and higher smoothness, comparing to binary and ternary schemes. Moreover the polynomial reproduction property has also been discussed.

REFERENCES