
86 Image and Video Compression
The LBG design algorithm is a generalization of Lloyd’s scalar quantization
technique, which was used in a pulse code modulation design of a scalar
random variable with a known probability density function and a square
error distortion.
Thus, the LBG VQ algorithm is often called the generalized Lloyd algorithm
(GLA). This algorithm was known earlier as the k-means algorithm by pat-
tern recognition people.
The algorithm proceeds as follows:
• Start with a large training set (≫N).
• Select N initial codevectors randomly. The size of the initial code-
book is the same as the size of the nal codebook.
• Encode all t