DCT (Discrete Cosine Transform)

Introducción

La compresión de imágenes reduce la cantidad de datos necesarios para representar una imagen, mediante la eliminación de datos redundantes o innecesarios. Esta compresión puede ser con o sin pérdida de datos. Usualmente, para la vida cotidiana, se utiliza la compresión con pérdida de datos, pues permite una mayor compresión (Zhe-Ming Lu &Shi-Ze Guo, 2017). Luego, por el alto nivel de imágenes que consumimos en el día a día, resulta necesario comprimirlas lo máximo posible, manteniendo una buena calidad de imagen. Luego, estas pérdidas, de ser controladas, son casi imperceptibles. La compresión de imágenes no solo permite disminuir el espacio requerido para almacenarlas, sino que permite una transferencia y carga de archivos más rápida. Finalmente, el objetivo es representar una imagen con el menor número de bits sin perder la información fundamental (Hussain, A, J., et al, 2018).

La transformada del coseno directa o DCT por sus siglas en inglés Discrete Cosine Transform es una técnica de procesamiento de señales y compresión de datos, principalmente imágenes, basada en representar los datos como la suma ponderada de distintas funciones de coseno.

La DCT fue desarrollada como un algoritmo de filtrado y reconocimiento de patrones por N. Ahmed; T. Natarajan; K.R. Rao en 1974 para el procesamiento de señales. (Ahmed, N., et al, 1974).

Definición

La DCT se utiliza para comprimir los datos de los pixeles que conforman la imagen. Cada imagen se divide en grupos de pixeles y luego, su información es representada por distintas funciones de frecuencia de coseno. Finalmente, para disminuir el tamaño de la imagen es que se eliminan las frecuencias altas.

Se destaca que la compresión de imágenes con DCT es una compresión con pérdida de datos. Esto significa que al descomprimir la imagen, aplicando la transformada inversa, no obtenemos la imagen original. En vez de esta, obtenemos una de menor calidad; sin embargo, esta pérdida de calidad es prácticamente imperceptible al ojo humano. Esta técnica se utiliza, pues obtiene un buen ratio de compresión.

Algoritmo para compresión

Supongamos un espacio \(2D\) con una matriz de \(m * n\). Esta matriz contiene la información de un bloque de imagen. De esta forma, la imagen se descompone en distintas matrices. Luego, cada valor de la matriz \(matriz[i][j]\), donde \(i,j \neq 0\), se debe multiplicar por:

\[ \frac{\sqrt{2}}{\sqrt{m}} \times \frac{\sqrt{2}}{\sqrt{n}} \times \sum_{k=0}^{m-1}\sum_{l=0}^{n-1}cos(\frac{(2k+1)\times \pi \times i}{2m}) \times cos(\frac{(2l+1)\times \pi \times j}{2n}) \]

En el caso de \(i,j=0\), se modifican los primeros componentes quedando:

\[ \frac{1}{\sqrt{m}} \times \frac{1}{\sqrt{n}} \times \sum_{k=0}^{m-1}\sum_{l=0}^{n-1}cos(\frac{(2k+1)\times \pi \times i}{2m}) \times cos(\frac{(2l+1)\times \pi \times j}{2n}) \]

Finalmente, la resultante de estas operaciones es la \(matriz'\), que corresponden a la matriz original luego de haber aplicado la DCT. En el caso de trabajar en un espacio \(1D\) la ecuación correspondería solo a los componentes de \(n\).

En la práctica, cada matriz correspondiente a una sección de la imagen, es una combinación lineal de \(64\) funciones básicas de ondas de coseno. Estas funciones básicas pueden producir cualquier imagen que se desee comprimir. Luego, este algoritmo determina el coeficiente de contribución de cada función para cada subsección de la imagen.

En la siguiente imagen, se muestran las 64 funciones de coseno que conforman las imágenes. Se observa como en el eje \(x\) la frecuencia aumenta de manera horizontal, mientras que en el eje \(y\) aumenta de manera vertical. La imagen fue obtenida desde (Hussain, A, J., et al, 2018).

imagen

Para la mayoría de las matrices, la información se concentra en las esquinas superiores derechas, correspondientes secciones de frecuencia más bajas. Luego, se pueden eliminar las bandas de frecuencias más altas, y así la matriz se representa por menos coeficientes.

Implementación

La implementación de la DCT se obtiene de la web Geeks for Geeks. El código base corresponde a la implementación en C++, pero es modificado para obtener una generalización del código y no un ejemplo en particular.

#include <bits/stdc++.h>
using namespace std;


int dctTransform(int matriz[m][n]){
    int i, j, k, l;
    float matriz'[m][n];

    float ci, cj, aux, sum;

    // se define la primera parte de la transformada 
    //la cual depende del i
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            if (i == 0)
                ci = 1 / sqrt(m);
            else
                ci = sqrt(2) / sqrt(m);
            if (j == 0)
                cj = 1 / sqrt(n);
            else
                cj = sqrt(2) / sqrt(n);

            // se define variable auxiliar
                // esta almacena la sumatoria de los cosenos
            sum = 0;
            for (k = 0; k < m; k++) {
                for (l = 0; l < n; l++) {
                       aux = matriz[k][l] * 
                        cos((2 * k + 1) * i * pi / (2 * m)) * 
                        cos((2 * l + 1) * j * pi / (2 * n));
                    sum = sum + aux;
                }
            }
            matriz'[i][j] = ci * cj * sum;
        }
    }
}

