I was trying to prototype some coding ideas for the new PAVC codec. Specifically, I decided to run the palettized keyframe data through the Burrows-Wheeler Transform (BWT) followed by a move-to-front (MTF) encoder and a Golomb encoder. Why BWT? I guess because I do not see it used in video compression at all and I wanted to see how it stacked up. In comparison to the least-bit approach in the last experiment, the results were a little better on my NES sample and significantly better for my SNES sample:

Super Castlevania IV, SNES

A serious problem, however, is that my AMD64 Linux PC kept crashing during the encoding. Eventually, I tried upgrading the kernel but that procedure also crashed. Per my understanding, these things are not supposed to happen during normal operation. I thought maybe my computer was too hot on this August night. So I am typing this in Windows XP on the same machine and no problem has manifested yet. Maybe I should try the Doom 3 demo…

Hmm, well, Doom 3 crashes pretty quickly, too. I guess I can claim that the problem is heat exhaustion on the part of the hardware. Anyway, presented for your academic consideration are some very shaky numbers from some very dodgy experiments. I should disclose at this point that I have not actually written a decoder for the BWT/MTF/Golomb coding method yet. But since the standalone sample code provided by the BWT article worked so well, and I incorporated the same code into the encoder, I am at least a little confident that the compressed data is valid.

NES sample, least bit method:

  60 video frames, 0m1s running time, 1694598 total video bytes
  1694598 avg video bytes/sec, 28243 avg video bytes/frame
  min video frame = 28722 bytes, max video frame = 28722 bytes

NES sample, BWT/MTF/Golomb method:

  60 video frames, 0m1s running time, 1272276 total video bytes
  1272276 avg video bytes/sec, 21204 avg video bytes/frame
  min video frame = 21564 bytes, max video frame = 21564 bytes

SNES sample, least bit method:

  60 video frames, 0m1s running time, 3408719 total video bytes
  3408719 avg video bytes/sec, 56811 avg video bytes/frame
  min video frame = 57742 bytes, max video frame = 57802 bytes

SNES sample, BWT/MTF/Golomb method:

  60 video frames, 0m1s running time, 1294749 total video bytes
  1294749 avg video bytes/sec, 21579 avg video bytes/frame
  min video frame = 21912 bytes, max video frame = 21972 bytes

I only collected the first 60 frames (1 second) of data since the kernel was likely to panic if I ran the testbed program any longer. Thus, we do not see those best-case scenarios, where the whole frame is a single color, that we saw in the previous experiment.

The next experiment I wish to try is a limited block search on keyframes. I have seen this technique used in Interplay’s MVE format. Search the area above and to the left for a block that matches the one to be coded. This could potentially work very well, especially for NES frames which rely on 8×8 block tiling, have a high degree of redundancy, and do not commonly have overlapped, transparent backgrounds. And for even faster encoding, it should only be necessary to search on 8-pel boundaries with respect to the current block being coded.