Algorithme de Lloyd-Max

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
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.

Sommaire

[modifier] Historique

Cette section est vide, pas assez 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.

[modifier] Conditions d'optimalités

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

Pour une source x de densité de probabilité pX(x), les conditions d'optimalités sur les niveaux de reconstructions rk et de décision tk, 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):

tk − tk − 1 = tk + 1 − tk = 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:

  • tk = tk − 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

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

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