ON AUTOMATIC THRESHOLD SELECTION FOR POLYGONAL APPROXIMATIONS OF DIGITAL CURVES

Polygonal approximation is a very common representation of digital cur ves. A polygonal approximation depends on a parameter epsilon, which i s the error value. In this paper we present a method for an automatic selection of the error value, epsilon. Let Gamma((epsilon)) be a polyg onal approximation of the original curve Gamma, with an error value ep silon. 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 ed ges that contain at least s vertices in Gamma((epsilon)). The time com plexity for computing the set of functions {N-s(epsilon)}(s is an elem ent of S) is almost linear in n, the number of vertices in Gamma. In t his paper we analyse the N-s(epsilon) graph, and show that for adequat e values of s a wide plateau is expected to appear at the top of the g raph. This plateau corresponds to a stable state in the multi-scale re presentation of {Gamma((epsilon))}(epsilon is an element of E). We sho w that the functions {N-s(epsilon)}(s is an element of S) are a statis tical representation of some kind of scale-space Image. Copyright (C) 1996 Pattern Recognition Society.