Statistical and Geometrical Way of Model Selection for a Family of Subdivision Schemes?

Ghulam MUSTAFA

1 Introduction

In[6],Deslauriers and Dubuc introduced a family of 2m-point n-ary subdivision schemes,that is,at each subdivision level the scheme uses 2m-point(called complexity of scheme)to compute new n points(called arity of scheme or n-ary)corresponding to each edge of the course control polygon/initial model.If the subdivision rules are represented by the operator S,the process has the formApplying S to an initial model f0yields a sequence of models, ···.If these rules are chosen carefully,the limit of this process is a smooth curve/modelthat approximates the coarse model f0.

A general increasing interest for investigating higher arity and complexity has emerged since then to achieve smoother curves,higher approximation order and small support etc.,by going from binary(i.e.,2-ary)to n-ary.The generalization of the binary schemes to high arity and complexity schemes has been proposed in the last few years[2–3,9–11,13–15,18–19].

Early work in the subdivision curves does not deal with noisy data and the related problem of over fitting.In the current practice,the comparison among the schemes is based on their known properties such as degree of smoothness,size of the support and degree of polynomial reproduction etc.The need to use a statistical way of selecting the appropriate subdivision scheme from the class of different arity and complexity schemes for a given noisy and data without noise modeling problem has not arisen yet.However,an initiative has been taken in this regard by Mustafa and Ivrissimtzis[16].A very recent paper[12]handled noisy curve/surface data with outliers.It removes noises and outliers without any prior information about the input data.

In this paper,we introduce a new family of curve subdivision schemes with mask of size m and arity n and study their properties.We also study the use of the proposed schemes as modeling tools and show how statistical and geometrical techniques can be used to select the appropriate subdivision scheme for a given modeling task.To facilitate the selection of the appropriate complexity and arity schemes for a given data(noisy and free from noise)modeling problem,we propose and compute real error,training error,average absolute curvature,residual sum of squares(RSS,for short)values and absolute discrete total curvature,as well as traditional properties(degree of the smoothness,H¨older regularity,size of the support and degree of polynomial reproduction)of the schemes.Experimental results show that the different arity and complexity schemes exhibit differently for noisy and data without noise.

This paper is organized as follows:In Section 2,we introduce a generalized algorithm to produce a family of approximating schemes derived from uniform B-spline blending functions.We also discuss its affine variance property and support size in this section.In Section 3,we give the intrinsic comparison of the member of family of schemes by statistical methods for the model assessment and selection.In Section 4,geometrical properties of the family of schemes are discussed for model selection and assessment.Finally,in Section 5 the comprehensive conclusion is presented.

2 Generalized Scheme

In this section,we introduce a generalized family of m-point n-ary approximating subdivision schemes using the uniform B-spline blending functions and the Cox-de Boor recursion relation.

If m represents the complexity of the scheme(i.e.,the number of points involved to insert/update the point)and n represents the arity of subdivision scheme,then our purposed m-point n-ary approximating subdivision scheme which maps a polygonrefined polygonis defined by

2.1 Affine invariance

The subdivision curve is affine invariant if the coordinate system of the curve can be changed without affecting the relative geometry of the curve.This can be seen by the fact that the geometry of the curve remains consistent when the curve is rotated,scaled,or translated.This is equivalent to say that the sum of mask coefficients of the scheme is one.In the following proposition,we see that the curves generated by proposed schemes hold the affine invariance property.

Figure 1 Effect of the non-zero vertex propagated on both sides of the vertex.

Here we see that the superscripts of variable z in above polynomial is a(5?0)=(3×2?1)-long sequence(i.e.,0,1,2,3,4,5).So in our context,we can say that the maskof 3-point 2-ary scheme is a(3×2?1)-long sequence.Similarly,we can say that the maskof m-point n-ary scheme is an(mn?1)-long sequence.In the coming section,we compute the support width of a family of schemes by using the approach of Beccari et al.[4].

2.2 Support of the family of schemes

The other basic property is the support of family of schemes,that is,the area of the subdivision curve that will be affected by the displacement of a single control point.In order to study the support of scheme,it is sufficient to discuss the support of its basic function.Since the basic function is the limit function of the scheme corresponding to mask(2.2)for the dataotherwiseits support width(SW,for short)can be determined by computing the effect of the non-zero vertexpropagated on both sides of the vertex

