Similar articles

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.