Linde–Buzo–Gray algorithm: Difference between revisions

Revision as of 14:31, 28 June 2013

Revision as of 15:07, 28 June 2013

Line 1:

{{multiple issues|

The vector quantization (VQ) is a classical quantization technique which works by dividing a large set of points (vectors) into groups. Each group is represented by its centric point, as in k-means and some other clustering algorithms [26]. VQ is used for both image and sound compression. In practice, VQ is commonly used to compress data that have been digitized from an analog source, such as sampled sound and scanned images. Vector quantization is based on two facts [38]:

{{notability|date=June 2012}}

1. The compression methods that compress strings, rather than individual symbols, can, in principle, produce better results.

{{primary sources|date=June 2012}}

}}

The '''Linde–Buzo–Gray algorithm''' (introduced by Yoseph Linde, Andrés Buzo and [[Robert M. Gray]] in 1980) is a [[vector quantization]] algorithm to derive a good [[codebook]].

2. Adjacent data items in an image (i.e., pixels) and digitized sound (i.e., samples) are correlated. There is a good chance that the nearest neighbors of a pixel P will have the same values as P or very similar values. Also consecutive sound samples rarely differ by much.

For signal compression, VQ divides the signal into small blocks of pixels, typically 2×2 or 4×4. Each block is considered a vector. The encoder maintains a list (called a codebook) of vectors and compresses each blockby writing to the compressed stream a pointer to the block in the codebook. The decoder has the easy task of reading pointers, following each pointer to a block in the codebook, and joining the block to the image-so-far (see Figure 2.6). Vector quantization is thus an asymmetric compression method.

It is similar to the [[k-means]] method in [[data clustering]].

In the case of 2×2 blocks, each block (vector) consists of four pixels. If each pixel is one bit, then a block is four bits long and there are only 24=16 different blocks. It is easy to store such a small, permanent codebook in both encoder and decoder. However a pointer to a block in such a codebook is, of course, four bits long, so there is no compression gain by replacing blocks with pointers. If each pixel is k bits, then each block is 4k bits long and there are 24k different blocks [35].

==The algorithm ==

At each iteration, each vector is split into two new vectors.

*A initial state: centroid of the training sequence;

*B initial estimation #1: code book of size 2;

*C final estimation after [[Lloyd's algorithm|LGA]]: Optimal code book with 2 vectors;

*D initial estimation #2: code book of size 4;

*E final estimation after [[Lloyd's algorithm|LGA]]: Optimal code book with 4 vectors;

== References ==

* The original paper describing the algorithm, as an extension to [[Lloyd's algorithm]]:

**Linde, Y., Buzo, A., [[Robert M. Gray|Gray, R.M.]], ''An Algorithm for Vector Quantizer Design'', [[IEEE Transactions on Communications]], vol. 28, pp. 84–94, 1980. ([http://ieeexplore.ieee.org/xpls/abs_all.jsp?&arnumber=1094577 Link])

==External links==

<ref name=undefined /> jaleel sadoon

* http://www.data-compression.com/vq.html#lbg

[e-mail]<ref name=undefined />

'''Bold text'''

{{DEFAULTSORT:Linde-Buzo-Gray algorithm}}

[[Category:Data clustering algorithms]]

[[Category:Machine learning algorithms]]

[[Category:Neural networks]]

{{algorithm-stub}}

Figure 2.6: The encoder and decoder in a vector quantization [39].

An improved algorithm of VQ codebook generation approaches have been developed such as the LBG algorithm. LBG algorithm designing a codebook that best represents the set of input vectors is very-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, therefore, we resort to suboptimal codebook design schemes, and the first one that comes to mind is the simplest. It is named LBG algorithm for Linde-Buzo-Gray, also it is known as K-means clustering [39].

This algorithm is in fact designed to iteratively improve a given initial codebook. The design of a codebook with N-codeword can be stated as follows [39]:-

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 cluster size the vectors around each codeword. This is done by taking each input vector and finding theEuclidean distance between it and each codeword. The input vector belongs to the cluster of the codeword that yields the minimum distance.

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 [39].

.................. (2.1)

Where i is the component of each vector (x, y, z, directions), and m is the number of vectors in the cluster.

Repeat steps1, 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.