“L1-medial skeleton of point cloud” by Huang, Wu, Cohen-Or, Gong, Zhang, et al. …

  • ©Hui Huang, Shihao Wu, Daniel Cohen-Or, Minglun Gong, Hao Zhang, Guiqing Li, and Baoquan Chen



Session Title:



    L1-medial skeleton of point cloud




    We introduce L1-medial skeleton as a curve skeleton representation for 3D point cloud data. The L1-median is well-known as a robust global center of an arbitrary set of points. We make the key observation that adapting L1-medians locally to a point set representing a 3D shape gives rise to a one-dimensional structure, which can be seen as a localized center of the shape. The primary advantage of our approach is that it does not place strong requirements on the quality of the input point cloud nor on the geometry or topology of the captured shape. We develop a L1-medial skeleton construction algorithm, which can be directly applied to an unoriented raw point scan with significant noise, outliers, and large areas of missing data. We demonstrate L1-medial skeletons extracted from raw scans of a variety of shapes, including those modeling high-genus 3D objects, plant-like structures, and curve networks.


    1. Au, O. K.-C., Tai, C.-L., Chu, H.-K., Cohen-Or, D., and Lee, T.-Y. 2008. Skeleton extraction by mesh contraction. ACM Trans. on Graph (Proc. of SIGGRAPH) 27, 3, 44:1–44:10. Google ScholarDigital Library
    2. Avron, H., Sharf, A., Greif, C., and Cohen-Or, D. 2010. l1-sparse reconstruction of sharp point set surfaces. ACM Trans. on Graph 29, 5, 135:1–135:12. Google ScholarDigital Library
    3. Blum, H. 1967. A transformation for extracting new descriptors of shape. Models for the Perception of Speech and Visual Form, 362–380.Google Scholar
    4. Bucksch, A., Lindenbergh, R., and Menenti, M. 2010. Skeltre: Robust skeleton extraction from imperfect point clouds. The Visual Computer 26, 10, 1283–1300. Google ScholarDigital Library
    5. Cao, J., Tagliasacchi, A., Olson, M., Zhang, H., and Su, Z. 2010. Point cloud skeletons via laplacian based contraction. Proc. IEEE Int. Conf. on Shape Modeling and Applications, 187–197. Google ScholarDigital Library
    6. Chuang, M., and Kazhdan, M. 2011. Fast mean-curvature flow via finite-elements tracking. Computer Graphics Forum (Proc. of Eurographics) 30, 6, 1750–1760.Google ScholarCross Ref
    7. Chung, J.-h., Tsai, C.-h., and Ko, M.-c. 2000. Skeletonization of three-dimensional object using generalized potential field. IEEE Trans. Pat. Ana. & Mach. Int. 22, 11, 1241–1251. Google ScholarDigital Library
    8. Cornea, N. D., Silver, D., and Min, P. 2007. Curve-skeleton properties, applications, and algorithms. IEEE Trans. Vis. & Comp. Graphics 13, 3, 530–548. Google ScholarDigital Library
    9. Daszykowski, M., Kaczmarek, K., Heyden, Y. V., and Walczak, B. 2007. Robust statistics in data analysis – a review: Basic concept. Chemometrics and Intelligent Lab. Sys. 85, 2, 203–219.Google ScholarCross Ref
    10. Dey, T. K., and Sun, J. 2006. Defining and computing curve-skeletons with medial geodesic function. Symp. on Geom. Proc., 143–152. Google ScholarDigital Library
    11. Fukunaga, K., and Hostetler, L. D. 1975. The estimation of the gradient of a density function with applications in pattern recognition. IEEE Trans. Info. Theo. 21, 32–40. Google ScholarDigital Library
    12. Gander, W., Golub, G. H., and Strebel, R. 1994. Least squares fitting of circles and ellipses. BIT Numerical Mathematics 34, 558–578.Google ScholarCross Ref
    13. Hassouna, M. S., and Farag, A. A. 2009. Variational curve skeletons using gradient vector flow. IEEE Trans. Pat. Ana. & Mach. Int. 31, 12, 2257–2274. Google ScholarDigital Library
    14. Hilaga, M., Shinagawa, Y., Kohmura, T., and Kunil, T. L. 2001. Topology matching for fully automatic similarity estimation of 3D shapes. Proc. of SIGGRAPH, 203–212. Google ScholarDigital Library
    15. Huang, H., Li, D., Zhang, H., Ascher, U., and Cohen-Or, D. 2009. Consolidation of unorganized point clouds for surface reconstruction. ACM Trans. on Graph (Proc. of SIGGRAPH Asia) 28, 5, 176:1–176:7. Google ScholarDigital Library
    16. Jiang, W., Xu, K., Cheng, Z., Martin, R. R., and Dang, G. 2013. Curve skeleton extraction by coupled graph contraction and surface clustering. Graphical Models 75, 3, 137–148. Google ScholarDigital Library
    17. Katz, S., and Tal, A. 2003. Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Trans. on Graph (Proc. of SIGGRAPH) 22, 3, 954–961. Google ScholarDigital Library
    18. Li, G., Liu, L., Zheng, H., and Mitra, N. J. 2010. Analysis, reconstruction and manipulation using arterial snakes. ACM Trans. on Graph (Proc. of SIGGRAPH Asia) 29, 5, 152:1–152:10. Google ScholarDigital Library
    19. Lipman, Y., Cohen-Or, D., Levin, D., and Tal-Ezer, H. 2007. Parameterization-free projection for geometry reconstruction. ACM Trans. on Graph (Proc. of SIGGRAPH) 26, 3, 22:1–22:6. Google ScholarDigital Library
    20. Livny, Y., Yan, F., Olson, M., Chen, B., Zhang, H., and El-sana, J. 2010. Automatic reconstruction of tree skeletal structures from point clouds. ACM Trans. on Graph (Proc. of SIGGRAPH Asia) 29, 6, 151:1–151:8. Google ScholarDigital Library
    21. Lu, L., Lévy, B., and Wang, W. 2012. Centroidal voronoi tessellations for line segments and graphs. Computer Graphics Forum (Proc. of Eurographics) 31, 2, 775–784. Google ScholarDigital Library
    22. Milasevic, P., and Ducharme, G. R. 1987. Uniqueness of the spatial median. Ann. Statist. 15, 1332–1333.Google ScholarCross Ref
    23. Mullen, P., de Goes, F., Desbrun, M., Cohen-Steiner, D., and Alliez, P. 2010. Signing the unsigned: Robust surface reconstruction from raw pointsets. Computer Graphics Forum 29, 1733–1741.Google ScholarCross Ref
    24. Natali, M., Biasotti, S., Patan, G., and BiancaFalcidieno. 2011. Graph-based representations of point clouds. Graphical Models 73, 151–164. Google ScholarDigital Library
    25. Sharf, A., Lewiner, T., Shamir, A., and Kobbelt, L. 2007. On-the-fly curve-skeleton computation for 3D shapes. Computer Graphics Forum 26, 323–328.Google ScholarCross Ref
    26. Siddiqi, K., and Pizer, S. 2009. Medial Representations: Mathematics, Algorithms and Applications. Springer. Google ScholarDigital Library
    27. Small, C. G. 1990. A survey of multidimensional medians. International Statistical Review 58, 3, 263–277.Google ScholarCross Ref
    28. Tagliasacchi, A., Zhang, H., and Cohen-Or, D. 2009. Curve skeleton extraction from incomplete point cloud. ACM Trans. on Graph (Proc. of SIGGRAPH) 28, 3, 71:1–71:9. Google ScholarDigital Library
    29. Tagliasacchi, A., Alhashim, I., Olson, M., and Zhang, H. 2012. Mean curvature skeletons. Computer Graphics Forum (Proc. of Symposium on Geometry Processing) 31, 5, 1735–1744. Google ScholarDigital Library
    30. Weber, A. 1909. Über den Standort der Industrie. Tübingen, J. C. B. Mohr (Paul Siebeck). English translation by C. J. Freidrich (1929): Alfred WebersTheory of the Location of Industries.Google Scholar
    31. Willcocks, C. G., and Li, F. W. B. 2012. Feature-varying skeletonization – intuitive control over the target feature size and output skeleton topology. The Visual Computer 28, 6-8, 775–785. Google ScholarDigital Library

ACM Digital Library Publication: