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 parameterspartitionandcodebookfor the training data in the vectortraining_set.initcodebook, a vector of length at least 2, is the initial guess of the codebook values. The outputcodebook是一个vector of the same length asinitcodebook. The outputpartition是一个vector whose length is one less than the length ofcodebook.

SeeRepresent Partitions,Represent Codebooks, or the reference page forquantizin this chapter, for a description of the formats ofpartitionandcodebook.

Note

lloydsoptimizes for the data intraining_set. For best results,training_setshould 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 argumentlenindicates the size of the vectorcodebook. This syntax does not include an initial codebook guess.

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

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

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

Examples

The code below optimizes the quantization parameters for a sinusoidal transmission via a three-bit channel. Because the typical data is sinusoidal,training_setis a sampled sine wave. Because the channel can transmit three bits at a time,lloydsprepares 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

lloydsuses 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 thaneps*max(training_set), whereepsis the MATLAB floating-point relative accuracy.

References

[1] Lloyd, S.P., “Least Squares Quantization in PCM,”IEEE信息理论, 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.

Version History

Introduced before R2006a