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 L_2. 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 L_2-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.