Linde–Buzo–Gray algorithm: Difference between revisions

Revision as of 14:31, 28 June 2013

Latest revision as of 00:44, 31 July 2025

(23 intermediate revisions by 16 users not shown)

Line 1:

{{missing information|general information, usage in the field (mention cinepak?), optimality conditions, choice of {{epsilon}}s, model instead of training data, ELBG|date=December 2023}}

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]:

{{one source|date=December 2023}}

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

The '''Linde–Buzo–Gray algorithm''' (named after its creators Yoseph Linde, Andrés Buzo and [[Robert M. Gray]], who designed it in 1980)<ref>{{Cite journal| doi = 10.1109/TCOM.1980.1094577| issn = 0090-6778| volume = 28| issue = 1| pages = 84–95| last1 = Linde| first1 = Y.| last2 = Buzo| first2 = A.| last3 = Gray| first3 = R.| title = An Algorithm for Vector Quantizer Design| journal = IEEE Transactions on Communications| date = 1980| s2cid = 18530691}}</ref> is an [[Iterative method|iterative]] [[vector quantization]] algorithm to improve a small set of vectors (codebook) to represent a larger set of vectors (training set), such that it will be [[Local optimum|locally optimal]]. It combines [[Lloyd's Algorithm]] with a splitting technique in which larger codebooks are built from smaller codebooks by splitting each code vector in two. The core idea of the algorithm is that by splitting the codebook such that all code vectors from the previous codebook are present, the new codebook must be as good as the previous one or better. <ref name=gray1992>{{Cite book| edition = 1| publisher = Springer| isbn = 978-1-4613-6612-6| last1 = Gray| first1 = R.| last2 = Gersho| first2 = A.| title = Vector Quantization and Signal Compression| date = 1992| doi = 10.1007/978-1-4615-3626-0| url = https://doi.org/10.1007/978-1-4615-3626-0}}</ref>{{rp|361-362}}

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.

== Description ==

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 Linde–Buzo–Gray algorithm may be implemented as follows:

'''algorithm''' linde-buzo-gray '''is'''

'''input''': set of training vectors ''training'', codebook to improve ''old-codebook''

'''output''': codebook that is twice the size and better or as good as ''old-codebook''

''new-codebook'' ← {}

'''for each''' ''old-codevector'' '''in''' ''old-codebook'' '''do'''

insert ''old-codevector'' into ''new-codebook''

insert ''old-codevector'' + {{epsilon}} into ''new-codebook'' where {{epsilon}} is a small vector

'''return''' lloyd(''new-codebook'', ''training'')

'''algorithm''' lloyd '''is'''

'''input''': ''codebook'' to improve, set of training vectors ''training''

'''output''': improved codebook

'''do'''

''previous-codebook'' ← ''codebook''

''clusters'' ← divide ''training'' into |''codebook''| clusters, where each cluster contains all vectors in ''training'' who are best represented by the corresponding vector in ''codebook''

'''for each''' cluster ''cluster'' in ''clusters'' '''do'''

the corresponding code vector in ''codebook'' ← the centroid of all training vectors in ''cluster''

'''while''' difference in error representing ''training'' between ''codebook'' and ''previous-codebook'' &gt; {{epsilon}}

'''return''' ''codebook''

== References ==

{{reflist}}

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

<ref name=undefined /> jaleel sadoon

[[Category:Cluster analysis algorithms]]

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

[[Category:Machine learning algorithms]]

'''Bold text'''

[[Category:Artificial neural networks]]

[[Category:Signal processing]]

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.