{"id":423,"date":"2007-04-23T09:21:47","date_gmt":"2007-04-23T16:21:47","guid":{"rendered":"http:\/\/multimedia.cx\/eggs\/first-love-vector-quantization\/"},"modified":"2007-04-23T11:36:47","modified_gmt":"2007-04-23T18:36:47","slug":"first-love-vector-quantization","status":"publish","type":"post","link":"https:\/\/multimedia.cx\/eggs\/first-love-vector-quantization\/","title":{"rendered":"First Love: Vector Quantization"},"content":{"rendered":"

Someone was asking me about vector quantizer codecs recently. Sure, Wikipedia has the obligatory article<\/a>. To its credit, the article is actually halfway useful these days (I seem to recall that it used to be a lot more impenetrable). It doesn’t help that the concept is identified by 2 terms that, by themselves, sound somewhat intimidating: ‘vector’ and ‘quantization’.<\/p>\n

Anyway, he asked the right person about VQ codecs because I happen to love<\/em> VQ codecs and can go on for days about them. In fact, I might do just that.<\/em> I’ll start with a post about the theory and then describe specific examples in separate posts.<\/p>\n

<\/p>\n

Aside:<\/em> When I first started studying and reverse engineering VQ codecs, I was confused by the word “vector”. For some reason when I think of vectors, I think of 3D graphics, which I do not understand very well. At first, I thought VQ had something to do with 3D math. If you are having similar conceptual comprehension problems, allow me to clarify:<\/p>\n

Mathematically, a vector is nothing but an ordered set of numbers; a tuple. Another math nerd definition is that vectors are one dimensional arrays of orthogonal variables. In the context of 3D math, a vector contains (x, y, z) coordinates. In the context of video codecs, a vector represents a group of pixel values. E.g., take a 4×2 pixel vector from an image, grouped by [square brackets]:<\/p>\n

\r\nx x [a b c d] x x\r\nx x [e f g h] x x\r\n<\/pre>\n
For coding purposes, this vector is [a b c d e f g h].\n<\/p><\/blockquote>\n
I was asked to sum up VQ as succinctly as I could. As a multimedia hacker, I would say that vector quantization is about picture tiling: The picture is composed of a series of indices into a table of pixel blocks. Granted, this is a video codec-centric view of VQ; VQ also has application in such audio codecs as Vorbis and TwinVQ.<\/p>\n
When decoding an image encoded with a VQ codec, the bitstream is generally comprised of a bunch of indices into a table. This table is called the codebook<\/em> (sounds fancy and technical). Reconstruct the image by pulling these blocks (or vectors) out of the codebook table and tiling the screen. But where does the codebook come from? And how does the encoder match the original image’s pixels to an entry in the codebook? Those are the 2 major recurring problems in the field of vector quantization<\/p>\n
To restate, the 2 big issues of encoding VQ:<\/p>\n
    \n
  1. How to generate an optimal codebook, either for a particular image, or for general image material.<\/li>\n
  2. How to search through the codebook in order to match blocks from an uncompressed image to the best possible vector from the codebook.<\/li>\n<\/ol>\n
    Naturally, different codecs make their mark by using different methods for solving these problems. However, no matter what the method, VQ encoding is infamously slow. In fact, a third major problem in the VQ field could be stated as:<\/p>\n
      \n
    1. How to encode a video in a reasonable amount of time.<\/li>\n<\/ol>\n
      If it’s so incredibly slow to encode, why do people care about VQ codecs at all? Ironically, the answer is speed. Relatively speaking, VQ codecs are blazingly fast to decode. As explained above, decoding VQ is often just a matter of copying a sequence of pixels out of a table at a particular index. VQ codecs were popular in the early days of computer multimedia when common PCs were not yet fast enough for codecs that relied of methods such as transform coding (most famously, the discrete cosine transform).<\/p>\n
      These days, since computers are so much faster than when optical storage was first widely available, VQ codecs have largely fallen out of favor compared to transform codecs which are far more efficient to encode.<\/p>\n
      Examples Of VQ Codecs:<\/strong><\/p>\n