¿Qué Onda?: Fundamentos Matemáticos de las WAVELETS. Parte I

Lo que se presenta a continuación es basado en un artículo de Albert Cohen y Jelena Kovacevic llamado Wavelets: The Mathematical Background.

 

Cuando se tiene una señal, existen una gran cantidad de maneras de representarla y en base a lo que necesitamos hacer con dicha señal es que elegimos la manera en que va a ser tratada. El objetivo es que la información obtenida de la señal tenga significado para nosotros, es ahí dónde se pueden lograr varios acercamientos. Entre ellos se encuentran la multiresolución y las transformaciones de dominio.

La multiresolución a grandes rasgos es ir representando la información de manera que los detalles son agregados de forma sucesiva. Para la representación de una señal, uno de los temas que se utilizan ampliamente son las transformaciones de dominio y con ello es menester hablar una de las técnicas más aplicadas, la transformada de Fourier. Con la transformada de Fourier cambiamos la representación de una señal en el dominio del tiempo al dominio de la frecuencia, pero no podemos saber en que instante de tiempo está ubicada la frecuencia, esto es en algunos casos una limitación.

Una manera de darnos una idea de la localización en tiempo de la frecuencia es construir bloques y aplicarles la transformada de Fourier. Si tenemos que es una señal de frecuencia, con Fourier obtenemos un pico en la frecuencia dada. A partir de esto podemos expresar dónde es la ventana usada para localizar la frecuencia en el tiempo, a esto se le llama Short-time Fourier Transform (STFT). Una de las principales desventajas con la STFT es que la localización en el espacio tiempo es fija. Con las wavelets se tiene un acercamiento diferente, la localización de la frecuencia es logarítmica y proporcional al nivel de frecuencia.

Se puede definir una familia de funciones de la siguiente manera que nos permita tener una representación en la escala del tiempo

,

(1)

dónde es una función fija llamada “wavelet madre”, a representa el escalamiento de la función y b son los corrimientos en el tiempo.

Basado en la función representada en (1) y tomando en cuenta que es un espacio de Hilbert, se define la transformada de una función f de la siguiente manera:

(2)

Para que la transformada (2) pueda ser invertible, se tiene elegir una de manera que cumpla con la condición de admisibilidad mostrada a continuación:

(3)

Y para asegurar que la integral es finita se debe cumplir que . En base a lo anterior tenemos que se puede reconstruir mediante:

(4)

Prácticamente, una transformada wavelet continua se aplica a una serie de puntos discretos de manera . Si se restringe la transformada continua wavelet de manera que , dónde entonces para valores fijos y . Entonces podemos definir la función wavelet de manera general cómo:

,

(5)

Para saber si la transformada wavelet en el caso discreto caracteriza completamente la función f y logra reconstruirla de manera estable, se requiere introducir el concepto de frames.

Para que un frame exista, y por lo tanto reconstrucción a partir de la wavelet, se debe tener una secuencia en un espacio de Hilbert H si para cada x perteneciente al espacio H se cumple lo siguiente:

(6)

En dónde los límites son independientes de x. A dicha secuencia se le asocia al operador F que representa a y también se desprende de ahí F* que asocia la sumatoria de las secuencias en .

La desigualdad expresada en (6) puede ser expresada en términos del operador hermitiano F* F de manera que:

(7)

En base a lo anterior podemos definir una secuencia dada por que también constituye un frame llamado dual frame con límites en y se asocia con el operador llamado por lo consiguiente tenemos que:

(8)

Y también tenemos que así que una x que forma parte del espacio de Hilbert es representada por:

(9)

Para reconstruir x debemos conocer . Teniendo en cuenta que:

(10)

Dónde el operador residual satisface lo siguiente:

(11)

Sustituyendo en (7) nos da como resultado la siguiente ecuación:

(12)

Si tenemos que A=B=1 después de renormalizar, entonces podemos definir lo siguiente:

(13)

De manera que elegimos valores de A-B/A+B que se aproximan a cero y también A y B de manera arbitraria cercanos a uno seguido de una renormalización, eligiendo valores a₀ y b₀ cercanos a uno y cero respectivamente. Lo anterior significa que se ha hecho un sobre-muestreo de la wavelet continua en un arreglo bastante denso. Una de las aplicaciones más usadas para usar el sobre-muestreo empleando frames es el de reducir el error de reconstrucción con una relación basada en el sobre-muestreo.

 

