Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
biOps: un paquete de procesamiento de
imagenes en R
Matıas BordeseWalter Daniel Alini
Director: Dr. Oscar Humberto Bustos
30 de noviembre de 2007
Facultad de Matematica, Astronomıa y Fısica
Universidad Nacional de Cordoba
“No se que hace, pero esta muy bueno.”
Nicolas Wolovick
Clasificacion:
I.4 Image Processing and Computer Vision
Palabras clave:
R, procesamiento de imagenes, deteccion de bordes, clasificacion, FFT
UNIVERSIDAD NACIONAL DE CORDOBA
Facultad de Matematica, Astronomıa y Fısica
Licenciatura en Ciencias de la Computacion
biOps: un paquete de procesamiento de imagenes en R
por
Matıas Bordese
Walter Daniel Alini
Resumen
El presente trabajo describe un paquete de procesamiento de imagenes realizado en R, un lengua-
je y entorno computacional libres, enfocado en estadıstica y graficos estadısticos. Las distintas
funciones del paquete, denominado biOps, fueron especificadas utilizando la notacion Z -un len-
guaje formal de especificaciones usado para describir y modelar sistemas de computacion- e
implementadas usando R mediante la codificacion e integracion de codigo C.
El paquete se compone de operaciones geometricas, morfologicas, aritmeticas, logicas, de tablas
de reemplazo, de deteccion de bordes y de convolucion. Incluye tambien filtros en el espacio
de frecuencias a partir de la Transformada Rapida de Fourier y metodos no supervisados de
clasificacion de imagenes. Se describen y detallan las implementaciones, sus fundamentos teoricos
y aplicaciones mas frecuentes.
biOps fue liberado bajo licencia libre GPL y aceptado por la comunidad de R para formar parte
de su repositorio oficial de paquetes.
Agradecimientos
Al Dr. Oscar H. Bustos, por la direccion del trabajo.
Al Dr. Pedro R. D’Argenio, por su apoyo, consejos y opiniones.
A la Dra. Laura Alonso y al MSc. Maximiliano Cristia, por su desinteresada colaboracion.
A Kurt Hornik y Uwe Ligges, del R Development Core Team, nuestros R-gurus.
A nuestros familiares y grupo de amigos.
iii
Indice general
Resumen II
Agradecimientos III
Listado de Figuras VII
1. Introduccion 1
2. R 42.1. Antecedente: El lenguaje S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2. R como implementacion de S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3. Interfaz contra lenguajes compilados . . . . . . . . . . . . . . . . . . . . . . . . . 72.4. R puro vs. interfaz C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.5. Colaboracion a CRAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3. Z 123.1. Las especificaciones formales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.2. El lenguaje de especificacion Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.3. Definiciones en Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3.1. Declaraciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.3.2. Abreviaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.3.3. Definiciones axiomaticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.3.4. Definiciones genericas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.3.5. Esquemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.4. fuzz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.5. Especificacion en Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.5.1. Especificacion de reales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.5.2. Resto de las especificaciones . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4. Imagen digital 214.1. Representacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.2. Resolucion espacial y de profundidad . . . . . . . . . . . . . . . . . . . . . . . . . 224.3. Modelos de color . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.3.1. RGB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.3.2. CYM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.3.3. HSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.4. Nuestra implementacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.4.1. Especificacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5. El procesamiento digital de imagenes 275.1. Orıgenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
iv
Indice general v
5.2. Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295.2.1. Astronomıa y exploracion del espacio . . . . . . . . . . . . . . . . . . . . . 295.2.2. Inteligencia y aplicacion militar . . . . . . . . . . . . . . . . . . . . . . . . 295.2.3. Ciencias de la tierra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295.2.4. Gobierno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305.2.5. Visualizacion de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305.2.6. Entretenimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305.2.7. Medicina . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305.2.8. Procesamiento de documentos . . . . . . . . . . . . . . . . . . . . . . . . . 315.2.9. Aplicaciones industriales y vision de maquinas . . . . . . . . . . . . . . . 315.2.10. Aplicaciones hogarenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
6. biOps: un paquete de procesamiento de imagenes para R 326.1. Otros paquetes R de manejo de imagenes . . . . . . . . . . . . . . . . . . . . . . 326.2. Estructura del paquete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336.3. Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346.4. biOpsGUI: el principio de una interfaz grafica de usuario . . . . . . . . . . . . . . 366.5. Proximos capıtulos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366.6. Formato Digital . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
7. Operaciones por pixel 387.1. Look-up tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.1.1. Modificacion de contraste . . . . . . . . . . . . . . . . . . . . . . . . . . . 407.1.2. Modificacion de intensidad . . . . . . . . . . . . . . . . . . . . . . . . . . 417.1.3. Otras modificaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
7.2. Operaciones aritmeticas y logicas . . . . . . . . . . . . . . . . . . . . . . . . . . . 437.3. Histogramas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457.4. Generacion de ruido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
8. Operaciones geometricas 488.1. Mapeo de valores: “hacia adelante” vs. “hacia atras” . . . . . . . . . . . . . . . . 488.2. Interpolacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
8.2.1. Interpolacion por el vecino mas cercano . . . . . . . . . . . . . . . . . . . 498.2.2. Interpolacion bilineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508.2.3. Interpolacion por B-Spline . . . . . . . . . . . . . . . . . . . . . . . . . . . 508.2.4. Interpolacion convolucional cubica . . . . . . . . . . . . . . . . . . . . . . 51
8.3. Operaciones implementadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518.3.1. Escalar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518.3.2. Encoger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528.3.3. Rotar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548.3.4. Espejar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558.3.5. Trasladar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558.3.6. Recortar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
9. Operaciones por vecino 589.1. Convolucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
9.1.1. Blurring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 609.1.2. Sharpening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
9.2. Filtro por mediana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629.3. Filtro por mınimo/maximo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
10.Algoritmos de deteccion de bordes 6410.1. Generalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6410.2. Tecnicas sencillas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Indice general vi
10.3. Tecnicas por convolucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6610.3.1. Deteccion de bordes por gradiente (Gradient Edge Detection) . . . . . . . 6710.3.2. Deteccion de bordes por compas (Compass Edge Detection) . . . . . . . . 68
10.4. Tecnicas avanzadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6910.4.1. Marr Hildreth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7010.4.2. Canny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7010.4.3. Shen Castan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
10.5. Deteccion de bordes en color . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
11.Filtros en el espacio de frecuencias 7411.1. Espacio de frecuencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7411.2. Transformada de Fourier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7511.3. Convolucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7811.4. Filtros por frecuencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
12.Operaciones morfologicas 8212.1. Operaciones sobre imagenes binarias . . . . . . . . . . . . . . . . . . . . . . . . . 82
12.1.1. Dilatacion binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8312.1.2. Erosion binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8512.1.3. Apertura y clausura binarias . . . . . . . . . . . . . . . . . . . . . . . . . 86
12.2. Operaciones sobre imagenes en escala de grises . . . . . . . . . . . . . . . . . . . 88
13.Clasificacion de imagenes 9013.1. Conceptos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9013.2. Clasificacion supervisada y no supervisada . . . . . . . . . . . . . . . . . . . . . . 9113.3. Metodos de clasificacion no supervisados . . . . . . . . . . . . . . . . . . . . . . . 92
13.3.1. K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9313.3.1.1. Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
13.3.2. Isodata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
14.Conclusiones 9914.1. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10014.2. Estadısticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
A. Profiling 103
Bibliografıa 110
Indice de figuras
4.1. Matriz imagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.2. Modelos de color RGB y CYM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.3. Modelo de color HSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.1. Estructura biOps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
7.1. Look-up tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397.2. Decrementar contraste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407.3. Incrementar contraste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417.4. Decrementar intensidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427.5. Incrementar intensidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427.6. Negativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427.7. Thresholding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437.8. Transformacion Gamma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437.9. Aplicacion de imgDiffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457.10. Histograma de una imagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457.11. Ruido “sal y pimienta” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
8.1. Rotacion de imagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548.2. Operacion de espejado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558.3. Operacion de traslacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
9.1. Convolucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599.2. Aplicacion de sharpening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 619.3. Aplicacion de filtro por mediana . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
10.1. Operador de homogeneidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6510.2. Operador por diferencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6510.3. Aplicacion de operador por diferencia . . . . . . . . . . . . . . . . . . . . . . . . 6610.4. Borde y derivadas en una dimension . . . . . . . . . . . . . . . . . . . . . . . . . 6610.5. Aplicacion de Sobel (threshold = 40, negativo) . . . . . . . . . . . . . . . . . . . 6810.6. Aplicacion de Canny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
11.1. Transformada de Fourier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7811.2. Filtros FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7911.3. Filtro por frecuencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
12.1. Representacion grafica de una imagen binaria . . . . . . . . . . . . . . . . . . . . 8312.2. Dilatacion binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8412.3. Dilatacion binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8512.4. Erosion binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8612.5. Erosion binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8612.6. Apertura y clausura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
vii
List of Figures viii
13.1. Clasificacion por k-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9413.2. Kd-tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9513.3. Nearest Neighbor Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Capıtulo 1
Introduccion
El procesamiento digital es el conjunto de tecnicas computacionales que se aplican sobre las
imagenes con el objetivo de mejorar la calidad, alterar su morfologıa, facilitar su interpretacion o
proporcionar herramientas para la busqueda de informacion. Aparece tardıamente en la historia
de la computacion, debido a los requisitos de hardware y los sistemas graficos que permitieran
desarrollarla. El abaratamiento de los costos y la evolucion de los equipos le dio un fuerte impulso
en los ultimos tiempos.
En la actualidad existen muchas aplicaciones de software que permiten el procesamiento digital
de imagenes, ası como librerıas para los diferentes lenguajes de programacion. R, un lenguaje
libre destinado principalmente al analisis estadıstico de datos, es quiza una excepcion a la regla.
Las alternativas que se presentan para el manejo multiproposito de imagenes son escasas.
La posibilidad de integrar funcionalidad para el procesamiento de imagenes en un entorno es-
tadıstico, libre y con una comunidad muy bien organizada y en constante crecimiento, sumado
a las ventajas que suponen las utilidades estadısticas (calculo de medias, desviaciones, histogra-
mas), nos impulsaron a la realizacion de este proyecto. El objetivo fue, entonces, el de investigar,
estudiar, especificar e implementar un conjunto de algoritmos para R, que provea un entorno
funcional, util y general para el procesamiento de imagenes, colaborando con la comunidad de
Software Libre, es decir, permitiendo de esta forma su libre uso y modificacion.
Presentamos en este escrito el resumen de varios meses de trabajo. Intentamos ser precisos al
introducir los conceptos manejados, para que el lector tenga una buena lectura preparatoria, y
analizar en detalle las especificaciones, utilidades e implementaciones de los algoritmos elegidos
para formar parte del paquete.
Se realizo el estudio, analisis, especificacion, implementacion y testeo de tecnicas para el manejo
de imagenes, que concluyeron con la creacion y publicacion de un paquete R, denominado biOps,
liberado bajo la licencia GPL y que se encuentra disponible en el repositorio oficial de paquetes
del lenguaje R. Ademas se comenzo con el trabajo de una interfaz grafica de usuario, biOpsGUI,
para brindar una mejor experiencia de usuario.
1
Capıtulo 1. Introduccion 2
Creemos que el paquete obtenido es una importante colaboracion con la comunidad R, que no
contaba con paquetes multiproposito de importancia en el procesamiento de imagenes. biOps, en
este sentido, resulta de gran utilidad, facilmente extensible y con una amplia gama de algoritmos.
Consideramos que los trabajos futuros para la mejora del paquete debieran considerar la exten-
sion de la interfaz grafica, diversificar los formatos de imagen soportados, reconsiderar el manejo
en memoria de la representacion de imagenes y anadir algoritmos para ampliar su utilidad (al-
goritmos supervisados de clasificacion de imagenes, filtros, reconocimiento de patrones, machine
vision, etc.).
Estructura de este trabajo
Este texto se compone de dos partes principales: los capıtulos 2 al 5 introducen conceptos re-
lacionados a las etapas previas a la codificacion. Se presentan la notacion Z, lenguaje utilizado
para las especificaciones formales en este trabajo, y el lenguaje R, sobre el cual se implementaron
los algoritmos estudiados. Se desarrollan ademas, los conceptos relacionados con imagenes, sus
representaciones, modelos de color y los usos en las diversas areas de aplicacion. El capıtulo 6
presenta una descripcion de las secciones posteriores (capıtulos 7 al 13), en los cuales se profun-
dizan los conceptos, utilidades, especificacion e implementacion correspondientes a cada una de
las divisiones del paquete.
Para una vision global de este trabajo, recomendamos la lectura de los capıtulos 1 (esta In-
troduccion), 6 (descripcion del paquete, contenidos del trabajo y capıtulos posteriores) y 14
(recapitulacion, evaluacion, conclusiones y desafıos para el trabajo futuro). Quien desee profun-
dizar acerca de los lenguajes y notaciones utilizados, puede concentrarse en los capıtulos 2 (el
lenguaje R, y sus interfaz con el lenguaje C) y 3 (la notacion Z, de especificacion de modelos
de sistemas computacionales). A los interesados en conceptos o implementaciones en una deter-
minada rama del procesamiento digital de imagenes que hayan sido tratados en este trabajo,
sugerimos la lectura del capıtulo correspondiente.
A continuacion se presenta un breve resumen del contenido de los capıtulos de este trabajo:
R [Cap. 2]: R es un lenguaje interpretado, de scripting, y un conjunto de librerıas destinadas
principalmente al analisis estadıstico de datos. El “Comprehensive R Archive Network” es
una red de sitios con las librerıas que estan disponibles para el uso en R. Se realiza una
breve descripcion del lenguaje, sus procedimientos para colaborar con su comunidad, su
red de archivos y las interfaces para comunicarlo con otros lenguajes de programacion. Se
comparan ademas algoritmos codificados en R y en C (mediante interfaz en R).
Z [Cap. 3]: Z es el nombre de la notacion que utilizamos para la especificacion de nuestro traba-
jo. Se presentan los conceptos basicos, definiciones de objetos necesarios para comprender
esta notacion e implementacion de los algoritmos del paquete y de una representacion de los
numeros reales, basado esto ultimo en la publicacion de R. D. Arthan [Art96]. Se menciona
tambien a fuzz, con el cual realizamos la verificacion de tipos de estas especificaciones.
Capıtulo 1. Introduccion 3
Imagen digital [Cap. 4]: Se presentan los conceptos necesarios para comprender la represen-
tacion computacional de imagenes: la resolucion espacial y de profundidad (detalles en una
imagen) y los modelos de color mas conocidos (RGB, CYM y HSI). Se detalla ademas la
representacion elegida para este trabajo e implementacion para la obtencion de imagenes
mediante R.
Procesamiento digital de imagenes [Cap. 5]: El procesamiento de imagenes es una rama
que data de principios de siglo pasado. Se relata su origen y las principales aplicaciones en
las diversas areas donde es utilizado.
biOps: un paquete de procesamiento de imagenes en R [Cap. 6]: biOps es el nombre
del paquete que desarrollamos y que se encuentra publicado en el repositorio oficial de
paquetes R. Se detallan estructura, componentes y el comienzo de la implementacion de su
interfaz grafica: biOpsGUI. Tambien se presenta una comparacion contra otros paquetes R
de manejo de imagenes y una vision global de los capıtulos posteriores:
Operaciones por pixel [Cap. 7]: Algoritmos de “tabla de reemplazos”, operaciones
aritmeticas, logicas, de representacion grafica (histogramas) y generacion de ruidos.
Operaciones geometricas [Cap. 8]: Operaciones de rotacion, escalado, espejado,
crop, shrink y traslacion. Ademas, diversas formas de interpolacion (vecino mas cer-
cano, bilineal, cubica y por spline).
Operaciones por vecino [Cap. 9]: Concepto de convolucion y aplicacion de filtros
lineales y no lineales.
Algoritmos de deteccion de bordes [Cap. 10]: Algoritmos sencillos y rapidos
(homogeneidad y diferencia), metodos basados en convolucion (Sobel, Prewitt, Roberts,
etc.) y algunas tecnicas avanzadas (Shen Castan, Marr Hildreth, etc.).
Filtros en el espacio de frecuencias [Cap. 11]: Filtros mediante la transformada
rapida de Fourier.
Operaciones morfologicas [Cap. 12]: Operaciones para imagenes binarias y de
escala de grises, de erosion, dilatacion y sus combinaciones: apertura y clausura.
Clasificacion de imagenes [Cap. 13]: Se dividen en algoritmos supervisados y no
supervisados. Se detallan Isodata y K-Means (no supervisados).
Conclusiones [Cap. 14]: Una recapitulacion, evaluacion de herramientas y breve comenta-
rio de lo realizado. Se incluyen algunas estadısticas y los trabajos futuros que a nuestro
entender deberıan ser prioritarios para mejorar el paquete.
Capıtulo 2
R
R es un lenguaje interpretado, de scripting, y un conjunto de librerıas destinadas principalmente
al analisis estadıstico de datos. Es una implementacion libre del lenguaje estadıstico S , creado
a mediados de la decada del ’70 por los Laboratorios Bell, aunque se ve influenciado tambien
por el lenguaje Scheme. Se distribuye sin costo y bajo la licencia GPL, y es el lenguaje sobre el
cual se ha llevado a cabo la implementacion de los diversos algoritmos que forman parte de este
trabajo. R esta construido principalmente sobre el lenguaje de programacion C , aunque mucha
funcionalidad esta escrita en R mismo. Ademas puede integrarse con otros lenguajes mediante
el uso de funciones especıficas, lo que nos permite una diversidad de opciones a la hora de tomar
decisiones de implementacion. Se codificaron algunos algoritmos, objeto de este trabajo, tanto
con acceso a codigo realizado en C como a uso explıcito de este lenguaje, y se compararon los
datos de eficiencia mediante algunas herramientas de profiling . La gran diferencia encontrada a
favor de las implementaciones con llamadas a codigo C , cuyas causas se mencionan, influencio en
su mayor uso en el resto de los algoritmos.
El “Comprehensive R Archive Network” es una red de sitios con las librerıas que estan disponibles
para el uso en R. Para colaborar con CRAN es necesario cumplir con una serie de requisitos que
hacen que los paquetes puedan funcionar correctamente y estar documentados de una manera
homogenea.
La comunidad R, en constante crecimiento, ha realizado diversas herramientas y comandos para
aliviar la tarea de los programadores que deseen colaborar con el proyecto. Entre ellas estan los
comandos check y build , que se explican brevemente.
2.1. Antecedente: El lenguaje S
Desde la segunda parte del siglo XX, y gracias al incremento del poder de calculo de la compu-
tacion, la estadıstica se ha visto sustancialmente impactada. Este impacto ha traıdo dos con-
secuencias fundamentales: por un lado, la automatizacion del calculo para los viejos metodos
estadısticos; y por el otro, el resurgimiento del interes en metodos menos estudiados, como los
4
Capıtulo 2. R 5
no lineales, encabezados por las redes neuronales y los arboles de decision. La abundancia en
recursos ha causado tambien el renacer de nuevos modelos lineales descartados con anterioridad.
Alrededor del ano 1980 comienzan a surgir los lenguajes de programacion especializados en
analisis estadısticos. Hoy en dıa hay tantos como programadores emprendedores hubo en las
ultimas decadas.
Entre los lenguajes que mas popularidad han logrado, se encuentra S . La historia de este lenguaje
se remonta a mediados de los ’70, en los Laboratorios Bell. Hasta ese entonces, mucho de los
investigadores se valıan de librerıas del lenguaje Fortran (acronimo de Formula Translator) para
realizar sus calculos, sobre todo la librerıa SCS (Statistical Computing Subroutines), rutinas
que se extendıan segun las necesidades. El impulso a realizar calculos mas simplistas que los que
proponıa esta librerıa, sumado a la paulatina disminucion de codigo Fortran necesario para los
calculos, hacen que Rick Becker, Allan Wilks y John Chambers comiencen el desarrollo de S
como una unidad independente.
S no fue el primer lenguaje con funcionalidad estadıstica realizado por los Laboratorios Bell, pero
sı el primero en ser implementado. La primera implementacion data del 1976 y funcionaba sobre
el sistema operativo GCOS (General Comprehensive Operating System). El nombre ’S’ (escrito
en un principio ası, con comillas simples) fue elegido por ser esta letra comunmente usada en
computacion estadıstica, siendo consistente con otros lenguajes de programacion desarrollados
en la misma institucion (lease el lenguaje de programacion C , de uso frecuente en nuestros dıas).
Tras una mutacion no demasiado importante que hizo que pudiera empezar a utilizarse en el sis-
tema operativo UNIX , por el ano 1988, S sufre una serie de cambios de peso (en implementacion
y, sobre todo, en sintaxis) y en 1991 se introduce el concepto de notacion de formulas.
Este “nuevo” lenguaje es bastante parecido a las implementaciones actuales: S − Plus (version
comercial de S , tambien conocida como S+), desarrollado por la empresa Insightful , y R (version
libre), objeto de nuestro estudio, y en el cual centraremos toda la atencion.
R tambien fue influenciado, sobre todo en lo que se refiere a implementacion subyacente y
semantica, por el lenguaje Scheme1, desarrollado por Guy L. Steele y Gerald Jay Sussman en
los anos ’70.
Actualmente, ademas de S − Plus2 existen otras alternativas comerciales, que si bien no son
objeto de estudio en este trabajo, vale la pena mencionarlas: SAS 3, Minitab4 y SPSS 5.
2.2. R como implementacion de S
La primera implementacion de S como proyecto de software libre fue disenada por Ross Ihaka
y Robert Gentleman en el Departamento de Estadısticas de la Universidad de Aukland, Nueva1http://www.schemers.org2http://www.insightful.com/products/splus3http://www.sas.com4http://www.minitab.com5http://www.spss.com
Capıtulo 2. R 6
Zelanda. Le llamaron R, que surge por un juego con S , principal antecesor, y el primer nombre
de ambos autores.
Un gran grupo de personas han contribuido con el desarrollo de R mediante el aporte de codigo y
reportes de bugs desde su creacion. Hacia mediados de 1997 se creo un grupo de desarrolladores
con permisos de modificacion de las fuentes de R, el “R Core Team”, que se compone actualmente
de 17 personas, entre ellas sus primeros programadores Ihaka y Gentleman.
R es, en pocas palabras, la suma de un lenguaje de scripting, un interprete y un conjunto muy
completo de modulos built-in para el manejo de datos y trabajos estadısticos. Consta de dos
componentes principales: el lenguaje propiamente dicho y el interprete, con los cuales se puede
manejar graficos, efectuar tareas de depuracion y debugging, ası como tambien acceder a algunas
funciones del sistema y correr scripts desde codigo guardado en archivos.
R integra programas para la manipulacion de datos, calculo y graficos. Dispone de una gran
cantidad de librerıas, con un fuerte hincapie en el manejo de datos y funcionalidades estadısticas.
Cuenta ademas con:
Almacenamiento y manipulacion eficaz de datos
Operadores para variables indexadas, en particular matrices (y arreglos, es decir, matrices
unidimensionales)
Una amplia coleccion integrada de herramientas para el analisis de datos
Funcionalidad de impresion grafica en pantalla o impresora
El lenguaje de programacion incluye condicionales, ciclos, funciones recursivas y de entrada/sa-
lida. Muchas de las funcionalidades que provee estan escritas en R mismo, si bien gran parte de
las librerıas basicas estan escritas en C .
R puede integrarse con distintas bases de datos y existen librerıas que facilitan su utilizacion
desde lenguajes de programacion interpretados (como Perl y Python) o desde lenguajes de codigo
compilado (como C , C + + y Fortran), como veremos mas adelante para el caso particular que
nos interesa. La lista de los lenguajes en los cuales pueden agregarse funcionalidad esta creciendo
con el correr del tiempo, a medida que estos aumentan en eficiencia o popularidad, y a medida
que R crece como utilidad para el usuario.
Una amplia coleccion de librerıas se encuentran en CRAN 6 (Comprehensive R Archive Network),
una red de sitios que cuentan con identico contenido (mirrors), tanto de codigo como de docu-
mentacion y de archivos binarios, y que mantienen la informacion que rodea a R actualizada
y a disposicion de toda la comunidad. En CRAN se mantienen, tambien, una lista de correo
electronico y un sistema de seguimientos de bugs.
R se utiliza mucho en la investigacion biomedica, la bioinformatica y la matematica financiera.
Los proyectos mas conocidos basados en R son Bioconductor7, destinado al analisis de datos en6http://cran.r-project.org7http://www.bioconductor.org
Capıtulo 2. R 7
genetica y biologıa molecular, y Rmetrics8, dedicado al analisis de tecnicas de mercadotecnia y
evaluacion de instrumentos financieros.
R se distribuye bajo la licencia GNU GPL y esta disponible para la mayorıa de los sistemas
operativos existentes (incluidas excentricidades como adaptaciones para funcionar en la consola
PlayStation2 y otras)
R tiene su propio formato de documentacion, similar al reconocido LATEX. Esta documentacion
es obligatoria para la aceptacion de paquetes en CRAN , lo que hace que los agregados tengan
la chance de ofrecer documentacion comprensible en varios formatos.
La distribucion de R cuenta con muchos procedimientos con fines estadısticos, entre los que se en-
cuentran: modelos lineales y generalizados, modelos de regresion no lineales y analisis de tiempos
de series, asi como tambien funcionalidad de graficos y representaciones de datos. Es relativa-
mente sencillo agregar nuevas utilidades, mediante lo que se denominan “add-on”s, modulos de
propositos especıficos.
2.3. Interfaz contra lenguajes compilados
R nos ofrece la posibilidad de acceder a codigo compilado que haya sido linkeado previamente.
Este link se puede realizar en tiempo de creacion del modulo o bien dinamicamente mediante
la funcion dyn.load . A traves de la funcion .C se genera una interfaz a codigo compilado en C
o C + +. Los argumentos que se le pasan a esta funcion son generalmente copiados antes de la
ejecucion del codigo, y tambien son copiados a una lista de argumentos en R cuando la funcion a
la cual accedemos ha retornado su valor. Los argumentos pueden pasarse con nombre, de forma
tal de tener un facil acceso a ellos en su posterior manejo. R tiene un mecanismo de pasajes de
parametros por defecto que transforma cada tipo del codigo en un tipo del codigo C . La lista de
tipos para los cuales R conoce mecanismos de transformacion es acotada, pero puede extenderse,
en caso de requerirse, de una manera sencilla. Para este ultimo caso, es preferible el uso de otras
funciones de ejecucion de codigo compilado. La funcion .Call es la que se utiliza generalmente,
y que da un mecanismo para pasar directamente a C algunos tipos mas complejos de R como
las listas. En el caso del lenguaje C , de interes para este trabajo, podemos ver en la siguiente
tabla la tranformacion que sufren los principales modos de almacenamiento:
Mapeo de tipos
R C
logical int∗integer int∗double double∗complex Rcomplex∗character char ∗ ∗raw char∗
8http://www.itp.phys.ethz.ch/econophysics/R
Capıtulo 2. R 8
Con type∗ se denota al puntero a type, es decir, la direccion de memoria de una variable de tipo
type. Rcomplex se refiere a una estructura en C incluida en los archivos de cabecera que provee
el lenguaje R.
2.4. R puro vs. interfaz C
La facilidad que presenta R de escribir add − ons en otros lenguajes (nombrados de forma breve
anteriormente) se enfrenta con las ventajas que encuentran algunos desarrolladores de basar sus
modulos sin la intervencion explıcita de otros lenguajes. La mayor parte de las librerıas de R
estan escritas en C , por la indiscutible eficiencia de este lenguaje.
Existe una forma de generar un analisis estadıstico de un script en R que muestre el uso de
procesador y el porcentaje de tiempo de ejecucion que cada parte del script ha utilizado. Lo
anterior es mucho mas facil de decir en ingles, para lo cual tenemos una palabra que lo expresa:
profiling .
Para hacer profiling en R puede llamarse a la funcion Rprof , entre cuyos argumentos se encuen-
tran el tiempo (medido en segundos) a esperar para hacer un muestreo del stack del proceso (en
general, este numero debe ser cercano a 15/20 milisegundos, ya que un numero menor harıa que
el tiempo necesario para recolectar la informacion se vea superpuesto con la siguiente consulta al
stack, y un numero mayor perjudicarıa la precision del analisis), y el nombre del archivo en el cual
(sobre)escribir la informacion recolectada. De esta manera, si bien el script que se esta corriendo
baja un poco su performance, es posible identificar las partes en que la ejecucion ha invertido
mas o menos tiempo. Los mecanismos que se usan para el profiling son los mismos que usa el
lenguaje C, con lo que estas herramientas no pueden usarse conjuntamente.
Los test para Windows y sistemas operativos UNIX puede que arrojen resultados distintos,
puesto que el intervalo fijo que se establece para el muestreo del stack corresponde a uso del
tiempo del CPU en UNIX , y simplemente tiempo nominal en Windows. Sin embargo, ante igual
carga de CPU, los resultados no deberıan variar para los distintos sistemas operativos.
La funcion Rprof consulta el estado de la ejecucion periodicamente y escribe en el archivo
indicado el estado encontrado. El archivo generado puede tratarse de varias formas. Entre las
que nos ofrece la distribucion de R se encuentran:
Mediante un script en Perl (comando de R) llamado tambien Rprof .
Una funcion del lenguaje llamada summaryRprof que devuelve un objeto en R que puede
ser analizado.
Este tipo de analisis se utilizan para identificar “cuellos de botella” o partes de codigo en R que
pueda ser beneficioso reemplazar por codigo compilado. Para que los resultados sean provechosos,
es necesario que las corridas sean lo suficientemente grandes como para que el tiempo en que el
lenguaje realiza garbage collections sean depreciables; caso contrario es posible que encontremos
resultados que no sean demostrativos para la experiencia que realizamos.
Capıtulo 2. R 9
La bibliografıa consultada es redundante en cuanto a la mayor eficiencia de las implementaciones
en codigo compilado en C contra las implementaciones puras en el lenguaje R. Sin embargo,
parte de nuestro interes era comparar cuantitativamente estas diferencias para algunos casos de
nuestro proyecto, de forma tal de tomar una decision al respecto basada en la aplicacion directa
de nuestras implementaciones.
Para ello, codificamos una seleccion de algoritmos tanto con acceso a codigo C como sin el
(y aquı hablamos de “sin acceso explıcito”), para realizar luego un analisis con la herramienta
anteriormente mencionada.
A continuacion se muestran los resultados obtenidos para un algoritmo de Look-up tables (de-
crementar contraste, funcion imgDecreaseContrast), que se detallan en 7.1.1, y, para uno de
operaciones aritmeticas (diferencia de imagenes, funcion imgDiffer), detallados en 7.2. El resto
de los resultados pueden encontrarse en el Apendice A:
r_dec_contrast vs. imgDecreaseContrast
Each sample represents 0.15 seconds.
Total run time: 1977.90000000047 seconds.
Total seconds: time spent in function and callees.
Self seconds: time spent in function alone.
% total % self
total seconds self seconds name
99.79 1973.70 0.00 0.00 "r_dec_contrast"
99.78 1973.55 48.40 957.30 "r_look_up_table"
...
0.21 4.20 0.00 0.00 "imgDecreaseContrast"
0.21 4.20 0.00 0.00 ".imgContrast"
...
0.06 1.20 0.06 1.20 ".C"
...
% self % total
self seconds total seconds name
48.40 957.30 99.78 1973.55 "r_look_up_table"
...
0.06 1.20 0.06 1.20 ".C"
0.05 0.90 0.05 0.90 "as.vector"
...
r_imgDiffer vs. imgDiffer
Each sample represents 0.15 seconds.
Total run time: 3592.50000000145 seconds.
Total seconds: time spent in function and callees.
Self seconds: time spent in function alone.
% total % self
total seconds self seconds name
99.61 3578.40 53.47 1920.90 "r_imgDiffer"
...
0.39 14.10 0.00 0.00 ".imgArithmeticOperator"
0.39 14.10 0.00 0.00 "imgDiffer"
0.29 10.35 0.29 10.35 ".C"
...
% self % total
self seconds total seconds name
Capıtulo 2. R 10
53.47 1920.90 99.61 3578.40 "r_imgDiffer"
...
0.29 10.35 0.29 10.35 ".C"
0.25 9.00 0.25 9.00 ":"
...
En el primero de los listados de estos resultados se encuentran las funciones llamadas en la
ejecucion, ordenadas por el porcentaje de tiempo ocupado dentro de cada una (y de aquellas a
las cuales ha llamado). El segundo listado corresponde al orden segun el porcentaje del tiempo
ocupado solo por la funcion (y no por las llamadas anidadas).
Notamos para el caso de la funcion de decrementar contraste (r dec contrast vs. imgDecreaseContrast)
que la relacion de uso de CPU fue de aproximadamente 475 a 1 (475.1904) y para la funcion de
diferencia de imagenes (r imgDiffer vs. imgDiffer) fue de 255 (255.4102) a 1, en ambos casos a
favor de las implementaciones con acceso a codigo C.
No resta demasiado analisis por hacer. Lo que valdrıa preguntarse es el por que de semejante
diferencia. La respuesta puede buscarse de entre las siguientes justificaciones:
Lo principal es recordar que C es un lenguaje compilado y R uno interpretado, con lo
que hay una capa de abstraccion (al menos) de diferencia. Ademas, muchas de las optimi-
zaciones a codigo fuente que hacen los codigos compilados se pierden para el caso de los
interpretados.
Las funciones de acceso a algunas estructuras de datos en R verifican ciertas condiciones
(como la validez del lugar de memoria a acceder), lo cual hace que las estructuras de R
subyacentes (implementadas en C ) sean mas complejas y tengan chequeos que no nos eran
necesarios realizar en nuestro codigo C (esto hace a R un lenguaje mas robusto que C ,
pagando el precio de la eficiencia).
El uso, en algunos casos, de funciones no del todo adecuadas pero que se pegaban mas a
las especificaciones de los algoritmos. Por caso, en las look-up tables, se usa una estructura
de memoria contigua (tal como lo describen los algoritmos). Sin embargo, esta razon no es
del todo valida: una evaluacion para estos casos (cambiando es uso de memoria contigua
por las funciones mapply y el uso de funciones en los parametros) arrojo, para el caso de
decrementar contraste, una relacion de 433.78 a 1. Es decir, del mismo orden de magnitud
que las pruebas anteriores.
2.5. Colaboracion a CRAN
La colaboracion con la comunidad R puede hacerse de diversas formas. Existen sistemas de bug-
tracking, para el reporte y discusion de bugs, manejo de versiones, utilidades diversas como de
testeo de nuevos paquetes, interfaz de interprete por web y un largo etcetera. La comunidad
R crece a un ritmo sorprendente, y es uno de los mejores ejemplos de como la colaboracion de
anonimos puede hacer crecer el software libre muy por encima de los programas de software
privativo.
Capıtulo 2. R 11
CRAN (explicado brevemente en la seccion anterior) recibe las colaboraciones de paquetes. Antes
de subir un paquete nuevo, es necesario seguir ciertos pasos que garanticen su funcionabilidad y
documentacion, entre otras cosas. El grupo de desarrollo de R ha creado un comando a tal fin:
check . Este comando verifica que el paquete pueda instalarse, que los ejemplos corran y que la
documentacion con la cual debe liberarse exista, este completa y pueda ser procesada por los
formateadores (la documentacion de un paquete se crea en los formatos de texto plano, HTML
y TEX). Si es necesario compilar codigo, tambien chequea que esto pueda hacerse correctamente.
Se verifica ademas que la estructura de archivos y directorios sea la adecuada: es necesario que
existan ciertos archivos de configuracion y de ayuda, los cuales usualmente contienen scripts de
verificacion de librerıas requeridas e informacion acerca de las licencias y caracterısticas generales.
Este comando debe finalizar su ejecucion sin errores ni advertencias para que el paquete sea
aceptado en el repositorio. Con el comando build puede generarse un archivo comprimido listo
para liberar una version de nuestro paquete. La “entrega” se realiza mediante la carga del
archivo a un repositorio temporario (FTP) de paquetes y el envıo de un correo electronico a los
mantenedores de CRAN .
Capıtulo 3
Z
Las especificaciones pueden ser provechosas en muchos sentidos: describen propiedades sin in-
miscuirse en implementaciones, son referencia constante para todos los individuos involucrados
de una u otra forma en el proceso de creacion de software (investigadores, codificadores, testers,
documentadores, clientes, etc.) y forman la estructura basica para la etapa de codificacion. La
matematica ha ayudado a formalizar estos conceptos a traves del concepto de tipos.
Z es el nombre de la notacion que utilizamos para la especificacion de nuestro trabajo. En este
capıtulo se presentan las notaciones basicas y definiciones de objetos necesarios para compren-
derla. Ellos son: definiciones, abreviaciones, definiciones axiomaticas, definiciones genericas y
esquemas.
Z es un lenguaje tipado, lo que permite la creacion de algoritmos para la verificacion automatica
de tipos y ambito de variables. Entre todas las herramientas disponibles a tal fin, elegimos fuzz
para este trabajo, por tener una notacion simple y adaptaciones para su impresion en formatos
como LATEX.
Al disponer solo del tipo de los numeros enteros (caracterıstica de Z ), vimos la necesidad de
definir el tipo que represente los numeros reales (y varios de sus subconjuntos), de modo de
clarificar notaciones y hacer nuestras especificaciones de lectura natural e intuitiva. Para ello nos
basamos en una publicacion de R. D. Arthan que axiomatiza este conjunto de forma precisa.
Con esta extension fue posible definir nuestro esquema de representacion de una imagen y a
partir de allı modelar los algoritmos que componen este trabajo, y que seran tratados en los
sucesivos capıtulos.
3.1. Las especificaciones formales
Las especificaciones formales usan la notacion matematica para describir de una forma precisa las
propiedades que debe tener un sistema de informacion, sin restringir excesivamente la forma en
que estas propiedades son alcanzadas. Describen que debe hacer el sistema sin decir como debe
12
Capıtulo 3. Z 13
hacerlo. Esta abstraccion hace de la especificacion formal una herramienta util en el proceso de
desarrollo de sistemas de computacion, porque permiten que las preguntas acerca de lo que hace
el sistema puedan ser respondidas de una manera confiable, sin la necesidad de desenmaranar la
informacion de una masa de codigo detallada, o especular acerca del significado de frases en una
descripcion en prosa imprecisa.
Una especificacion formal puede servir como un punto de referencia simple y confiable para
quienes investiguen las necesidades de los clientes, para quienes implementen los programas para
satisfacer esas necesidades, para aquellos que testeen los resultados y para aquellos que escriban
la documentacion del sistema. En definitiva, es una herramienta que puede ser util para todos
los integrantes del proceso de desarrollo.
Al ser independiente del codigo del programa, la especificacion formal de un sistema puede ser
realizada en las primeras etapas del proceso de desarrollo. Aun cuando cambie a medida que se
gane en comprension del problema y percepcion de la evolucion de las necesidades del cliente,
puede ser una media apreciable para promover un entendimiento comun entre todos los roles
involucrados en el sistema.
Una forma en que la notacion matematica puede ayudar a alcanzar estos objetivos es a traves
del modelo de tipos de datos matematicos del sistema. Estos tipos de datos no estan orientados a
la representacion computacional, pero responden a un conjunto de leyes que hacen posible sacar
conclusiones efectivas acerca del comportamiento que tendra un sistema especificado.
3.2. El lenguaje de especificacion Z
Z es un lenguaje de especificacion que trabaja a altos niveles de abstraccion. Esto permite que
aun comportamientos complejos puedan ser descriptos precisa y consisamente. Originalmente
propuesto por Jean-Raymond Abrial en 1977 con la ayuda de Steve Schuman y Bertrand Meyer,
fue desarrollado por el grupo de Investigacion de Programacion de la Universidad de Oxford.
Ha sido sometido en los ultimos anos a estandarizacion de la Organizacion Internacional de
Estandarizacion (ISO).
La semantica de Z es matematica; de esta manera las formulas pueden ser manipuladas algebraica
y logicamente.
En Z usamos la notacion de predicados logicos para describir abstractamente el efecto de cada
operacion del sistema, de una forma que permite sacar conclusiones y hacer analisis acerca de
su comportamiento.
La notacion esta basada en teorıa de conjuntos y logica matematica. La teorıa de conjuntos
usada incluye operadores de conjunto basicos y por comprension, productos cartesianos y partes
de conjuntos. La logica matematica es un calculo de predicados de primer orden. Juntos, forman
un lenguaje matematico que es facil de entender y, sobre todo, de llevar a la practica.
Otro aspecto es como se puede estructurar este lenguaje. En Z esto se responde con el concepto de
esquemas: una declaracion de patrones y restricciones. El lenguaje de esquemas puede ser usado
Capıtulo 3. Z 14
para describir el estado del sistema, y las formas en que este estado puede cambiar. Tambien
puede describir propiedades del sistema y ayudar a pensar acerca de posibles refinamientos del
diseno.
Los esquemas se utilizan para describir aspectos dinamicos y estaticos. Estos ultimos incluyen:
los estados que ocupa; y
las relaciones invariantes que son mantenidas en el movimiento de estado a estado en el
sistema
Los aspectos dinamicos incluyen:
las operaciones posibles;
la relacion entre las entradas y las salidas; y
los cambios de estados que pueden ocurrir
Una de las caracterısticas principales de Z es el uso de tipos. Ademas de ser esto un enlace de
extrema utilidad para el momento de la codificacion, puede ser sujeto de chequeos automaticos.
Existen varias herramientas a tal fin, entre las que se encuentra fuzz, la cual describiremos
brevemente mas adelante (seccion 3.4).
Otro aspecto es el uso del lenguaje natural: usamos el lenguaje matematico para determinar el
problema y eventualmente encontrar soluciones, e incluso para probar que los disenos cumplen
con la especificacion. El uso del lenguaje natural relaciona la matematica con los objetos de la
vida real, y es esencial para hacer que las especificaciones sean realmente obvias para el lector.
3.3. Definiciones en Z
A modo introductivo presentamos algunos de los conceptos sobre los cuales se basa el lenguaje
de especificacion Z , que seran de utilidad para la comprension de las especificaciones del trabajo.
3.3.1. Declaraciones
Es la forma mas simple de declarar un objeto en Z . Se utiliza en especial para tipos basicos o
conjuntos dados. Se denotan por una declaracion del nombre entre corchetes:
[A]
Este tipo de declaraciones introduce un nuevo tipo, con lo que podremos declarar variables con
ese tipo en el futuro:
Capıtulo 3. Z 15
0 : A
3.3.2. Abreviaciones
Es la manera en que se puede definir un objeto a partir de otros existentes, cuando sus objetos
y estados son iguales:
VALUE == MinValue . . MaxValue
3.3.3. Definiciones axiomaticas
Se pueden introducir objetos con restricciones, como las que deben asumirse cuando un sımbolo
es usado. Estas restricciones se interpretan como axiomas del objeto:
declaracion
predicado
donde predicado simboliza las restricciones del objeto u objetos declarados en declaracion.
Por ejemplo:
TopValue : N
TopValue = MaxValue + 1
Introduce un nuevo sımbolo, TopValue, que satisface el predicado que se menciona. Como en
este ejemplo, las declaraciones pueden restringirse hasta el punto que se denote solo un objeto.
3.3.4. Definiciones genericas
Se utilizan para definir una familia de constantes globales, parametrizadas por algun conjunto:
[Y ]
y : Y
predicado
Capıtulo 3. Z 16
introduce una constante generica de tipo Y, satisfaciendo el predicado predicado. Notar que Y
es, en este caso, un parametro formal: puede considerarse como un tipo basico con visibilidad en
esta definicion generica.
A modo de ejemplo, tenemos la definicion utilizada en el trabajo para obtener el largo de una
secuencia:
[X ]
# : seqX "N
#〈〉 = 0
∀ i : seqX | i 6= 〈〉 • # i = 1 + # (tail i)
3.3.5. Esquemas
Ademas del lenguaje matematico, en Z tenemos el lenguaje de esquemas, usado principalmente
para rejuntar partes de informacion, encapsularlas y nombrarlas para su futura reutilizacion. Este
ultimo aspecto es de vital importancia para las tecnicas formales: con ello podemos mantener
nuestras descripciones flexibles y manejables.
La forma general de los esquemas es esta:
NombreDeEsquema
declaraciones
predicados
A modo de ejemplo, nuestro esquema para representar una imagen:
Image
v : VALUES
width, height : N
dom v = {a : N ×N | 0≤ first a < width ∧ 0≤ second a < height}
3.4. fuzz
fuzz es un conjunto de herramientas de formateo e impresion de especificaciones en Z , y al-
goritmos para verificaciones de alcance y reglas de tipos conforme a la especificacion de este
lenguaje.
Entre las herramientas de formateo se incluyen archivos de estilo para LATEX, y la definicion
de un conjunto con sımbolos especiales propios de estas especificaciones. Para su uso fuzz pro-
vee, entre otros, de los siguientes entornos, los cuales fueron mencionados en la seccion 3.3: zed ,
Capıtulo 3. Z 17
axdef , gendef y schema, respectivamente para texto en prosa y fuera de estructuras, definicio-
nes axiomaticas, definiciones genericas y esquemas. Existen otros entornos disponibles que no
mencionaremos en este breve resumen.
Para este trabajo hicimos uso de sus dos funcionalidades principales. En la impresion actual se
utilizaron las herramientas que permiten que los diagramas y sımbolos especiales puedan verse
correctamente y mezclarse con texto en prosa, como es caracterıstico en muchos formatos de
especificacion. Y para la diagramacion del codigo Z para los algoritmos implementados, hicimos
uso del chequeador de tipos y alcance de variables, lo cual es mınimamente necesario en cualquier
chequeo de especificaciones.
El comando fuzz puede configurarse para tener dos tipos de salida: con la opcion −v obtenemos
un reporte en codigo ASCII de una representacion de cada parrafo en Z ; y con la opcion −t se
listan el tipo de cada nombre definido globalmente, en una representacion facil de leer. Ademas,
los esquemas son expandidos, para que resulte claro ver que componente tiene cada uno. La
salida de esta ultima opcion se incluye en formato digital con este trabajo (tal como se describe
en la seccion 6.6).
3.5. Especificacion en Z
3.5.1. Especificacion de reales
En la especificacion de software generalmente vienen incluidas ciertas nociones de tipos. En Z ,
esta nocion es muy acotada: un tipo es un conjunto maximal, al menos para los lımites de la
especificacion en cuestion. Esto trae como consecuencia que cada valor x en una especificacion
este asociado exactamente a un tipo: el conjunto mas grande s para el cual x ∈ s.
La notacion Z tiene un solo tipo built − in (esto es, propio de la notacion): el conjunto de todos
los enteros Z . Cualquier otro tipo puede construirse a base de este, o de valores de tipos basicos
(sobre los cuales no pueden asumirse ninguna propiedad).
Muchos de los algoritmos que presentamos en nuestra implementacion requieren de una precision
que los enteros no nos brindan de forma natural. Es facil determinar una biyeccion entre los
numeros enteros y los reales de precision acotada, pero el manejo de los mismos se torna tedioso
y la representacion no obedece a las costumbres sobre el manejo de valores que arrastramos
en la educacion que recibimos. Por esta razon, y por la estructura de imagenes que creimos
conveniente utilizar (aunque esta estructura y la representacion de valores estan ıntimamente
relacionadas) y que mencionaremos en esta seccion, es que necesitamos la especificacion de un
tipo que represente mas fidelignamente a los reales.
Para tal fin nos basamos en la publicacion de [Art96], “Arithmetics for Z”, la cual esta fuertemen-
te inspirada en el estandar [Dep95]. La especificacion que realizamos incluye la axiomatizacion
necesaria para definir el conjunto de los numeros reales y sus operaciones basicas (de acuerdo a
lo que nos resultaba excluyente disponer).
La axiomatizacion se caracteriza por tres propiedades de los numeros reales:
Capıtulo 3. Z 18
1. Los reales forman un campo
2. El campo de los reales puede ordenarse linealmente de forma que este orden sea compatible
con la suma y la multiplicacion. Para definir dicho orden es suficiente con encontrar un
conjunto R, cerrado por multiplicacion y suma, tales que Rp , Rn y {0} conformen una
particion del campo.
3. Cualquier subconjunto no vacıo de los reales, acotado inferiormente con respecto al orden
establecido en el punto anterior, tiene una cota inferior maximal.
Estas propiedades caracterizan a los reales (o cualquier isomorfismo) y una consecuencia de ello
es la existencia de un anillo incluido en este conjunto, que es isomorfo a los enteros.
Esta axiomatizacion es similar a las vistas en los libros de calculo. Comenzamos con un conjunto
maximal, que llamamos A
[A]
A partir de el, definimos el conjunto Z (el cual “redefinimos”),
Z : �A
y dos de sus elementos:
0 : A
1 : A
El resto de operaciones y axiomas se detallan a continuacion:
+ : A×A�A∼ : A�A
N : �Z
(Z × Z )� ( + ) ∈ Z × Z " Z
Z � (∼) ∈ Z " Z
{0, 1} ⊆ Z
∀ i , j , k : Z • (i + j ) + k = i + (j + k)
∧ i + j = j + i
∧ i + ∼i = 0
∧ i + 0 = i
∀ h : �Z • 1 ∈ h ∧ (∀ i, j : h • i + j ∈ h ∧ ∼i ∈ h) ⇒ h = Z
N =⋂{s : �Z | 0 ∈ s ∧ {i : s • i + 1} ⊆ s}
∼1 /∈ N
Capıtulo 3. Z 19
− : A×A�A
(Z × Z )� ( − ) ∈ Z × Z " Z
∀ i , j : Z • i − j = i + (∼j )
≤ , < , ≥ , > : A#A
∀ i , j : Z • (i ≤ j ⇔ j − i ∈ N )
∧ (i < j ⇔ i + 1≤ j)
∧ (i ≥ j ⇔ j ≤ i)
∧ (i > j ⇔ j < i)
∗ : A×A�A
(Z × Z )� ( ∗ ) ∈ Z × Z " Z
∀ i , j , k : Z • (i ∗ j ) ∗ k = i ∗ (j ∗ k)
∧ i ∗ j = j ∗ i
∧ i ∗ (j + k) = i ∗ j + i ∗ k
∧ 1 ∗ i = i
div , mod : A×A�A
(Z × Z \ {0})� ( div ) ∈ Z× Z" Z
(Z × Z \ {0})� ( mod ) ∈ Z× Z" Z
∀ i : Z • ∀ j : Z \ {0} • i = (i div j) ∗ j + i mod j
∧ (0≤ i mod j < j ∨ 0≥ i mod j > j)
R : �1 A
/ : A×A�A
(R × R)� ( + ) ∈ R × R" R
(R × R)� ( ∗ ) ∈ R × R" R
(R × R \ {0})� ( / ) ∈ R× R \ {0}" R
R � (∼) ∈ R" R
Z ⊆ R
∀ x , y , z : R • (x + y) + z = x + (y + z )
∧ x + y = y + x
∧ x + ∼x = 0
∧ x + 0 = x
∀ x , y , z : R • (x ∗ y) ∗ z = x ∗ (y ∗ z )
∧ x ∗ y = y ∗ x
∧ x ∗ (y + z ) = x ∗ y + x ∗ z
∧ 1 ∗ x = x
∀ x : R • ∀ y : R \ {0} • (x / y) ∗ y = x
Capıtulo 3. Z 20
Rp,Rn : �1 A
(Rp × Rp)� ( + ) ∈ Rp × Rp" Rp
(Rp × Rp)� ( ∗ ) ∈ Rp × Rp" Rp
Rn = (∼)�Rp�
Rn ∩ Rp = �
R = Rn ∪ {0} ∪ Rp
∀ x , y : R • x ≤ y ⇔ y + ∼x ∈ Rp ∪ {0}
Con esta “creacion” del tipo R, muchas de las operaciones sobre imagenes que fueron especificadas
(y que se mostraran pertinentemente, a medida que lo consideremos necesario) resultaron mas
claras e intuitivas.
3.5.2. Resto de las especificaciones
A partir de nuestro esquema de imagen
Image
v : VALUES
width, height : N
dom v = {a : N ×N | 0≤ first a < width ∧ 0≤ second a < height}
se especificaron las operaciones sobre imagenes que corresponden al presente trabajo. Las mismas
se presentaran en las secciones particulares de los algoritmos, cuando creamos necesario hacer
alguna aclaracion. De todas formas, los archivos correspondientes a estas descripciones pueden
encontrarse en formato digital, con el material que acompana este impreso (ver seccion 6.6 para
mas detalles).
Notese que no se hacen diferencias de acuerdo a la cantidad de canales que tenga la imagen en
cuestion. Esto fue una decision arbitraria y responde a una necesidad de claridad de notacion y en
algunos casos a similitudes en los diversos canales de una imagen. Vale decir que las especificacio-
nes realizadas en Z nos guiaron a traves de nuestro desarrollo, pero no nos restringieron. Es por
eso que algunas caracterısticas esperadas en las imagenes resultantes de la aplicacion de algun
algoritmo solo se describe a traves de una definicion axiomatica y algunas otras directamente se
asumen como disponibles para su uso.
Capıtulo 4
Imagen digital
Cuando se captura una imagen del mundo real a traves de una computadora, la continuidad de
tamano, intensidad y colores es truncada. La combinacion de caracterısticas fısicas continuas que
nuestra mente se encarga de manejar deben ser convertidas en numeros finitos para ser utilizados
por una computadora. Esa vision continua debe ser discretizada para obtener una imagen digital.
En esa conversion se determinan la resolucion espacial y la profundidad de color.
La representacion de imagenes color se basa en los denominados espacios de color, modelos
matematicos para especificar los colores. La mayorıa de estos modelos en uso estan orientados
o bien hacia el hardware o bien hacia aplicaciones en que la manipulacion de los colores es el
principal objetivo.
4.1. Representacion
Una imagen se puede definir como una funcion de dos dimensiones, f (x , y), donde x , y son
coordenadas espaciales, en el plano, y la amplitud de f en cualquier par de coordenadas (x , y)
se llama intensidad de la imagen en ese punto. La denominacion escala de grises se usa para
referirse a la intensidad en imagenes monocromaticas. Las imagenes en color estan formadas por
la combinacion de imagenes 2-D. Por ejemplo, en el sistema de color RGB (red, green, blue),
una imagen consiste de tres imagenes componentes individuales (rojo, verde, azul). Por esta
razon, muchas de las tecnicas desarrolladas para imagenes monocromaticas se pueden extender
a imagenes color mediante el procesamiento de cada una de las componentes individuales. En
general hablaremos en terminos de imagenes en escala de grises, haciendo las aclaraciones y
distinciones para extender a imagenes color cuando sea necesario.
Una imagen puede ser continua respecto a los ejes de coordenadas, como ası tambien en am-
plitud. Convertir dicha imagen a formato digital requiere que tanto las coordenadas como la
intensidad sean digitalizadas. El proceso de digitalizar las coordenadas se llama sampling (mues-
treo), mientras que el de digitalizar la amplitud se llama quantization. De esta manera, cuando
x , y , y la amplitud de f son valores finitos y discretos tenemos una imagen digital.
21
Capıtulo 4. Imagen digital 22
El resultado de sampling y quantization es una matriz de numeros reales. Asumiendo que f (x , y)
es muestreada a una imagen que tiene M filas y N columnas, decimos que la imagen tiene tamano
M ×N . El origen de la imagen lo definimos en (x , y) = (0, 0). La siguiente coordenada a lo largo
de la primera fila es (x , y) = (0, 1). Es decir, que de acuerdo con la notacion de matrices, el eje
vertical, y , recorre la imagen de arriba hacia abajo. El eje horizontal, x , la recorre de izquierda a
derecha. De esta manera podemos representar nuestra imagen digital como una matriz M ×N :
Figura 4.1: Matriz imagen
El lado derecho de la igualdad es por definicion una imagen digital. Cada elemento de esta matriz
se llama pixel (picture element). Usaremos los terminos imagen y pixel de aquı en adelante para
denotar una imagen digital y sus elementos, respectivamente.
En el proceso de digitalizacion se deben tomar decisiones sobre los valores de M , N , y para
el numero L de niveles de gris permitidos para cada pixel. No hay restricciones sobre M y N ,
solo que deben ser enteros positivos. Sin embargo, debido al tipo de procesos, almacenamiento y
hardware de sampling, el numero de niveles de gris es en general un entero potencia de 2: L = 2k .
Se asume tambien que estos niveles son equidistantes y que son enteros en el intervalo [0,L−1].
4.2. Resolucion espacial y de profundidad
El sampling determina la resolucion espacial de una imagen. La resolucion espacial define el me-
nor detalle discernible en una imagen. Supongamos que tenemos un cuadro con lıneas verticales
de ancho W , con un espacio entre estas lıneas tambien de ancho W . Un par consiste de una
lınea y el correspondiente espacio adyacente. Entonces el ancho de un par es 2W , y hay 1/2W
pares por unidad de distancia. Una definicion de resolucion es simplemente el menor numero de
pares discernibles por unidad de distancia; por ejemplo, 100 pares por milımetro.
Hay que tener en cuenta que cada pixel no representa solo un punto en la imagen, sino una region
rectangular. De esta forma, con pixels grandes no solo la resolucion espacial es baja, sino que el
valor del nivel de gris correspondiente hace aparecer discontinuidades en los bordes de los pixels.
A medida que los pixels se hacen mas pequenos, el efecto se hace menos pronunciado, hasta el
punto en que se tiene la sensacion de una imagen continua. Esto sucede cuando el tamano de
los pixels es menor que la resolucion espacial de nuestro sistema visual. Para una tarea dada el
tamano de pixel deberıa ser lo suficientemente pequeno de acuerdo a los objetos que queramos
estudiar de la imagen.
La resolucion de profundidad se refiere a la cantidad de bits que se utilizan para representar
la intensidad de un pixel, es decir el menor cambio distinguible en el nivel de gris. Como ya se
Capıtulo 4. Imagen digital 23
ha dicho, principalmente debido a restricciones de hardware, en general el numero de niveles de
gris es un entero potencia de 2, comunmente 8 bits, aunque algunas aplicaciones que requieren
mucha precision en este sentido pueden llevarlo a 16.
4.3. Modelos de color
Lo que los humanos percibimos como color es una combinacion de caracterısticas fısicas. Un
modelo (o espacio) de color es una representacion matematica de esas caracterısticas. El objetivo
es tambien facilitar la especificacion de colores mediante alguna forma estandar y aceptada. En
esencia se tratan de sistemas de coordenadas y subespacios en que cada color se representa por
un unico punto.
Brevemente repasaremos estos distintos esquemas. Si bien la mayorıa de los procesos con image-
nes digitales trabajan en RGB, muchas aplicaciones requieren la conversion a otros espacios de
color.
4.3.1. RGB
Todos los espacios de color son sistemas ortogonales tridimensionales de coordenadas, es decir
que los tres ejes (en este caso las intensidades de rojo, verde y azul) son perpendiculares entre
sı. La intensidad del rojo empieza en cero y se incrementa en uno de los ejes. Analogamente
para el verde y el azul en sus correspondientes ejes. Asumiendo 8 bits de profundidad, cada color
puede tener un valor maximo de 255, dando como resultado una estructura cubica. La escala de
grises (puntos de valores RGB iguales) se extiende desde el negro hasta el blanco, a lo largo de
la diagonal que une estos dos puntos.
Figura 4.2: Modelos de color RGB y CYM
Capıtulo 4. Imagen digital 24
De esta manera tenemos un modelo matematico que nos permite definir cualquier color dando
sus valores de rojo, verde y azul, es decir coordenadas en el cubo. El RGB es un espacio de color
aditivo, porque su origen esta en el negro y cualquier otro color se deriva sumando valores de
intensidad. Es el modelo usado en la practica para los monitores color y muchas camaras de
video.
4.3.2. CYM
Este espacio de color es el inverso exacto del RGB. En este caso, el origen es blanco y los ejes
primarios son cyan, amarillo y magenta. Ası, el color rojo es una combinacion de amarillo y
magenta, el verde de amarillo y cyan, y el azul de cyan y magenta. A continuacion se detallan
las ecuaciones que permiten pasar de un sistema a otro:
c = max − r m = max − g y = max − b
r = max − c g = max −m b = max − y
(max es el valor maximo de intensidad)
Si se muestra una imagen en CYM como si fuera RGB veremos una imagen con sus colores
invertidos o negativos. El CYM se usa principalmente en la industria de la impresion, donde
las imagenes empiezan sobre un papel blanco y la tinta se aplica para obtener los colores. Se
han desarrollado tecnicas para obtener imagenes de mayor calidad y a un menor costo. Uno de
estos avances es el llamado “under color removal” que modifica CYM en CYMK, donde la K
representa al negro.
Este proceso, sabiendo que todo color tiene un gris subyacente, es decir una misma cantidad de
cyan, magenta y amarillo, genera esa componente con tinta negra (mas barata) y utiliza menor
cantidad de tinta de color para lograr el tono correcto.
4.3.3. HSI
La vision humana tiende a observar los colores de una forma diferente. No vemos las cosas como
una mezcla de colores primarios en una proporcion particular, sino como tonos (hue), saturacion
(saturation) e intensidad (intensity). Todavıa se trata de un espacio tridimensional, aunque
bastante diferente del RGB o CYM.
En la imagen 4.3 vemos un eje que recorre el centro del cono, que representa la intensidad. Sobre
este eje se encuentran todos los valores de gris, con el negro en el origen del cono y el blanco
en la base. Cuanto mayor es la distancia sobre esta lınea al origen, la intensidad es mayor, mas
brillante.
Si vemos la base del cono desde arriba, se convierte en un cırculo. Los diferentes tonos estan
definidos por posiciones especıficas alrededor del cırculo. Los tonos estan dados por su posicion
angular en esta rueda.
Capıtulo 4. Imagen digital 25
Figura 4.3: Modelo de color HSI
La saturacion, o riqueza de color, esta definida como la distancia perpendicular al eje de intensi-
dad. Los colores mas cercanos al eje central tienen menor saturacion y se ven pastel. Los colores
cercanos al borde del cono tienen mayor saturacion y son mas marcados en apariencia. A veces
es preferible modificar una imagen en HSI en lugar de RGB. Por ejemplo, si quisieramos cambiar
el color amarillo de un auto a azul, pero sin afectar el brillo ni las sombras. Esto es relativamente
sencillo en HSI. Basta cambiar el valor de tono, sin modificar la intensidad ni la saturacion.
4.4. Nuestra implementacion
Siguiendo el esquema visto hasta aquı elegimos representar una imagen digital mediante una
matriz. Nos inclinamos por usar matrices de R, de dos dimensiones si la imagen tiene un unico
nivel de profundidad de color o tres dimensiones si se trata de imagenes RGB, el espacio de color
base del cual partimos. Sin embargo, esta decision tambien afectarıa nuestra forma de trabajar
en el lenguaje C.
Esta eleccion significarıa manejar arreglos lineales en C con una distribucion particular de los
datos, que es la forma en que R hace la conversion de matrices. Para hacer mas comprensible el
manejo de ındices sobre dicho arreglo se definio una macro que hace la traduccion de coordenadas
en la imagen a ındices en ese arreglo lineal.
Dada la siguiente matriz imagen
(r0,0, g0,0, b0,0) (r0,1, g0,1, b0,1) (r0,2, g0,2, b0,2) · · ·(r1,0, g1,0, b1,0) (r1,1, g1,1, b1,1) (r1,2, g1,2, b1,2) · · ·
......
.... . .
Capıtulo 4. Imagen digital 26
el correspondiente arreglo lineal que se obtiene en C tras la traduccion es:
r0,0 r1,0 . . . r0,1 r1,1 · · · g0,0 g1,0 · · · b0,0 b1,0 · · ·
Los formatos de imagen soportados son jpeg, a traves de la librerıa libjpeg, y tiff, mediante libtiff.
A partir de ellas se desarrollaron las funciones para leer y escribir archivos de imagenes. libjpeg es
una librerıa escrita en C que implementa un codificador/decodificador JPEG. Es mantenida por
el Grupo JPEG Independiente1. La version actual es la 6b. Similarmente, libtiff2 es una librerıa
que permite leer y escribir archivos en formato TIFF. Actualmente la ultima version estable es la
3.8.2. Ambas librerıas son libres, y se distribuyen tanto su codigo fuente como versiones binarias
para distintas plataformas.
4.4.1. Especificacion
A lo largo del trabajo se explican las distintas tecnicas y filtros mediante especificaciones en el
lenguaje Z. A continuacion se describen los esquemas que caracterizan a la representacion de
imagen elegida.
Existen un valor mınimo y un valor maximo. Para el caso de imagenes de 8 bits de profundidad,
tendremos MinValue = 0 y MaxValue = 255.
MinValue,MaxValue : N
Los posibles valores para cada pixel oscilan en el intervalo determinado por el mınimo y maximo
dados.
VALUE == MinValue . . MaxValue
VALUES define el espacio que va de un par (que representa las coordenadas de la imagen) en
un VALUE . Especifica el espacio de las matrices imagen.
VALUES == (N ×N �VALUE )
El esquema estado de una imagen esta dado por una matriz, y las dimensiones de alto y ancho.
En este caso se trata de imagenes con una sola componente de color.
Image
v : VALUES
width, height : N
dom v = {a : N ×N | 0≤ first a < width ∧ 0≤ second a < height}
1http://www.ijg.org/2http://www.remotesensing.org/libtiff
Capıtulo 5
El procesamiento digital de
imagenes
La vista es el mas avanzado de nuestros sentidos, tal es ası que las imagenes tienen un papel
importante en la percepcion humana. Sin embargo, a diferencia del ser humano que esta limitado
a la banda visual del espectro electromagnetico, las maquinas pueden cubrir distintas bandas,
desde las ondas gamma hasta las de radio. Pueden trabajar con imagenes generadas a partir de
fuentes que los humanos no estan acostumbrados a asociar con imagenes: ultrasonido, visualiza-
cion de modelos matematicos o vision por computadora, por citar algunos ejemplos. El campo
del procesamiento digital de imagenes se refiere al proceso de trabajar con imagenes digitales
mediante computadoras. Cubre una amplia gama de tecnicas, utilizadas en numerosas aplica-
ciones: para mejorar o distorsionar una imagen, destacar ciertas caracterısticas, crear una nueva
imagen desde otras o restaurar una imagen degradada (por transmision, adquisicion). Actual-
mente puede ser llevada a cabo por cualquier persona con una computadora personal. De esta
manera se observa el uso de tecnicas de procesamiento de imagenes entre artistas, cientıficos y
otros, aun sin conocimientos especıficos.
5.1. Orıgenes
Una de las primeras aplicaciones de las imagenes digitales fue en la industria de los periodicos,
cuando se enviaban fotos a traves de un cable submarino entre Londres y Nueva York. De esta
forma se redujo la transmision de una foto a traves del Atlantico, en 1920, de mas de una semana
a menos de tres horas. Un sistema de impresion especializado recibıa y reconstruıa las imagenes
codificadas enviadas a traves del cable. Algunos de los problemas iniciales fueron mejorar la
calidad visual de estas imagenes en funcion los procedimientos de impresion y la distribucion de
los niveles de intensidad.
Hasta ese momento tenemos ejemplos que involucran imagenes digitales, pero que no pueden
considerarse como ejemplos de procesamiento digital de imagenes, ya que no habıa computadoras
27
Capıtulo 5. El procesamiento digital de imagenes 28
en la generacion de las mismas. Entonces, la historia del procesamiento de imagenes se encuentra
ligada al desarrollo de las computadoras y la tecnologıa asociada (almacenamiento, visualizacion,
transmision).
Las primeras computadoras suficientemente poderosas para ejecutar tareas significativas de pro-
cesamiento de imagenes aparecieron en la decada del ’60. El nacimiento de lo que consideramos
el procesamiento digital de imagenes se puede remontar a la disponibilidad de esas maquinas y
el desarrollo del programa espacial de ese perıodo. La combinacion de estos dos factores saco a la
luz el potencial del campo de procesamiento de imagenes. El uso de tecnicas con computadoras
para mejorar imagenes espaciales empezo en el Jet Propulsion Laboratory (California) en 1964,
donde las imagenes de la Luna transmitidas por el Ranger 7 fueron procesadas por una compu-
tadora para corregir diferentes distorsiones inherentes a la camara de television utilizada. Estas
tecnicas constituyeron la base para nuevos metodos que se utilizarıan mas tarde para mejorar y
restaurar imagenes de misiones posteriores.
En paralelo a las aplicaciones espaciales, las tecnicas de procesamiento digital de imagenes se
comenzaron a usar en medicina, observaciones remotas de la Tierra y astronomıa (1960-70). La
invencion de la tomografıa computada es uno de los hechos mas importantes de la aplicacion del
procesamiento de imagenes en el diagnostico medico. Desde 1960 hasta nuestros dıas, el campo
del procesamiento de imagenes ha crecido de forma importante. Ademas de su aplicacion en la
medicina y las actividades espaciales, se ha extendido a multiples areas. Se usan procedimien-
tos por computadora para realzar el contraste o codificar los niveles de intensidad en colores
para facilitar la interpretacion de imagenes de rayos X y otros tipos utilizados en la industria,
la medicina y la biologıa. Los geografos usan tecnicas similares para estudiar los patrones de
contaminacion del aire e imagenes satelitales.
Los procedimientos para mejorar y restaurar imagenes se utilizan para procesar imagenes de-
gradadas de objetos irrecuperables o resultados experimentales demasiados costosos de repetir.
En arqueologıa, por ejemplo, se usan estos metodos para restaurar imagenes con ruido que son
el unico registro de artıculos raros, perdidos o danados despues de ser fotografiados. En fısica
y campos relacionados se usan tecnicas para procesar imagenes de experimentos en areas ta-
les como plasma de alta energıa y microscopıa del electron. Y de la misma manera se pueden
encontrar casos de aplicacion en astronomıa, biologıa, medicina nuclear, defensa o en la industria.
Todos estos ejemplos ilustran la utilidad de los resultados del procesamiento de imagenes con
la finalidad de la interpretacion del hombre. La segunda mayor area de aplicacion del proce-
samiento de imagenes es en el tratamiento de problemas relacionados con la percepcion de las
maquinas. En estos casos el interes se centra en procedimientos para extraer informacion de una
imagen para ser utilizada por una maquina, y por lo tanto, no necesariamente estos resultados
tienen que ver con las formas de interpretacion humana. Ejemplos de informacion utilizada por
las maquinas son los momentos estadısticos, los coeficientes de la transformada de Fourier y me-
didas de distancias multidimensionales. Problemas tıpicos en este campo son el reconocimiento
automatico de caracteres, vision de maquinas, aplicaciones militares, procesamiento de huellas
digitales, visualizacion de rayos X y muestras de sangre, y procesamiento de imagenes satelitales
para la prediccion del clima y analisis del medio ambiente.
Capıtulo 5. El procesamiento digital de imagenes 29
5.2. Aplicaciones
El uso del procesamiento digital de imagenes se ha ido extendiendo a distintas areas, y ha dejado
de ser una actividad exclusiva de un grupo de cientıficos, para ir teniendo cada vez mayor impacto
en nuestra vida cotidiana. A continuacion se describen algunas aplicaciones especıficas.
5.2.1. Astronomıa y exploracion del espacio
Este campo ha sido desde el comienzo una de las areas mas activas en el desarrollo de tecnicas
y avances en el procesamiento digital de imagenes. Debido a las senales debiles en la captura de
imagenes de los objetos celestes, se debieron desarrollar metodos para extraer informacion; es
ası como surgen muchos de los filtros disponibles hoy: promedio de imagenes, filtros de convolu-
cion y transformadas de Fourier, por ejemplo.
Los sistemas de imagenes disenados en esta area, en general, atribuyen menor importancia al
color, buscando el detalle. Es por eso que en gran medida se trabaja con imagenes en escala de
grises, aunque en algunos casos se anaden colores para resaltar determinada informacion.
5.2.2. Inteligencia y aplicacion militar
En este caso se utiliza como herramienta para la interpretacion de fotografıas, con el objetivo
de identificar areas de interes y extraer toda la informacion posible de la imagen. Puede ser en
busqueda de instalaciones militares, facilidades para la investigacion, complejos industriales o
estructuras residenciales. Una de las principales necesidades es la velocidad. Se hace zoom sobre
determinadas zonas de una imagen, rotaciones para lograr una perspectiva particular, o puede
ser necesario mejorar el contraste de la fotografıa. Adicionalmente tambien se requiere hacer
anotaciones sobre la imagen.
Otro uso en este campo es la combinacion de mapas digitalizados e imagenes satelitales para el
mejor conocimiento de una zona dada, sumado a la reconstruccion del terreno y animaciones,
que permiten conocer las caracterısticas topograficas del lugar.
5.2.3. Ciencias de la tierra
Los geologos pueden aprender mucho de imagenes tomadas de la superficie. Pueden identificar
facilmente fallas en la corteza de la Tierra, especialmente a partir de imagenes multiespectrales,
es decir cuando se cuenta con muchas imagenes capturadas de una misma area en diferentes
espectros electromagneticos.
Las imagenes multiespectrales se utilizan tambien en la explotacion de petroleo y minerales. Se
pueden determinar los mejores lugares para perforar o minar estudiando las macro estructuras
donde tienden a encontrarse el gas natural o los metales preciosos. Con sensores y radares se
pueden capturar y mapear imagenes del fondo del oceano. Tambien se utilizan sensores para
buscar patrones en las imagenes del clima, incrementando las capacidades de pronostico.
Capıtulo 5. El procesamiento digital de imagenes 30
5.2.4. Gobierno
Ası como se aplica el procesamiento de imagenes para el mapeo y exploracion de recursos,
los gobiernos pueden utilizar las mismas tecnicas con otros propositos. Una industria que ha
crecido mucho son los denominados Sistemas de Informacion Geografica (GIS, por sus siglas en
ingles). Los usos de GIS son amplios y variados. Se puede hacer seguimiento de proyectos de
construccion mediante fotografıas aereas. Mapas de centros de poblacion se pueden relacionar
con el cubrimiento de determinados servicios. A partir de informacion hidrografica y un mapa
de elevacion del terreno se pueden definir potenciales zonas de inundacion. Todas estas funciones
requieren distintas tecnicas de procesamiento que combinan imagenes con informacion grafica y
textual.
Este tipo de analisis puede ayudar a los gobiernos a estimar el crecimiento urbano y el planea-
miento de facilidades y servicios. La representacion visual de los datos abstractos en general
ofrece una mejor vista de situaciones del mundo real que los numeros y las estadısticas.
5.2.5. Visualizacion de datos
Mucho del trabajo de cientıficos e ingenieros dedicados a la investigacion involucra simulaciones
de problemas fısicos reales o potenciales usando modelos matematicos. Es razonable presentar
estos datos numericos de una manera visual. Ası se usan histogramas para analizar datos en una
dimension. Para el caso de dos dimensiones se puede utilizar alguna forma grafica o incluso una
imagen, en que la ubicacion de un pixel es funcion de los parametros de entrada y la intensidad
representa la magnitud u otro resultado de algun calculo.
5.2.6. Entretenimiento
La industria del entretenimiento se ha convertido en los ultimos anos en una de las principales
usuarias del procesamiento de imagenes. Los efectos visuales no se usan solo en pelıculas y
television, sino tambien en parques tematicos y eventos especiales. El uso de computadoras
transformo la industria y abrio la posibilidad al desarrollo de la creatividad. De hecho, el uso del
procesamiento digital de imagenes en la industria del entretenimiento impulsa el avance de los
lımites tecnologicos en lo que a computadoras y almacenamiento de datos se refiere.
5.2.7. Medicina
La medicina ha usado imagenes digitales durante muchos anos, y nuevas tecnicas hacen que
esta tendencia vaya en aumento. Los metodos en este campo son limitados, aunque hay que
tener en cuenta que deben proveer gran precision y confiabilidad puesto que en muchos casos
esta la vida en juego. Podemos citar por caso el uso de rayos X, como un metodo no intrusivo
que permite investigar un cuerpo, mostrando detalles finos de sus estructuras internas y que
se utiliza para diagnostico y tratamiento. Actualmente estas imagenes se pueden digitalizar, y
Capıtulo 5. El procesamiento digital de imagenes 31
ademas de integrar esa informacion en bases de datos, se tiene la posibilidad de realzar, escalar,
rotar, filtrar y manipular los datos de distintas maneras.
5.2.8. Procesamiento de documentos
Existen diversas tecnicas especializadas para operar sobre este tipo de datos. Una de las areas
de mayor investigacion es la de la compresion. Sin embargo, muchas veces contamos con esa
informacion en forma de imagen. Ası surge la necesidad de convertir una imagen digital en ca-
racteres ASCII. Este proceso se denomina Reconocimiento Optico de Caracteres (OCR). Usando
distintas operaciones y filtros sobre la imagen, esta se puede reducir a sus partes mınimas y luego
aplicar tecnicas de busqueda de patrones para distinguir los caracteres.
5.2.9. Aplicaciones industriales y vision de maquinas
Ası como los robots se han hecho cargo de tareas repetitivas o peligrosas, tambien se les ha dado
la habilidad de “ver” y tomar decisiones basadas en esas observaciones.
Una aplicacion es el ordenar y reconocer objetos, por ejemplo los productos que vienen en una
cinta transportadora. Se toma una captura de imagen, y usando filtros de contraste, threshold
y otras tecnicas, se pueden aislar e inspeccionar objetos individuales mediante un software es-
pecializado, y determinar la correccion de un objeto para pasar a una siguiente etapa en el
proceso.
5.2.10. Aplicaciones hogarenas
Finalmente el procesamiento digital de imagenes ha llegado tambien al hogar. A medida que se
va haciendo mas comun el uso de camaras digitales, surge para el usuario la necesidad, a traves
de su computadora personal, de manipular las imagenes capturadas. En general se trata de
operaciones por punto y procesos por vecino para el filtrado, correccion de color y composicion.
Capıtulo 6
biOps: un paquete de
procesamiento de imagenes para
R
biOps1, acronimo de Basic Image Operations, es el nombre del paquete publicado en los reposi-
torios de R con los algoritmos que en su mayorıa se decriben en este trabajo. El nombre se ha
instaurado por razones historicas, al ser la primer idea del proyecto la publicacion de varios pa-
quetes, con el mismo contenido que el actual dividido de acuerdo a su funcionalidad. Esta idea se
descarto por razones de experiencia en el uso de los paquetes y de dependencias y funcionalidades
en comun entre ellos.
En este capıtulo se describen otros paquetes R para el manejo de imagenes, parte de la investi-
gacion previa al desarrollo de biOps. A continuacion se detallan los componentes del paquete y
una introduccion a su interfaz grafica de usuario (biOpsGUI), el testing realizado, la estructura
y el contenido del material en formato digital que acompana el presente impreso y la organiza-
cion de los proximos capıtulos, en donde profundizaremos conceptos, teorıa y codificacion de los
algoritmos implementados.
Para una vision global del contenido y funcionalidad provista por el paquete, recomendamos la
lectura de este capıtulo. Para entrar en detalle en algun algoritmo o area particular, puede ser
conveniente la lectura del capıtulo correspondiente.
6.1. Otros paquetes R de manejo de imagenes
Nuestro estudio previo incluyo un rastreo y analisis de paquetes de R relacionados con el ma-
nejo y procesamiento de imagenes. En la actualidad, no hay muchos antecedentes en CRAN, el
repositorio oficial de paquetes R (analizado en la seccion 2.2). Aquı una lista de paquetes que
analizamos y un breve comentario de ellos:1http://cran.r-project.org/src/contrib/Descriptions/biOps.html
32
Capıtulo 6. biOps: un paquete de procesamiento de imagenes para R 33
adimpro2: maneja formatos de imagenes pgm, ppm y pnm, los cuales no seran tratados en
este trabajo. Si se tiene instalada la librerıa ImageMagick soporta mas formatos y cambio
de representaciones (algo que analizamos en 4.3 ya que esta librerıa tambien resulto del
interes de biOps, como se detalla en 14.1). Provee funcionalidad de rotar imagen, unos pocos
metodos de deteccion de bordes y extraccion de mascaras para aplicacion de algoritmos
mediante el Propagation-Separation approach3, un enfoque de imagenes que se basa en
adaptacion estructural, las cuales usan aproximaciones por modelos parametricos. Este
ultimo enfoque es central en los algoritmos de este paquete.
edci4: provee algunos metodos de deteccion de puntos en bordes mediante algoritmos ba-
sados en M-estimators, un concepto que utiliza la librerıa de modelado en Java, JVMA.
PET 5: algoritmos para escalar y rotar imagenes en formatos pet y fif. Pueden utilizarse
mas formatos, pero requieren del paquete adimpro. Provee tambien implementaciones de
algunas transformaciones, como la de Hough, Radon y Radon inversa6
rimage7: un paquete con implementacion de algoritmos multi proposito para imagenes jpeg.
Provee metodos de lectura de archivos, filtros pasalto y pasabajo, un par de algoritmos de
deteccion de bordes (Sobel y Laplace), filtro por transformada de Fourier y de impresion
de imagenes por pantalla.
biOps es mas abarcativo que los paquetes mencionados, tanto en ramas del procesamiento digital
de imagenes y diversidad de algoritmos, como en alternativas de implementacion (interpolacion
-capıtulo 8- y generalidad en deteccion de bordes -capıtulo 10-, por ejemplo). El paquete rima-
ge es, actualmente, el unico que presenta algunos algoritmos multi proposito, pero no ha sido
actualizado desde principios de 2005.
6.2. Estructura del paquete
La estructura de biOps (y en general, salvo algunas excepciones, de los paquetes R) es la siguiente:
ChangeLog
configure
data/
DESCRIPTION
inst/
LICENSE
man/
biOps-package.Rd
imgAdd.Rd
...
NAMESPACE
R/
arithmetics.R
2http://cran.r-project.org/src/contrib/Descriptions/adimpro.html3http://www.wias-berlin.de/project-areas/stat/projects/aws.html4http://cran.r-project.org/src/contrib/Descriptions/edci.html5http://cran.r-project.org/src/contrib/Descriptions/PET.html6http://eivind.imm.dtu.dk/staff/ptoft/ptoft papers.html7http://cran.r-project.org/src/contrib/Descriptions/rimage.html
Capıtulo 6. biOps: un paquete de procesamiento de imagenes para R 34
convolution.R
...
README
src/
arithmetics.c
convolution.c
...
Los archivos ChangeLog, DESCRIPTION, LICENSE y README contienen informacion acerca
de los cambios entre las versiones del paquete, la descripcion que aparecera en el repositorio, una
copia de la licencia e informacion de ayuda, respectivamente.
En configure y NAMESPACE se incluyen directivas para la instalacion (compilado, linkeado,
chequeo de dependencias, etc.) y ordenes para la carga dinamica del paquete.
Dentro de los directorios, se incluyen:
data: archivos que pueden ser cargados con la funcion de R data(). Estos son representacio-
nes de objetos o codigo R. En nuestro caso incluimos un objeto que representa la imagen
del logo de la comunidad.
inst : Se ubican los directorios que requieren ser copiados en la instalacion. En nuestro caso,
ubicamos aquı algunas imagenes de muestra.
man: paginas del manual. Cada funcion publica en R debe tener su correspondiente archivo
en este directorio, en un formato similar a LATEX, donde se indican (entre otros) tipos,
descripcion y ejemplos de uso. El comando check de R usa estos archivos para correr los
ejemplos en cada funcion, y detectar posibles errores en la pagina de manual o en las
implementaciones.
R: archivos de codigo R. En nuestro caso, son los algoritmos implementados (descriptos en
2.4) en R y los que utilizan funciones implementadas en C.
src: codigo C de las implementaciones de nuestros algoritmos.
En la figura 6.1 puede verse un diagrama con la organizacion del paquete. Cada rectangulo
representa una de nuestras divisiones: los nombres que se incluyen corresponden a los archivos
en codigo C, de los cuales el codigo R actua como interfaz. Se indica ademas, en que capıtulo se
trata cada uno de estas divisiones.
6.3. Testing
Para verificar el correcto funcionamiento de los algoritmos implementados se utilizo un script, es-
crito en R, que permite correr casos de prueba evaluando los resultados obtenidos en la aplicacion
de las funciones provistas por el paquete.
Un caso de prueba consiste de una matriz numerica que representa una posible imagen, de la
cual conocemos de antemano el resultado de una determinada operacion. De esta manera, se
Capıtulo 6. biOps: un paquete de procesamiento de imagenes para R 35
Figura 6.1: Estructura biOps
ejecuta la funcion correspondiente a la operacion y se chequea que el resultado obtenido sea el
esperado.
Esta metodologıa se puso en practica para aquellos algoritmos que consideramos susceptibles de
esta forma de testeo, en particular en los casos de las operaciones por pixel, aritmeticas, logicas,
por vecino, morfologicas y geometricas. Mientras que, por ejemplo, en el caso de la clasificacion
de imagenes, donde intervienen factores probabilısticos y aleatorios, y los resultados estan sujetos
a la interpretacion del usuario segun su necesidad, no fue posible su verificacion mediante este
tipo de testeo.
En todos los casos se efectuaron pruebas y aplicaciones de la implementacion con imagenes va-
riadas obteniendo resultados esperados. Por otra parte, desde su primera publicacion, el paquete
ha estado a disposicion de los usuarios quienes pueden hacer llegar sus reportes de uso a traves
de la lista de correo de la comunidad R. Al momento, solo se han recibido comentarios de algu-
nos inconvenientes con la instalacion de biOps en el sistema operativo Windows, que han sido
subsanados en la recientemente liberada version 0.2.
Capıtulo 6. biOps: un paquete de procesamiento de imagenes para R 36
6.4. biOpsGUI: el principio de una interfaz grafica de usua-
rio
Con el objetivo de brindar una mejor experiencia de usuario, comenzamos con la implementacion
de una interfaz grafica de usuario para biOps, llamada biOpsGUI. Este paquete requiere para su
uso de RGtk2 8, version portada a R de GTK 9, un conjunto de herramientas para crear interfaces
de usuario.
La interfaz grafica estuvo fuera del planeamiento de este proyecto, sin embargo pudimos imple-
mentar funciones para mostrar una imagen, manteniendo su tamano original, y utilidades para
visualizar las coordenadas y valores de los pixels de una imagen.
Es nuestro deseo el continuar desarrollando este paquete, como explicamos en la seccion 14.1.
6.5. Proximos capıtulos
Los proximos capitulos desarrollan la teorıa detras de los algoritmos y los detalles de especifica-
cion e implementacion. La distribucion de capıtulos es la siguiente:
Operaciones por pixel [Cap. 7]: Son, quiza, las modificaciones mas simples que pueden
realizarse: el valor de un pixel destino solo depende del correspondiente pixel fuente. Se
presentan algoritmos implementados mediante “tabla de reemplazos” o look-up tables (ma-
peo de valores en valores) y operaciones aritmeticas y logicas. Se introduce tambien una
representacion grafica de los valores de una imagen: los histogramas, utiles para ajus-
tar parametros en diversos algoritmos. Por ultimo, se desarrolla el concepto de ruido en
imagenes, y se describen dos formas de generarlo: Gaussiana e impulsiva.
Operaciones geometricas [Cap. 8]: Modifican la ubicacion de los pixels mediante una trans-
formacion geometrica. Se introduce el concepto de interpolacion, necesaria para “cubrir”
vacıos propios de estos mapeos. Si bien no es un proceso geometrico, es usado en muchas
de las transformaciones de este capıtulo. Se detallan las operaciones de rotacion, escalado,
espejado, recortado (crop), encogido (shrink) y traslacion.
Operaciones por vecino [Cap. 9]: Generan el pixel destino a partir del pixel fuente y
sus vecinos. Se introducen el concepto de convolucion (suma con peso de los pixels de
una seccion de imagen, llamada ventana) y los filtros que pueden ser aplicados con ella.
Tambien se describen filtros no lineales: mediana, mınimo y maximo.
Algoritmos de deteccion de bordes [Cap. 10]: Los bordes son los lımites entre objetos, y
entre objetos y fondo en una imagen. Existen aplicaciones para su deteccion en muchas de
las ramas del procesamiento digital de imagenes. Se revisaran algoritmos sencillos y rapidos
(homogeneidad y diferencia), metodos clasicos basados en convolucion (Sobel, Prewitt,
Roberts, etc.) y tecnicas avanzadas (Shen Castan, Marr Hildreth, etc.).8http://cran.r-project.org/src/contrib/Descriptions/RGtk2.html9http://www.gtk.org
Capıtulo 6. biOps: un paquete de procesamiento de imagenes para R 37
Filtros en el espacio de frecuencias [Cap. 11]: Se presentan filtros en el espacio de fre-
cuencias (tasa de cambio en la intensidad de los pixels) de una imagen. La transformacion
elegida es la difundida transformada rapida de Fourier. Con esta representacion es posible
la aplicacion de filtros, utiles para reemplazar a la convolucion con mascaras grandes. Se
desarrollan a fondo estos conceptos y la implementacion en biOps.
Operaciones morfologicas [Cap. 12]: Son operaciones matematicas sobre una representacion
de una imagen mediante un conjunto, y se utilizan para resaltar aspectos especıficos de la
forma. Se trataran las operaciones basicas, para imagenes binarias y de escala de grises,
de erosion, por la cual se borran ciertos pixels, dilatacion, donde se establece un patron
alrededor de un pixel, y sus combinaciones: apertura y clausura.
Clasificacion de imagenes [Cap. 13]: Se trata de obtener una nueva imagen, donde los pixels
han sido discriminados en diferentes categorıas. Se estudian los conceptos de clasificacion
supervisada y no supervisada, desarrollando los algoritmos no supervisados de Isodata y
K-Means, ofreciendo para este ultimo varias alternativas de implementacion.
6.6. Formato Digital
Un CD acompana este impreso. El contenido es el siguiente:
biOps/
biOpsGUI/
output/
packages/
report/
samples/
spec/
biOps y biOpsGUI : los paquetes descriptos en esta seccion.
output : se incluyen la salida de fuzz, con la opcion -t, para los archivos de especificacion
(como se vio en la subseccion 3.5.1) y las salidas completas del profiling (introducido en la
seccion 2.4 y ampliado en el apendice A).
packages: algunos de los paquetes que se describieron en este escrito: fuzz, R y rGTK
report : este impreso en varios formatos, y la documentacion de biOps y biOpsGUI.
samples: algunas imagenes de ejemplo
spec: los archivos de especificacion en Z para este proyecto (introducidos en la subseccion
3.5.1)
Capıtulo 7
Operaciones por pixel
Las operaciones por pixel son, quiza, las mas simples de las modificaciones que puedan sufrir
las imagenes. Esto es porque, para determinar el valor de un pixel en la imagen destino, solo es
necesario tener en cuenta el valor para el mismo pixel en la imagen fuente, independientemente
del resto de los valores para los demas componentes.
La implementacion de estas funcionalidades suelen ser bastante genericas y facilmente modifi-
cables. Este tipo de operaciones son, generalmente, unarias o binarias, aunque presentaremos
casos de numero ilimitado de parametros (por ejemplo, para la funcionalidad de promedio de
imagenes).
Dentro de esta categorıa se encuentran algoritmos de implementacion mediante “tabla de reem-
plazos” o look-up tables, mapeos de valores en valores que resultan en operaciones como el cambio
de intensidad y contraste, transformacion a negativo, etc., y que tienen multiples utilidades, que
intentaremos explicar y justificar.
Componen tambien esta categorıa las operaciones aritmeticas y logicas, manipulaciones naturales
que se realizan sobre valores numericos.
Los histogramas son representaciones graficas de la distribucion del rango de valores de una
imagen, que tiene utilidad para determinar parametros para muchas de las operaciones que se
implementaron en este trabajo.
El ruido es un vicio propio de cualquier senal, y las imagenes no escapan a este problema. En este
trabajo estudiaremos algunos metodos para eliminarlo y en este capıtulo, dos para generarlo: el
Gaussiano y el impulsivo. Estos metodos son utiles para evaluar la validez de filtros de eliminacion
o para mejorar otros algoritmos.
A priori, este tipo de procesamiento puede parecer banal, pero no debe minimizarse el potencial
que presenta, como trataremos de mostrar en este capıtulo.
38
Capıtulo 7. Operaciones por pixel 39
7.1. Look-up tables
El primer grupo de algoritmos que analizaremos son los que utilizan una “tabla de reemplazos”
como estructura de datos, mejor definida en ingles como look-up table, o LUT . Responden a
transformaciones numericas, descriptas genericamente por la siguiente ecuacion:
d(x , y) = lut(f (x , y)) (7.1)
donde d(x , y) y f (x , y) representan los pixels de la imagen destino y fuente, respectivamente,
en la coordenada (x , y). Las look-up tables son, en general, arreglos sencillos en donde se usa
el valor del pixel actual para obtener el valor del nuevo pixel (esto es, un mapeo de valores en
valores, lut). La imagen de destino se construye repitiendo este proceso para todos los pixels de
la imagen.
La ventaja de este tipo de implementaciones se basa en el ahorro del calculo repetido: como la
LUT se llena completamente, no es necesario hacer reiteradas veces un mismo calculo. El calculo
realizado es constante, independientemente del tamano de la imagen. La polıtica seguida para los
valores que se exceden de los lımites permitidos para un pixel es la de forzar su ingreso ajustando
el valor al mas cercano permitido. Ası, en nuestro caso, todo valor que supere 255 (maximo valor
para un pixel) sera ajustado a 255. Similarmente para los valores que desciendan mas alla del
mınimo (en nuestro caso 0, que se llevan a este valor). Es importante notar que la misma imagen
que tomamos como parametro puede usarse para llenar el buffer de la imagen de retorno.
El procedimiento es sencillo: para cada pixel en la imagen
Tomar el valor v del pixel
Consultar el valor v ′ de la LUT en el ındice v
Establecer a v ′ el valor de la posicion del pixel en cuestion para la imagen resultado
Este proceso puede verse en la figura 7.1. Usar la misma imagen como entrada y salida trae
aparejado un ahorro importante en la cantidad de memoria utilizada.
Esta transformacion numerica puede escribirse en notacion de funcion, como veremos en las
aplicaciones de esta seccion. Muchas veces resultan mas facil de visualizar si se las representa
graficamente. Por eso acompanamos para algunos casos un mapeo: el eje horizontal representa
el valor del pixel de entrada, y el eje vertical el resultado de la aplicacion de la operacion.
Figura 7.1: Look-up tables
Capıtulo 7. Operaciones por pixel 40
Cualquier funcion que pueda ser descripta en terminos matematicos (y que mapee valores en
valores), puede ser implementada como una tabla de reemplazos. Para el trabajo hicimos una
eleccion arbitraria de ellas, incluyendo las que nos parecıan mas representativas y utiles. De
todas formas, queda la implementacion de nuestra funcion en R llamada r look up table, por
la cual puede facilmente extenderse este trabajo a la inclusion de alguna otra funcion deseada.
La sencillez del procedimiento queda reflejado en la implementacion de esta funcion:
r_look_up_table <- function(imgdata , table){
for (i in 1: length(imgdata)){
imgdata[i] <- table[imgdata[i]+1]
}
imgdata
}
7.1.1. Modificacion de contraste
El contraste en una imagen es su distribucion de pixels claros y oscuros. Las imagenes con
poco contraste son en general mayormente claras, mayormente oscuras o mayormente “medio
tono”. Aquellas con mayor contraste tienen regiones de claros y oscuros, dado que usan mas
ampliamente el rango de valores.
El problema con las imagenes de alto contraste es que tienen grandes regiones de oscuros y de
claros. Por ejemplo, la fotografıa de una persona parada delante de una ventana en un dıa de
sol tiene alto contraste: la persona esta oscura y la ventana brillante. Las imagenes con buen
contraste exhiben un amplio rango de valores de pixels. Ninguno domina exageradamente por
sobre el resto, sino que todo el rango de valores es utilizado.
Nuestra implementacion para el incremento y decremento de contraste son un tanto distintas.
Para el caso del incremento (funcion imgIncreaseContrast), los valores entre los lımites dados
por parametro son mapeados en una distribucion lineal en el rango de los valores. El resto de los
valores se mapean al mas cercano hacia el maximo o mınimo. Visualmente la idea es la siguiente:
las zonas oscuras se hacen mas oscuras y las claras aun mas claras, lo que hace que la diferencia
de areas quede mas pronunciada. La funcion es la siguiente:
f (x ) =
0 n < min limitx −min limit min limit ≤ x ≤ max limit255 x > max limit
(7.2)
Figura 7.2: Decrementar contraste
Para el decremento de contraste (funcion imgDecreaseContrast) se usa el razonamiento inverso,
si bien estas operaciones, como puede verse, no son inversas, con lo que la aplicacion en cascada
Capıtulo 7. Operaciones por pixel 41
de algun orden de estas dos funciones no resulta en la misma imagen que al comienzo. Toma los
valores maximo y mınimo que deseamos que tenga la imagen resultado, y distribuye los valores
linealmente sobre esos parametros:
f (x ) = x×max desired −min desired
256+min desired
(7.3)
Figura 7.3: Incrementar contraste
Si bien no entra en la categorıa de LUT s, nos gustarıa nombrar tambien la implementacion de
imgNormalize, operacion que hace que los valores de la imagen ocupen todo el rango disponible.
Esto trae como consecuencia un decremento del contraste de la imagen, como mencionamos
anteriormente. Esta funcionalidad sera de utilidad para las transformaciones que se requieren en
los algoritmos que trabajan con la Transformada Rapida de Fourier (como se vera en el capıtulo
11).
7.1.2. Modificacion de intensidad
La intensidad es el nivel de color (o de gris, para imagenes en escala de grises) de una imagen.
Visualmente, el cambio de la intensidad da una sensacion de alteracion en el brillo de la imagen.
Los procedimientos que implementamos (funciones imgIncreaseIntensity e imgDecreaseIntensity)
toman como parametro el porcentaje de intensidad que deseamos modificar en la imagen en
cuestion. Las funciones subyacentes de estas transformaciones son:
f+(x ) = min(255, x + (x × percentage)) (7.4)
f−(x ) = max (0, x − (x × percentage)) (7.5)
7.1.3. Otras modificaciones
Una de las mas simples modificaciones que se suele realizar es la de inversion de los valores
de una imagen para obtener su negativo (imgNegative). La funcion relacionada y el grafico de
mapeo se muestra en la figura 7.1.3.
A modo ilustrativo mostramos ademas el esquema de especificacion en Z correspondiente a esta
aplicacion: los valores de alto y ancho permanecen sin modificar, y la funcion de valores se
modifica invirtiendo cada componente.
Capıtulo 7. Operaciones por pixel 42
Figura 7.4: Decrementar intensidad Figura 7.5: Incrementar intensidad
f (x ) = 255− x (7.6)
Figura 7.6: Negativo
Negative
∆Image
∀ a : dom v • v ′ a = MaxValue − v a
width ′ = width
height ′ = height
Muchas veces es util separar regiones de una imagen correspondientes a objetos que son de
nuestro interes con respecto a objetos que son parte del fondo de la imagen. El thresholding
(figura 7.1.3) es en general conveniente para este tipo de accion. Se establece un umbral o lımite
por el cual los valores que lo superen seran mapeados al valor maximo disponible, y los que no
al valor mınimo.
La modificacion gamma se trata de un mapeo exponencial. Se usa para cambiar el rango dinami-
co de una imagen. El resultado visual de esta aplicacion es el de resaltar los valores con alta
intensidad en la imagen (figura 7.1.3).
Capıtulo 7. Operaciones por pixel 43
f (x ) =
{0 x < thr value255 x ≥ thr value
(7.7)
Figura 7.7: Thresholding
f (x ) = b(x
255)1/gamma × 255c (7.8)
Figura 7.8: Transformacion Gamma
7.2. Operaciones aritmeticas y logicas
Como las imagenes digitales se componen de valores numericos, resulta natural aplicar aritmetica
sobre ellos. Estas operaciones en general son binarias, y pueden expresarse con la siguiente
ecuacion:
c(x , y) = a(x , y)〈operacion〉b(x , y) (7.9)
donde c es la imagen resultado (o destino), a y b son las imagenes de entrada, y 〈operacion〉es la operacion aritmetica efectuada; lease: suma (funcion imgAdd), resta (imgDiffer), division
(imgDivide) o multiplicacion (imgMultiply). En estos casos el valor de los pixels resultantes es
tambien independiente del resto de los pixels de las imagenes, con lo que seguimos en el campo de
las operaciones por pixel. En mas de un caso resulta necesario, como vimos en las LUT s, ajustar
el valor resultado para que permanezca dentro del rango aceptado para nuestra representacion.
Aquı la especificacion en Z general de estas aplicaciones binarias:
Capıtulo 7. Operaciones por pixel 44
BinaryOp
∆Image
op? : VALUE ×VALUE "VALUE
input? : Image
∀ x : (dom v) ∩ (dom input?.v) • v ′ x = clipPixel (op? (v x , input?.v x ))
∀ x : dom v ′ | x /∈ (dom v) ∩ (dom input?.v) • v ′ x = v x
width ′ = width
height ′ = height
Otras de las operaciones que implementamos son las de promedio (imgAverage), aunque esta
no necesariamente es una operacion binaria: toma como parametro una lista de imagenes de
la misma profundidad de color y calcula el valor promedio coordenada a coordenada, y la de
maximo (imgMaximum), que toma el maximo de cada coordenada entre dos imagenes y que se
usara en implementaciones que veremos en los proximos capıtulos.
Las aplicaciones de estas funcionalidades son variadas. Por ejemplo, el promedio entre imagenes
se utiliza en la eliminacion de ruido, pixels superfluos claros u oscuros que no son fiel reflejo
de la realidad. Estos “intrusos” aparecen en distintas intensidades y posiciones dentro de una
imagen (en general, puede asumirse que el ruido es aleatorio). Este hecho puede ser aprovechado
para eliminar el ruido: si se cuenta con una determinada cantidad de imagenes del mismo objeto
(como suele suceder con las fotos planetarias o satelitales, por ejemplo), se procede a obtener el
promedio de todas ellas:
r(x , y) =a1(x , y) + a2(x , y) + ... + an(x , y)
n(7.10)
Se experimentan buenos resultados al promediar al menos tres o cuatro imagenes, aunque con
dos imagenes pueden obtenerse comportamientos aceptables.
La diferencia entre imagenes es comun en aplicaciones de machine vision o aplicaciones roboticas.
Por ejemplo, es comun tener objetos pasando por una cinta transportadora. Se toma una imagen
de referencia, cuando no hay objetos presentes. Luego, tomando la diferencia entre esta imagen
y otra con elementos presentes en la cinta es posible, mediante la operacion de diferencia, aislar
estos objetos para ser analizados posteriormente. La resta entre imagenes tambien es usada para
la deteccion de cambios: si esta es mayormente cero, se puede deducir que no hubo cambios.
Si, por otro lado, hubo movimientos entre las escenas, se veran diferencias significativas y se
podra deducir que ha sido modificado. Un ejemplo de esto puede verse en la figura 7.9. En
7.9(c) puede verse el resultado de la diferencia negada de dos momentos de una distribucion de
herramientas (7.9(a) y 7.9(b)).
La suma y diferencia contra imagenes constantes suele utilizarse tambien para la correccion de
brillo de una imagen. Esto esta fuertemente relacionado con las operaciones de intensidad, vistas
en la seccion anterior, ası como las operaciones de multiplicacion y division, que modifican el
contraste de la imagen cuando son operadas contra imagenes constantes.
Capıtulo 7. Operaciones por pixel 45
(a) Imagen anterior (b) Imagen posterior (c) Diferencia negada
Figura 7.9: Aplicacion de imgDiffer
Similarmente a las operaciones aritmeticas se implementaron operaciones logicas ∧ (imgAND), ∨(imgOR) y xor (imgXOR). Estos operadores son funcionalmente completos para las operaciones
logicas, puesto que cualquier otro puede obtenerse a partir de combinaciones de los anteriores.
Los operadores de ∧ y ∨ son usados para masking , esto es, para seleccionar subimagenes de una
imagen. Esto es tambıen posible con la multiplicacion de imagenes.
La implementacion en C de estas operaciones aprovecha los operadores logicos entre bits: & (∧),
| (∨) y ∧ (xor)
7.3. Histogramas
El histograma de una imagen se refiere al histograma de los valores de intesidad de sus pixels.
Esto es, un grafico que muestra el numero de pixels de una imagen en cada intensidad encontrada.
La implementacion es sumamente sencilla. Se escanea la imagen y se va contando la cantidad
de pixels que tienen cada una de las intensidades posibles. Al finalizar se construye el grafico en
cuestion. Esto puede observarse en la implementacion de la funcion de R imgHistogram. En la
figura 7.10 podemos ver una imagen y su respectivo histograma.
(a) Imagen (b) Histograma
Figura 7.10: Histograma de una imagen
Capıtulo 7. Operaciones por pixel 46
El uso de los histogramas es realmente amplio. Uno de los mas comunes es decidir el valor por el
cual aplicar la operacion de thresholding (7.1.3). Si es conveniente aplicar esta operacion a una
imagen, es comun que el histograma sea “separable” en dos grandes grupos de valores (lo que se
denomina histogramas bimodales). Entonces, un buen valor para pasarle a la funcion podrıa ser
uno entre los dos “picos” que se daran en el histograma.
Dos operadores que estan relacionados con los histogramas son la normalizacion de contraste
(estiramiento de los valores para que ocupen todo el rango, como se vio en 7.1.1), ya que para
que esta operacion tenga sentido debe cumplirse que haya extremos en el rango de valores que
no esten siendo utilizados, y la ecualizacion de histogramas, metodos para modificar el rango
dinamico y el contraste de una imagen mediante la alteracion de las intensidades del histograma,
ecualizaciones sobre las cuales no hemos hecho hincapie en este trabajo.
7.4. Generacion de ruido
Todo proceso de senales tiene que tratar un evento aleatorio de fondo como es el ruido. Las
principales fuentes de ruido en las imagenes digitales se presentan durante la adquisicion (digita-
lizacion) y/o la transmision. No es parte de las senales ideales y puede ser causado por diversos
factores, entre ellos la variacion en la sensibilidad de los detectores, alteraciones en el ambiente,
radiaciones, errores de transmision, etc. Las caracterısticas del ruido dependen de su origen,
aunque lo mismo ocurre para el operador que mejor reduce sus efectos.
La generacion de ruido consiste en corromper deliberadamente una imagen. Esto puede reali-
zarse, por ejemplo, para probar la resistencia de algun operador al ruido o de intentar mejorar
los filtros existentes para la eliminacion del mismo.
La caracterizacion del ruido se hace mediante la funcion probabilıstica de densidad (PDF , por
sus siglas en ingles de probability density function). Dos de los mas comunes los presentaremos
a continuacion, por haber sido los elegidos para este trabajo: el ruido Gaussiano y el ruido
impulsivo (salt & pepper o sal y pimienta).
El ruido Gaussiano es matematicamente docil, por lo cual se lo utiliza mucho en la practica. El
PDF de una variable aleatoria Gaussiana z esta dado por:
p(z ) =1
√2πσ
× e−(z−µ)2/2σ2(7.11)
donde µ representa la media y σ el desvıo estandar. Para introducir ruido de este tipo (funcion
imgGaussianNoise) utilizamos el metodo de Box-Muller, el cual usa una tecnica de transforma-
da inversa para pasar de dos variables aleatorias uniformemente distribuidas a dos aleatorias
normales de media 0 y varianza 1, X e Y , las cuales pueden ser facilmente modificables para los
diferentes valores de media y varianza (σ2) usando la siguiente relacion:
X ′ = µ+√
σ2 ×X (7.12a)
Capıtulo 7. Operaciones por pixel 47
Y ′ = µ+√
σ2 ×Y (7.12b)
estas variables se suman a los pixels de a dos por vez, X ′ para el primero e Y ′ para el segundo.
El ruido impulsivo, tambien llamado salt & pepper se caracteriza por ocurrencias aleatorias de
valores mınimos o maximos en los canales de la imagen. Para imagenes de un solo canal, estos
valores corresponden a las tonalidades de blanco y negro, con lo que visualmente resulta en
“salpicados” blancos y negros, lo que da origen al nombre que recibe.
La implementacion (imgSaltPepperNoise) toma un valor que representa el porcentaje de pixels a
ser “contaminados”. Mediante el uso de variables aleatorias se determina si el pixel se transforma
y en tal caso si lo hace al valor maximo o al mınimo. En la figura 7.11 puede observarse una
aplicacion de esta funcion, con un parametro de 5 (es decir, 5 % de los pixels contaminados).
(a) Imagen original (b) Ruido agregado (5%)
Figura 7.11: Ruido “sal y pimienta”
Capıtulo 8
Operaciones geometricas
Los procesos geometricos modifican la ubicacion de los pixels basados en alguna transformacion
geometrica. La idea es mover los pixels alrededor de la imagen sin alterar, idealmente, sus valores.
Sin embargo, si algun proceso intenta mapear un pixel desde una ubicacion que no existe, se ge-
nerara un nuevo pixel. Este proceso de generacion se conoce como interpolacion. La interpolacion
propiamente dicha no es un proceso geometrico, pero es usado en muchas de las transformaciones
que veremos en este capıtulo. Se presentaran los conceptos basicos de los procesos geometricos
y las diferentes funciones que se utilizaron en la implementacion de los metodos.
En esta seccion se detallan la implementacion de las funciones de rotar, escalar, espejar, recortar
(crop), encoger y trasladar ; para muchas de las cuales, como veremos, puede elegirse el metodo
de interpolacion a aplicar.
8.1. Mapeo de valores: “hacia adelante” vs. “hacia atras”
En las operaciones geometricas se utiliza el mapeo inverso: a partir de las coordenadas de la
imagen destino se determinan las coordenadas de la imagen fuente de las cuales obtener los
valores para realizar la transformacion.
Transferir el pixel de entrada hacia un pixel de salida a traves de una funcion se denomina mapeo
“hacia adelante” (forward mapping). Esta alternativa trae aparejado ciertos problemas: agujeros
y solapamientos. Los agujeros son pixels cuyos valores no estan definidos, y el pixel destino no
tiene en estos casos su correspondiente pixel fuente. Los solapamientos ocurren cuando dos (o
mas) pixels se mapean al mismo pixel de destino. ¿Que valor se le asigna en esos casos?
Para resolver estos problemas se utiliza otro tipo de mapeo, “hacia atras” (reverse mapping).
Notar que en este caso surgen los mismos inconvenientes que en el mapeo “hacia adelante”, pero
no son problemas ya que cada pixel de la imagen destino tiene un valor asociado (es decir, los
agujeros quedaran en la imagen fuente, y los solapamientos no son problema al quedar los pixels
de la imagen destino con el mismo valor).
48
Capıtulo 8. Operaciones geometricas 49
Por esta razon es que se hace imprescindible el uso del mapeo “hacia atras”, que se utilizara en
las implementaciones de las operaciones geometricas de este capıtulo.
8.2. Interpolacion
El mapeo a veces genera problemas. Por ejemplo: ¿que pasa si nuestra funcion de mapeo calcula
una direccion de pixel no entera? Para que esto resulte mas visible, consideremos la siguiente
transformacion:
xs =xd
2ys =
yd
2
xs e ys denotan las coordenadas x e y del pixel fuente (respectivamente) y xd e yd las del pixel
destino.
El pixel para (0, 0) del destino vendra del (0, 0) del fuente. Pero, ¿que pasa con el pixel (1, 1)
del destino? La transformacion reversa buscarıa en (0.5, 0.5) del fuente, que no existe.
Para este tipo de problemas disponemos de una tecnica que se denomina interpolacion, un
proceso para generar valores de direcciones que se ubican “entre pixels”. Existen varias tecnicas
de interpolacion; la mas adecuada para usar depende mucho de la aplicacion en cuestion: los
algoritmos mas sofisticados mejoran la calidad de la imagen, pero hacen el proceso mas complejo
y computacionalmente mas costoso (y lo opuesto pasa para los algoritmos mas sencillos).
A continuacion presentamos los metodos de interpolacion que pueden aplicarse en las operaciones
(que lo requieren) de este capıtulo.
8.2.1. Interpolacion por el vecino mas cercano
La idea para el vecino mas cercano es la de asignar como salida el pixel que minimice la distancia
a la direccion generada (sin considerar en absoluto el resto de los pixels). La implementacion de
esta tecnica consiste en redondear la fraccion obtenida al entero mas cercano. La suma en 0.5 y el
redondeo logran este cometido. En el siguiente codigo C puede verse una posible implementacion:
fx = map (x_dest);
fy = map (y_dest);
x_src = (int) (fx + 0.5);
y_src = (int) (fy + 0.5);
Como no se genera ningun pixel, todos los valores son obtenidos del conjunto de entrada. En
general, a mayor cantidad de pixels asignados a uno mismo de entrada, mayor es la imprecision
que se logra en la imagen final. Esto puede verse, por ejemplo, en el escalado de imagenes cuando
el factor de escala es muy grande.
Capıtulo 8. Operaciones geometricas 50
8.2.2. Interpolacion bilineal
Otra tecnica comun de interpolacion es la bilineal. El pixel generado es una suma de pesos de los
cuatro vecinos mas cercanos. Los pesos son determinados linealmente. Cada peso es directamente
proporcional a la distancia a cada pixel existente.
Esta tecnica requiere tres interpolaciones lineales. Una de las formas de proceder, como veremos
en el siguiente codigo, es interpolar linealmente el par de pixels ubicado mas arriba y el par
ubicado mas abajo. Con ellos, se realiza la tercera interpolacion lineal, para obtener el valor
deseado:
pesoEO = fx - floor(x);
pesoNS = fy - floor(y);
/* 1ra interpolacion */
EOarriba = NO + pesoEO * (NE - NO);
/* 2da interpolacion */
EOabajo = SO + pesoEO * (SE - SO);
/* 3ra interpolacion */
dest = EOarriba + pesoNS * (EOabajo - EOarriba);
La interpolacion bilineal resulta en una imagen mas suave y lisa, en comparacion a la que se
obtiene con la interpolacion por vecino mas cercano. Sin embargo, al realizar tres interpolaciones
lineales, requiere claramente mas computacion que la mencionada anteriormente.
8.2.3. Interpolacion por B-Spline
El metodo del vecino mas cercano requiere un pixel de entrada. La interpolacion bilineal requiere
cuatro pixels de entrada. En este caso, veremos un metodo de orden mas alto, que requiere de
los 16 pixels mas cercanos. Se trata de B-Spline. La funcion esta definida ası:
f (x ) =
1
2| x |3 − | x |2 +
2
30 ≤| x |< 1
−1
6| x |3 + | x |2 −2 | x | +
4
31 ≤| x |< 2
0 2 ≤| x |
(8.1)
El principio es el mismo que para el resto de las interpolaciones de alto orden (que, salvo por la
convolucional cubica, no seran profundizadas en este trabajo): la funcion se centra en el punto de
interes y sus valores en los puntos de muestra son multiplicados por los valores de la funcion. La
suma de estos productos es el nuevo pixel generado. Se opera primero en cada fila, obteniendo
un resultado por cada una. Estos valores vuelven a procesarse, obteniendo un solo valor, que
corresponde al resultado de la interpolacion.
Capıtulo 8. Operaciones geometricas 51
8.2.4. Interpolacion convolucional cubica
Al igual que B-Spline, la interpolacion cubica utiliza los 16 pixels mas cercanos para generar el
nuevo pixel. En este caso, la familia de funciones esta definida de la siguiente manera:
f (x ) =
(a + 2) | x |3 −(a + 3) | x |2 +1 0 ≤| x |< 1
a | x |3 −5a | x |2 +8a | x | −4a 1 ≤| x |< 2
0 2 ≤| x |
(8.2)
El valor de la constante a es arbitrario, aunque se sugieren -0.5, -0.75 y -1.0. Las pruebas han
demostrado que para resultados visuales, el valor -1.0 es la mejor opcion.
Este metodo es quiza el que mas agudice la diferencia de valores. Una de las caracterısticas
notables es que puede tomar valores negativos o excederse de nuestro rango de valores. La salida
en estos casos debera ser alterada para satisfacer nuestras especificaciones.
Un detalle de implementacion: para ahorrar computacion en algunos casos fue conveniente la
aplicacion de la regla de Horner, metodo recursivo para transformar polinomios a la forma
monomial. Tal es el caso de expresiones como x 3 + 2x 2 + 3x + 4. Para evitar la operacion de
exponenciacion, costosa en sentido computacional, puede aplicarse esta regla, de la siguiente
forma:
x 3 + 2x 2 + 3x + 4
= (x 3 + 2x 2 + 3x ) + 4
= x (x 2 + 2x + 3) + 4
= x ((x 2 + 2x ) + 3) + 4
= x (x (x + 2) + 3) + 4
= (((x + 2)x + 3)x + 4)
8.3. Operaciones implementadas
8.3.1. Escalar
El escalar es la funcion por la cual se lleva la imagen a un tamano (mayor) deseado. Esta
operacion recibe muchos nombres: magnificar, zoom, estiramiento, etc. Hay dos cosas que deben
tenerse en cuenta cuando escalamos: la primera es que no se mejorara la resolucion de la imagen
original. No tenemos mas informacion de la que nos brinda la imagen original. Lo que sı puede
hacerse es una interpolacion que promedie de alguna manera e “invente” esos datos que estaran
faltando. La segunda cuestion es que, a menos que todos los escalados se realicen a partir de la
imagen original, los resultados seran siempre mas degradados. Al escalar, se estan creando pixels
Capıtulo 8. Operaciones geometricas 52
“artificiales”, con lo que las sucesivas aplicaciones generaran nuevos pixels a partir de estos, ya
creados anteriormente.
La implementacion de esta operacion es sencilla: recorremos la imagen de destino (mapeo hacia
atras) y obtenemos los valores a partir de las divisiones de las coordenadas actuales con los
respectivos factores de escala. El resultado puede obtenerse aplicando algunas de las funciones
de interpolacion.
Esta operacion, y aquellas que requieren de interpolacion para determinar sus valores, fueron
implementadas utilizando las operaciones mencionadas en la seccion anterior. Para el caso de
escalar una imagen, puede llamarse a la funcion imgScale con, ademas de la imagen en cuestion y
los factores de escala, alguno de las siguientes secuencia de caracteres, que identifican la operacion
de interpolacion a utilizar:
“nearestneighbor” (vecino mas cercano)
“bilinear” (bilineal)
“cubic” (convolucional cubica)
“spline” (B-Spline)
Esta identificacion de metodos es una constante a lo largo del trabajo. Es posible tambien invocar
directamente a un metodo en particular: esto se hace a traves de las funciones
imgNearestNeighborScale (vecino mas cercano)
imgBilinearScale (bilineal)
imgCubicScale (convolucional cubica)
imgSplineScale (B-Spline)
Estas operaciones no restringen su utilizacion para reducir el tamano de una imagen; aunque
para ello, como veremos, es conveniente el uso de funciones especıficas para encoger.
8.3.2. Encoger
En esta seccion se analizan dos algoritmos implementados para la reduccion del tamano de una
imagen. El uso tıpico de esta operacion es la creacion de imagenes en miniatura (comunmente
conocidas como thumbnails), y la idea que manejan es la de representar un conjunto de pixels
con un unico pixel. Para ello disponemos de varias tecnicas, entre las que elegimos las dos mas
usadas: la de representacion por mediana y por promedio.
Ambas tecnicas toman una ventana de n × n que van “deslizando” por sobre la imagen. El
valor de n depende del factor de reduccion que busquemos en la imagen: estos son inversamente
proporcionales, puesto que se requiere una ventana mas grande para determinar una cantidad
menor de pixels.
Capıtulo 8. Operaciones geometricas 53
En la representacion por mediana (imgMedianShrink) se ordenan los pixels de la ventana y se
elige el valor de la mediana, es decir, el que se encuentra en “el medio” del orden de valores
por magnitud. Esta tecnica requiere mucho tiempo de computacion debido a que el calculo de
la mediana no es sencillo. Existen algoritmos que mejoran por mucho el algoritmo ordinario de
calculo: para nuestra implementacion usamos quick select, que tiene la idea del ordenamiento
quick sort.
La idea de fondo es la misma. Echemos un vistazo al pseudocodigo:
quick_select (L){
elegir x en L
particionar L en L1 <x, L2=x, L3 >x
quick_sort (L1)
quick_sort (L3)
concatenar L1, L2, L3 en L’
devolver k-esimo de L’
}
Esto tiene el mismo orden que quick sort, O(n × log(n)). Podemos notar que si k es menor que
la longitud de L1, no es necesario ordenar L3. Lo mismo si k es mayor que la concatenacion de
L1 y L2. De esta forma podemos ahorrar un poco de calculo. Tambien podemos ahorrar (pero
no mucho) si no hacemos la concatenacion, simplemente mirando en el lugar que corresponda:
quick_select (L){
elegir x en L
particionar L en L1 <x, L2=x, L3 >x
if (k <= longitud (L1)){
quick_sort (L1)
devolver k-esimo de L1
}else if (k > longitud (L1) + longitud (L2)){
quick_sort (L3)
devolver (k - longitud (L1) - longitud (L2))-esimo de L3
}else{
devolver x
}
}
Esto sigue siendo O(n×log(n)), pero con una constante menor. Podemos hacer una nueva mejora:
el codigo de cada rama if ordena la lista y devuelve la posicion que corresponde, exactamente el
problema que estamos resolviendo. Luego, podemos hacer las mismas mejoras que hasta ahora:
quick_select (L, k){
elegir x en L
particionar L en L1 <x, L2=x, L3 >x
if (k <= longitud (L1)){
devolver quick_select (L1 , k)
}else if (k > longitud (L1) + longitud (L2)){
devolver quick_select (L3 , k - longitud (L1) - longitud (L2))
}else{
devolver x
}
}
La representacion por promedio (imgAverageShrink) utiliza el mismo concepto que la de por
mediana, pero toma el valor del promedio de los de la ventana. Esta no es una operacion tan
lenta como la de mediana, y los resultados son, en el caso general, igualmente aceptables.
Capıtulo 8. Operaciones geometricas 54
8.3.3. Rotar
La operacion basica de rotar es la siguiente:
xs = xd ∗ cos(α) + yd ∗ sin(α) (8.3)
ys = yd ∗ cos(α) + xd ∗ sin(α) (8.4)
De nuevo, xs e ys denotan respectivamente las coordenadas x e y del pixel fuente y xd e yd las
del pixel destino. Esta formula rotara la imagen sobre (0,0). Para rotar una imagen con respecto
a su centro (centrox , centroy), debemos modificar las ecuaciones 8.3 y 8.4:
xs = (xd − centrox ) ∗ cos(α) + (yd − centroy) ∗ sin(α) (8.5)
ys = (yd − centroy) ∗ cos(α) + (xd − centrox ) ∗ sin(α) (8.6)
La operacion de rotar cambiara las dimensiones de la imagen para que esta pueda verse completa-
mente, completando los vacıos que deje la rotacion con algun color predeterminado (tıpicamente
negro -caso de nuestra implementacion-). En la figura 8.1 pueden verse los sectores de la imagen
que no tendran valor asociado ante una rotacion de A grados. Ademas se indica con diferentes
colores los altos y anchos de la imagen original y de la rotada.
Figura 8.1: Rotacion de imagen
Una vez que se determinaron estos valores, deben ser interpolados. Para ello implementamos,
como en el resto de las operaciones que lo requerıan, funciones con las diversas interpolaciones:
imgNearestNeighborRotate, imgBilinearRotate, imgSplineRotate e imgCubicRotate. Lo impor-
tante para esta operacion es considerar los valores de xs e ys que caen dentro de los lımites de
la imagen fuente.
Capıtulo 8. Operaciones geometricas 55
Si el angulo de rotacion α es un multiplo de 90o, no es una buena idea aplicar las ecuaciones vistas
anteriormente, ya que lo unico que se precisa es una reubicacion de pixels; mas precisamente una
trasposicion de filas y columnas. Para ello se implementaron las rotaciones de 90o en sentido
horario (imgRotate90Clockwise) y antihorario (imgRotate90CounterClockwise).
8.3.4. Espejar
Espejar una imagen es, simplemente, darla vuelta sobre algunos de los ejes. El espejado horizontal
(imgHorizontalMirroring) voltea la imagen en el eje y . Ası, los objetos que antes aparecıan a la iz-
quierda de la imagen, ahora apareceran a la derecha. El espejado vertical (imgVerticalMirroring)
da vuelta la imagen en el eje x , con lo que los objetos que aparecıan en la parte superior de la
imagen, apareceran ahora en la parte inferior, y viceversa.
Es importante destacar que en esta operacion no hay intervencion de interpolacion, puesto que
el espejado es un mero reacomodo de la posicion de los pixels en la imagen.
En la figura 8.2 puede verse la imagen original y sus espejados en ambos ejes.
(a) Original (b) Espejado vertical (c) Espejado horizontal
Figura 8.2: Operacion de espejado
8.3.5. Trasladar
La traslacion consiste en mover un sector de una imagen a otra parte. Para ello debe utilizarse un
buffer secundario, de modo de no sobreescribir informacion que sea util en la misma operacion.
El uso de un unico buffer para este tipo de operaciones es un error comun que puede causar
operaciones recursivas sobre la imagen.
La implementacion de la operacion de trasladar, imgTranslate, toma como parametros, ademas
de la imagen en cuestion, las coordenadas del borde superior izquierdo del bloque fuente y destino,
y el ancho y alto del bloque a mover. En caso de que estos bloques sean demasiado grandes (es
decir, que los parametros indiquen que el bloque excede los lımites de la imagen), estos seran
corregidos automaticamente para hacer que la operacion sea valida.
En la figura 8.3 puede verse una imagen de 512 por 512 pixels (reducida para este impreso),
donde se ha trasladado un rectangulo de 110 (ancho) por 40 (alto) pixels desde la posicion (245,
Capıtulo 8. Operaciones geometricas 56
245) hasta la posicion (245, 285), produciendo la duplicacion de ojos de la bella Lenna, famosa
imagen utilizada en procesamiento de imagenes. En la figura 8.3(b) se demarcan los sectores de
destino y fuente de la operacion.
(a) Original (b) Posiciones de movimiento
(c) Trasladado
Figura 8.3: Operacion de traslacion
8.3.6. Recortar
El recortado, o crop, es quiza la operacion mas sencilla de entre las geometricas. Consiste en
reducir una imagen a una parte de la misma. El tamano en general es alterado y se requiere de
un segundo buffer para almacenar el resultado. Es una operacion muy comun a la hora de hacer
zoom de una imagen o, simplemente, de eliminar bordes que no son deseados. La implementacion
de esta funcion, imgCrop, toma como parametros las coordenadas de inicio del rectangulo que
deseamos conservar, y el ancho y alto correspondientes. Notar que este ancho y alto sera el
tamano final de la imagen, como puede verse en la especificacion Z de la operacion:
Capıtulo 8. Operaciones geometricas 57
ImageCrop
∆Image
x?, y? : N
width?, height? : N
0≤ x? < width
0≤ y? < height
0≤ width? < (width− x? + 1)
0≤ height? < (height− y? + 1)
width ′ = width?
height ′ = height?
∀ x , y : N | x ∈ 0 . . (width?− 1) ∧ y ∈ 0 . . (height?− 1) •v ′ (x , y) = v (x? + x , y? + y)
Podemos notar en este esquema, que se exige que el ancho y alto que se pasan por parametro
(width? y height? en este caso) no se excedan de los lımites que disponemos en la imagen
(habiendo fijado las coordenadas correspondientes a la margen superior izquierda del rectangulo
que deseamos conservar).
Capıtulo 9
Operaciones por vecino
Las operaciones por vecino, tambien denominadas procesos de imagenes por area, toman por
entrada un pixel y los pixels alrededor de este para generar el valor del pixel de salida.
Entre estas operaciones tenemos los llamados filtros espaciales lineales que trabajan sobre una
ventana de la imagen y una mascara o kernel del tamano de esa ventana. El termino filtro proviene
del procesamiento de senales en el espacio de frecuencias, a partir de la transformada de Fourier,
que veremos mas detalladamente en 11.3. Aquı veremos filtros que operan directamente en los
pixels de la imagen, implementados a partir de la convolucion de la imagen de entrada con un
kernel predefinido.
Describiremos algunos filtros no lineales, que tambien operan sobre ventanas de la imagen. Sin
embargo, la operacion de filtrado se basa en los valores de los pixels en la ventana y no se usa
una mascara con coeficientes para operar con ellos. Es el caso de los filtros por mediana, mınimo
y maximo.
9.1. Convolucion
La convolucion se usa en distintos filtros para el procesamiento de imagenes. Una convolucion
consiste en una suma con pesos del pixel de entrada y sus vecinos. Los pesos estan determinados
por una matriz, la matriz (o kernel) de convolucion. En general las dimensiones de esta matriz
son impares, de tal manera de poder determinar un centro. La ubicacion del centro corresponde
a la ubicacion del pixel de salida.
Entonces se mantiene una ventana corrediza que se centra en cada pixel de la imagen de entrada
y se generan nuevos pixels de salida. Cada nuevo valor se calcula multiplicando los pixels en
la ventana por su correspodiente peso en la matriz de convolucion y sumando esos productos
(figura 9.1). Es importante guardar los valores obtenidos en una nueva imagen, para calcular los
subsiguientes valores a partir de los pixels originales de la imagen.
La suma de los pesos de una mascara de convolucion afectan la intensidad global de la imagen
resultante. Muchas mascaras tienen coeficientes cuya suma es igual a 1. En estos casos la imagen
58
Capıtulo 9. Operaciones por vecino 59
Figura 9.1: Convolucion
producto de la convolucion tendra el mismo promedio de intensidad que la original. Otras masca-
ras (por ejemplo las de deteccion de bordes, ver 10.3) tienen coeficientes negativos y suman 0.
De esta forma se pueden obtener valores de pixel negativos. A ese valor se le suma una constante
(como la mitad de la maxima intensidad); si el resultado todavıa es negativo, el pixel se pone a
0.
En general, dada una imagen f de tamano M ×N y una mascara w de tamano m×n, la imagen
resultado de la convolucion g esta definida por:
g(x , y) =a∑
s=−a
b∑t=−b
w(s, t)f (x + s, y + t) (9.1)
donde a =(m − 1)
2y b =
(n − 1)
2.
Uno de los problemas que se plantean al momento de implementar filtros por convolucion es
como tratar los bordes de la imagen. Cuando la ventana de convolucion se centra en el pixel
(0, 0), que valores se deben multiplicar con los coeficientes de la mascara que quedan fuera de la
imagen? Existen distintas alternativas para manejar esta situacion.
Una es tratar las celdas vacıas de la ventana como ceros (zero padding). Es una solucion facil,
pero le resta importancia a los bordes de la imagen.
Otra posibilidad es iniciar la convolucion en la primera posicion tal que la ventana queda to-
talmente dentro de la imagen. Es decir, si la mascara es 3 × 3 empezarıa en (1, 1). Es simple
de implementar, y se suele copiar los bordes de la convolucion para obtener una imagen con las
mismas dimensiones que la original.
Hay alternativas que se basan en extender la imagen original antes de aplicar el filtro. Una forma
es duplicar los bordes. Si se usa una mascara 3 × 3, se duplican las filas de los bordes superior
Capıtulo 9. Operaciones por vecino 60
e inferior, y las columnas de los bordes izquierdo y derecho. Esta es la variante que elegimos en
nuestra implementacion.
Otro metodo es “envolver” (wrap) la imagen. O sea, si quisieramos aplicar una convolucion a
una imagen de 512 × 512 con una mascara 3 × 3, la primera ventana operarıa sobre los pixels
(511, 511), (0, 511), (1, 511), (511, 0), (0, 0), (1, 0), (511, 1), (0, 1), (1, 1).
Algo para tener en cuenta tambien es el hecho de que a medida que crece la mascara de convo-
lucion crece exponencialmente la carga computacional.
Nuestro esquema Z para la operacion de convolucion es el siguiente:
Convolution
∆Image
mask? : Mask
op? : Mask ×VALUES "VALUE
bias? : VALUE
width ′ = width
height ′ = height
∀ c : dom v ′ • v ′ (c) =
clipPixel (op? (mask?, getSlice (v ,width, height ,first c,
second c,mask?.width,mask?.height)) + bias?)
donde op? es la funcion que aplica la convolucion propiamente dicha a partir de la mascara dada
(mask?) y la ventana de la imagen con las dimensiones de la mascara correspondiente a un pixel
dado (el resultado de getSlice); al valor devuelto por op? se le suma bias?, un valor constante,
como se describio anteriormente. Y finalmente clipPixel garantiza que el valor del pixel final
este en el rango valido.
Al trabajar con imagenes color tenemos dos opciones. Una, operar sobre el canal de intensidad
en el modelo de color HSI. La otra es operar sobre cada uno de los canales de una imagen
RGB. El primero tiene la ventaja de que preserva la informacion de tonos original, pero requiere
conversiones de un modelo a otro. El metodo mas popular es el de hacer la convolucion sobre los
canales RGB, y es la alternativa que seguimos. Que tecnica es mejor depende del objetivo de la
aplicacion y los filtros.
Nuestro paquete ofrece una funcion de convolucion, imgConvolve, que aplica el filtro especi-
ficado por una mascara de entrada, definida por el usuario, sobre la imagen dada. Tambien
se implementaron algunos filtros predefinidos para blurring (imgBlur en biOps) y sharpening
(imgSharpen).
9.1.1. Blurring
El blurring es un filtro pasobajo que se aplica en la representacion espacial de una imagen.
Remueve los detalles finos de una imagen. Se usa, por ejemplo, para simular una camara fuera
Capıtulo 9. Operaciones por vecino 61
de foco o quitarle importancia al fondo.
En general se utilizan mascaras cuyos coeficientes son iguales. En una mascara 3 × 3 todos los
elementos son iguales a 1/9; en una 5×5, a 1/25. Como se puede ver se trata de un promedio entre
los vecinos. Cuanto mayor es la mascara, mayor sera el efecto y el tiempo de calculo requerido.
El blurring es una forma efectiva de reducir el ruido Gaussiano de una imagen, no ası para ruido
impulsivo (i.e. cuando no hay una correlacion con el valor original del pixel). Ademas se reducen
los valores extremos en cada ventana, y por lo tanto tiende a disminuir el contraste de la imagen.
Otra mascara usada es la que elige los coeficientes de tal manera de no afectar el promedio de
intensidad de la imagen, aproximando un perfil Gaussiano y haciendo la suma de los coeficientes
igual a 1.
El problema de usar filtros pasobajo para reducir el ruido de una imagen es que los bordes de los
objetos en la imagen se tornan difusos. Cuando se busca filtrar el ruido de una imagen el filtro
de mediana puede ser una mejor alternativa, ya que preserva mejor los bordes.
9.1.2. Sharpening
El sharpening produce el efecto opuesto al blurring. El sharpening enfatiza los detalles de una
imagen. Si una imagen es difusa puede llevarse a un nivel aceptable mediante este filtro. Claro
que tambien tiende a amplificar el ruido y se incrementa el contraste.
(a) Imagen original (b) Imagen filtrada
Figura 9.2: Aplicacion de sharpening
La mascara de convolucion usada tiene un coeficiente positivo en el centro y mayorıa negativos
en los bordes. El sharpening se basa en los filtros pasoalto que remueven los componentes de
baja frecuencia. Otro metodo para obtener un filtro pasoalto es restar a la imagen original la
imagen filtrada por pasobajo. Se conoce por unsharp.
Una alternativa al sharpening es el denominado filtro high-boost :
HighBoost = αOriginal − Pasobajo (9.2)
Cuando α = 1, el resultado es una imagen pasoalto. Si α > 1, una fraccion de la imagen original se
anade al resultado del pasoalto, lo que restablece algunos de los componentes de baja frecuencia.
El filtro high-boost retiene mas informacion del fondo de la imagen original. A medida que se
Capıtulo 9. Operaciones por vecino 62
incrementa α, la imagen se torna mas clara, ya que una mayor proporcion de la imagen original
se suma al resultado y entonces los valores de los pixels son mayores.
9.2. Filtro por mediana
Ya hemos mencionado que un filtro pasobajo puede resultar util para remover ruido Gaussiano,
pero no impulsivo. Una imagen con ruido impulsivo tiene pixels corruptos con valores de inten-
sidad de 0 o 255. Una manera efectiva de remover el ruido impulsivo es el filtro por mediana
(figura 9.3). Una de las ventajas de este filtro sobre el pasobajo es que preserva mejor los bordes
y detalles.
(a) Ruido agregado (5%) (b) Imagen filtrada
Figura 9.3: Aplicacion de filtro por mediana
El filtro por mediana se aplica llevando una ventana corrediza sobre la imagen original y or-
denando los pixels en la ventana en orden ascendente. La mediana (el pixel del centro en ese
ordenamiento) sera el valor del pixel correspodiente en la imagen resultado. La funcion principal
es forzar a los puntos cuya intensidad es muy distinta de sus vecinos a parecerse a ellos, elimi-
nando picos de intensidad. Al implementar el algoritmo surge el mismo inconveniente que con la
convolucion: como tratar las celdas de la ventana que no caen dentro de la imagen? Ademas de
las alternativas presentadas, se puede considerar una mas, que fue la elegida en nuestra imple-
mentacion (imgBlockMedianFilter): ignorar las celdas vacıas y operar solo sobre los valores de
la imagen en la ventana.
El procedimiento para filtrar imagenes color es diferente. El algoritmo para ordenar los pixels
debe ser distinto. Una posibilidad serıa aplicar el filtro descripto en cada uno de los canales y
combinar las salidas. Esto tiene el problema de que se pierde la correlacion entre los componentes
de color. Ademas una de las caracterısticas del filtro es que no se introducen nuevos valores en
la salida, sino que cada valor de pixel en el resultado se corresponde con alguno en la imagen de
entrada.
Capıtulo 9. Operaciones por vecino 63
Sin embargo hay una propiedad de la mediana que podemos aprovechar en este caso. La suma
de las diferencias entre un valor de mediana y todos los demas valores en un conjunto sera menor
que la suma de las diferencias para cualquier otro valor del conjunto:
N∑i=1
| xmed − xi | ≤N∑
i=1
| y − xi | (9.3)
N es el numero de elementos en el conjunto (serıa 9 para un filtro mediana 3× 3); y es un valor
arbitrario de ese conjunto; xmed es la mediana.
Entonces ahora podemos considerar sumas de diferencias en lugar de preocuparnos por como
ordenar los pixels color. Para cada pixel en nuestra ventana sumamos la diferencia entre los
componentes rojo, verde y azul con el resto de los pixels. El pixel con la menor suma es el valor
de salida. Es decir que para cada uno de los N pixels de la ventana se debe calcular la suma de
las diferencias para cada componente.
Distancei =N∑
j=1
(| redi − redj | + | greeni − greenj | + | bluei − bluej |) (9.4)
Donde i es el pixel que se esta procesando y j representa los demas pixels en la ventana; la menor
distancia, i , correspondera al pixel de salida xi .
Esta tecnica funciona bien tanto para ventanas de dimensiones impares como pares, aunque
tradicionalmente se utilizan dimensiones impares.
9.3. Filtro por mınimo/maximo
Los filtros por mınimo (imgMinimumFilter) y maximo (imgMaximumFilter) son similares al
filtro por mediana. En lugar de reemplazar el pixel del centro de la ventana por la mediana, se
usan el valor mınimo o maximo, respectivamente.
El filtro por mınimo remueve picos de blanco. De esta manera, un pixel es representado por el
mas oscuro de la ventana, y por lo tanto la intensidad de la imagen resultante se vera reducida
respecto de la original. El filtro por maximo remueve los picos oscuros, y la intensidad de la
imagen de salida sera mayor que la de la original.
Ambos filtros fallan a la hora de remover ruido impulsivo, ya que cada uno realza los picos
negativos (mınimo) o los picos positivos (maximo). Una cascada de filtros por maximo y mınimo
pueden servir para eliminar este ruido ”salt & pepper”. Un filtro por maximo seguido por uno
por mınimo se llama filtro de closing, mientras que uno por mınimo seguido por uno por maximo
es llamado filtro de opening.
Capıtulo 10
Algoritmos de deteccion de
bordes
Los bordes en una imagen suministran mucha informacion acerca de la misma. Por ejemplo
marcan los lımites entre un objeto y el fondo, y entre distintos objetos. Es decir que si se pueden
identificar los bordes con precision, se pueden localizar objetos y determinar algunas propiedades
basicas como area, perımetro o forma.
Existen numerosas aplicaciones para la deteccion de bordes, por ejemplo en vision de compu-
tadoras o en el proceso de identificar regiones en una imagen (segmentacion).
A lo largo de esta seccion revisamos distintos algoritmos para la deteccion de bordes: algunos
metodos sencillos y rapidos, los metodos tradicionales basados en mascaras de convolucion y
tambien algunas tecnicas avanzadas.
10.1. Generalidades
Diremos que existe un borde donde la intensidad de la imagen pasa de un valor bajo a uno alto
o viceversa. Como los bordes consisten principalmente de frecuencias altas, podrıamos detectar
bordes aplicando un filtro pasoalto en el espacio de Fourier (ver 11.4), o aplicando una convolucion
con una mascara apropiada en la representacion espacial. En la practica se suele utilizar esta
ultima alternativa, ya que es computacionalmente menos costosa y se obtienen muchas veces
mejores resultados.
Hay un numero infinito de orientaciones, anchos y formas de bordes. Y hay muchas tecnicas
para su deteccion, cada una con sus ventajas y desventajas. En algunos casos la experimentacion
ayuda a determinar cual es la mejor tecnica para aplicar en cada caso.
La salida de un operador de deteccion de bordes se denomina mapa de bordes. Como comple-
mento a la deteccion de bordes se puede aplicar una operacion de threshold para enfatizar los
bordes mas fuertes y disimular los debiles. Se pueden dar uno o dos niveles de threshold. Si se
64
Capıtulo 10. Algoritmos de deteccion de bordes 65
especifica solo uno, los pixels cuyos valores esten por encima se setean al maximo valor posible,
y aquellos que esten por debajo se setean a cero. Si se definen un valor de threshold superior y
uno inferior, los valores por debajo del inferior se setean a cero, aquellos entre los dos valores
dados no cambian y los que estan por encima del valor superior se setean al maximo posible.
10.2. Tecnicas sencillas
Los detectores de bordes mas simples y rapidos determinan el maximo valor a partir de una serie
de diferencias entre pixels. El operador de homogeneidad calcula la diferencia entre cada uno de
los 8 pixels y el del centro de una ventana de 3 × 3. El valor del pixel de salida es el maximo
entre los valores absolutos de las diferencias (ver figura 10.1). Puede ser necesario utilizar un
offset para acomodar los valores en la imagen final. En biOps esta implementado bajo el nombre
imgHomogeneityEdgeDetection.
(a) Operador (b) Ejemplo
res = max{| 11−11 |, | 11−13 |, | 11−15 |, | 11−16 |, | 11−11 |, | 11−16 |, | 11−12 |, | 11−11 |} = 5
Figura 10.1: Operador de homogeneidad
Similar al operador de homogeneidad se define el detector de bordes por diferencia (en biOps,
imgDifferenceEdgeDetection). Es mas rapido porque requiere cuatro restas por pixel. Las dife-
rencias que se calculan son superior izquierda - inferior derecha, medio izquierda - medio derecha,
inferior izquierda - superior derecha, y medio superior - medio inferior (figura 10.2).
(a) Operador (b) Ejemplo
res = max{| 11− 11 |, | 13− 12 |, | 15− 16 |, | 11− 16 |} = 5
Figura 10.2: Operador por diferencia
Capıtulo 10. Algoritmos de deteccion de bordes 66
Estos metodos son rapidos, pero a veces se necesitan tecnicas mas complejas. En la figura 10.3
se puede ver un ejemplo de una aplicacion del operador por diferencia.
(a) Imagen original (b) Deteccion de bordes
Figura 10.3: Aplicacion de operador por diferencia
10.3. Tecnicas por convolucion
Los operadores de gradiente encuentran bordes horizontales y verticales, es decir que podemos
usar las derivadas de la imagen. Se puede ver que la posicion de los bordes puede estimarse a
partir del maximo de la primera derivada o a partir de los llamados zero-crossings de la segunda
derivada (puntos en que la funcion cruza el cero). Por lo tanto, necesitamos una forma de calcular
la derivada de una imagen.
Figura 10.4: Borde y derivadas en una dimension
Para una funcion discreta de una dimension la primera derivada se puede aproximar por:
Capıtulo 10. Algoritmos de deteccion de bordes 67
df (i)
d(i)= f (i + 1)− f (i) (10.1)
El calculo de esta formula es equivalente a una convolucion de la funcion con [-1 1]. De mane-
ra similar, la segunda derivada se puede estimar convolviendo f (i) con [1 -2 1]. Entonces los
operadores por gradiente los podemos obtener por convolucion.
Existen diferentes mascaras de deteccion de bordes basadas en la formula descripta, que nos
permiten calcular la primera o segunda derivada de una imagen. Hay dos aproximaciones para
estimar la primera derivada de una imagen: gradient edge detection y compass edge detection.
Los coeficientes de estas mascaras suman 0. Si esto no fuera ası, entonces al convolver con una
imagen constante obtendrıamos una imagen distinta de 0, lo que implicarıa erroneamente la
existencia de bordes.
10.3.1. Deteccion de bordes por gradiente (Gradient Edge Detection)
Es una de las tecnicas mas utilizadas. Se aplican dos mascaras de convolucion sobre la imagen,
una que estima el gradiente en la direccion de x (Gx ), y otra en la direccion de y (Gy). La
magnitud absoluta del gradiente esta dada por:
| G |=√
G2x + G2
y (10.2)
y por lo general se aproxima por:
| G |=| Gx | + | Gy | (10.3)
Tambien se puede determinar la orientacion de los bordes por:
θ = arctan(Gx/Gy)− 3π/4 (10.4)
Las mascaras mas comunes, y que fueron implementadas, son Sobel (imgSobel , ver figura 10.5),
Roberts (imgRoberts), Prewitt (imgPrewitt) y Frei-Chen (imgFreiChen). A continuacion se des-
criben las correspondientes mascaras, tanto para la direccion horizontal como vertical. Notar que
una es la rotacion de 90o de la otra.
Capıtulo 10. Algoritmos de deteccion de bordes 68
Sobelx =
1 0 −1
2 0 −2
1 0 −1
Sobely =
1 2 1
0 0 0
−1 −2 −1
Robertsx =
0 0 −1
0 1 0
0 0 0
Robertsy =
0 0 0
0 1 0
0 0 −1
Prewittx =
1 0 −1
1 0 −1
1 0 −1
Prewitty =
1 1 1
0 0 0
−1 −1 −1
FreiChenx =
1 0 −1√
2 0 −√
2
1 0 −1
FreiCheny =
1
√2 1
0 0 0
−1 −√
2 −1
Figura 10.5: Aplicacion de Sobel (threshold = 40, negativo)
10.3.2. Deteccion de bordes por compas (Compass Edge Detection)
Los operadores por compass gradient encuentran bordes en ocho direcciones diferentes. Esto
requiere convolver la imagen con un conjunto de (en general ocho) mascaras, cada una sensible
a distintas orientaciones. La salida de la operacion corresponde al maximo de las convoluciones
aplicadas.
Hay que tener en cuenta que cuanto menor son las mascaras, son mas sensibles al ruido, mien-
tras que las mascaras mas grandes no pueden resolver detalles finos, ademas de ser el calculo
computacionalmente mas costoso.
Capıtulo 10. Algoritmos de deteccion de bordes 69
En este caso implementamos las mascaras de Prewitt (imgPrewittCompassGradient), Kirsch
(imgKirsch) y Robinson (imgRobinson3Level , imgRobinson5Level). A continuacion se detallan
las mascaras base. Las restantes se obtienen rotando 45o sucesivamente.
Prewitt =
1 1 −1
1 −2 −1
1 1 −1
Kirsch =
5 −3 −3
5 0 −3
5 −3 −3
Robinson3Level =
1 0 −1
1 0 −1
1 0 −1
Robinson5Level =
1 0 −1
2 0 −2
1 0 −1
10.4. Tecnicas avanzadas
Los operadores por gradiente vistos hasta aquı producen una respuesta grande a lo largo del area
donde hay bordes. Idealmente, un detector de bordes deberıa determinar el centro de los bordes.
Este concepto se denomina localizacion. Si un detector de bordes devuelve bordes de varios pixels
de ancho es difıcil definir el centro de los bordes. Se hace necesario aplicar un proceso de thinning
para reducir el ancho de los bordes a un pixel. Los detectores de bordes basados en la segunda
derivada proveen una mejor localizacion, importante en vision de maquinas.
Otra ventaja de los operadores de segunda derivada es que los bordes detectados son curvas
cerradas, importante para el proceso de segmentacion. Ademas, no responden ante areas de
variaciones lineales leves en la intensidad.
El operador de Laplacian es un buen ejemplo. Se trata de un operador omnidireccional, que
ademas produce bordes mas finos que los metodos anteriores. El resultado presenta un cambio
de signo en los bordes de la imagen, los ya mencionados zero-crossings. Por lo tanto, despues
de la convolucion, la imagen debe ser procesada para encontrar estos puntos y setear la salida
correspondiente.
Un problema con Laplacian es que es un operador susceptible al ruido, y entonces los zero-
crossings pueden indicar mas bordes que los esperados. En estos casos se debe aplicar un threshold
para filtrar el resultado.
Capıtulo 10. Algoritmos de deteccion de bordes 70
Otro operador de segunda derivada, menos susceptible al ruido, es el Laplacian of Gaussian
(LoG). Este aplica un suavizado gaussiano antes del operador de Laplacian. Ambas operaciones
se pueden resolver mediante una mascara de la siguiente forma:
LoG(x , y) =1
πσ4
1−x 2 + y2
2σ2
e−(x2+y2)/2σ2(10.5)
Cuanto mas ancha sea la funcion, mas ancho seran los bordes detectados; una funcion mas
angosta detectara bordes mas finos y mayor detalle. Mientras mayor sea el σ, mayor sera la
mascara de convolucion necesaria. Por otro lado, la deteccion de bordes basados en suavizado
gaussiano, al reducir el ruido en la imagen, reducen el numero de bordes falsos detectados.
Como aproximacion al LoG se suele usar el Difference of Gaussian (DoG) que tiene un menor
costo computacional para ser calculado:
DoG(x , y) =e−(x2+y2)/2σ2
1
2πσ21
−e−(x2+y2)/2σ2
2
2πσ22
s (10.6)
Este operador convuelve una imagen con una mascara que resulta de la diferencia de dos mascaras
Gaussianas con diferentes valores de σ. El cociente σ1/σ2 = 1,6 da una buena aproximacion a
LoG. Variando los valores de σ1 y σ2 se puede especificar el ancho de los bordes a detectar.
10.4.1. Marr Hildreth
Este algoritmo (1970, Marr y Hildreth) esta basado en el LoG. Consiste de los siguientes pasos:
1. Convolver la imagen I con una mascara Gaussiana
2. Aplicar el operador LoG (o DoG)
3. Los pixels correspondientes a bordes son los zero-crossings del resultado anterior
Este metodo tiene un par de limitaciones. En primer lugar, produce “falsos bordes”, es decir
genera respuestas donde no existen bordes; por otro lado, tampoco tiene buena localizacion. Fue
implementado en la funcion imgMarrHildreth, que tiene por argumentos una imagen y un valor
para el σ de la mascara Gaussiana.
10.4.2. Canny
El detector Canny (1986, John Canny) esta definido a partir de una serie de objetivos a cumplir:
Tasa de error: Debe responder solo a bordes y debe encontrarlos todos;
Localizacion: La distancia entre los bordes detectados y los reales debe ser mınima;
Capıtulo 10. Algoritmos de deteccion de bordes 71
Respuesta: No se deben detectar multiples pixels de borde cuando solo existe uno;
Para satisfacer estos criterios se utiliza el calculo de variaciones, que permite encontrar la funcion
que optimiza un funcional dado. En el caso de Canny, esa funcion se describe como la suma de
cuatro terminos exponenciales; sin embargo se puede aproximar por la primera derivada de una
Gaussiana.
El algoritmo esta definido por las siguientes etapas:
1. Convolucion con Gaussiana en las direcciones x , y
La derivada de una Gaussiana es susceptible al ruido; por esta razon se aplica una con-
volucion con una mascara Gaussiana, para obtener una imagen con un ligero borroneado
(blurring) que disminuya el ruido. El σ de esta Gaussiana es parametro del algoritmo. Se
aplica como dos convoluciones de una dimension por separado, dando por resultado las
imagenes componentes por direccion, Ix , Iy .
2. Convolucion con las derivadas Gaussianas en las direcciones x , y
Tambien se aplican por separado en cada direccion, y a la correspondiente componente,
para obtener I ′x , I ′y .
3. Calcular la magnitud del gradiente
Las componentes se combinan para obtener la magnitud del gradiente en cada pixel.
4. Aplicar eliminacion de puntos no maximos (nonmaximal suppression)
Los pixels de borde tienen una direccion asociada; la magnitud del gradiente en pixel de
borde debe ser mayor que la magnitud del gradiente de los pixels a cada lado del borde.
Los pixels que no son maximos locales son eliminados. Desde el pixel en cuestion, seguir la
direccion del gradiente hasta encontrar otro pixel; este es el primer vecino. Luego, desde el
pixel original, dirigirse en la direccion opuesta hasta encontrar un nuevo pixel, el segundo
vecino. Moviendose de un vecino al otro se pasa a traves del pixel de borde, cruzando el
borde, por lo tanto la magnitud del gradiente deberıa ser mayor en este ultimo pixel.
5. Threshold por Hysteresis
Canny sugiere aplicar hysteresis en lugar de simplemente elegir un valor de threshold para
toda la imagen. Hysteresis usa un valor de maximo de threshold, Th , y un valor mınimo,
Tl . Cualquier pixel en la imagen con un valor mayor que Th se marca como borde; luego,
cualquier pixel conectado a este, y que tenga un valor mayor a Tl , tambien se selecciona
como borde. Este proceso se puede hacer de forma recursiva, o mediante multiples pasadas
por la imagen.
En biOps se invoca a traves de la funcion imgCanny (ver figura 10.6), que toma como parametros
ademas de la imagen sobre la cual aplicar el algoritmo, el σ del filtro Gaussiano, y opcionalmente
los valores de threshold para el proceso de hysteresis.
Capıtulo 10. Algoritmos de deteccion de bordes 72
Figura 10.6: Aplicacion de Canny
10.4.3. Shen Castan
El concepto de optimalidad es relativo, y por lo tanto es posible definir un detector de bordes
mejor que Canny en ciertas circunstancias. El algoritmo de Shen Castan (1992, Shen y Castan)
coincide con Canny en la forma general: convolucion con una mascara suavizante, seguida de una
busqueda de pixels de borde. Sin embargo busca optimizar una funcion diferente para la tasa
de error, y en lugar de la derivada de una Gaussiana usa el filtro exponencial simetrico infinito
(ISEF, infinite symmetric exponential filter), que en dos dimensiones y para el caso discreto es:
f [i , j ] =(1− b)b|i|+|j |
1 + b(10.7)
donde b es el factor de suavizado usado por el filtro, y toma valores reales entre 0 y 1.
1. Sea I la imagen original. Aplicar ISEF y obtener la imagen filtrada, S
2. Calcular una aproximacion del operador Laplacian (bandlimitedLaplacian), B = S − I
3. Obtener BLI (binary Laplacian image)
Se obtiene de B seteando los pixels positivos a 1 y los demas a 0. Los pixels borde candidatos
son los lımites de las regiones en la imagen obtenida, que corresponden a los zero-crossings.
Si bien este podrıa ser el resultado, quedan un par de pasos para mejorar la calidad de los
pixels identificados.
4. Eliminar falsos zero-crossings
Analogo al proceso de eliminacion de puntos no maximos (nonmaximal suppression) del
algoritmo de Canny. En la posicion de un pixel borde habra un zero-crossing en la se-
gunda derivada de la imagen filtrada. Es decir que el gradiente en ese punto es o bien un
maximo o un mınimo. Si la segunda derivada cambia de signo de positivo a negativo, se
Capıtulo 10. Algoritmos de deteccion de bordes 73
llamara un zero-crossing positivo; y si pasa de negativo a positivo, zero-crossing negativo.
Los zero-crossings permitidos son aquellos que son positivos y tienen gradiente positivo, o
los negativos con gradiente negativo. Los demas zero-crossings seran considerados falsos y
no correspondientes a un borde.
5. Aplicar threshold por gradiente adaptativo
Una ventana de ancho fijo W se centra en cada pixel borde candidato en la imagen BLI.
Si se trata efectivamente de un pixel borde, entonces la ventana contendra dos regiones de
diferente nivel de gris separadas por un borde. La mejor estimacion del gradiente en ese
punto deberıa ser la diferencia de nivel entre las dos regiones, correspondientes una a los
pixels de valor 0 y la otra a los de valor 1 en la BLI.
6. Hysteresis
Es el mismo metodo que en Canny, pero adaptado para el caso en que los bordes estan
representados por zero-crossings.
Este algoritmo puede correrse sobre una imagen a traves de la funcion imgShenCastan que toma
argumentos para definir el factor de suavizado, un factor de thinning, el tamano de la ventana
del threshold por gradiente adaptativo, un porcentaje que indica la cantidad de pixels que debe
haber por encima del valor de threshold maximo, y un booleano que determina si se aplica
hysteresis o no.
10.5. Deteccion de bordes en color
La deteccion de bordes en imagenes color depende de la definicion de borde. Si se define como
la discontinuidad en la luminosidad de la imagen, entonces deberıamos hacer la deteccion en el
canal de intensidad, en el espacio de color HSI.
Otra definicion sostiene que un borde existe si esta presente en los tres canales, rojo, verde
y azul. En este caso se puede hacer la deteccion en cada componente y despues combinarlas,
obteniendo una imagen resultado color. Tambien podrıa hacerse la deteccion por componente y
luego sumarlas para crear una imagen en escala de grises.
Esta visto que la gran mayorıa de los bordes encontrados en las componentes de color de una
imagen tambien se encuentran en la componente de intensidad. De esta manera serıa suficiente
hacer la deteccion de bordes sobre el canal de intensidad. Sin embargo hay casos en imagenes
de bajo contraste en que existen bordes que no se detectan por luminosidad pero sı en las
componentes cromaticas. La decision entonces dependera principalmente de la aplicacion. En
nuestro caso, los algoritmos implementados trabajan sobre las componentes de color, trabajando
con imagenes en representacion RGB.
Capıtulo 11
Filtros en el espacio de
frecuencias
Gran parte del procesamiento digital de senales se hace en un espacio matematico conocido como
espacio de frecuencias. El espacio de frecuencias de una imagen se refiere a la tasa de cambio en la
intensidad de los pixels. Para representar la informacion en este espacio es necesario aplicar algun
tipo de transformacion. Una de las mas difundidas y estudiadas en este caso es la transformada
de Fourier.
En el caso particular de las imagenes introducimos una variante de la transformada de Fourier,
la denominada transformada de Fourier discreta. Sin embargo, el calculo de esta transforma-
cion es costoso computacionalmente. Por esta razon se desarrollo un metodo mas eficiente para
computarla, la llamada transformada rapida de Fourier, que es el utilizado en el procesamiento
digital.
Una vez que tenemos la representacion de la imagen en el espacio de frecuencias podemos analizar
su espectro de frecuencias, aplicar distintos filtros en este espacio e incluso, por una propiedad
de la transformada de Fourier, calcular mediante el producto de matrices complejas lo que en
representacion espacial hacıamos por convolucion, lo que es especialmente util para mascaras de
convolucion grandes.
11.1. Espacio de frecuencias
Una transformacion es simplemente un mapeo de un conjunto de coordenadas en otro. La trans-
formada de Fourier convierte coordenadas espaciales en frecuencias. Cualquier curva o superficie
se puede expresar como la suma de senos y cosenos. En el espacio de frecuencias (o espacio de
Fourier) una imagen se representa como los parametros de funciones seno y coseno. La transfor-
mada de Fourier es el metodo para pasar de una representacion a otra.
Se denomina espacio de frecuencias porque los parametros del seno son amplitud y frecuencia.
El hecho de que una imagen se pueda convertir al espacio de frecuencias implica que se puede
74
Capıtulo 11. Filtros en el espacio de frecuencias 75
reconocer informacion de baja y alta frecuencia. Una zona de la imagen que cambia lentamente
a lo largo de las columnas corresponde en el espacio de frecuencias a una funcion seno o coseno
con baja frecuencia. Por otro lado, si cambia rapidamente, como un borde, tendra componentes
con frecuencias altas.
El espacio de frecuencias de una imagen se refiere a la tasa en que la intensidad de los pixels
cambia. Las frecuencias altas se caracterizan por los grandes cambios de amplitud, mientras que
las bajas por zonas de valores casi constantes.
De esta manera es posible construir filtros para remover o realzar determinadas frecuencias en una
imagen, lo que permite en ciertas ocasiones producir efectos de restauracion. De hecho, el ruido
consiste principalmente de informacion de frecuencias altas, y entonces filtrar las frecuencias
altas deberıa producir una reduccion del ruido. Sin embargo, en este caso, tambien se obtiene
una reduccion de los bordes.
11.2. Transformada de Fourier
La transformada de Fourier convierte una imagen (o una senal, en una dimension) en un conjunto
de componentes de seno y coseno. Es importante mantener estas componentes separadas, y por
esta razon se suele usar vectores de la forma (coseno, seno) para cada punto de la representacion
en el espacio de frecuencias de una imagen. Una forma de representar estos vectores es mediante
numeros complejos. Cada numero complejo consiste de una parte real y una parte imaginaria, y
puede ser pensado como un vector. Un numero complejo tiene la siguiente forma:
z = (x , j y) = x + j y (11.1)
donde j es el numero imaginario√−1. El exponencial de un numero complejo se puede repre-
sentar como la suma de un seno y un coseno, que es exactamente lo que queremos:
ejθ = cos(θ) + j sin(θ) (11.2)
Esta representacion es la utilizada en la transformacion.
La transformada de Fourier opera sobre funciones continuas de longitud infinita. Para una funcion
de dos dimensiones:
H (u, v) =∫ ∞
−∞
∫ ∞
−∞h(x , y)e−j2π(ux+vy)dx dy (11.3)
Tambien es posible pasar del espacio de frecuencias a la representacion espacial, mediante la
transformada de Fourier inversa:
h(u, v) =∫ ∞
−∞
∫ ∞
−∞H (u, v)ej2π(ux+vy)du dv (11.4)
Capıtulo 11. Filtros en el espacio de frecuencias 76
Sin embargo al trabajar con imagenes no tenemos funciones continuas, sino que contamos con
un numero finito de pixels que tienen valores discretos. Por lo tanto necesitamos definir una
transformacion de Fourier discreta (DFT, Discrete Fourier Transformation), que no es mas que
un caso especial de la continua. La formula para computar la DFT de una imagen de M ×N es:
H (u, v) =1
MN
M−1∑x=0
N−1∑y=0
h(x , y)e−j2π(ux/M+vy/N ) (11.5)
y la inversa:
h(x , y) =M−1∑u=0
N−1∑v=0
H (u, v)ej2π(ux/M+vy/N ) (11.6)
Si representamos H (u, v) en coordenadas polares:
H (u, v) =| H (u, v) | e−jφ(u,v) (11.7)
tenemos
| H (u, v) |= [R2(u, v) + I 2(u, v)]1/2 (11.8)
φ(u, v) = tan−1
I (u, v)
R(u, v)
(11.9)
donde R(u, v) e I (u, v) son la parte real e imaginaria de H (u, v), respectivamente. A | H (u, v) |se le llama magnitud o espectro de la transformacion, y a φ(u, v), angulo de fase. A la hora de
trabajar con imagenes se usa especialmente el espectro.
El calculo de la DFT es computacionalmente intensivo. Trabajando con imagenes 2D de M ×M
se requieren M 4 multiplicaciones de complejos. Afortunadamente se desarrollo, por el ano 1942,
una tecnica “divide & conquer” para obtener la DFT que se denomino Transformada Rapida de
Fourier (FFT, Fast Fourier Transformation).
No entraremos en mas detalles acerca del calculo e implementacion de FFT, ya que irıan mas
alla de lo necesario para la comprension de este capıtulo. En nuestro desarrollo utilizamos FFTW
(Fast Fourier Transformation in the West), una librerıa libre bajo licencia GPL para calcular la
FFT en una o mas dimensiones. Esta librerıa puede manejar arreglos de tamanos arbitrarios, y
nos permite obtener rapidamente la DFT de una imagen.
Ahora que podemos obtener la transformacion de una imagen queremos mostrar la informacion.
Sin embargo existen algunas complicaciones que debemos superar para mostrar el espectro de
una imagen. Uno de los problemas que tenemos es que cada punto esta representado por un
Capıtulo 11. Filtros en el espacio de frecuencias 77
numero flotante, que no necesariamente esta en el rango 0 - 255. Una solucion usual es tomar el
logaritmo del espectro, es decir:
D(u, v) = c log[1+ | H (u, v) |] (11.10)
donde c es una constante, que representa el parametro de escala; ademas se suma 1 a cada pixel
para evitar pasar el valor 0 a la funcion logaritmo.
Una imagen del espectro tiene la componente cero en la esquina superior izquierda, como se ve
en 11.1(b). La forma convencional de mostrar el espectro es hacer un remapeo de los cuadrantes,
haciendo un intercambio (o “shift”) horizontal de la imagen en la mitad del ancho, y vertical en
la mitad del alto (11.1(c)).
¿Como interpretamos esta informacion? Cada pixel en el espectro (11.1(d)) representa un cambio
en el espacio de frecuencias de un ciclo por ancho de la imagen. El origen, en el centro del espectro
cuando este esta ordenado, es el termino constante. Si todos los pixels de la imagen fueran grises
entonces habrıa un unico valor en el espectro de frecuencias, y estarıa en el origen. El siguiente
pixel a la derecha del origen representa un ciclo por ancho de la imagen, el siguiente 2 ciclos
por ancho de imagen y ası sucesivamente. Es decir que las amplitudes de las frecuencias bajas
se encuentran en las esquinas del espectro, mientras que las altas estan alrededor del centro (el
origen del espectro).
biOps en este campo ofrece funciones para hacer la transformacion (imgFFT ) y su inversa
(imgFFTInv). Se puede decidir la organizacion de los cuadrantes tanto al momento de aplicar
FFT como una vez obtenido el resultado mediante la funcion imgFFTShift . Todas las funciones
mencionadas, a excepcion de imgFFTInv que devuelve una imagen, trabajan con matrices de
numeros complejos. Para obtener una imagen del espectro se puede invocar a imgFFTSpectrum,
y para generar la imagen de la informacion de fase, imgFFTPhase.
A continuacion se presentan los esquemas utilizados para representar las transformaciones y la
matriz resultado de FFT, y en los que se basan las especificaciones de los filtros en el espacio de
frecuencias que se detallan en las proximas secciones.
FFTMatrix
matrix : N ×N � Complex
width, height : N
dom matrix = {a : N ×N | 0≤ first a < width ∧ 0≤ second a < height}
fft : Image" FFTMatrix
∀ x : Image
• (∃1 y : FFTMatrix • fft (x ) = y ∧ x .width = y .width ∧ x .height = y .height)
Capıtulo 11. Filtros en el espacio de frecuencias 78
(a) Imagen original (b) Espectro FFT original
(c) Remapeo de cuadrantes (d) Espectro FFT remapeado
Figura 11.1: Transformada de Fourier
fftInv : FFTMatrix " Image
∀ x : FFTMatrix
• (∃1 y : Image • fftInv (x ) = y ∧ x .width = y .width ∧ x .height = y .height)
11.3. Convolucion
Una razon por la cual es util generar la informacion de frecuencia de una imagen es para aplicarle
filtros. Hemos visto filtros por convolucion en la representacion espacial (ver 9.1). Una convolucion
en la representacion espacial es equivalente a una multiplicacion de espectros en el espacio de
frecuencias.
Sean F (u, v) y H (u, v) las FFT de f (x , y) y h(x , y), respectivamente. Denotaremos a la operacion
de convolucion por ∗. El teorema de convolucion demuestra que f (x , y)∗h(x , y) y F (u, v)H (u, v)
constituyen un par FFT:
f (x , y) ∗ h(x , y) ⇔ F (u, v)H (u, v) (11.11)
Capıtulo 11. Filtros en el espacio de frecuencias 79
Figura 11.2: Filtros FFT
La flecha doble indica que la expresion de la izquierda (convolucion espacial) puede ser obtenida
tomando la FFT inversa de la expresion de la derecha (el producto en el espacio de frecuencias).
De la misma forma la expresion de la derecha se obtiene mediante la FFT de la expresion de la
izquierda. Un resultado analogo es que la convolucion en el espacio de frecuencias reduce a la
multiplicacion en la representacion espacial, y viceversa, es decir:
f (x , y)h(x , y) ⇔ F (u, v) ∗H (u, v) (11.12)
Estos dos resultados resumen el teorema de convolucion.
Entonces podemos sintetizar el proceso en los siguientes pasos (11.2):
1. Transformar una imagen al espacio de frecuencias mediante FFT
2. Multiplicar el espectro por una mascara
3. Aplicar la transformacion FFT inversa
Necesitamos crear la mascara. Existen dos metodos: uno es partir de una mascara en representa-
cion espacial y hacer la transformacion, y el otro directamente calcular la mascara en el espacio
de frecuencias.
Para utilizar una mascara en representacion espacial, se debe centrar esta en la imagen y comple-
tar con ceros de tal forma de cubrir la imagen. Luego, transformar esta mascara y multiplicarla
por la FFT de la imagen, mediante multiplicacion de complejos. Al resultado se le aplica la FFT
inversa. La imagen obtenida es la misma que si se hubiera hecho la convolucion en la represen-
tacion espacial con la mascara original. Este metodo se usa en general cuando se trabaja con
mascaras muy grandes.
La funcion imgFFTConvolve computa la convolucion en el espacio de frecuencias dada una
imagen ya transformada y una mascara en su representacion espacial, la que rellena y transforma
para efectuar el calculo. El resultado es una matriz compleja cuya FFT inversa es la imagen
resultado de la convolucion.
Capıtulo 11. Filtros en el espacio de frecuencias 80
Convolve
∆FFTMatrix
mask? : Image
width ′ = width = mask?.width
height ′ = height = mask?.height
let fft mask == fft(mask?) •(∀ x : dom matrix • matrix ′ x = matrix x ∗C fft mask .matrix x )
11.4. Filtros por frecuencia
Existen muchos tipos de filtros por frecuencia pero la mayorıa son una derivacion o combinacion
de los siguientes cuatro: pasobajo, pasoalto, bandpass y bandstop.
El filtro pasobajo deja pasar las frecuencias bajas atenuando las mas altas. El pasoalto, en cambio,
atenua las mas bajas mientras deja pasar las altas. Bandpass permite pasar sin modificaciones
una determinada banda de frecuencias, atenuando las frecuencias fuera del rango. Bandstop, por
el contrario, bloquea solo una banda especıfica de frecuencias, sin alterar aquellas fuera de esa
banda. Bandpass y bandstop se pueden obtener como combinacion de sustraccion y adicion de
los resultados de los filtros pasobajo y pasoalto.
Los filtros provistos por biOps son: imgFFTLowPass (filtro pasobajo) y imgFFTHighPass (filtro
pasoalto), que toman por argumento, ademas de la transformada de la imagen, un valor de
radio por el cual filtrar las frecuencias; imgFFTBandPass e imgFFTBandStop, que esperan la
transformada y dos valores de radio que delimitan la banda.
A modo de ejemplo se muestra el esquema que describe el filtro de pasoalto y se muestra una
aplicacion particular de este filtro (11.3).
HighPass
∆FFTMatrix
r? : R
width ′ = width
height ′ = height
∀ x : dom matrix | euclideanDistance(x , (width div 2, height div 2))≤ r?
• (matrix ′ x ).re = 0 ∧ (matrix′ x).im = 0
Capıtulo 11. Filtros en el espacio de frecuencias 81
(a) Imagen original (b) Filtro pasoalto con r=10
Figura 11.3: Filtro por frecuencia
Capıtulo 12
Operaciones morfologicas
Morfologıa significa “la forma y estructura de un objeto”, o “la colocacion e interrelacion entre
las partes de un objeto”. A diferencia de otras operaciones vistas en este trabajo, disenadas
para alterar la apariencia de una imagen, las morfologicas estan relacionadas con la forma, y la
morfologıa digital es una manera de describir o analizar la forma de un objeto digital.
La ciencia de la morfologıa digital es relativamente reciente, aunque basa sus conceptos en
la teorıa simple de conjuntos. Podemos pensar que las imagenes consisten en un conjunto de
elementos (pixels). Pueden usarse ciertas operaciones matematicas sobre este conjunto para
resaltar aspectos especıficos de las formas para, por ejemplo, ser contadas o reconocidas.
Las operaciones basicas, y que se trataran en este capıtulo, son la erosion, por la cual se borran
pixels de la imagen que cumplan con ciertas condiciones, y dilatacion, en donde se establece un
patron alrededor de un pixel. A partir de estas se definen la apertura u opening y la clausura o
closing.
Se trataran solo operaciones sobre dos tipos de imagenes: las denominadas binarias que corres-
ponden a las imagenes en “blanco y negro”, y las de canal unico, o de “escala de grises”. Las
imagenes de color podrıan tratarse como una generalizacion de escala de grises (trabajando so-
bre cada canal) o pensarse como dominios de aplicacion separados por color. En ambos casos,
los resultados que se obtienen hacen que sea realmente difıcil estructurarlos para llevar a cabo
una tarea particular. Sin embargo, este campo del procesamiento de imagenes esta creciendo
rapidamente.
12.1. Operaciones sobre imagenes binarias
Las operaciones morfologicas sobre imagenes binarias se basan en imagenes de dos niveles: el
valor de cada pixel pertenece a un conjunto de dos elementos que contiene solo el mınimo
y maximo aceptados (en nuestra especificacion, MinValue y MaxValue, respectivamente, y en
nuestra implementacion, 0 y 255). Este tipo de imagenes puede ser interpretado como un conjunto
matematico de pixels negros. Como cada pixel se identifica con sus coordenadas, decimos que
82
Capıtulo 12. Operaciones morfologicas 83
es un punto en un espacio bidimensional (E 2). Ası, por ejemplo, la imagen de la figura 12.1
puede representarse como {(0,0), (1,0), (1,1), (2,2)}, conjunto que llamaremos B1, para futuras
referencias.
Figura 12.1: Representacion grafica de una imagen binaria
12.1.1. Dilatacion binaria
Para definir la dilatacion en terminos de conjuntos, necesitamos antes algunas definiciones.
Se define a la traslacion de un conjunto A por el punto x como:
(A)x = {c | c = a + x , a ∈ A} (12.1)
Para nuestro ejemplo de la imagen de la figura 12.1, tomando x = (1, 2), tendrıamos que:
(B1)(1,2) = {(1, 2), (2, 2), (2, 3), (3, 4)}
La reflexion de un conjunto A se define como:
A = {c | c = −a, a ∈ A} (12.2)
que es en realidad una rotacion de A en 180o por el origen.
Tambien usaremos algunas definiciones conocidas de la teorıa de conjuntos:
Ac = {c | c /∈ A} (12.3)
A ∩ B = {c | c ∈ A ∧ c ∈ B} (12.4)
A ∪ B = {c | c ∈ A ∨ c ∈ B} (12.5)
A− B = {c | c ∈ A ∧ c /∈ B} (12.6)
La dilatacion del conjunto A por el conjunto B es:
A⊕ B = {c | c = a + b, a ∈ A, b ∈ B} (12.7)
donde A representa la imagen sobre la cual estamos trabajando y B un conjunto de pixels,
llamado elemento estructural, o simplemente ventana, y su composicion define la naturaleza de
la dilatacion. Para visualizarlo, sea B2 = {(0, 0), (0, 1)}. Tendremos que:
Capıtulo 12. Operaciones morfologicas 84
B1 ⊕ B2 = (B1 + {(0, 0)}) ∪ (B1 + {(0, 1)})
= B1 ∪ {(0, 1), (1, 1), (1, 2), (2, 3)}
= {(0, 0), (0, 1), (1, 0), (1, 1), (1, 2), (2, 2), (2, 3)}
La figura 12.2 grafica la operacion, mostrando el efecto causado para este caso.
(a) Original (b) 12.2(a)+ (0,0)
(c) 12.2(a)+ (0,1)
(d) 12.2(b)+ 12.2(c)
(e)Ven-tana
Figura 12.2: Dilatacion binaria
La forma en que se calcula la dilatacion nos hace conjeturar que puede ser definida como la union
de todas las traslaciones de los elementos de la ventana. Esto es:
A⊕ B =⋃b∈B
(A)b (12.8)
Como la dilatacion es conmutativa (pues esta definida en terminos de operaciones conmutativas),
podemos expresar la ecuacion 12.8 de la siguiente manera:
A⊕ B =⋃a∈A
(B)a (12.9)
Esto da un pista con respecto a la implementacion para el operador de dilatacion (en nuestro
codigo, imgBinaryDilation): cuando el centro de la ventana se alinea con un pixel negro de la
imagen, todos los pixels de la imagen que corresponden a un pixel negro de la ventana se marcan
para ser cambiados a negro. Cuando terminamos de recorrer la imagen, habremos marcado los
pixels que deben ser convertidos a negro. En general, y en nuestro caso particular, se usa un
buffer secundario (inicialmente en blanco) para ir cargando los valores de la imagen resultado.
Esto es beneficioso en terminos de tiempos de ejecucion, pero perjudicial en cuanto a uso de
memoria.
Una de las aplicaciones mas comunes para este tipo de operacion (y por la cual ha tomado este
nombre), es la de hacer que las zonas negras de una imagen crezcan, o se “dilaten”. Para ello
implementamos tambien la funcion imgStdBinaryDilation, que aplica el metodo anteriormente
analizado utilizando una ventana estandar igual a 0, con dimension pasada por parametro. Esta
operacion genera pixels negros alrededor de los ya existentes, “engrosando” de esta manera a los
objetos presentes. Un ejemplo concreto, utilizando la ventana estandar de dimension 5, puede
verse en la figura 12.3.
Capıtulo 12. Operaciones morfologicas 85
(a) Imagen original (b) Dilatacion con dimension 5
Figura 12.3: Dilatacion binaria
12.1.2. Erosion binaria
Ası como puede decirse que la dilatacion resulta en agregar pixels negros en los objetos de las
imagenes binarias (o hacerlos mas “gruesos” o “grandes”), la erosion resulta en sacar pixels
negros de los objetos (o hacerlos mas “finos” o “pequenos”).
Con los conceptos introducidos en la subseccion anterior, podemos definir la erosion de una
imagen A y un elemento estructural o ventana B como sigue:
A B = {c | (B)c ⊆ A} (12.10)
lo cual es el conjunto de pixels c tal que el elemento estructural B trasladado por c corresponde
al conjunto de pixels negros en A.
La definicion queda mas clara si analizamos la implementacion de la funcion (imgBinaryErosion):
en la imagen resultado se establecen a negro todos los pixels que hacen que la ventana en ese
lugar coincida en todos los lugares que corresponden a la imagen. Es decir, un pixel determinado
quedara en valor negro, si al centrar la ventana en el pixel, la ventana y la porcion de imagen
correspondiente coinciden en su totalidad.
Veamos un ejemplo: consideremos la imagen B1 y la ventana B2 vistas en la subseccion anterior
y calculemos B1 B2. Este conjunto es el de todas las traslaciones de B2 que alinean B2 sobre
un conjunto de pixels negros en B1. Luego, no es necesario considerar el total de traslaciones,
sino aquellas que situan el origen de B2 en algun miembro de B1. Tenemos cuatro con esas
caracterısticas:
Capıtulo 12. Operaciones morfologicas 86
(B2)(0,0) = {(0, 0), (0, 1)}
(B2)(1,0) = {(1, 0), (1, 1)}
(B2)(1,1) = {(1, 1), (1, 2)}
(B2)(2,2) = {(2, 2), (2, 3)}
De los cuales solo (B2)(1,0) queda incluido en B1 y, por consiguiente, aparecera en la erosion de
B1. En la figura 12.4 se muestra esta operacion.
(a) Original (b) Erosion (c)Ven-tana
Figura 12.4: Erosion binaria
Analogamente a la dilatacion, se implemento la funcion imgStdBinaryErosion, aplicacion parti-
cular de erosion utilizando una ventana estandar de dimension parametrizada. Una aplicacion
del metodo (para la figura 12.3(b)) puede verse en la figura 12.5.
(a) Imagen original (b) Erosion con dimension 3
Figura 12.5: Erosion binaria
12.1.3. Apertura y clausura binarias
A partir de las operaciones vistas en la subseccion anterior definiremos algunas mas, que son de
uso cotidiano en el procesamiento de imagenes digitales.
Es importante destacar que las operaciones de erosion y dilatacion no son inversas. Aunque haya
casos en que la aplicacion en cascada de estas operaciones resulte en la imagen original, no es
Capıtulo 12. Operaciones morfologicas 87
cierto en general. Las operaciones son duales en el siguiente sentido:
(A B)c = Ac ⊕ B (12.11)
La aplicacion de una erosion inmediatamente seguida de una dilatacion usando el mismo elemento
estructural se llama de apertura (en ingles, opening). En nuestro paquete puede encontrarse con
el nombre de imgBinaryOpening . Es un nombre descriptivo ya que pareciera que la operacion
tiende a “abrir” los pequenos espacios entre los objetos que se tocan en una imagen. Despues
de la aplicacion de apertura, los objetos parecen estar mejor aislados que en la imagen original.
Esta operacion puede ser util a la hora de contar o clasificar los objetos que se encuentran en
ella.
Otra aplicacion es la eliminacion de ruido. La operacion de erosion quitara los pixels aislados y
algunos bordes de los objetos, pero (la mayor parte de) estos ultimos podran ser recuperados con
la operacion de dilatacion, sin recuperar en este caso los pixels extranos agregados por el ruido.
Es necesario aclarar, de todas formas, que esta tecnica da buenos resultados para la eliminacion
de puntos negros, pero no hara lo propio con puntos blancos.
Una clausura (closing, en ingles) es similar a una operacion de apertura, salvo que la dilatacion
se realiza antes que la erosion. La funcion de biOps que implementamos a tal fin se denomi-
na imgBinaryClosing . La operacion tiende a “cerrar” o “rellenar” los pequenos espacios entre
objetos.
La clausura tambien puede usarse para suavizar los contornos de los objetos de una imagen y
disminuir la apariencia de “dentado” que suelen aparecer en los objetos de algunas imagenes,
sobre todo las que han pasado por un proceso de thresholding.
Para ambas operaciones, y al igual que en el caso de dilatacion y erosion, se han implementado las
variantes de aplicacion con ventana estandar: pueden usarse las funciones imgStdBinaryOpening
e imgStdBinaryClosing . Un ejemplo de cada una de estas funciones puede verse en la figura 12.6.
(a) Imagen original (b) Apertura (dim=3) (c) Apertura (dim=2) (d) Clausura (dim=3)
Figura 12.6: Apertura y clausura
Otra posibilidad es la aplicacion repetida de dilatacion seguido de la misma cantidad de aplicacio-
nes de erosion. Esta funcion fue implementada en biOps bajo en nombre de imgNDilationErosion
(imgStdNDilationErosion para la version de ventana fija), y para un valor n de aplicaciones, la
operacion resulta en el suavizado de irregularidades de tamano n.
Capıtulo 12. Operaciones morfologicas 88
La forma tradicional de aproximar la computacion de una apertura de profundidad n es realizar
n operaciones de erosion seguido de n aplicaciones de dilatacion. Esta operacion tambien fue im-
plementada, y se denomina imgNErosionDilation para el caso general, e imgStdNErosionDilation
para la version con ventana fija. Existen otros algoritmos que realizan esta misma operacion, pero
no seran tratados en este trabajo.
12.2. Operaciones sobre imagenes en escala de grises
El uso de imagenes en escala de grises para las operaciones vistas en la seccion anterior introduce
muchas complicaciones, tanto conceptuales como computacionales. La nocion alrededor de la
teorıa de conjuntos desaparece, puesto que los valores que pueden tomar los pixels se expande a
un rango notablemente mas grande.
Haremos un acercamiento intuitivo a las operaciones morfologicas, con la esperanza de que tengan
sentido aplicarlas para obtener resultados satisfactorios.
En las imagenes que consideramos en la seccion anterior, el valor de los pixels se restringıa al
maximo o mınimo permitidos. Estos valores se distinguıan uno del otro para aplicar las opera-
ciones de erosion y dilatacion. Es posible realizar una analogıa para las imagenes en escala de
grises.
Definimos la dilatacion en escala de grises de una imagen A con un elemento estructural S como
sigue:
(A⊕ S )[i , j ] = max{A[i − r , j − c] + S [r , c], [i − r , j − c] ∈ A, [r , c] ∈ S} (12.12)
Esta definicion puede computarse como sigue (implementacion de la funcion imgGrayScaleDilation):
1. Posicionar la ventana sobre el primer pixel de A
2. Computar la suma de los pares conformados por cada valor de la imagen con el pixel
correspondiente de la ventana
3. Buscar el maximo de estas sumas, y establecer este valor como pixel de salida
4. Repetir para todos los pixels de la imagen
Para esta implementacion debe tenerse presente que los valores pueden salirse del rango permi-
tido, en cuyo caso deberemos hacer el ajuste necesario para respetar nuestras especificaciones.
Podemos definir tambien la erosion en escala de grises de A con una ventana S , de modo tal
que respete la dualidad planteada en la ecuacion 12.11, de la siguiente manera:
(A S )[i , j ] = mın{A[i − r , j − c]− S [r , c], [i − r , j − c] ∈ A, [r , c] ∈ S} (12.13)
Capıtulo 12. Operaciones morfologicas 89
La implementacion para biOps (imgGrayScaleErosion) es similar a la de dilatacion: esta vez se
reemplaza el calculo del maximo de las sumas por el del mınimo de las restas de la ventana con
su correspondiente pixel de la imagen a erosionar.
Las operaciones de apertura (imgGrayScaleOpening) y clausura (imgGrayScaleClosing) se defi-
nen e implementan de la misma manera que las imagenes binarias, con la salvedad que se utilizan
las correspondientes versiones de las funciones de dilatacion y erosion.
El campo de aplicacion de estas ultimas operaciones es muy amplio. Se utilizan en la inspeccion
visual de objetos, ya que estos se tornan mas visibles en caso de ser elementos cortantes o muy
lustrados, que saturan de brillo la imagen. Tambien para remover brillos y oscuridades excesivas,
deteccion de bordes, reduccion de ruidos, segmentacion de texturas, distribucion de tamanos de
objetos y muchos mas.
Capıtulo 13
Clasificacion de imagenes
La clasificacion es un area importante dentro del analisis de imagenes, de aplicacion en campos
tales como la teledeteccion y el reconocimiento de patrones. En esta seccion se introduce el
concepto de clasificacion de imagenes digitales y se presentan distintas maneras de abordar el
problema.
Nuestro estudio se centra en los metodos de clasificacion no supervisados, y mas particularmente
en los algoritmos k-means e isodata. Tras una resena general sobre la clasificacion no supervisada,
se describen ambos algoritmos y se analizan diferentes implementaciones de k-means.
13.1. Conceptos
Dada una imagen, su clasificacion consiste basicamente en obtener una nueva imagen, del mismo
tamano y caracterısticas que la original, con la diferencia de que los valores de los pixels repre-
sentan una etiqueta que identifica la categorıa asignada a cada pixel. Es importante considerar
que no pueden aplicarse ciertas operaciones estadısticas a una imagen clasificada, ya que, pese a
ser digital, no es una variable cuantitativa sino cualitativa.
En el proceso de clasificacion digital se pueden distinguir las siguientes etapas:
1. Definicion de las categorıas (fase de entrenamiento)
Se trata de obtener el valor de pixel (o rango de valores) que identifica a cada categorıa.
Este objetivo se logra seleccionando una muestra de pixels de la imagen que representen,
adecuadamente, a las categorıas de interes. A partir de esos pixels se puede calcular el valor
medio y la variabilidad numerica de cada categorıa.
2. Agrupacion de los pixels de la imagen por categorıas (fase de asignacion)
Se trata de asociar cada uno de los pixels de la imagen a una de las clases previamente
seleccionadas. Esta asignacion se realiza en funcion de los valores de cada pixel. El resultado
sera una nueva imagen cuyos valores de pixel indican la categorıa a la cual ha sido asignado.
90
Capıtulo 13. Clasificacion de imagenes 91
En nuestra implementacion, los pixels resultado tienen el valor del pixel que representa a
la clase.
3. Comprobacion y verificacion de resultados
Toda clasificacion conlleva un cierto margen de error, en funcion de la calidad de los datos
o de la rigurosidad del metodo empleado. Es por ello que existen metodos de verificacion
estadıstica que permiten cuantificar el error y valorar la calidad final del trabajo y su
aplicabilidad operativa.
13.2. Clasificacion supervisada y no supervisada
Los metodos de clasificacion se pueden dividir en dos categorıas, supervisada y no supervisada, de
acuerdo a la forma en que son obtenidas las estadısticas de entrenamiento. El metodo supervisado
parte de un conocimiento previo de la imagen, a partir del cual se seleccionan las muestras para
cada una de las categorıas. Por su parte, el metodo no supervisado procede a una busqueda
automatica de grupos de valores homogeneos en la imagen. Queda al usuario, en este caso,
encontrar correspondencias entre esos grupos y sus categorıas de interes.
Suelen distinguirse dos tipos de clases: informacionales y espectrales. Las primeras son las que
constituyen la leyenda de trabajo que pretende deducir el interprete. Las segundas, correspon-
den a los grupos de valores espectrales homogeneos en la imagen, en funcion de ofrecer una
reflectividad similar.
Idealmente habrıa de producirse una correspondencia biunıvoca entre las dos, es decir, que a
cada clase de cobertura le corresponda un unico grupo espectral, y que cada grupo espectral
corresponda a una sola clase tematica. Este caso es poco frecuente. Normalmente se produce
alguna de las siguientes situaciones:
Una categorıa de cubierta se manifiesta en varias clases espectrales: bastarıa perfeccionar
el muestreo para corregir la dispersion espectral de cada clase, o subdividir la categorıa
informacional en varias subclases y fundirlas tras la clasificacion;
Dos o mas categorıas informacionales comparten una clase espectral: en este caso lo mas
razonable es optar por una clave mas general;
Varias clases informacionales comparten clases espectrales: frente a esta situacion se puede
intentar con las soluciones anteriores, pero tambien puede ser necesario reconsiderar la
estrategia.
Como se puede ver, el metodo supervisado pretende definir clases informacionales, mientras el
no supervisado tiende a identificar las clases espectrales presentes en la imagen.
En nuestro trabajo se opto por desarrollar e implementar dos algoritmos de clasificacion no super-
visada. En la siguiente seccion se describen, de forma mas detallada, los metodos no supervisados
en general y los algoritmos elegidos: K-means e Isodata.
Capıtulo 13. Clasificacion de imagenes 92
13.3. Metodos de clasificacion no supervisados
Estos metodos estan dirigidos a definir las clases espectrales presentes en la imagen. No implican
ningun conocimiento del area de estudio, por lo que la intervencion humana se centra mas en la
interpretacion que en la consecucion de los resultados.
Se asume que los valores de los pixels forman una serie de agrupaciones o conglomerados
(clusters), mas o menos nıtidos segun los casos. Estos grupos equivaldrıan a pixels con un com-
portamiento espectral homogeneo, y por tanto, deberıan definir clases tematicas de interes. Sin
embargo, como ya vimos, estas categorıas espectrales no siempre pueden equipararse a las clases
informacionales que el usuario pretende deducir, por lo que resta a este interpretar el significado
tematico de dichas categorıas espectrales.
La idea general se puede expresar mediante la especificacion en Z:
getCluster : Z × seqVALUE "VALUE
valueDistance : VALUE ×VALUE " R
Classification
input? : Image
k? : Z
clusters? : seq1 VALUE
output ! : Image
output !.width = input?.width
output !.height = input?.height
#clusters? = k?
∀ x : dom output !.v •let c == min{i : Z | 1≤ i≤ k? • valueDistance(input?.v(x), getCluster(i, clusters?))} •(∃ v : Z | getCluster(v , clusters?) = c • output !.v(x ) = v)
El metodo para definir los agrupamientos espectrales se basa en la seleccion de tres parametros:
Variables que intervienen en el analisis
En este contexto, las variables son las bandas de la imagen. Los casos son los pixels que
componen la imagen. En este espacio multivariado se trata de encontrar los grupos de pixels
con valores similares, para luego equipararlos con alguna de las clases informacionales de
nuestra leyenda.
Criterio para medir la similitud o distancia entre casos
Capıtulo 13. Clasificacion de imagenes 93
Para medir la similitud entre pixels se han propuesto diversos criterios. El mas utilizado
se basa en la distancia euclideana:
da,b =
√√√√ m∑i=1
(Ia,i − Ib,i)2 (13.1)
donde da,b denota la distancia entre dos pixels cualesquiera a y b; Ia,i y Ib,i los valores de
cada pixel en la banda i , y m el numero de bandas de la imagen.
Criterio para agrupar los casos similares
Las opciones son numerosas. En nuestro caso particular nos focalizamos en k-means e
isodata.
13.3.1. K-means
Dado un conjunto de n puntos (en nuestro caso particular, los pixels de la imagen) en un espacio
d -dimensional y un entero k , el problema consiste en determinar un conjunto de k puntos,
llamados centroides, tales que se minimiza la distancia cuadrada media entre cada punto y el
centroide mas cercano a este.
Este algoritmo, ademas de la imagen a clasificar, tiene por entrada un valor k , que representa el
numero de clusters a construir, y un entero maxit , que denota el numero maximo de iteraciones
a realizar.
El metodo de clasificacion por k-means se puede resumir en los siguientes pasos:
1. Inicializacion de centroides (un centroide es el valor medio de las muestras asociadas a un
cluster). Se toman k pixels aleatorios de la imagen.
2. Para cada pixel, encontrar el centroide mas cercano. Asociar el pixel al cluster correspon-
diente.
3. Si no hubo cambios en los clusters o se alcanzo el lımite de iteraciones, detenerse.
4. Recalcular los centroides y volver a 2.
Este algoritmo es popular debido a su simplicidad de implementacion, escalabilidad, velocidad
de convergencia y adaptabilidad. En la figura 13.1 se puede ver un ejemplo de su aplicacion. En
biOps hemos implementado tres versiones: imgKMeans, imgKDKMeans e imgEKMeans.
La primera es la implementacion directa del algoritmo a partir de la descripcion. Sin embargo
puede resultar lenta en determinados casos, debido principalmente al costo de encontrar los
vecinos mas cercanos (nearest neighbor search). Por esta razon decidimos analizar alternativas
para la codificacion de este metodo de clasificacion.
Al momento de buscar el centroide mas cercano la implementacion anterior revisa uno por uno
los k clusters. Sin embargo, existe una manera de estructurar la informacion de los centroides
Capıtulo 13. Clasificacion de imagenes 94
(a) Imagen original (b) Imagen clasificada. Las cla-ses que se podrıan deducir: zonaurbana, agua, vegetacion
Figura 13.1: Clasificacion por k-means
para evitar calcular la distancia a cada uno cada vez, guardando esos puntos en un kd-tree
[Moo91].
Sea un espacio acotado (bounding box ) de un conjunto de puntos en un espacio k-dimensional,
el menor hiperrectangulo que los contiene. Un kd-tree es un arbol binario, que representa una
subdivision jerarquica a traves de hiperplanos del espacio acotado correspondiente a un conjunto
de puntos dado. Cada nodo en un kd-tree tiene asociado un espacio cerrado (closed box ) dentro
del espacio acotado, llamado celda. La celda de la raız es el espacio que contiene a todos los
puntos del conjunto. Si una celda contiene a lo sumo un punto, entonces se trata de una hoja.
Caso contrario, estara dividida en dos hiperrectangulos por un hiperplano ortogonal. Los puntos
de la celda se ubican a un lado o al otro del hiperplano. De esta forma tenemos dos subceldas, los
hijos de la celda original (ver 13.2). Existen distintos criterios para elegir la coordenada por la
cual dividir una celda. En nuestra implementacion decidimos dividir una celda en la coordenada
de la dimension mas extendida (lo que tiende a producir regiones cuadradas).
A partir de un kd-tree, y dado un punto x , queremos encontrar el vecino mas cercano en el arbol.
Una primera aproximacion es inicialmente la hoja cuya celda contiene a x . En la figura 13.3(a),
x esta denotado por X y el punto dueno de la hoja que contiene a x esta coloreado en negro.
Como se puede ver en este caso, la primera aproximacion no es necesariamente el punto buscado
(i.e. no se trata del vecino mas cercano) pero al menos sabemos que cualquier potencial vecino
mas cercano debe estar mas proximo, y por lo tanto dentro del cırculo centrado en x y que tiene
por radio la distancia de x al dueno del nodo. Subimos entonces al padre del nodo actual. En
la figura 13.3(b), el nodo negro. Calculamos si es posible una solucion mas cercana que la que
tenıamos. En este caso no es posible, ya que el cırculo no interseca el espacio (sombreado) que
ocupa el otro hijo del nodo actual (el“hermano” de la hoja anterior). Si no puede existir un
vecino mas cercano en el otro hijo, el algoritmo sigue hacia arriba en el arbol. El proximo nodo
padre debera ser chequeado, es decir, considerar la distancia al punto dueno del nodo, puesto que
el area que le corresponde (norte de la lınea horizontal central) es intersecada por el cırculo. Esta
mecanica se aplica sucesivamente hasta alcanzar la raız del arbol. La descripcion del algoritmo
Capıtulo 13. Clasificacion de imagenes 95
(a) Arbol en 2 dimensiones. No se indican los pla-nos que dividen. El nodo (2,5) divide a lo largo delplano por la coordenada y=5 y el nodo (3,8) delplano por x=3
(b) Representacion del arbol anterior como un kd-tree
Figura 13.2: Kd-tree
para construir los kd-trees y efectuar la busqueda del vecino mas cercano, y algunos detalles de
implementacion se encuentran en [Moo91].
(a) Primer paso (b) Segundo paso
Figura 13.3: Nearest Neighbor Search
A partir de esta estructura de datos se implemento imgKDKMeans que utiliza el kd-tree para
realizar las busquedas de centroide mas cercano. Esta variante no significo una mejora notable,
ya que en general el numero de clusters no es alto (y por lo tanto el numero de centroides contra
los que comparar tampoco). Existe otra implementacion de k-means que no desarrollamos que
Capıtulo 13. Clasificacion de imagenes 96
utiliza kd-trees ligeramente modificados para mapear todos los puntos de la imagen y eficientizar
el algoritmo [KNW02].
Sin embargo, encontramos otra manera de optimizar el orden de complejidad de k-means [FSTR06].
En cada iteracion el algoritmo calcula la distancia entre cada punto y todos los centroides. ¿Por
que no usar la informacion de las iteraciones anteriores? Para cada punto podemos mantener la
distancia al centroide del cluster mas cercano. En la siguiente iteracion, calculamos la distancia
al nuevo centroide de ese cluster. Si la nueva distancia es menor o igual que la que habıamos
guardado, el punto se queda en el cluster y no hay necesidad de calcular la distancia con los
demas centroides.
La idea surge del hecho de que k-means descubre clusters de forma esferica, cuyo centro se va
moviendo a medida que se agregan puntos al cluster. Esto hace que el centro este mas cerca de
algunos puntos, y de esa forma, esos puntos cercanos permanecen en el cluster y no es necesario
encontrar la distancia a los otros clusters. Los puntos mas alejados pueden cambiar de cluster
y en esos casos sı se recalculan las distancias. La variante implementada bajo el nombre de
imgEKMeans realiza las 2 primeras iteraciones del algoritmo original y las siguientes aplicando
la mejora descripta.
13.3.1.1. Complejidad
El algoritmo k-means converge a un mınimo local. Antes de converger, se calculan los centroides
varias veces y se hace una redistribucion de todos los puntos de acuerdo a los nuevos centroides.
Esto tiene O(nkl), donde n esel numero de puntos, k el numero de clusters y l el numero de
iteraciones.
La variante que usa kd-trees para resolver la busqueda de vecino mas cercano no cambia el orden
de complejidad, pero tiene un mejor caso promedio ya que en el mejor caso se hacen O(log k)
inspecciones; aunque en el peor caso siguen siendo necesarias las k distancias. Ademas tiene por
desventaja el hecho de que es necesario reconstruir el arbol en cada iteracion y eso tambien tiene
un costo.
La ultima propuesta, para obtener los cluster iniciales requiere O(nk). Luego, algunos puntos se
mantienen en un cluster y otros cambian. Si un punto se mantiene en el cluster, esto requiere
O(1); caso contrario, requiere O(k). Si suponemos que la mitad de los puntos se cambian de
cluster, requiere O(nk/2); como el algoritmo converge a un mınimo local, el numero de puntos
que cambian de cluster decrece en cada iteracion. Entonces se espera que el costo total sea
nkl∑
i=1
1/i . Incluso para un numero grande de iteraciones, este valor es mucho menor que nkl , y
por lo tanto esta mejora nos provee aproximadamente un O(nk).
Capıtulo 13. Clasificacion de imagenes 97
13.3.2. Isodata
Este algoritmo puede ser considerado como una mejora al enfoque de k-means. Tambien busca
minimizar el error cuadratico asignando los pixels al centroide mas cercano. Sin embargo, a dife-
rencia del anterior, no se maneja con un numero fijo de clusters sino con k clusters, permitiendo
que k varıe en un intervalo que contiene la cantidad de clusters pedida por el usuario. Esta
situacion se debe a que se descartan los clusters con pocos elementos. Por otro lado, se combinan
clusters si hay muchos o si existen algunos muy cercanos (operacion merge). Tambien un cluster
se puede dividir si hay pocos clusters o si contiene pixels demasiado disımiles (operacion split).
Los parametros requeridos por Isodata son:
no clusters: numero deseado de clusters, y tambien el numero inicial.
min elements: mınimo numero de pixels requerido por cluster.
min dist: distancia mınima permitida entre los centroides de los clusters.
split sd: parametro que controla la division de clusters.
iter start: maximo numero de iteraciones de la primera parte del algoritmo.
max merge: maximo numero de combinaciones de clusters por iteracion.
iter body: maximo numero de iteraciones del loop principal del algoritmo.
El uso y significado de estos parametros se describen con mayor detalle a continuacion, junto
con los pasos del algoritmo:
1. Inicializacion de los centroides de los clusters.
2. Para cada pixel, encontrar el centroide mas cercano. Asociar el pixel al cluster correspon-
diente.
3. Calcular los centroides de los clusters resultantes.
4. Si al menos un cluster cambio y el numero de iteraciones es menos que iter start , volver a
2.
5. Descartar los clusters con menos de min elements pixels, y descartar esos pixels tambien.
6. Si el numero de clusters es mayor o igual que 2 ∗ no clusters, ir a 7 (merge); sino, ir a 8.
7. Si la distancia entre dos centroides es menor que min dist , combinar estos clusters y
actualizar el centroide; caso contrario, ir a 8. Repetir hasta max merge veces e ir a 8.
8. Si el numero de clusters es menor o igual a no clusters/2, o se trata de una iteracion impar
y el numero de clusters es menor que 2 ∗ no clusters, ir a 9 (split). Sino ir a 10.
Capıtulo 13. Clasificacion de imagenes 98
9. Encontrar un cluster que tenga desviacion estandar para alguna variable, digamos x , que
sea mayor que split sd . De no haber, ir a 10. Sino, calcular la media para x en el cluster.
Separar los pixels del cluster en dos conjuntos, uno conteniendo aquellos pixels en los que x
es mayor o igual que la media, y el otro aquellos en que x es menor. Calcular los centroides
de estos dos nuevos clusters. Si la distancia entre ellos es mayor o igual que 1,1 ∗min dist ,
reemplazar el cluster original por los dos creados; caso contrario, el cluster no se divide.
10. Si este paso ha sido ejecutado iter body veces o no hubo cambios en los clusters desde su
ultima ejecucion, detenerse. Sino, volver a 2.
La implementacion de este algoritmo en biOps esta dada por la funcion imgIsoData.
Capıtulo 14
Conclusiones
Este proyecto concluye con la publicacion del paquete biOps en los repositorios de R. La licencia
GPL garantiza, a quienes ası lo deseen, la posibilidad de usar, copiar, modificar y redistribuir
este paquete. Estimamos que se mantendra y mejorara su utilidad con el correr del tiempo, tanto
por nuestro aporte como el de los desarrolladores de R. La cooperacion que caracteriza a esta
filosofıa hace que quienes comulgamos con ella trabajemos por codigos de calidad y de constante
evolucion y correccion.
El paquete se encuentra disponible en http://cran.r-project.org/src/contrib/Descriptions/
biOps.html
Creemos que este trabajo resulto en un aporte importante a la comunidad R, y por extension a la
comunidad del Software Libre. Los antecedentes en el procesamiento de imagenes en R, como se
vio en la seccion 6.1 son escasos, y en su mayorıa aportan a aspectos muy especıficos o areas muy
particulares del manejo de imagenes. biOps, en este sentido, resulta un paquete multiproposito,
facilmente extensible y con una amplia gama de algoritmos.
Se estudiaron, analizaron, especificaron, implementaron y testearon procesamientos para la ma-
nipulacion de imagenes obteniendo operaciones:
geometricas
morfologicas
aritmeticas
logicas
de manipulacion de frecuencias
de tablas de reemplazo
de deteccion de bordes
de convolucion.
99
Capıtulo 14. Conclusiones 100
de clasificacion de imagenes
A lo largo del trabajo utilizamos diversas herramientas y lenguajes de programacion. Creemos
valido un breve comentario de los mas importantes:
El lenguaje R (tratado en el capıtulo 2) es muy poderoso y completo en lo que se refiere a
manipulacion de datos (principalmente numericos). Sus interfaces con otros lenguajes hacen
que sea modificable y extensible sin necesidad de demasiados conocimientos especıficos,
permitiendo aprovechar las ventajas de otros lenguajes, sobre todo si son compilados. El
hecho de ser interpretado lo hace un poco mas lento, como pudo verse en el analisis hecho
en 2.4, pero nos dejo una impresion general muy buena y satisfactoria.
La notacion Z (vista en el capıtulo 3) nos resulto util como herramienta de especificacion,
aunque debimos agregarle una representacion de reales para que la notacion no nos resultara
tan rebuscada. Ademas hemos evidenciado algunas falencias en su expresividad al tratar
de especificar ciertos comportamientos.
fuzz (seccion 3.4) es una herramienta muy practica para el chequeo de tipos de las especi-
ficaciones Z. Nos adaptamos muy rapidamente tanto a ella como a su paquete para el uso
en LATEX.
La comunidad R es muy grande y esta muy bien organizada. El equipo de desarrolladores
respondio nuestras consultas acerca de la publicacion de paquetes de manera rapida y
eficiente. Los comandos R facilitan mucho la tarea del programador: existen scripts para
instalacion, desinstalacion y control de la estructura de los paquetes que nos resultaron de
gran utilidad.
svn1, el sistema de control de versiones de Tigris2 y trac3, la wiki y sistema de seguimiento
de issues (asuntos, temas), nos resultaron muy practicos para la organizacion de nuestras
actividades y nuestros archivos.
El trabajo nos resulto muy entretenido y enriquecedor. El tratamiento digital de imagenes no es
un area que este en la currıcula de las materias de nuestra carrera; sin embargo, encontramos su
estudio y analisis muy natural y nos parecio una tarea sumamente agradable.
14.1. Trabajo futuro
El area del procesamiento digital de imagenes es muy amplia y esta en constante evolucion.
A lo largo del proceso de desarrollo de este trabajo fuimos estudiando muchas ramas de esta
ciencia, profundizando en aquellos aspectos que consideramos mas valiosos, de mayor interes y
que hicieran a la buena funcionalidad del paquete.
Por ello que muchas aplicaciones han quedado relegadas. A continuacion describimos los puntos
en que creemos conveniente focalizar el trabajo futuro de este proyecto:1http://subversion.tigris.org2http://www.tigris.org3http://trac.edgewall.org
Capıtulo 14. Conclusiones 101
Conversion entre espacios de color: Como vimos en 4.3, existen distintos modelos de color
que permiten trabajar sobre diferentes aspectos de una imagen. biOps se maneja actual-
mente en el espacio RGB, pero esta pensado incorporar funciones para el cambio entre
espacios, ademas de adaptar las funciones que sean necesarias para la manipulacion de las
distintas representaciones.
Seleccion manual de colores para las categorıas de clasificacion: Permitir modificar los
colores de las clases en el resultado segun la voluntad del usuario, para identificar con
tonos arbitrarios una categorıa espectral con su correspondiente categorıa informacional.
Interfaz grafica de usuario: La librerıa grafica Gtk ha sido portada a R, dando la posibi-
lidad de generar un entorno de trabajo mediante ventanas y botones haciendo mas facil
la experiencia del usuario. Al momento solo se ha implementado una ventana para ver las
imagenes que brinda informacion adicional, como las coordenadas y valores de los pixels
(ver 6.4).
Implementacion de nuevos algoritmos: Este trabajo se centro en areas especıficas, pero
existen caminos que no han sido explorados: reconocimiento de patrones, vision de maqui-
nas y un largo etcetera. Por otro lado, queda pendiente la implementacion de algoritmos de
clasificacion supervisada, y la posibilidad de combinar algunas de las funciones existentes
para obtener nuevos filtros, principalmente en el espacio de frecuencias.
Extender soporte de formatos de archivo: Actualmente se permite leer y escribir archivos
en formatos jpg (libjpeg) y tiff (libtiff), a traves de librerıas libres y portables; hay una
librerıa libre para el formato png (libpng) que no se incorporo. Serıa bueno considerar
tambien el uso de las librerıas de ImageMagick , que permitirıan ampliar el soporte de
formatos y el cambio de representaciones. Tambien existe la inquietud de leer archivos de
imagenes satelitales, multibandas.
Procesamiento de archivos grandes: Al trabajar con imagenes la necesidad de memoria para
su manipulacion hace difıcil operar con archivos muy grandes. En este sentido consideramos
que se podrıa evaluar alternativas para evitar cargar toda la imagen en memoria y optimizar
su uso en la implementacion.
14.2. Estadısticas
Algunos numeros de este proyecto:
∼1000 lıneas de especificacion
∼10500 lıneas de codigo (∼4100 en R, ∼6400 en C)
∼3300 lıneas de documentacion
∼1100 horas de trabajo
∼15 libros, ∼20 publicaciones y ∼70 paginas webs consultadas
Capıtulo 14. Conclusiones 102
∼20 herramientas, lenguajes y programas usados para codificar, especificar, testear y do-
cumentar
Apendice A
Profiling
En la seccion 2.4 hemos visto una comparacion entre implementaciones de diversos algoritmos
usando solamente codigo R y usando llamadas a codigo C. A continuacion se detallan estos
resultados:
% imgAdd
Each sample represents 0.15 seconds.
Total run time: 3557.25000000143 seconds.
Total seconds: time spent in function and callees.
Self seconds: time spent in function alone.
% total % self
total seconds self seconds name
99.64 3544.50 53.93 1918.35 "r_imgAdd"
22.53 801.30 22.53 801.30 "["
12.31 438.00 12.31 438.00 "[<-"
6.98 248.40 6.98 248.40 " <="
3.65 129.90 3.65 129.90 "+"
0.36 12.75 0.00 0.00 ".imgArithmeticOperator"
0.36 12.75 0.00 0.00 "imgAdd"
0.26 9.30 0.26 9.30 ".C"
0.24 8.55 0.24 8.55 ":"
0.05 1.80 0.05 1.80 "as.vector"
0.05 1.80 0.00 0.00 "array"
0.04 1.35 0.02 0.75 "imagedata"
0.03 0.90 0.00 0.00 "as.integer"
0.03 0.90 0.03 0.90 "as.integer.default"
% self % total
self seconds total seconds name
53.93 1918.35 99.64 3544.50 "r_imgAdd"
22.53 801.30 22.53 801.30 "["
12.31 438.00 12.31 438.00 "[<-"
6.98 248.40 6.98 248.40 " <="
3.65 129.90 3.65 129.90 "+"
0.26 9.30 0.26 9.30 ".C"
0.24 8.55 0.24 8.55 ":"
0.05 1.80 0.05 1.80 "as.vector"
0.03 0.90 0.03 0.90 "as.integer.default"
0.02 0.75 0.04 1.35 "imagedata"
% imgAverage
Each sample represents 0.15 seconds.
103
Apendice A. Profiling 104
Total run time: 2665.65000000089 seconds.
Total seconds: time spent in function and callees.
Self seconds: time spent in function alone.
% total % self
total seconds self seconds name
99.53 2653.20 48.85 1302.30 "r_imgAverage"
30.59 815.40 30.59 815.40 "["
16.19 431.70 16.19 431.70 "[<-"
3.48 92.85 3.48 92.85 "+"
0.47 12.45 0.04 1.05 "imgAverage"
0.33 8.85 0.33 8.85 ":"
0.16 4.35 0.08 2.10 "imagedata"
0.14 3.60 0.14 3.60 ".C"
0.09 2.40 0.09 2.40 "as.vector"
0.09 2.40 0.00 0.00 "array"
0.08 2.10 0.08 2.10 "/"
0.07 1.95 0.07 1.95 "list"
0.05 1.35 0.00 0.00 "as.integer"
0.05 1.35 0.05 1.35 "as.integer.default"
% self % total
self seconds total seconds name
48.85 1302.30 99.53 2653.20 "r_imgAverage"
30.59 815.40 30.59 815.40 "["
16.19 431.70 16.19 431.70 "[<-"
3.48 92.85 3.48 92.85 "+"
0.33 8.85 0.33 8.85 ":"
0.14 3.60 0.14 3.60 ".C"
0.09 2.40 0.09 2.40 "as.vector"
0.08 2.10 0.16 4.35 "imagedata"
0.08 2.10 0.08 2.10 "/"
0.07 1.95 0.07 1.95 "list"
0.05 1.35 0.05 1.35 "as.integer.default"
0.04 1.05 0.47 12.45 "imgAverage"
% r_dec_contrast
Each sample represents 0.15 seconds.
Total run time: 1977.90000000047 seconds.
Total seconds: time spent in function and callees.
Self seconds: time spent in function alone.
% total % self
total seconds self seconds name
99.79 1973.70 0.00 0.00 "r_dec_contrast"
99.78 1973.55 48.40 957.30 "r_look_up_table"
25.06 495.75 25.06 495.75 "["
25.02 494.85 25.02 494.85 "[<-"
1.27 25.05 1.27 25.05 "+"
0.21 4.20 0.00 0.00 "imgDecreaseContrast"
0.21 4.20 0.00 0.00 ".imgContrast"
0.10 1.95 0.08 1.65 "imagedata"
0.06 1.20 0.06 1.20 ".C"
0.05 0.90 0.05 0.90 "as.vector"
0.05 0.90 0.00 0.00 "array"
0.03 0.60 0.03 0.60 ":"
0.03 0.60 0.01 0.15 "as.integer"
0.02 0.45 0.02 0.45 "as.integer.default"
% self % total
self seconds total seconds name
48.40 957.30 99.78 1973.55 "r_look_up_table"
25.06 495.75 25.06 495.75 "["
Apendice A. Profiling 105
25.02 494.85 25.02 494.85 "[<-"
1.27 25.05 1.27 25.05 "+"
0.08 1.65 0.10 1.95 "imagedata"
0.06 1.20 0.06 1.20 ".C"
0.05 0.90 0.05 0.90 "as.vector"
0.03 0.60 0.03 0.60 ":"
0.02 0.45 0.02 0.45 "as.integer.default"
0.01 0.15 0.03 0.60 "as.integer"
% r_dec_intensity
Each sample represents 0.15 seconds.
Total run time: 1997.25000000048 seconds.
Total seconds: time spent in function and callees.
Self seconds: time spent in function alone.
% total % self
total seconds self seconds name
99.76 1992.45 0.00 0.00 "r_dec_intensity"
99.75 1992.30 47.71 952.80 "r_look_up_table"
25.61 511.50 25.61 511.50 "[<-"
24.89 497.10 24.89 497.10 "["
1.51 30.15 1.51 30.15 "+"
0.24 4.80 0.00 0.00 "imgDecreaseIntensity"
0.24 4.80 0.00 0.00 ".imgIntensity"
0.12 2.40 0.10 1.95 "imagedata"
0.06 1.20 0.06 1.20 ".C"
0.06 1.20 0.06 1.20 "as.vector"
0.06 1.20 0.00 0.00 "array"
0.04 0.75 0.04 0.75 ":"
0.03 0.60 0.01 0.15 "as.integer"
0.02 0.45 0.02 0.45 "as.integer.default"
0.01 0.15 0.00 0.00 "max"
% self % total
self seconds total seconds name
47.71 952.80 99.75 1992.30 "r_look_up_table"
25.61 511.50 25.61 511.50 "[<-"
24.89 497.10 24.89 497.10 "["
1.51 30.15 1.51 30.15 "+"
0.10 1.95 0.12 2.40 "imagedata"
0.06 1.20 0.06 1.20 ".C"
0.06 1.20 0.06 1.20 "as.vector"
0.04 0.75 0.04 0.75 ":"
0.02 0.45 0.02 0.45 "as.integer.default"
0.01 0.15 0.03 0.60 "as.integer"
% r_imgDiffer
Each sample represents 0.15 seconds.
Total run time: 3592.50000000145 seconds.
Total seconds: time spent in function and callees.
Self seconds: time spent in function alone.
% total % self
total seconds self seconds name
99.61 3578.40 53.47 1920.90 "r_imgDiffer"
22.99 825.75 22.99 825.75 "["
12.32 442.65 12.32 442.65 "[<-"
5.13 184.20 5.13 184.20 " <="
2.98 107.10 2.98 107.10 "<"
2.47 88.80 2.47 88.80 "-"
0.39 14.10 0.00 0.00 ".imgArithmeticOperator"
0.39 14.10 0.00 0.00 "imgDiffer"
0.29 10.35 0.29 10.35 ".C"
Apendice A. Profiling 106
0.25 9.00 0.25 9.00 ":"
0.05 1.95 0.05 1.95 "as.vector"
0.05 1.95 0.00 0.00 "array"
0.04 1.50 0.03 1.05 "imagedata"
0.02 0.75 0.00 0.00 "as.integer"
0.02 0.75 0.02 0.75 "as.integer.default"
% self % total
self seconds total seconds name
53.47 1920.90 99.61 3578.40 "r_imgDiffer"
22.99 825.75 22.99 825.75 "["
12.32 442.65 12.32 442.65 "[<-"
5.13 184.20 5.13 184.20 " <="
2.98 107.10 2.98 107.10 "<"
2.47 88.80 2.47 88.80 "-"
0.29 10.35 0.29 10.35 ".C"
0.25 9.00 0.25 9.00 ":"
0.05 1.95 0.05 1.95 "as.vector"
0.03 1.05 0.04 1.50 "imagedata"
0.02 0.75 0.02 0.75 "as.integer.default"
% r_gamma
Each sample represents 0.15 seconds.
Total run time: 1990.20000000048 seconds.
Total seconds: time spent in function and callees.
Self seconds: time spent in function alone.
% total % self
total seconds self seconds name
99.77 1985.70 0.01 0.15 "r_gamma"
99.77 1985.55 47.87 952.80 "r_look_up_table"
25.50 507.60 25.50 507.60 "["
24.97 496.95 24.97 496.95 "[<-"
1.39 27.60 1.39 27.60 "+"
0.23 4.50 0.00 0.00 "imgGamma"
0.11 2.25 0.08 1.50 "imagedata"
0.07 1.35 0.07 1.35 "as.vector"
0.07 1.35 0.00 0.00 "array"
0.06 1.20 0.06 1.20 ".C"
0.03 0.60 0.03 0.60 ":"
0.02 0.45 0.00 0.00 "as.integer"
0.02 0.45 0.02 0.45 "as.integer.default"
% self % total
self seconds total seconds name
47.87 952.80 99.77 1985.55 "r_look_up_table"
25.50 507.60 25.50 507.60 "["
24.97 496.95 24.97 496.95 "[<-"
1.39 27.60 1.39 27.60 "+"
0.08 1.50 0.11 2.25 "imagedata"
0.07 1.35 0.07 1.35 "as.vector"
0.06 1.20 0.06 1.20 ".C"
0.03 0.60 0.03 0.60 ":"
0.02 0.45 0.02 0.45 "as.integer.default"
0.01 0.15 99.77 1985.70 "r_gamma"
% r_inc_contrast
Each sample represents 0.15 seconds.
Total run time: 1989.60000000048 seconds.
Total seconds: time spent in function and callees.
Self seconds: time spent in function alone.
% total % self
Apendice A. Profiling 107
total seconds self seconds name
99.78 1985.25 47.72 949.35 "r_look_up_table"
99.78 1985.25 0.00 0.00 "r_inc_contrast"
25.59 509.10 25.59 509.10 "["
24.98 497.10 24.98 497.10 "[<-"
1.44 28.65 1.44 28.65 "+"
0.22 4.35 0.00 0.00 "imgIncreaseContrast"
0.22 4.35 0.00 0.00 ".imgContrast"
0.11 2.10 0.08 1.50 "imagedata"
0.06 1.20 0.06 1.20 ".C"
0.06 1.20 0.06 1.20 "as.vector"
0.06 1.20 0.00 0.00 "array"
0.05 1.05 0.05 1.05 ":"
0.02 0.45 0.00 0.00 "as.integer"
0.02 0.45 0.02 0.45 "as.integer.default"
% self % total
self seconds total seconds name
47.72 949.35 99.78 1985.25 "r_look_up_table"
25.59 509.10 25.59 509.10 "["
24.98 497.10 24.98 497.10 "[<-"
1.44 28.65 1.44 28.65 "+"
0.08 1.50 0.11 2.10 "imagedata"
0.06 1.20 0.06 1.20 ".C"
0.06 1.20 0.06 1.20 "as.vector"
0.05 1.05 0.05 1.05 ":"
0.02 0.45 0.02 0.45 "as.integer.default"
% imgIncreaseIntensity
Each sample represents 0.15 seconds.
Total run time: 2009.55000000049 seconds.
Total seconds: time spent in function and callees.
Self seconds: time spent in function alone.
% total % self
total seconds self seconds name
99.78 2005.05 0.00 0.00 "r_inc_intensity"
99.77 2004.90 47.74 959.40 "r_look_up_table"
25.33 508.95 25.33 508.95 "["
25.21 506.70 25.21 506.70 "[<-"
1.43 28.80 1.43 28.80 "+"
0.22 4.50 0.00 0.00 "imgIncreaseIntensity"
0.22 4.50 0.00 0.00 ".imgIntensity"
0.10 2.10 0.07 1.35 "imagedata"
0.07 1.50 0.07 1.50 "as.vector"
0.07 1.50 0.00 0.00 "array"
0.06 1.20 0.06 1.20 ".C"
0.05 1.05 0.05 1.05 ":"
0.03 0.60 0.00 0.00 "as.integer"
0.03 0.60 0.03 0.60 "as.integer.default"
0.01 0.15 0.00 0.00 "min"
% self % total
self seconds total seconds name
47.74 959.40 99.77 2004.90 "r_look_up_table"
25.33 508.95 25.33 508.95 "["
25.21 506.70 25.21 506.70 "[<-"
1.43 28.80 1.43 28.80 "+"
0.07 1.50 0.07 1.50 "as.vector"
0.07 1.35 0.10 2.10 "imagedata"
0.06 1.20 0.06 1.20 ".C"
0.05 1.05 0.05 1.05 ":"
0.03 0.60 0.03 0.60 "as.integer.default"
Apendice A. Profiling 108
% imgMaximum
Each sample represents 0.15 seconds.
Total run time: 2838.90000000099 seconds.
Total seconds: time spent in function and callees.
Self seconds: time spent in function alone.
% total % self
total seconds self seconds name
99.71 2830.80 21.69 615.75 "r_imgMaximum"
61.69 1751.25 31.25 887.25 "max"
30.43 864.00 30.43 864.00 "["
15.93 452.25 15.93 452.25 "[<-"
0.36 10.35 0.36 10.35 ":"
0.29 8.10 0.02 0.45 "imgMaximum"
0.11 3.00 0.11 3.00 ".C"
0.06 1.80 0.06 1.80 "list"
0.06 1.65 0.06 1.65 "as.vector"
0.06 1.65 0.00 0.00 "array"
0.05 1.50 0.04 1.05 "imagedata"
0.05 1.35 0.00 0.00 "as.integer"
0.05 1.35 0.05 1.35 "as.integer.default"
% self % total
self seconds total seconds name
31.25 887.25 61.69 1751.25 "max"
30.43 864.00 30.43 864.00 "["
21.69 615.75 99.71 2830.80 "r_imgMaximum"
15.93 452.25 15.93 452.25 "[<-"
0.36 10.35 0.36 10.35 ":"
0.11 3.00 0.11 3.00 ".C"
0.06 1.80 0.06 1.80 "list"
0.06 1.65 0.06 1.65 "as.vector"
0.05 1.35 0.05 1.35 "as.integer.default"
0.04 1.05 0.05 1.50 "imagedata"
0.02 0.45 0.29 8.10 "imgMaximum"
% imgNegative
Each sample represents 0.15 seconds.
Total run time: 1865.5500000004 seconds.
Total seconds: time spent in function and callees.
Self seconds: time spent in function alone.
% total % self
total seconds self seconds name
99.57 1857.60 43.70 815.25 "r_look_up_table"
99.57 1857.60 0.00 0.00 "r_negative_lut"
27.15 506.55 27.15 506.55 "[<-"
27.04 504.45 27.04 504.45 "["
1.65 30.75 1.65 30.75 "+"
0.28 5.25 0.00 0.00 "imgNegative"
0.15 2.85 0.10 1.95 "imagedata"
0.14 2.70 0.00 0.00 "r_negative"
0.14 2.70 0.14 2.70 "-"
0.10 1.80 0.10 1.80 "as.vector"
0.10 1.80 0.00 0.00 "array"
0.07 1.35 0.07 1.35 ".C"
0.03 0.60 0.03 0.60 ":"
0.01 0.15 0.00 0.00 "as.integer"
0.01 0.15 0.01 0.15 "as.integer.default"
% self % total
self seconds total seconds name
Apendice A. Profiling 109
43.70 815.25 99.57 1857.60 "r_look_up_table"
27.15 506.55 27.15 506.55 "[<-"
27.04 504.45 27.04 504.45 "["
1.65 30.75 1.65 30.75 "+"
0.14 2.70 0.14 2.70 "-"
0.10 1.95 0.15 2.85 "imagedata"
0.10 1.80 0.10 1.80 "as.vector"
0.07 1.35 0.07 1.35 ".C"
0.03 0.60 0.03 0.60 ":"
0.01 0.15 0.01 0.15 "as.integer.default"
% imgThreshold
Each sample represents 0.15 seconds.
Total run time: 1974.90000000047 seconds.
Total seconds: time spent in function and callees.
Self seconds: time spent in function alone.
% total % self
total seconds self seconds name
99.76 1970.25 47.84 944.85 "r_look_up_table"
99.76 1970.25 0.00 0.00 "r_threshold"
25.53 504.15 25.53 504.15 "["
24.84 490.50 24.84 490.50 "[<-"
1.54 30.45 1.54 30.45 "+"
0.24 4.65 0.00 0.00 "imgThreshold"
0.12 2.40 0.08 1.65 "imagedata"
0.07 1.35 0.07 1.35 "as.vector"
0.07 1.35 0.00 0.00 "array"
0.06 1.20 0.06 1.20 ".C"
0.02 0.45 0.00 0.00 "as.integer"
0.02 0.45 0.02 0.45 "as.integer.default"
0.02 0.30 0.02 0.30 ":"
% self % total
self seconds total seconds name
47.84 944.85 99.76 1970.25 "r_look_up_table"
25.53 504.15 25.53 504.15 "["
24.84 490.50 24.84 490.50 "[<-"
1.54 30.45 1.54 30.45 "+"
0.08 1.65 0.12 2.40 "imagedata"
0.07 1.35 0.07 1.35 "as.vector"
0.06 1.20 0.06 1.20 ".C"
0.02 0.45 0.02 0.45 "as.integer.default"
0.02 0.30 0.02 0.30 ":"
Bibliografıa
[Art96] R. D. Arthan. Arithmetics for Z. ICL, Febrero 1996.
[Bec90] Richard A. Becker. A brief history of S. AT&T Bell Laboratories - Murray Hill -
New Jersey, 1990.
[Chu96] Emilio Chuvieco. Fundamentos de teledeteccion espacial. Ediciones RIALP, 1996.
[Cra97] Randy Crane. A simplified approach to image processing. Prentice Hall, 1997.
[Dep95] Department of Computing, University of Brighton. Z Standards Document D-172,
Marzo 1995.
[FPWW94] Bob Fisher, Simon Perkins, Ashley Walker, and Erik Wolfart. Hypermedia image
processing reference, Marzo 1994.
[FSTR06] Fahim, Salem, Torkey, and Ramadan. An efficient enhanced k-means clustering
algorithm. Journal of Zhejiang University, 2006.
[GJJ96] Earl Gose, Richard Johnsonbaugh, and Steve Jost. Pattern recognition and image
analysis. Prentice Hall, 1996.
[GW02] Rafael Gonzalez and Richard Woods. Digital Image Processing. Prentice Hall, 2002.
[KNW02] Tapas Kanungo, Nathan Netanyahu, and Angela Wu. An efficient enhanced k-means
clustering algorithm: Analysis and implementation. IEEE Transactions on pattern
analysis and machine intelligence, 2002.
[Moo91] Andrew Moore. Efficient Memory-based Learning for Robot Control. An introductory
tutorial on kd-trees. PhD thesis, Carnegie Mellon University, 1991.
[Par96] J. R. Parker. Algorithms for image processing and computer vision. Wiley Computer,
1996.
[Spi98] J. M. Spivey. The Z Notation: a reference manual. Prentice Hall, 1998.
[Tea00] R Development Core Team. Introduccion a r, 2000.
[Tea06] R Development Core Team. Writing r extensions, 2006.
[WD95] Jim Woodcock and Jim Davies. Using Z. University of Oxford, 1995.
[ZWI] Wikipedia - Z Notation: http://en.wikipedia.org/wiki/Z notation.
110