ISE-bounded polygonal approximation of digital curves

In this paper we consider a problem of the polygonal approximation of digital curves with a minimum number of approximation segments for a given error bound with L2-norm. The Integral Square Error bound is defined by the number of vertices in the curve and by constraint on the Root-Mean-Squared-Error (RMSE) of the polygonal approximation. This paper proposes a new, fast and efficient algorithm for solving the problem. The algorithm that is offered was based on searching for the shortest path in a feasibility graph that has been constructed on the vertices of the input curve. The proposed algorithm provides a solution with 97% optimality on average in what is practically real time. This algorithm can also be used in combination with the Reduced-Search Dynamic Programming algorithm as a preliminary step for finding a near-optimal result in an acceptable time.Experiments conducted with the large size vector data have demonstrated both the high degree of efficiency and the fast performance time of the proposed algorithms. These algorithms can be used in practical applications for image vectorization and segmentation, the analysis of shapes and time series, the simplification of vector maps, and the compression of vector data.

Figure optionsDownload high-quality image (106 K)Download as PowerPoint slideHighlights
► Algorithm for polygonal approximation with a minimum number of nodes is proposed.
► Error-bound with L2-norm is defined by desired accuracy of the approximation.
► The Dynamic Programming algorithm gives a solution with efficiency up to 100%.
► Time complexity of the proposed fast algorithm is sub-quadratic.