On automatic threshold selection for polygonal approximations of digital curves

Polygonal approximation is a very common representation of digital curves. A polygonal approximation depends on a parameter epsilon, which is the error value. In this paper we present a method for an automatic selection of the error value, epsilon. Let Gamma((epsilon)) be a polygonal approximation of the original curve Gamma, with an error value epsilon. We define a set of function, {N-s(epsilon)}(s is an element of S), such that for a given value of s, N-s(epsilon) is the number of edges that contain at least s vertices in Gamma((epsilon)). The time complexity for computing the set of functions {N-s(epsilon)}(s is an element of S) is almost linear in n, the number of vertices in Gamma. In this paper we analyse the N-s(epsilon) graph, and show that for adequate values of s a wide plateau is expected to appear at the top of the graph. This plateau corresponds to a stable state in the multi-scale representation of {Gamma((epsilon))}(epsilon is an element of E). We show that the functions {N-s(epsilon)}(s is an element of S) are a statistical representation of some kind of scale-space Image. Copyright (C) 1996 Pattern Recognition Society.