Fast heuristics for polygonal approximation of a 2D shape boundary

Two algorithms for polygonal approximation of a two-dimensional (2D) shape boundary are proposed in this paper. If the number of vertices in the obtained polygonal representation is large, the representation will characterize the shape boundary with high accuracy, while the cost for storing or transmitting the representation will be high. That is, the larger the compression ratio is, the more detail is lost in the obtained polygonal representation. The proposed first algorithm automatically determines a suitable spread parameter of a Gaussian filter for smoothing a shape boundary. No human intervention is required in this algorithm. Curvature extrema in the smoothed boundary are used as vertices of the polygonal representation. The second algorithm allows users to specify a lower bound of the compression ratio in the obtained polygonal representation. This algorithm produces a polygonal representation of the given shape boundary, whose compression ratio is only a little larger than or equal to the given lower bound. The proposed algorithms are computationally simple and efficient. Experimental results show the proposed algorithms are indeed efficient and effective; they are very useful in early processing of object recognition and analysis. (C) 1997 Elsevier Science B.V.