A local mesh method for solving PDEs on point clouds

Rongjie Lai; Jiang Liang; Hong-Kai Zhao

doi:10.3934/ipi.2013.7.737

Article Contents

2013, Volume 7, Issue 3: 737-755. Doi: 10.3934/ipi.2013.7.737

This issue Previous Article Nonstationary iterated thresholding algorithms for image deblurring Next Article A direct sampling method for inverse scattering using far-field data

A local mesh method for solving PDEs on point clouds

1.
Department of mathematics, University of Southern California, Los Angeles, CA 90089-2532
2.
Department of mathematics, University of California, Irvine, Irvine, CA 92697-3875
3.
Department of Mathematics, University of California, Irvine, Irvine, CA 92697-3875

Received: October 2012

Revised: December 2012

Published: August 2013

Abstract / Introduction Related Papers Cited by

Abstract

In this work, we introduce a numerical method to approximate differential operators and integrals on point clouds sampled from a two dimensional manifold embedded in $\mathbb{R}^n$. Global mesh structure is usually hard to construct in this case. While our method only relies on the local mesh structure at each data point, which is constructed through local triangulation in the tangent space obtained by local principal component analysis (PCA). Once the local mesh is available, we propose numerical schemes to approximate differential operators and define mass matrix and stiffness matrix on point clouds, which are utilized to solve partial differential equations (PDEs) and variational problems on point clouds. As numerical examples, we use the proposed local mesh method and variational formulation to solve the Laplace-Beltrami eigenproblem and solve the Eikonal equation for computing distance map and tracing geodesics on point clouds.

Keywords:

Mathematics Subject Classification: Primary: 65D18, 65D25, 65D30; Secondary: 68P05.

Citation:

Related Papers

Cited by

References

