Open Journal of Applied Sciences, 2013, 3, 106-111 doi:10.4236/ojapps.2013.31B1022 Published Online April 2013 (http://www.scirp.org/journal/ojapps) The 4-Point α-Ary Approximating Subdivision Scheme Abdul Ghaffar1, Ghulam Mustafa1, Kaihuai Qin2 1Department of Mathematics, The Islamia University of Bahawalpur, Bahawalpur, Pakistan 2Dept. of Computer Science & Technology, Tsinghua University, Beijing 100084, P. R. China Email: abdulghaffar.jaffar@gmail.com, ghulam.mustafa@iub.edu.pk, qkh-dcs@tsinghua.edu.cn Received 2013 ABSTRACT A general formula for 4-point -Ary approximating subdivision scheme for curve designing is introduced for any ar- ity 2 . The new scheme is extension of B-spline of degree 6. Laurent polynomial method is used to investigate the continuity of the scheme. The variety of effects can be achieved in correspondence for different values of parameter. The applications of the proposed scheme are illustrated in comparison with the established subdivision schemes. Keywords: Approximating Subdivision Scheme; Binary; Ternary; -Ary; Continuity; Convergence and Shape Parameters 1. Introduction Subdivision modeling methods are effective algorithms to generate continuous curves and surfaces from a dis- crete set of control points by subdividing them according to some refining rules, recursively. Repetition of this process produces a very good approximation to the curve or surface defined by the original set of control points. In recent years, the subject of subdivision gained popularity due to some new applications, such as in the 3D anima- tion industry. The next venture is to introduce these methods to be more consistent and efficient to the world of geometric modeling in the industry. Approximating schemes were first developed by Rham and Chaikin [1,2]. Consequent to this, a lot of work has been done by different authors in the field of binary sub- division schemes, but the research communities are in- terested in introducing higher arity schemes (i.e. ternary, quaternary, ...n-ary) which give better result and less computational cost. In late 80,s with the help of wavelet theory, a relation- ship between subdivision scheme and the “mask” of re- finable function have been developed. Lian [3,4] has introduced 3, 4, 5 and 6-point a-ary interpolating schemes. In these research papers, Lian used wavelets theory, a relatively new subject area that has been deeply studied for the last two decades or so, and found many successful applications. Lian [5] also offered 2m and (2m + 1) -point interpolating a-ary schemes for curve design- ing. In 2009, Mustafa and Khan [6] for the first time in- troduced a new 4-point quaternary approximating subdi- vision scheme. Mustafa and Najma [7] presented same perspective for constructing (2b + 2) and (2b + 4) -point n-ary interpolating and approximating schemes. Ghaffar et al. presented unified 3-point -ary approximation schemes and discussed various properties [8]. This moti- vates us to present 4-point -ary approximating scheme with high smoothness and more degree of freedom for curve designing. One of the main objectives of current work is to extend “The B-Spline of degree 6” to 4-point -ary approximating subdivision scheme. This paper is organized as follows: General form of 4-point -ary subdivision scheme is constructed in Sec- tion 2. The family of 4-point -ary approximating scheme, basic properties and analysis are presented in Section 3. Comparison of 4-point -ary schemes is given in Section 4. Finally conclusion is given in Section 5. 2. Main Results In this section, we are introducing family of 4-point -ary approximating subdivision scheme for curve de- signing for any arity 2 . This family is the extension of B-spline of degree six i.e. (4-point approximating sub- division scheme): 1 21 1 1 2111 2 735211 , 6464 6464 121357 . 6464 6464 kkkk iiii kkkk iiii 2 k i k i ffff ffff , (1) If there exist a unique −sequence that de- scribes the “two scale equation” 2 l{} k P 2 k k Pxk (2) Copyright © 2013 SciRes. OJAppS
A. GHAFFAR ET AL. 107 of scaling function . Then corresponding to this - sequence, let us introduce the notation 2 l 1 () , 2 k k k PzP zPz (3) Due to the development of the wavelet theory, the schemes (1) can be easily re-discovered by the scaling functions 4 satisfying the two-scale equations 444 4 444 44 127 212122 64 352335242125 72627, ttt t tt tttR t (4) By taking the Fourier transforms of (4), we arrive at the following two-scale equations of 4 2 444 3 2 2 44 5 3 2 44 11 721 ˆˆˆ ˆ 64 222222 35 35 ˆˆ 2222 21 7 ˆˆ 2222 iw iw iw iw iw iw ww wee ww ee ww ee 4 w 7 2 4 1ˆ. 22 iw w e This implies 4 2 2 3 2 44 3 0 2 13 11 ˆˆ. 22 41 iw iw iw j e w we j e This normalization simplifies to the following Fourier transform formulation: 444 1 ˆˆ , 22 w wP z where 4 23 43 0 3 11 , 1 4 j z Pz z j z (5) and 2. iw ze By introducing the shape parameter in (5), we get j u 4 23 42 0 3 111. 14 4 j j z Pz uz j z (6) By taking and , we get 03 4uu w 12 4(1 )uu w 2 4 4 1(1 ) ()()(1 )(1 ). 16 (1) z Pzwwzwzwz z Now, if we allow the scaling factor, denoted by a, to be , and denote such a scaling function denoted by 2 a , then the Fourier transforms of two-scale equation of a becomes , iw aaa aw wP a e and . aaa w wP a z where and again, is its two-scale symbol and (/)iw a zeaP a is then equivalent to satisfies aP 42 43 1(1 ) ()()(1)(1 ). (1 ) (2) a az PZwwzwzwz z a 3 (7) 3. Family of 4-Point a-Ary Schemes In this section, we discuss only three 4-point schemes. For setting 2,3a and 4 in (7), we obtain three poly- nomials a Pza 4 with following sets of coef- ficients called the mask of the 4-point binary, ternary and quaternary schemes, respectively. ,2,3,4 2 4 ,13 ,5,105 , 1, 105 ,5,13, 16 www w ww ww (8) 3 4 ,13,55,143,263, 1359 ,359,263,143,, 54 55,13, ww www wwww www (9) and 4 4 ,13 ,55 ,147 ,305 , 51,717,8413 ,8413, 1, 717 ,51,305,147 , 128 55,13, ww www wwww www w www (10) Order of continuities of the above schemes is given in Table 1. One can easily find the order of continuity over the parametric intervals by using the approach of [9]. 3.1. Support of Basic Limit Function The basic function of a subdivision scheme is the limit function of the proposed scheme for the following data 01, 0, 0, 0. i i fi (11) 2 3 The following theorem is related to the support of ba- sic limit functions of the 4-point a-ary scheme. Theorem 1. The basic limit functions of 4 pro- posed 4-point a-ary approximating schemes have support Φ a Copyright © 2013 SciRes. OJAppS
A. GHAFFAR ET AL. Copyright © 2013 SciRes. OJAppS 108 Table 1. The order of continuity of proposed 4-point a-ary schemes for certain ranges of parameter. Scheme Parameter Cn Scheme Parameter Cn Binary 35 22 w C0 Quaternary 33 14 2 w C0 ... 35 22 w C1 ... 1319 22 w C1 ... 13 22 w C2 ... 35w C2 ... 13 22 w C3 ... 13w C3 01w C4 ... 1 4 w C5 Ternary 23 31 44 w C0 ... 71 22 w 1 C1 ... 24w C2 ... 13w C3 (a) (b) (c) Figure 1. (a-c) represent the basic limit functions of the 4-point binary, ternary and quaternary schemes, respectively. by 411 2 a a on both sides. Hence after k subdivision width 41 1 a sa , for which implies 2, 3,4,...,,am that it vanishes outside the interval 4141 , 2121 aa aa . steps the furthest non-zero vertex on the left will be at 2 1 0 41111 2 41 1 . k k j j a aaa a aa Proof. Since the basic function is the limit function of the scheme corresponding to (7) for the data (11), its support width “s” can be determine by computing how far the effect of the non-zero vertex 0 0 will propagate along by. As the mask of a-ary 4-point scheme is 41a long sequence by centering it on that vertex; the dis- tances to the last of its left and right non-zero coefficients So the total support width is 0 411 41 2. 1 j j aa aa a are equal to 41 2 a At the first subdivision step we see 3.2. Precision Set that the vertices on the both sides of 1 0 at 41 2 a are For approximating schemes, we do not expect new verti- ces to be lie on the same curve as old ones, so it is nec- essary to look to see whether all the vertices lie on a common curve. We can calculate the order of precision by using the technique as given in [10]. the furthest non-zero new vertices. At each refinement, the distances on both sides are reduced by the factor 1 a. At the next step of the scheme, this will propagate along
A. GHAFFAR ET AL. 109 Lemma 2. The scheme (3.1) has cubic precision. Proof. We carry out this result by taking our origin the middle of an original span with ordinate ,5,3,1,1,3,5, nnnnnn If n x, then we have 1234 4321 1111 4321 4321 ,531 1 5311, 3113, 3113, , 1135, nnn nnnn nnnn nnnn nn nn ya aa a aaaa aaaa aaaa aaaa , n where 1234 375 ,,, 1616 1616 aaaa 1 . If 1 x, then we have 2 531135 ,,,,,,, 2 22222 ,1,1,1,1,1, 0, y y y where represents the differences of the vertices. If 2 x, then we have 15 73 3 , 2,2,2,2 2 222 715 2,2, 22 y wwww ww , Taking further differences, we get . 30y If 3 x, then we have ,2515,9 9,22, 22,99,2515, yww ww w w by taking further differences, we get . 4 δy0t Thus the scheme has cubic precision. For this analysis we observe that the scheme (8) is de- signed so that it has cubic precision for any value of . While the schemes (9) and (10) have cubic precision for w any value of w and with the special values 1 w3 and 1 w 2 , the schemes have quartic precision, respectively. 4. Comparison and Application In this section, we show that the popular existing schemes are special cases of our proposed family of schemes (8)- (10). With the special values of parameter (w0 and 1 w4 ), the subdivision schemes generated by B-splines of degree 4 and 6, respectively, are obtained from the schemes (8). Moreover, the proposed scheme (8) is a generalized scheme, as the mask of the proposed scheme coincides with the mask of schemes [9,11-13] after setting 5 w, 8 1 w0,wω 6 and wu respectively. It may be noted that if we put 11 wω,w u 6162 1 3 and 35 w24 in (9), the proposed 4-point scheme can also be consid- ered as the general form of the stationary 4-point ternary approximating schemes of [8,13,16], respectively. For substituting 21 w8 , the obtained mask of scheme (10) coincides with mask of the famous 4-point quaternary scheme of Ko [17]. Here we compare our proposed schemes with the ex- isting binary, ternary and quaternary schemes (see Table 2). It is observed that the continuity and approximation order of proposed schemes are better than the existing schemes. Moreover, Figure 2 is exposed to show the role of free parameters when the schemes (8)-(10) applied on discrete data points. In Figure 2(a), black, red and blue lines show the visual smoothness of the binary scheme at the parametric values 1 0, 8 ww and 1 2 w , re- spectively. In Figure 2(b), blue, green, black and red lines show the visual smoothness of the ternary scheme at the parametric values 1 1,, 0 2 ww w, and 1 2 w , respectively. In Figure 2(c), blue, green, black and red lines show the visual smoothness of the quaternary scheme at the parametric values 1,w 1, 2 ww 0 and 1 2 w , respectively. From Figure 2, we conclude that the behavior of the limiting curve acts as tightness/looseness when the values of free pa- ameter vary. r Copyright © 2013 SciRes. OJAppS
A. GHAFFAR ET AL. Copyright © 2013 SciRes. OJAppS 110 Table 2. Comparison of 4-point ternary schemes. Type Support Scheme Order Cn Binary 4-point [18] Inteng rpolati6 4 1 Binary 4-point [19] Interpolating 4 6 1 Binary 4-point [12] Approximating 7 4 2 Interpolating Ternary 4-point [20] 5 4 1 Interpolating 5 3 Ternary 4-point [21, 3] 1 Interpolating Ternary 4-point [22] 5 2 Interpolating 5 Ternary 4-point [3] 3 1 Ternary 4-point [16] Approximating 4 5.5 2 Approximating 5 4 Quaternary 4-point [17] 2 Approximating 4 Quaternary 4-point [6] 5 3 Approximating 7 3 Binary 4-point proposed 5 Approximating 5 Ternary 4-point proposed 5.5 3 Approximating 5 5 Quaternary 4-point proposed 3 (a) (b) (c) Figure 2. ectively. . Conclusio oint a-ary approximating schemes for 027), the National Natural a (60973101) and HEC Paki- G. de Rham, “Un Peude Mathematiques a Proposed Une Courbe Plane,” Revwede Mathematiques Elementry II, Oevred Comp (a-c) show the role of shape parameter of the schemes (8), (9) and (10) resp 5ns 6. Acknowledgement The families of 4-p curve design were established in general. The first family is binary, the second is ternary and the third family is quaternary approximating. The support of subdivision scheme influences the locality. One of the best ways to get a smaller support is to raise the arity. This is one of the advantages of the proposal of the scheme. We have also studied its continuity and determined its order of precision. It is observed that the order of precision set increases by increasing the arity of the schemes while the continuity decreases by increasing the arity of the scheme. Moreover, we have showed that several previ- ously proposed schemes are members of this family. It has been shown that proposed schemes are better than existing schemes in the sense of smoothness and ap- proximation order. This work is supported by the Beijing Municipal Natural Science Foundation (4102 Science Foundation of Chin stan. REFERENCES [1] letes, 1947, pp. 678-689. [2] G. M. Chaikin, “An Algorithm for High-Speed Curve Generation,” Computer Graphics and Image Processing, Vol. 3, No. 4, 1974, pp. 346-349. doi:10.1016/0146-664X(74)90028-8 [3] J. -A. Lian, “On A-ary Subdivision for Curve Design: I. 4-point and 6-point Interpolatory Schemes,” Applications
A. GHAFFAR ET AL. 111 and Applied Mathematics: An Inte 3, No. 1, 2008, pp.18-29. rnational Journal, Vol. 7. p. 434-444. [4] J. -A. Lian, “On A-ary Subdivision for Curve Design: II. 3-point and 5-point Interpolatory Schemes,” Applications and Applied Mathematics: An International Journal, Vol. 3, No. 2, 2008, pp. 176-18 [5] J. -A. Lian, “On a-ary Subdivision for Curve design: III. 2m-point and (2m+1) point Interpolatory Schemes,” Ap- plications and Applied Mathematics: An International Journal, Vol. 4, No. 2, 2009, p [6] G. Mustafa and F. Khan, “A New 4-point Quaternary Approximating Subdivision Scheme,” Abstract and Ap- plied Analysis, Vol. 2009, Article ID 301967, 14 pages. [7] G. Mustafa and A. R. Najma , “The Mask of (2b + 4)-point n-ary Subdivision Scheme,” Computing, Vol. 90, No. 1-2, 2010, pp. 1-14. doi:10.1007/s00607-010-0108-x [8] A. Ghaffar, G. Mustafa and K. Qin, “Unification and Application of 3-point Approximating Subdivision Schemes of Varying Arity,” Open Journal of Applied Sciences, Vol. 2, No. 4B, 2012, pp. 48-52. doi:10.4236/ojapps.2012.24B012 [9] M. F. Hassan and N. A. Dodgson, “Ternary and Three-point Univariate Subdivision Schemes,” In: A. Cohen, J. L. Marrien, L. L. Schumaker (Ed Surface Fitting: Sant-Malo2002, N s.), Curve and ashboro Press, Brent- nger, 2002, pp. 51-68. wood, 2003, pp. 199-208. [10] N. Dyn, “Analysis of Convergence and Smoothness by the Formalism of Laurent Polynomials,” In: A.Iske, E. Quak, M. S Floater (Eds), Tutorials on Multiresolution in Geometric Modelling, Spri doi:10.1007/978-3-662-04388-2_3 [11] G. Mustafa, F. Khan and A. Ghaffar, “The -Point Ap- proximating Subdivision Scheme,” Lobachevskii Journal of Mathematics, Vol. 30, No. 2, 2009, pp. 138-145. doi:10.1134/S1995080209020061 [12] N. Dyn, M. S. Floater and K. Horman, “A Four-Point Subdivision Scheme with Fourth Order Accuracy and its Extension,” In Mathematical Methods for Curves and Surfaces: Tromso 2004, M. Daehlen, K. Morken, and L ring, 2009, pp. . L. Schumaker (eds.), 2005, pp. 145-156. [13] H. Zheng, M. Hu and G. Peng, “P-ary Subdivision Gen- eralizing B-splines,” Second International Conference: On Computer and Electrical Enginee 214-218. doi:10.1109/ICCEE.2009.204 [14] A. Ghaffar and G. Mustafa, “A Family of Even-Point ternary Approximating Schemes,” ISRN Applied Mathe- matics, Vol. 2012, 2012, Article ID 197383, 14 pages. er- [15] H. Zheng, M. Hu and G. Peng, “Ternary Even Symmetric 2n-point Subdivision,” International Conference on: Computational Intelligence and Software Engine ing,2009, pp. 1-4.doi:10.1109/CISE.2009.5363033 [16] K. P. Ko, B. -G. Lee and G. Joon Yoon. “A Ternary 4-point Approximating Subdivision Scheme,” Applied Mathematics and Computation, Vol. 190, 2007 [17] K. P. Ko, “A Quatnary Approximating 4-point Subdivi- sion Scheme,” J. KSIAM, Vol. 13, No. 4, 2009, PP. 307-341. [18] C. Beccari, G. Casciola and L. Romani, “A Non-stationary Uniform Tension Controlled Interpolating 4-point Scheme Reproducing Conics,” Computer Aided Geometric Design, Vol. 24, No. 1, 2007, pp. 1-9. [19] G. Casciola and L. Romani. “An Interpolating 4-point Ternarynon-stationary Subdivision Scheme with Tension Control,” Computer Aided Geometric Design, Vol. 24, . 1, 2009, pp. 916-927. No. 2, 2007, pp. 210-219. [20] G. Casciola and L. Romani, “Shape Controlled Interpola- tory Ternary Subdivision,” Applied Mathematics and Computation, Vol. 215, No [21] G. Deslauriers and S. Dubic, “Symmetric Iterative Inter- polation Process,” Constractive Approximation, Vol. 5, No. 1, 1989, pp. 49-68. doi:10.1007/BF01889598 [22] M. F. Hassan, I. P. Ivrissimitzis, N. A. Dodgson and M. A. Sabin, “An Interpolating 4-points C2 Ternary Stationary Subdivision Scheme,” Computer Aided Geometric Design, Vol. 19, 2002, pp. 1-18. Copyright © 2013 SciRes. OJAppS
|