Top

Journal of Scientific Computing

Published in:

01-04-2021

An Efficient Iterative Method for Reconstructing Surface from Point Clouds

Author: Dong Wang

Published in: Journal of Scientific Computing | Issue 1/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Surface reconstruction from point clouds is a fundamental step in many applications in computer vision. In this paper, we develop an efficient iterative method on a variational model for the surface reconstruction from point clouds. The surface is implicitly represented by indicator functions and the energy functional is then approximated based on such representations using heat kernel convolutions. We then develop a novel iterative method to minimize the approximate energy and prove the energy decaying property during each iteration. Asymptotic expansion is also performed to illustrate the dynamics of the surface during iterations. Extensive numerical experiments are performed in both 2- and 3- dimensional Euclidean spaces to show that the proposed method is simple, efficient, and accurate.

previous article Adaptive HDG Methods for the Steady-State Incompressible Navier–Stokes Equations

next article Superconvergence of the Local Discontinuous Galerkin Method for One Dimensional Nonlinear Convection-Diffusion Equations

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Berger, M., Tagliasacchi, A., Seversky, L.M., Alliez, P., Guennebaud, G., Levine, J.A., Sharf, A., Silva, C.T.: A survey of surface reconstruction from point clouds. Comput. Graph. Forum 36(1), 301–329 (2016). https://doi.org/10.1111/cgf.12802CrossRef

Bi, Z., Wang, L.: Advances in 3d data acquisition and processing for industrial applications. Robot. Comput. Integr. Manuf. 26(5), 403–413 (2010). https://doi.org/10.1016/j.rcim.2010.03.003CrossRef

Bolle, R., Vemuri, B.: On three-dimensional surface reconstruction methods. IEEE Trans. Pattern Anal. Mach. Intell. 13(1), 1–13 (1991). https://doi.org/10.1109/34.67626CrossRef

Calakli, F., Taubin, G.: SSD: smooth signed distance surface reconstruction. Comput. Graph. Forum 30(7), 1993–2002 (2011). https://doi.org/10.1111/j.1467-8659.2011.02058.xCrossRef

Dinh, H.Q., Turk, G., Slabaugh, G.: Reconstructing surfaces using anisotropic basis functions. In: Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, vol. 2, pp. 606–613. IEEE (2001)

Elsey, M., Esedoglu, S.: Threshold dynamics for anisotropic surface energies. Math. Comput. 87(312), 1721–1756 (2017). https://doi.org/10.1090/mcom/3268MathSciNetCrossRefMATH

Esedoglu, S., Otto, F.: Threshold dynamics for networks with arbitrary surface tensions. Commun. Pure Appl. Math. 68(5), 808–864 (2014). https://doi.org/10.1002/cpa.21527MathSciNetCrossRefMATH

Esedoglu, S., Tsai, R., Ruuth, S.: Threshold dynamics for high order geometric motions. Interfaces Free Bound. 10, 263–282 (2008)MathSciNetCrossRef

Esedoglu, S., Tsai, Y.H.R., et al.: Threshold dynamics for the piecewise constant Mumford–Shah functional. J. Comput. Phys. 211(1), 367–384 (2006). https://doi.org/10.1016/j.jcp.2005.05.027MathSciNetCrossRefMATH

10.

He, Y., Huska, M., Kang, S.H., Liu, H.: Fast algorithms for surface reconstruction from point cloud. arXiv:1907.01142 (2019)

11.

He, Y., Kang, S.H., Liu, H.: Curvature regularized surface reconstruction from point clouds. SIAM J. Imaging Sci. 13(4), 1834–1859 (2020)MathSciNetCrossRef

12.

Hu, W.: Threshold dynamics: analysis and applications. Ph.D. Thesis, Hong Kong University of Science and Technology (2020)

13.

