Linde–Buzo–Gray algorithm: Difference between revisions

Revision as of 17:33, 11 February 2009

Latest revision as of 00:44, 31 July 2025

(39 intermediate revisions by 28 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 '''Linde-Buzo-Gray algorithm''' is a [[vector quantization]] algorithm to derive a good [[codebook]].

{{one source|date=December 2023}}

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

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}}

==The algorithm ==

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

== Description ==

*A initial state: centroid of the training sequence;

The Linde–Buzo–Gray algorithm may be implemented as follows:

*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;

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

==See also==

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

* [[Canopy clustering algorithm]]

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

* [[Data clustering]]

* [[K-means algorithm]]

''new-codebook'' ← {}

* [[Lloyd's algorithm]]

* [[ELBG]] - Enhanced LBG

'''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}}

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

**Linde, Y., Buzo, A., Gray, R., ''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

==External links==

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

[[Category:Data clustering algorithms]]

[[Category:Machine learning]]

[[Category:Neural networks]]

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

{{compu-sci-stub}}

[[Category:DataCluster clusteringanalysis algorithms]]

[[Category:Machine learning algorithms]]

[[Category:NeuralArtificial neural networks]]

[[Category:Signal processing]]