Shape coding for MPEG-4

To encode a video object plan (for example talking head) efficiently and with a maximum of flexibility, MPEG-4 treats the shape and the texture of a video sequence separately. The shape encoder, which is our concern for this project, compresses a bitmap shape sequence, which can be extracted from the original video by chroma keying.

For Intra-coding of the first shape, we used 2 methods:

Chain coding: first, the encoder searches a start point on the border of the shape. Then, it puts vectors all along this border. These 3-bit (8 directions) vectors are written in differential code and Huffman-compressed. The decoder then only has to extract these vectors from the binary file and to "follow the path" along the border. At the end, the contour is simply filled by white (=active shape in the MPEG standard) pixels.

A lossy mode (see IEEE trans. on CSVT, vol.7 no.1, Feb. 1997) removes sharp edges in the contour, allowing to save some more bits without affecting visually the shape of natural objects.

The measured compression ratios where as follows:

Compression ratio:	Lossless	Lossy
Circle	75	87
Freehand shape	41	45
Akiyo	65	77

The lossless algorithm provides a good performance with simple natural shapes, and remains acceptable for more complicated forms. While the result of the lossy algorithm still looks very close to the lossles one , its performance improvement only matters for rather complicated shapes, where lots of edges exist. However, this is the case for natural video sequences.
It is also useful to notice that the usage of differential code dramatically increases the compression ratio of the Huffman algorithm!

Source code: chain_encode.c, huffmanencode.c, makefile_encode
chain_decode.c, huffmandecode.c, makefile_decode

Context-based arithmetic coding: with this technique, the image is divided into macro-blocks, and a context value is computed for each of them, allowing optimal arithmetic coding. Lossy compression can be done by adjusting a threshold value under which the whole macroblock is considered empty (lossy compression).

Following compression ratios are measured:

Compression ratio:	Lossless	Lossy (threshold 256)
Circle	61	100
Freehand shape	41	72
Akiyo	63	90

As we see, this algorithm is a little bit less efficient than chain coding for simple figures. However, with complicated natural shapes, chain coding becomes very computationnaly intensive and unefficient. The lossy compression with threshold 256 is efficient, but also extremely blocky!

Source code

Limitations: The chain coder is implemented for one contour. Nevertheless, it can easily be extended to a general coder by adding new start points.
The arithmetic encoder doesn't flush correctly, and other thresholds than 256 and 0 behave incorrectly. These problems should be corrected very soon.