SEGMENTACIÓN DE IMÁGENES EMPLEANDO EL MÉTODO DE LA MONTAÑA Y SUSTRACTIVO PARA LA ACELERACIÓN DEL PROCESAMIENTO DE LOS ALGORITMOS K-MEANS Y C-MEANS

Eloisa Guevara Gómez
Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Omar Alejandro Sánchez Tello
Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Dra. Yesenia Eleonor González Navarro
Unidad Profesional Interdisciplinaria en Ingeniería y Tecnologías Avanzadas-IPN. México, D. F.

Abstract

This article describes the mountain algorithm and the subtractive algorithm, both used to initialize and improve the performance of the K-Means and C-Means algorithms. An application of these techniques in image segmentation is presented.

Key Words: Image segmentation, clustering, mountain Method, subtractive method, K-Means, C-Means, Fuzzy C-Means.

Introducción

La segmentación de imágenes consiste en agrupar cada uno de los pixeles de una imagen en regiones destacadas dentro de ella como lo son aquellas regiones que corresponden a ciertos objetos, superficies individuales, texturas y demás regiones. La segmentación de imágenes tiene diversas aplicaciones como lo son el reconocimiento de objetos, la compresión de imágenes, edición de imágenes y detección de bordes, por mencionar algunas.
El agrupamiento de datos o  también conocido como clustering es un método que permite la clasificación de datos mediante técnicas de identificación de las estructuras o composición de los datos, con el fin de agrupar en diversos cúmulos dichos datos [1]. El método de la Montaña y el método Sustractivo pretenden obtener una aproximación de los centros de cúmulos (clusters) iniciales, que serán empleados posteriormente por los algoritmos K-Means y C-Means [2]. Esto permite una aceleración y optimización  en el proceso de agrupamiento de los datos en comparación a un sistema que no utilice alguno de los dos algoritmos como proceso inicial.  

Método de la Montaña

El método de la Montaña está basado en crear una rejilla del espacio dimensional  sobre el cual se encuentran los datos [3], las intersecciones de las líneas de la rejilla representan nodos candidatos a centros de cúmulo, cabe resaltar que al contar con una rejilla con una distancia entre intersecciones más pequeña, la aproximación tiene una mayor exactitud; sin embargo se requiere de un mayor tiempo de procesamiento, por lo cual no es recomendable manejar distancias muy pequeñas. 

Figura 1. Ejemplificación de la rejilla de un espacio tridimensional.

El siguiente paso consiste en construir una función montaña  basada en la distribución de los datos cuyo valor máximo representa el primer centro del cúmulo donde se concentra la mayor cantidad de datos.  El conjunto n de  datos a analizar se representan por:

La siguiente ecuación crea la montaña:

donde es una constante positiva y d es la distancia euclidiana entre cada dato y cada intersección de la rejilla. El primer centro de cúmulo calculado está definido por la ecuación:

Después de esto, deben obtenerse los demás centros de cúmulo, por lo cual se deben de eliminar los efectos del centro de cúmulo que fue encontrado previamente. Para esto, se resta a la primer función de montaña calculada la matriz de las distancia del punto con el valor más alto con respecto a cada una de los cruces de la rejilla, ésta última multiplicada por el valor máximo de la función de la montaña anterior. 

Lo anterior está dado por la siguiente ecuación:

El paso anterior se repite hasta encontrar el número de centros de cúmulo  deseados o bien hasta que una condición de paro sea cumplida, dicha condición está dada por el cociente que resulta de dividir el primer valor máximo encontrado entre el penúltimo valor máximo encontrado, es decir, el valor del primer centro de cúmulo entre el penúltimo obtenido, este cociente debe ser menor a una cierta constante positiva la Ecuación 5 muestra la condición de paro.

En el ejemplo mostrado más adelante los parámetros utilizados fueron:
y la resolución de la rejilla es de 83=512 puntos.

Método Sustractivo

A diferencia del método de la Montaña, el método Sustractivo, en lugar de utilizar una rejilla, toma como referencia a cada uno de los puntos que son parte del conjunto de datos a analizar como posibles centros potenciales de cúmulos, lo cual ofrece resultados más precisos, ya que no aproxima a alguna intersección en la rejilla, sino a uno de los datos que son analizados [4]. El algoritmo del método sustractivo, consta de ecuaciones muy similares a las utilizadas en el método de la montaña, aunque presentan algunas diferencias. Ambos métodos construyen una función que representa la distribución de los datos, en este caso se llama medida de densidad y se define por la siguiente ecuación:

Donde ra  es una constante positiva, esta constante actúa como el radio que define el área de proximidad al centro potencial de cúmulo. Una vez obtenidas todas las medidas de densidad, se toma la de mayor valor, ésta será elegida como el centro de clúster, la siguiente ecuación define lo anterior.

El centro de cúmulo obtenido será definido como xc1. El siguiente paso a realizar para la obtención de los demás centros de cúmulo es  restar la medida de densidad para el centro de cúmulo encontrado anteriormente:

donde rb < ra , por lo tanto también es una constante positiva y de igual forma, es un radio que define el área de proximidad, en este caso, la proximidad al centro de cúmulo encontrado anteriormente, esta área tiene una reducción medible en la medida de densidad. Después del cálculo anterior, nuevamente se elige al valor más grande de la medida de densidad y este es el valor del nuevo centro de cúmulo, estos últimos dos pasos se repiten hasta encontrar la cantidad deseada de centros. En el ejemplo mostrado ra=1.8,   rb=8ra’ , ε =0.598. 

Desarrollo

Los algoritmos fueron implementados en el programa MATLAB®. Al final de este artículo se encuentra un vínculo para descargarlos. Se empleó la imagen de la Figura 2 con extensión .jpeg, en formato de color RGB y resolución 243 x 320 pixeles. 

Figura 2. Imagen a segmentar.

La Figura 3 muestra la distribución de valores de pixeles con componentes RGB y los centros encontrados por los métodos Sustractivo y Montaña respectivamente. Para el ejemplo seleccionado, se encontraron más centros utilizando los métodos Sustractivo y de Montaña, que únicamente utilizando los propuestos en el artículo donde sólo se emplearon K-Means y C-Means [1], esto se debe a que los métodos analizados en este artículo sirven especialmente para obtener centros potenciales de clusters, esa es su tarea principal, en cambio, la tarea esencial delos algoritmos K-Means y C-Means es el agrupamiento de los datos.
La Figura 4 muestra la imagen segmentada mediante los métodos de la Montaña y Sustractivo y sus respectivas combinaciones con K-Means y C-Means. De los métodos Sustractivo y Montaña se obtuvieron vectores con los centros de cluster, posteriormente, esos valores ingresaron como parámetros a los algoritmos de K-Means y C-Means. Con el método de la Montaña el algoritmo encontró 20 centros y con el método Sustractivo, 4 centros.
Puede apreciarse por inspección visual las diferencias obtenidas al combinar los distintos métodos, por lo que para la elección de cuáles algoritmos utilizar, se sugiere realizar pruebas con la aplicación en particular y con los parámetros adecuados.

Figura 3. Dispersión de los pixeles en el espacio RGB.

Figura 4. Imágenes segmentadas.

Si lo importante es la velocidad de procesamiento, cuando el número de datos es extenso en proporción al número de nodos que se obtengan de proponer una rejilla usando el algoritmo de Montaña, entonces el algoritmo de Montaña realizará menos iteraciones que el algoritmo Sustractivo.
Como se observa en la Figura 4, cada cúmulo representa un color y entre mayor es el número de centros de cúmulo, la imagen segmentada se asemeja más a la original. También se observa que con el métodoC-Means en ambos casos se obtiene un resultado más preciso con respecto a K-Means.

Conclusiones

Los métodos de agrupamiento de Montaña y Sustractivo son efectivos y de gran utilidad para proporcionar el número de centros de cúmulos iniciales y pueden utilizarse como aproximación inicial de los algoritmos K-Means y C-Means,optimizando el proceso, ya que tanto K-Means como C-Means por sí solos no pueden determinar el número apropiado de cúmulos pero sí optimizan la posición de los centros.
Se obtuvieron tiempos menores de procesamiento combinando los métodos de la Montaña y C-Means, esto se debe a que en el ejemplo utilizado para el método de la Montaña la rejilla quedó conformada por 512 nodos candidatos a centros, mientras que para el método Sustractivo el análisis se efectuó hacia cada uno de los 77,760 pixeles, lo cual incrementa considerablemente el tiempo de procesamiento. 
Dependerá del problema a resolver la elección de los métodos de agrupamiento de datos a emplear.

Referencias y recursos electrónicos