Vector quantization is a classical technique from signal processing, originally used for data compression, which provides a method for modeling probability density functions by the distribution of prototype vectors.

Vector quantization solves the problem of dividing a large set of points(vectors) into 'N' groups, such that each group has approximately the same number of points closest to it. The groups are represented in vector quantization by their centroid, which is also a point(vector). In this respect, it is similar to k-means and other clustering algorithms. The k-means algorithm is a variant of the Expectation-Maximization algorithm in which the goal is to determine the k means of data generated from Gaussian distributions. ... Clustering can refer to Computer clustering - (in Computer science) the connection of many low-cost computers using special hardware and software such that they can be used as one larger computer. ...

The density matching property of vector quantization is powerful, especially for identifying the density of large and high dimensioned data. It is for this reason that it is very suitable for lossy compression; data points can be represented by the index of their closest centroid, and the compressed results will have errors that are inversely proportional to the data density (i.e. commonly occurring data will have low error, and rare data will have high error).

It is possible to perform density estimation using vector quantization; the area/volume that is closer to a particular centroid than to any other is inversely proportional to the density (due to the density matching property of the algorithm). In probability and statistics, density estimation is the construction of an estimate, based on observed data, of an unobservable underlying probability density function. ...

Vector quantization can be used for prediction or lossy data correction, where the data for one or more dimension is missing; one can find the nearest group/centroid with the data dimensions available, and then fill-in/predict the result based upon the values for the missing dimension(s), assuming that they will have the same value as the group's centroid.

Vector quantization is based on the Competitive Learning Paradigm, and as such is very closely related to the self-organizing map. The self-organizing map (SOM) is a subtype of artificial neural networks. ...

Training

The training algorithm for vector quantization is a very simple iterative algorithm:

• pick a sample point at random
• move the nearest quantization vector centroid towards this sample point, by a small fraction of the distance
• repeat

There is an improved algorithm, which reduces the bias in the density matching estimation, and ensures that all vectors are used, by including an extra sensitivity parameter:

• increase each of the centroid's sensitivity by a small amount
• pick a sample point at random
• find the quantization vector centroid with the smallest <distance-sensitivity>
  • move the chosen centroid toward the sample point by a small fraction of the distance
  • set the chosen centroid's sensitivity to zero
• repeat

It is desirable to use a cooling schedule to produce convergence.

The algorithm can be iteratively updated with 'live' data, rather than by picking random points from a data set, although there will be some bias introduced by this if the data is temporally correlated over many samples.

Use in data compression

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. In computer science and information theory, data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes. ... Generally, quantization is the state of being constrained to a set of discrete values, rather than varying continuously. ... A lossy data compression method is one where compressing data and then decompressing it retrieves data that may well be different from the original, but is close enough to be useful in some way. ... In mathematics, a vector space (or linear space) is a collection of objects (called vectors) that, informally speaking, may be scaled and added. ... Screenshot (from SSCX Star Warzone). ...

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 word projection can mean more than one thing. ... Categories: Cryptography stubs | Cryptography ... An entropy encoding is a coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols. ... This article needs to be cleaned up to conform to a higher standard of quality. ...

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 [x₁,x₂,...,x_k]. This vector (of amplitude levels) is compressed by choosing the nearest matching vector from a set of N dimensional vectors [y₁,y₂,...,y_n].

All possible combinations of the N dimensional vector [y₁,y₂,...,y_n] form the codebook.

Block Diagram: A simple vector quantizer is shown below

Image: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.

Twin vector quantization (VQF) is part of the MPEG-4 standard dealing with time domain weighted interleaved vector quantization. In data compression, twin vector quantization is related to vector quantization, but the speed of the quanitzationing is doubled by the secondary vector analyzer. ... MPEG-4 is a standard used primarily to compress audio and visual (AV) digital data. ...

Video codecs based on vector quantization

• Cinepak
• Sorenson codec
• Indeo
• Westwood's VQA format, used in many games

Compressed with Cinepak, quality 40% Cinepak is a video codec, developed by Radius Inc to accommodate 1x (150 kbyte/s) CD-ROM transfer rates. ... The Sorenson codec (also known as Sorenson Video Codec 3 or SVQ3) is a digital video codec devised by the company Sorenson Media and used by Apples QuickTime and the newest version of Macromedia Flash, a special version called Sorenson Spark. ... Indeo Video (commonly known now simply as Indeo) is a video codec developed by Intel in 1992. ...

Audio codecs based on vector quantization

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

TwinVQ (transform-domain weighted interleaved vector quantization) is an audio compression technique developed by Nippon Telegraph and Telephone Corporation (NTT). ... This page is about the audio compression codec. ... AMR-WB+ is an audio codec that extends AMR-WB. It adds support for stereo signals and higher sampling rates. ... DTS Coherent Acoustics is the full name for the audio format standard usually known as just DTS. It is covered in U.S. Patent 5,956,674. ...

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. Speech coding is the compression of speech (into a code) for transmission with speech codecs that use audio signal processing and speech processing techniques. ... This page is about the audio compression codec. ... This is the Voronoi diagram of a random set of points in the plane (all points lie within the image). ... Rate distortion theory is the branch of information theory addressing the problem of determining the minimal amount of entropy (or information) R that should be communicated over a channel such that the source (input signal) can be reconstructed at the receiver (output signal) with given distortion D. As such, rate... Clustering is the classification of objects into different groups, or more precisely, the partitioning of a data set into subsets (clusters), so that the data in each subset (ideally) share some common trait - often proximity according to some defined distance measure. ... LVQ, or Learning Vector Quantization, is a prototype-based supervised classification algorithm. ... This article does not cite any references or sources. ...

References

1. ^ Vorbis I Specification. Xiph.org (2007-03-09). Retrieved on 2007-03-09.

Year 2007 (MMVII) is the current year, a common year starting on Monday of the Gregorian calendar and the AD/CE era. ... is the 68th day of the year (69th in leap years) in the Gregorian calendar. ...

External links

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