Transformada discreta de cosseno

Transformada discreta de cosseno (ou DCT da sigla em inglês para Discrete Cosine Transform) é a extensão da Transformada de cosseno ou Transformada contínua de cosseno para um domínio discreto. É muito utilizada em processamento digital de imagens e compressão de dados.

Transformada unidimensional

A fórmula desta transformada para um vetor p de tamanho n é:

$G_{f}={\frac {1}{2}}C_{f}\sum _{t=0}^{n-1}p_{t}\cos {\left({\frac {(2t+1)f\pi }{2n}}\right)},$ onde: $C_{f}={\begin{cases}{\frac {1}{\sqrt {n}}},&f=0\\{\sqrt {2/n}},&f>0\end{cases}}{\mbox{ para }}f=0,1,...,n-1$

A matriz dessa transformada é composta de vetores ortonormais, sendo por isso uma matriz de rotação. Esta transformada é muito utilizada na compressão de dados, pois transfere a maior parte da informação contida para os primeiros elementos do vetor, otimizando o armazenamento (para compressão sem perdas) e facilitando a quantização dos valores (para compressão com perdas).

A recuperação dos dados transformados pode ser feita com a operação inversa, chamada de IDCT (do inglês Inverse Discrete Cosine Transform), que é dada pela fórmula abaixo:

$p_{t}={\frac {1}{2}}\sum _{j=0}^{n-1}C_{j}G_{j}\cos {\left({\frac {(2t+1)j\pi }{2n}}\right)},{\mbox{ para }}t=0,1,...,n-1$

Em compressão e imagens e vídeos a maioria dos padrões usa a transformada discreta de cosseno com o tamanho do vetor p n = 8.

Transformada bidimensional

Sabendo que os pixels de uma imagem tem correlação com seus vizinhos nas duas dimensões da imagem, e não apenas em uma dimensão, a transformada discreta de cosseno para ser usada na compressão de imagens também deve ser uma transformada bidimensional. A fórmula dessa transformada para uma matriz (ou seja uma imagem) p de tamanho n x n é:

$G_{ij}={\frac {1}{\sqrt {2n}}}C_{i}C_{j}\sum _{x=0}^{n-1}\sum _{y=0}^{n-1}p_{xy}\cos {\left({\frac {(2y+1)j\pi }{2n}}\right)}\cos {\left({\frac {(2x+1)i\pi }{2n}}\right)},$ para $0\leq i,j\leq n-1$

onde $C_{i,j}={\begin{cases}{\frac {1}{\sqrt {n}}},&{i,j}=0\\{\sqrt {2/n}},&{i,j}>0\end{cases}}$

Essa transformada pode ser considerada como uma rotação (ou duas rotações consecutivas, uma em cada dimensão), ou ainda como uma base ortogonal num espaço vetorial de n dimensões. A recuperação dos dados transformados pode ser feita usando-se a transformação inversa, conhecida como IDCT bidimensional:

$p_{xy}={\frac {1}{4}}\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}C_{i}C_{j}G_{ij}\cos {\left({\frac {(2x+1)i\pi }{2n}}\right)}\cos {\left({\frac {(2y+1)j\pi }{2n}}\right)}$

Analogamente à transformada unidimensional, a transformada bidimensional resulta em uma matriz onde os coeficientes mais significativos se acumulam no canto superior esquerdo (início da matriz) e os demais coeficientes são de pequeno valor podendo ser mais facilmente armazenados ou mesmo quantizados para proporcionar uma compressão com perdas.

Otimizações

Apesar de serem relativamente fáceis de implementar em qualquer linguagem de computador, a compressão de imagens demanda um grande poder de processamento e por isso precisa ser otimizada ao máximo. O uso da transformada discreta de cosseno em imagens grandes, apesar de apresentar ótimos resultados, exige um processamento muito grande. Por isso na prática a estratégia que se adota é de dividir a imagem em blocos de tamanho menor (em geral de tamanho 8x8 pixels, como no JPEG), levando a nossa primeira otimização:

Otimização 1: a imagem a ser tratada deve ser divida em blocos menores facilitando a computação das transformadas.

Outra justificativa para esta abordagem é que apesar de terem bastante correlação com os vizinhos próximos, existe pouca ou nenhuma correlação entre pontos distantes de uma mesma imagem. Os ganhos de processamento com esta abordagem suplantam em muito as perdas em termos de compressão.

