Description of the Sorenson Vector Quantizer #1 (SVQ1) Video Codec by Mike Melanson (mike at multimedia.cx) and Ewald Snel (ewald at rambo.its.tudelft.nl) v1.1: October 9, 2003 ======================================================================= NOTE: The information in this document is now maintained in Wiki format at: http://wiki.multimedia.cx/index.php?title=SVQ1 ======================================================================= Copyright (c) 2003 Mike Melanson & Ewald Snel Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled "GNU Free Documentation License". Contents -------- * Introduction * Algorithm Basics * Stream Format And Header * Decoding Intraframe Plane Data * Decoding Interframe Plane Data * Appendix A: SVQ1 Data Tables * References * Acknowledgements * ChangeLog * GNU Free Documentation License Introduction ------------ Sorenson Vector Quantizer #1 is identified by the four-character code SVQ1. This FOURCC will be used throughout this document to identify the codec. SVQ1 is primarily used to encode video in Quicktime files. The format was commonly seen from 1998-2002 before its successor, SVQ3 (which is based on completely different coding concepts), was rolled out. The algorithm uses hierarchical adaptive multistage vector quantization with mean removal and motion compensation in order to achieve its compression. The SVQ1 patent listed in the references is a good source for understanding both the encoding and decoding process. This document focuses on principles necessary to implement a SVQ1 decoder. This document assumes familiarity with certain general and video-specific coding concepts such as Huffman (a.k.a. variable length) coding, YUV colorspaces, inter/intraframe coding, and motion compensation. A familiarity with vector quantization is useful, but this document will explain what you need to know about the particular flavor of VQ that SVQ1 uses. Algorithm Basics ---------------- SVQ1 operates on vectors (think blocks) of pixels. At the highest level, the algorithm breaks an image into 16x16 blocks of pixels, or 256-pixel vectors. For each vector, the encoder performs a motion search (if the frame is not a keyframe), mean removal, and multi-stage codebook search through a series of pre-defined codebooks. If the encoder finds a good match for the vector after one or more of these operations, then it outputs the proper bit coding for that vector. Otherwise, the 16x16 block is broken in half into 2 16x8 blocks (128-pixel vectors) and the same operation is repeated (minus the motion search, which only operates on the 16x16 vector level). SVQ1 operates at 6 block sizes: 16x16 16x8 8x8 8x4 4x4 4x2 If the encoder has to break a 4x4 block into 2 4x2 blocks, the block cannot be subdivided further and must be encoded as is using mean removal and a combination of vector codebooks. SVQ1 uses YUV 4:1:0 planar data as its native colorspace. This is also known as YUV9. Each 4x4 block of pixels is represented by one Y sample per pixel, but only 1 U sample and 1 V sample for the entire block. The SVQ1 coding method embodies 3 types of frames: Intraframes, or I-frames, which are coded completely by themselves with no data dependencies from other frames; predicted frames, or P-frames, which are predicted from the previous I- or P-frame and thus have a data dependency on the previous I- or P-frame; and droppable P-frames, or B-frames, which are predicted from either the previous I- or P-frame and thus have a data dependency. However, the latter frame type is similar to MPEG B-frames in the sense that other frames cannot predict from them, so it is safe to drop them when decoding is behind schedule. SVQ1 B-frames are dissimilar to MPEG B-frames in the sense that they are unidirectional and not bidirectional. Stream Format And Header ------------------------ A single SVQ1 chunk has the following high-level organization: header | Y plane data | U plane data | V plane data Each SVQ1 chunk begins with a header which can be a variable number of bits in length. The header bits have the following meaning: frame code 22 bits if (bits 6-5 of frame code are both 0 (i.e., frame code & 0x60 == 0)) frame is invalid temporal reference 8 bits picture type 2 bits if (picture type is I-frame) if (frame code is 0x50 or 0x60) checksum 16 bits if (frame code ^ 0x10 > 0x50) embedded string n bits unknown 2 bits unknown 2 bits unknown 1 bit frame size code 3 bits if (frame size code is 7) frame width 12 bits frame height 12 bits checksum present 1 bit if (checksum present) use packet chksum 1 bit component chksums 1 bit after image data unknown_field_1 2 bits if (unknown_field_1 is not 0) invalid frame header unknown_flag_1 1 bit if (unknown_flag_1) unknown 1 bit unknown 4 bits unknown 1 bit unknown 2 bits while (next bit is 1) read a byte from the stream True, many of the header fields are unknown. But the stream can be decoded just fine with the known header fields. The picture type has the following 4 possible values: 0 I-frame 1 P-frame 2 B-frame 3 invalid frame code, do not proceed with frame decode If the frame size code is 7, 12 bits are stored in the header for each of the width and the height. If the frame size code is any of the other 7 possible values, the frame size is one of these common frame dimension pairs: code width height 0 160 120 1 128 96 2 176 144 3 352 288 4 704 576 5 240 180 6 320 240 A SVQ1 chunk can have a message string embedded inside the chunk header. If (frame code ^ 0x10 > 0x50), follow this algorithm to decoder the string: string[0] = next 8 bits xor_byte = string_xor_table[string[0]] foreach i from 1..string[0]-1 next_byte = next 8 bits string[i] = (next_byte) ^ xor_byte xor_byte = string_xor_table[next_byte] Note that since string[0] holds the string length and is a byte, the maximum string length is 255 characters. The specific details of the checksum coding are not all known. Decoding Intraframe Plane Data ------------------------------ After the frame header is decoded, the bitstream contains all of the encoded data to render the Y plane, then the data for the U plane, then the V plane. For the purposes of this description, each block size is assigned a level: level 5 16x16 level 4 16x8 level 3 8x8 level 2 8x4 level 1 4x4 level 0 4x2 For each of the 3 planes in an intraframe, iterate through each 16x16 block, which are each level 5 blocks, from left->right, top->bottom. processing a level 5 block: get next bit in stream if (bit is 1) subdivide level 5 block into 2 level 4 blocks insert top level 4 block into processing queue insert bottom level 4 block into processing queue else process block, which entails: fetch VLC from bitstream using the appropriate intra vector table; this specifies the number of VQ stages if stages is -1, skip this block if (stages > 0) && (level >= 4) invalid vector, error out of decode since levels 4 and 5 blocks do not use multistage VQ fetch VLC from bitstream using the intra mean table; this specifies the mean removed from the vector during encoding if (stages == 0) set each sample in block to the mean value else fetch the next (stages * 4) bits from the bitstream; these specify the codebooks to use in reconstructing the image; the first 4 bits specify the first codebook to use, the next 4 bits specify the second codebook, all the way up to a sixth codebooks for 6 possible stages add the mean to the each value in the block for each stage add the appropriate codebook to the block If the level 5 block was subdivided into 2 level 4 halves, process each half using the following algorithm: processing a level 4 block: get next bit in stream if (bit is 1) subdivide level 4 block into 2 level 3 blocks insert left level 3 block into processing queue insert right level 3 block into processing queue else process block the same way that a full level 5 block is processed, but use the appropriate level 4 VLC tables and codebooks If any level 3 blocks were inserted into the processing queue as a result of level 4 block subdivisions, process each level 3 block in order using this algorithm: processing a level 3 block: ... By now, you should be recognizing a pattern, e.g.: process_block(level) if (next_bit == 1) subdivide block into 2 (level - 1) halves insert first half into processing queue insert second half into processing queue else ...process block... Where does it end? The function requires a base case where the processing can go no further. In this algorithm, blocks cannot be subdivided beyond level 0 (4x2 samples): process_block(level) if (level > 0) && (next_bit == 1) subdivide block into 2 (level - 1) halves insert first half into processing queue insert second half into processing queue else ...process block... Thus, for each block, the entire block is processed as a level 5 block and possibly subdivided into ...
michalr1n