“3D skeletonization using an enhanced voxel tree” by Yang and Cheng

  • ©Xing-Dong Yang and Irene Cheng

  • ©Xing-Dong Yang and Irene Cheng

  • ©Xing-Dong Yang and Irene Cheng




    3D skeletonization using an enhanced voxel tree



    Although mesh mapped with texture is observed by viewers, skeleton is often used as a compact and simplified form to represent a complex 3D object for backend processing, e.g. animation, similarity match from database, shape comparison and perceptual evaluation [ZY96][CGC*02][HK00], because the original object is too computationally expensive to analyze given time constraints and limited resources. Many skeletonization algorithms have been discussed in the literature including the medial axis and thinning approaches [BO04][PSB01]. However, these algorithms may not generate a stable skeleton. These techniques either focus on a volume, e.g. medical DICOM data, or mesh data. Our skeletonization method using voxels is stable and can be used for both mesh and volume data. Figure 1 shows (a) the original 3D horse model, (b) model covered with voxels on the surface after three iterations, and (c) the tightly bound voxels after running six iterations of our algorithm, giving a good approximation of the horse.  


    1. {BKO*00} M. Berg, M. Kreveld, M. Overmars and O. Schwarzkopf, “Computational Geometry,” Springer, 2nd edition, pp 147–163.]]
    2. {BO02} G. Bradshaw and C. O’Sullivan, “Sphere-Tree Construction using Medial-Axis Approximation,” In Proc. of SIGGRAPH 2002.]]
    3. {BO04} G. Bradshaw and C. O’Sullivan, “Adaptive Medial-axis Approximation for Sphere-Tree Construction,” ACM Transaction on Graphics, 23(1) Jan 2004.]]
    4. {CGC*02} S. Capell, S. Green, B. Curless, T. Duchamp and Z. Popovic, “Interactive Skeleton-Driven Dynamic Deformations,” In Proc. of SIGGRAPH 2002.]]
    5. {HK00} C. Holleman and L. Kavraki, “A Framework for using the Workspace Medial Axis in prm Planners,” In Proc. of the 2000 IEEE Int. Conf. on Robotics and Automation, Vol.2, pp1408–1412, Apr 2000.]]
    6. {PSB*01} K. Palagyi, E. Sorantin, E. Balogh, et al., “A Sequential 3D Thinning Algorithm and Its Medical Applications,” Springer-Verlag Berlin Heidelberg IPMI 2001, pp.409–415.]]
    7. {ZY96} S. Zhu and A. Yuille, “Form: A Flexible Object Recognition and Modeling System,” Int Journal of Computer Vision, 20(3):187–212, 1996.]]

ACM Digital Library Publication:

Overview Page: