Archive for the ‘indeo3encfail’ Category

Indeo 3 encoder: done

Thursday, February 16th, 2023

After fixing some bugs I think my encoder requires no further improvement (there are still things left out there to improve but they are not necessary). The only annoying problem is that decoding some videos with the original VfW binary gives artefacts. Looks like this happens because of its peculiar way to generate and then handle codebooks: corrector pairs and quads are stored as single 32-bit word and its top bit is also used to signal if it’s a dyad or a quad. And looks like for some values (I suspect that for large negative ones) the system does not work so great so while e.g. XAnim module does what is expected, here it mistakes a result for another corrector type and decodes the following bytestream in a wrong way. Of course I’m not going to deal with that annoyance and I doubt anybody will care.

Also I’ve pruned one stupid bug from my MS Video 1 encoder so it should be done as well. The third one, Cinepak, is in laughable state (well, it encodes data but it does not do that correctly let alone effectively); hopefully I’ll work on it later.

For now, as I see no interesting formats to support (suggestions are always welcome BTW), I’ll keep writing toy encoders that nobody will use (and hopefully return to improving Cinepak encoder eventually).

Indeo 3 encoder: done

Monday, February 6th, 2023

I’ve done what I wanted with the encoder, it seems to work and so I declare it to be finished. It can encode videos that other decoders can decode, it has some adjustable options and even a semblance of rate control.

Of course I’ll return to it if I ever use it and find some bugs but for now I’ll move to other things. For instance, Indeo 3 decoder needs to be rewritten now that I understand the codec better. Also I have some ideas for improving MS Video 1 encoder. And there’s TrueMotion 1 that I wanted to take a stab at. And there are some non-encoder things as well.

There’s a lot of stuff to keep me occupied (provided that I actually get myself occupied with it in the first place).

Indeo 3: codebooks

Saturday, February 4th, 2023

As you probably remember, Indeo 3 has 21 codebook. In theory you’d expect them to correspond to coarser quantisers, in reality it’s not that easy. For starters, codebooks 8-15 trigger requantisation of the reference, i.e. in intra mode the top line used for prediction is replaced with coarser values. Yes, it really modifies previously decoded data. And for inter mode it does the same on the previous frame for the first line of the reference block. I’ve decided to enable codebooks 8-15 only for intra mode and not even attempt to use codebooks 16-20 at all. So, what can I achieve with those?

I’ve started experimenting with rate control so I encoded various kinds of samples (albeit small and short) and here are the results:

  • codebook set 0-7 and 8-15 give about the same frame sizes (i.e. it does not matter if you take e.g. codebook 2 or 10);
  • an average intra frame size decreases with codebook number but with inter frames some codebooks result in larger frames (sometimes codebook 2 resulted in larger P-frames than with any other codebook but codebook 6; in other case codebook 5 gave the smallest frames);
  • not forcing a codebook noticeably improves compression of P-frames compared to always using codebook 0 and has almost no effect on I-frames;
  • I-frame to P-frame size ratio varies greatly on the content: for realistic content with a lot of changes it is about 1:1, for videos with low motion and changes it can get to 1:3 or even more.

Maybe the compression ratio can be improved by fiddling with the (completely arbitrary) thresholds I use for some decisions (e.g. if the cell should be coded or marked as skipped). I’ve made them options so all zero people who want to play with it should be able to do that.

So far I think I’ll make rate control in a simple manner: all frames will be treated as potentially of equal size, codebook number will be adjusted depending on the expected and obtained frame sizes and if it overshoots I’ll try to re-encode it with a neighbouring codebook (as this may change frame size drastically).

I’ll write about the results when I have them.

Indeo 3: cell coding

Monday, January 30th, 2023

So we partitioned out the frame and now have to code the cell data. How to pick the best parameters in this case?

The patent suggest calculating vertical and horizontal differences (i.e. differences between top-bottom and left-right neighbours) and depending on how large they are select one of the modes. Codebook selection is not reviewed at all. The reference encoder calculates those differences and uses them to set both cell coding mode and select codebook. I.e. if both differences are large use mode 0 (fine-grained coding), if only one difference is large use mode 3 or 11, otherwise use mode 10. And a ratio of the differences is clipped, multiplied by a magic factor, then by a rate control factor and used as an index in a special magic table to select codebook.

Since my goal is to learn something new instead of simply replicating something existing, I took a completely different approach (that should contain less magic). Mode selection is done by comparing differences and amending it if I decide to use two codebooks. I used the fact that first eight codebooks mostly have differences in form kN+1 and the next eight codebooks have differences in form kM. So I simply calculate for each codebook how many delta values are represented best with those formulas and select the best fitting one. Also I calculate it separately for the even and odd lines (the histograms can be merged later to give a total statistics) so I can select the appropriate codebook or codebook pair for the coding mode. Maybe I’ll have to adjust the scheme for the rate control but it’ll happen later. Side note: Indeo 3 specifies a per-frame set of 16 codebook pairs that all cells should use and global codebook index offset so single-codebook modes may use additional 5 codebooks; the set seems to be static and has regular structure and I’m not sure that global codebook index offset is ever used.

That’s it. The rest of the things should be rather trivial: I’ve written how to perform motion search before, rate/quality control has never been great in the original codec (maybe I’ll report how I did it when I get to it), zero run compression is nothing special either. There’s not much to write until I fix some bugs, improve compression, introduce rate control and validate it against the reference decoder. And that will take a long time…

Indeo 3: splitting the frame

Saturday, January 28th, 2023