O cálculo das funções de cosseno, por ser uma função transcendental, também exige bastante poder de processamento. Se verificarmos a fórmula da transformada discreta de cosseno veremos que podemos pré-calcular todos os valores de cosseno a serem utilizados, e depois disto apenas realizar operações aritméticas de soma e multiplicação. Isso nos leva a segunda regra:

Otimização 2: os cossenos utilizados devem ser pré-calculados e armazenados, realizando-se assim apenas operações aritméticas ao se calcular a fórmula da transformada.

Com um pouco de esforço algébrico, pode-se provar que a somatória dupla da fórmula da transformada discreta de cosseno bidimensional corresponde ao produto matricial CPC^T, onde P é a matriz 8x8 representando o bloco de imagem a ser comprimido, C é a matriz definida por:

$C_{ij}={\begin{cases}{\frac {1}{\sqrt {8}}},&i=0\\{\frac {1}{2}}\cos {\left({\frac {(2j+1)i\pi }{16}}\right)},&i>0\end{cases}}$

e C^T é a sua transposta. Essa multiplicação matricial exige menor número de multiplicações e somas que a formula original, reduzindo ainda mais o tempo de execução da transformada. E isso nos leva a terceira otimização:

Otimização 3: aplicação da transformada discreta de cosseno sob a forma matricial CPC^T para reduzir ainda mais o número de operações.^[1]

Ainda uma última otimização é a utilização de aritmética de ponto fixo (número fixo de casas decimais). Esta técnica se aproveita de que muitos computadores executam as instruções de ponto fixo com mais rapidez do que as de ponto flutuante, acelerando assim o cálculo da transformada. Entretanto, esta técnica introduz uma quantização forçada, mas que no contexto da compressão de dados pode ser desprezada.

Otimização 4: uso de aritmética de ponto fixo para aproveitar a maior velocidade desse tipo de cálculo na maioria dos computadores.

Compressão

Ao aplicar a transformada discreta de cosseno, os coeficientes mais significativos se acumulam no início do vetor (ou matriz) dos dados, ficando o restante com valores muito pequenos e carregando pouca informação. Este tipo de distribuição já é suficiente para que uma técnica de redução de redundância (como os algoritmos LZ77, LZ78 ou LZW) ou uma codificação otimizada (como codificação de Huffman ou codificação aritmética) produzam melhores resultados do que na imagem ou nos dados originais. Entretanto, por trabalharmos sempre com uma precisão finita nas representações numéricas utilizadas, acabamos por ter uma perda nos dados. Portanto, mesmo sem aplicar nenhuma forma de quantização, a compressão usando transformada discreta de cosseno é uma compressão com perdas.

Entretanto, a forma mais comum e que gera melhores resultados, é a aplicação de uma operação de quantização nos dados gerados pela transformada, e armazenar apenas os dados quantizados. Essa quantização permite uma maior eficiência das técnicas de codificação e eliminação de redundância utilizadas. Algumas formas de quantização normalmente utilizadas com a transformada discreta de cosseno são:

Eliminação dos componentes menos significativos (determina-se um patamar de valor ou mesmo de posição na matriz de resultados da transformada, e elimina-se ou substitui-se esses valores por 0).
Divisão inteira dos valores por um coeficiente de quantização fixo (assim pode-se usar menos dígitos, ou bits, para se representar os valores).
Divisão inteira por uma matriz de coeficientes de quantização (Esta técnica é a empregada pela maioria dos padrões de compressão de dados, pois é mais flexível e permite que se ajuste a matriz a qualidade desejada da imagem).

O padrão JPEG usa esta última técnica, e a tabela de coeficientes utilizada deve ser gravada junto com o arquivo comprimido da imagem. A escolha das matrizes no padrão JPEG pode ser da seguinte forma:

Uso das tabelas padronizadas de quantização fornecidas pelo padrão JPEG; ou
Uso de uma tabela de quantização Q personalizada, em geral calculada com uma fórmula simples que pode ser parametrizada para melhor ou pior qualidade de imagem. Uma fórmula bem comum é a seguinte, que usa um valor inteiro R como parâmetro: $Q_{ij}=1+(i+j)\times R$

Ainda no padrão JPEG, os coeficientes quantizados são separados (o coeficiente mais significativo de cada bloco 8x8 é separado dos demais para efeito de maior compressão) e comprimidos usando-se uma combinação de RLE e codificação de Huffman. O padrão prevê também a compressão através de uma variante das codificações aritméticas, chamada de codificação QM. Entretanto a codificação QM assim como a maioria das codificações aritméticas está protegida por patentes, e é preciso de uma licença do detentor das patentes para ser utilizado. Esta restrição das patentes fez com que a maioria dos compressores de JPEG utilize apenas a codificação de Huffmann, ignorando o uso do QM.^[2]

