PDI_III.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><div style=\"text-align: center\"><img width=300px src=\"http://amaq.lais.huol.ufrn.br/static/img/logo-lais.png\"></div>\n",
    "<br><br><br>\n",
    "<center>\n",
    "<h1>Processamento Digital de Imagens para Curiosos ;-)</h1>\n",
    "<h2> **Parte III:** <u><i>Métodos de compressão de imagens: JPEG e Error Level Analysis</i></u> </h2>\n",
    "<h2>Escrito por <a href=\"mailto:mribeirodantas@lais.huol.ufrn.br?Subject=Curso%20PDI\" target=\"_top\">Marcel Ribeiro Dantas</a></h2>\n",
    "<h2>Agosto de 2016</h2>\n",
    "</center><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Nota do autor**: Caso você não tenha visto os primeiros dois módulos deste curso, ou caso já faça algum tempo, agora é uma boa hora para dar ao menos uma revisada rápida. De outro modo, a compreensão deste módulo poderá ser prejudicada já que alguns termos e conceitos serão tratados como algo já apresentado."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# O que é uma imagem digital?\n",
    "\n",
    "Em módulos anteriores, respondemos esta pergunta de um modo que para muitos pode ter parecido de baixo nível e o que realmente está lá. Tal suposição é coerente dado que para muitos os conceitos apresentados foram realmente surpreendentes e diferente do que esperavam. Mas a realidade, por incrível que pareça, ainda é um pouco diferente. Na computação, é comum que algoritmos cada vez mais modernos trabalhem em cima de grupos de dados relacionados de modo a tornar seu processamento e armazenamento mais eficiente.\n",
    "\n",
    "Quando se diz um processamento mais eficiente, costuma-se indicar mais veloz ou utilizando menos recursos computacionais, enquanto que um armazenamento mais eficiente em geral significa ocupar menos espaço no disco. Áudios ou imagens não são exceção aqui. Logo, embora tudo que vocês aprenderam até aqui sobre o que é uma imagem digital esteja correto, não é desse modo que elas rotineiramente são armazenadas e lidas em seus computadores.\n",
    "\n",
    "Existem diversos métodos de compactação de imagens, dentre os quais destacamos o JPEG que é o mais comum e,  portanto, será o que receberá maior enfoque neste módulo. No contexto que discutimos os conceitos apresentados até então, três termos costumam aparecer com certa frequência. Métodos de compressão *lossy* (ou com perdas), métodos de compressão *lossless* (ou sem perdas) e formatos de arquivos.\n",
    "\n",
    "# Formatos de arquivo\n",
    "\n",
    "Formatos de arquivo são padrões de como os dados são organizados no arquivo. São as sequências de bits que apontam diversas informações sobre o arquivo, como qual método de compactação será utilizado ou que tipo de arquivo é esse. Arquivos PNG, por exemplo, armazenam imagens em bitmap usando um algoritmo de compressão lossless ou sem perdas.\n",
    "\n",
    "É importante compreender que quando você salva uma imagem em um formato de arquivo com um determinado algoritmo de compressão, este arquivo será sempre comprimido quando for salvo, e descomprimido quando for aberto.\n",
    "\n",
    "# *Lossy data compression*\n",
    "\n",
    "Os métodos de compressão com perdas costumam atingir os melhores resultados no que tange redução no tamanho final do arquivo. No entanto, isto ocorre ao custo de salvar uma imagem diferente da original. Isto é, quando você abrir a imagem e o método de compressão descomprimir a imagem, a imagem não será exatamente a que foi inicialmente comprimida. Em alguns casos, a diferença não é perceptível ao olho humano, enquanto que em outros é. O JPEG permite diferentes níveis de compactação dando liberdade para você adaptá-lo ao seu cenário. Compressão máxima, sem se preocupar com a qualidade, ou a máxima compressão sem que haja perda de qualidade perceptível.\n",
    "\n",
    "<br><br><div style=\"text-align: center\"><img width=800px src=\"https://www.gimp.org/tutorials/GIMP_Quickies/JPG-Compression-Sample.png\"><center>**Fonte**: https://www.gimp.org</center></div>\n",
    "\n",
    "# *Lossless data compression*\n",
    "\n",
    "Os métodos de compressão sem perdas geralmente não obtêm resultados de compressão tão bons quanto os dos algoritmos com perdas, mas costumam apresentar melhores resultados para os casos onde não há perda de qualidade perceptível. Um famoso formato de arquivo com método de compressão sem perda é o *PNG*. A ideia de modificar uma imagem sem que o olho humano perceba diferenças não deve ser um conceito novo para você, já que o módulo passado tratou de esteganografia onde textos inteiros eram escondidos em uma imagem sem que o olho humano pudesse notar qualquer diferença na imagem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# JPEG e JExif\n",
    "\n",
    "Embora diversas coisas que tenham a ver com JPEG sejam chamadas também de JPEG, JPEG é apenas o método de compressão. *\"Arquivos JPEG\"* geralmente são arquivos no formato JExif (*JPEG Exchangeable image file format*), o formato de arquivo (ou *file format*) mais conhecido a utilizar o método de compressão JPEG.\n",
    "\n",
    "O método de compressão do JPEG se baseia no princípio de que, por incrível que pareça, o olho humano não visualiza cores tão bem quanto tons de cinza. Não só isso, mas também variações de intensidade nos componentes de alta frequência são menos percebidas do que imaginamos. Em imagens, as altas frequências costumam ser responsáveis por detalhes como bordas de figuras. Nas primeiras abordagens de frequência no contexto de imagens digitais, é difícil visualizar e, infelizmente, não é do escopo deste módulo entrar em detalhes da Transformada de Fourier, por exemplo. Mas, por questões didáticas, considere que uma soma de contribuições sobrepostas dão origem a imagem que visualizamos e os componentes de alta frequência são responsáveis por bordas.\n",
    "\n",
    "<br><br><div style=\"text-align: center\"><img width=800px src=\"https://foundationsofvision.stanford.edu/wp-content/uploads/2012/02/06_outlineofthejpeg1.png\"><center>**Fonte**: https://foundationsofvision.stanford.edu</center></div>\n",
    "\n",
    "O primeiro passo do método de compressão JPEG é converter o espaço de cores de nossa imagem para *YCbCr*. Em imagens que são originalmente RGB, a conversão seria de RGB para YCbCr, por exemplo. Faz-se esta conversão para obter a luminosidade  de uma imagem, isto é, captar a intensidade (brilho) de cada pixel da cor em questão. No YCbCr, o Y é a luminosidade enquanto que Cb e o Cr são as crominâncias de azul e vermelho. O olho humano, no entanto, não percebe muito bem crominância, ao menos não tão bem quanto percebe mudanças no brilho. O objetivo disso é realizar um *down-sample* já que não percebemos tão bem estas variações, ou seja, reduz-se a quantidade de cor em uma imagem.\n",
    "\n",
    "Essa redução de cor na prática significa diminuir o número de bits necessários para representar uma cor. Se um pixel RGB *True Color* tem 24 bits (8 bits ou 1 byte para cada canal), um exemplo seria um bloco de 4 pixels terem 48 bits, em vez de 96 (4*24) bits. Sabendo disso, talvez o lado direito da imagem acima faça mais sentido para você. Esses blocos na terminologia de compressão JPEG são conhecidos como *minimal coded units*, ou MCUs.\n",
    "\n",
    "Exemplos de formatos de amostragem ou *sampling formats*:\n",
    "\n",
    "* 4:4:4 (no downsampling)\n",
    "* 4:2:2 (reduction by a factor of 2 in the horizontal direction), \n",
    "* 4:2:0 (reduction by a factor of 2 in both the horizontal and vertical directions)\n",
    "\n",
    "Os MCUs são de tamanho 8×8 (4:4:4 – no subsampling), 16×8 (4:2:2), ou mais comumente 16×16 (4:2:0). \n",
    "\n",
    "PS: Eu vou entrar em mais detalhes sobre isso em próximas versões do módulo. As próximas etapas envolvem a Transformada Discreta de Cosseno, entre outros conceitos mais complexos, cujas apresentações mais didáticas e abstraídas ainda não preparei.\n",
    "\n",
    "<br><br><div style=\"text-align: center\"><img width=800px src=\"cfile_ycbcr.png\"><center>**Fonte**: Computerphile</center></div>\n",
    "\n",
    "<br><br><div style=\"text-align: center\"><img width=800px src=\"ycbcr_borda.png\"><center>**Fonte**: Computerphile</center></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Com as informações discutidas até aqui, acredito que já podemos abordar o que é conhecido como *ELA* ou Error Level Analysis. Error Level Analysis ou Análise dos Níveis de Erro é a análise de artefatos de compressão em dados digitais com compressões com perdas (lossy compressions) como é o caso do JPEG.\n",
    "\n",
    "Esta análise se baseia na ideia de que algoritmos de compressão com perdas costumam comprimir uma imagem por inteiro de forma uniforme, resultando em um nível uniforme de artefatos de compressão. Podem existir casos onde a imagem revele regiões com níveis diferentes de artefatos de compressão. Esta diferença pode ser por essas partes terem sido repetidamente comprimidas pelo algoritmo, de forma igual, mas um número diferente de vezes. Ou seja, esta parte da imagem foi comprimida um número diferente de vezes do que a imagem original, revelando uma edição."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Consultas e bibliografia\n",
    "\n",
    "https://foundationsofvision.stanford.edu <br>\n",
    "https://www.youtube.com/watch?v=LFXN9PiOGtY (pt 0) <br>\n",
    "https://www.youtube.com/watch?v=n_uNPbdenRs (pt 1) <br>\n",
    "https://www.youtube.com/watch?v=Q2aEzeMDHMA (pt 2) <br>\n",
    "https://www.youtube.com/watch?v=LWxu4rkZBLw (bayer filter) <br>\n",
    "http://photo.stackexchange.com/questions/40401/what-does-frequency-mean-in-an-image <br>\n",
    "https://www.youtube.com/watch?v=f2odrCGjOFY <br>\n",
    "https://en.wikipedia.org/wiki/Image_file_formats <br>\n",
    "https://www.youtube.com/watch?v=yBX8GFqt6GA (The problem of JPEG) <br>\n",
    "https://www.youtube.com/watch?v=06OHflWNCOE (Digital images) <br>\n",
    "http://wayback.archive.org/web/20130513181427id_/http://sharp.bu.edu/~slehar/fourier/fourier.html#filtering\n",
    "(frequencias) <br>\n",
    "http://www.dspguide.com/ch27/6.htm (JPEG Transform)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}