Vector quantization

For other uses, see VQ.

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.

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. Consider a K dimensional vector ${\displaystyle [x_{1},x_{2},...,x_{k}]}$ . This vector (of amplitude levels) is compressed by choosing the nearest matching vector from a set of N dimensional vectors ${\displaystyle [y_{1},y_{2},...,y_{n}]}$ .

All possible combinations of the N dimensional vector ${\displaystyle [y_{1},y_{2},...,y_{n}]}$  form the codebook.

Block Diagram: A simple vector quantizer is shown below

File:Vector quantization.JPG

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.

This file may be deleted after Friday, 27 July 2007.

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
• Westwood's VQA format, used in many games

Audio codecs based on vector quantization

• TwinVQ
• Ogg Vorbis ^[1]
• AMR-WB+
• DTS

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.

References

1. "Vorbis I Specification". Xiph.org. 2007-03-09. Retrieved 2007-03-09.

External links

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