Document Open Access Logo

Abstract Morphing Using the Hausdorff Distance and Voronoi Diagrams

Authors Lex de Kogel, Marc van Kreveld, Jordi L. Vermeulen

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.74.pdf
  • Filesize: 0.73 MB
  • 16 pages

Document Identifiers

Author Details

Lex de Kogel
  • Utrecht University, The Netherlands
Marc van Kreveld
  • Utrecht University, The Netherlands
Jordi L. Vermeulen
  • Utrecht University, The Netherlands

Funding

Research was funded by NWO TOP grant no. 612.001.651.

Cite AsGet BibTex

Lex de Kogel, Marc van Kreveld, and Jordi L. Vermeulen. Abstract Morphing Using the Hausdorff Distance and Voronoi Diagrams. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 74:1-74:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.74

Abstract

This paper introduces two new abstract morphs for two 2-dimensional shapes. The intermediate shapes gradually reduce the Hausdorff distance to the goal shape and increase the Hausdorff distance to the initial shape. The morphs are conceptually simple and apply to shapes with multiple components and/or holes. We prove some basic properties relating to continuity, containment, and area. Then we give an experimental analysis that includes the two new morphs and a recently introduced abstract morph that is also based on the Hausdorff distance [Van Kreveld et al., 2022]. We show results on the area and perimeter development throughout the morph, and also the number of components and holes. A visual comparison shows that one of the new morphs appears most attractive.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Morphing
  • Hausdorff distance
  • Voronoi diagrams

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. P. K. Agarwal, J. Pach, and M. Sharir. State of the union (of geometric objects). In J. Goodman, J. Pach, and R. Pollack, editors, Surveys on Discrete and Computational Geometry, volume 453 of Contemporary Mathematics, pages 9-48. American Mathematical Society, 2008. Google Scholar
  2. A. B. Albu, T. Beugeling, and D. Laurendeau. A morphology-based approach for interslice interpolation of anatomical slices from volumetric images. IEEE Transactions on Biomedical Engineering, 55(8):2022-2038, 2008. Google Scholar
  3. H. Alt, B. Behrends, and J. Blömer. Approximate matching of polygonal shapes. Annals of Mathematics and Artificial Intelligence, 13(3):251-265, 1995. Google Scholar
  4. H. Alt, P. Braß, M. Godau, C. Knauer, and C. Wenk. Computing the Hausdorff distance of geometric patterns and shapes. In B. Aronov, S. Basu, J. Pach, and M. Sharir, editors, Discrete and Computational Geometry - The Goodman-Pollack Festschrift, pages 65-76. Springer, 2003. Google Scholar
  5. H. Alt and L. J. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation. In Handbook of Computational Geometry, pages 121-153. Elsevier, 2000. Google Scholar
  6. N. Aspert, D. Santa-Cruz, and T. Ebrahimi. Mesh: Measuring errors between surfaces using the Hausdorff distance. In Proceedings of the IEEE International Conference on Multimedia and Expo, volume 1, pages 705-708, 2002. Google Scholar
  7. M. J. Atallah. A linear time algorithm for the Hausdorff distance between convex polygons. Information Processing Letters, 17(4):207-209, 1983. Google Scholar
  8. Franz Aurenhammer, Rolf Klein, and Der-Tsai Lee. Voronoi diagrams and Delaunay triangulations. World Scientific Publishing Company, 2013. Google Scholar
  9. G. Barequet, M. T. Goodrich, A. Levi-Steiner, and D. Steiner. Contour interpolation by straight skeletons. Graphical Models, 66(4):245-260, 2004. Google Scholar
  10. G. Barequet and M. Sharir. Piecewise-linear interpolation between polygonal slices. Computer Vision and Image Understanding, 63(2):251-272, 1996. Google Scholar
  11. G. Barequet and A. Vaxman. Reconstruction of multi-label domains from partial planar cross-sections. Computer Graphics Forum, 28(5):1327-1337, 2009. Google Scholar
  12. J.-D. Boissonnat. Shape reconstruction from planar cross sections. Computer Vision, Graphics, and Image Processing, 44(1):1-29, 1988. Google Scholar
  13. Q. W. Bouts, I. Kostitsyna, M. van Kreveld, W. Meulemans, W. Sonke, and K. Verbeek. Mapping polygons to the grid with small Hausdorff and Fréchet distance. In Proceedings of the 24th Annual European Symposium on Algorithms, pages 22:1-22:16, 2016. Google Scholar
  14. K. Buchin, M. Buchin, W. Meulemans, and B. Speckmann. Locally correct Fréchet matchings. Computational Geometry, 76:1-18, 2019. Google Scholar
  15. K. Buchin, E. W. Chambers, T. Ophelders, and B. Speckmann. Fréchet isotopies to monotone curves. In Proceedings of the 33rd European Workshop on Computational Geometry, pages 41-44, 2017. Google Scholar
  16. E. W. Chambers, D. Letscher, T. Ju, and L. Liu. Isotopic Fréchet distance. In Proceedings of the 23rd Canadian Conference on Computational Geomery, 2011. Google Scholar
  17. P. Cignoni, C. Rocchini, and R. Scopigno. Metro: measuring error on simplified surfaces. Computer Graphics Forum, 17(2):167-174, 1998. Google Scholar
  18. M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer, 3rd edition, 2008. Google Scholar
  19. M.-P. Dubuisson and A. K. Jain. A modified Hausdorff distance for object matching. In Proceedings of 12th IEEE International Conference on Pattern Recognition, volume 1, pages 566-568, 1994. Google Scholar
  20. C. Gotsman and V. Surazhsky. Guaranteed intersection-free polygon morphing. Computers & Graphics, 25(1):67-75, 2001. Google Scholar
  21. R. M. Haralick, S. R. Sternberg, and X. Zhuang. Image analysis using mathematical morphology. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-9(4):532-550, 1987. Google Scholar
  22. O. van Kaick, H. Zhang, G. Hamarneh, and D. Cohen-Or. A survey on shape correspondence. Computer Graphics Forum, 30(6):1681-1707, 2011. Google Scholar
  23. M. van Kreveld, T. Miltzow, T. Ophelders, W. Sonke, and J. L. Vermeulen. Between shapes, using the Hausdorff distance. Computational Geometry, 100:101817, 2022. Google Scholar
  24. Z. Liu, L. Zhou, H. Leung, and H. P.-H. Shum. High-quality compatible triangulations and their application in interactive animation. Computers & Graphics, 76:60-72, 2018. Google Scholar
  25. A. Maheshwari, J.-R. Sack, and C. Scheffer. Approximating the integral Fréchet distance. Computational Geometry, 70:13-30, 2018. Google Scholar
  26. G. Rote. Lexicographic Fréchet matchings. In Proceedings of the 30th European Workshop on Computational Geometry, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact