“Voxel cores: efficient, robust, and provably good approximation of 3D medial axes” by Yan, Letscher and Ju
Conference:
Type:
Entry Number: 44
Title:
- Voxel cores: efficient, robust, and provably good approximation of 3D medial axes
Session/Category Title: An Immersion in Computational Geometry
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We present a novel algorithm for computing the medial axes of 3D shapes. We make the observation that the medial axis of a voxel shape can be simply yet faithfully approximated by the interior Voronoi diagram of the boundary vertices, which we call the voxel core. We further show that voxel cores can approximate the medial axes of any smooth shape with homotopy equivalence and geometric convergence. These insights motivate an algorithm that is simple, efficient, numerically stable, and equipped with theoretical guarantees. Compared with existing voxel-based methods, our method inherits their simplicity but is more scalable and can process significantly larger inputs. Compared with sampling-based methods that offer similar theoretical guarantees, our method produces visually comparable results but more robustly captures the topology of the input shape.
References:
1. Nina Amenta, Sunghee Choi, and Ravi Krishna Kolluri. 2001. The power crust, unions of balls, and the medial axis transform. Computational Geometry 19, 2-3 (2001), 127–153. Google ScholarDigital Library
2. Nina Amenta and Ravi Krishna Kolluri. 2001. The medial axis of a union of balls. Comput. Geom. 20, 1-2 (2001), 25–37. Google ScholarDigital Library
3. Carlo Arcelli and Gabriella Sanniti di Baja. 1993. Euclidean skeleton via centre-of-maximal-disc extraction. Image and Vision Computing 11, 3 (1993), 163–173.Google ScholarCross Ref
4. Carlo Arcelli, Gabriella Sanniti di Baja, and Luca Serino. 2011. Distance-driven skeletonization in voxel images. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 4 (2011), 709–720. Google ScholarDigital Library
5. Dominique Attali and Jean-Daniel Boissonnat. 2004. A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces. Discrete & Computational Geometry 31, 3 (2004), 369–384. Google ScholarDigital Library
6. Dominique Attali and Annick Montanvert. 1996. Modeling noise for a better simplification of skeletons. In Proceedings 1996 International Conference on Image Processing, Lausanne, Switzerland, September 16-19, 1996. 13–16.Google ScholarCross Ref
7. Gilles Bertrand and Grégoire Malandain. 1994. A new characterization of three-dimensional simple points. Pattern Recognition Letters 15, 2 (1994), 169–175. Google ScholarDigital Library
8. Anders Björner, Bernhard Korte, and László Lovász. 1985. Homotopy properties of greedoids. Advances in Applied Mathematics 6, 4 (1985), 447–494. Google ScholarDigital Library
9. H. Blum. 1967. A transformation for extracting new descriptors of form. Models for the Perception of Speech and Visual Form (1967), 362–80.Google Scholar
10. J. Brandt and V. Algazi. 1992. Continuous skeleton computation by Voronoi diagram. CVGIP: Image Understanding 55, 3 (1992), 329 — 338. Google ScholarDigital Library
11. Frederic Cazals, Aditya Parameswaran, and Sylvain Pion. 2008. Robust construction of the three-dimensional flow complex. In Proceedings of the twenty-fourth annual symposium on Computational geometry. ACM, 182–191. Google ScholarDigital Library
12. Frédéric Chazal and André Lieutier. 2005. The “λ-medial axis”. Graphical Models 67, 4 (2005), 304–331. Google ScholarDigital Library
13. Frédéric Chazal and André Lieutier. 2008. Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees. Computational Geometry 40, 2 (2008), 156–170. Google ScholarDigital Library
14. Tim Culver, John Keyser, and Dinesh Manocha. 2004. Exact computation of the medial axis of a polyhedron. Computer Aided Geometric Design 21, 1 (2004), 65–98. Google ScholarDigital Library
15. Tamal K. Dey and Wulue Zhao. 2003. Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee. Algorithmica 38, 1 (2003), 179–200. Google ScholarDigital Library
16. Michal Etzion and Ari Rappoport. 2002. Computing Voronoi skeletons of a 3-D polyhedron by space subdivision. Computational Geometry 21, 3 (2002), 87–120. Google ScholarDigital Library
17. Mark Foskey, Ming C Lin, and Dinesh Manocha. 2003. Efficient computation of a simplified medial axis. In Proceedings of the eighth ACM symposium on Solid modeling and applications. ACM, 96–107. Google ScholarDigital Library
18. Yaorong Ge and J Michael Fitzpatrick. 1996. On the generation of skeletons from discrete Euclidean distance maps. IEEE Transactions on Pattern Analysis and Machine Intelligence 18, 11 (1996), 1055–1066. Google ScholarDigital Library
19. Joachim Giesen, Edgar A Ramos, and Bardia Sadri. 2006. Medial axis approximation and unstable flow complex. In Proceedings of the twenty-second annual symposium on Computational geometry. ACM, 327–336. Google ScholarDigital Library
20. Wim H Hesselink and Jos BTM Roerdink. 2008. Euclidean skeletons of digital image and volume data in linear time by the integer medial axis transform. IEEE Transactions on Pattern Analysis and Machine Intelligence 30, 12 (2008), 2204–2217. Google ScholarDigital Library
21. Christoph M Hoffmann. 1990. How to construct the skeleton of CSG objects. (1990).Google Scholar
22. Andrei C Jalba, Jacek Kustra, and Alexandru C Telea. 2013. Surface and curve skeletonization of large 3D models on the GPU. IEEE transactions on pattern analysis and machine intelligence 35, 6 (2013), 1495–1508. Google ScholarDigital Library
23. Andrei C Jalba, Andre Sobiecki, and Alexandru C Telea. 2016. An unified multiscale framework for planar, surface, and curve skeletonization. IEEE transactions on pattern analysis and machine intelligence 38, 1 (2016), 30–45. Google ScholarDigital Library
24. Tao Ju. 2004. Robust repair of polygonal models. ACM Transactions on Graphics (TOG) 23, 3 (2004), 888–895. Google ScholarDigital Library
25. Reinhard Klette and Azriel Rosenfeld. 2004. Digital geometry: Geometric methods for digital picture analysis. Elsevier. Google ScholarDigital Library
26. Jacques-Olivier Lachaud and Boris Thibert. 2016. Properties of gauss digitized shapes and digital surface integration. Journal of Mathematical Imaging and Vision 54, 2 (2016), 162–180. Google ScholarDigital Library
27. Yong-Gu Lee and Kunwoo Lee. 1997. Computing the medial surface of a 3-D boundary representation model. Advances in Engineering Software 28, 9 (1997), 593–605. Google ScholarDigital Library
28. Pan Li, Bin Wang, Feng Sun, Xiaohu Guo, Caiming Zhang, and Wenping Wang. 2015. Q-MAT: Computing Medial Axis Transform By Quadratic Error Minimization. ACM Trans. Graph. 35, 1 (Dec. 2015), 8:1–8:16. Google ScholarDigital Library
29. André Lieutier. 2003. Any Open Bounded Subset of Rn Has the Same Homotopy Type Than Its Medial Axis. In Proceedings of the Eighth ACM Symposium on Solid Modeling and Applications (SM ’03). 65–75. Google ScholarDigital Library
30. L. Liu, Erin W. Chambers, David Letscher, and T. Ju. 2010. A simple and robust thinning algorithm on cell complexes. Comput. Graph. Forum 29, 7 (2010), 2253–2260.Google ScholarCross Ref
31. Jaehwan Ma, Sang Won Bae, and Sunghee Choi. 2012. 3D medial axis point approximation using nearest neighbors and the normal field. The Visual Computer 28, 1 (2012), 7–19. Google ScholarDigital Library
32. Balint Miklos, Joachim Giesen, and Mark Pauly. 2010. Discrete Scale Axis Representations for 3D Geometry. ACM Trans. Graph. 29, 4 (July 2010), 101:1–101:10. Google ScholarDigital Library
33. Victor Milenkovic. 1993. Robust Construction of the Voronoi Diagram of a Polyhedron.. In CCCG, Vol. 93. 473–478.Google Scholar
34. Suraj Musuvathy, Elaine Cohen, and James Damon. 2011. Computing medial axes of generic 3D regions bounded by B-spline surfaces. Computer-Aided Design 43, 11 (2011), 1485–1495. Google ScholarDigital Library
35. Kálmán Palágyi and Attila Kuba. 1999. A parallel 3D 12-subiteration thinning algorithm. Graphical Models and Image Processing 61, 4 (1999), 199–221. Google ScholarDigital Library
36. Chris Pudney. 1998. Distance-ordered homotopic thinning: a skeletonization algorithm for 3D digital images. Computer Vision and Image Understanding 72, 3 (1998), 404–413. Google ScholarDigital Library
37. M Ramanathan and B Gurumoorthy. 2010. Interior Medial Axis Transform computation of 3D objects bound by free-form surfaces. Computer-Aided Design 42, 12 (2010), 1217–1231. Google ScholarDigital Library
38. Dennie Reniers, Jarke van Wijk, and Alexandru Telea. 2008. Computing Multiscale Curve and Surface Skeletons of Genus 0 Shapes Using a Global Importance Measure. IEEE Transactions on Visualization and Computer Graphics 14, 2 (2008), 355–368. Google ScholarDigital Library
39. Martin Rumpf and Alexandru Telea. 2002. A continuous skeletonization method based on level sets. In Proceedings of the symposium on Data Visualisation 2002. Eurographics Association, 151–ff. Google ScholarDigital Library
40. Punam K Saha, Gunilla Borgefors, and Gabriella Sanniti di Baja. 2016. A survey on skeletonization algorithms and their applications. Pattern Recognition Letters 76 (2016), 3–12. Google ScholarDigital Library
41. Punam K. Saha and Bidyut Baran Chaudhuri. 1994. Detection of 3-D simple points for topology preserving transformations with application to thinning. IEEE transactions on pattern analysis and machine intelligence 16, 10 (1994), 1028–1032. Google ScholarDigital Library
42. Evan C. Sherbrooke, Nicholas M. Patrikalakis, and Erik Brisson. 1996. An Algorithm for the Medial Axis Transform of 3D Polyhedral Solids. IEEE Transactions on Visualization and Computer Graphics 2, 1 (1996), 44–61. Google ScholarDigital Library
43. Hang Si. 2015. TetGen, a Delaunay-based quality tetrahedral mesh generator. ACM Transactions on Mathematical Software (TOMS) 41, 2 (2015), 11. Google ScholarDigital Library
44. Kaleem Siddiqi, Sylvain Bouix, Allen Tannenbaum, and Steven W. Zucker. 2002. Hamilton-Jacobi Skeletons. International Journal of Computer Vision 48, 3 (July 2002), 215–231. Google ScholarDigital Library
45. Kaleem Siddiqi and Stephen M. Pizer. 2008. Medial Representations. Springer.Google Scholar
46. André Sobiecki, Andrei Jalba, and Alexandru Telea. 2014. Comparison of curve and surface skeletonization methods for voxel shapes. Pattern Recognition Letters 47 (2014), 147–156. Google ScholarDigital Library
47. Peer Stelldinger, Longin Jan Latecki, and Marcelo Siqueira. 2007. Topological equivalence between a 3D object and the reconstruction of its digital image. IEEE transactions on pattern analysis and machine intelligence 29, 1 (2007). Google ScholarDigital Library
48. Svetlana Stolpner and Kaleem Siddiqi. 2006. Revealing significant medial structure in polyhedral meshes. In 3D Data Processing, Visualization, and Transmission, Third International Symposium on. IEEE, 365–372. Google ScholarDigital Library
49. Avneesh Sud, Liangjun Zhang, and Dinesh Manocha. 2006. Homotopy Preserving Approximate Voronoi Diagram of 3D Polyhedron. Technical Report. Technical report.Google Scholar
50. Andrea Tagliasacchi, T. Delame, M. Spagnuolo, N. Amenta, and A. Telea. 2016. 3D Skeletons: A State-of-the-Art Report. In Eurographics. Google ScholarDigital Library
51. Roger C. Tam and Wolfgang Heidrich. 2003. Shape Simplification Based on the Medial Axis Transform. In 14th IEEE Visualization 2003 Conference (VIS 2003), 19-24 October 2003, Seattle, WA, USA. 481–488. Google ScholarDigital Library
52. YF Tsao and King Sun Fu. 1981. A parallel thinning algorithm for 3-D pictures. Computer graphics and image processing 17, 4 (1981), 315–331.Google Scholar
53. Yajie Yan, Kyle Sykes, Erin Chambers, David Letscher, and Tao Ju. 2016. Erosion thickness on medial axes of 3D shapes. ACM Transactions on Graphics (TOG) 35, 4 (2016), 38. Google ScholarDigital Library