Exemplos

Abaixo seguem alguns exemplos de imagens (de tamanho 8x8 pixels, ampliadas para maior clareza) transformadas usando DCT, quantizadas com a tabela de quantização recomendada pelo padrão JPEG ^[3], e destransformadas para recompor a imagem descomprimida. Note que as imagens onde as transições de tons são mais suaves proporcionam uma melhor recomposição da imagem.


Degradê de cinzas sem passar por DCT	Degradê de cinzas após passar por DCT

Letra A com fundo preto sem passar por DCT	Letra A com fundo preto após passar por DCT

Letra A com fundo branco sem passar por DCT	Letra A com fundo branco após passar por DCT

Essa característica de suavizar as bordas, que pode ser notada nas imagens acima, é o que faz o DCT ser amplamente utilizado em compressão de fotos, pois nesse tipo de imagem a presença de bordas e mudanças abruptas nas imagens é mais rara. Para a compressão de desenhos e textos escaneados esta técnica não é tão boa pois "borra" ligeiramente as bordas das linhas retas, como podemos ver nos dois últimos conjuntos de imagens.

Matrizes de exemplo

Para demonstrar a capacidade de compressão proporcionada usamos a matriz que gerou a imagem em degradê e mostramos aqui todos os passos da compressão usando DCT.

Primeiros temos a matriz original abaixo. Podemos ver que essa matriz possui uma larga gama de valores distintos, não rendendo bons resultados se tentarmos apenas eliminar repetições:

$\left({\begin{smallmatrix}1.&19.&37.&55.&73.&91.&109.&127.\\19.&37.&55.&73.&91.&109.&127.&145.\\37.&55.&73.&91.&109.&127.&145.&163.\\55.&73.&91.&109.&127.&145.&163.&181.\\73.&91.&109.&127.&145.&163.&181.&199.\\91.&109.&127.&145.&163.&181.&199.&217.\\109.&127.&145.&163.&181.&199.&217.&235.\\127.&145.&163.&181.&199.&217.&235.&253.\end{smallmatrix}}\right)$

Quando aplicamos o DCT nesta matriz, temos a matriz seguinte. Esta matriz já tem uma ampla gama de valores zerados, que podem ser eliminados na compressão por alguma técnica de remoção de repetições, como RLE. A matriz abaixo esta arredondada para 2 casas decimais.

$\left({\begin{smallmatrix}1016.&-327.99&0.&-34.29&0.&-10.23&0.&-2.58\\-327.99&0.&0.&0.&0.&0.&0.&0.\\0.&0.&0.&0.&0.&0.&0.&0.\\-34.29&0.&0.&0.&0.&0.&0.&0.\\0.&0.&0.&0.&0.&0.&0.&0.\\-10.23&0.&0.&0.&0.&0.&0.&0.\\0.&0.&0.&0.&0.&0.&0.&0.\\-2.58&0.&0.&0.&0.&0.&0.&0.\end{smallmatrix}}\right)$

O passo seguinte é aplicar a quantização. Nesse momento podemos ver que o número de posições zeradas aumenta ainda mais, e os valores restantes são todos relativamente pequenos, podendo ser representados num arquivo com número menor de bits do que os valores maiores do arquivo original:

$\left({\begin{smallmatrix}63.&-30.&0.&-2.&0.&0.&0.&0.\\-27.&0.&0.&0.&0.&0.&0.&0.\\0.&0.&0.&0.&0.&0.&0.&0.\\-2.&0.&0.&0.&0.&0.&0.&0.\\0.&0.&0.&0.&0.&0.&0.&0.\\0.&0.&0.&0.&0.&0.&0.&0.\\0.&0.&0.&0.&0.&0.&0.&0.\\0.&0.&0.&0.&0.&0.&0.&0.\end{smallmatrix}}\right)$

Após a destransformação da matriz quantizada, usando IDCT, vemos que os valores quase não mudaram em relação ao arquivo original, com a maior diferença entre eles na posição (2,8) que é de 6 (num máximo de 256), ou seja, menos de 3%.

