L1-Medial Skeleton of Point Cloud

ACM Transactions on Graphics 2013

(Proceedings of SIGGRAPH 2013)

Hui Huang1   Shihao Wu 1,2   Daniel Cohen-Or3   Minglun Gong4  Hao Zhang5   Guiqing Li2  Baoquan Chen1   
1VisuCA / SIAT   2SCUT   3Memorial University   4Tel Aviv University  5Simon Fraser University


Figure 1: Given an unorganized, unoriented, and incomplete raw scan with noise and outliers, our L1-medial skeleton algorithm is able to extract a complete and quality curve skeleton.



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 obser- vation 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 the 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, plants, and curve networks.





1M PDF(downsampled)


60M mp4


Code & Data

Fast Forword

SIG Presentation

Demo (Windows 32bit exe)


Source Code

[To reference our code or data in a publication, please include the bibtex below and a link to this website.]




Figure 2: Overview of L1-medial skeleton extraction. Given an incomplete and noisy raw scan (b) of the object in (a), we randomly select a subset of samples, shown in red in (c). These points are iteratively projected onto a skeletal point cloud with a gradually increasing neighborhood size (d-g). After down-sampling, smoothing, and re-centering, the final curve skeleton is obtained (h).




Figure 3: Results gallery in the paper.




Figure 4: Comparing ROSA skeletons (c) from [Tagliasacchi et al. 2009] with our L1-medial skeletons (d) extracted from a set of raw scans (b). Blue boxes emphasize where the errors (small or big) occur. Note that ROSA requires correct normal estimation on each input.



The authors would like to thank all the reviewers for their valuable comments. The raw scan data shown in Figure 8 is courtesy of Andrea Tagliasacchi. This work is supported in part by grants from NSFC (61103166, 61232011, 61025012), Guangdong Science and Technology Program (2011B050200007), Shenzhen Innovation Program (CXB201104220029A and ZD201111080115A), Shenzhen Nanshan Program (KC2012JSJS0019A), Natural Science and Engineering Research Council of Canada (293127 and 611370) and the Israel Science Foundation.



  title = {L1-Medial Skeleton of Point Cloud},
  author = H. Huang and S. Wu and D. Cohen-Or and M. Gong and H. Zhang and G. Li and B.Chen},
  journal = {ACM Transactions on Graphics},
  volume = {32},
  issue = {4},
  pages = {8},
  year = {2013}

  title = {Consolidation of unorganized point clouds for surface reconstruction},
  author = H. Huang and D. Li and H. Zhang and U. Ascher and D. Cohen-Or},
  journal = {ACM Transactions on Graphics},
  volume = {28},
  issue = {5},
  pages = {176:1--176:78},
  year = {2009}