Algorithme de Lloyd-Max

Algorithme de Lloyd-Max
Page d'aide sur l'homonymie 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

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 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)

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.

Algorithme de Lloyd-Max

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

Voir aussi

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.

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Lloyd-Max de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • 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… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • Lloyd — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Le nom Lloyd est une variation du mot gallois llwyd ou clwyd, qui signifie « gris » ou « brun ». Sommaire 1 Lloyd 1.1 …   Wikipédia en Français

  • Lloyds — Lloyd Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Le nom Lloyd est une variation du mot gallois llwyd ou clwyd, qui signifie « gris » ou « brun ». Sommaire 1 Lloyd 1.1 Pa …   Wikipédia en Français

  • Quantification (signal) — Pour les articles homonymes, voir quantification. En traitement du signal, la quantification est le procédé qui permet d approximer un signal continu (ou à valeurs dans un ensemble discret de grande taille) par des valeurs d un ensemble discret d …   Wikipédia en Français

  • Bruit de quantification — Quantification (signal) Pour les articles homonymes, voir quantification. En traitement du signal, la quantification est le procédé qui permet d approximer un signal continu (ou à valeurs dans un ensemble discret de grande taille) par des valeurs …   Wikipédia en Français

  • Erreur de quantification — Quantification (signal) Pour les articles homonymes, voir quantification. En traitement du signal, la quantification est le procédé qui permet d approximer un signal continu (ou à valeurs dans un ensemble discret de grande taille) par des valeurs …   Wikipédia en Français

  • K-means — En statistiques et en apprentissage automatique, l algorithme K means de partitionnement de données est une méthode dont le but est de diviser des observations en K partitions (clusters) dans lesquelles chaque observation appartient à la… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Physique numérique (théorique) — En physique et en cosmologie, la physique numérique est une collection de points de vue théoriques basées sur l hypothèse que l univers est, fondamentalement, descriptible par l information, et est donc calculable. Par conséquent, l univers peut… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”