Simultaneous shape decomposition and skeletonization

ABSTRACT

Shape decomposition and skeletonization share many common properties and applications. However, they are generally treated as independent computations. In this paper, we propose an iterative approach that simultaneously generates a hierarchical shape decomposition and a corresponding set of multi-resolution skeletons. In our method, a skeleton of a model is extracted from the components of its decomposition --- that is, both processes and the qualities of their results are interdependent. In particular, if the quality of the extracted skeleton does not meet some user specified criteria, then the model is decomposed into finer components and a new skeleton is extracted from these components. The process of simultaneous shape decomposition and skeletonization iterates until the quality of the skeleton becomes satisfactory. We provide evidence that the proposed framework is efficient and robust under perturbation and. deformation. We also demonstrate that our results can readily be used in problems including skeletal deformations and virtual reality navigation.

REFERENCES

• 1: Amenta, N., Choi, S., and Kolluri, R. K. 2001. The power crust, unions of balls, and the medial axis transform. Computational Geometry 19, 2--3, 127--153.
• 2: Amenta, N., Choi, S., Jump, M. E., Kolluri, R. K., and Wahl, T. 2002. Finding alpha-helices in skeletons. Tech. rep., Dept. of Computer Science, University of Texas at Austin.
• 3: Attali, D., and Lachaud, J.-O. 2001. Delaunay conforming isosurface; skeleton extraction and noise removal. Computational Geometry: Theory and Applications 19, 2--3, 175--189.
• 4: Attali, D., Bertolino, P., and Montanvert, A. 1994. Using polyballs to approximate shapes and skeletons. In Proceedings of International Conference on Pattern Recognition (ICPR'94), 626--628.
• 5: Marco Attene , Silvia Biasotti , Michela Spagnuolo, Re-Meshing Techniques for Topological Analysis, Proceedings of the International Conference on Shape Modeling & Applications, p.142, May 07-11, 2001
• 6: Jérô Barraquand , Lydia Kavraki , Jean-Claude Latombe , Rajeev Motwani , Tsai-Yen Li , Prabhakar Raghavan, A random sampling scheme for path planning, International Journal of Robotics Research, v.16 n.6, p.759-774, Dec. 1997 [doi>10.1177/027836499701600604]
• 7: Biederman, I. 1987. Recognition-by-components: a theory of human image understanding. Psychol. Rev. 94, 2, 115--147.
• 8: Ingmar Bitter , Arie E. Kaufman , Mie Sato, Penalized-Distance Volumetric Skeleton Algorithm, IEEE Transactions on Visualization and Computer Graphics, v.7 n.3, p.195-206, July 2001 [doi>10.1109/2945.942688 ]
• 9: Blum, H. 1967. A transformation for extracting new descriptors of shape. In Models for the Perception of Speech and Visual Form, W. Wathen-Dunn, Ed. MIT Press, 362--380.
• 10: Gareth Bradshaw , Carol O'Sullivan, Sphere-tree construction using dynamic medial axis approximation, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545267]
• 11: H. Bunke , A. Kandel, Mean and maximum common subgraph of two graphs, Pattern Recognition Letters, v.21 n.2, p.163-168, Feb. 2000 [doi>10.1016/S0167-8655(99)00143-9 ]
• 12: Steve Capell , Seth Green , Brian Curless , Tom Duchamp , Zoran Popović, Interactive skeleton-driven dynamic deformations, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 13: Jen-Hi Chuang , Chi-Hao Tsai , Min-Chi Ko, Skeletonization of Three-Dimensional Object Using Generalized Potential Field, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.11, p.1241-1251, November 2000 [doi>10.1109/34.888709 ]
• 14: Tim Culver , John Keyser , Dinesh Manocha, Exact computation of the medial axis of a polyhedron, Computer Aided Geometric Design, v.21 n.1, p.65-98, January 2004 [doi>10.1016/j.cagd.2003.07.008]
• 15: Cyr, C. M., and Kimia, B. B. 2001. 3d object recognition using shape similarity-based aspect graph. In ICCV'01.
• 16: Tamal K. Dey , Wulue Zhao, Approximate medial axis as a voronoi subcomplex, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany [doi>10.1145/566282.566333]
• 17: Dey, T. K., Giesen, J., and Goswami, S. 2003. Shape segmentation and matching with flow discretization. In Proc. Workshop on Algorithms and Data Structures, 25--36.
• 18: Thomas Funkhouser , Michael Kazhdan , Philip Shilane , Patrick Min , William Kiefer , Ayellet Tal , Szymon Rusinkiewicz , David Dobkin, Modeling by example, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 19: Masaki Hilaga , Yoshihisa Shinagawa , Taku Kohmura , Tosiyasu L. Kunii, Topology matching for fully automatic similarity estimation of 3D shapes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.203-212, August 2001 [doi>10.1145/383259.383282]
• 20: Hoffman, D., and Richards, W. 1984. Parts of recognition. Cognition 18, 65--96.
• 21: Hoffman, D., and Singh, M. 1997. Salience of visual parts. Cognition 63, 29--78.
• 22: Philip M. Hubbard, Approximating polyhedra with spheres for time-critical collision detection, ACM Transactions on Graphics (TOG), v.15 n.3, p.179-210, July 1996 [doi>10.1145/231731.231732]
• 23: Sagi Katz , Ayellet Tal, Hierarchical mesh decomposition using fuzzy clustering and cuts, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 24: Kavraki, L. E., Svestka, P., Latombe, J. C., and Overmars, M. H. 1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Automat. 12, 4 (August), 566--580.
• 25: Yunjin Lee , Seungyong Lee , Ariel Shamir , Daniel Cohen-Or , Hans-Peter Seidel, Intelligent Mesh Scissoring Using 3D Snakes, Proceedings of the Computer Graphics and Applications, 12th Pacific Conference on (PG'04), p.279-287, October 06-08, 2004
• 26: Tsai-Yen Li , Jyh-Ming Lien , Shih-Yen Chiu , Tzong-Hann Yu, Automatically Generating Virtual Guided Tours, Proceedings of the Computer Animation, p.99, May 26-28, 1999
• 27: Xuetao Li , Tong Wing Toon , Zhiyong Huang, Decomposing polygon meshes for interactive applications, Proceedings of the 2001 symposium on Interactive 3D graphics, p.35-42, March 2001 [doi>10.1145/364338.364343]
• 28: Jyh-Ming Lien , Nancy M. Amato, Approximate convex decomposition of polygons, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997823]
• 29: Lien, J.-M., and Amato, N. M. 2006. Approximate convex decomposition of polyhedra. Tech. Rep. TR06-002, Parasol Lab, Dept. of Computer Science, Texas A&M University, Jan.
• 30: Rong Liu , Hao Zhang, Segmentation of 3D Meshes through Spectral Clustering, Proceedings of the Computer Graphics and Applications, 12th Pacific Conference on (PG'04), p.298-305, October 06-08, 2004
• 31: Lu, Y., Gadh, R., and Tautges, T. J. 1999. Volume decomposition and feature recognition for hexahedral mesh generation. In Proc. 8th International Meshing Roundtable, 269--280.
• 32: Alan P. Mangan , Ross T. Whitaker, Partitioning 3D Surface Meshes Using Watershed Segmentation, IEEE Transactions on Visualization and Computer Graphics, v.5 n.4, p.308-321, October 1999 [doi>10.1109/2945.817348 ]
• 33: Ogniewicz, R., and Kubler, O. 1995. Hierarchic voronoi skeletons. Pattern Recognition 28, 3, 343--359.
• 34: Page, D. L., Koschan, A. F., and Abidi, M. A. 2003. Perception-based 3d triangle mesh segmentation using fast marching watersheds. In Proceedings of the 2003 Conference on Computer Vision and Pattern Recognition (CVPR '03), 27--32.
• 35: Roman M. Palenichka , Marek B. Zaremba, Multi-Scale Model-Based Skeletonization of Object Shapes Using Self-Organizing Maps, Proceedings of the 16 th International Conference on Pattern Recognition (ICPR'02) Volume 1, p.10143, August 11-15, 2002
• 36: H. Rom , G. Medioni, Hierarchical Decomposition and Axial Shape Description, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.10, p.973-981, October 1993 [doi>10.1109/34.254054 ]
• 37: Rom, H., and Medioni, G. 1994. Part decomposition and description of 3d shapes. In Proc. International Conference of Pattern Recognition, 629--632.
• 38: P. V. Sander , Z. J. Wood , S. J. Gortler , J. Snyder , H. Hoppe, Multi-chart geometry images, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 39: Damian J. Sheehy , Cecil G. Armstrong , Desmond J. Robinson, Shape Description By Medial Surface Construction, IEEE Transactions on Visualization and Computer Graphics, v.2 n.1, p.62-72, March 1996 [doi>10.1109/2945.489387 ]
• 40: Yoshihisa Shinagawa , Tosiyasu L. Kunii, Constructing a Reeb graph automatically from cross sections, IEEE Computer Graphics and Applications, v.11 n.6, p.44-51, November 1991 [doi>10.1109/38.103393 ]
• 41: Yoshihisa Shinagawa , Tosiyasu L. Kunii , Yannick L. Kergosien, Surface Coding Based on Morse Theory, IEEE Computer Graphics and Applications, v.11 n.5, p.66-78, September 1991 [doi>10.1109/38.90568 ]
• 42: Kaleem Siddiqi , Ali Shokoufandeh , Sven J. Dickinson , Steven W. Zucker, Shock Graphs and Shape Matching, Proceedings of the Sixth International Conference on Computer Vision, p.222, January 04-07, 1998
• 43: Marek Teichmann , Seth Teller, Assisted articulation of closed polygonal models, ACM SIGGRAPH 98 Conference abstracts and applications, p.254, July 19-24, 1998, Orlando, Florida, United States [doi>10.1145/280953.282217]
• 44: A Verroust , F. Lazarus, Extracting Skeletal Curves from 3D Scattered Data, Proceedings of the International Conference on Shape Modeling and Applications, p.194, March 01-04, 1999
• 45: Steven A. Wilmarth , Nancy M. Amato , Peter F. Stiller, Motion planning for a rigid body using random networks on the medial axis of the free space, Proceedings of the fifteenth annual symposium on Computational geometry, p.173-180, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304967]
• 46: Kenong Wu , Martin D. Levine, 3D Part Segmentation Using Simulated Electrical Charge Distributions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.11, p.1223-1235, November 1997 [doi>10.1109/34.632982 ]
• 47: Wu, F.-C., Ma, W.-C., Liou, P.-C., Laing, R.-H., and Ouhy-Oung, M. 2003. Skeleton extraction of 3d objects with visible repulsive force. In Computer Graphics Workshop 2003, HuaLien, Taiwan.
• 48: Geoff Wyvill , Chris Handley, The 'Thermodynamics' of Shape, Proceedings of the International Conference on Shape Modeling & Applications, p.2, May 07-11, 2001
• 49: Yong Zhou , Arthur W. Toga, Efficient Skeletonization of Volumetric Objects, IEEE Transactions on Visualization and Computer Graphics, v.5 n.3, p.196-209, July 1999 [doi>10.1109/2945.795212 ]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Keywords:
convex decomposition, multi-resolution skeleton, skeletonization