QTC Codec

Using quad trees for video and image compression.

The goal of this project was to design and implement a fast and simple lossless codec designed for low-complexity video such as screen captures.
It should offer high speed encoding to make it suitable for live screen capture at high frame rates and low CPU load,
while also offering bit rates that make it suitable for Internet streaming in video lectures or screen casts.

Since playback of a new format often poses significant problems due to missing playback infrastructure,
I chose to implement a fully featured proof of concept decoder in JavaScript that offers streaming and playback using any modern browser.

Click the player to play/pause the video. Click the bar at the bottom to seek.

To get a more technical explanation scroll down.

This would be a lot more impressive if you had a modern browser.


Technical Explanation

Using quad trees for video and image compression.

The goal of this project was to design and implement a fast and simple lossless codec designed for low-complexity video such as screen captures.
It should offer high speed encoding to make it suitable for live screen capture at high frame rates and low CPU load,
while also offering bit rates that make it suitable for Internet streaming in video lectures or screen casts.

Since playback of a new format often poses significant problems due to missing playback infrastructure,
I chose to implement a fully featured proof of concept decoder in JavaScript that offers streaming and playback using any modern browser.

Algorithm

Click images to enlarge

The QTC algorithm can be split into three parts.
The first part is image preprocessing, the second part is the quad tree compression itself,
and the last part is a range coder based entropy encoder.

Input image
Input Image

Image preprocessing

In the fist step the image is preprocessed using lossless image and color transformations.
These are tweakable on a per frame basis.

The image can be processed using either a full Paeth transform, as used in the PNG file format,
or a simplified Paeth transform that only uses a single predictor for increased speed.

Image after applying the full Paeth Transform
Image after applying the full Paeth transform

The color information can be transformed into a simplified YUV color space called fakeyuv.
This is done to avoid rounding errors that appear when using the standard YUV color space.
The fakeyuv color space encodes the green channel as Y component,
the difference between red and green as U and the difference between red and blue as V.
In memory the colors are stored as UYV to increase computational efficiency.

Image after applying the fakeyuv transformation
Image after applying the fakeyuv transformation

This step does not reduce the image size and only serves to make the image more compressible in the next steps.

Quad tree compression

The quad tree compressor itself uses recursive subdivision of the input image to find areas of constant color
or areas that did not change in respect to the reference image.

When a reference image is available the encoder first checks the current block against the same block in the reference image.
If there are no changes subdivision stops and the next block gets encoded.
(Blue in sample figures)

When there is no reference image, or a change was detected in the last step,
the encoder checks if the current block is of a single color.
If the block is of a single color, subdivision stops and the color of the block is written to the output stream,
otherwise the block is subdivided and the process is repeated.
(Green in sample figures)

Should a block at any time get smaller than a certain threshold it gets saved as "literal" block,
where the image contents of the block are written to the output stream as they are.
(Red in sample figures)

At this point an optional caching mechanism can be used to reduce the number of literal blocks written to the file.
This cache allows to recognize recently used blocks and reference them using an id.
(White in sample figures)

The structure of the subdivision tree built during compression is saved as a separate command data bit stream
so the structure can be replicated during decompression.

Structure of quad tree for still image Structure of quad tree for still image
Structure of quad tree for still image without and with caching

Reference image Structure of quad tree for video frame
Reference image and structure of quad tree for video frame

Normally the compressor works on a per pixel basis, but a special mode for the aforementioned fakeyuv color model exists
that encodes the Y component separately. This is especially useful for gray scale images.

Chroma channel structure of quad tree for still image Chroma channel structure of quad tree for video frame
Chroma channel structure of quad tree for still image and video frame

Entropy coding

The last step of the encoder is a range coder based entropy encoder.

In the reference encoder this step is integrated into the container format.
The color and index data is encoded 8 bit at a time using a second order Markov chain model.
The command data is encoded one bit at a time using an eight order Markov chain model.

Implementation

In the source code archive you will find a plain C QTC encoder and decoder for both video and still images.
Included in the source there is also an SDL based video player and an X11 screen capture program.

There is also a proof of concept JavaScript decoder that is able to fluidly stream and play 720p video using a modern browser on any reasonably modern computer.

Source

QTC encoder and decoder

Needs SDL and libX11, libXfixes and libXext to compile and run the player and screen recorder.

Download: qtc.tar.gz
License: GPL V3.0

Source on github: https://github.com/50m30n3/QTC

JavaScript QTW decoder

Needs to be run from a local webserver for security reasons.

Download: qtw.tar.gz
License: GPL V3.0

Source on github: https://github.com/50m30n3/QTW