1 Terceiro Simpósio em Estatística Espacial e Modelagem de Imagens III - SEEMI 2010 Parque Tecnológico ITAIPU-PTI, Foz de Iguaçu, Brasil. Dezembro 14, 15 e 16 de 2010. TRANSFORMADA RÁPIDA FRACTAL Dr. Ing. Jesús Rubén Azor Montoya Universidad de Mendoza

2 La Transformada Fractal permite la codificación de una imagen basada en la Teoría de las Funciones Iteradas (IFS). La Transformada Fractal explota la auto-similitud asociada con las imágenes naturales

3 Todas las imágenes presentan la característica de auto-similitud y en base a esta característica Arnaud Jacquin discípulo de Michael Barnsley, a principio de los 80s desarrolló un esquema de compresión fractal que explotaba las auto-similitudes locales dentro de las imágenes. Con la estrategia propuesta por Jacquin, se logran algoritmos eficientes y seguros para codificar, y por ende comprimir con tasas muy altas, imágenes del mundo real con niveles de fidelidad suficientemente aceptables. Vale decir que, el proceso supone un análisis de la imagen que lleve a la obtención de los correspondientes códigos IFS, que serán el núcleo de la información que se habrá de archivar en el codebook.

4

5 Jacquin sugirió dividir a la imagen en dos tipos de bloques: el Dominio y el Rango, con la condición de que siempre sean cuadrados y que el tamaño del Dominio sea el doble del tamaño del Rango.

6 Bloque Dominio (a la derecha) y bloque Rango (a la izquierda). w indica la transformación que sufre el Dominio para ser comparado con el Rango, siendo i y k los índices que indican posición espacial

7

8 Los 8 mapeos afines contractivos transforman un bloque padre cuadrado en uno más pequeño, llamado bloque hijo.

9 Los datos de entrada son: - Matriz cuadrada de l 2 elementos conteniendo la información de la imagen a codificar (con l diádico) - Tamaño de los bloques Rango (rangesize), de modo que se obtienen (l/rangesize) 2 bloques Rango y (l/2*rangesize) 2 bloques Dominio.

10 2) Se reescalan los bloques Dominio (al mismo tamaño de los bloques Rango) por diezmado y se resta a cada elemento el promedio. Algoritmo Para la Codificación fractal 1) Se promedia la suma de los elementos del bloque Rango (por ejemplo, el primero de ellos), se redondea y se guarda el resultado en la variable o (Offset). Luego se resta a cada elemento del bloque la media calculada. o=round((133+255+188+31)/4)=round(151.75)=152 Nuevo Bloque Rango sin media -19 103 36 -121

11 3) Se encuentran las 8 transformaciones posibles para cada bloque Dominio transformado.

12 4) Se compara el primer bloque Rango con el primer bloque Dominio en sus ocho versiones transformadas para encontrar el que mejor se le parezca. Para ello, en cada transformación del Bloque Dominio escalado se hace una predicción lineal de primer orden para estimar el Bloque Rango desde cada Bloque Dominio. Al parámetro se lo denomina ss: El algoritmo exige que 0 < ss < 1 (Transformación Afín Contractiva)

13 5) La predicción (de las ocho transformaciones) que mejor mapea a los valores del Rango en consideración, es la llamada "distancia de collage" sobre dicho Rango. Se utiliza para determinarla el mean absolute error (error absoluto promedio) que es una cantidad usada para medir qué tan cerca de las previsiones o predicciones están los posibles resultados. El mean absolute error (MAE) está dado por: Como el nombre lo sugiere, el error absoluto promedio es un promedio de los errores absolutos e i = f i − y i, donde f i es la predicción e y i el valor verdadero. Se lo indicará con el nombre de variable minerror,

14 Cumplen con la condición: ss M minerror 0.2956 3 60.0653 0.8638 7 54.4494 0.7397 8 59.7877

15 Cumplen con la condición: ss M minerror 0.9735 1 61.9536 0.5386 7 61.1926

16 Cumplen con la condición: ss M minerror 0.2558 2 70.7093 0.5850 5 71.9438 0.9578 8 66.1582

17 Cumplen con la condición: ss M minerror 0.7993 1 53.5555 0.6137 3 58.1175 0.2972 7 57.7610

18 En resumen, de las 11 comparaciones válidas minerror resulta ser: Se sobremarca el menor de los valores minerror, correspondiente al Bloque Dominio con vétice superior izquierdo en (5, 5) y con la transformación 1.

19 Se salvan en el Codebook los siguientes coeficientes: Ubicación del Dominio del mejor ajuste: - Abscisa del vértice superior izquierdo ( e ) - Ordenada del vértice superior izquierdo ( f ) - La mejor transformación (conforme a un criterio, número del 1 al 8). - Contraste (factor de escalamiento, round(ss*100)). - Offset (o). 6) Se continúa haciendo lo mismo para el resto de los bloques Rango hasta que sea alcanzado el último.

20 Codificación total de la imagen ejemplo:

21 Algoritmo para la Transformada Rápida Fractal El algoritmo propuesto en este trabajo, apunta a agilizar el algoritmo clásico, a través de un pre-proceso, que se adelanta a las comparaciones de los bloques Dominio y Rango, utilizando como herramienta estadística la suma de las desviaciones medias absolutas de los mismos Para calcular la suma de desviaciones medias absolutas de un vector A de elementos {A i, i=1…n}, se utiliza la siguiente expresión:

22 Desarrollo del algoritmo Se parte de los mismos datos del algoritmo clásico, esto es se forman dos arreglos unidimensionales de Rango ({R i }) y Dominio ({D i }). Al arreglo de arreglos Dominio, ({D i }). que no está escalado, se lo escala a través de un diezmado y se calcula la suma de las desviaciones medias absolutas de cada uno de estos elementos del arreglo unidimensional conformándose un vector. Los elementos de este vector son la suma de las desviaciones medias absolutas de cada uno de los bloques Dominio escalados. Del mismo modo, se calcula la suma de las desviaciones medias absolutas de cada uno de estos elementos del arreglo unidimensional de Rangos, conformándose otro vector. Los elementos de este nuevo vector son la suma de las desviaciones medias absolutas de cada uno de los bloques Rango.

23

24 Se recorren todos los bloques Rango, comparando la suma de las desviaciones medias absolutas de cada uno de ellos con la de todos los bloques Dominio escalados, hasta encontrar el de suma de las desviaciones medias absolutas más próxima. En ese punto, se toma nota (en otro vector, que lo que se llamará índicador) del índice de Dominio para el cual se da esta cercanía. Posteriormente, se vuelve a recorrer todos los bloques Rango, pero ya con la información de los bloques Dominio que darán la mayor proximidad y se realizan las comparaciones correspondientes para obtener el número de la mejor transformación (de 1 a 8, en la Figura 2.1 de izquierda a derecha y de arriba abajo) y encontrando el contraste y el escalamiento.

25 Resultados experimentales Con el objeto de hacer consistentes los resultados de la aplicación de este nuevo algoritmo con otras investigaciones sobre el mismo tema, se usa la famosa imagen de Lenna en un arreglo de 512x512 pixeles en escala de grises en forma de archivo.bmp. Para toda la experimentación se ha usado una computadora portátil con procesador Intel Celeron (t.m.) de 1.5 Mhz, ejecutando el software Matlab 7.0 (t.m.). En primer lugar, se muestra la aplicación del método tradicional a la citada imagen y se registra el tiempo de codificación. Junto a este valor, se agregan el Root Mean Squared Error (RMSE) y el Peak Signal to Noise Ratio (PSNR) de la imagen decodificada, ambos como medidas de fidelidad de reproducción.

26 El Error Raíz Media cuadrada (Root Mean Squared Error, RMSE) es una “buena” medida de la fidelidad de una imagen estimada. Siendo u la imagen original de tamaño MxN, se define: Otra medida de la calidad de imagen relacionada es la Relación Señal a Rudo Pico (Peak Signal to Noise Ratio, PSNR), la cual es inversamente proporcional al RMSE, sus unidades están en decibeles (dB) y está formalmente definida por:

27 Resultados correspondientes al algoritmo tradicional Repetición de la experiencia para tres tamaños distintos del bloque Rango, pero aplicando el método de la Transformada Rápida Fractal. Como se puede apreciar, los tiempos de ejecución son notablemente menores con la aplicación del método propuesto, ante iguales rangesize. Si se observan las primeras filas de ambas tablas, se ve que se adquiere una fidelidad de imagen comparable utilizando un rangesize de 8 en el método tradicional que uno de 4 en el propuesto, pero esto con una relación en tiempo de 2374/62=38.29 a favor de este último, esto está indicando una rapidez de casi 40 veces.

28 a) Imagen de Lenna original, b) Tradicional, rangesize=8, c) Tradicional, rangesize=16, Rápido, rangesize=4, Rápido, rangesize=8, Rápido, rangesize=8. En todos los casos, la decodificación se ha hecho con 6 iteraciones.

29 Conclusiones Conforme a lo visto en los parágrafos anteriores, el algoritmo propuesto tiene todas las capacidades del de la Transformada Fractal clásica, pero su velocidad de ejecución es notablemente más rápida para una misma fidelidad de reconstrucción. Se ha elegido un estadístico en particular, la suma de desviaciones medias absolutas, pero esto no agota la búsqueda de algún otro, que pueda interpretar en forma más ajustada, la pre búsqueda que se propone en el trabajo como núcleo significativo del algoritmo.