Idea para un compresor de imágenes con pérdidas usando extracción de bits y codificación RLE a una imagen PGM

Tengo una idea para hacer un compresor de imágenes PGM (por si se preguntan, no, no tengo fijación alguna con este tipo de imágenes solo que es sencillo, ¡gulp!, trabajar con ellas) con pérdidas usando la extracción de bits (medio explicada aquí) y codificación RLE. La idea principal viene de el hecho de que al aplicar un algoritmo extracción de bits a una imagen tenemos un arreglo binario como resultado, tendremos 1 arreglo 2D de ceros y unos por cada bit extraído, es decir que para una imagen de 8-bits, tendremos 8 arreglos de binarios. De esto podemos observar que cada imagen resultante contiene información de la imagen, y se puede observar una degradación empezando del bit más significativo hacia abajo. Se pueden emplear un par de estas imágenes para codificarlas usando un algoritmo de RLE aprovechando que tendremos secuencias de unos y ceros; luego al recuperarlas y aplicarles algún tipo de técnica de Diethering, para mejorar la calidad de la imagen resultante, claro, con pérdida de información con respecto a la original.

A continuación listo los pasos que creo que son necesarios para este algoritmo:

• Aplicar la extracción de bits a la imagen. Resultado: 8 imágenes (1 por bit en este caso)
• Seleccionar las imágenes que serán empleadas para la codificación RLE. Resultado: conjunto de imágenes a comprimir.
• Aplicar RLE a un cada una de las imágenes seleccionadas en el paso anterior. Resultado: n número de conjuntos de datos (1 por imagen). El total de datos obtenidos aquí nos dará como resultado una compresión.
• Para descomprimir la imagen, aplicamos RLE inversa a los conjuntos de datos. Resultado: n número de imágenes binarias.
• Se combinan las imágenes obtenidas en el paso anterior (esto es posible asignando cada bit y reconstruyendo la imagen de 8bits). Resultado: Imagen de 8bits con pérdida de información.
• A la imagen resultante le aplicamos algún tipo de Diethering para mejorar la calidad. Resultado imagen codificada y decodificada con pérdidas.

No se hasta que punto sea posible obtener una buena imagen como resultado, o que tan buena compresión se pueda lograr para mantener un balance entre calidad de imagen y compresión.

Ya pondré los resultados en un post en cuanto tenga algo que valga la pena. :)

Ejemplo de extracción de bits de una imagen en escala de grises de 8 bits en MATLAB

En este caso supongamos que tenemos una imagen en formato PGM, (escala de grises de 256 niveles, o sea 8 bits). Si queremos extraer la información de cada bit entonces tenemos lo siguiente:

• u, es el valor del pixel al que le vamos a extraer el bit
• B, es el número de bits usado para representar un pixel
• n, es el bit que queremos extraer de cada pixel, B es el menos significativo y 1 es el más significativo
• L, es en nivel máximo que puede tener nuestra imagen

Según Anil K. Jain en su libro Fundamentals of Digital Image Processing, en el capítulo dedicado al mejoramiento de imágenes (o image enhancement), explica la extracción de bits en una imagen y define al pixel u de la siguiente manera: 

y queremos que nuestro pixel resultado v de la extracción de bit sea:

El autor define kn como se muestra a continuación:

En donde:

En  este caso u puede tomar valores entre 0 y 255 (ya que es una imagen PGM de 8 bits). Por ejemplo si decimos que u = 237 y queremos extraer el bit más significativo entonces tenemos que n = 8  y B = 8. Representando u en su equivalente binario tendriamos que u = 11101101. Nos quedaría de la siguiente manera:

1. in = i8 = int[237/(2^8-8)] = 237
2. in-1 = i7 = int[237/(2^8-7)] = int[237/2^1] = int[237/2] = int[118.5] = 118
3. kn = k8 = 237 – 2*118 = 237 – 236 = 1

Enseguida se muestra el codigo en MATLAB para llevar a cabo la extracción de bits de la imagen del bote:

clc;clear;
myImagen = imread('boat.pgm');
myImagenNueva = myImagen;
[rows cols] = size(myImagen);

B = 8;
L = 255;

for n = 1:B
    for i = 1 : rows
        for j = 1 : cols 
            u = double(myImagen(i,j));
            iEne = floor(u/2^(B-n));
            iEneMenosUno = floor(u/2^(B-(n-1)));
            BitExtraido = iEne - (2*iEneMenosUno);
            if BitExtraido == 1
                BitExtraido = L;
            else
                BitExtraido = 0;
            end
            myImagenNueva(i,j) = BitExtraido;
        end
    end
    subplot(2,4,n);
    imshow(myImagenNueva);
    title(['Bit', num2str(n)]);
end