Digital terrain models (DTMs) are created using elevation data collected in geological surveys using varied sampling techniques like airborne lidar and depth soundings. This often leads to large data sets with different distribution patterns, which may require smooth data approximations in irregular domains with complex boundaries. The thin plate spline (TPS) interpolates scattered data and produces visually pleasing surfaces, but it is too computationally expensive for large data sizes. The finite element thin plate spline (TPSFEM) possesses smoothing properties similar to those of the TPS and interpolates large data sets efficiently. This article investigated the performance of the TPSFEM and adaptive mesh refinement in irregular domains. Boundary conditions are critical for the accuracy of the solution in domains with arbitrary-shaped boundaries and were approximated using the TPS with a subset of sampled points. Numerical experiments were conducted on aerial, terrestrial, and bathymetric surveys. It was shown that the TPSFEM works well in square and irregular domains for modeling terrain surfaces and adaptive refinement significantly improves its efficiency. A comparison of the TPSFEM, TPS, and compactly supported radial basis functions indicates its competitiveness in terms of accuracy and cost.
Citation: Lishan Fang. Smooth digital terrain modeling in irregular domains using finite element thin plate splines and adaptive refinement[J]. AIMS Mathematics, 2024, 9(11): 30015-30042. doi: 10.3934/math.20241450
Digital terrain models (DTMs) are created using elevation data collected in geological surveys using varied sampling techniques like airborne lidar and depth soundings. This often leads to large data sets with different distribution patterns, which may require smooth data approximations in irregular domains with complex boundaries. The thin plate spline (TPS) interpolates scattered data and produces visually pleasing surfaces, but it is too computationally expensive for large data sizes. The finite element thin plate spline (TPSFEM) possesses smoothing properties similar to those of the TPS and interpolates large data sets efficiently. This article investigated the performance of the TPSFEM and adaptive mesh refinement in irregular domains. Boundary conditions are critical for the accuracy of the solution in domains with arbitrary-shaped boundaries and were approximated using the TPS with a subset of sampled points. Numerical experiments were conducted on aerial, terrestrial, and bathymetric surveys. It was shown that the TPSFEM works well in square and irregular domains for modeling terrain surfaces and adaptive refinement significantly improves its efficiency. A comparison of the TPSFEM, TPS, and compactly supported radial basis functions indicates its competitiveness in terms of accuracy and cost.
[1] | M. Bartels, H. Wei, Towards DTM generation from LiDAR data in hilly terrain using wavelets, 4th international workshop on pattern recognition in remote sensing, in conjunction with international conference on pattern recognition, 1 (2006), 33–36. |
[2] | R. K. Beatson, J. B. Cherrie, C. T. Mouat, Fast fitting of radial basis functions: Methods based on preconditioned gmres iteration, Adv. Comput. Math., 11 (1999), 253–270. https://doi.org/10.1023/A:1018932227617 doi: 10.1023/A:1018932227617 |
[3] | I. C. Briggs, Machine contouring using minimum curvature, Geophysics, 39 (1974), 39–48. https://doi.org/10.1190/1.1440410 doi: 10.1190/1.1440410 |
[4] | P. Brufau, M. Vázquez-Cendón, P. García-Navarro, A numerical model for the flooding and drying of irregular domains, Int. J. Numer. Methods Fluids, 39 (2002), 247–275. https://doi.org/10.1002/fld.285 doi: 10.1002/fld.285 |
[5] | M. D. Buhmann, Radial functions on compact support, Proc. Edinburgh Math. Soc., 41 (1998), 33–46. https://doi.org/10.1017/S0013091500019416 doi: 10.1017/S0013091500019416 |
[6] | M. Căteanu, A. Ciubotaru, The effect of lidar sampling density on DTM accuracy for areas with heavy forest cover, Forests, 12 (2021), 265. https://doi.org/10.3390/f12030265 doi: 10.3390/f12030265 |
[7] | C. Chen, Y. Li, C. Yan, A random features-based method for interpolating digital terrain models with high efficiency, Math. Geosci., 52 (2020), 191–212. https://doi.org/10.1007/s11004-019-09801-z doi: 10.1007/s11004-019-09801-z |
[8] | Z. M. Chen, R. Tuo, W. L. Zhang, Stochastic convergence of a nonconforming finite element method for the thin plate spline smoother for observational data, SIAM J. Numer. Anal., 56 (2018), 635–659. https://doi.org/10.1137/16M109630X doi: 10.1137/16M109630X |
[9] | S. Deparis, D. Forti, A. Quarteroni, A rescaled localized radial basis function interpolation on non-Cartesian and nonconforming grids, SIAM J. Sci. Comput., 36 (2014), A2745–A2762. https://doi.org/10.1137/130947179 doi: 10.1137/130947179 |
[10] | B. J. Drenth, Airborne magnetic total-field survey, Iron Mountain-Menominee region, Michigan-Wisconsin, USA, 2021. https://doi.org/10.5066/F7W66J0N |
[11] | T. A. Driscoll, A. R. Heryudono, Adaptive residual subsampling methods for radial basis function interpolation and collocation problems, Comput. Math. Appl., 53 (2007), 927–939. https://doi.org/10.1016/j.camwa.2006.06.005 doi: 10.1016/j.camwa.2006.06.005 |
[12] | A. Falini, M. L. Sampoli, Adaptive refinement in advection–diffusion problems by anomaly detection: A numerical study, Algorithms, 14 (2021), 328. https://doi.org/10.3390/a14110328 doi: 10.3390/a14110328 |
[13] | L. Fang, L. Stals, Adaptive finite element thin-plate spline with different data distributions, In: Domain Decomposition Methods in Science and Engineering XXVI, Cham: Springer, 2023,661–669. https://doi.org/10.1007/978-3-030-95025-5_72 |
[14] | L. Fang, L. Stals, Data-based adaptive refinement of finite element thin plate spline, J. Comput. Appl. Math., 451 (2024), 115975. https://doi.org/10.1016/j.cam.2024.115975 doi: 10.1016/j.cam.2024.115975 |
[15] | B. Fornberg, T. A. Driscoll, G. Wright, R. Charles, Observations on the behavior of radial basis function approximations near boundaries, Comput. Math. Appl., 43 (2002), 473–490. https://doi.org/10.1016/S0898-1221(01)00299-1 doi: 10.1016/S0898-1221(01)00299-1 |
[16] | E. Galin, E. Guérin, A. Peytavie, G. Cordonnier, M.-P. Cani, B. Benes, et al., A review of digital terrain modeling, Comput. Graph. Forum, 38 (2019), 553–577. https://doi.org/10.1111/cgf.13657 doi: 10.1111/cgf.13657 |
[17] | A. Karageorghis, C. S. Chen, Y. S. Smyrlis, A matrix decomposition RBF algorithm: Approximation of functions and their derivatives, Appl. Numer. Math., 57 (2007), 304–319. https://doi.org/10.1016/j.apnum.2006.03.028 doi: 10.1016/j.apnum.2006.03.028 |
[18] | H. Laga, Y. Guo, H. Tabia, R. B. Fisher, M. Bennamoun, 3D Shape analysis: Fundamentals, theory, and applications, John Wiley & Sons, 2018. https://doi.org/10.1002/9781119405207 |
[19] | R. A. McLaren, T. J. Kennie, Visualisation of digital terrain models: Techniques and applications, In: Three Dimensional Applications in GIS, London: CRC Press, 79–98. https://doi.org/10.1201/9781003069454-6 |
[20] | W. F. Mitchell, A comparison of adaptive refinement techniques for elliptic problems, ACM TOMS, 15 (1989), 326–347. https://doi.org/10.1145/76909.76912 doi: 10.1145/76909.76912 |
[21] | A. L. Montealegre, M. T. Lamelas, J. De la Riva, Interpolation routines assessment in als-derived digital elevation models for forestry applications, Remote Sens., 7 (2015), 8631–8654. https://doi.org/10.3390/rs70708631 doi: 10.3390/rs70708631 |
[22] | C. M. Morris, T. L. Welborn, J. T. Minear, Geospatial data, tabular data, and surface-water model archive for delineation of flood-inundation areas in Grapevine Canyon near Scotty's Castle, Death Valley National Park, California, 2020. https://doi.org/10.5066/P9IPKW55 |
[23] | A. Papastavrou, R. Verfürth, A posteriori error estimators for stationary convection–diffusion problems: A computational comparison, Comput. Methods Appl. Mech. Eng., 189 (2000), 449–462. https://doi.org/10.1016/S0045-7825(99)00301-1 doi: 10.1016/S0045-7825(99)00301-1 |
[24] | T. Ramsay, Spline smoothing over difficult regions, J. R. Stat. Soc.: Ser. B, 64 (2002), 307–319. https://doi.org/10.1111/1467-9868.00339 doi: 10.1111/1467-9868.00339 |
[25] | S. Roberts, M. Hegland, I. Altas, Approximation of a thin plate spline smoother using continuous piecewise polynomial functions, SIAM J. Numer. Anal., 41 (2003), 208–234. https://doi.org/10.1137/S0036142901383296 doi: 10.1137/S0036142901383296 |
[26] | A. G. Snyder, C. D. Johnson, A. E. Gibbs, L. H. Erikson, Nearshore bathymetry data from the Unalakleet River mouth, Alaska, 2019, 2021. https://doi.org/10.5066/P9238F8K |
[27] | L. Stals, Efficient solution techniques for a finite element thin plate spline formulation, J. Sci. Comput., 63 (2005), 374–409. https://doi.org/10.1007/s10915-014-9898-x doi: 10.1007/s10915-014-9898-x |
[28] | L. Stals, S. Roberts, Smoothing large data sets using discrete thin plate splines, Comput. Visualization Sci., 9 (2006), 185–195. https://doi.org/10.1007/s00791-006-0033-x doi: 10.1007/s00791-006-0033-x |
[29] | H. Wendland, Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree, Adv. Comput. Math., 4 (1995), 389–396. https://doi.org/10.1007/BF02123482 doi: 10.1007/BF02123482 |
[30] | M. Wojciech, Kriging method optimization for the process of DTM creation based on huge data sets obtained from MBESs, Geosciences, 8 (2018), 433. https://doi.org/10.3390/geosciences8120433 doi: 10.3390/geosciences8120433 |
[31] | X. Xu, K. Harada, Automatic surface reconstruction with alpha-shape method, Visual Comput., 19 (2003), 431–443. https://doi.org/10.1007/s00371-003-0207-1 doi: 10.1007/s00371-003-0207-1 |
[32] | Z. Zhang, Y. Wang, P. K. Jimack, H. Wang, Meshingnet: A new mesh generation method based on deep learning, In: Computational Science – ICCS 2020, Cham: Springer, 2020. https://doi.org/10.1007/978-3-030-50420-5_14 |
[33] | O. C. Zienkiewicz, R. L. Taylor, J. Z. Zhu, The finite element method: Its basis and fundamentals, Oxford: Elsevier, 2005. https://doi.org/10.1016/C2009-0-24909-9 |