“Erosion thickness on medial axes of 3D shapes”
Conference:
Type(s):
Title:
- Erosion thickness on medial axes of 3D shapes
Session/Category Title: GEOMETRY
Presenter(s)/Author(s):
Moderator(s):
Abstract:
While playing a fundamental role in shape understanding, the medial axis is known to be sensitive to small boundary perturbations. Methods for pruning the medial axis are usually guided by some measure of significance. The majority of significance measures over the medial axes of 3D shapes are locally defined and hence unable to capture the scale of features. We introduce a global significance measure that generalizes in 3D the classical Erosion Thickness (ET) measure over the medial axes of 2D shapes. We give precise definition of ET in 3D, analyze its properties, and present an efficient approximation algorithm with bounded error on a piece-wise linear medial axis. Experiments showed that ET outperforms local measures in differentiating small boundary noise from prominent shape features, and it is significantly faster to compute than existing global measures. We demonstrate the utility of ET in extracting clean, shape-revealing and topology-preserving skeletons of 3D shapes.
References:
1. Amenta, N., and Kolluri, R. K. 2001. The medial axis of a union of balls. Comput. Geom. 20, 1-2, 25–37. Google ScholarDigital Library
2. Amenta, N., Choi, S., and Kolluri, R. K. 2001. The power crust. In SMA ’01: Proceedings of the sixth ACM symposium on Solid modeling and applications, 249–266. Google ScholarDigital Library
3. Arcelli, C., and di Baja, G. S. 1993. Euclidean skeleton via centre-of-maximal-disc extraction. Image Vision Comput. 11, 3, 163–173.Google ScholarCross Ref
4. Attali, D., and Montanvert, A. 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 Scholar
5. Attali, D., di Baja, G. S., and Thiel, E. 1995. Pruning discrete and semiocontinuous skeletons. In Image Analysis and Processing, 8th International Conference, ICIAP ’95, San Remo, Italy, September 13-15, 1995, Proceedings, 488–493. Google ScholarDigital Library
6. Bertrand, G. 1995. A parallel thinning algorithm for medial surfaces. Pattern Recogn. Lett. 16, 9. Google ScholarDigital Library
7. Blum, H. 1967. A transformation for extracting new descriptors of form. Models for the Perception of Speech and Visual Form, 362–80.Google Scholar
8. Blum, H. 1973. Biological shape and visual science (part i). Journal of Theoretical Biology 38, 2, 205–287.Google ScholarCross Ref
9. Brandt, J., and Algazi, V. 1992. Continuous skeleton computation by voronoi diagram. CVGIP: Image Understanding 55, 3, 329–338. Google ScholarDigital Library
10. Chaussard, J., Couprie, M., and Talbot, H. 2009. A discrete lambda-medial axis. In DGCI, vol. 5810, 421–433. Google ScholarDigital Library
11. Chazal, F., and Lieutier, A. 2004. Stability and homotopy of a subset of the medial axis. In Proceedings of the Ninth ACM Symposium on Solid Modeling and Applications, SM ’04, 243–248. Google ScholarDigital Library
12. Chazal, F., and Soufflet, R. 2003. Stability and finiteness properties of medial axis and skeleton. Journal of Dynamical and Control Systems 10, 2, 149–170. Google ScholarDigital Library
13. Choi, S. W., and Seidel, H.-P. 2001. Hyperbolic hausdorff distance for medial axis transform. Graph. Models 63, 5 (Sept.), 369–384. Google ScholarDigital Library
14. Cornea, N. D., and Min, P. 2007. Curve-skeleton properties, applications, and algorithms. IEEE Transactions on Visualization and Computer Graphics 13, 3, 530–548. Member-Silver, Deborah. Google ScholarDigital Library
15. Crane, K., Weischedel, C., and Wardetzky, M. 2013. Geodesics in heat: A new approach to computing distance based on heat flow. ACM Trans. Graph. 32, 5 (Oct.), 152:1–152:11. Google ScholarDigital Library
16. Culver, T., Keyser, J., and Manocha, D. 2004. Exact computation of the medial axis of a polyhedron. Computer Aided Geometric Design 21, 1, 65–98. Google ScholarDigital Library
17. Dey, T. K., and Sun, J. 2006. Defining and computing curve-skeletons with medial geodesic function. In SGP ’06: Proceedings of the fourth Eurographics symposium on Geometry processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 143–152. Google ScholarDigital Library
18. Dey, T. K., and Zhao, W. 2004. Approximate medial axis as a voronoi subcomplex. Computer-Aided Design 36, 2, 195–202.Google ScholarCross Ref
19. Dill, A. R., Levine, M. D., and Noble, P. B. 1987. Multiple resolution skeletons. IEEE Trans. Pattern Anal. Mach. Intell. 9, 4, 495–504. Google ScholarDigital Library
20. Fletcher, P. T., Lu, C., Pizer, S. M., and Joshi, S. C. 2004. Principal geodesic analysis for the study of nonlinear statistics of shape. IEEE Trans. Med. Imaging 23, 8, 995–1005.Google ScholarCross Ref
21. Foskey, M., Lin, M. C., and Manocha, D. 2003. Efficient computation of A simplified medial axis. J. Comput. Inf. Sci. Eng. 3, 4, 274–284.Google ScholarCross Ref
22. Giblin, P. J., and Kimia, B. B. 2004. A formal classification of 3d medial axis points and their local geometry. IEEE Trans. Pattern Anal. Mach. Intell. 26, 2, 238–251. Google ScholarDigital Library
23. Giesen, J., Miklos, B., Pauly, M., and Wormser, C. 2009. The scale axis transform. In Proceedings of the Twenty-fifth Annual Symposium on Computational Geometry, SCG ’09, 106–115. Google ScholarDigital Library
24. Golland, P., Eric, W., and Grimson, L. 2000. Fixed topology skeletons. In Computer Vision and Pattern Recognition, 2000. Proceedings. IEEE Conference on, vol. 1, 10–17 vol. 1.Google Scholar
25. Ho, S.-B., and Dyer, C. R. 1986. Shape smoothing using medial axis properties. IEEE Transactions on Pattern Analysis and Machine Intelligence 8, 4, 512–520. Google ScholarDigital Library
26. Lanthier, M., Maheshwari, A., and Sack, J.-R. 1997. Approximating weighted shortest paths on polyhedral surfaces. In Proceedings of the Thirteenth Annual Symposium on Computational Geometry, SCG ’97, 485–486. Google ScholarDigital Library
27. Li, P., Wang, B., Sun, F., Guo, X., Zhang, C., and Wang, W. 2015. Q-mat: Computing medial axis transform by quadratic error minimization. ACM Trans. Graph. 35, 1 (Dec.), 8:1–8:16. Google ScholarDigital Library
28. Lieutier, A. 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
29. Liu, L., Chambers, E. W., Letscher, D., and Ju, T. 2010. A simple and robust thinning algorithm on cell complexes. Comput. Graph. Forum 29, 7, 2253–2260.Google ScholarCross Ref
30. Liu, L., Chambers, E. W., Letscher, D., and Ju, T. 2011. Extended grassfire transform on medial axes of 2d shapes. Computer-Aided Design 43, 11, 1496–1505. Google ScholarDigital Library
31. Miklos, B., Giesen, J., and Pauly, M. 2010. Discrete scale axis representations for 3d geometry. ACM Trans. Graph. 29, 4 (July), 101:1–101:10. Google ScholarDigital Library
32. Niblack, W., Gibbons, P., and Capson, D. 1992. Generating connected skeletons for exact and approximate reconstruction. In Computer Vision and Pattern Recognition, 1992. Proceedings CVPR ’92., 1992 IEEE Computer Society Conference on, 826–828.Google Scholar
33. Ogniewicz, R., and Ilg, M. 1992. Voronoi skeletons: theory and applications. In Computer Vision and Pattern Recognition, 1992. Proceedings CVPR ’92., 1992 IEEE Computer Society Conference on, 63–69.Google Scholar
34. Ogniewicz, R. L., and Kübler, O. 1995. Hierarchic voronoi skeletons. Pattern Recognition 28, 3, 343–359.Google ScholarCross Ref
35. Pizer, S. M., Oliver, W. R., and Bloomberg, S. H. 1987. Hierarchical shape description via the multiresolution symmetric axis transform. IEEE Trans. Pattern Anal. Mach. Intell. 9, 4, 505–511. Google ScholarDigital Library
36. Pizer, S. M., Fletcher, P. T., Joshi, S. C., Thall, A., Chen, J. Z., Fridman, Y., Fritsch, D. S., Gash, A. G., Glotzer, J. M., Jiroutek, M. R., Lu, C., Muller, K. E., Tracton, G., Yushkevich, P. A., and Chaney, E. L. 2003. Deformable m-reps for 3d medical image segmentation. International Journal of Computer Vision 55, 2-3, 85–106. Google ScholarDigital Library
37. Pizer, S. M., Gerig, G., Joshi, S. C., and Aylward, S. R. 2003. Multiscale medial shape-based analysis of image objects. Proceedings of the IEEE 91, 10, 1670–1679.Google ScholarCross Ref
38. Reniers, D., van Wijk, J., and Telea, A. 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, 355–368. Google ScholarDigital Library
39. Shaked, D., and Bruckstein, A. M. 1998. Pruning medial axes. Comput. Vis. Image Underst. 69, 2, 156–169. Google ScholarDigital Library
40. Siddiqi, K., and Pizer, S. M. 2008. Medial Representations. Springer.Google Scholar
41. Siddiqi, K., Bouix, S., Tannenbaum, A., and Zucker, S. W. 2002. Hamilton-jacobi skeletons. International Journal of Computer Vision 48, 3 (July), 215–231. Google ScholarDigital Library
42. Styner, M., Gerig, G., Joshi, S. C., and Pizer, S. M. 2003. Automatic and robust computation of 3d medial models incorporating object variability. International Journal of Computer Vision 55, 2-3, 107–122. Google ScholarDigital Library
43. Sud, A., Foskey, M., and Manocha, D. 2005. Homotopy-preserving medial axis simplification. In SPM ’05: Proceedings of the 2005 ACM symposium on Solid and physical modeling, ACM, New York, NY, USA, 39–50. Google ScholarDigital Library
44. Tagliasacchi, A., Delame, T., Spagnuolo, M., Amenta, N., and Telea, A. 2016. 3d skeletons: A state-of-the-art report. In Eurographics.Google Scholar
45. Tam, R. C., and Heidrich, W. 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
