Algorithme de Lloyd-Max

Pour les articles homonymes, voir Lloyd.

L'algorithme de Lloyd-Max est un algorithme qui permet de construire le quantifieur scalaire optimal.

« Quantifieur optimal » veut dire, en fait, que c'est le quantifieur qui minimise la distorsion, mesurée par l'erreur quadratique moyenne. Le quantifieur est alors dit optimal au sens de l'erreur quadratique moyenne.

L'optimalité du quantifieur est assurée par deux conditions sur les niveaux de reconstruction et de décision, découvertes par Lloyd en 1957. Il fournit aussi un algorithme, qui permet de construire itérativement le quantifieur optimal.

Historique

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue !

L'algorithme est développé par Lloyd en 1957, mais malheureusement non publié. il sera redécouvert par Max en 1960.

Conditions d'optimalités

Nous reprenons les notations de l'article Quantification (signal), où le quantifieur possède N + 1 niveaux de reconstructions r_k, et N + 1 niveaux de décision t_k.

Pour une source x de densité de probabilité p_X(x), les conditions d'optimalités sur les niveaux de reconstructions r_k et de décision t_k sont obtenues en minimisant l'erreur de reconstruction (appelée aussi distorsion):

$D=E\left[|x-\hat{x}|^2\right]$

Les conditions d'optimalités sont alors données par:

• $t_k=\frac{r_k+r_{k+1}}{2}$ (1)
• $r_k=\frac{\int_{t_k}^{t_{k+1}}x p_X(x)}{\int_{t_k}^{t_{k+1}}p_X(x)}$ (2)

Cas particulier

Dans le cas d'une source uniforme: $p_X(x)=\frac{1}{t_N-t_0}$, les conditions d'optimalités se simplifient:

$r_k=\frac{t_{k+1}+t_k}{2}$

ce qui donne, en injectant dans (1):

t_k − t_{k − 1} = t_{k + 1} − t_k = q = cste

Le pas de quantification q est constant, et égale à $q=\frac{t_N-t_0}{N}$. Les niveaux de reconstruction et de décisions sont alors régis par les règles simples:

• t_k = t_{k − 1} + q
• $r_k=t_k+\frac{q}{2}$

On retrouve le quantifieur scalaire uniforme, qui est donc optimal pour une source de distribution uniforme.

Algorithme de Lloyd-Max

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue !

Voir aussi

• quantification (signal)
• quantification vectorielle
• compression d'image

Références

• M. Antonini and V. Ricordel. Chapitre Quantification, pages 45-72. Traité IC2. Hermès, Paris, janvier 2002.
• Quantization, Robert M. Gray, David L. Neuhoff, IEEE Trans. on Inf. Theory, 1998
• Source Coding Theory, Robert M. Gray
• S. P. Lloyd, Least squares quantization in PCM, IEEE Trans. Inform. Theory, vol. IT-28, pp. 129-137, Mar. 1982
• Anil K. Jain, Fundamentals of digital image processing, Prentice hall series, 1989.