Continuará…

MEMORIA

NO SE OLVIDA

wavedemo: Herramienta didáctica en MATLAB para wavelets. Ejemplo para descomponer una imagen paso a paso

En este post no voy a hablar de la teoría de las wavelets, eso ya tocará en otra ocasión. Buscando desesperadamente información cuando estaba tratando de entender el “image denoising” usando wavelets, me tope con este demo que trae incluido del toolbox de wavelets en MATLAB. Aquí pongo un ejemplo muy simple para ver como se realiza una transformada wavelet aplicada a una imagen.

Primero se tiene que cargar el demo, simple y sencillamente poniendo lo siguiente en la línea de comandos:

wavedemo

y aparece a continuación la siguiente ventana

Como se muestra en la imagen anterior, se tienen tres opciones, la primera es un buen ejemplo para mostrar los comandos utilizados a bajo nivel por MATLAB para realizar la transformada wavelet de manera secuencial. En este ejemplo presionamos el botón que dice: “Command line mode” y nos muestra la siguiente ventana

como se puede observar, cuenta con varios ejemplos aplicando la transformada wavelet, continuamos presionando el botón que dice “Wavelet 2-D” y nos muestra la siguiente pantalla

Es importante notar en donde dice Image, obviamente se selecciona la imagen que queremos mostrar en el ejemplo, y presionamos “Start >>” para ir paso a paso o “AutoPlay” para que lo reproduzca automáticamente.

A continuación se muestran algunos de los pasos:

¡GANADORAS!

Escribo en celebración de una memorable ocasión, ahora si es oficial el anuncio.

Si, nuestras cuenta cuentos urbanas, (por si no han visto el link allá arriba) han sido ganadoras ni más ni menos del Premio al Fomento de la Lectura "México lee 2009", pueden ver la nota oficial aquí. Y la semana que entra estará en representación del colectivo Ivonne en el palacio de Chapultepec, en México D.F. para asistir al Primer Encuentro Internacional de Salas de Lectura en el cual se llevará a cabo la premiación.

A continuación transcribo un fragmento de la nota oficial, claro donde se anuncia a nuestras ganadoras:

En la categoría de Fomento de la lectura desde la sociedad civil, el jurado, integrado por la promotora y capacitadora Carola Díez, el profesor Amílcar Saavedra y el especialista en promoción de la lectura Rubén Pérez Buendía eligió como ganadora a Ivonne Ramírez Ramírez, de Ciudad Juárez, Chihuahua, representante del Colectivo Palabras de Arena, con el trabajo Regalando palabras en el desierto: cuentacuentos urbanos entre maquiladoras y narcofosas.

Nuevamente, cómo dice Mr. Cómic Man y se ha convertido en frase célebre local:

"Esa es la actitud"

¡Felicidades PuentaPuentos Urbanas!

Graficar la respuesta a la frecuencia y los polos y ceros de un filtro FIR en MATLAB

En este ejemplo se grafican los filtros que vienen como ejemplo en el post anterior: ¿Qué es un filtro de respuesta finita? (FIR:Finite impulse Response). Un ejemplo.

Si tenemos un filtro como se muestra a continuación:

Lo podemos graficar en MATLAB con el siguiente código:

RaizDeDos = 2^(1/2);
h = [1/RaizDeDos 1/RaizDeDos];
freqz(h,1);

La función freqz ejecutada de la manera anterior nos regresa una ventana con la siguiente información:

Como se puede observar nos regresa la magnitud y la fase del filtro, pero solo nos muestra hasta pi, para graficar la respuesta de 2pi, tenemos que hacerlo de la siguiente manera:

RaizDeDos = 2^(1/2);
h = [1/RaizDeDos 1/RaizDeDos];
freqz(h,1,'whole');

Si, es de la misma manera, simplemente  se le agrega ‘whole’ a la función freqz. Para mas información simple y sencillamente teclear doc freqz para acceder a la documentación de MATLAB. La respuesta a la frecuencia queda como a continuación:

Para graficar los polos y ceros del filtro, el código en MATLAB es de la siguiente manera:

RaizDeDos = 2^(1/2);
h = [1/RaizDeDos 1/RaizDeDos];
z = roots(h);
zplane(z',1);

Como se observa, primero se tienen que calcular las raíces de h, ya que tenemos que

y

Así que para calcular los ceros tenemos que calcular las raíces de z en h, por eso la línea z=roots(h); y como nos regresa un vector columna, ponemos la transpuesta en la función zplane. La gráfica quedaría como se muestra a continuación:

Si, es simple como eso, pero para poder llegar a eso tuve que pelearme un buen rato con MATLAB, por eso es que aquí lo pongo, jeje.

 

Technorati Tags: MATLAB,FIR,zplane,freqz,filtros

¡Santas pandemias Bacman!

 

Hay cosas que no se pueden definir con la rigurosidad científica que en más de un par de ocasiones embarga este espacio, como por ejemplo el explicar invasiones de seres putrefactos y hambrientos y es por eso que los expertos en la materia se encargan de ello, este es un buen ejemplo.

Infestación es la obra de un grupo de comiqueros en el borderland juarezpaseño y áreas circunvecinas. Ya tienen un buen rato haciendo monitos por estos lados y a primera vista se aprecia el resultado de su excelente jale. Es un orgullo ver el nacimiento de este pequeño insecto y esperemos que pronto se pueda ver infectando por doquier.

Bueno no me podía quedar así y pues ahí les van unos cuantos datos cuantizados de esta obra:

 

- 370 páginas

- 16 historias

- 2 países

- 3 escritores

- 8 dibujantes

- 6+ Artistas invitados

- 1era edición

- 07/2009

- ISBN: 978-0-578-03442-3

- Portada a Colores

- Resto a escala de grises

 

 

Para más información pues, dense una vuelta por el blog oficial de los seis cinco seis.

 

Technorati Tags: 656 Comics,Infestación the mythology

BuzzNet Tags: 656 Comics,Infestación the mythology

¿Qué es un filtro de respuesta finita? (FIR:Finite Impulse Response): Un ejemplo.

Este post trata sobre un ejemplo tomado del Libro: Digital Signal Processing Using MATLAB and Wavelets, de Michael Weeks, Capítulo 3.

Básicamente, existen principalmente tres tipos de filtros: pasabajas que dejan pasar solamente bajas frecuencias; pasaaltas que dejan pasar altas frecuencias y pasabanda que permiten el paso de todo el espectro, no es menester de este ejemplo el explicar en teoría que es un filtro (eso tomaría demasiado) ni tratar el diseño de los mismos (eso tomaría aún más).

El nombre FIR viene de la manera en que el filtro afecta una señal. Una función impulso es una entrada bastante interesante, donde la señal es 0 siempre, excepto en un lugar donde tiene valor de 1 (una unidad). Se llama también delta Dirac en tiempo continuo y delta Kronecker en discreto (shhh!). La respuesta de un filtro FIR a esta entrada es de duración finita, y por lo consiguiente se le da este nombre.

Suponiendo que la Figura 1 tiene una entrada x[n] = [1,0]. La salida sería [0.5,0.5], y cero después de eso. Se pueden obtener estas salidas aplicándolas en orden a la estructura del filtro. En el tiempo 0, x[0] aparece en la entrada, y cualquier cosa antes de esto es cero, que es lo que el elemento delay producirá como salida. En el siguiente intervalo de tiempo x[0] será la salida del delay mientras que x[1] será la entrada actual.

Figura 1: Filtro FIR con coeficientes {0.5,0.5}

¿Cómo se expresa y[n] en forma de ecuación? Como se observa de calcular y[0] y y[1], se tiene exactamente el mismo patrón:

y[0] = 0.5x[0] + 0.5x[-1]

y[1] = 0.5x[1] + 0.5x[0]

esto se generaliza como:

y[n] = 0.5x[n] + 0.5x[n-1]

La Figura 2 muestra la forma general de un filtro FIR, para K+1 coeficientes (son K+1, porque se empieza en 0 y se cuenta hasta K). El número de coeficientes también es llamado taps. Por convención el número de taps es igual al número de coeficientes. Así que un filtro con coeficientes {b0, b1, …, bK} tiene K+1 taps, debido a que tiene K+1 coeficientes. De todas maneras se dice que el orden es K. En otras palabras el orden del filtro y los taps expresan lo mismo pero con diferencia de 1.

Figura 2: Forma generalizada de un Filtro FIR

Con la estructura de la Figura 2 es posible determinar la salida. También es posible determinar la ecuación de la salida, la cual es:

y[n] = b[0]x[n-0] + b[1]x[n-1] + b[2]x[n-2] + … + b[K]x[n-K]

Nótese que para cualquier índice que se usa para b[.] es usado en x[n-.]. Esto significa que podemos representar todo lo que se encuentra al lado derecho de la ecuación como una sumatoria:

¡Hey!, eso parece como una convolución, ¿no es así?

Un filtro pasabajas, puede llamarse también filtro promediador, mientras que un pasaaltas, puede ser llamado filtro diferenciador, debido a que estos términos describen el funcionamiento de los filtros.

Por ejemplo, un filtro FIR con dos coeficientes de 0.5 y 0.5, se observa que la salida es:

y[n] = 0.5x[n] + 0.5x[n-1], o equivalentemente y[n]=(x[n]+x[n-1])/2

dicha salida, encuentra el promedio entre la entrada actual y la anterior. Si se observa la respuesta a la frecuencia de dicho filtro, se observa que las partes de bajas frecuencias (cambian lentamente) aparecen en la salida, mientras que el filtro decrementa las partes de altas frecuencias (cambian rápidamente).

Para el filtro de diferencias, se pueden tener coeficientes de {0.5 , –0.5} donde:

y[n]=(x[n]-x[n-1])/2

Esto da el cambio entre las dos muestras, escalado por 1/2 para ser consistente con el filtro de promedios. Como es de esperarse, la respuesta a la frecuencia de dicho filtro, debe atenuar las partes de cambios lentos en la señal, y enfatizar la parte que cambia rápidamente, concluyendo que es un filtro pasaaltas.

WTF

The pseudomathematicalgeek Joke of the day...

- How do you say that! It’s not allowed here.

- Easy, easy, let me explain to you what it means.

- It better be true!

- Wavelet Transform

- And the F?

- Nah!, that is just for Fun…

Ejemplo para leer una imagen PGM en Visual Basic 6.0

En el mundo de los programadores de software, Visual Basic no sirve para nada, je je, y para un par de cosas es cierto, pero para el resto, no. Déjenme explicarme un poco en esto. Visual Basic es un lenguaje desarrollado para hacer aplicaciones rápidas, en pocas palabras es un RAD (Rapid Application Development) como a los geeks de IBM los 80's les gusto llamarle.

Así que por ende, debe tener unas cosas por otras, es un lenguaje hasta cierto punto fácil de aprender y puedes desarrollar interfaces graficas de tres patadas, pero, pierdes un poco de control sobre la programación así que nada en cuestiones como programación orientada a objetos y apuntadores), conste no es solo esto, si no una lista que desconozco y tampoco necesito conocer. Otra de las desventajas es la lentitud para ejecutar los programas. Esta última es muy notable si lo comparamos con lenguajes un tanto más específicos para el procesamiento digital de imágenes, como por ejemplo MATLAB, o hasta LabVIEW.