The mask of m-point n-ary scheme is an mn?1 long sequence by centering it on that vertex—the distances to the last of its left and right non-zero coefficients are equal toThis phenomena is explained in Figure 1.At the first subdivision step,the vertices on the both sides ofare the furthest non-zero new vertices.At each refinement,the distances on both sides are reduced by the factorAt the next step of the scheme,this will propagate alongon both sides.Hence,after k subdivision steps,the furthest non-zero vertex on the left will be atSo the total support width isThis implies that the basic limit functions of proposed family of m-point n-ary approximating schemes have support widthThat is,the area of the curve over the intervalwill be affected by moving a single control point of the polygon.

Here we summarize the above discussion:In Table 1,we present complexity,arity,support,and the maskof few schemes generated by our proposed mask(2.2).We have the following judgement keeping in the view of Figure 2 and Table 1:The support width may decrease(increase)with the increase of arity(complexity)of the schemes.

Table 1 Complexity,arity,support and mask of the schemes corresponding to different values of m,here m shows complexity of the schemes(i.e.,2-,3-,···-point schemes),while n,SW and anmstand for arity,support width and mask of the schemes respectively.

Figure 2(a)Represents the graph of support of the scheme with variable arity and fixed complexity.(b)Represents the graph of support with variable complexity and fixed arity.

In coming sections,we give the intrinsic comparison of the member of family of schemes by statistical and traditional methods for model assessment and selection(MAS,for short).

3 Statistical Way of MAS

In this section,we numerically compute training errors,average absolute curvatures,residual sum of squares and absolute discrete total curvatures of the limiting curves(i.e.models)generated by the members of family of schemes.

3.1 Training error

Given an initial/input data,we fit a subdivision curve on it by using the input data(i.e.,training data)as the initial control polygon.The simplicity of the model fitting process is justified by the fact that the family of subdivision curves we work with is large and diverse.That means that we can expect to obtain satisfactory models through the assessment and selection process over the family,without needing a complicated algorithm to fi t subdivision curves to the initial data.The error of the model on a certain point is the distance between that point and the limit subdivision curve.The average error of the model on the training data itself is called training error(TE,for short),of the model.

In our experiments on model assessment and selection,we first measure the real error,that is,the error between the two models generated with and without added noise,and compare it with the training error.We have the following results for fixed complexity(arity)and variable arity(complexity)of the schemes:

(1)High arity(complexity)schemes may have less(greater)training and real errors than low arity(complexity)schemes for initial data free from noise(see Figure 3(a)–(f)).

(2)High arity schemes may have less(greater)training(real)errors than low arity schemes for initial data with added noise(see Figure 4(a)–(f)).

(3)High complexity schemes may have less(greater)real(training)errors than low complexity schemes for initial data with added noise(see Figure 4(a)–(f)).

The use of the training error for model selection would result in over fitted models(see Figure 5).Since 2-point quaternary and senary schemes have less training errors than 2-point binary scheme so these schemes causes over fitting.

3.2 Average absolute curvature

Furthermore,we have computed the average absolute curvature at a sufficiently refined control polygon(originated from with and without noisy polygon)as the average absolute curvature over all vertices.The absolute value of the curvature at a vertex is computed as the inverse of the radius of the circle interpolating that vertex and its left and right neighbours at the control polygon.We have following finding:

(1)High arity(complexity)schemes may have less(greater)curvature than low arity(complexity)schemes for initial data free from noise(see Figure 3(g)–(i)).

(2)High arity(complexity)schemes may have greater(less)curvature than low arity(complexity)schemes for initial data with added noise(see Figure 4(g)–(i)).

(3)The curvature of high arity schemes may diverge with the increase of refinement levels for highly noisy data(see Figure 4(g)–(i)).

Figure 3 Comparison of real and training errors,curvature and RSS of the models generated by fixed complexity and variable arity of schemes without added noise.

Figure 4 Comparison of real and training errors,curvature and RSS of the models generated by fi xed complexity and variable arity of schemes with added noise.

Figure 5 Models with and without over fitting.

3.3 Residual sum of squares

If the absolute curvature is large,the scheme is more oscillatory and this produces curves with inferior geometric properties on this type of data.Thus,we need a sophisticated technique that control the trade-off between two conflicting properties(training error and average absolute curvature)for obtaining a more reliable assessment.That is,among all subdivision curves with two continuous derivatives, find one that minimizes the penalized residual sum of squares(see[8])

