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,
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.
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.
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.
This step does not reduce the image size and only serves to make the image more compressible in the next steps.
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.
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.
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.
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.
You can download some example videos in QTV and QTW format from here: QTV Example Videos
The multi file QTW videos are tarred for easier downloading.
Needs SDL and libX11, libXfixes and libXext to compile and run the player and screen recorder.
License: GPL V3.0
Source on github: https://github.com/50m30n3/QTC
Needs to be run from a local webserver for security reasons.
License: GPL V3.0
Source on github: https://github.com/50m30n3/QTW