CLC number: TP391.4
On-line Access: 2024-08-27
Received: 2023-10-17
Revision Accepted: 2024-05-08
Crosschecked: 2011-06-03
Cited: 1
Clicked: 7744
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",
volume="12",
number="7",
pages="523-532",
year="2011",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C1000308"
}
%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
TY - JOUR
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
Abstract: 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.
[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
<1>