Théorie du taux – distorsion – Wikipedia wiki

Théorie du taux de distorsion est une branche majeure de la théorie de l’information qui fournit les fondements théoriques de la compression des données avec perte; Il aborde le problème de la détermination du nombre minimal de bits par symbole, tel que mesuré par le taux R , cela doit être communiqué sur un canal, afin que la source (signal d’entrée) puisse être approximativement reconstruite au niveau du récepteur (signal de sortie) sans dépasser une distorsion attendue D .

Introduction [ modifier ]]

La théorie du taux-distorsion donne une expression analytique pour la quantité de compression que la compression peut être obtenue en utilisant des méthodes de compression avec perte. Bon nombre des techniques de compression audio, de la parole, de l’image et des vidéos existantes ont des procédures de transformations, de quantification et d’allocation de taux de bit qui capitalisent sur la forme générale des fonctions de taux-distorsion.

La théorie du taux-distorsion a été créée par Claude Shannon dans son travail fondamental sur la théorie de l’information.

Dans la théorie du taux – distorsion, le taux est généralement compris comme le nombre de bits par échantillon de données à stocker ou à transmettre. La notion de Distorsion est un sujet de discussion en cours. ^[d’abord] Dans le cas le plus simple (qui est réellement utilisé dans la plupart des cas), la distorsion est définie comme la valeur attendue du carré de la différence entre l’entrée et le signal de sortie (c’est-à-dire l’erreur carré moyenne). Cependant, puisque nous savons que la plupart des techniques de compression avec perte fonctionnent sur des données qui seront perçues par les consommateurs humains (écouter de la musique, regarder des images et des vidéos), la mesure de la distorsion devrait de préférence être modélisée sur la perception humaine et peut-être l’esthétique: un peu comme l’utilisation de la probabilité Dans la compression sans perte, les mesures de distorsion peuvent finalement être identifiées avec les fonctions de perte utilisées dans l’estimation bayésienne et la théorie de la décision. Dans la compression audio, les modèles perceptuels (et donc les mesures de distorsion perceptuelle) sont relativement bien développés et systématiquement utilisés dans les techniques de compression tels que MP3 ou Vorbis, mais ne sont souvent pas faciles à inclure dans la théorie du taux-distorsion. Dans la compression d’image et de vidéo, les modèles de perception humaine sont moins bien développés et l’inclusion est principalement limitée à la matrice JPEG et MPEG de pondération (quantification, normalisation).

Fonctions de distorsion [ modifier ]]

Les fonctions de distorsion mesurent le coût de la représentation d’un symbole

${displaystyle x}$

par un symbole approximatif

${displayStyle {hat {x}}}$

. Les fonctions de distorsion typiques sont la distorsion de Hamming et la distorsion d’erreur carrée.

Distorsion de Hamming [ modifier ]]

${displayStyle d (x, {hat {x}}) = {begin {case} 0 & {text {if}} x = {hat {x}} \ 1 & {text {if}} xneq {hat {x}} end {cas}}}$

Distorsion d’erreur carrée [ modifier ]]

${displayStyle d (x, {hat {x}}) = Left (x- {hat {x}} droit) ^ {2}}$

Fonctions de taux de distorsion [ modifier ]]

Les fonctions qui relient le taux et la distorsion sont trouvées comme la solution du problème de minimisation suivant:

${displayStyle inf _ {q_ {ymid x} (ymid x)} i_ {q} (y; x) {texte {soumis à}} d_ {q} leq d ^ {*}.}.$

Ici

${displayStyle q_ {ymid x} (ymid x)}$

, parfois appelé canal de test, est la fonction de densité de probabilité conditionnelle (PDF) de la sortie du canal de communication (signal compressé)

${displaystyle y}$

pour une entrée donnée (signal d’origine)

${displaystyle x}$

, et

${displayStyle i_ {q} (y; x)}$

est le informations mutuelles entre

${displaystyle y}$

et

${displaystyle x}$

défini comme

${displayStyle i (y; x) = h (y) -h (ymid x),}$

où

${displayStyle h (y)}$

et

${displayStyle h (ymid x)}$

sont l’entropie du signal de sortie ET et l’entropie conditionnelle du signal de sortie étant donné le signal d’entrée, respectivement:

${DisplayStyle h (y) = -int _ {-infty} ^ {infty} p_ {y} (y) log _ {2} (p_ {y} (y)), dy}$

${displayStyle h (ymid x) = – int _ {- infty} ^ {infty} int _ {- infty} ^ {infty} q_ {ymid x} (ymid x) p_ {x} (x) log _ {2} (Q_ {ymid x} (ymid x)), dx, dy.}$

