Skip to main content
SpringerLink
Log in

External versus Internal Parameterizations for Lengths of Curves with Nonuniform Samplings

  • Conference paper
  • First Online:
Geometry, Morphology, and Computational Imaging

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2616))

Abstract

This paper studies differences in estimating length (and also trajectory) of an unknown parametric curve γ : [0, 1] → IRn from an ordered collection of data points qi = γ(t i), with either the ti’s known or unknown. For the ti’s uniform (known or unknown) piecewise Lagrange interpolation provides efficient length estimates, but in other cases it may fail. In this paper, we apply this classical algorithm when the ti’s are sampled according to first α-order and then when sampling is ∈- uniform. The latter was introduced in [20] for the case where the ti’s are unknown. In the present paper we establish new results for the case when the ti’s are known for both types of samplings. For curves sampled ∈-uniformly, comparison is also made between the cases, where the tabular parameters ti’s are known and unknown. Numerical experiments are carried out to investigate sharpness of our theoretical results. The work may be of interest in computer vision and graphics, approximation and complexity theory, digital and computational geometry, and digital image analysis.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Asano T., Kawamura Y., Klette R., Obokkata K. (2000) A new approximation scheme for digital objects and curve length estimation. In: Cree M. J., Steyn-Ross A. (eds) Proc. Int. Conf. Image and Vision Computing New Zealand, Hamilton, New Zealand, Nov. 27–29, 2000. Dep. of Physics and Electronic Engineering, Univ. of Waikato Press, 26–31.

    Google Scholar 

  2. Barsky B. A., DeRose T. D. (1989) Geometric continuity of parametric curves: three equivalent characterizations. IEEE. Comp. Graph. Appl. 9:60–68.

    Article  Google Scholar 

  3. Boehm W., Farin G., Kahmann J. (1984) A survey of curve and surface methods in CAGD. Comput. Aid. Geom. Des., 1:1–60.

    Article  MATH  Google Scholar 

  4. Bülow T., Klette R. (2000) Rubber band algorithm for estimating the length of digitized space-curves. In: Sneliu A., Villanva V. V., Vanrell M., Alquézar R., Crowley J., Shirai Y. (eds) Proc. 15th Int. IEEE Conf. Pattern Recognition, Barcelona, Spain, Sep. 3–8, 2000, Vol. III, 551–555.

    Google Scholar 

  5. Bülow T., Klette R. (2001) Approximations of 3D shortest polygons in simple cube curves. In: Bertrand G., Imiya A., Klette R. (eds) Digital and Image Geometry, Springer, LNCS 2243, 285–295.

    Chapter  Google Scholar 

  6. Coeurjolly D., Debled-Rennesson I., Teytaud O. (2001) Segmentation and length estimation of 3D discrete curves. In: Bertrand G., Imiya A., Klette R. (eds) Digital and Image Geometry, Springer, LNCS 2243, 299–317.

    Chapter  Google Scholar 

  7. Dabrowska D., Kowalski M. A. (1998) Approximating band-and energy-limited signals in the presence of noise. J. Complexity 14:557–570.

    Article  MATH  MathSciNet  Google Scholar 

  8. Dorst L., Smeulders A.W. M. (1991) Discrete straight line segments: parameters, primitives and properties. In: Melter R., Bhattacharya P., Rosenfeld A. (eds) Ser. Contemp. Maths., Amer. Math. Soc., 119:45–62.

    Google Scholar 

  9. Epstein M. P. (1976) On the influence of parametrization in parametric interpolation. SIAM. J. Numer. Anal., 13:261–268.

    Article  MATH  MathSciNet  Google Scholar 

  10. Hoschek J. (1988) Intrinsic parametrization for approximation. Comput. Aid. Geom. Des., 5:27–31.

    Article  MATH  MathSciNet  Google Scholar 

  11. Klette R. (1998) Approximation and representation of 3D objects. In: Klette R., Rosenfeld A., Sloboda F. (eds) Advances in Digital and Computational Geometry. Springer, Singapore, 161–194.

    Google Scholar 

  12. Klette R., Bülow T. (2000) Critical edges in simple cube-curves. In: Borgefors G., Nyström I., Sanniti di Baja G. (eds) Proc. 9th Int. Conf. Discrete Geometry for Computer Imagery, Uppsala, Sweden, Dec. 13–15, 2000, Springer, LNCS 1953, 467–478.

    Google Scholar 

  13. Klette R., Kovalevsky V., Yip B. (1999) On the length estimation of digital curves. In: Latecki L. J., Melter R. A., Mount D. M., Wu A. Y. (eds) Proc. SPIEConf. Vision Geometry VIII, Denver, USA, July 19–20, 1999, 3811:52–63.

    Google Scholar 

  14. Klette R., Yip B. (2000) The length of digital curves. Machine Graphics and Vision, 9:673–703.

    Google Scholar 

  15. Moran P. (1966) Measuring the length of a curve. Biometrika, 53:359–364. 403

    MATH  MathSciNet  Google Scholar 

  16. Milnor J. (1963) Morse Theory. Princeton Uni. Press, Princeton, New Jersey.

    MATH  Google Scholar 

  17. Noakes L., Kozera R. (2002) More-or-less-uniform sampling and lengths of curves. Quart. Appl. Maths., in press.

    Google Scholar 

  18. Noakes L., Kozera R. (2002) Interpolating sporadic data. In: Heyden A., Sparr G., Nielsen M., Johansen P. (eds) Proc. 7th European Conf. Comp. Vision, Copenhagen, Denmark, May 28–31, 2002, Springer, LNCS 2351, 613–625.

    Google Scholar 

  19. Noakes L., Kozera R. (2002) Cumulative chord piecewise quadratics. In: Wojciechowski K. (ed.) Proc. Int. Conf. Computer Vision and Graphics, Zakopane, Poland, Sep. 25–29, 2002, Association of Image Processing of Poland, Silesian Univ. of Technology and Institute of Theoretical and Applied Informatics, PAS, Gliwice Poland, Vol. 2, 589–595.

    Google Scholar 

  20. Noakes L., Kozera R., Klette R. (2001) Length estimation for curves with different samplings. In: Bertrand G., Imiya A., Klette R. (eds) Digital and Image Geometry, Springer, LNCS 2243, 339–351.

    Chapter  Google Scholar 

  21. Noakes L., Kozera R., Klette R. (2001) Length estimation for curves with ∈-uniform sampling. In: Skarbek W. (ed.) Proc. 9th Int. Conf. Computer Analysis of Images and Patterns, Warsaw, Poland, Sep. 5–7, 2001, Springer, LNCS 2124, 518–526.

    Google Scholar 

  22. Piegl L., Tiller W. (1997) The NURBS Book. Springer, Berlin.

    Google Scholar 

  23. Plaskota L. (1996) Noisy Information and Computational Complexity. Cambridge Uni. Press, Cambridge.

    MATH  Google Scholar 

  24. Sederberg T. W., Zhao J., Zundel A. K. (1989) Approximate parametrization of algebraic curves. In: Strasser W., Seidel H. P. (eds) Theory and Practice in Geometric Modelling. Springer, Berlin, 33–54.

    Google Scholar 

  25. Sloboda F., Zaťko B., Stör J. (1998) On approximation of planar one-dimensional continua. In: Klette R., Rosenfeld A., Sloboda F. (eds) Advances in Digital and Computational Geometry. Springer, Singapore, 113–160.

    Google Scholar 

  26. Steinhaus H. (1930) Praxis der Rektifikation und zur Längenbegriff (In German). Akad. Wiss. Leipzig, Berlin 82:120–130.

    Google Scholar 

  27. Traub J. F., Werschulz A. G. (1998) Complexity and Information. Cambridge Uni. Press, Cambridge.

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science and Software Engineering, The University of Western Australia, 35 Stirling Highway, 6009, Crawley, WA, Australia

    Ryszard Kozera

  2. School of Mathematics and Statistics, The University of Western Australia, 35 Stirling Highway, 6009, Crawley, WA, Australia

    Lyle Noakes

  3. Centre for Images Technology and Robotics Tamaki Campus, The University of Auckland, Building 731, Auckland, New Zealand

    Reinhard Klette

Authors
  1. Ryszard Kozera
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lyle Noakes
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Reinhard Klette
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. JAIST, School of Information Science, 1-1 Asahidai, Tatsunokuchi, 923-1202, Ishikawa, Japan

    Tetsuo Asano

  2. Computer Science Dept. and CITR, University of Auckland, Tamaki Campus, Glen Innes, 1005, Auckland, New Zealand

    Reinhard Klette

  3. LSIIT UMR 7005 CNRS-ULP, Parc d’Innovation, Boulevard Sebastien Brant, BP 10413, 67412, Illkirch, France

    Chrisitan Ronse

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kozera, R., Noakes, L., Klette, R. (2003). External versus Internal Parameterizations for Lengths of Curves with Nonuniform Samplings. In: Asano, T., Klette, R., Ronse, C. (eds) Geometry, Morphology, and Computational Imaging. Lecture Notes in Computer Science, vol 2616. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36586-9_26

Download citation

  • DOI: https://doi.org/10.1007/3-540-36586-9_26

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-00916-0

  • Online ISBN: 978-3-540-36586-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation