UNIVERSIDAD AUTONOMA METROPOLITANf148.206.53.84/tesiuami/UAM7021.pdf · variacion de los puntos en...
Transcript of UNIVERSIDAD AUTONOMA METROPOLITANf148.206.53.84/tesiuami/UAM7021.pdf · variacion de los puntos en...
UNIVERSIDAD AUTONOMA METROPOLITANf
UNIDAD IZTAPALAPA
CIENCIAS BASICAS E INGENIERIA
LICENCIATURA EIN COMPUTACION
PROYECTO DE INVESTIGACION I1
/'IMAGENES Y FRACTALES'
ARTE Y CIENCIA
ASESORES: M. EN C. JORGIE LOZANO DR. JOSE LUIS DEL RIO
ALUMNO: DAVID ARCIA SEGURA
MATRICULA: 85224588 E
I ENERO 1991
C O N T E N I D O
Pag . I .. IMAGENES Y FRACTALES ........................... 1
I1 .- DIGITALIZACION DE FRACTALES .................... 3
111.- EL FORMATO ESTANDARD PCX ....................... 5
IV .- EL FORMATO DE ARCHIVOS PCX ..................... 6
V .- RUN LENGTH ENCODING (PRINCIPIOS BASICOS) ....... 8
FUNCIONAMIENTO DEL ALGORITMO ................. 10 LISTADO 1 (ENSAMBLADOR) ...................... 13
LISTADO 2 (LENGUAJE C) ...................... 16
VI .- RUN LENGTH ENCODING (MODIFICADO) ................ 2 3
LISTADO 3 (CORREGIDO Y AUMENTADO) ............ 26 VI1.- DIBUJO DE FRACTALES ............................. 32
FUNCIONAMIENTO DEL ALGORITMO ................. 3 2
LISTADO 4 (BASICO) ........................... 33
LISTADO 5 (EXPANSION DIRECTA CON PUNTOS) ..... 37 LISTADO 6 (EXPANSION DIRECTA CON LINEAS) ..... 41
VII1.- BIBLIOGRAFIA ................................... 47
IMAGENES FRACTALES
En. terminos generales, podemos describir a un fractal como un
objeto que posee una peculiar dimensionalidad fracciona1 o
dimension fraccionada, y ademas tienen la característica de ser
autosimilares, esto es, que cada microelemento de un fractal,
posee las mismas caracteristicas de un elemento de mayores
dimensiones.
Los fractales son el resultado de mas de 100 años de
investigacion por parte de algunos brillantes matematicos del
siglo pasado, como Cantor, Peano y Hilbert, ya que fueron ellos
los que descubrieron unas curvas maravillosas con propiedades
sorprendentes. Cantor demostró la posibilidad de construir una
curva que pasara por todos los puntos de un cuadrado, Peano fué
el primero en encontrar como construirla, en tanto que Hilbert
encontró una forma distinta de hacerlo, que además permitía
generalizar fácilmente a tres di,mensiones, de hecho con la curva
de Hilbert se puede llenar un cubo con una línea. Sin embargo no
fui! sino Benoit Mandelbrot, el cientifico que logró avances
sorprendentes en el campo de los fractales cuando despues de
pasar desapercibido con sus trabajos por mas de quince años,
publicó un titulo llamado "cuánto miden las costas de Bretaña ?.
Autosimilaridad estadística y dimension fraccionalll. En este
trabajo Mandelbrot muestra que las costas de Inglaterra, son
objetos cuya longitud es infinita y que la única manera de
1
asociarles alguna medida, es asociándoles una dimension no
entera, de manera que las costas son objetos que comparten varias
propiedades de las curvas de Pea:no.
Una de estas propiedades ya mencionadas en la definición de
fractal es la autosimilaridad, que se presenta cuando los objetos
son invariantees ante un cambio Ide escala, esto significa que si
nosotros poseemos dos fotos de u:n objeto autosimilar, una de todo
el objeto, y la otra una amplificación de una parte de tal
objeto, y no se nos dice cuál es cuál, entonces seremos incapaces
de distinguir entre el todo y un pedazo amplificado del mismo.
Mandelbrot mostró que la curva de Koch, hera un modelo burdo pero
realista de una costa, la diferencia es que la curva de un copo
de nieve es perfectamente autosi:milar en tanto que las costas son
estadísticamente autosimilares. Lo anterior significa que si
tomamos un fragmento de la curva de Koch y la multiplicamos por
un factor adecuado, esta amplificación la podemos superponer
exactamente con toda la curva. Esto no sucede con la foto de una
costa, en donde aunque no seamos capaces cuál es la foto original
y cuál la amplificacíon, al sup'erponer ambas fotos no coinciden
todos los puntos.
.2
DIGITALIZACIOIN DE FRACTALES
Una gran variedad de fract'ales son el resultado de una
variacion de los puntos en el plano complejo, el comportamiento
de esos puntos está descrito por ecuaciones matematicas aplicadas
repetidamente en el plano comlejo. una de estas equaciónes es la
descrita por bX + iY. Donde X 'y Y son números reales y i es la
raiz cuadrada de -1. Una funcion en el plano complejo es una
regla que rota un punto de una posicion a otra en el plano. Esta
es especialmente interesante al ver el efecto de la función
en un punto cuando dicho punto es movido repetidamente por la
misma función. A dicho proceso se le conoce como iteracion.
Invariantemente para toda función en el plano complejo, por muy
simple que éSta sea, el efecto de iteracion en diferentes puntos
puede arrojar resultados verdaderamente dramaticos. A traves de
la iteración, una función puede introducir un punto una y otra
vez desde su punto de inicio, mientras que otro punto puede ser
guardado en otra area. Es posible dibujar una imagen basandose en
la variacion de puntos en el plano complejo dandoles colores
diferentes a cada una de las regiones cercanas al centro del
punto de iteracion, y un color diferente a las regiones mas
alejadas del punto inicial. El resultado de utilizar esta
técnica para algunas funciónes es que la frontera entre
diferentes zonas de colores son una curva FRACTAL. Una de las
funciónes más estudiadas y en la cuál se basa el trabajo
3
realizado por el proyecto "ARTE 'Y CIENCIA'' es :
f(Z) = lamda * Z * ( 1-Z )
Donde lamda y Z son números complejos. La función toma el punto
Z como inicio y lo rota a un nuevo punto f ( z ) . El número complejo
lamda es una constante en esta ecuación, y diferentes valores de
lamda darán por resultado diferentes curvas FRACTALES.
Cuando esta técnica es aplicada por medio de un algoritmo de
computadora, y cada punto en el plano complejo es representado
por un pixel en el monitor de la computadora, se obtiene lo que
se conoce como un mapa de bits, el cuál se almacena en forma de
archivo en formato ASCII standard, el tamaño del archivo generado
es siempre de 307200 bytes, independientemente del fractal
generado por el algoritmo, esto se debe a que está diseñado para
monitores V.G.A. de 640 X 480 pixel's, y dado que cada pixel
representado en el archivo es de 1 byte de longitud, el area del
monitor es precisamente 307200 pixel's.
Es en este punto en donde la compactacion de archivos juega un
papel muy importante, la razón es que al digitalizar imágenes - converetir imagenes en bits para el procesamiento por
computadora- demanda una gran cantidad de memoria de computadora.
El siguiente tema aborda de manera detallada algunos de los
formatos estandares mas empleados en el almacenamiento de
imágenes digitalizadas, así como las tecnicas de compactacion de
archivos mas empleadas en este tipo de imágenes y gráficas,
exponiendo sus principales ventajas y desventajas.
4
FORMATO =TANDAR pcX
Los formatos PCX se han convertido en uno de los formatos
estándares de hoy en día. Desarrollado por ZSoft (Marietta,
Georgia), para ser utilizado co:n su editor 'lPaintul para gráficas
en PC. El formato PCX además es 'un método simple y razonablemente
compacto, de almacenamiento de d.atos gráficos.
Este formato ha ganado gran popularidad debido a que el
paquete para PC Paint Brush incluye a este formato junto con el
Mouse de Microsoft. Esto originó que un mayor número de
usuarios de paquetes gráficos se sientan atraídos hacia este
formato. Al parecer mas scanners, fax y sistemas publisher desks
procesan archivos en formatos PCX. Se ha encontrado sin embargo,
que no ha habido una forma manual de imprimir esas imágenes en
una impresora PostScript, excepto por lectura previa mediante
otro procesador de imágenes como el Manuscript de Lotus, lo cual
en muchas ocasiones no resulta conveniente ( particularmente
cuando la imagen proviene de un fax).
PostScript, por otra lado, es un lenguaje PDL (Page-
Definition-Lenguage), que es un lenguaje de programación de alto
nivel con un conjunto de operaciones a las que se les asigna la
especificación de marcas en la página, incluyendo imágenes,
trazado de líneas y texto. Este es un lenguaje orientado a pila
(Stack Oriented) en el que la mas sobresaliente e interesante
función es que éste puede ser leido y procesado en orden lineal,
sin que siempre se tenga que retroceder. Esto lo hace ideal para
5
uso en una impresión, que es una típica conexión unidireccional a
la computadora. PostScript es probablemente la mas poderosa forma
disponible actualmente para especificar la descripción de una
salida de página a una impresora.
El problema con PostScript es que ninguna impresora fue
hecha para escribir en PostScrip't, no es posible enviar un texto
directamente (por ejemplo con Print Screen), y ciertamente no se
puede enviar una imagen a impr'esión sin trabajar bastante duro
para lograrlo.
FORMATO DE .ARCHIVOS PCX
El método de compresión de datos que emplea el formato PCX es
el RLE (Run Length Encoding), que consiste básicamente en tomar
cualquier número de caracteres consecutivos y reemplazarlo por un
contador de compresión seguido ,por el valor mismo del caracter.
El contador de compresión es distinguible del byte de datos por
medio de los bits mas significativos, que son puestos en rrllr para
los caracteres repetidos y en r r O t r para los no repetidos. Los 6
bits restantes representan el numero de repeticiones, de O a 6 3 .
RLE es frecuentemente una excelente forma de almacenar datos
de imágenes (como lo hace el Paint Brush en la generación de
imágenes), especialmente cuando la imagen contiene áreas extensas
de un mismo color. Sin embargo, en datos aleatorios o imágenes en
tonos de gris, donde son repetidos pocos bytes de datos, el
6
formato PCX quizá no sea muy recomendable, ya que puede aumentar
hasta en un 2 5 % el tamaño del a r c h i v o o r i g i n a l .
'7
RUN LENGTH ENCODING 1 R. L.E 1 ( PRINCIPIOS BASICOS)
La elección de una técnica de compactación de imágenes que
ofreciera un factor de compresió:n muy elevado, así como un método
muy simple de compactación y recuperación de archivos, reduciendo
al máximo el tiempo de ejecución y que a la vez considerara las
características de l o s fractales, es de vital importancia en la
fase del procesamiento de imágenes.
Tomando en cuenta estos requerimientos, la técnica que reune
las mejores características es el método conocido como Run Length
Encoding ( RLE ) el cual ofrece una forma eficiente y simple de
reducir los requerimientos de almacenamiento.
Run Length Encoding ( RLE ) es una técnica empleada para reducir
l o s requerimientos de almacenamiento de archivos de texto, bases
de datos, e imágenes digitales : siendo estas últimas en las que
se aprovechan al máximo las ventajas que ofrece la técnica. El
algoritmo es muy simple de implementar y produce archivos de
salida, que en promedio para los archivos de texto y base de
datos requieren un 80 % del espacio del archivo original, es
decir, reducen el espacio en un 2 0 %; en el caso de la imágenes
digitales el factor de compresión se incrementa en una forma
dramática, llegando a ocupar, en el mejor caso ( cuando todos los
caracteres son iguales ) , tan solo el 0 . 7 8 del espacio que
ocupaba el archivo original, lo que representa una reducción de
espacio del 9 9 . 2 1 % .
8
Cabe hacer notar que este algoritmo tiene grandes deficiencias
en el peor caso ( este ocurre cuando todos los caracteres son
diferentes ) , ya que el espacio que ocupa el archivo original se
duplica .
9
FUNCIONAMIENTO DEL ALGORITMO
El algoritmo RLE consiste en tomar un buffer de entrada para
examinar todas las apariciones de caracteres idénticos, en el
momento que se detecta un cambio de caracter, el conteo de
repetición del caracter previo ( que corresponde al conteo del
número de veces que se repite ) , es enviado a un buffer de salida
junto con dicho caracter, esta operación requiere de dos bytes,
uno para el caracter equivalente al contador de repetición y otro
para el caracter mismo; de esa forma es posible tener un máximo
de 256 caracteres repetidos en un solo byte para el contador de
repetición, sin embargo, cuando no hay caracteres repetidos, se
emplea un byte para contabilizar la aparición de un solo
caracter, empleando un byte adicional en esa operación. Para
ejemplificar lo anterior veamos lo que ocurre con las siguientes
cadenas de caracteres correspondientes al buffer de entrada y de
salida, respectivamente :
Buffer de entrada : AAAABB:BBBBCCDEEEEE Buffer de salida : 4A6B2ClD5E
En este ejemplo los 18 caracteres del buffer de entrada son
reducidos a 10 en el buffer de salida, con la aclaración de que
el contador de repetición no es un número, sino el caracter
correspondiente ( recuérdese que cualquiera de los 256 caracteres
ASCII es direccionable con 8 bits "un byte" ) .
Hasta el momento solo se ha hablado de la técnica de
compactación; ahora veamos como se recupera el archivo
comprimido.
Esta sencilla operación consiste en tomar un buffer de entrada
del cual se extrae el caracter de repetición, entonces, el
caracter siguiente en el buffer de entrada se envía a un buffer
de salida las veces indicadas por el caracter de repetición.
Run Length Encoding es una técnica rápida y eficiente para
reducir los requerimientos de espacio de archivos, dando los
mejores resultados en imágenes digitales. Aunque existen
algoritmos mas complejos con mejores factores de compresión,
éstos requieren de un gran tiempo de ejecución, tanto en
compresión como en recuperación. Las ventajas que ofrece RLE
radican en su elegancia y simplicidad.
1 It 146242
Por otra parte, es indispensable considerar el lenguaje y la
implementacion del algoritmo, ]para poder contar con la máxima
optimizacion de los recursos disponibles en la rápida ejecucion
de la rnanipulacion de las imagenes.
En base a los requerimientos, se desarrolló una primera
aplicación en lenguaje ensamblador del microprocesador 80286 para
ser ligada posteriormente al modulo de manejo de imagenes propio
del paquete comercial "ARTE Y CIENCIAgg desarrollado en lenguaje
ggCgv utilizando el compilador Quick-C de MicroSoft, el programa
fuente se muestra en el listado 1, el cual incluye las rutinas de
compactación y de recuperacion de archivos.
1 :2
LISTADO 1
PROGRAMA DE COMPACTACION TJTILIZANDO LA TECNICA RLE
I
; PROGRAMA : RLE .ASM ( Run Length Encoding ) ; AUTOR : David Garcia Segura ; FECHA : 10/07/90
I
I
I
I
I
Empaqueta : I
Esta rutina empaqueta el bu.ffer fuente dentro del buffer destino ; por reducci'ln de secuencias de caracteres identicos utilizando ; 1 byte para el contador de repetici"n, y 1 byte para el caracter.; ENTRADA : DS:SI -> Apuntador al buffer fuente a empaquetar ;
ES: DI -> Apuntador al destino. I
I DX -> N#inero de carac. en el buffer fuente a ; I colnprimir. I
I SALIDA : DI -> Es actualizado para el soporte de ; I mu:ltiples llamadas. I
I I
TITLE COMPRIME
DATA SEGMENT WORD PUBLIC
ASSUME DS : DATA
I EXTRN Checksnow : BYTE
DATA ENDS
CODE SEGMENT BYTE PUBLIC
ASSUME CS:CODE ;Texto segment public pack proc near mov bP, SP push ax push bx push cx lodsb mov bl, al xor cx, cx cld
; guardar el ambiente
; inicializar el contador de frecuencia ; todo movimiento es adelante
( Continua ...) 1 :3
pl0 :
je
lnc sub
CmP j ne
mov inc xor mov inc
p20: je mov inc xor mov inc mov j mp
lodsb ; cargar el caracter dentro de AL cx ; incrementa el contador de caracter dx, 1 I
P30 ; salir cuando DX = O cx, 255 ; hay 25!5 caracteres todavia en este bloque ? P20 ; si no entonces salta
[di] , cl ; salida de longitud di cx , cx [di] , bl ; salida de caracter di
CmP al , bl I
PI0 ; no.. . asi que salta [di] , cl ; salida de longitud di cx , cx [di] ,bl ; salida de caracter di bl , al ; mueve e1 caracter mas reciente a BL PI0 ; regresa al ciclo por m S
; se llega a aqu! cuando DX finalmente es cero
p30: mov al , cl ; salida de longitud I
stosb mov al , bl ; salida de caracter stosb
POP cx POP bx POP ax ret
pack endp
I
I I
; DESEMPAQUETA : I
I NOTA : La region fuente debe terminar con NULL I
I ENTRADA : DS:SI -> buffer fuente a empaquetar I ES:DI -> buffer destino a desempaquetar en el
I
I
I
I
I SALIDA : I
unpack proc near push ax push cx xor cx, cx : inicializar contador de repeticion en o cld ; todo movimiento es adelante
unpl0: lodsb ; cargar en AL el caracter de DS:[SI] FmP a1,O : longitud O en el fin de la region le unp4 O mov cl , al ; dejar :La longitud en CL lodsb : AL fu el caracter a repetir
TeP stosb ; almacena AL a [DI] y repite mientras CX <> o Imp unplO ; regresa al ciclo nuevamente
unp4 O : pop cx
unpack endp :texto ends code ends end
POP ax ret
"
No obstante a que este algoritino es lo suficientemente simple y
eficiente, no proporciona :La suficiente versatilidad y
adaptavilidad para ser manejado con libertad en el dibujo y
almacenamiento de las imagenes, así que nuevamente se pensó en
una implementacion en un 1engua:je que combine caracteristicas de
bajo y de alto nivel como el lenguaje IrCrl, por tal motivo se
desarrolló una segunda versióm del algoritmo con una mejor
presentación en lenguace IrCrr la cual se muestra en el listado 2.
LISTADO 2
PROGRAMA DE COMPACTACION UTILIZANDO LA TECNICA RLE
/* FUNCION : COMPR1ME.C FECHA : 28/10/1990 DESCRIPCION : Funcion que comprime el archivo de entrada utilizando
tecnica RLE.
#include <stdio.h> #include <mem.h > #define maxmem 30720 #define maxlong 30725 void comprime (f i, fo) FILE *fi,*fo; { register int i = O ; register int j = O ; register int k; register int 1; int in size,q; unsigned chgr in-str[maxlong], out-str[maxlong];
memset (in-str, NULL, maxlong) ; memset(out-str,NULL,maxlong); while ((in-size = fread(in str,l,rnaxmem,fi)) != NULL ) {
i = O ; - while ( i < in-size )
{ if ( in-str[i] == in str[:i+l] & & in-str[i+l] == in_str[i+2] )
{ -
k = proces-comp(in-str,i,in-size); if ( k+j > maxmem ) {
fwrite (out-str, 1, j , :€o) ; memset (out-str , NULL,, maxlong) ; j = O ;
) out str[j++] = (unsigned char) k I 0x80; outrstr[j++] = in str[i]; i += k;
} /* if */ -
else
( Continua.. . )
LISTADO 2
PROGRAMA DE COMPACTACION UTILIZANDO LA TECNICA RLE
{ k = proces descomp(in-,str,i,in-size); if ( k+j >maxmem ) {
fwrite (out str, 1, j , fo) ; memset (outIstr,NULL,maxlong) ; j = O ;
1 out-str[j++] = (unsign'ed char) k; for ( 1 = 0;l < k;l++) out str[ j++] = in-str[i++] ;
1 /* else */ } /* while */ memset ( in-str , NULL, maxlong) ;
} /* while */ fwrite(out str,l,j,fo);
1 /* compres-*/ (****at***** preces camp **********/ lnt proces-comp(inIstr,i,in-size) unsigned char *in-str; int i; int in-size; {
reqister int lon = O ; while ( in-str[i] == in-str[i+l] & & i < in size )
{ -
ion++ ; i++ ; if ( lon == 126 )
break; } /* while */
if ( i >= in-size )
return(1on + 1) ; lon-- ;
} /* proces-comp */ ( Continua ...)
18
LISTADO 2
PROGRAMA DE COMPACTACION UTILIZANDO LA TECNICA RLE
/********** preces descomp **********/ int proces descomp7i.n-str,i,in-size) unsigned cEar *in-str; int i; int in-size; {
reqister int lon = O; while ((in-str[i] != in - str[i+l] I I in-str[i+l] != in_str[i+2]) & &
i < in-size) {
ion++ ; i++ ; if ( lon == 127 )
break: )/* while */
) /* proces-descomp */ return (lon) ;
1 '9
LISTADO 2
PROGRAMA DE COMPACTACION UTILIZANDO LA TECNICA RLE
/ * FUNCION : RESTAURA.C FECHA : 29/10/1990 DESCRIPCION : Funcion que restaura el archivo comprimido mediante la
tecnica RLE.
#include <stdio.h> #include <mem.h > #define maxlong 30725 #define maxmem 30720 #define no-fin 1 void restaura(fi,fo) F I L E *fi,*fo; {
register int i= O ; register int j ; register long k= O ; register int 1 ; unsigned char in~str[maxlong],out~str[rnaxlong]; int m,resto,in-size;
memset (out-str , NULL, maxlong) ; mernset(in-str ,NULL,maxlong); in-size = fread(in-str,l,rnaxmem,fi); while ( no-fin ) {
j = in-str[ i++] ; if (j > 128) {
if ((j - 128) + k > maxmmem) { fwrite(out-str, 1, :k, fo); memset (out-str, NUL:L, maxlong) ; k = O ;
1 i f ( i >= in-size ) {
memset (in str, NULL, maxlong) ; if ( (in-size = fread( in-str, 1, rnamnem, f i) ) == NULL ) {
fwrite(out-str, l , k , fo) ; memset (out-str, NULL, maxlong) ; break; /* if */
i = o; }
(Continua ...)
LISTADO 2
PROGRAMA DE COMPACTACION TJTILIZANDO LA TECNICA RLE
for (j -= 128; j > O ; j--)
i++ ; out-str[k++] = in-str[i];
} /* if */ else { 1 = O ;
if ( (j+k) > maxmeim ) { fwrite(out str, 1, k, fo); memset(outIstr, NULL, maxlong); k = O ;
1 if ((j+i) >= in-size) {
resto = in size - i; for (1 = 07 1 .< resto ; I++)
memset (Tn str, NULL, maxlong) ; if ((in-size = fread(in str, 1, maxmem, fi)) == N U L L ) {
fwrite(out-str, l,k,-fo) ; memset (out-str, NULL, maxlong) ; break;
out str [k++] = in-str [ i++] ;
} / * if */ i = O ;
1 for (m = O ; m < (j-1); m++)
out-str[k++] := in-str[i++]; 1
1 /* while */ } /* restaura */
2 :1
1 4 6 2 4 2
Esta versión del algoritmo resulta ser lo suficientemente
rapida y eficiente como para ser empleada con buenos resultados,
sin embargo, aún existe un problema grave por resolver : Como ya
se explicó anteriormente, este algoritmo sufre de severas
deficiencias cuando se aproxima al peor caso, esto es, entre
menor sea el número de caracteres repetidos dentro del archivo a
compactar, lo cua1,implica que el factor de compresion se reduce
significativamente e inclusive llega a duplicar el tamaño del
archivo de entrada. Por tal motivo, se planteó la pregunta :
Será posible modificar el algoritmo original de modo que se
optimize el factor de compresión al acercarse al peor caso ?o, la
respuesta a esa pregunta llevó a replantear el problema original,
para cambiar ciertas condicionels básicas, dando como resultado
una reducción dramática en la colmplejidad temporal del algoritmo,
la nueva versión de RLE se describe detalladamente a continuación.
2 :2
RUN LENGTH ENCODING
(MODIFICADO)
Como ya se mencionó anteriormente, existe una gran diversidad
de técnicas de compresión, que van desde las muy simples
(salvando una mínima cantidad de espacio) a las muy complejas
(que requieren cantidades significativas del tiempo del
procesador) . Pensando en esto, se crea el RLE descrito anteriormente, sin
embargo como ya hemos mencionado, el enfoque presentado en los
principios básicos tiene gralndes deficiencias cuando los
caracteres en el archivo de entrada son únicos, es decir cuando
no existen caracteres contiguos idénticos. En este caso el tamaño
del archivo original se duplica.
4
Dichas deficiencias originain al planteamiento de algunas
consideraciones tendientes a mejorar la técnica original.
$ Básicamente son dos l o s cambios al método de codificación, que
arrojan resultados muy favorables y un dramático incremento en el
factor de compresión, sin que esto afecte de manera significativa
el tiempo de procesamiento:
1.- No comprimir menos de tres caracteres repetidos.
2.- Marcar áreas de caracteres no repetidos, del mismo modo que se hace con l o s caracteres idénticos, usando un bit para indicar si la siguiente entrada es compresible o no.
La forma en que afectan estos cambios al algoritmo original,
es la siguiente:
2 :3
3' Cada byte en el archivo es marcado como IvcomprimidoV1 o "no
comprimidov1, los marcadores (o bytes de compresión) ocupan un
byte. Un byte de compresión se puede diferenciar mediante la
utilización del bit mas significativo puesto en I v l t 1 , mientras que
un byte no comprimido tendrá IIOvl en el bit mas significativo. Los
7 bits restantes son usados para indicar la longitud (1 - 128) de los caracteres compresos o incompresos.
El byte de compresión (con el bit mas significativo puesto en
vvlll), cuyo valor total es mayor o igual a 128, indica el número
de veces que se repite el caracter siguiente al byte de
compresión.
Cuando un byte de compresión indica caracteres no duplicados
(con el bit mas significativo puesto en vvO1l ) , y cuyo valor total
es menor o igual a 127, estará .indicando el número de caracteres
no repetidos que vienen a continuación en el buffer de entrada.
Con estas modificaciones, el peor caso (con todos los
caracteres no repetidos) genera 1 2 9 bytes por cada 128, y el
mejor caso (con todos los caracteres idénticos) genera 2 bytes
por 128 de entrada. Observemos esto en el mismo ejemplo
mostrado para el método original:
Buffer de entrada : AAAABBBBB:BCCDEEEEE Buffer de Salida : SABBCCDaE , que representa :4A6B3CCD5E En este ejemplo podemos observar que el buffer de entrada se
comprime a solo 10 bytes, que es la misma longitud resultante del
algoritmo original. Sin embarlgo, cuando existen mas de 128
caracteres no repetidos, el algoritmo original duplica esta
24
.
cantidad, mientras que este nuevo algoritmo solo lo incrementa en
un byte.
Nótese que el patrón CCD sollo incrementa la longitud en un
byte, que corresponde al contador de caracter; esto debe ser
verdadero para cualquier número de caracteres únicos en el buffer
de entrada.
25
En base a las nuevas consideraciones con respecto al programa
inicial, se desarrolló la nueva version de RLE en lenguaje ttc",
la cual se muestra en el listado 3.
26
LISTADO 3
RUTINA DE COMPACTACION u m x z m D o LA TECNICA RLE
( VERSION MODIFICADA )
/* FUNCION : COMPRIME. C FECHA : 28/10/1990 DESCRIPCION : Funcion que comprime el archivo de entrada utilizando
tecnica RLE.
#include <stdio.h> #include <mem.h > #define maxmem 30720 #define maxlong 30725 void comprime(fi,fo) FILE *fi,*fo; { register int i = O ; register int j = O ; register int k; register int 1; int in size,q; unsigned chgr in-str[maxlong], out - str[maxlong]; memset ( in-str , NULL, maxlong) : memset (out-str , NULL, maxlong) ; while ((in-size = fread(in-str,l,maxmem,fi)) != NULL ) {
i = O ; while ( i < in-size )
{ if ( in-str[i] == in str[:i+l] & & in-str[i+l] == in_str[i+2] )
{ -
k = proces-comp(in-str,i,in-size); if ( k+j > maxmem ) {
fwrite(out-str, ij j, :€o) ; memset(out-str,NULL,maxlong); j = O ;
1 out str[j++] = (unsigned char) k I 0x80; outIstr [ j ++ 3 = in-str [ .i 1 ; i += k;
} /* if */ else
{
(Conmtinua ...)
2 '7
LISTADO 3
RUTINA DE COMPACTACION UTILIZANDO LA TECNICA RLE
( VERSION MODIFICADA )
k = proces descomp (in-sstr, i , in-size) ; if ( k+ j >-maxmem ) {
fwrite (out-str , 1 , j , fo) ; memset (out-str , NULL,, maxlong) ; j = O ;
1 out-str[j++] = (unsigned char) k; for ( 1 = 0;l c k;l++) out-str [ j ++] = in-str [ i++] ;
} /* else */ } /* while */ memset (in-str, NULL, maxlong) :
} /* while */ fwrite(out str,l, j,fo) :
} /* compres-*/ /********** preces camp ********:k*/
" . . int proces comp(in-str,i,in-size) unsigned cEar *in-str; int int í
i; in-size;
I
reqister int lon = O ; while ( in-str[ i] == in str[ :i+l] & & i 4
{ -
ion++ ; i++ ; if ( lon == 126 )
break; } /* while */
if ( i >= in-size )
return (lon + 1) ; lon--;
} /* proces-comp */
c in-size )
(continua ...)
2 :B
LISTADO 3
RUTINA DE COMPACTACION u~rILIzmm LA TECNICA RLE
( VERSION MODIFICADA )
int int
i; in-size;
{ reqister int lon = O ; while ((in-str[i] != in str[i+l] I I in-str[i+l] != in_str[i+2]) & &
i < in-size) -
{ ion++ ; i++ ; if ( lon == 127 )
break; }/* while */
) /* proces-descomp */ return (lon) ;
( continua ...)
2 '9
LISTADO 3
RUTINA DE COMPACTACION UTILIZANDO LA TECNICA RLE
( VERSION MODIFICADA )
/*
FUNCION : RESTAURA.C FECHA : 29/10/1990 DESCRIPCION : Funcion que restaura el archivo comprimido mediante la
tecnica RLE.
#include <stdio.h> #include <mem.h > #define maxlong 30725 #define maxmem 30720 #define no-fin 1 void expande(out-str,fi) unsigned char *out-str; FILE *fi; {
register int i= O; register int j I
register long k= O; register int 1 ; unsigned char in-str[maxlong]; int m,resto,in-size; memset (out str, N U L L , maxlong) ; memset (in - str , N U L L , maxlong) ; in-size = fread(in-str,l,maxmem,fi); while ( no-fin ) {
j = in-str[ i++] ; if ( j > 128) {
if ((j - 128) + k > maxlmem) { fwrite(out str, 1, :k, fo); memset (outIstr, NUL:L, maxlong) ; k = O ;
1
(Continua ...)
30
LISTADO 3
RUTINA DE COMPACTACION U ~ r I L I z m m LA TECNICA RLE
( VERSION MODIFICADA )
if ( i >= in-size ) { memset(in str, NULL, maxlong); if ((in size = fread(in-str, 1, maxmem, fi)) == NULL ) (
fwrite(out-str,, l,k, fo) ; memset (out-str ,, NULL, maxlong) ; break;
} /* if */ i = o;
for (j -= 128; j>O; j--)
i++ ; out-str[k++] = in-str[i] ;
} /* if */ else { 1 = O ;
if ( (j+k) > mamem ) ( fwrite(out-str, 1, k, fo); memset (out - str, NULL, maxlong) ; k = O ;
1 if ((j+i) >= in si:ze) (
resto = in size - i; for (1 = 07 1 .c resto ; 1++)
memset (in str, NULL, maxlong) ; if ((in-size = fread(in-str, 1, maxmem, fi)) == NULL)(
fwrite(out-str, l,k, fo) ; memset (out-str, NULL, maxlong) ; break;
out str[k+-t] = in-str[i++];
} / * if */ i = O ;
for (m = O ; m < (:j-l); m++) out-str[k++] := in-str[i++];
1 1 /* while */
} /* restaura */
3 1
146242
DIBUJO DE FRACTALES Una vez resuelto el problema de compactacion y recuperación de
imágenes, el siguiente paso es e1 dibujo de los fractales, para
lo cual se requiere de un algoritmo capaz de expander el
codigo de la imagen comprimida y generar con ella el dibujo del
fractal correspondiente.
FUNCIONAMIENTO DEL ALGORITMO
La primera aproximacion rea:Lizada se basa en un buffer de
entrada que toma fragmentos de 3 2 kb del archivo comprimido, para
ser expandido en memoria en un buffer de salida de hasta 64 kb, misma que es enviada a una rutina que envía cada caracter de
entrada a una determinada posicion de la pantalla, el algoritmo
implementado en lenguaje "C" se ]nuestra en el LISTADO 4 .
3 :2
LISTADO 4
PROGRAMA DE GENERACION Y DIBUJO DE FRACTALES
#include <mem.h > #include <stdio.h > #include <string.h > #include <graph.h> #define MaxCol 639 #define MaxRen 479 #define delta 4 #define cierto 1 #define falso O #define maxlong 30725 #define minlong 1445 #define maxmem 30720 #define minmem 1440 #define no-fin 1 double AspectRatio; / I* Relacion de pixel's en la pantalla int GraphDriver; / I* Manejador de Dispositivo Grafico int GraphMode ; / I* Valor de Modo Grafico int MaxX, MaxY; / I* La maxima resolucion del monitor int MaxColors; Maximo Numero de Colores Disponibles int Errorcode; / I* Reporta algun error grafico void Inicio ( ) ; void Mandelbrot(F1LE *fi); struct palettetype palette; struct st-rgb{int rojo ,verde,azul;) color , colores[l5]; unsigned char in-str[maxlong];
int i = O ; int primero = 1; int in-size;
main ( ) { FILE *fopen() *fi; int x[250] ; int x1,x2,r,g,bfifj,k; char entrada[l3Ifop = I s ! ;
(Continua ...)
3 3
.
LISTADO 4
PROGRAMA DE GENERACION Y DIBUJO DE FRACTALES
while ( op != Inv clrscr ( ) ; gotoxy (20,12) ; printf ("NOMBRE DEL FRACTAL A DIBUJAR : \n*l) ; gotoxy (53,12) ; gets (entrada) ; fi = fopen(entrada,gfrbll) ; if ( fi == NULL ) {
gotoxy (15,12) ; printf("***** NO PUEDO ABRIR EL ARCHIVO < %S > *****\nIl,entrada); sleep ( 3 ) ; continue;
} /* if */ Inicio ( ) ;
/* setallpalette (&palette) ; */ Mandelbrot (f i) ;
fclose (f i) ; closegraph ( ) ; clrscr ( 1 ;
/* delay (5000) ; */
gotoxy(20,l2) ; printf ("DESEAS DIBUJAR OTRO FRACTAL ? : \nl11 ; . . - ¿Jotoxy(53,12) ; op = getch() ;
} /* while */ clrscr ( ) ; return ( O ) ;
} /* main */ void Inicio ( ) {
int xasp, yasp,modo; /* Used to read the aspect ra while ( !-setvideomode(modo) ) /* Modalidad de auto-deteccio
modo --; /* inicializa el modo Grafico /* Lee el resultado de la ini if ( modo <= O ) { /* Ocurre un error durante la printf (Ig Error al inicializar modo Grafico \rill) ; sleep (2) ; exit( 1 ) ;
1
LISTADO 4
PROGRAMA DE GENERACION Y DIBUJO DE FRACTALES
void Mandelbrot (f i) FILE *fi;
register int l,j,ap; int 1onqltud.tint: unsigned char ou6_str~minlÓng] ;
memset(out-str,NULL,minlong); memset (in-str , NULL,maxlong) ; longitud = expande (out-str, f i) ; aP = o ; for ( j=o ; j <= MaxCol ;j++) (
if ( ap == longitud ) { for ( 1=0 ; 1 <= MaxRen ; l++) (
longitud = expande(out"str, fi) ; ap = O ;
1 if (out_str[ap]%31 <= 15)
else
- setcolor (tint) ; - setpixel (j ,MaxRen-1) ; ap ++;
tint = out-str[ap]%l€i;
tint = 30 - (out-str[ap]%30);
} /* for */ } /* for */
} /* mandelbrot */
(Continua. . . )
35
LISTADO 4
PROGRAMA DE GENERACION Y DIBUJO DE FRACTALES
int expande(out-str,fi) unsigned char *out-str; FILE *fi; {
register int j ; register long k= O ; register int 1 ; int m, resto; if ( primero == cierto ) {
} /* if */ while ( no fin ) { j = in-sEr[i++] ; if ( j > 128) {
inTsize = fread(in-str,l,maxmem,fi); primero = falso;
if ((j - 128) + k >= minmem) { /* se lleno el buffer de salida i return (k) ;
} / * if */ if ( i >= in-size ) { /* se termino el fubber de entrad
in-str[O] = ' \ O 1 ; if ((in-size = fread(in - str, 1, maxmem, fi)) == NULL )
i = O ; return ( O ) ;
1 for (j -= 128; j>O;.j--;)
i++ ; out-str [ k++] = in-str [ i] ;
} / * if */ else {
1 = o ; if ( (j+k) >= minmem ) { /* se lleno el buffer de salida */
} /* if */ if ((j+i) >= in size) { /* se termino el buffer de entrada */
i return (k) ;
resto = in-size - i; for (1 = O ; 1 < resto ; 1++)
in str[~] = I \ o ~ ;
if-((in size = fread(in-str, 1, maxmem, fi)) == NULL)
i = O ;
out-str [ k++] = in"str [ i++] ;
breax;
for (m = O ; m < (j-1); m++) out-str[k++] = in-str[i++];
} /* else */ } /* while */
) /* expande */
Despues de analizar este algoritmo, se encuentra que resuelve
de manera satisfactoria el problema, sin embargo, el tiempo que
tarda en la decodificacion del codigo de repetición es bastante
considerable, por lo tanto, se realizó un algoritmo capaz de
decodificar los caracteres comprimidos de manera directa, es
decir, sin nesecidad de expander el buffer, el algoritmo
modificado es el que se muestra en el listado 5
3 '7
LISTADO 5
PROGRAMA DE GENERACION Y DIBUJO DE FRACTALES
#include <stdio.h> #include <string.h> #include <graphics.h> #define MaxCol 639 #define MaxRen 479 #define delta 4 double AspectRatio; ,/* Relacion de pixel's en la pantalla int GraphDriver; ,/* Manejador de Dispositivo Grafico int GraphMode ; ,I* Valor de Modo Grafico int MaxX, MaxY; ,I* La maxima resolucion del monitor int MaxColors; ,/* Maximo Numero de Colores Disponibles int Errorcode; ,/* Reporta algun error grafico void Inicio ( ) ; void Mandelbroot (FILE *f i) ; struct palettetype palette; struct st-rgb{int rojo ,verde,azul;} color , colores[15];
main ( ) { FILE *fopen() ,*fi; int xr2501 ; int xi,x2;r,g,b,i,j,k; char entrada[l3];
clrscr ( ) ; gotoxy(20,12) ; printf ("NOMBRE DEL FRACTAL A DIBUJAR : \nit) ; gotoxy (53,12) ; gets (entrada) ; f i = f open (entrada, IlrblI) ; if ( fi == NULL ) {
gotoxy (15,12) ; printf(Il***** NO PUEDO ABRIR EL ARCHIVO < %S > *****\n",entrada); exit (1) ;
} /* if */
(Continua ...)
3 r3
LISTIIDO 5
PROGRAMA DE GENERACION Y DIBUJO DE FRACTALES
Inicio ( ) ; if( GraphDriver==EGA I I GraphDriver==EGALO I I GraphDriver==VGA )
for (i= O ; i < 16 ; i++ ) { r = g = O ; b = 4*i ; /* k * delta ;*/ colores[i].rojo = r ; colores[i].verde = g; colores[i].azul = b ; setrgbpalette( i + 16 , O , O ,colores[i].azul ) ; palette.colors[i] = i+16;
} /* for */ setallpalette (&palette) ;
Mandelbroot ( f i) ; /* delay (5000) ; */ fclose(fi); closegraph ( ) ; return ( O ) ;
} /* main */
void Inicio ( ) {
int xasp, yasp; /* Used to read the aspect r
GraphDriver = DETECT; /* Modalidad de auto-detecci initgraph( &GraphDriver, &GrapllMode, 1111 ) ;/* inicializa el modo Grafic Errorcode = graphresult ( ) : /* Lee el resultado de la in if( Errorcode != grOk ) { /* Ocurre un error durante 1 printf (I1 Error al inicializar modo Grafico %s\ntl, grapherrormsg( Err exit( 1 ) ;
1
getpalette( &palette ) ; MaxColors = getmaxcolor() + 1;
/* Lee la paleta de la target /* Lee el maximo numero de co MaxX = getmaxx() ; MaxY = getmaxy() ; /* Obtiene el tama$o de la pa getaspectratlo( &xasp, hyasp ) ; /* Obtiene el aspecto del har AspectRatio = (doub1e)xasp / (doub1e)yasp; /* Obten el factor de corre
( Continua ...)
3 !3
L I S T A D O 5
PROGRAMA DE GENERACION Y D I B U J O D E FRACTALES
void Mandelbroot(fi) FILE *fi;
int c,i,j,tint;
for ( j=O ; j $= MaxCol ;j++) {( for ( i=O ; 1 e= MaxRen ;i++) { c = getc(fi); if (c%31 <= 15)
tint = c%16; else
tint = 30 - (c)%30 ; putpixel( j , MaxRen-i ,tint ) ;
} /* for */ } /* for */
} /* mandelbroot */
La implantación de este nuevo algoritmo es bastante eficiente
en cuanto al tiempo de ejecución,, y en terminos generales supera
en velocidad a todos los algoritmos desarrollados hasta el
momento.
En un afan de seguir optimizando el tiempo de ejecución, se
desarrolló un tercer algoritmo, el cuál emplea líneas en el
dibujo del fractal para todas aquellas cadenas de caracteres
repetidos, y puntos para aquellos caracteres únicos, dando como
resultado el programa que se muestra en el listado 6
4 :1
1 4 6 2 4 2
LISTADO 6
PROGRAMA DE GENERACION Y DIBUJO DE FRACTALES
( VERSION DIRECTA IJTILIZANDO LINEAS )
#include <memory.h > #include <stdio.h > #include <string.h > #include <graph.h> #define MaxCol 639 / * 639 */ #define MaxRen 479 #define delta 4 #define cierto 1 #define falso O #define maxlong 5125 / J t 30725 */ #define maxmem 5120 / * 30720 */ #define no fin 1 void Inicio ( ) ; void Mandelbrot (FILE *f i) ; long paleta;
unsigned char in-str[maxlong];
int int
primero = 1; in-size;
main ( ) ( FILE *fopen() ,*fi; int x[250] ; int xl, x2, r,g, b, i, j , k; char entrada[13],op = I s 1 ;
while ( op != In1 ) ( - clearscreen(-GCLEARSCREEN); printf (It NOMBRE DEL FRACTAL A DIBUJAR : It) ; gets (entrada) ; f i = f open (entrada, rlrba) ; if ( fi == NULL ) {
} /* if */ printf ( CUAL ES LA PALETA QUE DESEA ? : It) ; scanf ( ll%dlt, &paleta) ; Inicio ( ) ;
printf (I1***** NO PUEDO ABRIR EL ARCHIVO < %S > *****\nIl,entrada) ; continue;
(continua ...)
LISTADO 6
PROGRAMA DE GENERACION Y DIBUJO DE FRACTALES
( VERSION DIRECTA ZJTILIZANDO LINEAS )
Mandelbrot (f i) ;
getch() ; fclose(fi); - setvideomode(-DEFAULTMODE) ; - clearscreen(-GCLEARSCREEN); printf ( DESEAS DIBUJAFI OTRO FRACTAL ? : 'I) ; op = getch() ;
) /* while */ return ( O ) ; - clearscreen ( GCLEARSCREEN) ; -
} /* main */
void Inicio ( ) {
short int modo; /* Used to read the asp
modo =-setvideomode (-MRES4COLOR) ; - selectpalette (paleta) ;
/* Modalidad de auto-deteccio /* Lee el resultado de la ini /* if( modo <= O ) { Ocurre un error durante la
printf (I@ Error al inicializar modo Grafico \ntl) ; exit ( 1 ) ;
*/ 1
(Continua ...)
4 3
LISTADO 6
PROGRAMA DE GENERACION Y DIBUJO DE FRACTALES
( VERSION DIRECTA UTILIZANDO LINEAS )
void Mandelbrot(fi) FILE *fi; {
register int l,jr int inslze,k,m,ap,n; long tint;
setlinestyle(0xFFFF); -" 3 -l=ap=k=O ; memset (in-str,NULL,maxlong) ; in size = fread(in-str,l,maxmem,fi); while ( j <= MaxCol ) {
if ( ap >= in-size ) {
breax:
memset (in str,NULL,maxlong) ; if ( (in size = fread(in1-str,l,maxmem,fi)) == NULL )
ap = O ; } /* if */ k = in-str[ap++]; if ( k > 128 ) { /* dibujar por medio de lineas
k -= 128; if ( ap >= in-size ) { /* se termino el buffer de entr memset ( in str , NULL, ma.xlong) ; if ((in-size = fread(in str,l,maxmem,fi)) == NULL )
ap = O ; } /* if */ if ( in str[ap] % 31 <=: 15 )
tint= in str[ ap] % 16; else
tint = 30 - (in_str[ap]%30); - setcolor (tint) ;
'if ( MaxRen < l+k ) { / * No cabe la linea completa
break: -
-
moveto ( j , MaxRen-1) ; T lineto(j,o); I++; - moveto ( j , MaxRen) ; n = k -(MaxRen-1)-1;
} /* if */ else
- lineto(j,MaxRen-(n-1)); ap++ ; 1 = n;
n = l + k ;
44
LISTADO 6
PROGRAMA DE GENERACION Y DIBUJO DE FRACTALES
( VERSION DIRECTA UTILIZANDO LINEAS )
) /* if */ else{ /* dibujar pixel por pixel
for ( m=l ;m <=k ;m++) { if (1 > MaxRen) { /* se termino la columna
j++; 1 =o;
} / * if */ if ( ap >= in-size ) { /* se termino el buffer de ent
memset ( in str ,I, nlaxmem) ; I
if ((in-size = fread(in-str,l,mamem,fi)) == NULL )
ap = O ; } /* if */ if (in-str[ap] % 31 <= 15 )
tint = in-str[ap] % 1 6 ; else
tint = 30 - (in"str[ap] % 30); - setcolor(tint); - setpixel (j ,MaxRen -m 1) ; 1++ ; ap++ ;
) /* for */ ) /* else */
} /* while */ } /* mandelbrot */
break;
4 5'