Breaking Eggs And Making Omelettes

Topics On Multimedia Technology and Reverse Engineering


Archives:

World’s Simplest Vector Quantizer

December 18th, 2005 by Multimedia Mike

Vladimir “VAG” Gneushev has uncovered the world’s simplest vector quantizer codec. An FMV format named AVS was used in a 1994 CD-ROM title called Creature Shock. Intraframes carry a vector codebook and vector map; interframes also carry a change map. The audio chunks are actually Creative VOC chunks. Complete details are here.

The strangest thing about this particular VQ codec is that the vectors can have a dimension of 3. For example, the intraframes are comprised of 3×3 pixel vectors. 3 is not divisible by many common video frame resolutions. This game ran on IBM VGAs in 320x200x256 color mode. But the resolution of the movies was actually 318×198. Look carefully at a screenshot from the game:


Creature Shock Screenshot
screenshot courtesy of MobyGames

The top row, bottom row, and 2 right columns are all left undrawn.

So, who wants to implement this format first? If the inspiration strikes you, here are some sample files.

Posted in Game Hacking, Reverse Engineering, Vector Quantization | 1 Comment »

One Response

  1. EdorFaus Says:

    Couldn’t it be argued that paletted mode graphics is a very simple form of vector quantization? Simpler than this format, since this uses a palette? :P

    Well, anyway, I took a stab at it, and implemented a rudimentary video decoder for the AVS format. Haven’t tried to do anything with the audio blocks yet though, just skipping them like the game data blocks. Didn’t spend more than an evening on it, actually; well, after reading some of the articles on vector quantization here first. It’s the first time I ever looked at VQ actually.

    It’s not very good code, and is rather slow (especially the drawing in the “player” is, which is somewhat integrated atm), which isn’t helped by the whole thing being written in Java.
    But then, this was mostly a proof of concept/first stab implementation. :P :)

    I’m having an issue with the interframe decoding algorithm though – had to add an extra step to get the change bitmap to work properly – but that /could/ just be a bug in my code. Not sure yet.