Teoría de la distorsión de la velocidad

La teoría de la distorsión de 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 tasa 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

Tasa de distorsión encoder y decodificador. Un encoder fn{displaystyle f_{n} codifica una secuencia Xn{displaystyle X^{n}. La secuencia codificada Yn{displaystyle Y. es entonces alimentado a un decodificador gn{displaystyle g_{n} que produce una secuencia X^ ^ n{displaystyle {hat {X}} {n}}} {fn}}} {fn}}} {fn}}} {fn}}}} {fn}}}}} {fn}}}}} {fn}}. Intentamos minimizar la distorsión entre la secuencia original Xn{displaystyle X^{n} y la secuencia reconstruida X^ ^ n{displaystyle {hat {X}} {n}}} {fn}}} {fn}}} {fn}}} {fn}}}} {fn}}}}} {fn}}}}} {fn}}.

La teoría de la distorsión de velocidad 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 procedimientos de transformación, cuantificación y asignación de tasa de bits que aprovechan la forma general de las funciones de distorsión de tasa.

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

En la teoría de la tasa de distorsión, la tasa generalmente se entiende como el número de bits por muestra de datos que se almacenará o transmitirá. La noción de distorsión es un tema de discusión en curso. 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 consumidores humanos (escuchando música, viendo imágenes y videos), la medida de distorsión debe modelarse preferiblemente en la percepción humana y tal vez en la estética: al igual que el uso de la probabilidad. en la compresión sin pérdidas, las medidas de distorsión se pueden identificar en última instancia con las funciones de pérdida tal como se utilizan en la estimación bayesiana y la teoría de decisiones. En la compresión de audio, los modelos perceptuales (y, por lo tanto, las medidas de distorsión perceptiva) están relativamente bien desarrollados y se usan de forma rutinaria en técnicas de compresión como MP3 o Vorbis, pero a menudo no son fáciles de incluir en la teoría de distorsión de velocidad. En la compresión de imagen y video, los modelos de percepción humana están menos desarrollados y la inclusión se limita principalmente a la matriz de ponderación JPEG y MPEG (cuantificación, normalización).

Funciones de distorsión

Las funciones de distorsión miden el costo de representar un símbolo x{displaystyle x} por un símbolo aproximado x^ ^ {displaystyle {hat {x}}. Las funciones típicas de distorsión son la distorsión Hamming y la distorsión del terror Squared.

Distorsión de Hamming

d()x,x^ ^ )={}0six=x^ ^ 1sixل ل x^ ^ {displaystyle d(x,{hat {x})={begin{cases}0 {text{if} }x={hat {x}1 âtext{if }xneq {hat {x}end{cases}}

Distorsión de error cuadrático

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

Funciones de tasa de distorsión

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

infQY▪ ▪ X()Sí.▪ ▪ x)IQ()Y;X)sujeto aDQ≤ ≤ DAlternativa Alternativa .{displaystyle inf _{Q_{Ymid X}(ymid x)}I_{Q}(Y;X){text{ subject to }D_{Q}leq D^{*}

Aquí. QY▪ ▪ X()Sí.▪ ▪ x){displaystyle Q_{Ymid X}(ymid x)}, a veces llamado un canal de prueba, es la función de densidad de probabilidad condicional (PDF) de la salida del canal de comunicación (seña rota) Y{displaystyle Sí. para una entrada dada (señal original) X{displaystyle X}, y IQ()Y;X){displaystyle I_{Q}(Y;X)} es información mutua entre Y{displaystyle Sí. y X{displaystyle X} definidas

I()Y;X)=H()Y)− − H()Y▪ ▪ X){displaystyle I(Y;X)=H(Y)-H(Ymid X),}

Donde H()Y){displaystyle H(Y)} y H()Y▪ ▪ X){displaystyle H(Ymid 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)=− − ∫ ∫ − − JUEGO JUEGO JUEGO JUEGO PY()Sí.)log2⁡ ⁡ ()PY()Sí.))dSí.{displaystyle H(Y)=- ¿Por qué?

H()Y▪ ▪ X)=− − ∫ ∫ − − JUEGO JUEGO JUEGO JUEGO ∫ ∫ − − JUEGO JUEGO JUEGO JUEGO QY▪ ▪ X()Sí.▪ ▪ x)PX()x)log2⁡ ⁡ ()QY▪ ▪ X()Sí.▪ ▪ x))dxdSí..{displaystyle H(Ymid X)=- - No. _{-infty }{infty }Q_{Ymid X}(ymid x)P_{X}(x)log _{2}(Q_{Ymid X}(ymid x)),dx,dy.}

El problema también se puede formular 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:

infQY▪ ▪ X()Sí.▪ ▪ x)E[DQ[X,Y]]sujeto aIQ()Y;X)≤ ≤ R.{displaystyle inf - ¿Por qué?

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

La información mutua se puede entender como una medida para la incertidumbre 'prior' que el receptor tiene acerca de la señal del remitente (H()Y)), disminuido por la incertidumbre que queda después de recibir información sobre la señal del remitente (H()Y▪ ▪ X){displaystyle H(Ymid X)}). Por supuesto, la disminución de la incertidumbre se debe a la cantidad comunicada de información, que es I()Y;X){displaystyle Ileft(Y;Xright)}.

Como ejemplo, en caso de que exista no comunicación en absoluto, entonces H()Y▪ ▪ X)=H()Y){displaystyle H(Ymid X)=H(Y)} y I()Y;X)=0{displaystyle I(Y;X)=0}. Alternativamente, si el canal de comunicación es perfecto y la señal recibida Y{displaystyle Sí. es idéntico a la señal X{displaystyle X} en el remitente, entonces H()Y▪ ▪ X)=0{displaystyle H(Ymid X)=0} y I()Y;X)=H()X)=H()Y){displaystyle I(Y;X)=H(X)=H(Y)}.

En la definición de la función tasa-distorsión, DQ{displaystyle D_{Q} y DAlternativa Alternativa {displaystyle D^{*} son la distorsión entre X{displaystyle X} y Y{displaystyle Sí. para una QY▪ ▪ X()Sí.▪ ▪ x){displaystyle Q_{Ymid X}(ymid x)} y la distorsión máxima prescrita, respectivamente. Cuando usamos el error medio cuadrado como medida de distorsión, tenemos (para señales de amplitud-continua):

DQ=∫ ∫ − − JUEGO JUEGO JUEGO JUEGO ∫ ∫ − − JUEGO JUEGO JUEGO JUEGO PX,Y()x,Sí.)()x− − Sí.)2dxdSí.=∫ ∫ − − JUEGO JUEGO JUEGO JUEGO ∫ ∫ − − JUEGO JUEGO JUEGO JUEGO QY▪ ▪ X()Sí.▪ ▪ x)PX()x)()x− − Sí.)2dxdSí..{displaystyle D_{Q}=int ¿Por qué? - No. ¿Por qué?

Como muestran las ecuaciones anteriores, calcular una función de tasa–distorsión requiere la descripción estocástica de la entrada X{displaystyle X} en términos del PDF PX()x){displaystyle P_{X}(x)}, y luego tiene como objetivo encontrar el PDF condicional QY▪ ▪ X()Sí.▪ ▪ x){displaystyle Q_{Ymid X}(ymid x)} que minimiza la tasa de una distorsión dada DAlternativa Alternativa {displaystyle D^{*}. Estas definiciones pueden formularse teóricamente para dar cuenta de variables discretas y mixtas al azar también.

A menudo es difícil obtener una solución analítica para 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 velocidad 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 cuadrático y fuentes sin memoria, establece que para fuentes arbitrarias con diferencial finito entropía,

R()D)≥ ≥ h()X)− − h()D){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 de la SLB es que es asintóticamente ajustada en el régimen de baja distorsión para una amplia clase de fuentes y, en algunas ocasiones, en realidad 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, co-inventado por Richard Blahut, es una elegante técnica iterativa para obtener numéricamente funciones de distorsión de tasa 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 tasa y debe entenderse en el sentido de un límite asumido sobre secuencias de longitudes crecientes.

R()D)=limn→ → JUEGO JUEGO Rn()D){displaystyle R(D)=lim _{nrightarrow infty }R_{n}(D)}

