Some Notes on Lossless Video Codecs

While reading a nice PhD thesis from 2014 (in Russian) about new lossless video compression method I laughed hard at lossless video codec descriptions (here’s the link for unbelievers – http://gorkoff.ru/wp-content/uploads/articles/dissertation.pdf, translation below is mine):

To date various lossless videostream compression methods and algorithms have been developed. They are used in the following widespread codecs:

* CorePNG employs deflate algorithm for independent compression of every frame. Theoretically the codec supports delta frames but this option is not used.

* FFV1 employs prediction coding with following entropy coding or prediction error.

* Huffyuv, like FFV1 algorithm, employs predictive coding but prediction error is effectively coded with Huffman algorithm.

* MSU Lossless Video Codec has been developed for many years at Moscow State University labs.

And yet some real world tasks demand more effective compression and thus a challenge of developing new more effective lossless video compression methods still remains actual.

Readers are welcome to find inaccurate, erroneous and outright bullshit statements in this quote themselves. I’d rather talk about lossless video codecs as I know them.

First, there’s a plague of lossless video codecs. They are very easy to develop — even easier than lossless audio codec because you don’t have to care about container and it’s easy to modify HuffYUV sources.

Second, lossless video coding and any compression scheme really can be represented as two parts: modelling (it may include several stages, like e.g. Burrows-Wheeler Transform, then Move-To-Front and then Run-Length coding) and entropy coding (writing Huffman codes, employing arithmetic coder or simply outputting bytes, it can also be multistaged — lossless audio codecs like to employ range coding on Rice codes, modern video codecs employ binary arithmetic coder on Huffman trees (like VP family) or Golomb codes (like H.264/H.265) etc.).

Third, most lossless video codecs can be grouped into two families — HuffYUV descendants (they do spatial prediction like PNG or JPEG-LS and then code errors with Huffman codes or arithmetic coding) and LCL descendants (they compress frames with some LZ77 variation often doing nothing else). Exceptions are not very common.

Fourth, it’s rather peculiar geographic distribution of codecs. Most of lossless video codecs seem to come from Japan and there’s a peculiar group of codecs originated at MSU labs (MSU Lossless, MSU Screen, YUVSoft lossless (the company is spinoff) and ScreenPressor from the original MSU codecs author).

And now here’s very incomplete list of lossless video codecs that I could remember with some description:

  • AlparySoft lossless codec — median prediction plus Huffman coding. Russian codec;
  • ArithYUV — median prediction plus arithmetic coding;
  • CamStudio — optional delta frame coding as dst - src plus LZO or deflate;
  • Canopus Lossless — left prediction plus Huffman coding. Japanese codec (from a well-known company even);
  • CorePNG — frames (or difference to the previous frame for delta frames) are compressed as PNG pictures. Very original;
  • DxTory — each component in pixel is coded as index in LRU list with unary code or full bits for an escape value. Japanese codec;
  • Ensharpen/Camtasia — M$ RLE plus deflate;
  • FastCodec — 4×4 or 8×4 tiles with enumerative coding (i.e. it codes separately block average and variance, using combinatorics to pack variance too). Russian codec;
  • FFV1 — FFmpeg’s own lossless codec employing median prediction, Golomb codes or range coding and lots of tricks to make compression better. It probably has the most features too;
  • Flash Screen Video — frame is split in tiles, each tile is compressed with deflate;
  • FoxMagic Video Codec — simple codec with delta frames and two LZ77 compression schemes;
  • Fraps — top prediction plus Huffman coding;
  • HuffYUV — several predictors (like left and median) plus Huffman codes;
  • IgCodec — FastLZ and LZF compression with probably only difference for delta frames, from the author of ZeroCodec. Japanese codec;
  • innoHeim/Rsupport Screen Capture Codec — frames is coded in two deflated chunks, the first chunk contains rectangles to update, the second chunk contains pixels for those rectangles;
  • Kega Video — homebrew recording codec for Kega emulator that employs LZ77 scheme;
  • Lagarith — planar coding consisting of median prediction plus range coding (plus some tricks to save bits on lines of the same colour);
  • LCL (AVIzlib, MSZH) — left prediction plus deflate or homebrew LZ77 scheme. Japanese codec(s);
  • LOCO Codec — median prediction plus adaptive Rice coding (should be obvious from the name really);
  • Luna codec — range coder with maybe some simple prediction (left/top). Japanese codec;
  • MagicYUV — most probably median prediction plus Huffman coding on tiles. It’s mostly interesting for the fact its author keeps it closed source but released decoder for Linux in form of VLC plugins (I’d prefer XAnim plugins though 😉 and probably he wants to monetise on “pro” features on 10-bit support and SDK (at least I have such impression);
  • MLC codec — some prediction by modelling plus range coding;
  • M$ Screen video — the original codec that employed frame partitioning (i.e. frame area could be recursively split into smaller regions to improve compression) and arithmetic coding with adaptive modelling. There were such features as motion compensation and masked region update added there. And yet image compression technique for regions remained the same — median prediction with residue coding. Following codecs added lossy compression (DCT blocks with quantisation or even regions coded as WMV9 I-frame);
  • MSU Lossless — an advanced codec with context modelling from previous component history and range coding. Russian codec;
  • MSU Screen — a development of MSU Lossless codec. Now in addition to intraframe coding (first it tries to reuse one of three top neighbours, if that fails it decodes components using two previous instances of previous component as a context — and checks if there’s a run of this pixel) there’s interframe coding too (the codec can signal that only blocks in range should be decoded and not skipped, depending on block flags only a subblock of it can be decoded and there’s optional motion compensation now too). Russian codec;
  • various RLE codecs — are any comments needed?
  • ScreenPresso codec (SPV1) — simply deflate with no prediction and simple delta frames;
  • ScreenPressor — looks like MSU Screen Codec modification but with coding closer to YUVSoft lossless codec. Essentially Russian codec;
  • SheerVideo — median prediction plus static Huffman codes;
  • Toponoky — from the author of FastCodec, no description and I’m too lazy to look at it (probably it’s the same coding principles as its predecessor). Obviously Russian codec;
  • UtVideo — median prediction plus Huffman coding. Japanese codec;
  • VBLE — median prediction, residue is coded as split Golomb code (first it’s exponents for all values and then mantissas). Oh, and IIRC I’ve met its author once;
  • VMware Screen Codec — essentially it’s just VNC recording;
  • YLC (YUY2 Lossless Codec) — static Huffman codes for each component (plus one for common YUYV quads and zero runs) with T + L - TL predictor. Japanese codec;
  • YUVSoft lossless codec — as expected, some context modelling plus range coder. Russian codec;
  • ZeroCodec — difference coding for delta frames plus deflate, Japanese codec;
  • Zip Motion Blocks Video — DosBox homebrew video codec, tiles compressed with deflate plus motion compensation.

There are many more screen and lossless codecs out there to RE if you want to get into it. If decoder .dll is less than 200kB (and especially if it features signatures from zlib) then it won’t take much effort to find out how it works. I’ve managed to do that with TSCC (aka Camtasia/Ensharpen) without any previous RE experience or hardly any video coding knowledge so you should be able to do such things too.

3 Responses to “Some Notes on Lossless Video Codecs”

  1. Peter says:

    So in Russia, does this post earn you a doctorate?

    * Dr Kostya’s Multimedia Research *

    Also add CineFORM to the list of exotic specimens. Oh and how can you forget Microsoft Screen!

  2. Kostya says:

    Well, I got the suspicion that the thesis in question was written by traditional scheme — your scientific supervisor has invented/discovered something and if you want to get your degree you should base your thesis on it. By no means that’s the only scheme but it’s widely used. In this case the guy knew something about data compression (but even in basics I could correct him in some places) and he chose lossless video compression to demonstrate his scientific supervisor’s invention (essentially a tree for compact representation of very many leaves with similar characteristics). And again IMO getting a degree there is more of a formal procedure — meeting requirements, doing paperwork, typesetting it properly — than doing an original research. Plus you should have good relations with your scientific supervisor, peer reviewers and commission that will listen how you defend your work.

    I had an opportunity to hear what people at my university had for thesis topics ­- in most cases it was obvious BS even to me, in some other cases it sounded fine unless you think on it really hard, maybe there were even good topics. But again, in this case thesis is more of a proof that you know how to deal with papers and process and that you know something in your field of “research”. I hated it so I’ve quit postgraduate program and don’t regret it at all.

    P.S. I’ve added M$ Screen codec description too, thanks for reminding. As for CineForm, I think it’s more like an intermediate codec that might have lossless mode but it’s not the main mode of operation. For the same reasons I’ve not included other codecs like H.264 or Snow.

  3. Peter says:

    I haven’t got to the hate/resentment stage yet… but at times, academic research does seem to be some kind of pyramid scheme.