In order to solve the bottleneck problem of region-based coding scheme, which is the contour coding, lossy methods are introduced in this paper for both 2D and 3D (2D plus time) contour image(s). A non-linear filter by means of majority operation is designed to act as contour simplification for both pre-processing and post-processing of contour coding. An average of 20% gain in contour coding cost is achieved by using this filter while the contour location error is controlled within one pixel width. Afterwards, an efficient contour motion estimation and compensated coding method are presented. In order to exploit the high temporal redundancy of the contour image sequence, motion estimation and compensation are applied to the correspondent label image sequence. First frame is directly coded by Chain-code method. All the following frames are coded in motion compensated mode. Meanwhile, a fast implementation of full search motion estimation algorithm is also described. This algorithm is 2R times faster than traditional method (R is the total regional number). Within each frame, labels are divided into foreground labels and background labels. Only the noticeable prediction errors for the foreground labels are coded. Morphological filters are used to clean the prediction errors of the foreground labels. An efficient prediction error coding algorithm is then introduced based on one-side Chain-code method. The reconstruction of foreground and background regions in the decoder side is also described. Experimental results have demonstrated good performance For very low bitrate video coding applications.