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…

Continue reading →

Today’s project involved transitioning from a passthrough codec to one that does some minimal amount of coding. This version determines the number of unique colors that a frame uses, codes the palette, and codes the palette indices using the minimum number of of bits necessary. For example, if there are 16 unique colors, only 4 bits are needed to code each pixel. If there are 18 colors, 5 bits are needed. Both of these are common situations for my basic test case:

The Adventures of Lolo, NES

According to my AVI frame-tallying tool:

Assuming 60 frames/sec:
  952 video frames, 0m15s running time, 30263114 total video bytes
  2017540 avg video bytes/sec, 31788 avg video bytes/frame
  min video frame = 5 bytes, max video frame = 35905 bytes

This compression scheme is all keyframes so far. While 30 MB is better than 218 MB, which is the original size of the movie, this is far from an optimal coding. The best compression at this point comes from single-color frames. The next phase is to try some different compression techniques and see which one yields the best nominal result.

I got the basic codec infrastructure working correctly tonight. This is simply an FFmpeg module that “codes” the raw RGBA32 data by passing it through untouched and “decodes” it by doing the same. Hey, it still felt like a major achievement.

Next goal is a basic palette coding model.

I decided it is time to stop talking about what I going do and start talking about how I am going to do it. I want to try my hand at creating a new video codec. This is my first attempt at such a feat. I need to write both the encoder and decoder simultaneously. I need to develop some idea about which coding theories I wish to test and how I will go about testing them. I need test vectors for encoding.

But first and foremost, I need a name for this new codec. I have decided on “Palettized Animation Video Codec.” That is what its name shall be unless someone can come up with a better name. The fourcc shall be ‘PAVC’ which is yet unclaimed (although ‘PDVC’ is claimed according to fourcc.org). Since this is an article about PAVC, I need to lead in with some cool shots of old video games, if only as a reminder of this endeavor’s challenge:

Crystalis, NES Widely regarded as the finest video game ever produced

Solar Jetman, NES Perhaps the toughest Nintendo game to get the hang of

Continue reading →