Updates:
20051023: Updated decoding algorithm for 'unknown' codes.
20041130: Initial version.

Intro

This page is about improving Linux support for webcams containing a SN9C101 camera controller, specifically the compression algorithm used for images sent by this chip.

Frame format

(this is largely a table-ised version of the information found in the macam webcam package)
Each frame starts with a frame header, followed by the actual frame image data. The frame header looks like this:

	val	comment
00	FF	Frame synchronisation pattern
01	FF
02	00
03	C4
04	C4
05	96	Unknown
06	00	Unknown
07	xx	bits looks look this: xx00.yzzw, where xx is a frame counter, y = unknown, zz = size indicator (00=VGA, 01=SIF, 10=QSIF), w = compresssion enabled
08	xx	brightness sum inside auto-exposure window (byte 0x08 is LSB, byte 0x09 is MSB). For a pure white image, this number will be equal to 500 times the area of the specified AE window. For images that are not pure white, the value scales down according to relative whiteness.
09	xx
0A	xx	brightness sum outside auto-exposure window (byte 0x0A is LSB, byte 0x0B is MSB). For a pure white image, this number will be equal to 125 times the area outside of the specified AE window. For images that are not pure white, the value scales down according to relative whiteness.
0B	xx

Compression

When used with windows, the webcam sends compressed images over the USB.

Algorithm

Current guess at the compression algorithm:

Data is encoded in a bitstream consisting of fixed huffman codes.
The compressed data consists of a bitstream that encodes for every pixel the difference between the pixel and some reference pixel value.
Pixels are organised in the Bayer pattern and the Bayer sub-pixels are tracked individually and alternatingly. For example, in the first line values for the R and G1 pixels are alternatingly encoded, while in the second line values for the G2 and B pixels are alternatingly encoded.
The pixel reference value is calculated as follows:
The 4 top left pixels are encoded in raw uncompressed 8-bit format.
The value in the top two rows is simply the pixel left of the current pixel.
The value in the left column is simply the pixel above the current pixel.
For all other pixels, the reference value is the average of the pixel on the left and the pixel above the current pixel.
There is one code in the bitstream that specifies the value of a pixel directly (in 4-bit resolution).
Pixel values need to be clamped inside the range 0..255 for proper decoding.

The algorithm purely describes the conversion from sonix compressed Bayer code to uncompressed Bayer. Additional steps are required to converts this to a color image (i.e. a bayer2rgb algorithm).

So far, the following huffman codes have been found:

0: +0 (relative to reference pixel)
100: +4
101: -4
1110xxxx: set absolute value (xxxx.0000)
1101: +11
1111: -11
11001: +20
110000: -20
110001xx: ??? unknown, simply skip these codes.

This algorithm seems to work quite well, except for some images with high contrast. In those images, decoding errors can still be seen, which look like bright points with a hazy 'tail' on the bottom-right side. These high-contrast images also contain some of the unknown 110001xx codes.

Downloads

Source code that demonstrates decompression for the SN9C101 camera controller chip:
(not up-to-date with latest algorithm)

Raw and compressed images: