Teoría de la distorsión de la tasa

Rama de la teoría de la información que proporciona los fundamentos teóricos para la compresión de datos con pérdida.

La teoría de la distorsión de la velocidad es una rama importante de la teoría de la información que proporciona los fundamentos teóricos para la compresión de datos con pérdida ; aborda el problema de determinar el número mínimo de bits por símbolo, medido por la velocidad R , que debe comunicarse 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 luego se envía 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 la tasa de distorsión proporciona una expresión analítica de cuánta compresión se puede lograr utilizando métodos de compresión con pérdidas. Muchas de las técnicas de compresión de audio, voz, imagen y vídeo existentes tienen transformaciones, cuantificación y procedimientos de asignación de velocidad de bits que aprovechan la forma general de las funciones de velocidad-distorsión.

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

En la teoría de la distorsión de la velocidad, la velocidad generalmente se entiende 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 constante. ^[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 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 con datos que serán percibidos por los consumidores humanos (escuchando música , viendo imágenes y videos), la medida de distorsión debería preferiblemente modelarse según la percepción humana y quizás la estética : de manera muy similar al uso de la probabilidad. En la compresión sin pérdidas , las medidas de distorsión pueden identificarse en última instancia con funciones de pérdida como las que se utilizan en la estimación bayesiana y la teoría de la decisión . En la compresión de audio, los modelos perceptivos (y, por tanto, las medidas de distorsión perceptiva) están relativamente bien desarrollados y se utilizan habitualmente en técnicas de compresión como MP3 o Vorbis , pero a menudo no son fáciles de incluir en la teoría de la distorsión de velocidad. 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 ( cuantización , normalización ) 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 al cuadrado

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

Funciones de distorsión de velocidad

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 determinada (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 mínimo sobre 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 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 alguna, entonces y . Alternativamente, si el canal de comunicación es perfecto y la señal recibida es idéntica a la señal del remitente, 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 distorsión de velocidad, 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 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, calcular una función de tasa-distorsión requiere la descripción estocástica de la entrada en términos de la PDF , y luego apunta a encontrar la PDF condicional que minimice la tasa para una distorsión dada . Estas definiciones se pueden formular desde el punto de vista teórico para tener en cuenta también 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 a este problema de minimización, excepto en algunos casos para los cuales a continuación ofrecemos dos de los ejemplos más conocidos. Se sabe que la función de distorsión de velocidad de cualquier fuente obedece a varias propiedades fundamentales, siendo las más importantes que es una función convexa (U) continua , monótonamente decreciente y, por lo tanto, la forma de la función en los ejemplos es típica (incluso la función de distorsión medida –las funciones de distorsión 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 de error al cuadrado y 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, de hecho coincide con la función 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 , coinventado por Richard Blahut , es una elegante técnica iterativa para obtener numéricamente funciones de distorsión de velocidad de fuentes alfabéticas de entrada/salida finitas arbitrarias y se ha trabajado mucho 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 tomado 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 al cuadrado

Si asumimos que es una variable aleatoria gaussiana con varianza , y si asumimos 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 tasa –función de 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 distorsión de la velocidad 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 funcionará. Como regla general, este límite sólo puede alcanzarse aumentando el parámetro de longitud del bloque de codificación. Sin embargo, incluso con longitudes de bloque unitarias, a menudo se pueden encontrar buenos cuantificadores (escalares) que operan a distancias de la función de distorsión de velocidad que son prácticamente relevantes. ^[3]

Esta función de distorsión de velocidad sólo es válida para fuentes gaussianas sin memoria. 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 trabaje, digamos, con imágenes, bien puede estar por debajo del límite inferior mostrado. ${\displaystyle R\left(D\right)}$

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

La función de distorsión de velocidad 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 distorsión de velocidad para : ${\displaystyle p=0.5}$

Conexión de la teoría de la distorsión de la 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 la distorsión de la velocidad 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 canales de Shannon que si la entropía de la fuente es H bits/símbolo y la capacidad del canal es C (donde ), entonces los bits/símbolo se perderán al transmitir esta información a través del 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)}$

Ver también

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

Referencias

1. Azul, Y.; Michaeli, T. (2019). "Repensar la compresión con pérdidas: la compensación 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. 310
3. Portada, Thomas M.; Thomas, Joy A. (2012) [2006]. "10. Teoría de la distorsión de tipos". 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 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, Sara; DeDeo, Simón. "PyRated: un paquete de Python para la teoría de la distorsión de tasas". PyRated es un paquete de Python muy simple para realizar el cálculo más básico en la teoría de distorsión de velocidad: la determinación del "libro de códigos" y la velocidad de transmisión R , dada una función de utilidad (matriz de distorsión) y un multiplicador beta de Lagrange .
• Herramienta de aprendizaje de compresión de imágenes y videos VcDemo