As mentioned in the previous post, Indeo 3 splits frame into cells using binary trees and they’re coded using one of several possible modes. In reality it’s more complex: there’s a primary tree that splits frame into regions and tells how to code them (intra or inter) and those regions themselves can be split using another binary tree to tell which coding method to use (or to skip decoding it entirely). See, it had tree coding, prediction units and coding units two decades before H.265! And slices as well: it divides data into strips 160 pixels wide too.

Splitting the frame optimally is practically impossible task (because of its combinatorial complexity). In reality though it’s much simpler: first we split plane into 160-pixel wide (or 40-pixel wide for chroma) strips then split them along the largest dimension until we get cells of maximum acceptable size (which seems to be 767 pixels but the encoder seems to handle up to 2048 pixels in a coded cell). Then it’s up to a secondary cell coding.

From what I could gather in the encoder, it also tries to split secondary cells if they’re above the limit but it’s the same value used in the reference encoder even if it could be set separately.

Since my goal is to learn something new instead of re-creating something existing, I use a different approach: initial mode is selected by the relation between horizontal and vertical differences (if both are too high I try to split the cell and try again). Similarly for inter mode I first try to see whether the cell can be coded as inter (and if splitting it will make at least one of the sub-cells code as inter) and if not then I resort to intra coding.

There is probably a better way than brute force to find out the optimal splitting but for lack of it a simple heuristic should do.

Cell coding mode and codebook selection is a topic best left for the next time.

Indeo 3 overview

Friday, January 27th, 2023

The overall idea behind this codec is simple: a frame is split into cells of variable size (the patent says “a roughly regular grid of cells”) using a binary tree, each cell can then either be coded in intra mode (differences to the previous line) or inter mode (differences to some region in the previous frame). Coding is done by splitting cell into 4×4, 4×8, 8×8 or 8×4 blocks and using one or two of 21 codebook to code pairs of differences (with some tricks to compress small differences and zero runs even further).

The patent describes thirteen different modes, the decoders I know about support only some of those:

  • mode 0—code 4×4 blocks using a single codebook;
  • mode 1—code 4×4 blocks using two different codebooks for even and odd lines;
  • mode 2—code 4×4 blocks using two different codebooks but the second one is used only for the second line (no known decoder supports that mode);
  • mode 3—code 4×8 block using a single codebook by coding differences to the even lines and interpolating the odd ones;
  • mode 4—the same as mode 3 but with two codebooks;
  • mode 5—very similar to mode 3 but with a possibility to add a correction to the interpolated lines (since it involves writing single bits that no other part of the codec does, no known implementation supports it);
  • mode 6—like mode 5 but with two codebooks (and equally unsupported by anything known);
  • mode 7—code 4×4 blocks with bit flags for telling which dyad to code (no known decoder supports this);
  • mode 8—the same as mode 7 but with two codebooks (of course it’s unsupported);
  • mode 9—the same as mode 7 but with the second codebook specially for the second line (equally unsupported);
  • mode 10—code 8×8 block using a single codebook by either duplicating pixels on even lines and interpolating odd lines (for intra) or scaling each delta for 2×2 block (in inter mode);
  • mode 11—code 4×8 (inter only) block using corrector repeated for each odd line;
  • mode 12—mode 11 with two codebooks (only VfW version supports it).

Considering the internal implementation details (e.g. using arrays for opcode handling or not), I’d say that QuickTime and XAnim versions of the decoder are based on the same porting kit code supplied by Intel while Video for Windows version uses the different codebase (it’s not just an encoder being present and mode 12 support, it’s also the way how many tables are generated in runtime while they are static in other decoders, not using the opcode tables and other minor things).

But before we start to code cells we need to perform the initial frame splitting and the next post should be about that.

Starting yet another useless encoder

Thursday, January 26th, 2023

Even before I started to write my series of posts on FFhistory, I had another work in progress already which I’m now making public in order not to chicken out (as I did several times already). I’m talking about Indeo 3 encoder.

Why Indeo 3 of all possible things? It’s both not your conventional DCT-based codec and it’s widespread enough to be of some limited use for me (being present in AVI, MOV and VMD containers, only Cinepak is more ubiquitous). I’m not as good as Mike Melanson but I’m willing to try my hoof at it.

The funny thing is, there’s an opensource decoder for it and even a decent description in US patent 5,386,232 from 1995 (so it’s expired already and anybody can write an encoder for it). The problem is that those two sources don’t match between each other and somewhat disagree with the official binary specification (I’m pretty sure that both Indeo3 decoders were REd from XAnim module). And Ghidra does not like VfW binary (maybe it’ll like the version inside QT6 better) so I can’t easily refer to it either.

Anyway, I attempted and gave up writing an encoder for Indeo 3 several times because of its perceived combinatoric complexity. First you need to split frame recursively into blocks—how to select them? Then you need to select one of the coding modes (again, how?) and codebooks (same question). Trying to think of a reasonable way to implement it all made me shudder and give up until I finally read the format description and persisted enough to write at least something working (side note: I also have the same problem with TrueMotion 1 encoder which I also want to write one day, hopefully it’ll be easier now).

Also I tried to look into the encoder implementation and found it as a bunch of magic numbers at work. I’m not joking, during initialisation it seems to set several dozens of various integers and floats and use them for various coding decisions (at least what I could understand from it is that codebook selection is kinda tied to the internal quantiser parameter which is calculated depending on bitrate/quality—and various magic numbers).

So I want to document how this codec works, what differs in the different descriptions of it and how my encoder decides what to use in different situations. This should amount to another dozen of posts that nobody will read.