Jacobs, M., Merkurjev, E., Esedoglu, S.: Auction dynamics: a volume constrained MBO scheme. J. Comput. Phys. 354(1), 288–310 (2018). https://doi.org/10.1016/j.jcp.2017.10.036MathSciNetCrossRefMATH

14.

Jiang, S., Wang, D., Wang, X.P.: An efficient boundary integral scheme for the MBO threshold dynamics method via the Nufft. J. Sci. Comput. 74(1), 474–490 (2018)MathSciNetCrossRef

15.

Kao, C.Y., Osher, S., Qian, J.: Lax–Friedrichs sweeping scheme for static Hamilton–Jacobi equations. J. Comput. Phys. 196(1), 367–391 (2004). https://doi.org/10.1016/j.jcp.2003.11.007MathSciNetCrossRefMATH

16.

Kazhdan, M., Bolitho, M., Hoppe, H.: Poisson surface reconstruction. In: Proceedings of the fourth Eurographics symposium on Geometry processing, pp. 61–70. Eurographics Association (2006)

17.

Khan, D., Shirazi, M.A., Kim, M.Y.: Single shot laser speckle based 3d acquisition system for medical applications. Opt. Lasers Eng. 105, 43–53 (2018). https://doi.org/10.1016/j.optlaseng.2018.01.001CrossRef

18.

Liang, J., Park, F., Zhao, H.: Robust and efficient implicit surface reconstruction for point clouds based on convexified image segmentation. J. Sci. Comput. 54(2–3), 577–602 (2012). https://doi.org/10.1007/s10915-012-9674-8MathSciNetCrossRef

19.

Mascarenhas, P.: Diffusion generated motion by mean curvature. University of California, Los Angeles (1992)

20.

Merkurjev, E., Kostic, T., Bertozzi, A.L.: An MBO scheme on graphs for classification and image processing. SIAM J. Imaging Sci. 6(4), 1903–1930 (2013). https://doi.org/10.1137/120886935MathSciNetCrossRefMATH

21.

Merriman, B., Bence, J., Osher, S.: Diffusion generated motion by mean curvature. In: AMS Selected Letters, Crystal Grower’s Workshop, pp. 73–83 (1993)

22.

Merriman, B., Bence, J.K., Osher, S.: Diffusion generated motion by mean curvature. University of California, Los Angeles (1992)

23.

Merriman, B., Bence, J.K., Osher, S.J.: Motion of multiple junctions: a level set approach. J. Comput. Phys. 112(2), 334–363 (1994). https://doi.org/10.1006/jcph.1994.1105MathSciNetCrossRefMATH

24.

Merriman, B., Ruuth, S.J.: Convolution-generated motion and generalized Huygens’ principles for interface motion. SIAM J. Appl. Math. 60(3), 868–890 (2000). https://doi.org/10.1137/S003613999833397XMathSciNetCrossRefMATH

25.

Miranda, M., Pallara, D., Paronetto, F., Preunkert, M.: Short-time heat flow and functions of bounded variation in \(\mathbb{R}^n\). Ann. Facul. Sci. Toulouse Math. 16(1), 125–145 (2007). https://doi.org/10.5802/afst.1142CrossRefMATH

26.

Nan, L., Wonka, P.: PolyFit: polygonal surface reconstruction from point clouds. In: 2017 IEEE International Conference on Computer Vision (ICCV), pp. 2372–2380. IEEE (2017). https://doi.org/10.1109/iccv.2017.258

27.

Osting, B., Wang, D.: Diffusion generated methods for denoising target-valued images. Inverse Probl. Imaging 14(2), 205–232 (2020). https://doi.org/10.3934/ipi.2020010MathSciNetCrossRefMATH

28.

Osting, B., Wang, D.: A diffusion generated method for orthogonal matrix-valued fields. Math. Comput. 89, 515–550 (2020). https://doi.org/10.1090/mcom/3473MathSciNetCrossRefMATH

29.

