# zbMATH — the first resource for mathematics

Point data reconstruction and smoothing using cubic splines and clusterization. (English) Zbl 07318061
Summary: An algorithm to smooth a sequence of noisy data in $$\mathbb{R}^d$$ with cubic polynomials is herein presented. The data points are assumed to be sequentially ordered, with the idea that they are sampled in time/space and represent an unknown curve to be reconstructed. An example is the reconstruction of left and right borders of a road from GPS and/or lidars data, that is a common problem encountered in applications for autonomous vehicles or for the generation of high definition digital maps. The result is a sequence of denoised points, that ideally, belong to the original unknown curve, which is the basis for an interpolation process that aims at building the best approximating curve. The problem is solved employing a least squares approach, with quasi-orthogonal projections. The possibility to weight the samples is provided, as well as a Tikhonov regularisation term to penalise the magnitude of the derivative of the cubic curve used to smooth the data. The Tikhonov term is weighted with a parameter that is determined applying the Generalised Cross-Validation (GCV), which, in particular cases, can be written in closed form. We show and validate the algorithm on a real application example reconstructing the road borders of the circuit track of Doha, Qatar.
Reviewer: Reviewer (Berlin)
##### MSC:
 65D Numerical approximation and computational geometry (primarily algorithms) 65K Numerical methods for mathematical programming, optimization and variational techniques
