Teoría de la tasa de distorsión

Rama de la teoría de la información que proporciona las bases teóricas para la compresión de datos con pérdida.

La teoría de tasa-distorsión es una rama importante de la teoría de la información que proporciona las bases teóricas para la compresión de datos con pérdida ; aborda el problema de determinar la cantidad mínima de bits por símbolo, medida por la tasa R , que se debe comunicar a través de un canal, de modo que la fuente (señal de entrada) pueda reconstruirse aproximadamente en el receptor (señal de salida) sin exceder una distorsión esperada D.

Introducción

Codificador y decodificador de distorsión de velocidad. Un codificador codifica una secuencia . La secuencia codificada se envía luego a un decodificador que genera una secuencia . Intentamos minimizar la distorsión entre la secuencia original y la secuencia reconstruida . ${\displaystyle f_{n}}$ ${\displaystyle X^{n}}$ ${\displaystyle Y^{n}}$ ${\displaystyle g_{n}}$ ${\displaystyle {\hat {X}}^{n}}$ ${\displaystyle X^{n}}$ ${\displaystyle {\hat {X}}^{n}}$

La teoría de tasa-distorsión proporciona una expresión analítica de cuánta compresión se puede lograr utilizando métodos de compresión con pérdida. Muchas de las técnicas de compresión de audio, voz, imagen y video existentes tienen transformaciones, cuantificación y procedimientos de asignación de velocidad de bits que aprovechan la forma general de las funciones de tasa-distorsión.

La teoría de tasa-distorsión fue creada por Claude Shannon en su trabajo fundacional sobre la teoría de la información.

En la teoría de tasa-distorsión, la tasa se entiende generalmente como el número de bits por muestra de datos que se almacenarán o transmitirán. La noción de distorsión es un tema de discusión en curso. ^[1] En el caso más simple (que en realidad se usa en la mayoría de los casos), la distorsión se define como el valor esperado del cuadrado de la diferencia entre la señal de entrada y la de salida (es decir, el error cuadrático medio ). Sin embargo, dado que sabemos que la mayoría de las técnicas de compresión con pérdida operan en datos que serán percibidos por los consumidores humanos (escuchando música , viendo imágenes y videos), la medida de la distorsión debería modelarse preferiblemente en la percepción humana y quizás en la estética : al igual que el uso de la probabilidad en la compresión sin pérdida , las medidas de distorsión pueden identificarse en última instancia con funciones de pérdida como las que se usan en la estimación bayesiana y la teoría de la decisión . En la compresión de audio, los modelos perceptuales (y, por lo tanto, las medidas de distorsión perceptual) están relativamente bien desarrollados y se usan rutinariamente en técnicas de compresión como MP3 o Vorbis , pero a menudo no son fáciles de incluir en la teoría de tasa-distorsión. En la compresión de imágenes y vídeos, los modelos de percepción humana están menos desarrollados y la inclusión se limita principalmente a la matriz de ponderación ( cuantificación , normalización ) de JPEG y MPEG .

Funciones de distorsión

Las funciones de distorsión miden el costo de representar un símbolo mediante un símbolo aproximado . Las funciones de distorsión típicas son la distorsión de Hamming y la distorsión de error cuadrático. ${\displaystyle x}$ ${\displaystyle {\hat {x}}}$

Distorsión de Hamming

${\displaystyle d(x,{\hat {x}})={\begin{cases}0&{\text{if }}x={\hat {x}}\\1&{\text{if }}x\neq {\hat {x}}\end{cases}}}$

Distorsión de error cuadrático

${\displaystyle d(x,{\hat {x}})=\left(x-{\hat {x}}\right)^{2}}$

Funciones de tasa-distorsión

Las funciones que relacionan la velocidad y la distorsión se encuentran como solución del siguiente problema de minimización:

${\displaystyle \inf _{Q_{Y\mid X}(y\mid x)}I_{Q}(Y;X){\text{ subject to }}D_{Q}\leq D^{*}.}$

Aquí , a veces llamado canal de prueba, es la función de densidad de probabilidad condicional (PDF) de la salida del canal de comunicación (señal comprimida) para una entrada dada (señal original) , y es la información mutua entre y definida como ${\displaystyle Q_{Y\mid X}(y\mid x)}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle I_{Q}(Y;X)}$ ${\displaystyle Y}$ ${\displaystyle X}$

${\displaystyle I(Y;X)=H(Y)-H(Y\mid X)\,}$

donde y son la entropía de la señal de salida Y y la entropía condicional de la señal de salida dada la señal de entrada, respectivamente: ${\displaystyle H(Y)}$ ${\displaystyle H(Y\mid X)}$

${\displaystyle H(Y)=-\int _{-\infty }^{\infty }P_{Y}(y)\log _{2}(P_{Y}(y))\,dy}$

${\displaystyle H(Y\mid X)=-\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }Q_{Y\mid X}(y\mid x)P_{X}(x)\log _{2}(Q_{Y\mid X}(y\mid x))\,dx\,dy.}$