dónde

Rn()D)=1ninfQYn▪ ▪ Xn▪ ▪ QI()Yn,Xn){displaystyle R_{n}(D)={frac {1}{n}inf ¿Por qué?

y

Q={}QYn▪ ▪ Xn()Yn▪ ▪ Xn,X0):E[d()Xn,Yn)]≤ ≤ D}{displaystyle {fn}= {fn} {fn} {fn} {fnh}} {\fn}} {\fn}}}\fn}}\fn}\\fn}\\\fnK}}}\\\\fnK}}}}}\\\\\\\\\\\\\\\\\\\\fn}\\\\\\\\\\\\\\\fn}}}\\\\\\\\\\\\\\\\\fn}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} E [d(X^{n},Y^{n})]leq D}

donde los superíndices indican 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 asumimos que X{displaystyle X} es una variable aleatoria Gaussiana con varianza σ σ 2{displaystyle sigma ^{2}, y si asumimos que muestras sucesivas de la señal X{displaystyle X} son stocásticamente independientes (o equivalentemente, la fuente es sin memoria, o la señal es no estructurado), encontramos la siguiente expresión analítica para la función de tasa-distorsión:

sigma _{x}^{2}.end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">R()D)={}12log2⁡ ⁡ ()σ σ x2/D),si0≤ ≤ D≤ ≤ σ σ x20,siD■σ σ x2.{displaystyle R(D)={begin{cases}{frac {1}{2}log _{2}(sigma _{x}^{2}/D), ventaja{if}0leq Dleq sigma ¿Por qué?sigma _{x}^{2}.end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc89a166827baad1636946909a24cf2ac58e6439" style="vertical-align: -2.671ex; width:41.25ex; height:6.509ex;"/>

La siguiente figura muestra el aspecto de 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 solo puede lograrse 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 operan a distancias de la función de tasa de distorsión que son relevantes en la práctica.

Esta función de distorsión de tarifas sólo tiene para fuentes Gaussianas sin memoria. Se sabe que la fuente gausiana es la fuente más "difícil" para codificar: para un error cuadrado medio dado, requiere el mayor número de bits. El funcionamiento de un sistema de compresión práctico que trabaja en imágenes, puede estar muy por debajo del R()D){displaystyle Rleft(Dright)} Se muestra un límite inferior.

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

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

min {(p,1-p)}end{matrix}}right.}" xmlns="http://www.w3.org/1998/Math/MathML">R()D)={}Hb()p)− − Hb()D),0≤ ≤ D≤ ≤ min()p,1− − p)0,D■min()p,1− − p){displaystyle R(D)=left{begin{matrix}H_{b}(p)-H_{b}(D), limit0leq Dleq min {(p,1-p)}, implicadmin {(p,1-p)}end{matrix}right.}min {(p,1-p)}end{matrix}}right.}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2a4c8ba5682f16c5747ef5b8a91e36e564f8f01a" style="vertical-align: -2.505ex; width:52.081ex; height:6.176ex;"/>

Donde Hb{displaystyle H_{b} denota la función binaria entropía.

Plot of the rate-distortion function for p=0.5{displaystyle p=0.5}:

Conexión de la teoría de distorsión de velocidad a 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 nos dice que al menos R()D){displaystyle R(D)} bits/symbol de información de la fuente debe llegar al usuario. También sabemos del teorema de codificación del canal de Shannon que si la entropía de la fuente es H bits/symbol, y la capacidad del canal es C (donde) <math alttext="{displaystyle CC.H{displaystyle C.H.<img alt="{displaystyle C), entonces H− − C{displaystyle H-C! bits/symbol se perderá al transmitir esta información sobre 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 H− − R()D){displaystyle H-R(D)} bits/symbol. Esto significa que la capacidad del canal debe ser al menos tan grande como R()D){displaystyle R(D)}.