lloyds

Optimize quantization parameters using Lloyd algorithm

Syntax

[partition,codebook] = lloyds(training_set,initcodebook)
[partition,codebook] = lloyds(training_set,len)
[partition,codebook] = lloyds(training_set,...,tol)
[partition,codebook,distor] = lloyds(...)
[partition,codebook,distor,reldistor] = lloyds(...)


Description

[partition,codebook] = lloyds(training_set,initcodebook) optimizes the scalar quantization parameters partition and codebook for the training data in the vector training_set. initcodebook, a vector of length at least 2, is the initial guess of the codebook values. The output codebook is a vector of the same length as initcodebook. The output partition is a vector whose length is one less than the length of codebook.

See Represent Partitions, Represent Codebooks, or the reference page for quantiz in this chapter, for a description of the formats of partition and codebook.

Note

lloyds optimizes for the data in training_set. For best results, training_set should be similar to the data that you plan to quantize.

[partition,codebook] = lloyds(training_set,len) is the same as the first syntax, except that the scalar argument len indicates the size of the vector codebook. This syntax does not include an initial codebook guess.

[partition,codebook] = lloyds(training_set,...,tol) is the same as the two syntaxes above, except that tol replaces 10^-7 in condition 1 of the algorithm description below.

[partition,codebook,distor] = lloyds(...) returns the final mean square distortion in the variable distor.

[partition,codebook,distor,reldistor] = lloyds(...) returns a value reldistor that is related to the algorithm's termination. In condition 1 of the algorithm below, reldistor is the relative change in distortion between the last two iterations. In condition 2, reldistor is the same as distor.

Examples

The code below optimizes the quantization parameters for a sinusoidal transmission via a three-bit channel. Because the typical data is sinusoidal, training_set is a sampled sine wave. Because the channel can transmit three bits at a time, lloyds prepares a codebook of length 2³.

% Generate a complete period of a sinusoidal signal.
x = sin([0:1000]*pi/500);
[partition,codebook] = lloyds(x,2^3)

The output is below.

partition =

  Columns 1 through 6 

   -0.8540   -0.5973   -0.3017    0.0031    0.3077    0.6023

  Column 7 

    0.8572


codebook =

  Columns 1 through 6 

   -0.9504   -0.7330   -0.4519   -0.1481    0.1558    0.4575

  Columns 7 through 8 

    0.7372    0.9515

Algorithms

lloyds uses an iterative process to try to minimize the mean square distortion. The optimization processing ends when either

• The relative change in distortion between iterations is less than 10^-7.

• The distortion is less than eps*max(training_set), where eps is the MATLAB floating-point relative accuracy.

References

[1] Lloyd, S.P., “Least Squares Quantization in PCM,” IEEE Transactions on Information Theory, Vol. IT-28, March, 1982, pp. 129–137.

[2] Max, J., “Quantizing for Minimum Distortion,” IRE Transactions on Information Theory, Vol. IT-6, March, 1960, pp. 7–12.