El problema también puede formularse como una función de tasa de distorsión, donde encontramos el ínfimo de las distorsiones alcanzables para una restricción de tasa dada. La expresión relevante es:

${\displaystyle \inf _{Q_{Y\mid X}(y\mid x)}E[D_{Q}[X,Y]]{\text{ subject to }}I_{Q}(Y;X)\leq R.}$

Las dos formulaciones conducen a funciones que son inversas entre sí.

La información mutua puede entenderse como una medida de la incertidumbre "previa" que tiene el receptor sobre la señal del emisor ( H ( Y )), disminuida por la incertidumbre que queda después de recibir información sobre la señal del emisor ( ). Por supuesto, la disminución de la incertidumbre se debe a la cantidad de información comunicada, que es . ${\displaystyle H(Y\mid X)}$ ${\displaystyle I\left(Y;X\right)}$

Por ejemplo, en caso de que no haya comunicación en absoluto, entonces y . Alternativamente, si el canal de comunicación es perfecto y la señal recibida es idéntica a la señal del emisor, entonces y . ${\displaystyle H(Y\mid X)=H(Y)}$ ${\displaystyle I(Y;X)=0}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle H(Y\mid X)=0}$ ${\displaystyle I(Y;X)=H(X)=H(Y)}$

En la definición de la función de tasa de distorsión, y son la distorsión entre y para una distorsión máxima dada y prescrita, respectivamente. Cuando utilizamos el error cuadrático medio como medida de la distorsión, tenemos (para amplitud - señales continuas ): ${\displaystyle D_{Q}}$ ${\displaystyle D^{*}}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Q_{Y\mid X}(y\mid x)}$

${\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_{Y\mid X}(y\mid x)P_{X}(x)(x-y)^{2}\,dx\,dy.}$

Como muestran las ecuaciones anteriores, el cálculo de una función de tasa-distorsión requiere la descripción estocástica de la entrada en términos de la función de densidad de probabilidad (PDF) y luego apunta a encontrar la función de densidad de probabilidad condicional que minimice la tasa para una distorsión dada . Estas definiciones se pueden formular de manera teórica para tener en cuenta también las variables aleatorias discretas y mixtas. ${\displaystyle X}$ ${\displaystyle P_{X}(x)}$ ${\displaystyle Q_{Y\mid X}(y\mid x)}$ ${\displaystyle D^{*}}$

A menudo es difícil obtener una solución analítica para este problema de minimización, excepto en algunos casos para los que a continuación ofrecemos dos de los ejemplos más conocidos. Se sabe que la función de velocidad-distorsión de cualquier fuente obedece a varias propiedades fundamentales, siendo la más importante que es una función convexa (U) continua y monótonamente decreciente y, por lo tanto, la forma de la función en los ejemplos es típica (incluso las funciones de velocidad-distorsión medidas en la vida real tienden a tener formas muy similares).

Aunque las soluciones analíticas a este problema son escasas, existen límites superiores e inferiores para estas funciones, incluido el famoso límite inferior de Shannon (SLB), que en el caso del error al cuadrado y las fuentes sin memoria, establece que para fuentes arbitrarias con entropía diferencial finita,

${\displaystyle R(D)\geq h(X)-h(D)\,}$

donde h ( D ) es la entropía diferencial de una variable aleatoria gaussiana con varianza D. Este límite inferior es extensible a fuentes con memoria y otras medidas de distorsión. Una característica importante del SLB es que es asintóticamente ajustado en el régimen de baja distorsión para una amplia clase de fuentes y, en algunas ocasiones, coincide realmente con la función de tasa-distorsión. Los límites inferiores de Shannon generalmente se pueden encontrar si la distorsión entre dos números cualesquiera se puede expresar como una función de la diferencia entre el valor de estos dos números.

El algoritmo Blahut-Arimoto , co-inventado por Richard Blahut , es una elegante técnica iterativa para obtener numéricamente funciones de tasa-distorsión de fuentes de alfabetos de entrada/salida finitas arbitrarias y se ha realizado mucho trabajo para extenderlo a instancias de problemas más generales.

Cuando se trabaja con fuentes estacionarias con memoria, es necesario modificar la definición de la función de distorsión de velocidad y debe entenderse en el sentido de un límite asumido sobre secuencias de longitudes crecientes.

${\displaystyle R(D)=\lim _{n\rightarrow \infty }R_{n}(D)}$

dónde

${\displaystyle R_{n}(D)={\frac {1}{n}}\inf _{Q_{Y^{n}\mid X^{n}}\in {\mathcal {Q}}}I(Y^{n},X^{n})}$

y

${\displaystyle {\mathcal {Q}}=\{Q_{Y^{n}\mid X^{n}}(Y^{n}\mid X^{n},X_{0}):E[d(X^{n},Y^{n})]\leq D\}}$

donde los superíndices denotan una secuencia completa hasta ese momento y el subíndice 0 indica el estado inicial.

Fuente gaussiana sin memoria (independiente) con distorsión de error cuadrático