[1]	F. Camastra and A. Vinciarelli, Estimating the intrinsic dimension of data with a fractal-based method, Pattern Analysis and Machine Intelligence, IEEE Transactions on, 24 (2002), 1404-1407.doi: 10.1109/TPAMI.2002.1039212.
[2]	M. Belkin and P. Niyogi, Semi-supervised learning on riemannian manifolds, Machine Learning, 56 (2004), 209-239.doi: 10.1023/B:MACH.0000033120.25363.1e.
[3]	G. Chen, A. V. Little, M. Maggioni and L. Rosasco, Some recent advances in multiscale geometric analysis of point clouds, Wavelets and Multiscale Analysis, 199-225. doi: 10.1007/978-0-8176-8095-4_10.
[4]	M. Belkin, J. Sun and Y. Wang, Constructing laplace operator from point clouds in $\mathbbR^d$, In "Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms," 1031-1040, Philadelphia, PA, (2009).
[5]	C. Luo, J. Sun and Y. Wang, Integral estimation from point cloud in d-dimensional space: A geometric view, In "Symposium on Computational Geometry," (2009), 116-124.doi: 10.1145/1542362.1542389.
[6]	J. Liang, R. Lai, T. W. Wong and H. Zhao, Geometric understanding of point clouds using Laplace-Beltrami operator, CVPR, (2012).
[7]	J. Liang and H. Zhao, Solving partial differential equations on point clouds, SIAM J. Sci. Comput., 35 (2013), A1461-A1486.doi: 10.1137/120869730.
[8]	I. Jolliffe, "Principal Component Analysis," Wiley Online Library, 2005.
[9]	G. Taubin, Geometric signal processing on polygonal meshes, EUROGRAPHICS, (2000).
[10]	M. Meyer, M. Desbrun, P. Schröder and A. H. Barr, Discrete differential-geometry operators for triangulated 2-manifolds, Visualization and Mathematics III, 35-57, Math. Vis., Springer, Berlin, (2003).
[11]	M. Desbrun, M. Meyer, P. Schröder and A. H. Barr, Discrete differential geometry operators in nd, In "Proc. VisMath'02 Berlin Germany," (2002).
[12]	Guoliang Xu, Convergent discrete Laplace-Beltrami operator over triangular surfaces, Proceedings of Geometric Modelling and Processing, (2004), 195-204.
[13]	R. Lai and T. F. Chan, A framework for intrinsic image processing on surfaces, UCLA CAM 10-25, submitted, 115 (2011), 1647-1661.doi: 10.1016/j.cviu.2011.05.011.
[14]	J. W. Milnor and J. D. Stasherff, "Characteristic Classes," Annals of Mathematics Studies, No. 76. Princeton University Press, Princeton, N. J.; University of Tokyo Press, Tokyo, 1974. vii+331 pp.
[15]	J. M. Lee, "Riemannian Manifolds: An Introduction to Curvature," Graduate Texts in Mathematics, 176. Springer-Verlag, New York, 1997, xvi+224 pp.
[16]	X. Li, W. Wang, R. R. Martin and A. Bowyer, Using low-discrepancy sequences and the crofton formula to compute surface areas of geometric models, Computer-Aided Design, 35 (2003), 771-782.doi: 10.1016/S0010-4485(02)00100-8.
[17]	J. A. Sethian, A fast marching level set method for monotonically advancing fronts, Proc. Nat. Acad. Sci. U. S. A., 93 (1996), 1591-1595.doi: 10.1073/pnas.93.4.1591.
[18]	R. Kimmel and J. A. Sethian, Computing geodesic paths on manifolds, Proc. Natl. Acad. Sci. USA, 95 (1998), 8431-8435.doi: 10.1073/pnas.95.15.8431.
[19]	H. Zhao, A fast sweeping method for eikonal equations, Mathematics of Computation, 74 (2005), 603-627.doi: 10.1090/S0025-5718-04-01678-3.
[20]	J. Qian, Y. T. Zhang and H. K. Zhao, Fast sweeping methods for eikonal equations on triangular meshes, SIAM Journal on Numerical Analysis, 45 (2007), 83-107.doi: 10.1137/050627083.
[21]	K. Uhlenbeck, Generic properties of eigenfunctions, Amer. J. of Math., 98 (1976), 1059-1078.doi: 10.2307/2374041.
[22]	J. Sun, M. Ovsjanikov and L. Guibas, A concise and provabley informative multi-scale signature baded on heat diffusion, In " Eurographics Symposium on Geometry Processing," (2009), 1383-1392.
[23]	M. M. Bronstein and I. Kokkinos, Scale-invariant heat kernel signatures for non-rigid shape recognition, In "Proc. Computer Vision and Pattern Recognition (CVPR)", (2010), 1704-1711.doi: 10.1109/CVPR.2010.5539838.
[24]	Y. Shi, R. Lai, R. Gill, D. Pelletier, D. Mohr, N. Sicotte and A. W. Toga, Conformal metric optimization on surface (CMOS) for deformation and mapping in Laplace-Beltrami embedding space, MICCAI, 14 (2011), 327-334.
[25]	R. Lai, Y. Shi, K. Scheibel, S. Fears, R. Woods, A. W. Toga and T. F. Chan, Metric-induced optimal embedding for intrinsic 3D shape analysis, Computer Vision and Pattern Recognition (CVPR), (2010), 2871-2878.
[26]	R. Lai, Y. Shi, N. Sicotte and A. W. Toga, Automated corpus callosum extraction via Laplace-Beltrami nodalâparcellation and intrinsic geodesic curvature flows on surfaces, ICCV, 11 (2011), 2034-2040.
[27]	I. Chavel, "Eigenvalues in Riemannian Geometry," Including a Chapter by Burton Randol. With an Appendix by Jozef Dodziuk. Pure and Applied Mathematics, 115. Academic Press, Inc., Orlando, FL, 1984. xiv+362 pp.
[28]	J. Jost, "Riemannian Geometry And Geometric Analysis," Springer, 3rd edition, 2001.
[29]	M. Reuter, F. E. Wolter and N. Peinecke, Laplace-Beltrami spectra as shape-DNA of surfaces and solids, Computer-Aided Design, 38 (2006), 342-366.doi: 10.1016/j.cad.2005.10.011.
[30]	J. Brandman, A level-set method for computing the eigenvalues of elliptic operators defined on compact hypersurfaces, Journal of Scientific Computing, 37 (2008), 282-315.doi: 10.1007/s10915-008-9210-z.
[31]	W. Gao, R. Lai, Y. Shi, I. Dinov and A. W. Toga, A narrow-band approach for approximating the Laplace-Beltrami spectrum of 3D shapes, In "AIP Conference Proceedings," 1281 (2010), 1010-1013.doi: 10.1063/1.3497791.
[32]	B. Levy, Laplace-Beltrami eigenfunctions: Towards an algorithm that understands geometry, IEEE International Conference on Shape Modeling and Applications, invited talk, (2006), 13pp.doi: 10.1109/SMI.2006.21.
[33]	S. Dong, P.-T. Bremer, M. Garland, V. Pascucci and J. C. Hart, Spectral surface quadrangulation, ACM Transactions on Graphics (TOG) - Proceedings of ACM SIGGRAPH, (2006), 1057-1066.
[34]	R. M. Rustamov, Laplace-Beltrami eigenfunctions for deformation invariant shape representation, Eurographics Symposium on Geometry Processing, (2007), 225-233.
[35]	B. Vallet and B. Lévy, Spectral geometry processing with manifold harmonics, Computer Graphics Forum (Proceedings Eurographics), 27 (2008), 251-260.doi: 10.1111/j.1467-8659.2008.01122.x.
[36]	M. Reuter, Hierarchical shape segmentation and registration via topological features of Laplace-Beltrami eigenfunctions, International Journal of Computer Vision, 89 (2009), 287-308.doi: 10.1007/s11263-009-0278-1.
[37]	A. M. Bronstein, M. M. Bronstein, R. Kimmel, M. Mahmoudi and G. Sapiro, A gromov-hausdorff framework with diffusion geometry for topologically-robust non-rigid shape matching, Int. Jour. Comput. Vis., 89 (2010), 266-286.doi: 10.1007/s11263-009-0301-6.
[38]	A. Qiu, D. Bitouk and M. I. Miller, Smooth functional and structural maps on the neocortex via orthonormal bases of the Laplace-Beltrami operator, IEEE Trans. Med. Imag., 25 (2006), 1296-1306.
[39]	Y. Shi, R. Lai, S. Krishna, N. Sicotte, I. Dinov and A. W. Toga, Anisotropic Laplace-Beltrami eigenmaps: Bridging reeb graphs and skeletons, In "Proc. MMBIA," (2008).
[40]	Y. Shi, R. Lai, K. Kern, N. Sicotte, I. Dinov and A. W. Toga, Harmonic surface mapping with Laplace-Beltrami eigenmaps, In "Proc. MICCAI," (2008), 147-154.doi: 10.1007/978-3-540-85990-1_18.
[41]	R. Lai, Y. Shi, I. Dinov, T. F. Chan and A. W. Toga, Laplace-Beltrami nodal counts: A new signature for 3D shape analysis, In "Proc. ISBI," (2009), 694-697.doi: 10.1109/ISBI.2009.5193142.
[42]	Y. Shi, I. Dinov and A. W. Toga, Cortical shape analysis in the Laplace-Beltrami feature space, In "Proc. MICCAI," (2009), 208-215.
[43]	Y. Shi, R. Lai, J. Morra, I. Dinov, P. Thompson and A. W. Toga, Robust surface reconstruction via Laplace-Beltrami eigen-projection and boundary deformation, IEEE Trans. Medical Imaging, 29 (2010), 2009-2022.
[44]	Y. Shi, R. Lai and A. Toga, Unified geometry and topology correction for cortical surface reconstruction with intrinsic reeb analysis, MICCAI, (2012), 601-8.
[45]	F. Mémoli and G. Sapiro, Distance functions and geodesics on submanifolds of rd and point clouds, SIAM Journal on Applied Mathematics, (2005), 1227-1260.
[46]	M. De Berg, O. Cheong, M. Van Kreveld and M. Overmars, "Computational Geometry: Algorithms and Applications," Third edition. Springer-Verlag, Berlin, 2008.