Linde–Buzo–Gray algorithm

The Linde-Buzo-Gray algorithm is a vector quantization algorithm to derive a good codebook. It is similar to the k-means method in data clustering.

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 LGA: Optimal code book with 2 vectors;
• D initial estimation #2: code book of size 4;
• E final estimation after LGA: Optimal code book with 4 vectors;

See also

• Canopy clustering algorithm
• Data clustering
• K-means algorithm
• Lloyd's algorithm
• ELBG - Enhanced LBG

References

• 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