VK tem um grupo com a seguinte descrição:

A mesma foto é salva manualmente todos os dias em um computador e é carregada novamente, perdendo gradualmente a qualidade.

À esquerda, a imagem original carregada em 7 de junho de 2012, à direita, o que é agora.

Essa diferença é muito suspeita. Vamos tentar descobrir o que aconteceu durante esses 7 anos. Para conhecimento, existe um artigo sobre a Medusa sobre esse grupo, mas apenas o lado técnico nos interessará.

Por que e em que estágio o JPEG é compactado com perdas

Considere um esquema de codificação e decodificação JPEG altamente simplificado. Somente essas operações são mostradas que ilustram os princípios básicos do algoritmo JPEG.

Então, 4 operações:

• DCT é uma transformação discreta de cosseno.
• Quantização - arredondando cada valor para o múltiplo mais próximo da etapa de quantização: y = [x / h] * h, onde h é a etapa.
• IDCT é a transformada cosseno discreta inversa.
• O arredondamento é o arredondamento normal. Este estágio não pôde ser mostrado no diagrama, pois é óbvio. Mas então sua importância será demonstrada.

A cor verde indica operações que salvam todas as informações (sem levar em conta as perdas ao trabalhar com números de ponto flutuante), as rosas - perdem. Ou seja, as perdas e artefatos aparecem não por causa da transformação do cosseno, mas por causa da quantização simples. O artigo não considerará uma etapa importante - a codificação de Huffman, uma vez que é realizada sem perdas.

Considere estas etapas com mais detalhes.

DCT

Como existem várias variações do DCT, apenas esclarecemos que o JPEG usa um segundo tipo de DCT com normalização. Ao codificar, cada imagem é dividida em quadrados 8x8 (para cada canal). Cada quadrado pode ser representado como um vetor de 64 dimensões. A transformação do cosseno é encontrar as coordenadas desse vetor em outra base ortonormal. Como é difícil visualizar o espaço 64-dimensional, as analogias bidimensionais serão apresentadas abaixo. Você pode imaginar que a imagem é dividida em blocos 2x1. Nos gráficos que serão mostrados abaixo, o eixo x corresponde aos valores do primeiro pixel do bloco, o eixo y ao segundo.

Continuando a analogia com um exemplo específico, suponha que os valores de dois pixels da imagem original sejam 3 e 4. Desenhe o vetor (3, 4) na base original, conforme mostrado na figura abaixo. A base original está marcada em azul. As coordenadas do vetor em alguma nova base são (4.8, 1.4).

No exemplo considerado, uma nova base foi escolhida aleatoriamente. O DCT oferece uma base fixa 64-dimensional muito específica. A justificativa de por que ela é usada em JPEG é muito interessante e foi descrita por mim em outro artigo . Nós apenas tocaremos na essência. Em geral, os valores de todos os pixels são equivalentes. Porém, se as convertermos usando o DCT, a partir das 64 coordenadas resultantes em uma nova base (denominadas coeficientes de transformação do DCT), poderemos zerar com segurança ou aproximar-se de algumas delas, com perdas mínimas. Isso é possível graças aos recursos de imagens compactáveis.

Quantização

Valores fracionários não podem ser salvos em um arquivo. Portanto, dependendo da etapa de quantização, os valores 4.8, 1.4 serão salvos da seguinte forma:

• na etapa 1 (a opção mais suave): 5 e 1,
• na etapa 2: 4 e 2,
• na etapa 3: 6 e 0.

Geralmente, a etapa é escolhida diferente para cada valor. Um arquivo JPEG possui pelo menos uma matriz, chamada tabela de quantização, que armazena 64 etapas de quantização. Esta tabela depende da qualidade da compactação definida em qualquer editor de gráficos.

IDCT

O mesmo que o DCT, mas com uma base transposta. Matematicamente, x = IDCT (DCT (x)), portanto, se não houvesse quantização, seria possível recuperar sem perda. Mas não haveria compressão. Devido ao uso da quantização, o vetor original nem sempre pode ser calculado com precisão. A figura a seguir mostra 2 exemplos com recuperação precisa e imprecisa. A grade inclinada corresponde a uma nova base, a linha reta à original.

Surge a pergunta óbvia: uma sequência de transcodificação pode levar a um vetor muito diferente do original? Talvez.

Seria interessante classificar todos os vetores inteiros e ver a que sua transcodificação levaria. Para reduzir o ruído da informação, removemos a grade da base inicial e conectaremos diretamente os vetores originais e reconstruídos (sem uma etapa intermediária) por segmentos. Primeiro, considere uma etapa de quantização igual a 1 para todas as coordenadas. A nova base na figura a seguir é girada 45 graus e, para isso, temos 17,1% de recuperações imprecisas. As cores dos segmentos não significam nada, mas serão úteis para impedir a mesclagem visual.

Essa base é de 10,3 graus, com 7,4% de recuperações imprecisas:

Próximo:

E este é 10,4 de 6,4%:

19 graus a partir de 12,5%:

Mas se você definir a etapa de quantização maior que 1, os vetores reconstruídos começarão a se concentrar claramente perto dos nós da grade. Este é o passo 5:

Este é 2:

Se você gravar a imagem várias vezes, mas com o mesmo tom, quase nada acontecerá se comparado a uma única gravação. Os valores parecem estar "presos" nos nós da grade e não podem mais "pular" de lá para outros nós. Se a etapa for diferente, o vetor irá “pular” de um nó da grade para outro. Isso pode levá-lo a qualquer lugar. A figura a seguir mostra o resultado de 4 transcodificações nas etapas 1, 2, 3, 4. Você pode ver uma grade grande na etapa 12. Esse valor é o menor múltiplo comum de 1, 2, 3, 4.

E nisso - com as etapas de 1 a 7. A visualização é mostrada apenas para parte dos vetores originais, a fim de melhorar a visualização.

Arredondamento

Por que arredondar valores após o IDCT? Afinal, se você se livrar desse estágio, a imagem restaurada será representada por valores fracionários e não perderemos nada ao recodificar. Do ponto de vista matemático, simplesmente passaremos de uma base para outra sem perda. É necessário mencionar aqui a conversão de espaços de cores. Embora o JPEG não regule o espaço de cores e permita que você salve diretamente no RGB de origem, mas na grande maioria dos casos, a conversão preliminar para YCbCr é usada. Características dos olhos e tudo isso. E essa conversão também leva a perdas.

Suponhamos que compactamos um arquivo JPEG com a máxima qualidade, ou seja, com uma etapa de quantização de 1 para todos os coeficientes. Não sabemos qual codec foi usado, mas geralmente os codecs executam o arredondamento após a conversão RGB -> YCbCr. Como a qualidade é máxima, após o IDCT, obtemos valores fracionários, mas próximos dos originais no espaço YCbCr. Se arredondarmos, a maioria deles será restaurada exatamente.

Mas, se não for arredondada, devido a essas pequenas diferenças, a conversão YCbCr -> RGB pode distanciar ainda mais os valores originais. Com a transcodificação subsequente, a diferença aumentará cada vez mais. Para visualizar de alguma forma esse processo, usamos o método do componente principal para projetar vetores 64-dimensionais em um plano. Então, para 1000 transcodificações, obtemos aproximadamente a seguinte sequência de alterações:

Os valores absolutos dos eixos aqui não fazem muito sentido, mas o significado relativo das distorções pode ser usado.

Vários exemplos de transcodificação

Gato de origem:

Após uma re-preservação com qualidade 50:

Após qualquer número subsequente de transcodificações com a mesma qualidade, a imagem não muda. Agora vamos reduzir gradualmente a qualidade de 90 para 50 em 1:

Aconteceu a mesma coisa no gráfico abaixo:

Após uma re-preservação com qualidade 20:

Sem problemas de 90 a 20:

Agora 1000 vezes com qualidade aleatória de 80 a 90:

10.000 vezes:

Análise de Fotos do Grupo VK

Vamos começar a análise de mais de 2000 fotos do grupo VK. Primeiro, verifique o desvio absoluto médio desde o primeiro. O eixo x é o número da imagem (ou dia), o eixo y é o desvio.

Vamos para o gráfico diferencial, mostrando o desvio médio absoluto das imagens vizinhas.

Pequenas flutuações no início são normais. Até o dia 232, tudo está indo bem, as fotos são completamente idênticas. E o 233º difere repentinamente em média de 1,23 para cada pixel (em uma escala de 0 a 255). Isso é muito. Talvez as tabelas de quantização tenham mudado. Confira. E, ao mesmo tempo, é comparável ao tamanho dos arquivos recebidos.

Sim, as tabelas foram alteradas. Mas não antes dos anos 700. Então, talvez, ocorreu uma transcodificação oculta intermediária com baixa qualidade. Vamos tentar recodificar o 232º duas vezes. Pela primeira vez, passaremos por diferentes níveis de qualidade e, pela segunda, usaremos a mesma tabela de quantização de todos, do 1º ao 700s. Nosso objetivo é obter a imagem o mais semelhante possível ao dia 233. Na figura a seguir, ao longo do eixo x está a qualidade da transcodificação intermediária, ao longo de y é o desvio médio absoluto da 233ª.

Embora exista uma falha no gráfico com uma qualidade de 75%, aproximadamente igual a 1, mas ainda longe do zero desejado. A adição do 2º estágio intermediário e a alteração dos parâmetros da subamostragem não melhoraram a situação.

Com o restante das imagens, tudo fica igual, além da alteração nas tabelas de quantização. Ou seja, em algum momento, a imagem muda drasticamente e estabiliza em alguns dias, mas apenas até que ocorra uma nova onda. Talvez haja uma alteração na própria imagem nos servidores. Não posso excluir completamente o envolvimento do administrador do grupo.

Infelizmente, não descobri o que realmente aconteceu com a imagem. Pelo menos agora, tenho certeza de que não foi apenas uma re-preservação. Mas, mais importante, tornou-se melhor representar os processos em andamento durante a codificação e decodificação. Espero que você também.

Arquivo com fotos , para pesquisa independente.