Teoria de distorção de taxa - Rate–distortion theory

A teoria da taxa de distorção é um ramo importante da teoria da informação que fornece os fundamentos teóricos para a compressão de dados com perdas ; aborda o problema de determinar o número mínimo de bits por símbolo, conforme medido pela taxa R , que deve ser comunicada através de um canal, de modo que a fonte (sinal de entrada) possa ser aproximadamente reconstruída no receptor (sinal de saída) sem exceder uma distorção D esperada .

Introdução

Codificador e decodificador de distorção de taxa. Um codificador codifica uma sequência . A sequência codificada é então fornecida a um decodificador que emite uma sequência . Tentamos minimizar a distorção entre a sequência original e a sequência reconstruída .

{\ displaystyle f_ {n}}

{\ displaystyle X ^ {n}}

{\ displaystyle Y ^ {n}}

{\ displaystyle g_ {n}}

{\ displaystyle {\ hat {X}} ^ {n}}

{\ displaystyle X ^ {n}}

{\ displaystyle {\ hat {X}} ^ {n}}

A teoria da taxa de distorção fornece uma expressão analítica de quanta compressão pode ser alcançada usando métodos de compressão com perdas. Muitas das técnicas de compressão de áudio, voz, imagem e vídeo existentes têm procedimentos de transformação, quantização e alocação de taxa de bits que capitalizam a forma geral das funções de distorção de taxa.

A teoria da taxa de distorção foi criada por Claude Shannon em seu trabalho fundamental sobre a teoria da informação.

Na teoria da distorção de taxa, a taxa é geralmente entendida como o número de bits por amostra de dados a serem armazenados ou transmitidos. A noção de distorção é um assunto em discussão contínua. No caso mais simples (que é realmente usado na maioria dos casos), a distorção é definida como o valor esperado do quadrado da diferença entre o sinal de entrada e de saída (ou seja, o erro quadrático médio ). No entanto, uma vez que sabemos que a maioria das técnicas de compressão com perdas operam em dados que serão percebidos por consumidores humanos (ouvir música , assistir fotos e vídeos), a medida de distorção deve preferencialmente ser modelada na percepção humana e talvez na estética : bem como o uso da probabilidade na compressão sem perdas , as medidas de distorção podem, em última análise, ser identificadas com as funções de perda usadas na estimativa bayesiana e na teoria de decisão . Na compressão de áudio, os modelos de percepção (e, portanto, as medidas de distorção de percepção) são relativamente bem desenvolvidos e usados rotineiramente em técnicas de compressão como MP3 ou Vorbis , mas muitas vezes não são fáceis de incluir na teoria de taxa de distorção. Na compressão de imagem e vídeo, os modelos de percepção humana são menos desenvolvidos e a inclusão é principalmente limitada à matriz de ponderação JPEG e MPEG ( quantização , normalização ).

Funções de distorção

As funções de distorção medem o custo de representar um símbolo por um símbolo aproximado . As funções de distorção típicas são a distorção de Hamming e a distorção de erro quadrático. ${\ displaystyle x}$ ${\ displaystyle {\ hat {x}}}$

Distorção de Hamming

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

Distorção de erro quadrático

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

Funções de distorção de taxa

As funções que relacionam a taxa e distorção são encontradas como a solução do seguinte problema de minimização:

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

Aqui , às vezes chamado de canal de teste, está a função de densidade de probabilidade condicional (PDF) da saída do canal de comunicação (sinal comprimido) para uma determinada entrada (sinal original) e é a informação mútua entre e 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) \,}

onde e são a entropia do sinal de saída Y e a entropia condicional do sinal de saída dado o sinal 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.}

O problema também pode ser formulado como uma função de taxa de distorção, onde encontramos as distorções mínimas acima do possível para uma determinada restrição de taxa. A expressão relevante é:

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

As duas formulações conduzem a funções que são inversas uma da outra.

A informação mútua pode ser entendida como uma medida da incerteza 'prévia' que o receptor tem sobre o sinal do emissor ( H ( Y )), diminuída pela incerteza que sobra após o recebimento da informação sobre o sinal do emissor ( ). É claro que a diminuição da incerteza se deve à quantidade de informações comunicada, que é . ${\ displaystyle H (Y \ mid X)}$ ${\ displaystyle I \ left (Y; X \ right)}$

Por exemplo, caso não haja comunicação alguma, então e . Alternativamente, se o canal de comunicação for perfeito e o sinal recebido for idêntico ao sinal do remetente, então e . ${\ 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)}$

Na definição da função de taxa de distorção, e são as distorções entre e para um dado e a distorção máxima prescrita, respectivamente. Quando usamos o erro quadrático médio como medida de distorção, temos (para amplitude - sinais contínuos ): ${\ 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) (xy) ^ { 2} \, dx \, dy = \ int _ {- \ infty} ^ {\ infty} \ int _ {- \ infty} ^ {\ infty} Q_ {Y \ mid X} (y \ mid x) P_ { X} (x) (xy) ^ {2} \, dx \, dy.}