where λ is a fixed smoothing parameter.The first term measures closeness to the data(i.e.,training error in our case),penalizes bad fitting of the data from subdivision curves that are far away from the initial control polygon.Such bad fittings are usually the characteristic of high continuity schemes.The second term penalizes curvature(average absolute curvature in our case)i.e.,“l(fā)ow level of continuity” in the subdivision curve,which is the characteristic of interpolatory or near interpolatory schemes.The user parameter λ establishes a trade off between the two.Two special cases are:(1)λ=0:f∞can be any interpolating curve;(2)λ=∞:The simple least squares line fit,since no second derivative can be tolerated.These vary from very rough to very smooth,and the hope is that λ =(0,∞)indexes an interesting class of subdivision curves in between.

In statistics,RSS is a measure of the discrepancy between the data and an estimated model(limiting model in our case).A small RSS indicates a tight fit of the model to the data.It is used as an optimality criterion in parameter selection and model selection.In Figures 3–4,we demonstrate that the minimization of an RSS function can be used for the selection of appropriate subdivision scheme.We notice that:

(1)High arity(complexity)schemes may have less(greater)RSS value than low arity(complexity)schemes with fixed complexity(arity)for initial data free from noise.That is 5-point senary scheme is better than 5-point quinary,···,and 3-point n-ary schemes are better than 4-point n-ary schemes(see Figure 3(j)–(l)).

(2)RSS values grow suddenly for high arity schemes for noisy initial data at high level of iteration,but low arity and complexity schemes may have less RSS values than other schemes(see Figure 4(j)–(l)).

(3)In particular,3-point n-ary schemes for noisy data may give a smaller residual sum of square value than other schemes,depending of course on the selection of the value of λ(see Figure 4(j)–(l)).

The selection of the value of λ that is most suitable for the application at hand,is still an open question.In our experiments shown in this paper,we consider the closed polygonal curves defined by 25 and 5 points sampled from a circle with added noise and without noise respectively.We have experimented the methods on different polygons with different number of initial input data points and get the same results as shown above.We did not show their graphs/ figures for the clarity of the paper.

3.4 Absolute discrete total curvature

The above methods have more emphasis on statistical and less on geometric properties of the schemes.So here,we suggest the method of absolute discrete total curvature which has more emphasis on geometric and less on the statistical properties of the subdivision curve for the model selection and assessment.Thus,this approach is more suitable for design rather than data modeling applications.The discrete total curvature of a closed polygonal subdivision curve is the sum of exterior angles formed by the right and left tangents at the vertices of polygonal curve.Similarly,the sum of the absolute values of the exterior angles formed by the right and left tangents at the vertices of polygonal curve is the absolute discrete total curvature.For a detailed description and discussion of the properties of the discrete total curvature,see[1].

The discrete total curvature and the absolute discrete total curvature are the same for a closed convex polygonal curve and both are equal to 2π.Therefore for a non-convex subdivision curve the excess in the absolute discrete total curvature with respect to the discrete total curvature of the convex curve can be used as a measure of deviation from the property of convexity.

In Figure 6,we show the deviation of subdivision curves from convex polygonal curve.The non-convex curves we tested are refined subdivision polygons,produced by different subdivision schemes,with initial data taken from a circle with some added noise.From this figure,we have following finding:High arity(complexity)schemes may have greater(low)deviation from the property of convexity than low arity(complexity)schemes for initial non-convex data.

Now we present brief description of above statistical algorithms for the model selection and assessment.

Figure 6 The deviation of the subdivision schemes from convexity.

3.5 Outline of algorithm for statistical way of MAS

(1)Input:A family of subdivision schemes along with initial/original/training control polygon(i.e.,initial model)f0with data set

(2)Choose scheme from family of schemes:A subdivision scheme with the set of subdivision rules or subdivision matrix S to generate the subdivision curve(i.e.,limiting model)and the set of rules or matrix S∞to find the points on the limiting model.

(3)Training error(TE):Find the average of the distances between the initial model and the limiting model generated by the scheme selected from the family of schemes.

Prompt Response:If training error approaches zero,then the scheme causes over fitting.

(4)Average absolute curvature(κ):Compute the absolute value of the curvature at a vertex as the inverse of the radius of the circle interpolating that vertex and its left and right neighbours at the refined control polygon.

Prompt Response:If κ is small,the scheme is less oscillatory on this type of data.

(5)Residual sum of squares(RSS):For a fixed smoothing parameter λ,compute,RSS=TE+ λκ.

Prompt Response:A small RSS indicates a tight fit of the model to the data.

(6)Absolute discrete total curvature(ADTC):Compute ADTC,i.e.,compute the sum of the absolute values of the exterior angles formed by the right and left tangents at the vertices of the limiting curve.Then compute discrete total curvature(DTC).

