[76] What is Vector Quantization?

Some vector quantization software for data analysis that is available
in the ftp://cochlea.hut.fi/pub/ directory.  One package is lvq_pak and
one is som_pak (som_pak generates Kohonen maps of data using lvq to
cluster it).

A VQ-based codec that is based on the Predictive Residual Vector
Quantization is in ftp://mozart.eng.buffalo.edu/pub/prvq_codec/

VQ software is also available in ftp://isdl.ee.washington.edu/pub/VQ/


For a book on Vector Quantization, see the reference (Gersho and Gray)
given in item 7 of this FAQ. For a review article: N. M. Nasrabadi and
R. A. King, "Image Coding Using Vector Quantization: A review",
IEEE Trans. on Communications, vol. COM-36, pp. 957-971, Aug. 1988.


A short introduction to Vector Quantization, written by Alex Zatsman
<alex.zatsman@analog.com>:

In Scalar  Quantization one represents  the values by  fixed subset of
representative values. For  examples, if you  have  16 bit  values and
send  only 8 most  signifcant bits, you  get an  approximation  of the
original data  at  the expense of  precision.  In this case  the fixed
subset is all the 16-bit numbers divisable by 256, i.e 0, 256, 512,...

In  Vector Quantization  you   represent   not individual values   but
(usually small) arrays of them. A typical  example  is a color  map: a
color picture can  be  represented by  a  2D array  of  triplets  (RGB
values). In most pictures  those triplets do  not cover the  whole RGB
space but  tend to   concetrate  in certain   areas. For  example, the
picture of a forest will typically have a lot of green. One can select
a relatively  small  subset (typically 256 elements) of representative
colors, i.e RGB  triplets,  and then approximate  each  triplet by the
representative of  that small set. In case  of 256 one  can use 1 byte
instead of 3 for each pixel.

One  can do   the  same   for  any large  data  sets,  especialy  when
consecutive points are correlated in some way. CELP speech compression
algorithms  use  those subsets  "codebooks" and   use them to quantize
exciation vectors  for linear prediction  -- hence the name CELP which
stands for Codebook Excited Linear Prediction.  (See item 26 in part 1
of this FAQ for more information about CELP.)

Note that Vector Quantization, just like Scalar Quantization, is a lossy
compression.