Segmentation and multi-model approximation of digital curves

This paper examines a problem in the multi-model representation of digital curves. It presents Dynamic Programming algorithms for curves approximation with a Minimum Description Length for a given error threshold with measure L∞ or L2. For the error measure L∞, the optimal algorithm was based on a search for the shortest path in the weighted multigraph constructed on the vertices of the curve. As for the case with an approximation with L2-norm, the optimal algorithm includes the construction of the shortest path in two-dimensional search space. We then proposed various fast and efficient versions of the algorithms for the solution of the problem. We proceeded to test these algorithms on large-size contours and were able to demonstrate a good trade-off between time performance and the efficiency of the solutions. We were thus able to produce results for the optimal and fast near-optimal algorithms for a two-model approximation with line segments and circular arcs. In addition, the proposed algorithm was demonstrated on the adaptive motion model for trajectory segmentation.

► We consider the problem of the multi-model approximation of curves.
► We present optimal algorithms with a Minimum Description Length.
► We propose simple and fast near-optimal algorithms for the problem.
► We produce results for multi-model approximation of curves and trajectories.