Dejando de lado un poco el rollo, este ejemplo lo iniciaremos haciendo la interfaz gráfica de nuestro ejemplito, en una forma de Visual Basic, no iniciaré desde la creación del proyecto para no volver este post muy largo como el ejemplo de GUIDE. Primero ponemos un PictureBox y un CommandButton, el primero lo dejé con el nombre que le pone por default VB Picture1 y el segundo le puse cmdLoadPGM y le cambié el caption a “Cargar PGM”

La siguiente función es la que se encarga de leer el archivo PGM de la PC, y lo despliega en el Picturebox que le pasamos como parámetro:

Public Function LoadPGMtoPictureBox(strPGMpath As String, myPictureBox As PictureBox)
    
    Dim bytes() As Byte
    Dim pFileLenght As Long
    Dim iWidth As Long
    Dim iHeight As Long
    Dim i As Long
    Dim j As Long
    Dim iCountZeros As Long
    Dim iCounter As Long
    Dim strCatchWidth As String
    Dim strCatchHeight As String
    Dim pFileLength As Long
    Dim ptrToBytes As Long
    Const PGM_MAGIC_NUMBER = "P5"
    Dim u As Long
    Dim u2 As Long
    
    pFileLength = FileLen(strPGMpath)
    
    ReDim bytes(1 To pFileLength)
    
    Open strPGMpath For Binary Access Read As #10
    
        Get #10, 1, bytes
    
    Close #10
        
    If Not Chr(bytes(1)) & Chr(bytes(2)) = PGM_MAGIC_NUMBER Then _
	
        Exit Function
    
    iCountZeros = 0
    iCounter = 4
    strCatchWidth = ""
    strCatchHeight = ""
    
    Do
        strCatchWidth = strCatchWidth & Chr(bytes(iCounter))
        iCounter = iCounter + 1
    Loop While IsNumeric(Chr(bytes(iCounter)))
    
    Do
        strCatchHeight = strCatchHeight & Chr(bytes(iCounter))
        iCounter = iCounter + 1
    Loop While IsNumeric(Chr(bytes(iCounter)))
    
    
    iWidth = CInt(strCatchWidth)
    iHeight = CInt(strCatchHeight)
    
    For i = 0 To iHeight - 1
        For j = 0 To iWidth - 1
            ptrToBytes = ((i) * iWidth) + j
            u = bytes(ptrToBytes + &H10)
            u2 = RGB(u, u, u)
            SetPixelV myPictureBox.hdc, j, i, u2
        Next j
    Next i

    myPictureBox.ScaleMode = 3
    myPictureBox.Height = iHeight
    myPictureBox.Width = iWidth
    