int main()
{
    int matriz[m][n]; // se define la matriz 
    dctTransform(matriz); // se llama la función
    return 0;
}

Esta implementación tiene una complejidad temporal de \(0(n*m)^2\). Además, la DCT se guarda en un espacio auxiliar correspondiente a \(n*m\).

Ejemplos de usos y Avances

Este algoritmo es muy utilizado dado su alto ratio de compresión. Es la técnica de compresión aplicada en los archivos de imagen JPEG (Joint Photographers Expert Group) y archivos de audio MPEG. Además, recientes estudios están trabajando en un método híbrido que utiliza la DCT para poder comprimir las imágenes de resonancias magnéticas, optimizando así los recursos necesarios para transferirlas y almacenarlas (Vikraman & Afthab , 2024)).

En el caso de los archivos JPEG, la imagen se divide en bloques de \(8 *8\), es decir en la definición anterior, \(m,n=8\), y se divide en matrices de \(M[8][8]\).

Como entrada del algoritmo se entrega la imagen en RGB, luego se transforma a YCbCr. Luego, los pasos para traspasar la imagen a JPEG son los siguientes:

Dividir la imagen en en matrices de \(8 \times 8\)
Centrar los valores de cada matrix en \(0\). Esto se debe a que se trabaja con la función coseno, cuyo dominio es del \(-1\) al \(1\). Por ejemplo, la luminiscencia se mide desde el \(0\) al \(255\), luego todos los valores de las matrices \(8\times 8\) deben ser centrados para que se representen en valores desde el \(-128\) al \(128\).
Aplicar la DCT a cada valor de la matriz, según las ecuaciones anteriores. Este paso nos permite obtener los coeficientes de la DCT, los cuales indican la participación de cada función del coseno en la imagen original.
Aplicar tabla de cuantificación. Esta tabla es de \(8*8\), y por cada coordinada \(i,j\) indica por cuanto se dividirá cada valor de las matrices \(M'[i][j]\). Esta tabla es requerida posteriormente para recuperar la imagen original. Existen distintas tablas estándares según el ratio de compresión que se desea alcanzar.
Los valores resultantes del paso anterior son redondeados al entero más cercano. Esto permite que muchos valores tiendan a \(0\), luego resulta más comprimible.
Finalmente, los datos son leídos en zig- zag, partiendo de la esquina superior izquierda y moviéndose a la derecha, y almacenados utilizando Huffman encoding.

A continuación, se muestran dos imágenes, aparentemente iguales. La primera corresponde a la versión en JPEG, mientras que la segunda es la versión en PNG. Originalmente la primera es una fotografía \(3337*2494\) pixeles que pesa \(1,7MB\), mientras que la segunda cuenta con la misma cantidad de pixeles pero pesa \(21,9MB\), es decir pesa casi 13 veces más que la primera.

jpg

png

A simple vista estas imágenes no tienen diferencia, luego al realizar a cada una un zoom de \(500\%\), se observan diferencias en los colores. En la siguiente imagen se observa mano izquierda la imagen en JPEG y a mano derecha la imagen en PNG. Luego, en la segunda es posible apreciar que existe una mayor variabilidad de colores en la imagen. Sin embargo, como no vemos ese nivel de detalle en la imagen original, no se modifica nuestra apreciación de la fotografía.

jpg2

png2