An automatic and efficient dynamic programming algorithm for polygonal approximation of digital curves

An automatic and efficient algorithm based on the dynamic programming approach for constructing optimal polygonal approximation of digital curves is proposed. The number of polygonal vertices is determined automatically by a termination mechanism. Three techniques are used to improve the efficiency of computation. Our algorithm is applied to the widely adopted test patterns provided by Teh and Chin and to the shapes extracted from a real image. Excellent results confirm the applicability of the proposed algorithm. (C) 2002 Elsevier Science B.V. All rights reserved.