End Function

Cuando suficiente nunca es suficiente

O como los gringos dirían, when enough is not enough, esta ocasión me he puesto a buscarle dos pies al gato sabiendo que solo tiene tres (si, adivinaron: es cojo).

Estoy a punto de empezar oficialmente a escribir mi tesis de maestría. Digo oficialmente porque el lunes inician clases en la UACJ, pero pues ya he iniciado a darle unos entres a esto de la tesis. No he escrito nada todavía en formato oficial, es más ni siquiera en formato no oficial. Pero, ya he leído un par de cosas al respecto, es más, ya hasta he pensado en más de una vez que hasta creo que sé lo que estoy haciendo.

En este blog he tratado de poner algo de las cosas que he ido aprendiendo en estos semestres que llevo de la escuela, y es reconfortante ver que tiene algo de tráfico el blog, el objetivo de este espacio es que pongo lo que voy viendo y lo que considero que vale la pena subir, y que además no lo enseñan en la escuela, al menos no de manera clara, (jeje) claro, aquí ni yo mismo me entiendo tampoco.

Eso no es todo, me puse a cambiarle la plantilla al blog y encontré esta que esta bastante bien, solo espero cambiarle el logo. Ya que nada más lo puse a lo loco para que no dijera lo que traía el theme por default.

¿Y por qué molestarse? Bueno, en realidad no es molestia, más bien es una manera de canalizar lo que esta en la sesera y no dejarlo que se amontone ahí, sin ningún oficio ni beneficio. Sé que la mayoría que visitan este sitio es gente que esta estudiando y busca con relación al procesamiento de imágenes, así que que mejor que poner un par de comentarios para así poder mejorar este sitio y poder agregar contenido (esta bien, también alimentar mi ego :P)

Codificación RLE para una imagen binaria en MATLAB

La codificacion RLE (Run Length Encoding) se aplica a cadenas de caracteres en las cuales existe una secuencia de datos. En este caso tenemos una imagen binaria, que es resultado de aplicar la extracción de bits a una imagen en escala de grises, como se pretende extraer solo un bit en especifico de la imagen, pues el resultado es una imagen binaria, en la cual se tienen valores de 0 o 1 dependiendo del valor del pixel. La imagen será del mismo tamaño de la imagen original puesto que es una operación de pixel por pixel.

Para visualizar de mejor manera lo que se intenta hacer aquí es menester mostrar un ejemplo. La imagen es una matriz de 2D de MxN, y tendremos para una imagen de 8x8 una matriz como la siguiente:

 

De lo anterior se desprende:

a) Aquí podemos observar la imagen de 8x8 original, en la cual cada valor de la matriz representa un pixel de 8 bits, o sea valores de 0-255.

b) En esta imagen se representa cada valor en su equivalente binario, con el propósito de visualizar el valor en bits de cada pixel.

c) El ultimo ejemplo de estas tres imágenes muestra el valor extraído de cada pixel para el bit mas significativo (MSB), o sea el bit 8.

La matriz que nos interesa es la matriz contenida en c). Para poder codificarla tenemos que tener una cadena de valores en los cuales existan secuencias de valores repetidos. En este caso son solo 0 y 1, y dado a que es una matriz 2D, tenemos que redimensionarla a 1D, y quedaría como se muestra a continuación:

 

Tenemos una secuencia de valores que se representa en 16 caracteres, y debido a que sabemos que tendremos una secuencia de ceros y unos es importante notar el primer número y después de ahí solo se irán alternando.

