Compresion-Fractal

Vista previa del material en texto

Compresión Fractal de Imágenes
S. Pérez-Becker
Facultad de Ciencias, Universidad Nacional Autónoma de México
En este art́ıculo se estudia de manera teórica y práctica la compresión fractal de imágenes. Se
explican las bases teóricas de su funcionamiento y se esboza un algoritmo para comprimir y descom-
primir imágenes con dicha técnica. La idea es presentar el método de forma clara y sencilla para su
mejor apreciación.
INTRODUCCIÓN
Este art́ıculo trata sobre el método de compresión frac-
tal de imágenes. La motivación principal de estudiar este
método fue entender el cómo las técnicas matemáticas
de los años recientes se pueden aplicar a problemas de la
vida cotidiana, como lo es la compresión de imágenes.
La vida digital actual no la podŕıamos concebir sin in-
ternet, e internet no seŕıa lo mismo sin técnicas de com-
presón y descompresión de datos. Esto es aśı, ya que la
velocidad de transmisión y la capacidad de almacena-
miento de datos son dos de los parámetros fundamenta-
les en el funcionamiento de la red. Estas técnicas hacen
mucho más eficientes los conceptos antes mencionados,
reduciendo enormemente los gastos que conllevan. La re-
levancia de la compresión de imágenes no se limita al
internet. Otros campos como la exploración espacial y
las aplicaciones tanto en satélites geoestacionarios como
en imágenes médicas son ejemplos en donde contar con
estas técnicas es fundamental [1].
Una de las técnicas de compresión de imágenes es la
compresión fractal (ver [2] para un resumen de otros ti-
pos de compresión), que fue inventada y refinada por
Michael F. Barnsley a finales de los años ochenta [9].
Esta técnica se basa en comprimir imágenes utilizando
el hecho de que muchas imágenes “naturales” presentan
autosemejanza. Una de las diferencias fundamentales de
este tipo de técnicas es que el código de compresión no
guarda pixeles, por lo que es libre de escalas. De esta for-
ma se puede descomprimir a cualquier escala sin tener
problemas de resolución.
La meta de este texto es explicar la teoŕıa que sus-
tenta el método y mostrar un algoritmo ilustrativo que
ejemplifica su implementación.
MARCO TEÓRICO
A continuación presentamos las herramientas ma-
temáticas y teoremas necesarios para entender el funcio-
namiento del método.
Mapeos y sus atractores
Las bases matememáticas para este método son los ma-
peos de subconjuntos de R2 en śı mismos que utilizan
transformaciones afines. Una transformación af́ın en un
punto del subconjunto S tiene la forma
wi
(
x
y
)
=
(
ai bi
ci di
)(
x
y
)
. (1)
Si le aplicamos el mapeo a todos los puntos de S, decimos
que le aplicamos el mapeo a S. Estos mapeos pueden ro-
tar, trasladar y reescalar dichos subconjuntos. Al volver a
aplicar el mapeo al subconjunto S previamente mapeado,
hicimos una iteración del mapeo. Usualmente trabajamos
con varios mapeos que actúan sobre nuestro subconjun-
to, si además lo hacen de forma iterativa decimos que
tenemos un sistema de funciones iteradas (IFS, por sus
siglas en inglés) [4].
El primer resultado importante de estos sistemas es el
llamado teorema de los puntos fijos en mapeos contrac-
tivos. Este teorema asegura que al aplicar una serie de
mapeos contractivos a un subconjunto S ∈ R2 de forma
iterativa, dicho subconjunto se irá a al atractor (o punto
fijo) SW de los mapeos. Esto pasa siempre y cuando los
mapeos sean contractivos. Cabe resaltar que el atractor
es independiente de las condiciones iniciales. Un ejemplo
muy famoso es el helecho de Barnsley, en donde un IFS
compuesto por sólo cuatro mapeos tiene como atractor
la imagen de un helecho (ver Fig. 1).
Fisher
(a) (b) (c) (d)
Figura 1: Esquema del IFS para el helecho de Barnsley. (a) El
subconjunto S esta marcado con una “L” para ver rotaciones
del mismo. (b) el IFS para el helecho, consiste en cuatro ma-
peos que contraen a S. (c) el atractor para el IFS: el helecho
de Barnsley. (d) un acercamiento al helecho muestra su na-
turaleza fractal, ya que es autosemejante. Figura tomada de
[5]
2
Esto también es la idea básica de la compresión fractal
de imágenes: es más compacto guardar las transforma-
ciones cuyo atractor es la imagen que queremos, que los
pixeles de dicha imagen. Siguiendo el ejemplo del helecho,
si guardamos la imagen como una colección de pixeles re-
queriŕıamos 65536 bits, mientras que si la guardamos co-
mo una colección de transformaciones sólo requeriŕıamos
768 bits (por los seis números que definen los cuatro ma-
peos).
Usualmente, las imágenes reales son un poco más com-
plicadas que un helecho en blanco y negro, por lo que un
IFS no será suficiente. El siguiente paso es considerar un
sistema de funciones iteradas en donde cada mapeo wi
actúa sobre un subconjunto Di ∈ R2 (ver Fig. 2). A es-
Welstead
Figura 2: Un sistema particionado de funciones iteradas. So-
bre un subconjunto Di ∈ R2 actúa un único mapeo wi que lo
lleva al rango Ri. Figura tomada de [8]
te sistema se le llama sistema particionado de funciones
iteradas (PIFS por sus siglas en inglés) [3].
Imágenes y PIFSs
Una vez definido un PIFS, pasamos a ver la definición
matemática de una imagen. Para este art́ıculo solamente
consideraremos imágenes en escalas de grises. Podemos
ver a una imagen de este tipo como una función f en
R2 que nos regresa un valor entero dentro de una escala
predeterminada (escala de grises):
f(x, y) → (1, 2, ..., N) ⊂ R, (x, y) ∈ I2. (2)
Por sencillez, suponemos que la imagen esta confinada
al cuadrado unitario (I2). También queremos definir la
distancia entre 2 imágenes, ya que esto nos dirá que tanto
se parecen éstas entre si. Nosotros tomamos la distancia
RMS como la adecuada, aunque nada nos impide utilizar
otras distancias.
dRMS(f, g) =
 n∑
