The efficiency of shape coding is an important problem concerning content-based image manipulations and object-based coding of the video sequences. In order to encode the shape information of an object, the boundary is approximated by a polygon which can be encoded with the smallest number of bits for maximum allowable distortion. The conventional boundary coding schemes, however, does not successfully remove the temporal redundancy of the video sequences. This paper proposes a new boundary encoding scheme by which the temporal redundancy between two successive frames is efficiently removed, resulting in lower bit-rate than the conventional algorithms. The interframe vertex selection problem is solved by finding the path with the minimum cost in the directed acyclic graph (DAG) and its fast version using a simplified graph is introduced to reduce the computational load. The vertices were selected from both the current frame to be encoded and the previous frame already encoded, and thus, the temporal redundancy was effectively removed.

When approximating the shape of a region, a fixed bound on the tolerable distortion is set for approximating its contour points. An adaptive approximation bound for lossy coding of the contour points is proposed. A function representing the relative significance of the contour points is defined to adjust the distortion bound along the region contour allowing an adaptive approximation of the region shape. The effectiveness of the adaptive contour coding approach for a region-based coding system is verified through experiments.