Signal Processing: Image Communication, vol. 15, no. 7-8, pp. 643-663, May 2000

Generalized Predictive Binary Shape Coding Using Polygon Approximations

Jong-il Kim Alan C. Bovik, and Brian L. Evans

Department of Electrical and Computer Engineering, Engineering Science Building, The University of Texas at Austin, Austin, TX 78712-1084 USA - -


This paper introduces a new binary shape coding technique called generalized predictive shape coding (GPSC) to encode the boundary of a visual object compactly by using a vertex-based approach. GPSC consists of a contour pixel matching algorithm and a motion-compliant contour coding algorithm. The contour pixel matching algorithm utilizes the knowledge of previously decoded contours by using a uniform translational model for silhouette motion, and generalizes polygon approximation for lossless and lossy motion estimation by adjusting a tolerance parameter dmax. To represent motion-compliant regions with minimum information in the transmitted bitstream, we develop a reference index-based coding scheme to represent the 2D positions of the matched segments using 1D reference contour indices. Finally, we encode the mismatched segments by sending residual polygons until the distortion is less than dmax.

While GPSC realizes polygon approximation exactly at every encoding stage, we can guarantee quality of service because the peak distortion is no greater than dmax, and we improve coding efficiency as long as a silhouette complies with the model. The tolerance parameter dmax can be assigned to each contour to smooth the transmitted data rate, which is especially useful for constant bandwidth channels. Compared with non-predictive approaches, simulation using MPEG-4 sequences demonstrates that GPSC not only improves objective gain but also enhances visual quality based on MPEG-4 subjective tests. The significance of GPSC is that it provides a generic framework for seamlessly extending conventional vertex coding schemes into the temporal domain yet it retains the advantages of existing polygon-based algorithms for visual content description while furnishing better geometric compression.

Last Updated 11/08/04.