Multiscale contour segmentation and approximation: An algorithm based on the geometry of regular inscribed polygons

This paper describes an algorithm to segment and approximate a contour into circular arcs and straight line segments. This algorithm finds an adequate set of circular arcs and straight line segments to describe the contour shape. The resulting description respects a large number of shape representation criteria much better than any previous method. These criteria support efficient, general-purpose, unique, shape preserving, local, robust, stable, invariant, multiscale, coherent, hierarchical, and multipart shape representations. The adequacy of the algorithm is a direct consequence of the formal computational theory on which it is based, The resulting description may depend on sensor accuracy, sampling step size, minimum and maximum contour curvatures, and scale. The algorithm is thus parameterized using a small number of thresholds related to these data set and task properties. Predictions regarding the ground-truth performance of the algorithm can be made given some knowledge of the above properties. Experimental comparative results are presented for contour data of varying complexity. (C) 1998 Academic Press.