Algorithme de Lloyd-Max

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche à compléter concernant l'informatique, vous pouvez partager vos connaissances en le modifiant.

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.

Sommaire

1 Historique
2 Conditions d'optimalités
- 2.1 Cas particulier
3 Algorithme de Lloyd-Max
4 Voir aussi
5 Références

[modifier] Historique

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

[modifier] 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)

[modifier] 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 = c s t e

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.

[modifier] Algorithme de Lloyd-Max

[modifier] Voir aussi

[modifier] 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.