Como mostram as equações acima, o cálculo de uma função de distorção de taxa requer a descrição estocástica da entrada em termos de PDF e, em seguida, visa encontrar a PDF condicional que minimiza a taxa para uma determinada distorção . Essas definições podem ser formuladas de forma teórica em termos de medida para levar em conta também variáveis aleatórias discretas e mistas. ${\ displaystyle X}$ ${\ displaystyle P_ {X} (x)}$ ${\ displaystyle Q_ {Y \ mid X} (y \ mid x)}$ ${\ displaystyle D ^ {*}}$

Uma solução analítica para este problema de minimização é freqüentemente difícil de obter, exceto em alguns casos para os quais oferecemos a seguir dois dos exemplos mais conhecidos. A função de taxa de distorção de qualquer fonte é conhecido para obedecer a várias propriedades fundamentais, os mais importantes são que é um contínuo , monotonamente decrescente convexa (L) função e, assim, a forma para a função nos exemplos é a taxa típica (mesmo medido –Funções de distorção na vida real tendem a ter formas muito semelhantes).

Embora as soluções analíticas para este problema sejam escassas, existem limites superior e inferior para essas funções, incluindo o famoso limite inferior de Shannon (SLB), que, no caso de erro quadrado e fontes sem memória, afirma que, para fontes arbitrárias com entropia diferencial finita,

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

onde h ( D ) é a entropia diferencial de uma variável aleatória Gaussiana com variância D. Este limite inferior é extensível a fontes com memória e outras medidas de distorção. Uma característica importante do SLB é que ele é assintoticamente rígido no regime de baixa distorção para uma ampla classe de fontes e, em algumas ocasiões, ele realmente coincide com a função de distorção de taxa. Os limites inferiores de Shannon geralmente podem ser encontrados se a distorção entre quaisquer dois números puder ser expressa como uma função da diferença entre o valor desses dois números.

O algoritmo Blahut-Arimoto , co-inventado por Richard Blahut , é uma técnica iterativa elegante para obter funções de taxa-distorção de fontes alfabéticas de entrada / saída finitas arbitrárias e muito trabalho foi feito para estendê-lo a instâncias de problemas mais gerais.

Ao trabalhar com fontes estacionárias com memória, é necessário modificar a definição da função de distorção de taxa e deve ser entendida no sentido de um limite assumido sobre sequências de comprimentos crescentes.

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

Onde

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

e

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

onde os sobrescritos denotam uma sequência completa até aquele momento e o subscrito 0 indica o estado inicial.

Fonte gaussiana sem memória (independente) com distorção de erro quadrático

Se assumirmos que é uma variável aleatória Gaussiana com variância , e se assumirmos que amostras sucessivas do sinal são estocasticamente independentes (ou equivalentemente, a fonte não tem memória ou o sinal não está correlacionado ), encontramos a seguinte expressão analítica para a taxa –Função de distorção: ${\ 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}} }

A figura a seguir mostra a aparência dessa função:

A teoria da taxa de distorção nos diz que 'não existe nenhum sistema de compressão que funcione fora da área cinza'. Quanto mais próximo um sistema de compressão prático estiver do limite vermelho (inferior), melhor será seu desempenho. Como regra geral, este limite só pode ser alcançado aumentando o parâmetro de comprimento do bloco de codificação. No entanto, mesmo em comprimentos de bloco de unidade, muitas vezes podemos encontrar bons quantizadores (escalares) que operam a distâncias da função de distorção de taxa que são praticamente relevantes.

Esta função de distorção de taxa é válida apenas para fontes Gaussianas sem memória. Sabe-se que a fonte gaussiana é a fonte mais "difícil" de codificar: para um dado erro quadrático médio, ela requer o maior número de bits. O desempenho de um sistema de compressão prático trabalhando em - digamos - imagens, pode muito bem estar abaixo do limite inferior mostrado. ${\ displaystyle R \ left (D \ right)}$

Fonte Bernoulli sem memória (independente) com distorção Hamming

A função de distorção de taxa de uma variável aleatória de Bernoulli com distorção de Hamming é 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 {matriz}} \ right.}

onde denota a função de entropia binária . ${\ displaystyle H_ {b}}$

Gráfico da função de distorção de taxa para : ${\ displaystyle p = 0,5}$

Conectando a teoria da taxa de distorção à capacidade do canal

Suponha que queremos transmitir informações sobre uma fonte para o usuário com uma distorção não superior a D . A teoria da taxa de distorção nos diz que pelo menos bits / símbolo de informação da fonte devem chegar ao usuário. Também sabemos do teorema de codificação de canal de Shannon que se a entropia da fonte for H bits / símbolo e a capacidade do canal for C (onde ), então os bits / símbolo serão perdidos ao transmitir essa informação pelo canal fornecido. Para que o usuário tenha alguma esperança de reconstruir com uma distorção máxima D , devemos impor a exigência de que a informação perdida na transmissão não exceda a perda máxima tolerável de bits / símbolo. Isso significa que a capacidade do canal deve ser pelo menos tão grande quanto . ${\ displaystyle R (D)}$ ${\ displaystyle C <H}$ ${\ displaystyle HC}$ ${\ displaystyle HR (D)}$ ${\ displaystyle R (D)}$

Veja também

Referências

links externos

PyRated : código Python para cálculos básicos na teoria da taxa de distorção.
Ferramenta de aprendizado de compressão de imagem e vídeo VcDemo

Languages

In other projects