$\left({\begin{smallmatrix}4.&18.&39.&57.&74.&93.&113.&128.\\17.&32.&52.&71.&88.&106.&127.&141.\\37.&52.&72.&91.&107.&126.&146.&161.\\56.&70.&91.&109.&126.&144.&165.&179.\\73.&87.&108.&126.&143.&161.&182.&196.\\91.&106.&126.&145.&161.&180.&200.&215.\\111.&125.&146.&164.&181.&200.&220.&235.\\124.&139.&159.&178.&195.&213.&234.&248.\end{smallmatrix}}\right)$

Para imagens onde as variações dos tons são graduais, a técnica de DCT mostra excelente resultados, e por isso é adotada nos padrões mais usados hoje em dia.

MDCT

O padrão MP3 usa para a compressão de áudio uma variante da transformada Discreta de Cosseno conhecida como MDCT (do inglês Modified Discrete Cosine Transform). Esta transformada é bastante parecida com a transformada de cosseno unidimensional, e sua fórmula é dada abaixo:

$S_{i}=\sum _{k=0}^{n-1}x_{k}\cos {\left({\frac {\pi }{2n}}\left[2k+1+{\frac {n}{2}}\right](2i+1)\right)},i=0,1,...,{\frac {n}{2}}-1,$

E a sua inversa, conhecida como IMDCT é dada por:

$x_{k}=\sum _{i=0}^{n/2-1}S_{i}\cos {\left({\frac {\pi }{2n}}\left[2k+1+{\frac {n}{2}}\right](2i+1)\right)},k=0,1,...,n-1.$

Aplicações

A transformada discreta de cosseno é uma das técnicas mais utilizadas na compressão de dados, principalmente para a compressão de imagens e vídeos. Entre os formatos e padrões mais amplamente empregados hoje, listamos abaixo alguns que usam esta técnica:

JPEG para compressão de imagens com perdas (lossy compression)
MPEG para compressão de vídeos
MPEG-4 para compressão de vídeos, também conhecido pelos codecs DivX ou XviD.
MP3 para compressão de áudio usa a variante MDCT.

Implementação em linguagem Java

Seguem duas funções em linguagem Java que calculam a transformada discreta de cosseno (DCT) e sua inversa (IDCT):

/****
  *
  * Função    : DCT
  *
  * Descrição : Calcula a DCT de um arranjo unidimensional de double.
  *
  * Parâmetros: x - [Parâmetro de entrada] Sinal para ser calculada a DCT.
  *             tamanho - [Parâmetro de entrada] Tamanho do array (número de elementos).
  *
  * Retorno   : Resposta - [Parâmetro de saída]   Resultado da transformada.
  *
  * OBS.      : A DCT resultante do arranjo 'x' será colocada no arranjo 'X'.
  *
  ****/
     public static double [] DCT( double [] x, int tamanho )
     {
        double [][] xk = new double[tamanho][tamanho];
        double [] X = new double[tamanho];

        for( int n = 0; n < tamanho; n++ )
           xk[0][n] = 1/Math.sqrt(tamanho) * x[n];

        for( int k = 1; k < tamanho; k ++ )
           for( int n = 0; n < tamanho; n ++ )
              xk[k][n] = Math.sqrt(2.0/tamanho) * Math.cos(k * Math.PI/(2.0 * tamanho)*(2.0 * n+1)) * x[n];

        for( int k = 0; k < tamanho; k++ )
           X[k] = 0;

        for( int k = 0; k < tamanho; k++ )
           for( int n = 0; n < tamanho; n++)
              X[k]+=xk[k][n];

        return X;
     }

  /****
  *
  * Função    : IDCT
  *
  * Descrição : Calcula a 'DCT inversa' de um arranjo unidimensional de double.
  *
  * Parâmetros: X - [Parâmetro de entrada] Sinal para ser calculada a IDCT.
  *             tamanho - [Parâmetro de entrada] Tamanho do array (número de elementos).
  *
  * Retorno   : Resposta - [Parâmetro de saída]   Resultado da transformada.
  *
  * OBS.      : Observe que a IDCT é ligeiramente diferente da DCT.
  *
  ****/
     public static double [] IDCT( double [] X, int tamanho )
     {
        double [][] xk = new double [tamanho][tamanho];
        double [] x = new double[tamanho];

        for(int n=0;n<tamanho;n++)
           xk[0][n]= Math.sqrt(1.0/tamanho) * X[0] * Math.cos(0);

        for(int k=1;k<tamanho;k++)
           for(int n=0;n<tamanho;n++)
              xk[k][n] = Math.sqrt(2.0/tamanho) * X[k] * Math.cos(k*(2*n+1)*Math.PI/(2.0*tamanho));

        for(int k=0;k<tamanho;k++)
           X[k]=0;

        for(int k=0;k<tamanho;k++)
           for(int n=0;n<tamanho;n++)
              x[k]+=xk[n][k];

        return x;
     }