i=1
m∑
j=1
(
f(xi, yj)− g(xi, yj)
)2 12 . (3)
Aqúı ya estamos suponiendo que el dominio de nuestras
imágenes es discreto, puesto que estamos hablando de
pixeles. Aqúı n y m son el número de pixeles horizontales
y verticales de las imágenes.
Ahora bien, siguiendo la idea del helecho, queremos en-
contrar un PIFS cuyo atractor se parezca mucho a una
imagen (es decir, que la dRMS entre el atractor y la ima-
gen sea pequeña). Dada una imagen, comenzamos par-
tiendola en una serie de celdas rango {Ri}. Estas celdas
rango deben cubrir por completo a la imagen y no se
deben traslapar. A cada Ri le asociamos una transfor-
mación wi que mapea los puntos de cierto dominio Di a
Ri (ver Fig 3). Formalmente, las wi’s se definen como
Welstead
Figura 3: El PIFS relacionado a una imagen. Los mapeos w̃i
actúan en su dominio Di (estos se pueden traslapar) y lo lleva
a su rango Ri (que cubren por completo el cuadrado unitario
sin que haya traslape). Figura tomada de [8]
wi(f(x, y)) = sif(w̃
−1
i (x, y)) + oi. (4)
Aqúı, w̃−1i (x, y) es la transformación que me lleva de Ri
a Di. Por lo que nuestra wi (que se define aplicándola a
f evaluada en los puntos de Ri) es la función f evaluada
en los puntos del dominio Di, multiplicado por un factor
si y recorrido por un factor oi. Cabe notar que la parte
espacial de wi mapea el dominio en el rango, por lo que
la transformación total toma a f evaluada en puntos del
dominio Di, la multiplica por si, le suma oi y la lleva al
rango Ri. Como estamos hablando de imágenes, si con-
trae o expande los valores de f , por lo que podemos decir
que se trata del contraste. Por otro lado, oi recorre los
valores de f , por lo que le asociamos el brillo de dicha
imagen. En la páctica, los dominios siempre serán ma-
yores que los rangos, por lo que las wi’s siempre serán
mapeos contractivos.
Para nosotros, el PIFS interesante (W que actúa sobre
f) va a ser la unión de todas las wi’s. Como los rangos
cubren toda la imagen, también lo hará nuestro PIFS.
Además, como se trata de una transformación contracti-
va, tiene un punto fijo.
Aśı que lo que nosotros buscamos es el PIFS W cuyo
punto fijo (fW ), se parezca mucho a la imagen original f .
Puede sonarcomplicado y poco práctico buscar los atrac-
tores de diferentes PIFS y ver si se parecen a la imagen
original (sobre todo por que los atractores aparecen des-
pués de muchas iteraciones del PIFS). Pero un teorema
nos facilita considerablemente el trabajo.
3
Un teorema útil
Un teorema que nos da una idea de cómo encontar a
W es el teorema del collage. Éste dice que si la distan-
cia entre una imagen f y la imagen transformada por W
(W (f)) se parecen mucho, entonces el atractor deW tam-
bién se parecerá mucho a f . Matemáticamente nos dice
que si dRMS(f,W (f)) ≤ �, entonces dRMS(f, fW ) ≤ �1−s .
Aqui s es el factor de contractividad de W (ver [8]).
El teorema nos asegura lo siguiente: solamente reque-
rimos que una iteración de W se pareza a f para que su
atractor fW también lo haga. Por lo que nuestra busque-
da de un W se facilita bastante.
Una vez que encontramos a la W indicada, la deco-
dificación consiste simplemente en aplicarle W muchas
veces a una imagen inicial g. Esto basta puesto que fW
es independiente de la imagen inicial y por el teorema del
collage sabemos que se parecerá mucho a f . El problema
se reduce entonces a encontrar W .
EL ALGORITMO
El algoritmo que utilizamos para encontrar a W se le
conoce como el de quadtree partitioning [5]. Consiste en
lo siguiente: Dada una imagen f que queremos codificar,
Partimos a f en una serie de celdas rango {Ri}.
Estas celdas deben cubrir por completo a f y no se
deben traslapar.
Cubrimos a f con un conjunto de celdas dominio
{Di}. Usualmente son muchas celdas dominio y se
traslapan. Entre mayor sea el numero de las Di’s
mejor será el resultado final, pero la compresión
será más tardada.
Para cada Ri, buscamos en el conjunto de las {Di}
la celda dominio y la transformación wi que mejor
la cubran. Las wi consisten en una rotación, una
reducción y un ajuste de brillo y contraste. Decimos
que una celda Di cubre a una Ri si la dRMS entre
ambas es menor a una tolerancia dada.
Si el ajuste no fue lo suficientemente bueno según
la tolerancia, dividimos a la celda Ri en cuatro sub-
celdas y repetimos el punto anterior para cada sub-
celda.
Continuamos repitiendo estos pasos hasta que todas las
celdas Ri estén cubiertas o que hayamos alcanzado el ta-
maño mı́nimo de las celdas rango que intentamos cubrir
(a esto le llamamos profundidad del quadtree). En caso
que lleguemos al tamaño mı́nimo de la celda rango, toma-
mos la celda dominio que mejor la cubre y la marcamos
como cubierta.
Cuando decimos que el resultado una compresión es
“mejor” que otro, cuantitativamente nos referimos a que
la suma de las dRMS de todas celdas Ri y sus respectivas
Di es menor que la suma del otro. Es decir, el error de
compresión es menor.
El código fractal como tal, consiste en una lista con un
renglón para cada Ri. Ah́ı escribimos el ı́ndice de quadtree
para la Ri, el indice de rotación (de 0 a 7, sólo hay ocho
posibles rotaciones de 90◦ en el plano, considerando la
reflexión como una), el ı́ndice de la celda Di que la cubrió,
el valor del contraste y el del brillo.
El ı́ndice de quadtree es una forma sencilla de ubicar
la posición de cada Ri utilizando vectores de dimensión
igual a la de la profundidad del quadtree. Los detalles son
bastante ténicos y poco importantes para este texto, por
lo que los omitiremos aunque el lector interesado puede
buscarlos en la bibliograf́ıa [8], en donde se explica muy
bien. La ventaja del ı́ndice de quadtree es que es libre de
escalas y se puede utilizar para descomprimir imágenes
de mayor tamaño.
Un ejemplo ilustrativo
Supongamos que queremos comprimir la imagen Lena
(ver Fig 4). Siguiendo los pasos del algoritmo, dividimos
Figura 4: La imagen a comprimir: Lena
inicialmente la imagen en cuatro celdas rango y al mismo
tiempo creamos una base grande de dominios que son
parte de la misma imagen (ver Fig. 5). La base de las
Di’s contiene de preferencia subconjuntos de la imagen
que se sobrelapan y que sean de muchos tamaños (es
decir, tamaños más pequeños). De esta forma será más
fácil encontrar una celda dominio que cubra bien la celda
rango en cuestión.
La primera iteración de nuestro algorimo no encon-
trará ninguna Di que cubra satisfactoriamente alguna de
4
D1 D2 D3 D4
D5
D9
Ri’s Di’s
Figura 5: Los primeros pasos del algoritmo. Partimos la ima-
gen en cuatro celdas rango Ri’s y al mismo tiempo hacemos
una base de celdas dominio Di. La base de las Di’s debe ser
muy grande, por lo que hacemos que las celdas se sobrelapen.
Dicha base debe contener celdas de todos los tamaños, para
poder estar seguros de que siempre encontremos una Di que
cubra a una celda rango dada.
nuestras cuatro Ri’s, puesto que una condición que le
imponemos al algoritmo es que el tamaño de las celdas
dominio sea mayor al de las celdas rango, para asi tener
efectivamente un mapeo contractivo.
Al no cubrir satisfactoriamente las Ri’s, el algoritmo
subdivide la primera celda rango (la celda color rojo en la
Fig. 5) y para cada una de las subceldas generadas repite
el proceso. Continuará subdividiendo las Ri’s hasta que
haya cubierto satisfactoriamente todas ellas.
La figura 6 muestra una celda dominio que, bajo un
mapeo bien escogido, podŕıa cubrir la celda rango mar-
cada. Por un lado cumple la condición de que la Di tiene
mayor tamaño que la Ri, además concuerdan bien los to-
nos claros y los obscuros en ambas celdas. Faltaŕıa ver
si una rotación y un ajuste de contraste y brillo mejora
la cobertura (esto seŕıa la elección del mapeo que mejor
cubre a la Ri.) Una forma gráfica de cómo el algoritmo
elige el mejor mapeo se muestra en la a figura 7. Teniendo
la Ri y Di candidatas, rotamos a la Di las ocho posibles
rotaciones en el plano. Aqúı consideramos únicamente
rotaciones de 90◦ y la reflexión sobre un eje como otra
rotación. Por lo que tenemos cuatro posibles rotaciones
de la celda original más otras cuatro de la celda reflejada
(ocho en total). De esas rotaciones escogemos la que me-
jor se ajusta a la Ri y la comprimimos para que ámbas
queden del mismo tamaño. Finalmente ajustamos los va-
lores del contraste y brillo mediante un procedimiento de
mı́nimos cuadrados para obtener los valores óptimos y
minimizar aśı la dRMS entre ambas celdas (ver [6]). Si
la distancia es menor a una tolerancia dada, considera-
mos la Ri como cubierta. Si no lo fue, subdividimos la
Ri en cuatro nuevas subceldas y para cada una volvemos
a buscar.
La naturaleza del método lo hace adaptativo al detalle
de cada parte la imagen. Los ojos de Lena por ejemplo
Di
Ri
wi
Figura 6: Un candidato para cubrir celda rango. Tarde o tem-
prano en el algoritmo de partición quadtree se llega a una
celda rango como esta Ri. Al algoritmo busca en la base de
celdas dominio y encuentra que esta Di la cubre bien.
Di
Ri
(a) (b) (c) (d)
Figura 7: Procedimiento para encontrar el mapeo. (a) tene-
mos la celda rango y la dominio que queremos comparar. (b)
rotamos a Di en una de las ocho posibles formas (cada 90
◦ es
una, también reflejamos y rotamos otras cuatro veces) y es-
cojemos la mejor. Aqúı solamente mostramos cuatro posibles
rotaciones. (c) comprimimos a Di para que coincida con el ta-
maño de Ri. (d) ajustamos el contraste y el brillo por medio
de mı́nimos cuadrados para obtener sus valores óptimos.
requerirán celdas rango mucho más pequeñas que seg-
mentos de la pared de fondo. Con este método siempre
tendremos el tamaño adecuado de celda según el detalle.
Como hab́ıamos mencionado, en la práctica ponemos
un cota inferior al tamaño de las Ri’s más pequeñas. De
lo contrario el tiempo de compresión seŕıa muy grande y
el factor de compresión bajo. Esta cota es justo la pro-
fundidad de quadtree.
5
DE LA TEORÍA A LA PRÁCTICA
Una vez que entendimos cómo funciona el algoritmo,
procedemos a explicar cómo se debe hacer un programa
que codifique y decodifique una imagen.
Codificando
La forma más clara de proceder con el programa es
primero crear las funciones que hacenlo que uno re-
quiere y luego escribir el programa mismo. Una de las
funciones más importantes es aquella que crea la ba-
se de las celdas dominio. Esta función toma una serie
de parámetros (número de celdas “columna”, número de
celdas “renglón”, traslape horizontal, traslape vertical y
niveles de tamaño: cada nivel implica celdas de la mitad
de tamaño que también cubren la imagen traslapándo-
se). Con esto hacemos que la función sea suficientemente
flexible y a la vez práctica, puesto que sólo requerimos
un ı́ndice para tener acceso a cualquier celda de la base.
El resultado es un lista de celdas en la que cada entrada
es una celda dominio. (por ejemplo la primera entrada de
la lista corresponde a la celda D1, etcétera.)
Otra función importante es aquella que registra las cel-
das rango. En este caso también trabajamos con una lis-
ta de celdas rango. La función registro controla que cada
celda rango de la lista tenga su ı́ndice quadtree correcto
y una “bandera” que indique si esta cubierta o no. Es-
tos elementos los guardamos en otra lista. Ambas listas
siempre deben ir sincronizadas.
Las funciones “operativas” consisten en dividir una cel-
da (rango), rotar una celda un cierto ángulo, reflejarla y
reducir el tamaño de la celda. Las útlimas tres funciones
son importantes para el proceso de comparación de cel-
das, puesto que eso se hace para cada celda dominio a
la hora de compararla con la celda rango. La forma en
que se reduce el tamaño de una celda es promediando un
pixel con sus vecinos mas cercanos y tomar dicho valor
promedio para ese pixel. Otras funciones importantes son
la que calcula los valores óptimos del contraste y brillo
(ver [6] para los detalles) y la que calcula la dRMS entre
una celda rango y una de dominio.
Todas estas funciones las utilizamos en la función
“maestra” que compara las celdas. Esta función toma
una celda dominio y una rango, a la celda dominio la
rota en cada una de las ocho posibilidades, la reduce al
tamaño de la celda rango y calcula los mejores valores de
contraste y brillo. Para cada rotación mide la distancia
entre las celdas y al final regresa la mejor distancia, jun-
to con el valor de contraste, brillo e indice de rotación
correspondiente.
El programa como tal empieza creando los dominios y
la lista inicial de rangos. Aqúı particionamos hasta que la
longitud de las celdas rango sea menor a la longitud de las
celdas dominio más grandes, para asegurarnos que siem-
pre haya un mapeo contractivo. Todas las modificaciones
que le vamos haciendo a las celdas rango las anotamos
en nuestra función registro.
Mientras que no haya cubierto todas las celdas rango,
el programa va analizando las Ri’s no cubiertas y para
cada una busca en todos los dominios aquel que diste
menos de esa celda rango. Si la distancia es menor a la
tolerancia, escribe en el archivo del código fractal el ı́ndi-
ce de quadtree, el ı́ndice de rotación, el ı́ndice de la celda
dominio, el valor del contraste y el del brillo. Marca como
cubierta esta Ri y pasa a la siguiente. Si la distancia no
fue menor a la tolerancia, parte la celda en cuatro e in-
serta en el lugar de la celda las cuatro subceldas nuevas.
Hace lo mismo con la función registro para que siempre
esté sicronizada. En caso de que no haya una celda do-
minio que cubra a una Ri que ya esta en la profundidad
máxima del quadtree, el programa toma la celda domi-
nio que mejor la cubrió, escribe esos valores al archivo
y la marca como cubierta. El programa acaba cuando
hayamos cubierto todas las celdas rango. La tolerancia
la definimos como el 2.5 % del error total entre las dos
celdas.
Para agilizar la compresión podemos hacer que una
vez que se haya encontrado una celda dominio que cubra
una celda rango, escriba los datos y se pase a la siguien-
te celda rango, ignorando las demás celdas dominio. De
esta forma ahorramos tiempo de compresión, aunque el
resultado final tendrá mayor error.
El código fractal
El código fractal consiste en un archivo que contiene
los datos relevantes. Dicho archivo contiene un renglón
por cada celda rango que se cubrió. Este número es va-
riable, según el detalle de la imagen o la tolerancia que
se haya impuesto. En cada renglón escribimos el ı́ndice
de quadtree, el ı́ndice de rotación, el ı́ndice de la celda
dominio, el valor del contraste y el del brillo. Un ejemplo
de un archivo con la imagen comprimida se muestra en la
figura 8. En este ejemplo utilizamos una profundidad de
quadtree de seis, por lo que los primeros seis valores de
cada reglón corresponden al ı́ndice quadtree. El séptimo
elemento es el ı́ndice de rotación, el octavo el ı́ndice de
la celda dominio (con los parámetros que escogimos en
este ejemplo, tenemos 1186 celdas dominio), el noveno es
el valor del contraste y el décimo elemento el valor del
brillo.
Para maximizar el factor de compresón se debeŕıa utili-
zar un código fractal en dónde el ı́ndice quadtree se guarde
en números binarios en lugar de números ASCII, que fue
lo que hicimos en este ejemplo. De esta forma se reduciŕıa
el tamaño del archivo de compresión, ya que cada número
del tipo ASCII ocupa ocho bits y uno binario solamente
uno. Si se hace correctamente se requeriŕıa 24 bits por
cada elemento del ı́ndice quadtree en lugar de los 48 que
6
1 1 1 1 0 0 5 214 -0.972271 143,701
1 1 1 2 1 0 1 1025 -0.181081 155.425
1 1 1 2 2 0 6 1000 0.128092 118.402
1 1 1 2 3 1 6 906 -0.6473713 238.301
1 1 1 2 3 2 6 708 -0.997927 224.18
índice quadtree rot. dom. contraste brillo
R1
R2
R3
.
.
.
.
.
.
R4
R5
Figura 8: Ejemplo del código fractal. En el archivo se escribe
un renglón por cada celda rango cubierta. En cada renglón se
escribe el ı́ndice quadtree (primeras seis columnas), el ı́ndice
de rotación, el ı́ndice de la celda dominio, el valor del contraste
y el valor del brillo.
nosotros requerimos. La diferencia es que el programa de
descompresión seŕıa algo más complicado para recuperar
el ı́ndice quadtree “comprimido”.
En este art́ıculo nos enfocamos en exponer la técnica de
compresión y no en hacerla eficiente, por lo que nuestro
archivo de compresión contiene el ı́ndice quadtree tipo
ASCII. Si el lector esta interesado en hacer un código
eficiente, se expone muy claro en la referencia [8].
Decodificando
El programa de decodificación está escructurado de
manera análoga al de codificación. También tiene las fun-
ciones de crear dominio, rotar una celda, y reducir una
celda. Las funciones nuevas que requerimos son una que
dé la posición en la imagen de una celda rango dado su
ı́ndice quadtree. Nosotros usamos como parametro la lon-
gitud de la imagen base para la decodificacion (la imagen
inicial que al aplicarle el PIFS se verá como el atractor),
que puede ser mayor o menor que la codificada. Aqúı po-
demos apreciar el hecho que este método es libre de es-
calas. Este parámetro también lo utilizamos en la fun-
ción crear rangos, que crea una lista de celdas rango en
la posición adecuada en la imagen base según su ı́ndice
quadtree.
Las funciones “maestras” son una que itera y otra que
muestra el resultado. En la primera le aplicamos una ite-
ración del mapeo guardado en nuestro código fractal a las
celdas dominio adecuadas y le asignamos el resultado a
las celdas rango correspondientes. En la función mostrar
colocamos a las celdas rango en su lugar apropiado en la
imagen (según su ı́ndice quadtree) y los mostramos en la
pantalla.
El programa como tal solamente carga los datos del
código fractal, se los asigna a listas correspondientes y
crea la lista de dominios y la de los rangos. De esta forma
se le deja al usuario iterar las veces que quiera e ir viendo
el resultado.
Un ejemplo del proceso de decodificado se muestra en
la figura 9. Aqúı tenemos la imagen base para decodificar
Imagen inicial 1.ra iteración 2.da iteración 6.ta iteración
a)
b)
Figura 9: Ejemplo del proceso de decodificación. a) La imagen
base (imagen inicial) es un cuadrado negro, despuésde algu-
nas iteraciónes se va pareciendo más y más al atractor, que
por el teorema del collage sabemos que se parecerá mucho a la
imagen inicial. b) Mismo procedimiento con otra imagen ba-
se. Vemos que el proceso es independiente de la imagen base,
lo cual confirma que el atractor de un PIFS es independiente
de la condición inicial.
(a) en su estado original, después de la primera, segunda
y sexta iteración. Vemos que las primeras dos iteraciones
son todav́ıa muy burdas, pero ya la sexta iteración se pa-
rece mucho a Lena. Sabemos que el atractor de nuestro
PIFS se parecerá mucho a la imagen original, ya que el
teorema del collage nos lo asegura. Para enfatizar nue-
vamente, lo único que estamos haciendo con la imagen
inicial es a ciertos segmentos de ella, les cambiamos el
contraste y el brillo, los rotamos y reducimos para lue-
go asignárselos a otros segmentos de la imagen. Es por
eso que la primera iteración consta solamente de cuadra-
dos de diferentes escalas de gris. La segunda imagen (b)
es el mismo procedimiento, pero con otra imagen inicial.
Podemos apreciar que el resutado final es el mismo. Este
hecho resalta el atractor de nuestro PIFS es independien-
te de la condición (imagen) inicial.
Es muy importante que los dominios creados en la par-
te de codificación sean los mismos que en la parte de
decodificación, porque si no, no coinciden los ı́ndices en
el código y no se verá el resultado deseado. Es por eso
que en principio de debeŕıan escribir los parámetros de
la función que crea las celdas dominio en la cabecera del
archivo con el código fractal.
CONCLUSIONES
Con estos programas logramos codificar y decodificar
la imagen de Lena. El tiempo de compresión en una
máquina con procesador de 2.83GHz fue de aproxima-
damente media hora para el programa que se queda con
la primera celda dominio que cubre la celda rango y de
7
aproximadamente dos horas para el que busca la mejor
distancia en todas las celdas dominio. En el programa de
decodificación se puede cambiar el tamaño de la imagen
inicial fácilmente y ver como se crea la imagen “libre de
escalas”. Como hubo una tolerancia a la hora de com-
parar dominios con rangos, la imagen final tiene ciertos
errores en comparación con la original, dichos errores se
magnifican si descomprimimos a mayores escalas.
Este método, aunque lento, tiene la ventaja de ser libre
de escalas y se puede usar para obtener imágenes relati-
vamente grandes. Esto a su vez lleva a que, dependiendo
del tamaño de la imagen descomprimida, se lleguen a te-
ner razones de compresión muy buenas. Como nota, el
algoritmo que utilizamos para comprimir es uno muy ru-
dimentario. Existen algoritmos mucho más eficientes que
reducen el tiempo de compresión a segundos (ver [8]).
Podemos extender la compresión de imágenes a imáge-
nes con color haciendo algunas ligeras modificaciones de
las técnicas aqúı presentadas. Básicamente tendŕıamos
que tratar a nuestra imagen como una función de R2 a
R3, en donde cada entrada del rango de la función corres-
ponde a un valor de rojo, verde y azul respectivamente.
Eso y un ligero cambio en la definición de las distan-
cia entre imágenes seŕıa suficiente para codificarlas. La
compresión de imágenes a color no solo tiene ventajas
estéticas. El poder manejar este tipo de imágenes permi-
te guardar información adicional mediante un código de
color, que en áreas como la medicina es de suma impor-
tancia.
Espero que este art́ıculo haya mostrado que no es tan
complicado entender y hacer un programa que codifique
imágenes con este método tan fascinante, que de hecho
sirve para más que sólo comprimir [7]. Se podŕıa decir
que éste es un ejemplo concreto de cómo el avance de
la ciencia nos ha permitido disfrutar de una vida digital
más completa.
[1] T. Acharya and A. K. Ray. Image Processing: Principles
and Applications. John Wiley and Sons, 2005.
[2] Mauro Barni. Document and Image Compression. CRC,
2006.
[3] Michael Barnsley. Fractals Everywhere. Academic Press,
1989.
[4] Michael Barnsley. Fractal image compression. Notices of
the AMS, 43(6), 1996.
[5] Yuval Fisher. Fractal image compression. In SIGGRAPH
’92 Course Notes, 1992.
[6] David Jeff Jackson and Greg Scott Tinney. Performance
analysis of distributed implementations of a fractal image
compression algorithm. Concurrency - Practice and Expe-
rience, 8:357–386, 1996.
[7] Joan Puate and Fred Jordan. Using fractal compression
scheme to embed a digital signature into an image. In Tes-
cher, AG and Chiueh, TC, editor, Video techniques and
software for full-service network, volume 2915 of Procee-
dings of the society of photo-optical instrumentation engi-
neers (SPIE), pages 108–118, 1997.
[8] Stephen Welstead. Fractal and Wavelet Image Compres-
sion Techniques. SPIE, 1999.
[9] Barnsley patentó varios de estos métodos y fundó la com-
pañ́ıa Iterated Systems Incorporated (La primera patente
de Barnsley y Sloan con respecto a compresión de imáge-
nes usando sistemas de funciones iteradas, fue U.S. Pa-
tent 4,941,193, registrada en Octubre de 1987). Este hecho
ejemplifica que a partir de una idea relativamente sencilla
y una aplicación de los fractales, una compañ́ıa ha sido
capaz de generar recursos económicos considerables.