##### Software:
Algorithm 547; Clothoids; pchip; TSPACK
Full Text:
##### References:
 [1] Aydın, Dursun; Memmedli, Memmedağa, Optimum smoothing parameter selection for penalized least squares in form of linear mixed effect models, Optimization, 61, 4, 459-476 (2012) · Zbl 1245.65016 [2] Bertolazzi, E.; Bevilacqua, P.; Biral, F.; Fontanelli, D.; Frego, M.; Palopoli, L., Efficient re-planning for robotic cars, (European Control Conference (ECC) (2018)), 1068-1073 [3] Bertolazzi, Enrico; Bevilacqua, Paolo; Frego, Marco, Clothoids: a C++ library with Matlab interface for the handling of clothoid curves, Rend. Semin. Mat. Univ. Politec. Torino, 76, 2 (2018) · Zbl 1440.65029 [4] Bertolazzi, Enrico; Biral, Francesco; Da Lio, Mauro, Symbolic-numeric indirect method for solving optimal control problems for large multibody systems: The time-optimal racing vehicle example, Multibody Syst. Dyn., 13, 2, 233-252 (2005) · Zbl 1104.70003 [5] Bertolazzi, Enrico; Frego, Marco, $$G^1$$ fitting with clothoids, Math. Methods Appl. Sci., 38, 5, 881-897 (2015) · Zbl 1314.65019 [6] Bertolazzi, Enrico; Frego, Marco, On the $$G^2$$ Hermite interpolation problem with clothoids, J. Comput. Appl. Math., 341, 99-116 (2018) · Zbl 07143613 [7] Bertolazzi, Enrico; Frego, Marco, Semianalytical minimum-time solution for the optimal control of a vehicle subject to limited acceleration, Optim. Control Appl. Methods, 39, 2, 774-791 (2018) · Zbl 1391.93147 [8] Bertolazzi, Enrico; Frego, Marco, A note on robust biarc computation, Comput.-Aided Des. Appl., 16, 5, 822-835 (2019) · Zbl 07124609 [9] Bevilacqua, Paolo; Frego, Marco; Fontanelli, Daniele; Palopoli, Luigi, Reactive planning for assistive robots, IEEE Robot. Autom. Lett., 3, 2, 1276-1283 (2018) [10] Biral, Francesco; Bertolazzi, Enrico; Bosetti, Paolo, Notes on numerical methods for solving optimal control problems, IEEJ J. Ind. Appl., 5, 2, 154-166 (2016) [11] de Boor, Carl, A Practical Guide to Splines, Applied Mathematical Sciences (2001), Springer New York · Zbl 0987.65015 [12] de Boor, C.; Fix, G. J., Spline approximation by quasiinterpolants, J. Approx. Theory, 8, 1, 19-45 (1973) · Zbl 0279.41008 [13] de Boor, Carl; Höllig, Klaus; Sabin, Malcolm, High accuracy geometric Hermite interpolation, Comput. Aided Geom. Design, 4, 4, 269-278 (1987) · Zbl 0646.65004 [14] Borges, Carlos F.; Pastva, Tim, Total least squares fitting of Bézier and B-spline curves to ordered data, Comput. Aided Geom. Design, 19, 4, 275-289 (2002) · Zbl 0995.68137 [15] Campagna, Rosanna; Conti, Costanza; Cuomo, Salvatore, Smoothing exponential-polynomial splines for multiexponential decay data, Dolomit. Res. Notes Approx., 12, 1, 86-100 (2019) [16] Conti, C.; Morandi, R.; Rabut, C., $$\mathbf{P}_1$$-reproducing shape-preserving quasi-interpolant using positive quadratic splines with local support, J. Comput. Appl. Math., 104, 2, 111-122 (1999) · Zbl 0934.65010 [17] Costantini, P.; Kaklis, P. D.; Manni, C., Polynomial cubic splines with tension properties, Comput. Aided Geom. Design, 27, 8, 592-610 (2010) · Zbl 1205.65048 [18] Costantini, P.; Manni, C., Geometric construction of spline curves with tension properties, Comput. Aided Geom. Design, 20, 8-9, 579-599 (2003), cited By 12 · Zbl 1069.41500 [19] Costantini, P.; Manni, C., Shape-preserving c3 interpolation: The curve case, Adv. Comput. Math., 18, 1, 41-63 (2003) · Zbl 1018.65017 [20] Costantini, Paolo; Pelosi, Francesca, Shape-preserving approximation by space curves, Numer. Algorithms, 27, 3, 237-264 (2001) · Zbl 1079.65018 [21] Costantini, Paolo; Pelosi, Francesca; Sampoli, Maria L., New spline spaces with generalized tension properties, BIT Numer. Math., 48, 4, 665-688 (2008) · Zbl 1175.41006 [22] Costantini, Paolo; Sampoli, Maria Lucia, A general scheme for shape preserving planar interpolating curves, BIT Numer. Math., 43, 2, 297-317 (2003) · Zbl 1037.65019 [23] Craven, Peter; Wahba, Grace, Smoothing noisy data with spline functions, Numer. Math., 31, 4, 377-403 (1978) · Zbl 0377.65007 [24] Dal Bianco, Nicola; Bertolazzi, Enrico; Biral, Francesco; Massaro, Matteo, Comparison of direct and indirect methods for minimum lap time optimal control problems, Veh. Syst. Dyn., 1-32 (2018) [25] Dongarra, Jack; Gates, Mark; Haidar, Azzam; Kurzak, Jakub; Luszczek, Piotr; Tomov, Stanimire; Yamazaki, Ichitaro, The singular value decomposition: Anatomy of optimizing an algorithm for extreme scale, SIAM Rev., 60, 4, 808-865 (2018) · Zbl 1410.65114 [26] Duris, Charles S., Algorithm 547: Fortran routines for discrete cubic spline interpolation and smoothing [e1], [e3], ACM Trans. Math. Software, 6, 1, 92-103 (1980) · Zbl 0425.41002 [27] Eilers, Paul H. C.; Marx, Brian D., Flexible smoothing with b -splines and penalties, Statist. Sci., 11, 2, 89-121 (1996) · Zbl 0955.62562 [28] Enrico, Bertolazzi; Marco, Frego, Interpolating clothoid splines with curvature continuity, Math. Methods Appl. Sci., 41, 4, 1723-1737 (2017) · Zbl 1386.65073 [29] Farouki, Rida T.; Manni, Carla; Sampoli, Maria Lucia; Sestini, Alessandra, Shape-preserving interpolation of spatial data by Pythagorean-hodograph quintic spline curves, IMA J. Numer. Anal., 35, 1, 478-498 (2015) · Zbl 1312.65013 [30] Farouki, Rida T.; Manni, Carla; Sestini, Alessandra, Shape-preserving interpolation by $$G^1$$ and $$G^2$$ PH quintic splines, IMA J. Numer. Anal., 23, 2, 175-195 (2003) · Zbl 1022.65008 [31] Floater, Michael S., Chordal cubic spline interpolation is fourth-order accurate, IMA J. Numer. Anal., 26, 1, 25-33 (2006) · Zbl 1095.41006 [32] Floater, Michael S., On the deviation of a parametric cubic spline interpolant from its data polygon, Comput. Aided Geom. Design, 25, 3, 148-156 (2008) · Zbl 1172.65312 [33] Foley, Thomas A., A shape preserving interpolant with tension controls, Comput. Aided Geom. Design, 5, 2, 105-118 (1988) · Zbl 0663.65009 [34] Frego, Marco; Bertolazzi, Enrico; Biral, Francesco; Fontanelli, Daniele; Palopoli, Luigi, Semi-analytical minimum time solutions with velocity constraints for trajectory following of vehicles, Automatica, 86, 18-28 (2017) · Zbl 1375.93035 [35] Frego, M.; Bevilacqua, P.; Bertolazzi, E.; Biral, F.; Fontanelli, D.; Palopoli, L., Trajectory planning for car-like vehicles: A modular approach, (IEEE Conf. on Decision and Control (2016)), 203-209 [36] Fritsch, F.; Carlson, R., Monotone piecewise cubic interpolation, SIAM J. Numer. Anal., 17, 2, 238-246 (1980) · Zbl 0423.65011 [37] Golub, Gene H.; Heath, Michael; Wahba, Grace, Generalized cross-validation as a method for choosing a good ridge parameter, Technometrics, 21, 2, 215-223 (1979) · Zbl 0461.62059 [38] Golub, Gene H.; Van Loan, Charles F., Matrix Computations (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD, USA · Zbl 0865.65009 [39] Google Earth application (2019), https://www.google.com/earth/ [40] Gwon, Gi-Poong; Hur, Woo-Sol; Kim, Seong-Woo; Seo, Seung-Woo, Generation of a precise and efficient lane-level road map for intelligent vehicle systems, IEEE Trans. Veh. Technol., 66, 6, 4517-4533 (2017) [41] Hagen, Hans, Geometric spline curves, Comput. Aided Geom. Design, 2, 1, 223-227 (1985) · Zbl 0577.65006 [42] Hansen, Per Christian; O’leary, Dianne P., The use of the l-curve in the regularization of discrete ill-posed problems, SIAM J. Sci. Comput., 14, 6, 1487-1503 (1993) · Zbl 0789.65030 [43] Hoffmann, Miklós; Juhász, Imre, On interpolation by spline curves with shape parameters, (Chen, Falai; Jüttler, Bert, Advances in Geometric Modeling and Processing (2008), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 205-214 · Zbl 1152.65030 [44] Höllig, Klaus; Koch, J., Geometric Hermite interpolation, Comput. Aided Geom. Design, 12, 6, 567-580 (1995) · Zbl 0875.68851 [45] Hutchinson, Michael F.; de Hoog, Frank R., Smoothing noisy data with spline functions, Numer. Math., 47, 1, 99-106 (1985) · Zbl 0578.65009 [46] Jaklic, Gasper; Kozak, Jernej; Krajnc, Marjeta; Zagar, Emil, On geometric interpolation by planar parametric polynomial curves, Math. Comp., 76, 260, 1981-1993 (2007) · Zbl 1201.41001 [47] Jo, Kichun; Sunwoo, Myoungho, Generation of a precise roadway map for autonomous cars, IEEE Trans. Intell. Transp. Syst., 15, 3, 925-937 (2014) [48] Jupp, David L. B., Approximation to data by splines with free knots, SIAM J. Numer. Anal., 15, 2, 328-343 (1978) · Zbl 0403.65004 [49] Karavelas, M. I.; Kaklis, P. D., Spatial shape-preserving interpolation using $$\nu$$-splines, Numer. Algorithms, 23, 2, 217-250 (2000) · Zbl 0948.65007 [50] Kozak, Jernej; Zagar, Emil, On geometric interpolation by polynomial curves, SIAM J. Numer. Anal., 42, 3, 953-967 (2004) · Zbl 1076.65016 [51] Kvasov, Boris I., Algorithms for shape preserving local approximation with automatic selection of tension parameters, Comput. Aided Geom. Design, 17, 1, 17-37 (2000) · Zbl 0939.68122 [52] Lavery, John E., Shape-preserving, first-derivative-based parametric and nonparametric cubic $$L_1$$ spline curves, Comput. Aided Geom. Design, 23, 3, 276-296 (2006) · Zbl 1094.65013 [53] Lee, E. T.Y., Choosing nodes in parametric curve interpolation, Comput. Aided Des., 21, 6, 363-370 (1989) · Zbl 0675.65002 [54] Li, X.; Sun, Z.; Cao, D.; He, Z.; Zhu, Q., Real-time trajectory planning for autonomous urban driving: Framework, algorithms, and verifications, IEEE/ASME Trans. Mechatronics, 21, 2, 740-753 (2016) [55] Lin, Chun-Shin; Chang, P. R.; Luh, J. Y.S., Formulation and optimization of cubic polynomial joint trajectories for industrial robots, IEEE Trans. Automat. Control, 28, 12, 1066-1074 (1983) · Zbl 0525.93035 [56] Manni, Carla, On shape preserving C2 Hermite interpolation, BIT Numer. Math., 41, 1, 127-148 (2001) · Zbl 0985.65008 [57] Mazzia, Francesca; Sestini, Alessandra, The bs class of Hermite spline quasi-interpolants on nonuniform knot distributions, BIT Numer. Math., 49, 3, 611-628 (2009) · Zbl 1181.65017 [58] Meek, D. S.; Walton, D. J., The use of cornu spirals in drawing planar curves of controlled curvature, J. Comput. Appl. Math., 25, 1, 69-78 (1989) · Zbl 0662.65008 [59] Meek, D. S.; Walton, D. J., The family of biarcs that matches planar, two-point $$G^1$$ Hermite data, J. Comput. Appl. Math., 212, 1, 31-45 (2008) · Zbl 1133.68079 [60] Nocedal, Jorge; Wright, Stephen J., Numerical Optimization (2006), Springer: Springer New York, NY, USA · Zbl 1104.65059 [61] Paige, Christopher C.; Saunders, Michael, Towards a generalized singular value decomposition, SIAM J. Numer. Anal., 18, 3, 398-405 (1981) · Zbl 0471.65018 [62] Pelosi, Francesca; Farouki, Rida T.; Manni, Carla; Sestini, Alessandra, Geometric Hermite interpolation by spatial pythagorean-hodograph cubics, Adv. Comput. Math., 22, 4, 325-352 (2005) · Zbl 1065.68103 [63] Peña, Juan M., Shape Preserving Representations in Computer-Aided Geometric Design (1999), Nova Publishers · Zbl 1005.68163 [64] Piazzi, Aurelio; Visioli, Antonio, Global minimum-jerk trajectory planning of robot manipulators, IEEE Trans. Ind. Electron., 47, 1, 140-149 (2000) [65] Piegl, Les A.; Tiller, Wayne, The NURBS Book, Monographs in Visual Communication (1997), Springer Berlin Heidelberg · Zbl 0868.68106 [66] Piegl, Les A.; Tiller, Wayne, Biarc approximation of NURBS curves, Comput. Aided Des., 34, 11, 807-814 (2002) [67] Pope, S. B.; Gadh, R., Fitting noisy data using cross-validated cubic smoothing splines, Comm. Statist. Simulation Comput., 17, 2, 349-376 (1988) · Zbl 0695.62114 [68] Renka, R. J., Algorithm 716: Tspack: Tension spline curve-fitting package, ACM Trans. Math. Software, 19, 1, 81-94 (1993) · Zbl 0889.65007 [69] Romero-Zaliz, R.; Reinoso, J. F.; Barrera, D.; Ariza-López, F. J., Minimizing b-spline knots in representative road axis from GPS points cloud, Math. Methods Appl. Sci., 39, 16, 4773-4779 (2016) · Zbl 1351.41006 [70] Ruppert, David, Selecting the number of knots for penalized splines, J. Comput. Graph. Statist., 11, 4, 735-757 (2002) [71] Schumaker, Larry, Spline Functions: Basic Theory, Cambridge Mathematical Library (2007), Cambridge University Press · Zbl 1123.41008 [72] Schumaker, Larry L.; Stanley, Sonya S., Shape-preserving knot removal, Comput. Aided Geom. Design, 13, 9, 851-872 (1996) · Zbl 0900.68413 [73] Schütze, Torsten; Schwetlick, Hubert, Constrained approximation by splines with free knots, BIT Numer. Math., 37, 1, 105-137 (1997) · Zbl 0874.65006 [74] Seif, Heiko G.; Hu, Xiaolong, Autonomous driving in the iCity—HD maps as a key challenge of the automotive industry, Engineering, 2, 2, 159-162 (2016) [75] Traub, J. F., Iterative Methods for the Solution of Equations, AMS Chelsea Publishing Series (1982), Chelsea · Zbl 0472.65040 [76] Van Loan, Charles, Generalizing the singular value decomposition, SIAM J. Numer. Anal., 13, 1, 76-83 (1976) · Zbl 0338.65022 [77] Wang, Wenping; Pottmann, Helmut; Liu, Yang, Fitting B-spline curves to point clouds by curvature-based squared distance minimization, ACM Trans. Graph., 25, 2, 214-238 (2006) [78] Weinert, Howard L., A fast compact algorithm for cubic spline smoothing, Comput. Statist. Data Anal., 53, 4, 932-940 (2009) · Zbl 1452.62140 [79] Welham, Sue J.; Cullis, Brian R.; Kenward, Michael G.; Thompson, Robin, A comparison of mixed model splines for curve fitting, Austral. New Zealand J. Stat., 49, 1, 1-23 (2007) · Zbl 1117.62041 [80] Yang, Xunnian; Wang, Guozhao, Planar point set fairing and fitting by arc splines, Comput. Aided Des., 33, 1, 35-43 (2001) · Zbl 1206.65039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.