Algorithme de Lloyd-Max

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



Catégories :

Théorie du signal - Compression d'image

L'algorithme de Lloyd-Max est un algorithme qui sert à 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 apporte aussi un algorithme, qui sert à construire itérativement le quantifieur optimal.

Historique

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 :

Cas spécifique

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

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

On retrouve le quantifieur scalaire uniforme, qui est par conséquent optimal pour une source de distribution uniforme.

Algorithme de Lloyd-Max

Voir aussi

Références

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Algorithme_de_Lloyd-Max.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu