Linde–Buzo–Gray algorithm

On this page

Algorithm in vector quantization to derive a good codebook

The Linde–Buzo–Gray algorithm (named after its creators Yoseph Linde, Andrés Buzo and Robert M. Gray, who designed it in 1980) is an 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 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. : 361–362

We don't have any images related to Linde–Buzo–Gray algorithm yet.

You can add one yourself here.

We don't have any YouTube videos related to Linde–Buzo–Gray algorithm yet.

You can add one yourself here.

We don't have any PDF documents related to Linde–Buzo–Gray algorithm yet.

You can add one yourself here.

We don't have any Books related to Linde–Buzo–Gray algorithm yet.

You can add one yourself here.

We don't have any archived web articles related to Linde–Buzo–Gray algorithm yet.

You can submit a link to a page to archive here.

Description

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 + 𝜖 into new-codebook where 𝜖 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 > 𝜖 return codebook

References

Linde, Y.; Buzo, A.; Gray, R. (1980). "An Algorithm for Vector Quantizer Design". IEEE Transactions on Communications. 28 (1): 84–95. doi:10.1109/TCOM.1980.1094577. ISSN 0090-6778. S2CID 18530691. Retrieved 2023-12-28. https://ieeexplore.ieee.org/document/1094577 ↩
Gray, R.; Gersho, A. (1992). Vector Quantization and Signal Compression (1 ed.). Springer. doi:10.1007/978-1-4615-3626-0. ISBN 978-1-4613-6612-6. 978-1-4613-6612-6 ↩