Dynamic programming approach to optimal vertex selection for polygon-based shape approximation

A new vertex selection scheme for polygon-based contour coders is presented. In the proposed method, final vertex points are determined by a ´two-step procedure´. In the first step, the initial vertices are simply selected from the contour, thereby constituting a subset of the original contour, using conventional methods such as the iterated refinement method (IRM) or progressive vertex selection (PVS) method. In the second step, a vertex adjustment process is incorporated to generate final vertices that are no longer confined to the contour and are optimal in view of the given distortion measure. For the optimality of the final vertices, a dynamic programming (DP)-based solution for the adjustment of the vertices is proposed. Consequently, the authors offer two main contributions. First, it is shown that DP can be successfully applied to vertex adjustment. Secondly, the use of DP enables global optimality to be achieved in vertex selection without any iterative processes. Experimental results are presented to demonstrate the superiority of the proposed method over traditional methods