Necesitamos establecer una manera de poder decodificar nuestra cadena de caracteres, y reconstruir la imagen original, necesitamos saber un par de datos para regresar a nuestra imagen original. Como se decía en el párrafo anterior es necesario saber con que valor se empieza la secuencia de caracteres, también es necesario saber el tamaño de la imagen original, para que al reconstruir la secuencia unidimensional la podamos regresar a 2D de la misma manera que la original.

Así que el encabezado nos quedará mas o menos de la siguiente manera: Fb M N . . . Secuencia . . .

En donde Fb es el primer caracter, M y N es el tamaño de la imagen original y Secuencia, como su nombre lo indica es la cadena de valores que vamos a almacenar iniciando con Fb y alternando hasta terminar. El ejemplo anterior nos quedaría como a continuación:

1 8 8 1 1 1 4 1 3 1 1 1 1 1

Ahora si, despues de tanto rollo, aqui esta el código en MATLAB para hacer esto.

a = imread('c:\matlab7\work\lena.pgm');
[cols rows] = size(a);
b = BitExtraction(a,8,1,1);
figure(1); imshow(a);
figure(2); imshow(uint8(b));
myEncodedImageB = EncodeRLEimage(b);

Este es el código de la función para extraer bits de la imagen:

function x = BitExtraction(myImagen, B, n ,L)

myImagenNueva = myImagen;
[rows cols] = size(myImagen);

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
x = myImagenNueva;

Este es la función encargada de codificar la imagen.

function eImg = EncodeRLEimage(myImage)
    encoded = [];
    [cols rows] = size(myImage);
    img1D = double(reshape(myImage,1,[]));
    SizeOf1D = cols*rows;
    counter = 0;
    encoded = [img1D(1)];
    for i =1:SizeOf1D-1
        if img1D(i)==img1D(i+1)
            counter=counter+1;
        else
            encoded = [encoded counter];
            counter = 1;
        end
    end

    if counter ~= 1
    encoded = [encoded counter+1];
    end

    eImg = encoded;

¿Sirve de algo?

Technorati Tags: Procesamiento Digital de Imagenes,Tratamiento Digital de Imagenes,Extraccion de Bits,Imagen PGM,Codificacion RLE,RLE

¿Qué es compresión de Imágenes?

Antes de terminar el compresor (que en estos momentos creo que no va a servir mas que de práctica, je je je, bueno, de todos modos no pensaba desbancar al JPG, todavía), quiero explicar un poco que es la compresión de imágenes. Voy a empezar por poner un par de definiciones:

Según Gonzalez et al:

"La compresión de imágenes aborda el problema de reducir la cantidad de datos para representar una imagen digital. La compresión se logra removiendo una o más de las tres posibles redundancias básicas. (a)Redundancia de código: cuando se usan códigos de palabra menos óptimos (de menor longitud). (b)Redundancia interpixelaria: Que resulta de la correlación entre pixeles de una imagen. (c)Redundancia psicovisual: La cual se da debido a los datos que el sistema de visión humano ignora"¹

Según Wikipedia:

"Compresión de imágenes es la aplicación de la compresión de datos en imágenes digitales. En efecto, el objetivo es reducir redundancias en la imagen con el objetivo de transmitirla o almacenarla en una manera eficiente. La compresión puede ser con pérdidas (lossy), o sin pérdidas (lossless). La compresión con pérdidas que produce diferencias imperceptibles se llama también visualmente sin pérdidas (visual lossless)."²

Entonces podemos decir que se trata de reducir el número de bits con necesarios para representar una imagen. Y hay de dos tipos (que pueden ser tres, y no es el chiste del gato). Con pérdidas, sin pérdidas y visualmente sin pérdidas. En el ejemplo de compresor que estoy tratando de hacer, es un compresor con pérdidas, de una imagen en escala de grises de 8 bits.

Pero bueno, ¿cómo le hacemos para saber si el compresor que estamos haciendo vale la pena? Pues fácil, hacemos un montón de pruebas, observamos las imágenes resultantes y la que no se vea tan peor pues decimos que es nuestra imagen codificada usando un compresor con pérdidas. También lo podemos hacer de la manera fancy, usamos PSNR o MSE o cualquier otra medida de error matemática para ver que tanto se distorsiona en referencia con la imagen original.

---

1. Digital Image Processing 2nd Edition (DIP/2e)
   by Gonzalez and Woods
   © 2002. Prentice Hall
   
2. Image Compression
   From Wikipedia, the free encyclopedia. Extracted July 28th, 2009
   

Update del Compresor que estoy haciendo

• Ya tengo el algoritmo para hacer la extracción de Bits.
• Ya tengo el código para codificar la imagen binaria en RLE (gracias JMG, ya lo tenía arrinconado)
• Ya tengo el código para decodificar la imagen codificada con lo anterior

Ahora solo me falta hacer pruebas suficientes para llegar a una conclusión.

Lo voy a terminar...

... algún día.

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. :)

Visión por Computadora

¿Qué Visión por Computadora? Emular la visión humana por medio de una computadora. (¿Uhhh?)


El propósito de la visión por computadora es hacer lo que la visión humana hace, pero, por medios artificiales, para poder entender esto, primero hay que entender un poco como funciona la visión humana ¿no? Pues si, es ahí en donde empiezan los problemas. Nosotros tenemos los sentidos para percibir e interpretar nuestro medio ambiente, las cosas que nos rodean, es ahí donde comienza nuestra realidad. Físicamente, nuestros ojos nos sirven como una especie de sensores que captan las ondas luminosas que se reflejan en los objetos y los captura, los pasa al cerebro como impulsos eléctricos y el cerebro se encarga de hacer todo lo demás. (Que fácil se escucha todo esto, en realidad es mucho más complicado, pero a grandes rasgos así es).


El sensor que se encuentra en una cámara fotográfica la podemos comparar (en este caso) con los ojos, es la que nos permite captar las información de las ondas luminosas del ambiente y la convierte a impulsos eléctricos, aquí en este caso, la cámara también funge un poco como cerebro, puesto que procesa las señales eléctricas obtenidas del sensor y las acomoda en una forma que puedan ser transferidas a otro medio. Aquí, no se puede limitar a las cámaras fotográficas como único ejemplo, puesto a que también lo es un aparato de resonancia magnética, o bien, un ultrasonido.


Una parte muy importante en los sistemas de visión por computadora es la iluminación, ya sea la del ambiente o la propia del sistema. ¿Por qué es necesario un sistema de iluminación? Pues porque las condiciones de iluminación del objeto que vamos a capturar pueden afectar el objeto. Nuestro sistema de visión humano no necesita de tan preciso sistema de iluminación ya que puede distinguir los objetos ya que sus algoritmos son demasiado complejos y perfectos que no los podemos comprender. (Si, todavía soy de los que piensan que la computadoras no van a poder igualar el cerebro humano :P) La técnica a utilizar en el sistema va a depender puramente de la aplicación de la misma, esto es, no existe una técnica única para los sistemas de visión, y por lo consiguiente se tiene que analizar cual es la más apropiada para utilizar.


Bueno, si ya tenemos el sensor y la iluminación, ¿qué es lo que nos hace falta? pues la computadora, una vez que el sensor nos capturó la información y la convertimos de una manera que la computadora la pueda leer, pues lo que nos hace falta, son los algoritmos para procesar la imagen. ¡PUM!


Es ahí donde entra el procesamiento digital de imágenes, es emular lo que el cerebro hace, no los ojos, eso ya lo hicieron los sensores, ahora es el turno de emular al cerebro. (good grief!) Existen un gran número de algoritmos y técnicas de procesamiento de imágenes, y al pasar del tiempo se vuelven más complejos y pueden atacar problemas especificos que antes no era posible. Pero hay muchas cosas que el cerebro humano puede hacer y un sistema de visión no (¿por ahorita?)

Por ejemplo, si vemos la imágen del gran Vicente, una persona puede decir muchas cosas, desde la combinación de colores, hasta temas filosóficos acerca del porque del sí. Pero, si esta imagen es alimentada a un sistema de visión por computadora, pues no serían más que una fila de ceros y unos, haría falta de aplicar ciertos algoritmos para obtener cierta información, pero solamente será la información para la cual esta diseñado el algoritmo. Una computadora no puede decir nada de la pintura, no puede saber que se quiso transmitir cuando el pintor pintó la obra, ni siquiera se deprime cuando ve la imagen, ni mucho menos se siente identificada con el hastío que le transmite, ni se siente de ese mismo modo.

Technorati : visión computacional, visión por computadora

Del.icio.us : visión computacional, visión por computadora

Zooomr : visión computacional, visión por computadora

Flickr : visión computacional, visión por computadora