Si suponemos que es una variable aleatoria gaussiana con varianza , y si suponemos que las muestras sucesivas de la señal son estocásticamente independientes (o equivalentemente, la fuente no tiene memoria o la señal no está correlacionada ), encontramos la siguiente expresión analítica para la función de tasa-distorsión: ${\displaystyle X}$ ${\displaystyle \sigma ^{2}}$ ${\displaystyle X}$

${\displaystyle R(D)={\begin{cases}{\frac {1}{2}}\log _{2}(\sigma _{x}^{2}/D),&{\text{if }}0\leq D\leq \sigma _{x}^{2}\\0,&{\text{if }}D>\sigma _{x}^{2}.\end{cases}}}$   ^[2]

La siguiente figura muestra cómo se ve esta función:

La teoría de la tasa de distorsión nos dice que "no existe ningún sistema de compresión que funcione fuera del área gris". Cuanto más cerca esté un sistema de compresión práctico del límite rojo (inferior), mejor será su rendimiento. Como regla general, este límite solo se puede alcanzar aumentando el parámetro de longitud del bloque de codificación. Sin embargo, incluso en longitudes de bloque unitarias, a menudo se pueden encontrar buenos cuantificadores (escalares) que funcionan a distancias de la función de tasa de distorsión que son relevantes en la práctica. ^[3]

Esta función de tasa de distorsión se cumple únicamente para fuentes sin memoria gaussianas. Se sabe que la fuente gaussiana es la fuente más "difícil" de codificar: para un error cuadrático medio dado, requiere la mayor cantidad de bits. El rendimiento de un sistema de compresión práctico que funcione con imágenes, por ejemplo, puede estar por debajo del límite inferior mostrado. ${\displaystyle R\left(D\right)}$

Fuente de Bernoulli sin memoria (independiente) con distorsión de Hamming

La función de tasa-distorsión de una variable aleatoria de Bernoulli con distorsión de Hamming viene dada por:

${\displaystyle R(D)=\left\{{\begin{matrix}H_{b}(p)-H_{b}(D),&0\leq D\leq \min {(p,1-p)}\\0,&D>\min {(p,1-p)}\end{matrix}}\right.}$

donde denota la función de entropía binaria . ${\displaystyle H_{b}}$

Gráfico de la función de tasa-distorsión para : ${\displaystyle p=0.5}$

Conexión de la teoría de la distorsión de velocidad con la capacidad del canal

Supongamos que queremos transmitir información sobre una fuente al usuario con una distorsión que no exceda D . La teoría de tasa-distorsión nos dice que al menos bits/símbolo de información de la fuente deben llegar al usuario. También sabemos por el teorema de codificación de canal de Shannon que si la entropía de la fuente es H bits/símbolo, y la capacidad del canal es C (donde ), entonces se perderán bits/símbolo al transmitir esta información por el canal dado. Para que el usuario tenga alguna esperanza de reconstruir con una distorsión máxima D , debemos imponer el requisito de que la información perdida en la transmisión no exceda la pérdida máxima tolerable de bits/símbolo. Esto significa que la capacidad del canal debe ser al menos tan grande como . ^[4] ${\displaystyle R(D)}$ ${\displaystyle C<H}$ ${\displaystyle H-C}$ ${\displaystyle H-R(D)}$ ${\displaystyle R(D)}$

Véase también

• Algoritmo de Blahut-Arimoto  : una clase de algoritmos en la teoría de la información
• Compresión de datos  : codificación compacta de datos digitales
• Decorrelación  : proceso de reducción de la correlación dentro de una o más señales.
• Optimización de tasa de distorsión  : algoritmo de decisión utilizado en la compresión de vídeoPages displaying wikidata descriptions as a fallback
• Empaquetamiento de esferas  – Estructura geométrica
• Ruido blanco  : tipo de señal en el procesamiento de señales

Referencias

1. Blau, Y.; Michaeli, T. (2019). "Replanteamiento de la compresión con pérdida: el equilibrio entre tasa, distorsión y percepción" (PDF) . Actas de la Conferencia Internacional sobre Aprendizaje Automático . PMLR. págs. 675–685. arXiv : 1901.07821 .
2. Portada y Thomas 2012, pág. 310
3. Portada, Thomas M.; Thomas, Joy A. (2012) [2006]. "10. Teoría de la distorsión de la tasa". Elementos de la teoría de la información (2.ª ed.). Wiley. ISBN 978-1-118-58577-1.
4. Berger, Toby (1971). Teoría de la distorsión de la velocidad: una base matemática para la compresión de datos . Prentice Hall. ISBN 978-0-13-753103-5. LCCN  75-148254. OCLC  156968.

Enlaces externos

• Marzen, Sarah; DeDeo, Simon. "PyRated: un paquete de Python para la teoría de la distorsión de la tasa". PyRated es un paquete de Python muy simple para realizar los cálculos más básicos en la teoría de la distorsión de la tasa: la determinación del "libro de códigos" y la tasa de transmisión R , dada una función de utilidad (matriz de distorsión) y un multiplicador de Lagrange beta .
• Herramienta de aprendizaje de compresión de imágenes y vídeos VcDemo