Öztireli, A.C., Guennebaud, G., Gross, M.: Feature preserving point set surfaces based on non-linear kernel regression. Comput. Graph. Forum 28(2), 493–501 (2009). https://doi.org/10.1111/j.1467-8659.2009.01388.xCrossRef

30.

Ruuth, S.J., Merriman, B.: Convolution-thresholding methods for interface motion. J. Comput. Phys. 169(2), 678–707 (2001). https://doi.org/10.1006/jcph.2000.6580MathSciNetCrossRefMATH

31.

Ruuth, S.J., Wetton, B.T.: A simple scheme for volume-preserving motion by mean curvature. J. Sci. Comput. 19(1–3), 373–384 (2003). https://doi.org/10.1023/A:1025368328471MathSciNetCrossRefMATH

32.

Wang, D., Jiang, S., Wang, X.P.: An efficient boundary integral scheme for the threshold dynamics method II: applications to wetting dynamics. J. Sci. Comput. 81(3), 1860–1881 (2019)MathSciNetCrossRef

33.

Wang, D., Li, H., Wei, X., Wang, X.P.: An efficient iterative thresholding method for image segmentation. J. Comput. Phys. 350(1), 657–667 (2017). https://doi.org/10.1016/j.jcp.2017.08.020MathSciNetCrossRefMATH

34.

Wang, D., Osting, B.: A diffusion generated method for computing Dirichlet partitions. J. Comput. Appl. Math. 351, 302–316 (2019). https://doi.org/10.1016/j.cam.2018.11.015MathSciNetCrossRefMATH

35.

Wang, D., Osting, B., Wang, X.P.: Interface dynamics for an Allen–Cahn-type equation governing a matrix-valued field. SIAM J. Multisc. Model. Simul. 17(4), 1252–1273 (2019). https://doi.org/10.1137/19M1250595MathSciNetCrossRefMATH

36.

Wang, D., Wang, X.P.: The iterative convolution-thresholding method (ICTM) for image segmentation. arXiv:1904.10917 (2019)

37.

Wang, D., Wang, X.P., Xu, X.: An improved threshold dynamics method for wetting dynamics. J. Comput. Phys. 392, 291–310 (2019). https://doi.org/10.1016/j.jcp.2019.04.037MathSciNetCrossRefMATH

38.

Wang, Y.: Characterizing three-dimensional surface structures from visual images. IEEE Trans. Pattern Anal. Mach. Intell. 13(1), 52–60 (1991). https://doi.org/10.1109/34.67630CrossRef

39.

Xu, X., Wang, D., Wang, X.P.: An efficient threshold dynamics method for wetting on rough surfaces. J. Comput. Phys. 330(1), 510–528 (2017). https://doi.org/10.1016/j.jcp.2016.11.008MathSciNetCrossRefMATH

40.

Zhao, H.K., Osher, S., Merriman, B., Kang, M.: Implicit and nonparametric shape reconstruction from unorganized data using a variational level set method. Comput. Vis. Image Underst. 80(3), 295–314 (2000). https://doi.org/10.1006/cviu.2000.0875CrossRefMATH

Title: An Efficient Iterative Method for Reconstructing Surface from Point Clouds
Author: Dong Wang
Publication date: 01-04-2021
Publisher: Springer US
Published in: Journal of Scientific Computing / Issue 1/2021
Print ISSN: 0885-7474
Electronic ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-021-01457-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2021

Robust Low Transformed Multi-Rank Tensor Methods for Image Alignment

Stochastic Variance Reduced Gradient Methods Using a Trust-Region-Like Scheme

A New Hybrid WENO Scheme on a Four-Point Stencil for Euler Equations

Higher Order Approximation for Stochastic Space Fractional Wave Equation Forced by an Additive Space-Time Gaussian Noise

Smoothing Strategy Along with Conjugate Gradient Algorithm for Signal Reconstruction

Finite Element Calculation of Photonic Band Structures for Frequency Dependent Materials

Premium Partner