Le problème peut également être formulé comme une fonction de distorsion-taux, où nous trouvons l’infimum sur les distorsions réalisables pour la contrainte de taux donnée. L’expression pertinente est:

${displayStyle inf _ {q_ {ymid x} (ymid x)} e [d_ {q} [x, y]] {texte {soumis à}} i_ {q} (y; x) leq r.}$

Les deux formulations conduisent à des fonctions qui sont inversées les unes des autres.

Les informations mutuelles peuvent être comprises comme une mesure pour l’incertitude «antérieure» que le récepteur a sur le signal de l’expéditeur ( H ( ET )), diminué par l’incertitude qui reste après avoir reçu des informations sur le signal de l’expéditeur (

${displayStyle h (ymid x)}$

). Bien sûr, la diminution de l’incertitude est due à la quantité communiquée d’informations, qui est

${displayStyle ileft (y; xRight)}$

.

Par exemple, en cas de cas Non communication du tout, alors

${displayStyle h (ymid x) = h (y)}$

et

${displayStyle i (y; x) = 0}$

. Alternativement, si le canal de communication est parfait et le signal reçu

${displaystyle y}$

est identique au signal

${displaystyle x}$

à l’expéditeur, alors

${displayStyle h (ymid x) = 0}$

et

${DisplayStyle i (y; x) = h (x) = (y)}$

.

Dans la définition de la fonction taux-distorsion,

${displayStyle d_ {q}}$

et

${displayStyle d ^ {*}}$

sont la distorsion entre

${displaystyle x}$

et

${displaystyle y}$

pour une donnée

${displayStyle q_ {ymid x} (ymid x)}$

et la distorsion maximale prescrite, respectivement. Lorsque nous utilisons l’erreur quadratique moyenne comme mesure de distorsion, nous avons (pour les signaux continues de l’amplitude):

${displayStyle d_ {q} = int _ {- infty} ^ {infty} int _ {- infty} ^ {infty} p_ {x, y} (x, y) (x-y) ^ {2}, dx, dy = int _ {- infty} ^ {infty} int _ {- infty} ^ {infty} q_ {ymid x} (ymid x) p_ {x} (x) (x-y) ^ {2}, dx, dy.}$

Comme le montrent les équations ci-dessus, le calcul d’une fonction de taux-distorsion nécessite la description stochastique de l’entrée

${displaystyle x}$

en termes de PDF

${displayStyle p_ {x} (x)}$

, puis vise à trouver le PDF conditionnel

${displayStyle q_ {ymid x} (ymid x)}$

qui minimisent le taux pour une distorsion donnée

${displayStyle d ^ {*}}$

. Ces définitions peuvent être formulées en théorie pour tenir compte des variables aléatoires discrètes et mixtes.

Une solution analytique à ce problème de minimisation est souvent difficile à obtenir, sauf dans certains cas pour lesquelles nous proposons ensuite deux des exemples les plus connus. La fonction de taux-distorsion de toute source est connue pour obéir à plusieurs propriétés fondamentales, les plus importantes étant qu’il s’agit d’une fonction convexe (U) continue et décroissante monotone et donc la forme de la fonction dans les exemples est typique (même le taux mesuré mesuré –Les fonctions de distorsion dans la vie réelle ont tendance à avoir des formes très similaires).

Bien que les solutions analytiques à ce problème soient rares, il existe des limites supérieures et inférieures à ces fonctions, notamment la célèbre borne inférieure de Shannon (SLB), qui dans le cas d’une erreur carrée et de sources sans mémoire, indique que pour des sources arbitraires avec une entropie différentielle finie,

${displayStyle r (d) geq h (x) -h (d),}$

où H ( D ) est l’entropie différentielle d’une variable aléatoire gaussienne avec la variance D. Cette limite inférieure est extensible aux sources avec la mémoire et d’autres mesures de distorsion. Une caractéristique importante du SLB est qu’elle est asymptotiquement serrée dans le régime de faible distorsion pour une large classe de sources et à certaines occasions, il coïncide en fait avec la fonction de taux-distorsion. Les limites inférieures de Shannon peuvent généralement être trouvées si la distorsion entre deux nombres peut être exprimée en fonction de la différence entre la valeur de ces deux nombres.

L’algorithme de Blahut – Arimoto, co-inventé par Richard Blahut, est une technique itérative élégante pour obtenir des fonctions de taux de taux et de distorsion numérique des sources d’alphabet d’entrée / sortie finies arbitraires et beaucoup de travail a été fait pour l’étendre à des instances de problèmes plus générales.

