An online polygonal approximation of digital signals and curves with Dynamic Programming algorithm

Author

Kolesnikov, Alexander

Author_Institution

Dept. of Comput. Sci. & Stat., Univ. of Joensuu, Joensuu

fYear

2008

fDate

8-11 Dec. 2008

Firstpage

1

Lastpage

4

Abstract

A fast online algorithm was developed for polygonal approximation of signals and curves with a minimum number of line segments for a given constraint on the standard deviation of the approximation error. A continuous Dynamic Programming search with piecewise backtracking of the locally optimal solutions is performed in overlapping windows. The developed online algorithm can be used for polygonal approximation of data streams, time series, digital signals, curves, and trajectories.

Keywords

approximation theory; dynamic programming; search problems; signal processing; statistical analysis; approximation error; continuous dynamic programming search; curves; data streams; digital signals; fast online algorithm; line segments; locally optimal solutions; online polygonal approximation; overlapping windows; piecewise backtracking; standard deviation; time series; trajectories; Approximation algorithms; Approximation error; Computer science; Dynamic programming; Electrocardiography; Error analysis; Heuristic algorithms; Iterative algorithms; Signal processing algorithms; Standards development;

fLanguage

English

Publisher

ieee

Conference_Titel

Pattern Recognition, 2008. ICPR 2008. 19th International Conference on

Conference_Location

Tampa, FL

ISSN

1051-4651

Print_ISBN

978-1-4244-2174-9

Electronic_ISBN

1051-4651

Type

conf

DOI

10.1109/ICPR.2008.4761634

Filename

4761634