Vector Quantization

In what applications is VQ used?

What is VQ?

The set of Voronoi regions partition the entire space R^k such that:

As an example we take vectors in the two dimensional case without loss of generality.  Figure 1 shows some vectors in space.  Associated with each cluster of vectors is a representative codeword.  Each codeword resides in its own Voronoi region.  These regions are separated with imaginary lines in figure 1 for illustration.  Given an input vector, the codeword that is chosen to represent it is the one in the same Voronoi region.
 
 

Figure 1: Codewords in 2-dimensional space.  Input vectors are marked with an x, codewords are marked with red circles, and the Voronoi regions are separated with boundary lines.

The representative codeword is determined to be the closest in Euclidean distance from the input vector.  The Euclidean distance is defined by:

where x_j is the jth component of the input vector, and y_ij is the jth is component of the codeword y_i.

How does VQ work in compression?

Figure 2: The Encoder and decoder in a vector quantizer.  Given an input vector, the closest codeword is found and the index of the codeword is sent through the channel.  The decoder receives the index of the codeword, and outputs the codeword.

How is the codebook designed?

Unfortunately, designing a codebook that best represents the set of input vectors is NP-hard.  That means that it requires an exhaustive search for the best possible codewords in space, and the search increases exponentially as the number of codewords increases (if you can find an optimal solution in polynomial time your name will go down in history forever).  We therefore resort to suboptimal codebook design schemes, and the first one that comes to mind is the simplest.  It is named LBG for Linde-Buzo-Gray, the authors of this idea.  This algorithm is similar to the k-means algorithm.
 

The algorithm

1. Determine the number of codewords, N,  or the size of the codebook.
2. Select N codewords at random, and let that be the initial codebook.  The initial codewords can be randomly chosen from the set of input vectors.
3. Using the Euclidean distance measure clusterize the vectors around each codeword.  This is done by taking each input vector and finding the Euclidean distance between it and each codeword.  The input vector belongs to the cluster of the codeword that yields the minimum distance.
4. Compute the new set of codewords.  This is done by obtaining the average of each cluster.  Add the component of each vector and divide by the number of vectors in the cluster.

where i is the component of each vector (x, y, z, ... directions), m is the number of vectors in the cluster.
1. Repeat steps 2 and 3 until the either the codewords don't change or the change in the codewords is small.

This algorithm is by far the most popular, and that is due to its simplicity.  Although it is locally optimal, yet it is very slow.  The reason it is slow is because for each iteration, determining each cluster requires that each input vector be compared with all the codewords in the codebook (We have programmed this algorithm in C, and for an 512x512 image, a codebook of 256, and vectors in 4 dimensions, the generation of the codebook took about 20 minutes on an HP machine).

There are many other methods to designing the codebook, methods such as Pairwise Nearest Neighbor (PNN), Simulated Annealing, Maximum Descent (MD), and Frequency-Sensitive Competitive Learning (FSCL), etc.

How does the search engine work?

The simplest search method, which is also the slowest, is full search.  In full search an input vector is compared with every codeword in the codebook.  If there were M input vectors, N codewords, and each vector is in k dimensions, then the number of multiplies becomes kMN, the number of additions and subtractions become MN((k - 1) + k) = MN(2k-1), and the number of comparisons becomes MN(k - 1).  This makes full search an expensive method.

What is the measure of performance VQ?

where M is the number of elements in the signal, or image.  For example, if we wanted to find the MSE between the reconstructed and the original image, then we would take the difference between the two images pixel by pixel, square the results, and average the results.

The PSNR is defined as follows:

where n is the number of bits per symbol.  As an example, if we want to find the PSNR between two 256 gray level images, then we set n to 8 bits.

Some sites with VQ

• For a really brief description of VQ you can visit this FAQ sheet.
• Jim Fowler was a graduate at The Ohio State University.  Now he is teaching at the Department of Electrical & Computer Engineering at Mississippi State University. He has developed a wonderful package, QccPack,  for quantization, data compression and coding  that includes VQ tools.  He also worked with video coding using VQ.  He is a definite VQer.
• Possibilistic Clustering in Kohonen Networks for Vector Quantization.  VQ using neural nets.
• Light Field Compression using Wavelet Transform and Vector Quantization.
• Robert Gray teaches at Stanford University, and within his class of Quantization and Data compression he devotes a topic to vector quantization.  This is an acrobat file of slides.
• Vivek Goyal has some interesting papers on VQ.  Check out his publications page.
• Another Neural Network based VQ with code called, Predictive Residual Vector Quantization (PRVQ) CODEC.
• Dynamic Learning Vector Quantization (DLVQ).

VQers

• Stanley Ahalt.
• Jim Fowler.
• Allen Gersho.
• Robert M. Gray.
• Batuhan Ulug .