Implementação em linguagem C

Seguem duas funções em linguagem C que calculam a transformada discreta de cosseno (DCT) e sua inversa (IDCT):

Transformada direta

#include <math.h>

/****
*
* Função    : DCT
*
* Descrição : Calcula a DCT de um arranjo unidimensional de double.
*
* Parâmetros: X - [Parâmetro de saída]   Resultado da transformada.
*             x - [Parâmetro de entrada] Sinal para ser calculada a DCT.
*             N - [Parâmetro de entrada] Tamanho do array (número de elementos).
*
* Retorno   : Não há.
*
* OBS.      : A DCT resultante do arranjo 'x' será colocada no arranjo 'X'.
*
****/
void DCT(double *X, double *x, long N)
{
  long n, k;
  double xk[N][N];

  for(n=0;n<N;n++)
      xk[0][n]=1/sqrt(N) * x[n];

  for(k=1;k<N;k++)
      for(n=0;n<N;n++)
          xk[k][n] = sqrt(2.0/N) * cos(k*M_PI/(2.0*N)*(2.0*n+1)) * x[n];

  for(k=0;k<N;k++)
      X[k]=0;

  for(k=0;k<N;k++)
      for(n=0;n<N;n++)
          X[k]+=xk[k][n];
}

Transformada inversa

#include <math.h>

/****
*
* Função    : IDCT
*
* Descrição : Calcula a 'DCT inversa' de um arranjo unidimensional de double.
*
* Parâmetros: x - [Parâmetro de saída]   Resultado da transformada.
*             X - [Parâmetro de entrada] Sinal para ser calculada a IDCT.
*             N - [Parâmetro de entrada] Tamanho do array (número de elementos).
*
* Retorno   : Não há.
*
* OBS.      : Observe que a IDCT é ligeiramente diferente da DCT.
*
****/
void IDCT(double *x, double *X, long N)
{
  long n, k;
  double xk[N][N];

  for(n=0;n<N;n++)
      xk[0][n]= sqrt(1.0/N) * X[0] * cos(0);

  for(k=1;k<N;k++)
      for(n=0;n<N;n++)
          xk[k][n] = sqrt(2.0/N) * X[k] * cos(k*(2*n+1)*M_PI/(2.0*N));

  for(k=0;k<N;k++)
      x[k]=0;

  for(k=0;k<N;k++)
      for(n=0;n<N;n++)
          x[k]+=xk[n][k];
}

Bibliografia

SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer

Notas e referências

↑ Ainda é possível otimizar mais o cálculo da transformada, reduzindo o número de operações necessárias. para uma maior discussão do assunto veja SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer página 1280.
↑ SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer
↑ Apesar de podermos usar qualquer matriz de quantização para comprimir imagens usando o padrão JPEG, o padrão recomenda o uso da seguinte tabela para imagens em tons de cinza:
$\left({\begin{smallmatrix}16&11&10&16&24&40&51&61\\12&12&14&19&26&58&60&55\\14&13&16&24&40&57&69&56\\14&17&22&29&51&87&80&62\\18&22&37&56&68&109&103&77\\24&35&55&64&81&104&113&92\\49&64&78&87&103&121&120&101\\72&92&95&98&112&100&103&99\end{smallmatrix}}\right)$

Ver também

[otimizacao-1] Ainda é possível otimizar mais o cálculo da transformada, reduzindo o número de operações necessárias. para uma maior discussão do assunto veja SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer página 1280.

[salomon-2] SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer

[tabelajpeg-3] Apesar de podermos usar qualquer matriz de quantização para comprimir imagens usando o padrão JPEG, o padrão recomenda o uso da seguinte tabela para imagens em tons de cinza:
$\left({\begin{smallmatrix}16&11&10&16&24&40&51&61\\12&12&14&19&26&58&60&55\\14&13&16&24&40&57&69&56\\14&17&22&29&51&87&80&62\\18&22&37&56&68&109&103&77\\24&35&55&64&81&104&113&92\\49&64&78&87&103&121&120&101\\72&92&95&98&112&100&103&99\end{smallmatrix}}\right)$

[1]

[2]

[3]