Sistemas e Informática

A
Revista
nálisis dede la Facultad
la compresión de Ingeniería
de imágenes Industrial
utilizando clustering bajo el enfoque de colonia de hormigas
16(2): 118-131 (2013) UNMSM
ISSN: 1560-9146 (Impreso) / ISSN: 1810-9993 (Electrónico)

Análisis de la compresión de imágenes

utilizando clustering bajo el enfoque de
colonia de hormigas
María Elena Ruiz Rivera*
Juan Eduardo Yarasca Carranza**
Recibido: 03/12/13 Aceptado: 09/12/13
Edgar Ruiz Lizama***

1. Introducción
RESUMEN
Almacenar una imagen digital implica contar con un gran
El siguiente trabajo de investigación presenta espacio de memoria, y si se trata de varias imágenes se
una solución para el problema del alto costo de complica aún más. Por ello es deseable crear métodos
almacenamiento digital de las imágenes usadas
en diversos campos como ingeniería, medicina, y algoritmos que permitan realizar diferentes tipos de
educación, arquitectura, administración, trabajo (comprensión, clasificación, etc.) con imágenes y
entretenimiento, etc. videos, cuyo objetivo será reducir el espacio de memoria
La solución está basada en la aplicación u/o agilizar su procesamiento.
de un método de compresión utilizado en el
procesamiento de imágenes que es el de En la actualidad cuando se trabaja con grandes cantidades
clustering; en donde se usa el algoritmo de de imágenes se piensa en la comprensión de imágenes
colonia de hormigas, con la finalidad de reducir para reducir el espacio de almacenamiento.
el tamaño de la paleta de colores utilizada para
representar una imagen. Con ello se logra reducir
el tamaño de almacenamiento de la imagen sin
La Imagen Digital
que esto afecte la visualización de la misma por Una imagen digital es una representación bidimensional
parte de la persona.
de una imagen utilizando bits.
Palabras clave: imagen digital, mapa de bits,
compresión de imagen, clustering, algoritmo de
colonia de hormigas

Analysis of image understanding using

clustering under the approach of ant
colony

ABSTRACT
The following research paper presents a solution
to the problem of high cost of digital storage of
images used in various fields such as engineering,
medicine, education, architecture, management,
entertainment, etc.
The solution is based on the implementation of a
compression method used in image processing
is that of clustering, in which the algorithm ant
colony is used, in order to reduce the size of the
color palette used to represent an image. This Figura 1. Imagen Digital.
will reduce the storage size of the image without
affecting the display of the same by the person.
Fuente: Marcelo Ragone, Juan Pablo Vittori. 2006. Fotografía Digital.
Keywords: digital image, bits map, image Especialización en lenguajes artísticos combinados.
compression, clustering, ant colony algorithms

* Licenciada en Computación. Docente Asociada Facultad de Ingeniería de Sistemas e

Informática-UNMSM. E-mail: meruri@hotmail.com
** Ingeniero de Sistemas UNMSM.
*** Ingeniero Industrial, Magister en Informática. Docente Principal, Facultad de
Ingeniería Industrial UNMSM. E-mail: eruizl@unmsm.edu.pe

118 Ind. data 16(2), 2013

 Sistemas e Informática

María Elena Ruiz Rivera / Juan Eduardo Yarasca Carranza / Edgar Ruiz Lizama

Clustering
Clustering es el proceso de organizar objetos
en grupos y cuyos elementos sean similares de
alguna manera. Un cluster es una colección de
objetos “similares” entre ellos y que no lo son con
los objetos de otros clústeres [Matteucci, 2008].
Un criterio de similitud bastante usado es la
distancia: dos o más objetos pertenecen al mismo
cluster si están “cerca” de acuerdo con una
distancia dada, a esto se le llama distance – based
clustering.
Otra clase de clustering es el conceptual clustering,
en donde dos o más objetos pertenecen al mismo
clúster si uno de estos objetos define un concepto
común para todos los demás objetos.

Gráfica 2. Compresión Fractal.

Fuente: Benjamín Dugnol Álvarez, Ana María San Luis Fernández,

Doina Ana Cernea. Geometría Fractal. Universidad de Oviedo.
Departamento de Matemáticas. 2008. [Dugnol et al.,2008 ].

Gráfica 1. Clustering.
Cuantificación Vectorial
Fuente: Matteo Matteucci. 2008. Clustering: An Introduction La idea base de la cuantificación vectorial es la de
[Matteucci, 2008]. representar un vector N-dimensional que puede
tomar cualquier valor continuo en cada una de sus N
componentes mediante otro vector seleccionado de
Compresión de Datos entre un conjunto finito de vectores N-dimensionales
(Codebook) [Galindo, García, Barrientos, 1999].
La compresión de datos trata de reducir el número
de bits necesarios para representar la información
[Piñeiro, 2010]. Como ejemplo tenemos que para
representar digitalmente un segundo de video, sin
compresión, se necesitan más de 20 megabits y
para representar 2 minutos de un CD de música se
requieren más de 84 millones de bits. Actualmente
se han producido significativos avances
tecnológicos que permiten transmitir o almacenar
cantidades de información cada vez más grandes.
Sin embargo, parece que las necesidades crecen
con mayor rapidez que los avances tecnológicos en
cuestión y, por ello, las técnicas de compresión se Gráfica 3. Proceso de Cuantificación Vectorial
hacen imprescindibles.
Fuente: Pedro Galindo, Carmen García, Juan Barrientos (1999). La
cuantificación vectorial. pág. 8.

Ind. data 16(2), 2013 119

 Sistemas e Informática

Análisis de la compresión de imágenes utilizando clustering bajo el enfoque de colonia de hormigas

Algoritmo de Colonia de Hormigas de vehículos, enrutamiento de redes orientadas

El algoritmo de colonia de hormigas es un algoritmo a conexión, coloración de grafos, asignación de
para encontrar las rutas óptimas que se basa en frecuencias, asignación generalizada, enrutamiento
el comportamiento de las hormigas en busca de de redes ópticas, redundancia de asignación,
alimento [Viktor Macura, Ant Colony Algorithm]. satisfacción de restricciones [Dorigo y Stützel,
2005].
Al principio, las hormigas vagan al azar. Cuando una
hormiga encuentra una fuente de alimento, regresa
a la colonia dejando “marcadores” (feromonas)
que muestran el camino que lleva a los alimentos. 2. La mayoría de las técnicas estándares tratan la
Cuando otras hormigas vengan por las feromonas, cuantificación del color en las imágenes como un
es probable que sigan este camino. Si lo hacen, problema de agrupamiento (clustering) de puntos
a continuación dejan en el camino sus propios en el espacio tridimensional donde los puntos re-
marcadores al llevar la comida de regreso. presentan los colores encontrados en la imagen ori-
Debido a que las hormigas dejan sus feromonas ginal y los tres ejes son representados por los tres
cada vez que traen la comida, las rutas más cortas canales de color (rojo, verde y azul). Casi cualquier
son más propensas a ser más fuertes, por lo tanto algoritmo de agrupamiento en tres dimensiones se
optimizan la “solución”. Mientras tanto, algunas puede aplicar a la cuantificación de color, y vice-
hormigas siguen al azar la exploración de fuentes versa.
de alimento más cerca.
2.1. Taxonomía
Una vez que la fuente de alimento se agota, la
ruta ya no se llena con feromonas y lentamente se Según la clasificación establecida por la ACM
desintegra. (Association for Computing Machinery) [ACM,
1998], el tema a desarrollar en la tesis se
El trabajo de la colonia de hormigas en un sistema
encuentra en:
bastante dinámico, esto hace que funcione muy
bien en grafos con topologías de cambio.

2.2. Compresión

Debido a que los archivos de imagen pueden ocupar

mucha memoria volviéndose inmanejables, se han
Gráfica 4. Algoritmos de Hormigas. desarrollado diferentes técnicas de compresión.
Éstas tratan de reducir, mediante algoritmos
Fuente: Ant Algorithms, 2010 [Ant Algorithms, 2010].
matemáticos, el volumen del archivo para, así,
disminuir los recursos que consuma y abreviar el
El algoritmo de colonia de hormigas tiene diferentes tiempo de transferencia. Estos complejos algoritmos
aplicaciones entre las cuales tenemos el problema matemáticos reducen, de múltiples maneras, la
del agente viajero, el problema de asignación cantidad de 0 y 1 que conforman una imagen digital
cuadrática, problemas de horarios, enrutamiento [Ragone y Vittori, 2006b].

120 Ind. data 16(2), 2013

 Sistemas e Informática

María Elena Ruiz Rivera / Juan Eduardo Yarasca Carranza / Edgar Ruiz Lizama

diferentes técnicas, suavizando los degradados y

áreas que tienen un color similar, esto hace que
la falta de información sea más o menos invisible
a la vista. Este método permite un alto grado de
compresión.
En las aplicaciones más avanzadas es posible definir
entre distintos grados de compresión o pérdida al
crearse estos archivos. Hay que tratar de evitar la re
comprensión de imágenes ya comprimidas, ya que
esto implica sucesivas pérdidas de información. El
formato más utilizado de este tipo es JPEG.

2.4. Formatos de Archivos de Imágenes

2.4.1. Ventajas y Desventajas de los formatos de
archivos de imágenes
En la Tabla 1 se presenta un listado de archivos
de imágenes junto a sus ventajas y desventajas
obtenidas a partir de las definiciones previas.
2.4.2. Algoritmos utilizados en Compresión de
Imágenes
Algoritmo Median Cut
Gráfica 5. Compresión de Imágenes.
El concepto para aplicar el algoritmo de Median
Fuente: Neil Rhodes (2008). Photo Restoration Blog, accesado el 08 Cut es utilizar cada uno de los colores que se
de febrero del 2011. encuentran sintetizados en el mapa de colores
(colourmap) para representar un número igual
de píxeles de la imagen original. Este algoritmo
2.3. Tipos de Compresión subdivide en varias ocasiones en el espacio de
color en cajas rectangulares cada vez más y más
Los tipos de compresión según [Ragone y Vittori, pequeñas. Empezamos con una caja que encierra
2006c] se pueden clasificar en: los colores de todos los píxeles de la imagen
Sin Compresión original. El número de colores diferentes en el primer
cuadro depende de la resolución de color utilizado.
En este caso no se utiliza compresión, se logran Los resultados experimentales han mostrado que
los menores tiempos de decodificación de imagen, imágenes que tienen 15 bits / pixel (la resolución
y los archivos más grandes. Entre los formatos que del histograma) pueden ser cuantificados a 8 o
utilizan este método están TIFF, BMP, PSD, y GIF. menos bits / pixel y dicha cantidad de pixeles es
Compresión sin Pérdida suficiente en la mayoría de los casos, generando
poca degradación de la imagen original.
Esta técnica utiliza complejos algoritmos
matemáticos que logran condensar las cadenas En el algoritmo se aplica un paso iterativo, la
de código sin despreciar nada de la información división de una caja, la cual es reducida alrededor
que forma la imagen, por lo que esta se regenera de los colores que encierra, encontrando los valores
intacta al ser descomprimida. Esto implicará un mínimo y máximo de cada una de las coordenadas
cierto tiempo de codificación y decodificación. de color. El proceso de particionamiento adaptativo
se utiliza para decidir la forma de dividir la caja.
Un formato que utiliza este método es PNG.
Los puntos cerrados se ordenan a lo largo de la
Compresión con Pérdida dimensión más larga de la caja, y separadas en
dos mitades en el punto medio, aproximadamente
La compresión con pérdida implica que los
el mismo número de puntos recaerá en cada lado
algoritmos usados desechen información
del plano de corte.
supuestamente poco visible de la imagen. Así,
en los archivos comprimidos con este método se El paso anterior se aplica de forma recursiva hasta
pierden parte de los datos de la imagen. Algunos que se generan K cajas. (Si se realiza un intento
formatos, como JPG, realizan esta pérdida con de dividir una caja que contiene un solo punto, el

Ind. data 16(2), 2013 121

 Sistemas e Informática

Análisis de la compresión de imágenes utilizando clustering bajo el enfoque de colonia de hormigas

Tabla 1. Matriz de ventajas y desventajas de algunos de los formatos de archivos de imágenes

Formato de
Ventajas Desventajas
Archivo

- Imágenes de hasta 16 millones de colores.

TIFF - Alto costo de almacenamiento en disco.
- Buena calidad de imagen.

- Permite imágenes de hasta 16 millones de colores.

- A mayor compresión de la imagen menor
JPEG - Compresión con buena calidad de imagen.
calidad tendrá.
- Formato universalmente aceptado.

- Permite gráficos de hasta 256 colores.

- Puede ser animado.
- Muy pocos colores.
GIF - Permite transparencias.
- Animaciones simples.
- Aceptado por la mayoría de navegadores y
herramientas gráficas.

- No es compatible con programas que no

PSD - Permite la composición de imágenes por capas.
sean de Adobe.

- Alto costo de almacenamiento en disco.

RAW - Flexibilidad de procesamiento. - No es portable, debe convertirse a un
formato más universal.

- No disminuye la calidad de la imagen con el - No aptos para codificar fotografías o videos

escalamiento. del “mundo real”.
EPS - Control con gran precisión de los elementos del - Necesidad de un computador potente para
dibujo. realizar los cálculos necesarios para formar la
- Permiten animación imagen final.

cuadro es reasignado para dividir el cuadro más Algoritmo NeuQuant

grande que se pueda encontrar [Paul Heckbert,
El algoritmo NeuQuant fue presentado por Anthony
1982].
Dekker en su artículo “Kohonen Neural Networks
En este método se pueden distinguir 4 fases en la for Optimal Colour Quantization” [Dekker, 1994] en
cuantificación de imágenes: 1994.
1. El muestreo de la imagen original para las En este método se utiliza a las redes neuronales
estadísticas del color. auto-organizadas de Kohonen para la cuantificación
2. La elección de un mapa de colores (colourmap) de las imágenes.
basados en las estadísticas del color. Las redes neuronales auto organizadas son
3. Mapear los colores originales hacia sus vecinos aquellas que en su entrenamiento no requieren
más cercanos en el mapa de colores. las salidas objetivo que se desean asociar a cada
patrón de entrada, será la red la que proporcione
4. Cuantificación y redibujo de la imagen. cierto resultado. La principal aplicación es
Las imágenes de Lena que se presentan han sido la realización de agrupamiento de patrones
cuantificadas utilizando el algoritmo Median Cut (clustering), visualización de datos y representación
empleando 16, 8, 4 y 2 bits / píxel [Mota et al., de densidades de probabilidad, es por tanto, la más
2001]. (Ver Gráfica 6). utilizada en el campo de la documentación.

122 Ind. data 16(2), 2013

 Sistemas e Informática

María Elena Ruiz Rivera / Juan Eduardo Yarasca Carranza / Edgar Ruiz Lizama

Gráfica 6. Algoritmo Median Cut

Fuente: Mota, Gomes, Cavalcante. 2001. Optimal Image Quantization, Perception and the Median Cut Algorithm. pág. 10.

Algoritmo K – Means 2. Se crean k clusters asociando cada observación

a la media más cercana, dichas particiones
El algoritmo fue propuesto por Stuart Lloyd en 1957
pueden representarse mediante el diagrama de
como una técnica de la Modulación Código – Pulso,
Voronoi.
pero no fue publicado hasta 1982, fecha en la que
presentó su artículo «Least square quantization 3. El centroide de cada cluster se convierte en la
in PCM» [Lloyd, 1982]. Este algoritmo también es nueva media.
conocido como el algoritmo de Lloyd.
4. Se repiten los pasos 2 y 3 hasta que se alcance
El algoritmo sigue los siguientes pasos: la convergencia.
1. Elegir las k – medias (means) iniciales en forma 5. La fórmula para asociar cada observación al
aleatoria. cluster correspondiente es la siguiente:

Ecuación 2: K – Means, Cluster

La fórmula para calcular el centroide en cada iteración es la siguiente:

1
mi(t +1) =
S i(t )
∑x j
x j ∈Si( t )
Ecuación 3: K – Means, Centroide

Ind. data 16(2), 2013 123

 Sistemas e Informática

Análisis de la compresión de imágenes utilizando clustering bajo el enfoque de colonia de hormigas

Gráfica 7. Algoritmo K – Means.

Ant – Based Clustering De donde k+ y k- que determinan la influencia de las

funciones vecindario f(i), la cual es una estimación
Ant – Based Clustering es un método heurístico
de la fracción de datos en el ambiente inmediato de
de clustering y ordenamiento inspirado en el
la hormiga y que dependiendo de la similitud que
comportamiento de las hormigas en la naturaleza.
exista la hormiga recogerá o soltará el ítem.
El primer algoritmo Ant – Based Clustering fue
propuesto por Deneubourg et al. en su artículo La probabilidad de recoger un ítem ppick(i) decrece
“The dynamics of collective sorting: Robot-like ants con f(i), desde 1 ( f(i) = 0 ) hasta ¼ ( f(i) = k+ ) y
and Ant-like robots”en 1991 [Deneubourg et al., menos cuando f(i) tiende a 1.
1991] para producir comportamiento de clustering
La probabilidad de soltar un ítem pdrop(i) se
en grupos de robots.
incrementa con f(i), desde 0 ( f(i) = 0) hasta ¼ ( f(i)
Según Handl et al. [Handl et al., 2003], las = k- ) y más cuando f(i) tiende a 1.
hormigas son modeladas como agentes simples
En la versión original del algoritmo la estimación
que se movilizan aleatoriamente en un cuadrado
se obtiene usando una memoria a corto plazo de
de ambiente toroidal. Los datos que van a ser
cada agente, la cual contenía la última ubicación
procesados son inicialmente posicionados
del último ítem procesado y esto sólo permitía la
aleatoriamente en el ambiente y que pueden ser
discriminación entre un grupo limitado de clases de
recogidos, trasladados y soltados por los agentes.
ítems.
El ordenamiento y agrupamiento de los datos se
Esta limitación fue superada por Lumer y Faieta
obtiene introduciendo un sesgo para las operaciones
[Lumer y Faieta, 1994], en donde considera el
de recoger y soltar los ítems de datos. Los ítems
promedio de similitud entre el ítem i con todos los
que son rodeados por otros ítems diferentes tienen
ítems j dentro de su vecindad. La función f(i) es
mayor probabilidad de ser recogidos por los agentes
calculada mediante:
y transportados a la vecindad donde se encuentran
los similares con características similares.
Deneubourg et al.[Deneubourg et al., 1991]  1  d (i, j )  
presentan las siguientes funciones en donde se f (i ) = max 0, 2 ∑ 1 − α  

definen las funciones de probabilidad de recoger o  σ j

soltar un ítem.
En donde d(i,j) Є [0,1] es la función de disimilitud
2
definida para 2 puntos de data en el espacio
 k+  calculada como la función coseno, α Є [0,1] es un
p pick (i ) =  +  parámetro de escalamiento dato – dependiente, σ2
 k + f (i )  es el tamaño del vecindario local, generalmente σ2
Є [9, 25].
 f (i ) 
2

p drop (i ) =  −  El agente es colocado en el centro de su vecindario

 k + f (i )  local y cuyo radio de percepción en todas las
direcciones es (σ-1)/2.

124 Ind. data 16(2), 2013

 Sistemas e Informática

María Elena Ruiz Rivera / Juan Eduardo Yarasca Carranza / Edgar Ruiz Lizama

Gráfica 8. Ant – Based Clustering.

Fuente: Deneubourg et al., The dynamics of collective sorting: Robot-like ants and Ant-like robots. (Deneubourg et al., 1991).

2.5. Casos de Éxito del Algoritmo de Colonia de Yoon. Ellos proponen un algoritmo de clustering
Hormigas que imite el ecosistema teniendo en cuenta
las características de datos biológicos con la
Dentro de los casos en que se ha aplicado con éxito
finalidad de mejorar el proceso de análisis de
el algoritmo de colonia de hormigas tenemos:
los chips o micro arreglos de ADN, para ello han
a) Desarrollo de una aplicación para la gestión, implementado un sistema utilizando el algoritmo
clasificación y agrupamiento de documentos de colonia de hormigas. El sistema determina el
económicos con algoritmos bio-inspirados número de clústeres automáticamente, procesa
[Cobo y Rocha, 2007], este trabajo fue los datos biológicos de entrada, para luego
desarrollado por Ángel Cobo y Rocío Rocha, ejecutar el algoritmo de colonia de hormigas,
en el cual desarrollan una aplicación Web que asignar a los grupos genes y finalmente mostrar
utiliza técnicas bio-inspiradas para clasificar y el resultado. Se ha probado el algoritmo con una
agrupar colecciones multilingües de documentos base de datos de prueba de 100 y 1000 genes
en el campo de la economía y los negocios. La las cuales muestran resultados prometedores
aplicación identifica grupos relacionados de para la aplicación de este algoritmo para agrupar
documentos económicos, escritos en español los datos de chips de ADN.
e inglés, utilizando algoritmos de clustering
c) Enrutamiento Multicast Multiobjetivos
inspirados en el comportamiento de las colonias
basado en Colonia de Hormigas [Pinto et
de hormigas. Para la generación de una
al., 2005], desarrollado por Diego Pinto, Hugo
representación vectorial de los documentos que
Estigarribia, y Benjamín Barán. En su trabajo
resulte independiente del idioma, se utilizan
presentan a los algoritmos de optimización
varios recursos lingüísticos y herramientas
basados en Sistemas de Colonias de Hormigas
de procesamiento de documentos textuales.
(Ant Colony Optimization - ACO) como métodos
Cada documento es representado utilizando
meta-heurísticos recientes, inspirados en el
cuatro vectores de rasgos independientes del
comportamiento de colonias de hormigas
idioma, y la similitud entre ellos es calculada
reales. Proponen un algoritmo mult iobjetivo,
mediante combinaciones lineales convexas de
para la resolución del problema de Enrutamiento
las similitudes de esos vectores de rasgos.
Multicast en Ingeniería de Tráfico, denominado
b) An Ant-based Clustering System for Multi objective Ant Colony System (MOACS),
Knowledge Discovery in DNA Chip Analysis que está basado en ACO y que es utilizado
Data [Lee et al., 2007], este trabajo ha sido para la construcción del árbol multicast, en
desarrollado por Minsoo Lee, Yun-mi Kim, el contexto de transmisión de datos en redes
Yearn Jeong Kim, Yoon-kyung Lee, Hyejung de computadoras. El MOACS optimiza de

Ind. data 16(2), 2013 125

 Sistemas e Informática

Análisis de la compresión de imágenes utilizando clustering bajo el enfoque de colonia de hormigas

manera simultánea tres parámetros: el costo la aplicación del procedimiento presupone la

del árbol multicast, el retardo promedio y el reducción de los recorridos en la distribución de
retardo máximo (de origen a destino) y obtiene mercancías de Los Portales S.A. en el orden del
como resultado un conjunto de soluciones 30%, lo que trae consigo un ahorro aproximado
óptimas, a las que denominan conjunto Pareto. de más de 800 dólares al mes y 10 mil dólares
Los resultados experimentales obtenidos al año.
con el MOACS fueron comparados con el
Multio bjective Multicast Algorithm (MMA) que
demostró ser un excelente algoritmo evolutivo 3. Almacenamiento de Datos
basado en el SPEA. Esta comparación muestra
El almacenamiento de datos agrupa dispositivos
que el MOACS presenta mejores soluciones
de hardware y software dedicados a guardar,
que las arrojadas por el MMA, indicando que los
administrar y buscar los datos[Glosario.net, 2006].
algoritmos basados en colonias de hormigas
son muy prometedores en la resolución de En relación al hardware existen diferentes tipos de
problemas multi objetivos. dispositivos de almacenamiento: discos, disquetes,
discos ópticos, cintas, cartuchos, etc. Cada uno de
d) Optimización por Colonia de Hormigas
ellos tiene ventajas e inconvenientes, y resultan más
para la Asignación Dinámica de Recursos
o menos adecuados para diferentes utilizaciones.
en una Plataforma de Experimentación de
Temperatura Multizona [Muñoz et al., 2007], En relación al software se tiene los sistemas
este trabajo fue desarrollado por Mario Muñoz, manejadores de datos (DBMS) los cuales les
Jesús López y Eduardo Caicedo, en el cual permiten a los usuarios definir, consultar y modificar
presentan un algoritmo basado en el Ant System los datos.
para la asignación dinámica de recursos en una
plataforma de experimentación con múltiples
entradas y salidas. Esta plataforma, que emula 4. Definición del problema
una grilla de temperatura, está compuesta por El continuo avance en la tecnología de las
múltiples sensores y actuadores organizados telecomunicaciones ha conllevado a un aumento en
en zonas. El uso del algoritmo de colonia de la demanda del uso de imágenes, audio y video en
hormigas en esta aplicación permite asignar las diversas actividades cotidianas [Ross Dawson,
dinámicamente el tiempo de encendido de un 2007].
actuador en la plataforma de experimentación
de temperatura multizona para lograr una Esto ha generado ciertos aspectos a tener
temperatura uniforme sobre una área en en cuenta como el elevado tiempo empleado
particular, lo que permitió obtener una para la transmisión de datos y el alto costo de
temperatura uniforme sobre la plataforma. almacenamiento de este tipo de archivos [Seagate,
2008], el problema abordado en la presente tesis
e) Selección de rutas de distribución utilizando
estará vinculado al almacenamiento de imágenes.
optimización por colonia de hormigas
[Feitón y Cespón, 2009], trabajo desarrollado
por Michael Feitó y Roberto Cespón, en donde 5. Objetivos
se enfocan en el diseño y aplicación de un
procedimiento metaheurístico para la selección Objetivos Generales
de rutas de distribución en la sucursal Villa Clara
−− Realizar un análisis de los diferentes algoritmos
de Almacenes Universales S.A., que permita la
que emplee el método de clustering bajo el
reducción de los costos de transporte y un mejor
enfoque de colonia de hormigas, con la finalidad
tiempo de entrega a partir de la optimización
de solucionar el problema de almacenamiento
de las distancias a recorrer. Para lograr este
digital de imágenes.
objetivo implementaron un algoritmo basado
en la optimización por colonias de hormigas,
Objetivos Específicos
llamado AntHill 0.1 el cual brinda soluciones
óptimas a problemas de diversas magnitudes en −− Conocer el funcionamiento de los algoritmos de
un tiempo aceptable. La ejecución del software cuantificación que se utilizan actualmente y que
aplicado a varios casos reales y comparados puedan servir de base para obtener una paleta
con la documentación de la empresa arrojó que de colores reducida.

126 Ind. data 16(2), 2013

 Sistemas e Informática

María Elena Ruiz Rivera / Juan Eduardo Yarasca Carranza / Edgar Ruiz Lizama

Gráfica 9. Almacenamiento de datos.

Fuente: Seagate (2008). ¿Qué capacidad de almacenamiento necesitan sus cliente?

6. Justificación desarrollo se realizarán diversas actividades como

Es poder dar solución a la problemática del revisión bibliográfica, estudio del marco teórico, la
almacenamiento y transmisión de contenidos revisión del estado del arte, selección de la técnica
multimedia, especialmente de imágenes, los a usar, desarrollo de la propuesta y la redacción de
cuales son muy utilizados en los distintos campos las conclusiones.
de nuestra vida diaria, como por ejemplo en la
medicina, arquitectura, ingeniería, administración,
educación, entretenimiento, etc. [Tom Smith, 2008]. 8. Desarrollo de la Solución o del
Estudio

7. Propuesta AporteTeórico
La propuesta es desarrollar un aporte teórico –
práctico (conocimientos y herramienta tecnológica) Comparación de Algoritmos de Clustering
en el tema de codificación de imágenes basadas en Para analizar las ventajas y desventajas de
algoritmos de clustering. cada algoritmo de clustering presentados en
El desarrollo de este aporte se dará de manera la tesis he elaborado los siguientes cuadros
periódica e incremental, durante este proceso de comparativos.

Ind. data 16(2), 2013 127

 Sistemas e Informática

Análisis de la compresión de imágenes utilizando clustering bajo el enfoque de colonia de hormigas

Tabla 2. Comparación cualitativa de algoritmos de clustering.

ALGORITMO VENTAJAS DESVENTAJAS

- Soluciones poco óptimas.

- Simplicidad de implementación.
- Generación de codebook limitada.
Median Cut - Poco uso de recursos de memoria
- No cuenta con procesamiento en
y procesador de la PC.
paralelo.

- Excesivo tiempo para llegar a la

solución final cuando se maneja
- Simplicidad de implementación. gran cantidad de data.
K-Means - Técnica muy usada en la - Posibilidad de la no convergencia
identificación de patrones. del método.
- No cuenta con procesamiento en
paralelo

- Necesidad de un tiempo para el

- Aprendizaje adaptativo.
entrenamiento de la red neuronal.
- Tolerancia a fallos.
NeuQuant - Gran coste de recursos de
- Dinámico.
memoria y procesador de la PC.
- Procesamiento paralelo.
- Implementación complicada.

- Procesamiento paralelo.
- Mejora constante del algoritmo.
- Complejidad de implementación
Ant Based Clustering - Auto-organización.
media.
- Algoritmo robusto.
- No necesitan información a priori.

Tabla 3. Primera comparación cuantitativa de algoritmos de clustering

Algoritmos

Ítem Median Cut K – Means NeuQuant Ant – Based Clustering

Ponde- Ponde- Ponde-

Peso Valor Peso Valor Ponde-rado Peso Valor Peso Valor
rado rado rado

Robustez 0.35 1 0.35 0.35 2 0.70 0.35 2 0.70 0.35 3 1.05

Paralelismo 0.30 1 0.30 0.30 1 0.30 0.30 3 0.90 0.30 3 0.90

Eficacia 0.35 1 0.35 0.35 2 0.70 0.35 3 1.05 0.35 3 1.05

Totales 1.00 3 1.00 1.00 5 1.70 1.00 8 2.65 1.00 9 3.00

Leyenda:

Descripción Valor
Baja 1
Media 2
Alta 3

128 Ind. data 16(2), 2013

 Sistemas e Informática

María Elena Ruiz Rivera / Juan Eduardo Yarasca Carranza / Edgar Ruiz Lizama

De este cuadro se elegirá el algoritmo cuyo valor algoritmo Ant – Based Clustering que tiene de
ponderado sea el mayor,lo que representaráque valor ponderado 3.00, el cual es superior al de los
el algoritmo otorga mayor beneficio frente a demás algoritmos de la tabla.
los demás algoritmos. En este caso se elige el

Tabla 4. Segunda comparación cuantitativa de algoritmos de clustering

Algoritmos

Median Cut K – Means NeuQuant Ant – Based Clustering

Ítem
Ponde- Ponde- Ponde- Ponde-
Peso Valor Peso Valor Peso Valor Peso Valor
rado rado rado rado

Complejidad de
0.3 2 0.6 0.3 2 0.6 0.3 3 0.3 0.3 2 0.6
implementación

Uso de recursos
0.3 2 0.6 0.3 2 0.6 0.3 3 0.9 0.3 2 0.6
computacionales

Tiempo de
0.3 2 0.6 0.3 2 0.6 0.3 3 0.9 0.3 2 0.6
procesamiento

Necesidad de
0.1 1 0.1 0.1 1 0.1 0.1 3 0.1 0.1 1 0.1
información a priori

Totales 1.0 12 1.9 1.0 12 1.9 1.0 10 2.2 1.0 12 1.9

Leyenda:

Descripción Valor
Baja 1
Media 2
Alta 3

De este cuadro se elegirá el algoritmo cuyo valor las mejores condiciones para la implementación
ponderado sea el menor,lo que representaráque de un sistema de compresión de imágenes. Este
el algoritmo otorga menores costos en cuanto a sistema usará dicho algoritmo para localizar los
tiempo y esfuerzo empleados en la implementación colores característicos o predominantes de una
del mismo frente al de los demás algoritmos. En imagen, lo que dará origen al Codebook que será
este caso los algoritmos con menor ponderado utilizado en el proceso de cuantificación vectorial
sonel algoritmo Median Cut, el algoritmo K - Means al que será sometida la imagen. Para disminuir el
y el algoritmo Ant – Based Clustering los cuales error de cuantificación que se genera durante el
presentan un valor ponderado de 1.9. proceso se utilizará un algoritmo de dithering del
De las comparaciones realizadas se puede observar tipo error-difusión con el cual se distribuirá dicho
que el algoritmo Ant – Based Clustering presenta error en los píxeles vecinos de la imagen.

Ind. data 16(2), 2013 129

 Sistemas e Informática

Análisis de la compresión de imágenes utilizando clustering bajo el enfoque de colonia de hormigas

Conclusiones y Trabajos Futuros [2] [Ragone y Vittori, 2006b] Marcelo Ragone, Juan
Las conclusiones que he llegado en el desarrollo de Pablo Vittori. Fotografía Digital. Especialización
la tesis son las siguientes: en Lenguajes Artísticos Combinados. Instituto
Universitario Nacional de Arte. 2006. Buenos
−− El continuo avance en la tecnología de las Aires, Argentina. Pp 3-5.
telecomunicaciones ha conllevado a un el
aumento en la demanda del uso de imágenes, [3] [Ragone y Vittori, 2006c] Marcelo Ragone, Juan
audio y video en las diversas actividades Pablo Vittori. Fotografía Digital. Especialización
cotidianas como por ejemplo en la medicina, en Lenguajes Artísticos Combinados. Instituto
arquitectura, ingeniería, administración, Universitario Nacional de Arte. 2006. Buenos
educación, etc., esto ha generado ciertos Aires, Argentina. Pp 5-6.
aspectos a tener en cuenta debido a su alto
costo computacional, por un lado se tiene la [4] [Mota et al., 2001] Cicero Mota, Jonas Gomes
transmisión de los contenidos multimedia y por y María I. A. Cavalcante. Optimal Image
el otro su almacenamiento. Quantization, Perception and the Median
Cut Algorithm. Instituto de Ciencias Exactas.
−− La solución para estos problemas es utilizar una
Universidad del Amazonas. 2001. Manaus,
técnica de compresión basada en la clustering
Brasil. Pp. 14.
la cual consiste, en el caso de las imágenes, en
mapear una imagen original a full color, en otra [5] [Paul Heckbert, 1982] Paul S. Heckbert. Color
imagen que tenga una paleta de colores mucho Image Quantization for Frame Buffer Display.
más reducida que la de la imagen original y Laboratorio de Computación Gráfica del Intituto
además que las diferencias de percepción visual de Tecnología de New York. 1982. USA. Pp.
entre estas 2 imágenes sean mínimas. 4-8.
−− El algoritmo de compresión basado en colonia [6] [Piñeiro, 2010] Teoría de la Información y
de hormigas que se presenta en este artículo Codificación. Cándido Piñeiro Gómez. 2010.
permite reducir el peso de las imágenes en
Cap. I, Pp. 2.
aproximadamente un 66.41% sin afectar
drásticamente la percepción visual de las [7] [Dorigo y Stützel, 2005] The Ant Colony
mismas. Optimization Metaheuristic: Algorithms,
Los trabajos futuros que se pueden plantear a partir Applications, and Advances. Marco Dorigo,
de esta tesis serían: Thomas Stützel . 2005. Pp 24.

−− La optimización del algoritmo de colonia de [8] [Dekker, 1994] Kohonen Neural Networks for
hormigas, para evitar el gran consumo de Optimal Color Quantization. Anthony Dekker.
recursos computacionales cuando se procese 1994.
mayor volumen de información.
[9] [Lloyd, 1982] Stuart Lloyd. Least Squares
−− El uso del paralelismo para mejorar el tiempo de Quantization PCM. IEEE Transactions on
procesamiento, especialmente en la generación Information Theory, Vol. It-28, No. 2, 1982.
del Codebook.
[10] [Deneubourg et al., 1991] J. L. Deneubourg,
−− Preparar al algoritmo para que sea capaz de S. Goss, N. Franks, A. Sendova-Franks,
recibir una imagen de entrada en cualquier C. Detrain, y L. Chrétien. The dynamics of
formato gráfico y pueda procesarla sin collective sorting: Robot-like ants and Ant-like
inconvenientes.
robots. Université Libre de Bruxelles, Bélgica;
University of Bath, Reino Unido, 1991.
REFERENCIAS BIBLIOGRÁFICAS [11] [Lumer y Faieta, 1994] E. Lumer y B. Faieta.
Artículos Diversity and Adaptation in populations of
clustering ants. 1994
[1] [Galindo, García, Barrientos, 1999] Pedro
L. Galindo, Carmen García López, Juan M. [12] [Handl et al., 2003] J. Handl, J. Knowles and M.
Barrientos Villar. La Cuantificación Vectorial. Dorigo. Strategies for the increased robustness
Escuela Superior de Ingeniería Universidad de of ant – based clustering, Université Libre de
Cádiz.1999. Cádiz, España. Pp. 2, 3. Bruxelles, Bélgica. 2003.

130 Ind. data 16(2), 2013

 Sistemas e Informática

María Elena Ruiz Rivera / Juan Eduardo Yarasca Carranza / Edgar Ruiz Lizama

Revistas [17] [ACM, 1998] ACM Computing Classification

[13] [Ross Dawson, 2007] Future of Media Report. System. Accesado el 28 de enero del 2013
Ross Dawson. Future Exploration Network. desde http://www.acm.org/about/class/ccs98-
2007. Sydney, Australia. Pp. 6. html
[14] [Tom Smith, 2008] Social Media Tracker Wave [18] [Viktor Macura, Ant Colony Algorithm] Viktor
3. Tom Smith. Universal McCann. 2008
Macura. Ant Colony Algorithm. Accesado el
[15] [Seagate, 2008] ¿Qué capacidad de 28 de enero del 2013 desde http://mathworld.
almacenamiento necesitan sus clientes?
wolfram.com/AntColonyAlgorithm.html
Seagate. EE.UU. 2008.
Web [19] [Dugnol et al., 2008] Benjamín Dugnol Álvarez,
Ana María San Luis Fernández, Doina Ana
[16] [Matteucci, 2008] Clustering: An Introduction.
Accesado el 28 de enero del 2013 desde Cernea. Geometría Fractal. Universidad de
http://home.dei.polimi.it/matteucc/Clustering/ Oviedo. Departamento de Matemáticas. Área
tutorial_html/ de Matemática Aplicada.

Ind. data 16(2), 2013 131