Vector quantization

In data compression, vector quantization is a quantization technique often used in lossy data compression in which the basic idea is to code or replace with a key, values from a multidimensional vector space into values from a discrete subspace of lower dimension.

Explanation

The lower-space vector requires less storage space and the data is thus compressed. The transformation into the subspace is usually achieved through projection, or by using a codebook. In some cases, a codebook implementation can be also used to entropy code the discrete value in the same step by generating a prefix coded variable-length encoded value as its output.

The Vector Quantization also called block quantization or pattern matching quantization is a process of compressing K dimensional vectors to a finite set of N dimensional Vectors. The process of jointly quantizing a set of discreet amplitude levels is called vector quantization instead of quantizing each and every sample. Consider a K dimensional vector [x1,x2,...,xk]. These set of vectors (amplitude levels) are compressed by choosing the nearest matching from a set of N dimensional vector [y1,y2,...,yn].

The all possible combinations of the N dimensional vector [y1,y2,..,yn] form the codebook.

Block Diagram: A Simple Vector Quantizer is shown below

It is evident that only the index of the codeword in the codebook is sent instead of the quantized values. This conserves space and achieved more compression.

Twin vector quantization (VQF) is part of the MPEG-4 standard dealing with time domain weighted interleaved vector quantization.

Video codecs based on vector quantization

• Cinepak
• Sorenson codec
• Indeo

Audio codecs based on vector quantization

• TwinVQ
• Ogg Vorbis
• AMR-WB+

See also

• speech coding
• Ogg Vorbis
• Voronoi diagram
• rate-distortion function
• data clustering
• Learning Vector Quantization

Part of this article was originally based on material from the Free On-line Dictionary of Computing and is used with permission under the GFDL.

External links

• http://www.data-compression.com/vq.html
• List of papers and resources about quantization
• QccPack — Quantization, Compression, and Coding Library (open source)