Real-time interpolation of streaming data
DOI:
https://doi.org/10.7494/csci.2020.21.4.3932Keywords:
streaming algorithm, online algorithm, spline interpolation, cubic Hermite splineAbstract
One of the key elements of real-time $C^1$-continuous cubic spline interpolation of streaming data is an estimator of the first derivative of the interpolated function that is more accurate than the ones based on finite difference schemas.Two such greedy look-ahead heuristic estimators (denoted as MinBE and MinAJ2) based on Calculus of Variations are formally defined (in closed form) together with the corresponding cubic splines they generate, and then comparatively evaluated in a series of numerical experiments involving different types of performance measures.
The results presented show that the cubic Hermite splines generated by heuristic MinAJ2 significantly outperformed these based on finite difference schemas in terms of all tested performance measures (including convergence).
The proposed approach is quite general. It can be directly applied to streams of univariate functional data like time-series. Multidimensional curves defined parametrically, after splitting, can be handled as well.
The streaming character of the algorithm means that it can also be useful in processing data sets that are too large to fit in memory (e.g., edge computing devices, embedded time-series databases).
Downloads
References
@book{farin:2002,
Author = {Farin, Gerald and Hoschek, Josef and Kim, M-S},
Publisher = {Elsevier},
Title = {Handbook of computer aided geometric design},
Year = {2002}}
@book{du:1752,
Author = {Du Monceau, Henri-Louis Duhamel},
Publisher = {CA Jombert},
Title = {El{'e}mens de l'architecture navale ou trait{'e} pratique de la construction des vaisseaux},
Year = {1752}}
@article{wallis:1656,
Author = {Wallis, John},
Journal = {John Wallis, Operum Mathematicorum},
Pages = {1--199},
Publisher = {Oxford University Press},
Title = {Arithmetica infinitorum},
Volume = {2},
Year = {1656}}
@article{hermite:1878,
Author = {Hermite, M Ch and Borchardt, M},
Journal = {Journal f{"u}r die reine und angewandte Mathematik (Crelles Journal)},
Number = {84},
Pages = {70--79},
Publisher = {De Gruyter},
Title = {Sur la formule d'interpolation de Lagrange},
Volume = {1878},
Year = {1878}}
@article{birkhoff:1906,
Author = {Birkhoff, George David},
Journal = {Transactions of the American Mathematical Society},
Number = {1},
Pages = {107--136},
Publisher = {JSTOR},
Title = {General mean value and remainder theorems with applications to mechanical differentiation and quadrature},
Volume = {7},
Year = {1906}}
@phdthesis{versprille:1975,
Author = {Versprille, Kenneth James},
School = {Syracuse University},
Title = {Computer-aided design applications of the rational b-spline approximation form},
Year = {1975}}
@article{li:2019,
Author = {Li, Juncheng},
Journal = {Journal of Advanced Mechanical Design, Systems, and Manufacturing},
Number = {1},
Pages = {JAMDSM0011--JAMDSM0011},
Publisher = {The Japan Society of Mechanical Engineers},
Title = {A class of quintic Hermite interpolation curve and the free parameters selection},
Volume = {13},
Year = {2019}}
@inproceedings{ogniewski:2019,
Author = {Ogniewski, Jens},
Booktitle = {27. International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision WSCG 2019, Plzen, Czech Republic, May 27--30, 2019},
Organization = {World Society for Computer Graphics},
Pages = {1--10},
Title = {Cubic Spline Interpolation in Real-Time Applications using Three Control Points},
Volume = {2901},
Year = {2019}}
@article{meijering:2002,
Author = {Meijering, Erik},
Journal = {Proceedings of the IEEE},
Number = {3},
Pages = {319--342},
Publisher = {IEEE},
Title = {A chronology of interpolation: from ancient astronomy to modern signal and image processing},
Volume = {90},
Year = {2002}}
@incollection{catmull:1974,
Author = {Catmull, Edwin and Rom, Raphael},
Booktitle = {Computer aided geometric design},
Pages = {317--326},
Publisher = {Elsevier},
Title = {A class of local interpolating splines},
Year = {1974}}
@article{decarvalho:1986,
Author = {de Carvalho, Joao Marques and Hanson, John V},
Journal = {Canadian Electrical Engineering Journal},
Number = {2},
Pages = {64--72},
Publisher = {IEEE},
Title = {Real-time interpolation with cubic splines and polyphase networks},
Volume = {11},
Year = {1986}}
@article{guven:2016,
Author = {Guven, Onur and Eftekhar, Amir and Kindt, Wilko and Constandinou, Timothy G},
Journal = {Healthcare technology letters},
Number = {2},
Pages = {105--110},
Publisher = {IET},
Title = {Computationally efficient real-time interpolation algorithm for non-uniform sampled biosignals},
Volume = {3},
Year = {2016}}
@book{kroger:2010,
Author = {Kr{"o}ger, Torsten},
Publisher = {Springer},
Title = {On-Line Trajectory Generation in Robotic Systems: Basic Concepts for Instantaneous Reactions to Unforeseen (Sensor) Events},
Volume = {58},
Year = {2010}}
@article{bazaz:1999,
Author = {Bazaz, Shafaat Ahmed and Tondu, Bertrand},
Journal = {Robotics and Autonomous Systems},
Number = {4},
Pages = {257--268},
Publisher = {Elsevier},
Title = {Minimum time on-line joint trajectory generator based on low order spline method for industrial manipulators},
Volume = {29},
Year = {1999}}
@phdthesis{forrest:1968,
Author = {Forrest, Archibald Robin},
School = {University of Cambridge},
Title = {Curves and surfaces for computer-aided design.},
Year = {1968}}
@misc{bezier:1966,
Author = {B{'e}zier, P},
Publisher = {XI},
Title = {D{'e}finition numerique de courbes et surfaces I, Autom{'a}tisme, Vol},
Year = {1966}}
@article{decasteljau:1963,
Author = {De Casteljau, Paul},
Journal = {Andr{'e} Citro{"e}n, Automobiles SA, Paris},
Title = {Courbes et surfaces {`a} p{^o}les},
Year = {1963}}
@article{forrest:1972,
Author = {Forrest, A Robin},
Journal = {The Computer Journal},
Number = {1},
Pages = {71--79},
Publisher = {The British Computer Society},
Title = {Interactive interpolation and approximation by B{'e}zier polynomials},
Volume = {15},
Year = {1972}}
@article{schoenberg:1946,
Author = {Schoenberg, I.J.},
Date-Modified = {2020-05-13 00:16:26 +0200},
Journal = {Quarterly of Applied Mathematics},
Number = {1},
Pages = {45--99},
Publisher = {American Mathematical Society (AMS)},
Title = {Contributions to the problem of approximation of equidistant data by analytic functions},
Volume = {4},
Year = {1946}}
@book{schoenberg:1973,
Author = {Schoenberg, Isaac J},
Publisher = {Siam},
Title = {Cardinal spline interpolation},
Volume = {12},
Year = {1973}}
@article{bolton:1975,
Author = {Bolton, KM},
Journal = {Computer-Aided Design},
Number = {2},
Pages = {89--92},
Publisher = {Elsevier},
Title = {Biarc curves},
Volume = {7},
Year = {1975}}
@book{deboor:1978,
Author = {De Boor, Carl},
Publisher = {Springer-verlag New York},
Title = {A practical guide to splines},
Volume = {27},
Year = {1978}}
@book{schumaker:2007,
Author = {Schumaker, Larry},
Publisher = {Cambridge University Press},
Title = {Spline functions: basic theory},
Year = {2007}}
@book{knott:2012,
Author = {Knott, Gary D},
Publisher = {Springer Science & Business Media},
Title = {Interpolating cubic splines},
Volume = {18},
Year = {2012}}
@book{spath:1995,
Author = {Sp{"a}th, H.},
Date-Modified = {2020-05-12 16:23:45 +0200},
Isbn = {9781568810164},
Lccn = {93040858},
Publisher = {Taylor & Francis},
Series = {Ak Peters Series},
Title = {One Dimensional Spline Interpolation Algorithms},
Year = {1995}}
@article{fan:2015,
Author = {Fan, Wei and Lee, Chen-Han and Chen, Ji-Hong},
Journal = {International Journal of Machine Tools and Manufacture},
Pages = {27--46},
Publisher = {Elsevier},
Title = {A realtime curvature-smooth interpolation scheme and motion planning for CNC machining of short line segments},
Volume = {96},
Year = {2015}}
@article{lu:2018,
Author = {Lu, Lizheng and Jiang, Chengkai and Hu, Qianqian},
Journal = {Computers & Graphics},
Pages = {92--98},
Publisher = {Elsevier},
Title = {Planar cubic {G1} and quintic {G2} Hermite interpolations via curvature variation minimization},
Volume = {70},
Year = {2018}}
@article{lu:2015,
Author = {Lu, Lizheng},
Journal = {Journal of Computational and Applied Mathematics},
Pages = {109--117},
Publisher = {Elsevier},
Title = {Planar quintic {G2} Hermite interpolation with minimum strain energy},
Volume = {274},
Year = {2015}}
@incollection{milenkovic:1996,
Author = {Milenkovic, Veljko and Milenkovic, Paul H},
Booktitle = {Recent Advances in Robot Kinematics},
Pages = {217--224},
Publisher = {Springer},
Title = {Tongue model for characterizing vocal tract kinematics},
Year = {1996}}
@book{biagiotti:2008,
Author = {Biagiotti, Luigi and Melchiorri, Claudio},
Publisher = {Springer Science & Business Media},
Title = {Trajectory planning for automatic machines and robots},
Year = {2008}}
@book{angeles:2002,
Author = {Angeles, Jorge},
Publisher = {Springer},
Title = {Fundamentals of robotic mechanical systems},
Year = {2002}}
@article{debski:2014,
title={High-performance simulation-based algorithms for an alpine ski racer's trajectory optimization in heterogeneous computer systems},
author={D{k{e}}bski, Roman},
journal={International Journal of Applied Mathematics and Computer Science},
volume={24},
number={3},
pages={551--566},
year={2014},
publisher={Sciendo}
}
@article{debski:2016a,
Author = {D{k{e}}bski, Roman},
Journal = {International Journal of Applied Mathematics and Computer Science},
Number = {2},
Pages = {351--365},
Publisher = {Sciendo},
Title = {An adaptive multi-spline refinement algorithm in simulation based sailboat trajectory optimization using onboard multi-core computer systems},
Volume = {26},
Year = {2016}}
@article{debski:2016b,
title={Simulation-based sailboat trajectory optimization using on-board heterogeneous computers},
author={D{k{e}}bski, Roman},
journal={Computer Science},
volume={17},
number={4},
pages={461},
year={2016}
}
@article{juttler:2001,
Author = {J{"u}ttler, Bert},
Journal = {Mathematics of Computation},
Number = {235},
Pages = {1089--1111},
Title = {Hermite interpolation by Pythagorean hodograph curves of degree seven},
Volume = {70},
Year = {2001}}
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2020 Computer Science
This work is licensed under a Creative Commons Attribution 4.0 International License.
