Full Text:   <1738>

CLC number: TP391.4

On-line Access: 2011-07-04

Received: 2010-09-07

Revision Accepted: 2011-03-24

Crosschecked: 2011-06-03

Cited: 1

Clicked: 3361

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2011 Vol.12 No.7 P.523-532


Efficient reconstruction of non-simple curves

Author(s):  Yuan-di Zhao, Jun-jie Cao, Zhi-xun Su, Zhi-yang Li

Affiliation(s):  School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China, State Key Laboratory of Structural Analysis for Industrial Equipment, Department of Engineering Mechanics, Dalian University of Technology, Dalian 116024, China

Corresponding email(s):   jjcao1231@gmail.com

Key Words:  Reverse engineering, Strip-shaped points, Curve reconstruction, Anisotropic adaptive sampling

Share this article to: More |Next Article >>>

Yuan-di Zhao, Jun-jie Cao, Zhi-xun Su, Zhi-yang Li. Efficient reconstruction of non-simple curves[J]. Journal of Zhejiang University Science C, 2011, 12(7): 523-532.

@article{title="Efficient reconstruction of non-simple curves",
author="Yuan-di Zhao, Jun-jie Cao, Zhi-xun Su, Zhi-yang Li",
journal="Journal of Zhejiang University Science C",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Efficient reconstruction of non-simple curves
%A Yuan-di Zhao
%A Jun-jie Cao
%A Zhi-xun Su
%A Zhi-yang Li
%J Journal of Zhejiang University SCIENCE C
%V 12
%N 7
%P 523-532
%@ 1869-1951
%D 2011
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1000308

T1 - Efficient reconstruction of non-simple curves
A1 - Yuan-di Zhao
A1 - Jun-jie Cao
A1 - Zhi-xun Su
A1 - Zhi-yang Li
J0 - Journal of Zhejiang University Science C
VL - 12
IS - 7
SP - 523
EP - 532
%@ 1869-1951
Y1 - 2011
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C1000308

We present a novel algorithm to reconstruct curves with self-intersections and multiple parts from unorganized strip-shaped points, which may have different local shape scales and sampling densities. We first extract an initial curve, a graph composed of polylines, to model the different structures of the points. Then a least-squares optimization is used to improve the geometric approximation. The initial curve is extracted in three steps: anisotropic farthest point sampling with an adaptable sphere, graph construction followed by non-linear region identification, and edge refinement. Our algorithm produces faithful results for points sampled from non-simple curves without pre-segmenting them. Experiments on many simulated and real data demonstrate the efficiency of our method, and more faithful curves are reconstructed compared to other existing methods.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Albou, L.P., Schwarz, B., Poch, O., Wurtz, J.M., Moras, D., 2008. Defining and characterizing protein surface using alpha shapes. Proteins, 76(1):1-12.

[2]Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., Silva, C.T., 2001. Point Set Surfaces. Proc. Conf. on Visualization, p.21-28.

[3]Bernardini, F., Bajaj, C.L., 1997. Sampling and Reconstructing Manifolds Using $α$-Shapes. Proc. 9th Canadian Conf. on Computational Geometry, p.193-198.

[4]Cao, J., Tagliasacchi, A., Olson, M., Zhang, H., Su, Z., 2010. Point Cloud Skeletons via Laplacian Based Contraction. Shape Modeling Int. Conf., p.187-197.

[5]Cheng, S., Funke, S., Golin, M., Kumar, P., Poon, S., Ramos, E., 2005. Curve reconstruction from noisy samples. Comput. Geom., 31(1-2):63-100.

[6]De-Alarcón, P.A., Pascual-Montano, A., Gupta, A., Carazo, J.M., 2002. Modeling shape and topology of low-resolution density maps of biological macromolecules. Biophys. J., 83(2):619-632.

[7]Delicado, P., 2001. Another look at principal curves and surfaces. J. Multivar. Anal., 77(1):84-116.

[8]Dey, T.K., Kumar, P., 1999. A Simple Provable Algorithm for Curve Reconstruction. Proc. 10th Annual ACM-SIAM Symp. on Discrete Algorithms, p.893-894.

[9]Edelsbrunner, H., Mucke, E.P., 1994. Three-dimensional alpha shapes. ACM Trans. Graph., 13(1):43-72.

[10]Einbeck, J., Tutz, G., Evers, L., 2005. Local principal curves. Statist. Comput., 15(4):301-313.

[11]Funke, S., Ramos, E.A., 2001. Reconstructing a Collection of Curves with Corners and Endpoints. Proc. 12th Annual ACM-SIAM Symp. on Discrete Algorithms, p.344-353.

[12]Gold, C.M., Snoeyink, J., 2001. A one-step crust and skeleton extraction algorithm. Algorithmica, 30(2):144-163.

[13]Hastie, T., Stuetzle, W., 1989. Principal curves. J. Am. Statist. Assoc., 84(406):502-516.

[14]Hiyoshi, H., 2006. Closed Curve Reconstruction from Unorganized Sample Points. Proc. 3rd Int. Symp. on Voronoi Diagrams in Science and Engineering, p.122-131.

[15]Kégl, B., Krzyzak, A., 2002. Piecewise linear skeletonization using principal curves. IEEE Trans. Pattern Anal. Mach. Intell., 24(1):59-74.

[16]Kégl, B., Krzyzak, A., Linder, T., Zeger, K., 2000. Learning and design of principal curves. IEEE Trans. Pattern Anal. Mach. Intell., 22(3):281-297.

[17]Krasnoshchekov, D.N., Polishchuk, V., 2008. Robust Curve Reconstruction with k-Order alpha-Shapes. IEEE Int. Conf. on Shape Modeling and Applications, p.279-280.

[18]Lee, I.K., 1999. Curve reconstruction from unorganized points. Comput. Aid. Geom. Des., 17(2):161-177.

[19]Levin, D., 1998. The approximation power of moving least squares. Math. Comput., 67(224):1517-1531.

[20]Lin, H., Chen, W., Wang, G., 2005. Curve reconstruction based on an interval B-spline curve. Vis. Comput., 21(6):418-427.

[21]Lipman, Y., Cohen-Or, D., Levin, D., Tal-Ezer, H., 2007. Parameterization-free projection for geometry reconstruction. ACM Trans. Graph., 26(3):22.

[22]Liu, X., Jia, Y., 2005. A bottom-up algorithm for finding principal curves with applications to image skeletonization. Pattern Recogn., 38(7):1079-1085.

[23]Ohbuchi, R., Takei, T., 2003. Shape-Similarity Comparison of 3D Models Using alpha Shapes. Proc. 11th Pacific Conf. on Computer Graphics and Applications, p.293-302.

[24]Pauly, M., Gross, M., Kobbelt, L.P., 2002. Efficient Simplification of Point-Sampled Surfaces. Proc. Conf. on Visualization, p.163-170.

[25]Ruiz, O., Vanegas, C., Cadavid, C., 2007. Principal component and Voronoi skeleton alternatives for curve reconstruction from noisy point sets. J. Eng. Des., 18(5):437-458.

[26]Shapira, L., Shamir, A., Cohen-Or, D., 2008. Consistent mesh partitioning and skeletonisation using the shape diameter function. Vis. Comput., 24(4):249-259.

[27]Singh, R., Cherkassky, V., Papanikolopoulos, N.P., 2000. Self-organizing maps for the skeletonization of sparse shapes. IEEE Trans. Neur. Networks, 11(1):241-248.

[28]Song, Y., 2010. Boundary fitting for 2D curve reconstruction. Vis. Comput., 26(3):187-204.

[29]Sorkine, O., Cohen-Or, D., 2004. Least-Squares Meshes. Proc. Shape Modeling Applications, p.191-199.

[30]Tagliasacchi, A., Zhang, H., Cohen-Or, D., 2009. Curve skeleton extraction from incomplete point cloud. ACM Trans. Graph., 28(3), Article 71, p.1-9.

[31]Tharpey, T., Flury, B., 1996. Self-consistency: a fundamental concept in statistics. Statist. Sci., 11(3):229-243.

[32]Tibshirani, R., 1992. Principal curves revisited. Statist. Comput., 2(4):183-190.

[33]Verbeek, J.J., Vlassis, N., Kröse, B., 2002. A k-segments algorithm for finding principal curves. Pattern Recogn. Lett., 23(8):1009-1017.

[34]Wang, H., Lee, T.C.M., 2006. Automatic parameter selection for a k-segments algorithm for computing principal curves. Pattern Recogn. Lett., 27(10):1142-1150.

[35]Wang, W., Pottmann, H., Liu, Y., 2006. Fitting B-spline curves to point clouds by curvature-based squared distance minimization. ACM Trans. Graph., 25(2):214-238.

[36]Yang, Z., Deng, J., Chen, F., 2005. Fitting unorganized point clouds with active implicit B-spline curves. Vis. Comput., 21(8-10):831-839.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE