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 Li 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.


[To reference our ALGORITHM, API, CODE or DATA in any publication, please include the bibtex below and a link to this webpage.]

The code portable to linux (Ubuntu), thanks go to Davide Faconti:https://github.com/facontidavide/PointCloudProcessing


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).


   Youtube link      Youtube link ②


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. 

Data & Code

Note that the DATA and CODE are free for Research and Education Use ONLY. 

Please cite our paper (add the bibtex below) if you use any part of our ALGORITHM, CODE, DATA or RESULTS in any publication.

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},
  number = {4},
  pages = {65:1--65:8},
  year = {2013}

Downloads (faster for people in China)

Downloads (faster for people in other places)