Teoría de la tasa-distorsión - Enciclopedia

Teoría de la tasa-distorsión es una rama principal 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 el número mínimo de bits por símbolo, medido por la tasa R, que debe comunicarse a través de un canal, de manera que la fuente (señal de entrada) pueda reconstruirse aproximadamente en el receptor (señal de salida) sin superar una distorsión esperada D.

Introducción

La teoría de la tasa-distorsión proporciona una expresión analítica para cuánto se puede lograr en términos de compresión utilizando métodos de compresión con pérdida. Muchos de los métodos de compresión de audio, voz, imágenes y video existentes tienen transformadas, cuantificación y procedimientos de asignación de tasa de bits que capitalizan la forma general de las funciones de tasa-distorsión.
La teoría de la 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 la tasa-distorsión, la tasa se entiende generalmente como el número de bits por muestra de datos a almacenar o transmitir. La noción de distorsión es un tema de discusión continua. En el caso más simple (que se utiliza realmente 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 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 consumidores humanos (escuchando música, viendo imágenes y videos), la medida de distorsión debe preferiblemente basarse en la percepción humana y tal vez en la estética: al igual que el uso de probabilidad en la compresión sin pérdida, las medidas de distorsión pueden identificarse finalmente con las funciones de pérdida como se utilizan en la estimación bayesiana y la teoría de la toma de decisiones. 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 utilizan 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 la tasa-distorsión. En la compresión de imágenes y video, los modelos de percepción humana están menos desarrollados y su inclusión se limita principalmente a la matrices de ponderación (cuantificación, normalización) JPEG y MPEG.

Funciones de distorsión

Las funciones de distorsión miden el costo de representar un símbolo

x

por un símbolo aproximado

x̂

. Las funciones de distorsión típicas son la distorsión de Hamming y la distorsión del cuadrado del error.

= Distorsión de Hamming =

d(x, x̂) = { 0, si x = x̂; 1, si x ≠ x̂ }

= Distorsión del cuadrado del error =

d(x, x̂) = (x - x̂)²

Funciones de tasa-distorsión

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

inf QY∣X(y∣x) IQ(Y;X)

sujeta a DQ ≤ D∗.

Aquí

QY∣X(y∣x)

, a veces llamada canal de prueba, es la función de densidad de probabilidad condicional (PDF) de la salida del canal de comunicación (señal comprimida) Y para una señal de entrada dada X, y IQ(Y;X) es la información mutua entre Y y X, definida como

I(Y;X) = H(Y) - H(Y∣X)

donde H(Y) y H(Y∣X) 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:

H(Y) = -∫_{-\infty}^{\infty} P_Y(y) log_2(P_Y(y)) dy

H(Y∣X) = -∫_{-\infty}^{\infty} ∫_{-\infty}^{\infty} QY∣X(y∣x) P_X(x) log_2(QY∣X(y∣x)) dx dy

El problema también se puede formular como una función de distorsión-tasa, donde encontramos el infimo sobre las distorsiones alcanzables para una restricción de tasa dada. La expresión relevante es:

inf QY∣X(y∣x) E[DQ[X,Y]]

sujeta a IQ(Y;X) ≤ 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 (H(Y∣X)). Por supuesto, la disminución de la incertidumbre es debida a la cantidad de información comunicada, que es I(Y;X).
Como ejemplo, en caso de que no haya comunicación alguna, entonces H(Y∣X) = H(Y) y I(Y;X) = 0. Alternativamente, si el canal de comunicación es perfecto y la señal recibida Y es idéntica a la señal X en el emisor, entonces H(Y∣X) = 0 y I(Y;X) = H(X) = H(Y).
En la definición de la función de tasa-distorsión, DQ y D∗ son la distorsión entre X e Y para una dada QY∣X(y∣x) y la distorsión máxima prescrita, respectivamente. Cuando utilizamos el error cuadrático medio como medida de distorsión, tenemos (para señales de amplitud continua):

DQ = ∫_{-\infty}^{\infty} ∫_{-\infty}^{\infty} P_{X,Y}(x,y)(x-y)² dx dy = ∫_{-\infty}^{\infty} ∫_{-\infty}^{\infty} QY∣X(y∣x) P_X(x)(x-y)² dx dy

Como muestran las ecuaciones anteriores, calcular una función de tasa-distorsión requiere la descripción estocástica de la entrada X en términos de la PDF P_X(x), y luego buscar la PDF condicional QY∣X(y∣x) que minimize la tasa para una distorsión dada D∗. Estas definiciones se pueden formular teóricamente para tener en cuenta variables aleatorias discretas y mixtas.
Una solución analítica a este problema de minimización es difícil de obtener excepto en algunos casos para los que presentamos dos de los mejores ejemplos. Se sabe que la función de tasa-distorsión de cualquier fuente obedece a varias propiedades fundamentales, las más importantes siendo que es una función continua, monótonamente decreciente y convexa (U), por lo que la forma de la función en los ejemplos es típica (incluso las funciones de tasa-distorsión medidas en la vida real tienden a tener formas muy similares).
A pesar de que las soluciones analíticas a este problema son escasas, hay límites superior e inferior a estas funciones, incluyendo el famoso límite inferior de Shannon (SLB), que en el caso de fuentes con error cuadrático y memoria menos, establece que para fuentes con entropía diferencial finita,

R(D) ≥ h(X) - h(D)

donde h(D) es la entropía diferencial de una variable aleatoria gaussiana con varianza D. Este límite inferior se puede extender a fuentes con memoria y otras medidas de distorsión. Una característica importante del SLB es que es asintóticamente cercano 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 de tasa-distorsión. Los límites inferiores de Shannon se pueden encontrar generalmente si la distorsión entre cualquier dos números puede expresarse como una función de la diferencia entre los valores de estos dos números.
El algoritmo Blahut–Arimoto, co-inventado por Richard Blahut, es una técnica iterativa elegante para obtener numéricamente las funciones de tasa-distorsión de fuentes de entrada/salida alfanuméricas finitas arbitraias y se ha realizado mucho trabajo para extenderlo a instancias de problemas más generales.
El cálculo de la función de tasa-distorsión requiere conocimiento de la distribución subyacente, que a menudo no está disponible en aplicaciones contemporáneas en ciencias de datos y aprendizaje automático. Sin embargo, este desafío se puede abordar utilizando estimadores basados en aprendizaje profundo de la función de tasa-distorsión. Estos estimadores se denominan típicamente 'estimadores neurales', que involucran la optimización de una forma variacional parametrizada del objetivo de tasa-distorsión.
Cuando se trabaja con fuentes estacionarias con memoria, es necesario modificar la definición de la función de tasa-distorsión y debe entenderse en el sentido de un límite tomado sobre secuencias de longitudes crecientes.

R(D) = lim_{n→∞} R_n(D)

donde

R_n(D) = 1/n inf_{Q_{Y^n∣X^n}∈Q} I(Y^n,X^n)

y

Q = {Q_{Y^n∣X^n}(Y^n∣X^n,X_0) : E[d(X^n,Y^n)] ≤ D}

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

= Fuente gaussiana (independiente) de Bernoulli con distorsión de Hamming =

La función de tasa-distorsión de una variable aleatoria binaria de Bernoulli con distorsión de Hamming se da por:

R(D) = { H_b(p) - H_b(D), 0 ≤ D ≤ min(p, 1-p); 0, D > min(p, 1-p) }

donde H_b denota la función de entropía binaria.
Gráfico de la función de tasa-distorsión para p = 0.5:

La teoría de la tasa-distorsión nos dice que 'no existe ningún sistema de compresión que realice 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 a longitudes de bloque unitarias, a menudo se pueden encontrar cuantificadores (escalar) que operan a distancias de la función de tasa-distorsión que son prácticamente relevantes.
Esta función de tasa-distorsión solo se aplica a fuentes gaussianas con memoria menos. Se sabe que la fuente gaussiana es la más "difícil" de codificar: para un error cuadrático medio dado, requiere el mayor número de bits. El rendimiento de un sistema de compresión práctico que trabaja en, digamos, imágenes, puede estar bien por debajo del límite inferior R(D) mostrado.

Ver también

Algoritmo Blahut–Arimoto - Clase de algoritmos en la teoría de la información
Compresión de datos - Codificación compacta de datos digitales
Descorrelación - Proceso de reducción de correlación dentro de una o más señales
Optimización de tasa-distorsión
Empaquetamiento esférico - Estructura geométrica
Ruido blanco - Tipo de señal en el procesamiento de señales

Referencias


Enlaces externos

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