Lorsque vous travaillez avec des sources stationnaires avec de la mémoire, il est nécessaire de modifier la définition de la fonction de distorsion de taux et il doit être compris dans le sens d’une limite de séquences prises en fonction des longueurs croissantes.

${displayStyle r (d) = lim _ {nrightarrow infty} r_ {n} (d)}$

où

$gens }, X ^ {n})}$

et

${displayStyle {mathcal {q}} = {q_ {y ^ {n} mid x ^ {n}} (y ​​^ {n} mid x ^ {n}, x_ {0}): e [d (x ^ {{ n}, y ^ {n})] leq d}}$

où les exposés indiquent une séquence complète jusqu’à ce moment et l’indice 0 indique l’état initial.

Source gaussienne sans mémoire (indépendante avec une distorsion d’erreur carrée [ modifier ]]

Si nous supposons que

${displaystyle x}$

est une variable aléatoire gaussienne avec variance

${displayStyle Sigma ^ {2}}$

, et si nous supposons que des échantillons successifs du signal

${displaystyle x}$

sont stochastiques indépendantes (ou de manière équivalente, la source est sans mémoire ou le signal est non corrélé ), nous trouvons l’expression analytique suivante pour la fonction de taux-distorsion:

${displayStyle r (d) = {begin {cas _ {x} ^ {2} \ 0, & {text {if}} d> sigma _ {x} ^ {2} .end {cas}}}$

[2] ^{: 310}

La figure suivante montre à quoi ressemble cette fonction:

La théorie du taux-distorsion nous dit qu ‘«aucun système de compression n’existe qui se produit en dehors de la zone grise». Plus un système de compression pratique est proche de la limite rouge (inférieure), mieux elle fonctionne. En règle générale, cette limite ne peut être atteinte qu’en augmentant le paramètre de longueur de bloc de codage. Néanmoins, même chez les longues de blocs d’unité, on peut souvent trouver de bons quantités (scalaires) qui fonctionnent à des distances de la fonction de taux-distorsion qui sont pratiquement pertinentes. ^[2]

Cette fonction de taux-distorsion ne vaut que pour les sources sans mémoire gaussiennes. Il est connu que la source gaussienne est la source la plus “difficile” à encoder: pour une erreur quadratique moyenne, elle nécessite le plus grand nombre de bits. Les performances d’un système de compression pratique travaillant – par exemple -, peuvent bien être inférieures à la

${DisplayStyle Rleft (Dright)}$

Bound inférieur indiqué.

Source de Bernoulli sans mémoire (indépendante) avec distorsion de Hamming [ modifier ]]

La fonction de débit-distorsion d’une variable aléatoire de Bernoulli avec distorsion de Hamming est donnée par:

${displayStyle r (d) = Left {{begin {matrix} h_ {b} (p) -h_ {b} (d), & 0leq dleq min {(p, 1-p)} \ 0, & d> min {((( p, 1-p)} fin {matrice}} à droite.}$

${displayStyle h_ {b}}$

indique la fonction d’entropie binaire.

Tracé de la fonction de taux-distorsion pour

${displayStyle p = 0,5}$

:

Connexion de la théorie des taux de distorsion à la capacité du canal ^[3] [ modifier ]]

Supposons que nous voulons transmettre des informations sur une source à l’utilisateur avec une distorsion ne dépassant pas D . La théorie du taux – distorsion nous dit qu’au moins

${displayStyle r (d)}$

Les bits / symbole des informations de la source doivent atteindre l’utilisateur. Nous savons également du théorème de codage de la chaîne de Shannon que si l’entropie source est H bits / symbole, et la capacité du canal est C (où

${DisplayStyle C$

), alors

${displaystyle h-c}$

Les bits / symboles seront perdus lors de la transmission de ces informations sur le canal donné. Pour que l’utilisateur ait un espoir de reconstruire avec une distorsion maximale D , nous devons imposer l’exigence que les informations perdues en transmission ne dépassent pas la perte tolérable maximale de

${displayStyle h-r (d)}$

bits / symbole. Cela signifie que la capacité du canal doit être au moins aussi grande que

${displayStyle r (d)}$

.

Voir également [ modifier ]]

Les références [ modifier ]]

1. ^ Blue, Y. & Michaeli, T. “Repenser la compression avec perte: le compromis de rate-perception” . Actes de la Conférence internationale sur l’apprentissage automatique, 2019.
2. ^ ^{un b} Thomas M. Cover, Joy A. Thomas (2006). Éléments de la théorie de l’information . John Wiley & Sons, New York.
3. ^ Toby Berger (1971). Théorie de la distorsion des taux: une base mathématique pour la compression des données . Prentice Hall.

Liens externes [ modifier ]]