Prompt Response:The excess in the ADTC with respect to the DTC gives a measure of deviation from the property of convexity.

(7)Output:Best subdivision scheme among the members of family of schemes.

4 Geometrical Way of MAS

Traditionally/geometrically,subdivision models are assessed on the basis of high degree of polynomial reproduction,approximation order,order of continuity and H¨older regularity of the schemes.So in this section,we brie fly discuss these properties for selection and assessment of subdivision models.

4.1 Polynomial reproduction and approximation order

In the view[5],the polynomial reproduction property of the scheme with Laurent polynomial a(z)can be obtained after having the parameterizationswith corresponding parametric shift and attached datato the parameter values

We observe that the first derivative of Laurent polynomial a(z)of odd-point odd-ary scheme at z=1 is zero,that is a(1)(1)=0.for odd integer n.This implies that odd-point odd-ary schemes have primal parametrization.This further implies that

So odd-point odd-ary schemes have reproduction degree one.Similarly,we see that even-point n-ary(any integer n)and odd-point even-ary schemes have reproduction degree one with dual parametrization.Since the degree of reproduction of the family of m-point n-ary schemes is one then by[7]its approximation order is two.The above discussion has been summarized in Table 2.

4.2 Continuity and H¨older continuity of the schemes

Continuity of a subdivision curve is defined by just saying that if the nth derivative of a curve exists everywhere in an interval and is continuous,then the curve is said to be Cncontinuous in that interval.But the H¨older continuity/regularity of a subdivision curve is a measure of how many derivatives are continuous,and of how continuous the highest continuous derivativeis.So we also need to find H¨older continuity of the schemes to further explore their properties.By following the methods of Dyn[7]and Rioul[17],the continuity and H¨older continuity of the proposed family of schemes can easily be computed and are shown in Table 2 with graphical representation in Figure 7.We have following findings:

Table 2 Comparison:Here m,n,OC,DR,P,and OA represent complexity,arity,order of continuity,degree of reproduction,parametrization,and order of approximation,respectively.

(1)The order of continuities of proposed schemes,in general,may increase(may not increase)by increasing the complexity(arity)of the schemes.

(2)H¨older continuities may increase(decrease)with the increase of complexity(arity)of the schemes.

(3)In general m-point scheme is at least Cm?1continuous.Particulary,our 4-point and 6-point binary schemes are C4and C6respectively.

Figure 7 Represents the graphs of H¨older continuities of the schemes

4.3 Visual performances and comparison

Here we present visual performances of different arity and complexity schemes.In Figure 8,we observe that the smoothness of the limit curves may increase(does not increase)with the increase of complexity(arity)of the schemes.This figure supports our finding in previous section that continuity increases(does not increase)with the increase of complexity(arity)of the schemes.In this figure,dotted lines are initial polygons while solid curves are obtained after sufficient refinements of initial polygons by using schemes with different arity and complexity.In Figures 8–9,we see that proposed family of schemes does not suffer from the Gibbs phenomenon oscillations while DD family of schemes(see[6]),and 4-point quaternary interpolating/approximating schemes of Ko[10]have Gibbs phenomenon oscillations.Amat and Liandrat[3]have already showed that 4-point quaternary scheme of Mustafa and Khan[15]suffer Gibbs phenomenon oscillations while the m-point quaternary approximating schemes(see[18])are the special case of our family of schemes so we do not present comparison with these schemes.

Figure 8 Visual performances of different arity and complexity proposed schemes.

Figure 9 Gibbs phenomenon exhibits by DD’s schemes and Ko’s scheme.Here pt means point.

5 Conclusion

The new family of m-point n-ary schemes are presented in this paper.In particular,we tested the statistical and geometrical(traditional)methods for the model selection and assessment for selecting a subdivision curve from the proposed family of schemes for modeling noisy and data without noise.We have concluded that in general:

(1)If the arity of scheme increases then training error,real error,curvature and RSS value of the scheme may decrease while these identities may increase with increase of complexity of the schemes for modeling data free from noise.

(2)If the arity of scheme increases then training error may decrease but real error,curvature and RSS value of the scheme may increase,while training error and RSS value may increase,but real error and curvature may decrease by the increase of complexity of the schemes for modeling data with some added noise.

(3)The deviation of subdivision curves from a convex polygonal curve may increase by the increase of arity,while it may decrease with the increase of complexity of the scheme.

