Qual é o limite de dados de compactação sem perdas? (se existir esse limite)

Ultimamente, tenho lidado com algoritmos relacionados à compactação, e me perguntava qual é a melhor taxa de compactação que pode ser alcançada pela compactação de dados sem perdas.

Até agora, a única fonte que pude encontrar sobre esse tópico foi a Wikipedia:

A compactação sem perdas de dados digitalizados, como vídeo, filme digitalizado e áudio, preserva todas as informações, mas raramente pode ser muito melhor que a compactação 1: 2 devido à entropia intrínseca dos dados.

Infelizmente, o artigo da Wikipedia não contém uma referência ou citação para apoiar esta reivindicação. Como não sou especialista em compactação de dados, gostaria de receber qualquer informação que você possa fornecer sobre esse assunto ou se puder me indicar uma fonte mais confiável que a Wikipedia.

Não tenho certeza se alguém já explicou por que o número mágico parece ser exatamente 1: 2 e não, por exemplo, 1: 1,1 ou 1:20.

Uma razão é que, em muitos casos típicos, quase metade dos dados digitalizados é ruído e o ruído (por definição) não pode ser compactado.

Eu fiz um experimento muito simples:

• Peguei um cartão cinza . Para um olho humano, parece um pedaço simples e neutro de papelão cinza. Em particular, não há informações .

• E então eu peguei um scanner normal - exatamente o tipo de dispositivo que as pessoas podem usar para digitalizar suas fotos.

• Examinei o cartão cinza. (Na verdade, digitalizei o cartão cinza junto com um cartão postal. O cartão postal estava lá para verificação de sanidade, para garantir que o software do scanner não faça nada de estranho, como adicionar automaticamente contraste ao ver o cartão cinza inexpressivo.)

• Recortei uma parte de 1000x1000 pixels do cartão cinza e a converti em escala de cinza (8 bits por pixel).

O que temos agora deve ser um bom exemplo do que acontece quando você estuda uma parte inexpressiva de uma foto em preto e branco digitalizada , por exemplo, céu claro. Em princípio, não deveria haver exatamente nada para ver.

No entanto, com uma ampliação maior, fica assim:

Não há um padrão claramente visível, mas ele não tem uma cor cinza uniforme. Parte disso é provavelmente causada pelas imperfeições do cartão cinza, mas eu diria que a maioria é simplesmente ruído produzido pelo scanner (ruído térmico na célula do sensor, amplificador, conversor A / D etc.). Parece muito com o ruído gaussiano; aqui está o histograma (em escala logarítmica ):

Agora, se assumirmos que cada pixel tem seu tom escolhido nesta distribuição, quanta entropia temos? Meu script Python me disse que temos até 3,3 bits de entropia por pixel . E isso é muito barulho.

Se esse fosse realmente o caso, implicaria que, independentemente do algoritmo de compactação usado, o bitmap de 1000 x 1000 pixels seria compactado, na melhor das hipóteses, em um arquivo de 412500 bytes. E o que acontece na prática: eu tenho um arquivo PNG de 432018 bytes, bem próximo.

Se generalizarmos um pouco demais, parece que não importa quais fotos em preto e branco digitalizo com este scanner, obteremos a soma do seguinte:

• informações "úteis" (se houver),
• barulho, aprox. 3 bits por pixel.

Agora, mesmo que seu algoritmo de compactação comporte as informações úteis em << 1 bits por pixel, você ainda terá até 3 bits por pixel de ruído incompressível. E a versão não compactada é de 8 bits por pixel. Portanto, a taxa de compressão estará no campo de 1: 2, não importa o que você faça.

Outro exemplo, com uma tentativa de encontrar condições super idealizadas:

• Uma câmera DSLR moderna, usando a configuração de sensibilidade mais baixa (menos ruído).
• Uma foto fora de foco de um cartão cinza (mesmo que houvesse alguma informação visível no cartão cinza, ela seria borrada).
• Conversão do arquivo RAW em uma imagem em escala de cinza de 8 bits, sem adicionar nenhum contraste. Eu usei configurações típicas em um conversor RAW comercial. O conversor tenta reduzir o ruído por padrão. Além disso, estamos salvando o resultado final como um arquivo de 8 bits - estamos, essencialmente, jogando fora os bits de ordem mais baixa das leituras brutas do sensor!

E qual foi o resultado final? Parece muito melhor do que o que recebi do scanner; o barulho é menos pronunciado e não há exatamente nada a ser visto. No entanto, o barulho gaussiano está lá:

E a entropia? 2,7 bits por pixel . Tamanho do arquivo na prática? 344923 bytes para 1M pixels. Em um cenário realmente melhor, com algumas trapaças, aumentamos a taxa de compactação para 1: 3.

É claro que tudo isso não tem nada a ver com a pesquisa da TCS, mas acho que é bom ter em mente o que realmente limita a compactação de dados digitalizados no mundo real. Os avanços no design de algoritmos de compressão mais sofisticados e no poder bruto da CPU não ajudarão; se você quiser economizar todo o ruído sem perdas, não poderá fazer muito melhor que 1: 2.

Você já conhece o teorema silencioso de codificação de Shannon ? Este teorema estabelece limites teóricos à compressão sem perdas. Alguns dos comentários dos outros parecem assumir que você conhece esse teorema, mas a partir da pergunta, acho que pode ser a resposta que você está procurando.

$n>0$

1. $n$

2. A solução prática comum é usar 8 bits, se os únicos números inteiros que você codificar estiverem entre 1 e 256 (generalize para 16, 32 e 64 bits, se desejar).

3. $n+1$$n$$n$

4. $\lceil\log_2 n\rceil$$\lceil\log_2 n\rceil+1$$n$$\lceil\log_2 n\rceil-1$$\lceil\log_2 n\rceil$$2\lceil\log_2 n\rceil-1$$n$$\lg n=\max(1,\lceil\log_2 n\rceil)$

5. O código gama não é o ideal$2\lceil\log_2 n\rceil-1$

6. $K$$K$não é computável. Uma solução fácil para contornar essa noção é dada pelos programas auto-delimitadores de Levin , em que você considera apenas programas com um tempo de execução limitado (por exemplo, dentro de um fator constante da duração da instância original, que é um limite inferior no complexidade do algoritmo que precisa escrever cada símbolo).

Existe uma comunidade inteira trabalhando sobre a complexidade de Kolmogorov e suas variantes, e outra comunidade trabalhando sobre a compactação sem perdas (o exemplo de números inteiros que usei tem o equivalente em muitos outros tipos de dados), eu apenas arranhei a superfície e outras podem adicionar precisões (Kolmogorov realmente não é minha especialidade), mas espero que isso possa ajudá-lo a esclarecer sua pergunta, se não necessariamente fornecer a resposta que você esperava :)

(apenas uma extensão do meu comentário)

(Como apontado por Joe em sua resposta) Shannon - em seu artigo de 1948, " Uma teoria matemática da comunicação " formulou a teoria da compactação de dados e estabeleceu que há um limite fundamental para a compactação sem perda de dados. Esse limite, chamado de taxa de entropia, é indicado por H. O valor exato de H depende da fonte de informação - mais especificamente, da natureza estatística da fonte. É possível comprimir a fonte, de maneira sem perdas, com taxa de compressão próxima a H. É matematicamente impossível fazer melhor que H.

No entanto, algumas classes de imagens (por exemplo, imagens médicas em escala de cinza) sem bordas de alto contraste e com transições suaves de nível podem ser compactadas (não tão eficientemente).

JPEG-LS e JPEG2000 parecem ser os padrões para armazenamento sem perdas de imagens médicas. Consulte esta tabela para obter uma comparação das taxas de compactação (o JPEG-LS obtém uma compactação um pouco melhor).

Usando a "compressão de imagem médica sem perdas", encontrei os seguintes artigos que podem ajudá-lo:

Uma pesquisa recente (2011) sobre técnicas de compressão de imagens médicas: Técnicas de compressão bidimensional de imagens médicas - Uma pesquisa

... Este artigo apresenta uma visão geral de várias técnicas de compressão baseadas em DCT, DWT, ROI e Redes Neurais para imagens médicas estáticas bidimensionais (2D).

Uma apresentação detalhada de dois algoritmos de compactação sem perdas padrão: JPEG-LS e JPG2000 no modo sem perdas: Compactação sem perdas de imagens médicas em escala de cinza - eficácia das abordagens tradicionais e de

... Três mil, seiscentas e setenta e nove (3.679) imagens em escala de cinza de quadro único de várias regiões anatômicas, modalidades e fornecedores, foram testadas. ...

Outra pesquisa: uma pesquisa de técnicas contemporâneas de compressão de imagens médicas

EDITAR

Talvez você ainda esteja se perguntando "O que diabos é a entropia de uma imagem?" ... OK, é a quantidade de informações contidas na imagem ... mas, para melhor entendê-las, você deve ler algo sobre as três fases normalmente usadas na compactação de imagens :

• transformação (por exemplo, Transformação discreta da wavelet)
• quantização
• codificação de entropia

Você pode usar o Google para procurar um tutorial ou livro sobre compactação de imagem (por exemplo, um tutorial rápido ) ou tentar assistir a um vídeo técnico on-line (por exemplo, Aula 16 - Introdução à codificação de imagem e vídeo ).

Pense em um arquivo como uma string.

Você nunca pode fazer melhor do que a complexidade de Kolmogorov de uma string (isso é definido pela complexidade de Komogorov).

Corrija um comprimento de string. Então agora estamos apenas olhando para cadeias de comprimento n.

Metade de todas essas seqüências de caracteres pode ser compactada no máximo 1 bit. 1/4 de todas as seqüências de caracteres pode ser compactado em no máximo 2 bits. 1/8 de todas essas seqüências de caracteres pode ser compactado em no máximo 3 bits.

Portanto, qual fração de strings (imagens, arquivos etc.) pode ser compactada na proporção de 2: 1 - muito, muito poucas. Então, por que a compactação funciona? Como quase todos os dados que pessoas reais estão realmente tentando compactar são altamente estruturados - eles não se parecem com um arquivo aleatório. Quanto mais aleatórios forem os dados, mais difícil será compactar. Eles andam de mãos dadas. A maioria das strings parece aleatória.

Para ver isso em ação, gere um arquivo aleatório usando algum processo aleatório. Quero dizer, um arquivo muito, muito aleatório. Agora tente compactá-lo usando seu algoritmo de compactação favorito. Ele permanecerá do mesmo tamanho ou aumentará, quase o tempo todo.

Por outro lado, existem cordas altamente compressíveis. Pegue a seguinte string: 100000..000 (1 seguido por um milhão de zeros). A descrição disso se encaixa na frase anterior, e um computador poderia reconstruí-lo a partir dessa descrição (ou de um muito parecido). No entanto, essa descrição não chega nem perto de um milhão de dígitos.

O fato é que as strings com essa propriedade (de serem altamente compressíveis) são extremamente raras entre todas as strings possíveis. O fato secundário é que quase todos os dados gerados por humanos são super, super compressíveis porque são muito estruturados.