Curve skeleton extraction from incomplete point cloud

ABSTRACT

We present an algorithm for curve skeleton extraction from imperfect point clouds where large portions of the data may be missing. Our construction is primarily based on a novel notion of generalized rotational symmetry axis (ROSA) of an oriented point set. Specifically, given a subset S of oriented points, we introduce a variational definition for an oriented point that is most rotationally symmetric with respect to S. Our formulation effectively utilizes normal information to compensate for the missing data and leads to robust curve skeleton computation over regions of a shape that are generally cylindrical. We present an iterative algorithm via planar cuts to compute the ROSA of a point cloud. This is complemented by special handling of non-cylindrical joint regions to obtain a centered, topologically clean, and complete 1D skeleton. We demonstrate that quality curve skeletons can be extracted from a variety of shapes captured by incomplete point clouds. Finally, we show how our algorithm assists in shape completion under these challenges by developing a skeleton-driven point cloud completion scheme.

REFERENCES

• 1: Nina Amenta , Yong Joo Kil, Defining point-set surfaces, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 2: Oscar Kin-Chung Au , Chiew-Lan Tai , Hung-Kuo Chu , Daniel Cohen-Or , Tong-Yee Lee, Skeleton extraction by mesh contraction, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 3: Blum, H. 1967. A transformation for extracting new descriptors of shape. Models for the perception of speech and visual form. MIT Press, 362--380.
• 4: Bouix, S., Siddiqi, K., Tannenbaum, A., and Zucker, S. 2006. Medial axis computation and evolution. Statistics and Analysis of Shapes.
• 5: J. C. Carr , R. K. Beatson , J. B. Cherrie , T. J. Mitchell , W. R. Fright , B. C. McCallum , T. R. Evans, Reconstruction and representation of 3D objects with radial basis functions, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.67-76, August 2001 [doi>10.1145/383259.383266]
• 6: Chuang, J.-H., Ahuja, N., Lin, C.-C., Tsai, C.-H., and Chen, C.-H. 2004. A potential-based generalized cylinder representation. Computers & Graphics 28, 6, 907--918.
• 7: Nicu D. Cornea , Deborah Silver , Patrick Min, Curve-Skeleton Properties, Applications, and Algorithms, IEEE Transactions on Visualization and Computer Graphics, v.13 n.3, p.530-548, May 2007 [doi>10.1109/TVCG.2007.1002]
• 8: de Aguiar, E., Theobalt, C., Thrun, S., and Seidel, H.-P. 2008. Automatic conversion of mesh animations into skeleton-based animations. Computer Graphics Forum (Proc. of Eurographics) 27, 2 (4), 389--397.
• 9: Tamal K. Dey , Jian Sun, Defining and computing curve-skeletons with medial geodesic function, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 10: Giblin, P. J., and Brassett, S. A. 1985. Local symmetry of plane curves. American Mathematical Monthly, 689--707.
• 11: 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]
• 12: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.71-78, July 1992
• 13: Doug L. James , Christopher D. Twigg, Skinning mesh animations, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 14: Sagi Katz , Ayellet Tal, Hierarchical mesh decomposition using fuzzy clustering and cuts, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 15: Michael Kazhdan , Thomas Funkhouser , Szymon Rusinkiewicz, Symmetry descriptors and 3D shape matching, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057448]
• 16: Michael Kazhdan , Matthew Bolitho , Hugues Hoppe, Poisson surface reconstruction, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 17: Young J. Kim , Gokul Varadhan , Ming C. Lin , Dinesh Manocha, Fast swept volume approximation of complex polyhedral models, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781613]
• 18: In-Kwon Lee, Curve reconstruction from unorganized points, Computer Aided Geometric Design, v.17 n.2, p.161-177, Feb. 2000 [doi>10.1016/S0167-8396(99)00044-8]
• 19: Jaakko Lehtinen , Matthias Zwicker , Emmanuel Turquin , Janne Kontkanen , Frédo Durand , François X. Sillion , Timo Aila, A meshless hierarchical representation for light transport, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 20: J. P. Lewis , Matt Cordner , Nickson Fong, Pose space deformation: a unified approach to shape interpolation and skeleton-driven deformation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.165-172, July 2000 [doi>10.1145/344779.344862]
• 21: Xuetao Li , Tong Wing Woon , Tiow Seng Tan , 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]
• 22: Yaron Lipman , Daniel Cohen-Or , David Levin , Hillel Tal-Ezer, Parameterization-free projection for geometry reconstruction, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 23: Lu, L., Choi, Y.-K., Wang, W., and Kim, M.-S. 2007. Variational 3D shape segmentation for bounding volume computation. Computer Graphics Forum (Proc. of Eurographics) 26, 3, 329--338.
• 24: Malandain, G., and Fernández-Vidal, S. 1998. Euclidean skeletons. Image and Vision Computing 16, 5, 317--327.
• 25: Niloy J. Mitra , Leonidas J. Guibas , Mark Pauly, Partial and approximate symmetry detection for 3D geometry, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 26: Niloy J. Mitra , Simon Flöry , Maks Ovsjanikov , Natasha Gelfand , Leonidas Guibas , Helmut Pottmann, Dynamic geometry registration, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
• 27: Diego Nehab , Szymon Rusinkiewicz , James Davis , Ravi Ramamoorthi, Efficiently combining positions and normals for precise 3D geometry, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 28: Ogniewicz, R., Ilg, M., and Zurich, E. 1992. Voronoi skeletons: theory and applications. In Proc. IEEE Conf. on Comp. Vis. and Pat. Rec., 63--69.
• 29: Ovsjanikov, M., Sun, J., and Guibas, L. 2008. Global intrinsic symmetries of shapes. In Computer Graphics Forum (Proc. of Symp. on Geom. Proc.), vol. 27, 1341--1348.
• 30: Patane, G., Spagnuolo, M., and Falcidieno, B. 2008. Reeb graph computation based on a minimal contouring. In Proc. IEEE Conf. on Shape Modeling and App., 73--82.
• 31: Pekelny, Y., and Gotsman, C. 2008. Articulated object reconstruction and motion capture from depth video. Computer Graphics Forum (Proc. of Eurographics) 27, 2, 399--408.
• 32: Joshua Podolak , Philip Shilane , Aleksey Golovinskiy , Szymon Rusinkiewicz , Thomas Funkhouser, A planar-reflective symmetry transform for 3D shapes, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 33: Raab, R., Gotsman, C., and Sheffer, A. 2004. Virtual woodwork: Making toys from geometric models. Int. J. of Shape Modeling 10, 1, 1--30.
• 34: Sharf, A., Lewiner, T., Shamir, A., and Kobbelt, L. 2007. On-the-fly curve-skeleton computation for 3D shapes. Computer Graphics Forum (Proc. of Eurographics) 26, 3, 323--328.
• 35: Andrei Sharf , Thomas Lewiner , Gil Shklarski , Sivan Toledo , Daniel Cohen-Or, Interactive topology-aware surface reconstruction, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 36: Andrei Sharf , Dan A. Alcantara , Thomas Lewiner , Chen Greif , Alla Sheffer , Nina Amenta , Daniel Cohen-Or, Space-time surface reconstruction using incompressible flow, ACM Transactions on Graphics (TOG), v.27 n.5, December 2008
• 37: Kaleem Siddiqi , Stephen Pizer, Medial Representations: Mathematics, Algorithms and Applications, Springer Publishing Company, Incorporated, 2008
• 38: Patricio D. Simari , Karan Singh, Extraction and remeshing of ellipsoidal representations from mesh data, Proceedings of Graphics Interface 2005, May 09-11, 2005, Victoria, British Columbia
• 39: Least-Squares Meshes, Proceedings of the Shape Modeling International 2004, p.191-199, June 07-09, 2004 [doi>10.1109/SMI.2004.38]
• 40: Sebastian Thrun , Ben Wegbreit, Shape from Symmetry, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.1824-1831, October 17-20, 2005 [doi>10.1109/ICCV.2005.221]
• 41: Michael Wand , Philipp Jenke , Qixing Huang , Martin Bokeloh , Leonidas Guibas , Andreas Schilling, Reconstruction of deforming geometry from time-varying point clouds, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Edge and feature detection
      I.4.7 Feature Measurement
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

General Terms:
Algorithms, Design, Measurement

Keywords:
curve skeleton, incomplete data, rotational symmetry