Asymptotics for Length and Trajectory from Cumulative Chord Piecewise-Quartics

• Autorzy: Kozera R.
• Języki publikacji: EN

Abstrakty

EN

We discuss the problem of estimating the trajectory of a regular curve γ:[0,T]→Rⁿ and its length d(γ) from an ordered sample of interpolation points Q_m = {γ(t₀),γ(t₁),...,γ(t_m)}, with tabular points ti˘s unknown, coined as interpolation of unparameterized data. The respective convergence orders for estimating γ and d(γ) with cumulative chord piecewise-quartics are established for different types of unparameterized data including e-uniform and more-or-less uniform samplings. The latter extends previous results on cumulative chord piecewise-quadratics and piecewise-cubics. As shown herein, further acceleration on convergence orders with cumulative chord piecewise-quartics is achievable only for special samplings (e.g. for ԑ-uniform samplings). On the other hand, convergence rates for more-or-less uniform samplings coincide with those already established for cumulative chord piecewise-cubics. The results are experimentally confirmed to be sharp for m large and n = 2,3. A good performance of cumulative chord piecewise-quartics extends also to sporadic data (m small) for which our asymptotical analysis does not apply directly.

Słowa kluczowe

EN

interpolation; unparameterized data; cumulative chord piecewise-quartics; curve and length estimation; orders of approximation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 61, nr 3,4
• Strony: 267--283
• Opis fizyczny: Bibliogr. 45 poz., rys.

Twórcy

autor

Kozera R.

• School ofComputer Science and Software Engineering, The University of Western Australia,35 Stirling Highway, Crawley W.A. 6009, Perth, Australia,

Bibliografia

• 1] Barsky, B. A., DeRose. T. D.: Geometric Continuity of Parametric Curves: Three Equivalent Characterizations, IEEE. Camp. Graph, Appl..9, 1989,60-68.
• [2] Bertrand, G., Imiya, A., (eds), R. K.: Digital and Image Geometry, vol. 2243 of LNCS, Springer-Verlag, Berlin Heidelberg, 2001.
• [3] Bezier, P. E.: Numerical Control: Mathematics and Applications, John Wiley, New York, 1972.
• [4] Boehm. E., Farin. G., Kahmann, J.: A Survey of Curve and Surface Methods in CAGD. Computer Aided Geom. Design,1. 188. 1-60.
• [5] de Boor, C: A Practical Guide to Spline, Revised edition, Springer-Verlag, New York Heidelberg Berlin, 2001.
• [61 de Boor, C, Hollig, K., Sabin. M.: High accuracy geometric Hermite interpolation. Computer Aided Geom. Design,4, 1987,269-278,
• [7] Bülow. T, Klette. R.: Rubber Band Algorithm for Estimating the Length of Digitized Space-Curves. 15th Int. Con. Pattern Recog., ICPR 2000. Barcelona. Spain. September 2000 (A. Sneliu. V. V. Villanva, M. Vanrell, R. Alquezar, J. Crowley, Y, Shirai, Eds.), vol. ill, IEEE. 2000, 551-555.
• [8] Davis, P. J.: Interpolation and Approximation, Dover Pub. Inc., New York, 1975.
• [9] Dąbrowska, D., Kowalski, M. A.: Approximating Band- and Energy-Limited Signals in the Presence of Noise, J. Complexity, 14, 1998. 557-570, In German.
• [10] Dorst, L., Smeulders. A, W. M.: Discrete Straight Line Segments: Parameters, Primitives and Properties, in: Ser. Contemp. Maths (R. Melter, P. Bhauacharya, A. Rosenfeld, Eds.), vol. 119, Amer. Math. Soc, 1991, 45-62.
• [11] Epstein, M. P.: On the influence of parameterization in parametric interpolation, SIAM J. Numer. Anal., 13. 1976.261-268.
• [12] Farin. G.: Curves and Surfaces for Computer Aided Geometric Design, 3nd edition. Academic Press. San Diego, 1993.
• [13] Hoschek, J.: Intrinsic Parametrization for Approximation, Computer Aided Geom. Design, 5, 1988,27-31.
• [14] Kiciak, P.: Postawy modelowania krzywych i powierzchni, Wydawnictwo Naukowo-Techniczne, Warszawa, 2000, In Polish.
• [15] Klette, R.: Approximation and Representation of 3D Objects, in; Advances in Digital and Computational Geometry (R. Klette, A. Rosenfeld, R Sloboda. Eds.), Springer, Singapore, 1998, 161-194.
• [16] Klette, R., Bülow, T.: Critical Edges in Simple Cube-Curves. 9th Int. Conf. on Discrete Geometry for Computer Imagery. DGCI2000. Uppsala, Sweden. December 2000 (G. Borgefors, I. Nystrdm, G. S. di Baja, Eds.), LNCS, vol. 1953 of LNCS, Springer-Verlag, Berlin Heidelberg, 2000, 467-478.
• [17] Klette, R., Kovalevsky, V., Yip, B.: On the Length Estimation of Digital Curves, SPIE Conf. Vision Geometry VIII. SPIE VIII Denver. USA. January 1999 (L. J. Latecki. R. A. Melter, D. A. Mount, A. Y Wu. Eds.), vol. 3811, The International Society for Optical Engineering, 1999, 52-63.
• [18] Klette, R., Yip, B.: The Length of Digital Curves, Machine Graphics and Vision, 9, 2000, 673-703.
• [19] Klingenberg, W.: A Course in Differential Geometry, Springer-Verlag, Berlin Heidelberg, 1978.
• [20] Kozera, R.: Cumulative chord piecewise-quartics for length and trajectory estimation, 10th Int. Conf. on Computer Analysis of Images and Patterns. CAIP 2003. Groningen. The Netherlands. August 2003 (N. Petkov, M. A. Westenberg, Eds.), LNCS, vol. 2756 of LNCS, Springer-Verlag, Berlin Heidelberg, 2003, 697-705.
• [21] Kozera, R., Noakes, L.: C^ Interpolation with Cumulative Chord Cubics, Fundamenta Informaticae, In press.
• [22] Kozera, R., Noakes, L., Klette, R.: External versus internal parameterization for lengths of curves with nonuniform samplings, in: Theoretical Foundations of Computer Vision, Geometry and Computational Imaging (C. R. T. Asano, R. Klette, Ed.), vol. 2616 of LNCS, Springer-Ver lag, Berlin Heidelberg, 2003, 403-418.
• [23] Kvasov, B. L: Methods of Shape-Preserving Spline Approximation, World Scientific, Singapore, 2000.
• [24] Lachance, M. A., Schwartz, A. J.: Four point parabolic interpolation. Computer Aided Geom. Design, 8, 1991.143-149.
• [25] Lee, E. T. Y: Comers, cusps, and parameterization: variations on a theorem of Epstein, SIAM J. Numer. Anal.,29, 1992,553-565.
• [26] Milnor, J. W.: Morse Theory, Annals Math. Studies 51, Princeton Uni. Press, 1963.
• [27] Moran, P.: Measuring the Length of a Curve, Biometrika, 53, 1966, 359-364.
• [28] M0rken, K., Scherer. K.: A general framework for high-accuracy parametric interpolation. Math. Computation, 66(217) 1991,231-260.
• [29] Noakes, L., Kozera, R.: Cumulative chords piecewise-quadratics and piecewise-cubics, in: Geometrical Properties from Incomplete Data (R. Klette, R. Kozera, L. Noakes, J. Weickert, Eds.), Kluver Academic Publishing, Submitted.
• [30] Noakes. L., Kozera, R.: Cumulative chords and piecewise-quadratics. Int. Conf. on Computer Vision and Graphics, ICCVG 2002. Zakopane. Poland. May 2002 (K. Wojciechowski. Ed.), vol. II, Association for Image Processing Poland, Silesian University of Technology Gliwice Poland, Institute of Theoretical and Applied Informatics PAS Gliwice Poland, 2002.589-595.
• [31] Noakes. L., Kozera. R.: Interpolating sporadic data. 7th Euro. Conf. on Computer Vision. ECCV 2002. Copenhagen, Denmark. May 2002 (A. Heyden, G. Sparr, M. Nielsen, P. Johansen, Eds.), LNCS, vol. 2351/II of LNCS, Springer-Verlag, Berlin Heidelberg, 2002,613-625.
• [32] Noakes, L., Kozera, R.: More-or-less uniform sampling and lengths of curves, Quar. Appl. Math., 61(3), 2003,475-484.
• [33] Noakes, L., Kozera, R., Klette, R.; Length estimation for curves with different samplings, in: Digital Image Geometry (G. Bertrand, A. Imiya, R. Klette, Eds.), vol. 2243 of LNCS, Springer-Verlag, Berlin Heidelberg, 2001,339-351.
• [34] Noakes, L., Kozera, R., Klette, R.: Length estimation for curves with e-uniform sampling, 9th Int. Conf. on Computer Analysis of Images and Patterns, CAIP 2001, Warsaw. Poland, September 2001 (W. Skarbek, Ed.), LNCS, vol. 2124 of LNCS, Springer-Verlag, Berlin Heidelberg, 2001,518-526.
• [35] Piegl, L., Tiller, W.: The NURBS Book, 2nd edition. Springer-Verlag, Berlin Heidelberg, 1997.
• [36] Plaskota, L.: Noisy Information and Computational Complexity, Cambridge Uni. Press, Cambridge, 1996.
• [37] Rababah. A.: High order approximation methods for curves. Computer Aided Geom. Design, 12, 1995, 89-102.
• [38] Ralston, A.: A First Course in Numerical Analysis, McGraw-Hill, 1965.
• [39] Schaback, R.: Optimal geometric Hermite interpolation of curves, in: Mathematical Methods for Curves and Surfaces II (M. Dæhlen, T. Lyche, L. Schumaker. Eds.), Vanderbilt University Press, 1998, 1-12.
• [40] Sederberg, T. W., Zhao, J., Zundel, A. K.: Approximate Parametrization of Algebraic Curves, in: Theory and Practice in Geometric Modelling (W. Strasser, H. P. Seidel, Eds.), Springer-Verlag, Berlin Heidelberg, 1989,33-54.
• [41] Sloboda, F, Zaiko, B., Stör, J.: On Approximation of Planar One-Dimensional Continua, in: Advances in Digital and Computational Geometry (R. Klette, A. Rosenfeld, F. Sloboda, Eds.), Springer, Singapore, 1998, 113-160.
• [42] Steinhaus, H.: Praxis der Rektifikation und zur Längenbegriff, Akad. Wiss. Leipzig Ber., 82, 1930, 120-130, In German.
• [43] Taubin, T: Estimation of Planar Curves, Surfaces, and Non-planar Space Curves Defined by Implicit Equations with Applications to Edge and Range Image Segmentation, IEEE Trans. Patt. Mach. intell, 13(11), 1991,1115-1138.
• [44] Traub, J. F., Werschulz, A. G.: Complexity and Information, Cambridge Uni. Press, Cambridge, 1998.
• [45] van der Waerden, B. L.: Geometry and Algebra in Ancient Civilizations, Springer, Berlin, 1983.