(4)Continuity of the scheme may remain fix,but H¨older continuity may decrease with the increase of arity while both identities may increase with the increase of complexity of the schemes.Moreover,in general m-point scheme is at least Cm?1continuous.

(5)Even-point n-ary and odd-point even-ary schemes are dual while odd-point odd-ary schemes are primal.Moreover,the degree of reproduction of proposed family of scheme is two.

(6)Numerical study shows that proposed family of schemes is free from Gibbs oscillations.

Proposed statistical methods can also be used to compare the existing family of schemes in the literature.We did not present statistical comparisons with other existing schemes due to the space problem.The analytical comparison of Gibbs oscillations of proposed and existing family of subdivision schemes is possible future research directions.

AcknowledgementsThe author would like to thank the anonymous referee for his helpful suggestions and comments which have showed the way to improve this work.

[1]Alboul,L.,Echeverria,G.and Rodrigues,M.,Curvature Criteria to Fit Curves to Discrete Data,20th European Workshop on Computational Geometry,Seville,Spain,2004.

[2]Aslam,M.,Mustafa,G.and Ghaffar,A.,(2n?1)-point ternary approximating and interpolating subdivision schemes,Journal of Applied Mathematics,vol.2011,Article ID 8632630,2011,12 pages.

[3]Amat,S.and Liandrat,J.,On a nonlinear 4-point quaternary approximating subdivision schemes eliminating the Gibbs phenomenon,SeMA Journal,62,2013,15–25.

[4]Beccari,C.,Casiola,G.and Romani,L.,An interpolating 4-point C2ternary non-stationary subdivision scheme with tension control,Computer Aided Geometric Design,24(4),2007,210–219.

[5]Conti,C.and Hormann,K.,Polynomial reproduction for univariate subdivision scheme of any arity,Approximation Theory,163,2011,413–437.

[6]Deslauriers,G.and Dubuc,S.,Symmetric iterative interpolation processes,Constructive Approximation,5,1989,49–68.

[7]Dyn,N.,Tutorial on multiresolution in geometric modeling summer school lecture notes series,Mathematics and Visualization,Iske,A.,Quak,E.;Floater,Michael S.(Eds.)Springer-Verlag,2002.

[8]Hastie,T.,Tibshirani,R.and Friedman,J.,The Elements of Statistical Learning:Data Mining,Inference,and Prediction,Springer-Verlag,London,2002.

[9]Lian,J-A.,On a-ary subdivision for curve design:I.2m-point and(2m+1)-point interpolatory schemes,Applications and Applied Mathematics:An International Journal,4(1),2009,434–444.

[10]Ko,K.P.,A quaternary approximating 4-point subdivision scheme,The Journal of the Korean Society for Industrial and Applied Mathematics,13(4),2009,307–314.

[11]Mustafa,G.,Deng,J.,Ashraf,P.and Rehman,N.A.,The mask of odd points n-ary interpolating subdivision scheme,Journal of Applied Mathematics,Article ID 205863,2012,20 pages.

[12]Mustafa,G.,Li,H.,Zhang J.and Deng,J.,?1-Regression based subdivision schemes for noisy data,Computer-Aided Design,58,2015,189–199.

[13]Mustafa,G.and Rehman,N.A.,The mask of(2b+4)-point n-ary subdivision scheme,Computing,90(1–2),2010,1–14.

[14]Mustafa,G.,Ashraf,P.and Deng,J.,Generalized and unified families of interpolating subdivision schemes,Numerical Mathematics:Theory,Methds and Applications,7(2014),193–213,2014.

[15]Mustafa,G.and Khan,F.,A new 4-point C3quaternary approximating subdivision scheme,Abstract and Applied Analysis,2009,Article ID:301967,2009,14 pages.

[16]Mustafa,G.and Ivrissimtzis,I.P.,Model selection for the Dubuc-Deslauriers family of subdivision scheme,in Proceeding of the 14th IMA Conference on Mathematics of Surfaces,2013,155–162.

[17]Rioul,O.,Simple regularity for subdivision schemes,SIAM Journal on Mathematical Analysis,23,1992,1544–1576.

[18]Siddiqi,S.S.and Younis,M.,The m-point quaternary approximating subdivision schemes,American Journal of Computational Mathematics,3,2013,6–10.

[19]Zheng,H.,Hu,M.and Peng,G.,p-ary subdivision generalizing B-splines,2009 Second International Conference on Computer and Electrical Engineering,DOI:10.1109/ICCEE.2009.204