Real-time interpolation of streaming data

• Autorzy: Dębski Roman

Identyfikatory

DOI

10.7494/csci.2020.21.4.3932

• Języki publikacji: EN

Abstrakty

EN

One of the key elements of the 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 those based on finite difference schemas. Two such greedy look-ahead heuristic estimators, based on the calculus of variations (denoted as MinBE and MinAJ2), are formally defined (in closed form), along with the corresponding cubic splines that they generate. They are then comparatively evaluated in a series of numerical experiments involving different types of performance measures. The presented results show that the cubic Hermite splines generated by heuristic MinAJ2 significantly outperformed those that were based on finite difference schemas in terms of all of the 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. Multi-dimensional curves that are 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 the memory (e.g., edge computing devices, embedded time-series databases).

Słowa kluczowe

EN

streaming algorithm; online algorithm; spline interpolation; cubic Hermite spline

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2020
• Tom: T. 21 (4)
• Strony: 513–532
• Opis fizyczny: Bibliogr. 35 poz., rys., tab.

Twórcy

autor

Dębski Roman

• AGH University of Science and Technology, Department of Computer Science, al. Mickiewicza 30, 30-059 Krakow, Poland

Bibliografia

• [1] Angeles J.: Fundamentals of Robotic Mechanical Systems, Springer, 2002.
• [2] Bazaz S.A., Tondu B.: Minimum time on-line joint trajectory generator based on low order spline method for industrial manipulators, Robotics and Autonomous Systems, vol. 29(4), pp. 257–268, 1999.
• [3] Bézier P.: Définition numerique de courbes et surfaces I, Automátisme, vol. XI, pp. 625–632, 1966.
• [4] Biagiotti L., Melchiorri C.: Trajectory Planning for Automatic Machines and Robots, Springer Science & Business Media, 2008.
• [5] Birkhoff G.D.: General mean value and remainder theorems with applications to mechanical differentiation and quadrature, Transactions of the American Mathematical Society, vol. 7(1), pp. 107–136, 1906.
• [6] Bolton K.: Biarc curves, Computer-Aided Design, vol. 7(2), pp. 89–92, 1975.
• [7] Boor de C.: A Practical Guide to Splines, Applied Mathematical Sciences, vol. 27, Springer-Verlag, New York, 1978.
• [8] Carvalho de J.M., Hanson J.V.: Real-time interpolation with cubic splines and polyphase networks, Canadian Electrical Engineering Journal, vol. 11(2), pp. 64–72, 1986.
• [9] Catmull E., Rom R.: A class of local interpolating splines. In: Computer aided geometric design, pp. 317–326. Elsevier, 1974.
• [10] De Casteljau P.: Courbes et surfaces à pôles. André Citroën, Automobiles SA, Paris, 1963.
• [11] Dębski R.: High-performance simulation-based algorithms for an alpine ski racer’s trajectory optimization in heterogeneous computer systems, International Journal of Applied Mathematics and Computer Science, vol. 24(3), pp. 551–566, 2014.
• [12] Dębski R.: An adaptive multi-spline refinement algorithm in simulation based sailboat trajectory optimization using onboard multi-core computer systems, International Journal of Applied Mathematics and Computer Science, vol. 26(2), pp. 351–365, 2016.
• [13] Dębski R.: Simulation-Based Sailboat Trajectory Optimization Using On-Board Heterogeneous Computers, Computer Science, vol. 17(4), pp. 461–481, 2016.
• [14] Fan W., Lee C.H., Chen J.H.: A realtime curvature-smooth interpolation scheme and motion planning for CNC machining of short line segments, International Journal of Machine Tools and Manufacture, vol. 96, pp. 27–46, 2015.
• [15] Farin G., Hoschek J., Kim M.S.: Handbook of computer aided geometric design, Elsevier, 2002.
• [16] Forrest A.R.: Curves and surfaces for computer-aided design. Ph.D. thesis, University of Cambridge, 1968.
• [17] Forrest A.R.: Interactive interpolation and approximation by Bézier polynomials, Computer-Aided Design, vol. 22(9), pp. 527–537, 1990.
• [18] Guven O., Eftekhar A., Kindt W., Constandinou T.G.: Computationally efficient real-time interpolation algorithm for non-uniform sampled biosignals, Healthcare Technology Letters, vol. 3(2), pp. 105–110, 2016.
• [19] Hermite M.C., Borchardt M.: Sur la formule d’interpolation de Lagrange, Journal für die reine und angewandte Mathematik (Crelles Journal), vol. 1878(84), pp. 70–79, 1878.
• [20] Jüttler B.: Hermite interpolation by Pythagorean hodograph curves of degree seven, Mathematics of Computation, vol. 70(235), pp. 1089–1111, 2000.
• [21] Knott G.D.: Interpolating Cubic Splines, Progress in Computer Science and Applied Logic, vol. 18, Birkhäuser, Boston, MA, 2000.
• [22] Kröger T.: On-Line Trajectory Generation in Robotic Systems: Basic Concepts for Instantaneous Reactions to Unforeseen (Sensor) Events, Springer Tracts in Advanced Robotics, vol. 58, Springer-Verlag, Berlin–Heidelberg, 2010.
• [23] Li J.: A class of quintic Hermite interpolation curve and the free parameters selection, Journal of Advanced Mechanical Design, Systems, and Manufacturing, vol. 13(1), pp. JAMDSM0011–JAMDSM0011, 2019.
• [24] Lu L.: Planar quintic G2 Hermite interpolation with minimum strain energy, Journal of Computational and Applied Mathematics, vol. 274, pp. 109–117, 2015.
• [25] Lu L., Jiang C., Hu Q.: Planar cubic G1 and quintic G2 Hermite interpolations via curvature variation minimization, Computer & Graphics, vol. 70, pp. 92–98, 2018.
• [26] Meijering E.: A chronology of interpolation: from ancient astronomy to modern signal and image processing, Proceedings of the IEEE, vol. 90(3), pp. 319–342, 2002.
• [27] Milenkovic V., Milenkovic P.H.: Tongue Model for Characterizing Vocal Tract Kinematics. In: Recent Advances in Robot Kinematics, pp. 217–224, Springer,1996.
• [28] Monceau Du H.L.D.: Elémens de l’architecture navale ou traité pratique de la construction des vaisseaux, CA Jombert, 1752.
• [29] Ogniewski J.: Cubic Spline Interpolation in Real-Time Applications using Three Control Points. In: 27. International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision WSCG 2019, Plzen, Czech Republic, May 27–30, 2019, vol. 2901, pp. 1–10, World Society for Computer Graphics, 2019.
• [30] Schoenberg I.: Contributions to the Problem of Approximation of Equidistant Data by Analytic Functions, Quarterly of Applied Mathematics, vol. 4(1), pp. 45–99, 1946.
• [31] Schoenberg I.J.: Cardinal spline interpolation, vol. 12. Siam, 1973.
• [32] Schumaker L.: Spline functions: basic theory, Cambridge University Press, 2007.
• [33] Späth H.: One Dimensional Spline Interpolation Algorithms. Ak Peters Series, Taylor & Francis, 1995.
• [34] Versprille K.J.: Computer-Aided Design Applications of the Rational B-Spline Approximation Form. Ph.D. thesis, Syracuse University, 1975.
• [35] Wallis J.: Arithmetica infinitorum, John Wallis, Operum Mathematicorum, vol. 2, pp. 1–199, 1656.