Pursuant to that outlandish PAVC idea of mine (that I first started writing about 3 years ago), I began to tinker with the DosBox Video Codec, a.k.a. Zip Motion Blocks Video or ZMBV for short, which was suggested as an alternative the last time I posted about this topic. I have met with some mixed results.

Briefly, the goal of PAVC is to efficiently and losslessly compress frames of video generated by early video game systems, where “early” is defined as anything including and preceding the Super Nintendo Entertainment System. ZMBV is designed to compress, in real time, data from old DOS games running at a number of color modes, with careful consideration given to 8-bit palette data. FFmpeg had an independent ZMBV decoder soon after the codec appeared in DosBox, and also features an independent encoder as well; both the encoder and decoder come courtesy of Kostya.

Item 1: This past week, I found a way to improve the motion estimator in FFmpeg’s ZMBV encoder by changing the assumption it used to compute error between 2 blocks. Michael, being the compulsive mathematical gambler that he is, said, “I’ll see your rudimentary error minimizer and I’ll raise you a 0^th-order entropy approximater.” No, I don’t understand what that means either. But the net result is that all 8-bit files that FFmpeg converts to ZMBV are notably more compact. Score 1.

Item 2: Read the rest of this entry »

Remember my old PAVC idea? I have been thinking about it again. As a refresher, this idea concerns efficiently and losslessly compressing RGB video frames output from an emulator for early video game systems such as the Nintendo Entertainment System (NES) and the Super NES. This time, I have been considering backing off my original generalized approach and going with a PPU-specific approach. (PPU stands for picture processing unit, which is what they used to call the video hardware in these old video games systems.) Naturally, I would want to start this experiment (again) with my favorite — nay — the greatest video game console of all time, the NES. Time for more obligatory, if superfluous, NES screenshots.

Little Samson, all-around awesome game

Here’s the pitch: Modify an emulator (I’m working with FCE-Ultra) to dump PPU data to a file. Step 2 is to take that data and run it through a compression tool. What kind of data would I care about for step 1? On the first frame, dump out all of the interesting areas of the PPU memory space. This may sound huge, but it is only about 9-12 kilobytes, depending on the cartridge hardware. Also, dump the initial states of a few key PPU registers that are mapped into the CPU’s memory space. As the game runs, watch all of these memory and register values and log changes. This really isn’t as difficult as it sounds since FCEU already cares deeply when one of these values changes. When something changes, mark it as “dirty” and dump that value during the next scanline update.

With that data captured, the next challenge is to compress it. I am open to suggestions on how best to encode this change data. I would hope that we could come up with something a little better than shoving a frame of change data through zlib.

Decompression and playback would entail unraveling whatever was performed in step 2 above. Then, the decoder simulates the NES PPU by drawing scanline by scanline, and applying state change data between scanlines.

What are the benefits to this approach? Ideally, I am aiming not only for lossless compression, but for better compression than what is ordinarily achieved with the large files distributed via BitTorrent and coordinated at tasvideos.org. When I first started investigating this idea over 2 years ago, MPEG-4 variants were still popular for compressing the videos. These days, H.264 seems to have taken over, which performs much better, even on this type of data (allegedly, H.264′s 4×4 transform allows for lower artifacts on sharp edge data such as material from old video game consoles).

Sword Master, mediocre game with great graphics

There are also some benefits from the perspective of NES purists. The most flexible NES emulators allow the user to switch palettes in order to get one that is “just right”. A decoder for this type of data could offer the same benefits.

Of course, an encoder is not much use without an analogous decoder that end users can easily install and use. I think this is less of an issue due to the possibility of creating a decoder in Flash or Java.

A few weeks ago, I posted a new thread over on Bisqwit’s Nesvideos forums about my experimental codec research: Custom Video Codec For Console Movies. There has been some interesting discussion regarding PAVC-related compression concepts and it is worth reading.

It has been a little while since I have posted a gratuitous console game screenshot. For a change, instead of posting a screenshot of a game of which I have fond memories, I am posting a screenshot of one of the most dreadful games ever published on the NES:

Heroes of the Lance

I realized recently that I have completed my initial goals laid out in this post. And since this is a post about PAVC, let’s start out with some pretty console screenshots:

Metalstorm, NES,
one of the most graphically complex games on the NES console

Read the rest of this entry »

Looking forward to the intercoding portion of this codec, it is very common for palettized graphic animations to use palette tricks to achieve certain graphical effects. One of the most prevalent such uses is screen fades– rather than suddenly showing the entire screen, set all the palette colors to 0 and then draw the graphics. After a certain time delta, adjust the palette to dim colors, wait, set the palette a little brighter, and repeat until the screen is at full color. Perform the inverse process for a fade out effect.

fade-in frame #1

Read the rest of this entry »

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…

Read the rest of this entry »

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

Read the rest of this entry »

Originally, I was building this hypothetical video codec around old 8-bit NES videos. However, my Old Skool gaming colleague, Trixter, suggested that I think more generally and design the codec around video output from 1st and 2st generation gaming consoles. For reference, these generations are defined as:

• 1st-generation: Atari 2600/5200/7800, Intellivision, Colecovision, Nintendo Entertainment System, Sega Master System, etc. 1976-1988
• 2nd-generation: Sega Genesis/CD/32X, Super NES, TurboGrafx-16, Neo Geo. 1989-1993

Writing about this codec idea is so much fun because I get to use colorful video game screenshots. For example:

U.N. Squadron, Super Nintendo

Golden Axe, Sega Genesis

Read the rest of this entry »