Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color

Equation Chapter 1 Section 1 Proyecto Fin de Grado Ingeniería de las Tecnologías de Telecomunicación Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color Autor: Luis Fernando Pinto Sánchez-Matamoros Tutor: José Antonio Pérez Carrasco Dep. Teoría de la Señal y Comunicaciones Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2015 iii Proyecto Fin de Grado Ingeniería de las Tecnologías de Telecomunicación Análisis de la aplicación de algoritmos de Kmeans y Continuous Max-Flow a la segmentación de imágenes en color Autor: Luis Fernando Pinto Sánchez-Matamoros Tutor: José Antonio Pérez Carrasco Profesor Ayudante Doctor Dep. de Teoría de la Señal y Comunicaciones Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2015 v Proyecto Fin de Grado: Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color Autor: Luis Fernando Pinto Sánchez-Matamoros Tutor: José Antonio Pérez Carrasco El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2015 El Secretario del Tribunal vii A mis padres A mis hermanos ix Agradecimientos Me gustaría utilizar estas líneas para agradecer a aquellas personas que me han ayudado a lo largo de mi carrera universitaria. En primer lugar, expresar mi agradecimiento a D.José Antonio Pérez Carrasco por haberme brindado la oportunidad de trabajar con él, haberme prestado su apoyo a lo largo del desarrollo de este trabajo y su confianza para asignarme este proyecto. A mis padres, Leonor y Fernando, a los que les debo ser lo que soy. Me han enseñado el valor de una buena educación y apoyado durante todo este episodio de mi vida. A mi hermanos Leonor e Ismael que me han aportado todos los valores que un hermano puede pretender y me han dado fuerzas y consejos como ninguna otra persona podría hacerlo. También me gustaría agradecer a mis compañeros de carrera Jon Senra, Jesús Rivera y Pablo Pizarro, con los que he compartido grandes momentos y espero seguir compartiéndolos en esta nueva aventura que comenzamos juntos. Hacer especial mención a mi tío Javier, el cual fue la persona que más me influyó a la hora de elegir la carrera. A todos ellos, muchas gracias. Luis Fernando Pinto Sánchez-Matamoros Sevilla, 2015 ÍNDICE DE TABLAS Tabla 1. Resultados de la imagen 1.bmp. 37 Tabla 2. Resultados de la imagen 2.bmp. 38 Tabla 3. Resultados de la imagen 10.bmp. 39 Tabla 4. Resultados de la imagen 11.bmp. 40 Tabla 5. Resultados de la imagen 12.bmp. 41 Tabla 6. Resultados de la imagen 13.bmp. 42 Tabla 7. Resultados de la imagen 14.bmp. 43 Tabla 8. Resultados de la imagen 15.bmp. 44 Tabla 9. Resultados de la imagen 3096.jpg. 46 Tabla 10. Resultados de la imagen 8068.jpg. 47 Tabla 11. Resultados de la imagen 12003.jpg. 48 Tabla 12. Resultados de la imagen 35070.jpg. 49 Tabla 13. Resultados de la imagen 118035.jpg. 50 Tabla 14. Resultados de la imagen 124084.jpg. 51 Tabla 15. Resultados de la imagen 207056.jpg. 52 Tabla 16. Resultados de la imagen 238011.jpg. 53 Tabla 17. Valores promedio de las imágenes. 54 xvii ÍNDICE DE FIGURAS Figura 1. Espectro de luz visible. 6 Figura 2. Absorción espectral (normalizada) de los conos. 6 Figura 3. Mezcla aditiva de los tres colores primarios Rojo, Verde y Azul. 8 Figura 4. Arriba a la izq.: iluminante D65, luz de medio día. Arriba a la der.: iluminante A, bombilla incandescente. Abajo a la izq.: iluminante F2, Tubo fluorescente. Abajo a la der.: iluminante D50, luz de día. 8 Figura 5. Representación Tridimensional del espacio RGB. 9 Figura 6. Representación Tridimensional del espacio de color L*a*b*. 12 Figura 7. Arriba a la izq.: imagen original. Arriba a la der.: segmentación realizada mediante K-means con la distancia euclídea y 4 etiquetas. Abajo a la izq.: segmentación realizada mediante K-means con la distancia CIEDE94 y 4 etiquetas. Abajo a la der.: segmentación realizada mediante K-means con la distancia CIEDE2000 y 4 etiquetas. 14 Figura 8. Agrupamiento de muestras aleatorias según dos etiquetas. 16 Figura 9. Representación del algoritmo de Max-Flow en tiempo discreto (izq.) y tiempo continuo (der.). 17 Figura 10. Representación de Max-Flow en tiempo Continuo para 2 etiquetas (izq.) y n etiquetas (der.). 19 Figura 11. Imágenes utilizadas como test, squares. 23 Figura 12. Imágenes utilizadas como test, reales. 23 Figura 13. A la izq. la imagen de squares. A la der. su imagen de bordes óptima obtenida con nuestro algoritmo. 24 Figura 14. Representación de la imagen real con sus cinco ground truth. 25 Figura 15. A la izq. la imagen de bordes obtenida de una imagen tipo squares. A la der. una imagen de bordes obtenida de una imagen tipo real. 26 Figura 16. Imágenes de bordes de muestra. Arriba a la izq.: se muestra la imagen de ground truth. Arriba a la der.: se encuentra la imagen de bordes resultante de la segmentación. Abajo, la imagen diferencia. 27 Figura 17 Imágenes squares utilizadas como ground truth en el método de regiones. 28 Figura 18. Imagen de ground truth utilizada para las imágenes del grupo reales 28 Figura 19. A la izq. la imagen original. A la der. la imagen tras ordenarse las etiquetas de mayor a menor. 29 Figura 20. Arriba a la izq.: imagen ground truth de regiones. Arriba a la der.: imagen de bordes segmentada con el algoritmo de Continuous Max-Flow.Abajo:imagen diferencia de regiones. 31 Figura 21. Imagen 8068.jpg con el mismo número de etiquetas que el ground truth (4 etiquetas) y segmentada con el algoritmo C.Max-Flow y distancia CIEDE 00. 55 Figura 22. Imagen 35070.jpg segmentada con el algoritmo C.Max-Flow, distancia CIEDE 00 y 2 etiquetas. 56 Figura 23. Imagen 118035.jpg segmentada con el algoritmo C.Max-Flow, distancia CIEDE 00 y 2 etiquetas. 56 Figura 24. Imagen 207056.jpg segmentada con el algoritmo C.Max-Flow, distancia CIEDE 00 y 2 etiquetas. 57 xix Notación ≡ Equivalente = Igual > Mayor que < Menor que ≥ Mayor o igual que ≤ Menor o igual que e.o.c En otro caso ∑𝑎 𝑐 𝑏 Sumatorio sobre a desde b hasta c ∪ Unión ∩ Intersección ∅ Conjunto vacío Ω Conjunto entero | | Módulo ⊂ Subconjunto de ∀ Para todo sin Función de seno tan−1 Función de tangente inversa ∈ Pertenece a ∫ Integral [] Intervalo cerrado 1 1 INTRODUCCIÓN ste capítulo pretende servir de introducción para explicar detalladamente la justificación, el porqué de la realización de este trabajo, el objetivo, qué queremos conseguir con la elaboración de este proyecto, el estado del arte, qué estudios e investigaciones existen en relación a este tema y la metodología, el trabajo y la búsqueda de recursos que apoyan este proyecto. En primer lugar, se detallará la justificación del trabajo. En segundo lugar, se marcarán unos objetivos antes de comenzar con el desarrollo. La consecución o no de estos, será un tema que se tratará en capítulos siguientes. En tercer lugar, se mostrarán todos los estudios e investigaciones que se han ido desarrollando estos últimos años en relación al tema que en este proyecto se hace referencia. Por último, se describirá la metodología que se ha llevado a cabo a lo largo del trabajo. 1.1 Justificación La segmentación de imágenes es un proceso clave en el análisis y comprensión de las mismas. Sin embargo, llevar a cabo este proceso no es del todo trivial. Esto es debido a que en el ámbito de la segmentación de imágenes existen muchos factores y muy diversos como pueden ser el ruido, las características del objeto, texturas,… El proceso de dividir una imagen digital en múltiples regiones (grupo de píxeles), que guardan algún tipo de característica común, es lo que se denomina segmentación de imágenes. El resultado de la segmentación es un grupo de píxeles que cubren toda la superficie de la imagen. Todos los píxeles de una misma región guardan entre sí características similares, como pueden ser el color, textura, intensidad… Las regiones adyacentes son significativamente diferentes con respecto a las mismas características. Como ya he comentado anteriormente, este proceso no es fácilmente aplicable debido a la gran variedad de imágenes (no existe un método de segmentación estándar). Además de ello, existen otros grandes problemas a la hora de la segmentación de imágenes como puede ser la carga computacional necesaria para realizarla. Es por todo esto, que cada vez más se llevan a cabo investigaciones y avances sobre nuevos algoritmos de segmentación que sean capaces de solventar estos problemas. Este trabajo se centra precisamente en el estudio de resultados del uso de dos algoritmos altamente conocidos en el ámbito de la segmentación de imágenes en color, como son K-means y Continuous Max-Flow, para satisfacer la búsqueda del etiquetado óptimo de cada pixel o nodo, con respecto a una función de energía. El primer algoritmo, K-means, se centra en el agrupamiento de los píxeles siguiendo una característica en É “There is nothing worse than a sharp image of a fuzzy concept” - Ansel Adams - Introducción 2 común. En este caso, el color. También se denominan técnicas de segmentación basadas en clustering (agrupamiento). El segundo de ellos, Continuous Max-Flow, se fundamenta en la segmentación de imágenes basada en la optimización de una función de energía. En los apartados siguientes se explicará de forma más detallada el funcionamiento de ambos algoritmos y la actuación conjunta de ambos. 1.2 Objetivos Mediante la actuación coordinada de los dos algoritmos anteriormente citados, se buscará y analizará si mediante este proceso se puede mejorar la segmentación sobre algunas imágenes a color, que por sí solo el algoritmo de K-means no es capaz de realizar correctamente. También se buscará reducir los costes computacionales, reduciendo el número de iteraciones de K-means y por tanto el tiempo de segmentación. Además, este trabajo también nos servirá para establecer cuáles son las diferencias aportadas entre el uso de las diferentes distancias que la CIE propone y que en este trabajo ponemos en práctica (véase el punto 2.1.3). 1.3 Estado del arte En la actualidad, existen numerosos estudios e investigaciones relacionados con el campo del procesamiento de imágenes que se centran en intentar resolver los problemas de minimización de una función de energía a través de métodos basados en corte de grafos, como Min-Cut o Max-Flow. Algunos de esos recientes estudios se basan en la búsqueda de soluciones para: segmentación de imágenes [20,27,28], reconstrucción de escenas tomadas desde varias cámaras [29], reconstrucciones de modelos en 3D y shape fitting [30,31,32], síntesis de imágenes y fotomontajes [33], etc. Normalmente, los problemas de minimización de energía en tiempo discreto se basan en la búsqueda del corte mínimo sobre un apropiado grafo. Igualmente, pueden ser resueltos de una manera eficiente mediante la búsqueda del máximo flujo correspondiente al mismo grafo. Esto es lo que se denomina la teoría del Min-Cut y Max-Flow. Ha habido muchísimas investigaciones en relación a este tema en los últimos años [19, 20]. Recientes estudios en el campo de la investigación de segmentación de imágenes muestran, que formular los problemas de Min-Cut en tiempo continuo configurado de una manera correcta, evita una conversión predefinida y permite encontrar de manera más rápida unas soluciones globales a través de Convex Optimization. G.Strangs [21, 22] fue el primero en estudiar los problemas de Min-Cut y Max-Flow en un dominio temporal continuo. Existen estudios relacionados [27,34] donde Appleton y colaboradores propusieron una mínima aproximación superficial basada en bordes en el dominio continuo para la segmentación de objetos 2D y 3D. Además, Chan y colaboradores fueron capaces de formular la segmentación de imágenes con dos regiones como la resolución de un problema de minimización convexa [23]. Sin embargo, en contraste con la dualidad entre Max-Flow y Min-Cut en tiempo discreto, donde los algoritmos de Min-Cut son definidos de la forma de Max-Flow, en tiempo continuo, el modelado de Max-Flow como una formulación dual de (2.37) está todavía inmerso en investigaciones y desarrollos. 1.4 Metodología En este apartado especificaremos la metodología que hemos seguido a lo largo de todo el proyecto para la búsqueda de la información que contiene. Así, iremos nombrando las diferentes fuentes de información a las que hemos acudido y daremos algunos detalles de cómo se ha realizado la búsqueda para llegar a los diferentes títulos de las referencias. 3 Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color 1.4.1 Base de datos fama Fama es el catálogo donde se encuentran todos los recursos de lectura de los que dispone la Universidad de Sevilla, libros, artículos, monografías… Esta base de datos ha sido una de las más recurridas debido a que, desde ella, se puede acudir a numerosos artículos y libros, incluso hace referencia a artículos de los que dispone la Universidad pero que se encuentran alojadas en otra base de datos. Para la búsqueda de información sobre los conceptos teóricos que se expondrán más adelante fue bastante útil puesto que realizando una búsqueda mediante palabras claves tales como “space color”, “color”, “luz”… fue suficiente para encontrar unas muy buenas referencias. Sin embargo, para algunos temas tales como “segmentation” “clustering” o “K-means” los resultados a los que nos llevaban no eran del todo concretos sobre lo que buscábamos. Así que decidimos que en lugar de buscar por palabras claves que tuviesen que ver con este proyecto, buscar por autores que supiésemos nosotros que utilizaban muchos de los términos que aquí aplicamos. 1.4.2 CIE CIE, la comisión internacional del color, dispone en su página web de una aplicación donde se pueden encontrar la lista de términos más conocidos en el ámbito del color y su definición normalizada. Además, dispone de un gran conjunto de artículos publicados, de los cuales, muchos de ellos tienen que ver con el color. Es por ello, que acudimos a la página web en busca de recursos que nos fuesen útiles para poder desarrollar con fundamento la parte teórica del proyecto. Utilizamos, por tanto, su buscador de términos para poder dar con criterio definiciones en este proyecto. Además, también hicimos uso de su gran lista de artículos gratuitos publicados para que nos sirvieran, junto con otras publicaciones, a la hora de realizar una explicación básica sobre conceptos teóricos más profundos que la mera descripción de un término, como por ejemplo, en la explicación de los espacios de color. 1.4.3 Mathworks Mathworks, además de ser conocidos por el programa Matlab, también dispone de un buscador en el cual, las personas que van realizando algoritmos en código Matlab las van aportando a un pequeño foro interno. Además de incluir los algoritmos en código matlab, suelen incluir una pequeña referencia a un artículo donde ha sido usado. Así pues, una de las búsquedas que realizamos en ésta página fue continuous Max-Flow algorithm, justo el algoritmo que utilizamos en este proyecto. Al descargar el contenido, además del algoritmo, se incluía un documento al cual hemos hecho referencia en el proyecto. 1.4.4 IEEE IEEE, el instituto de ingenieros electrónicos y eléctricos, es un referente en cuanto a normativa se refiere. Sin embargo, no acudimos de forma directa a su buscador de normas, sino que fue a través de fama donde encontramos los artículos que se hacían referencia en otros artículos. Por lo tanto, el haber hecho uso del buscador de normas de la que dispone, fue como resultado de haber leído distintos artículos en los cuales se hace referencia a muchas de las normas de las que nosotros mismos ahora hacemos referencia. 1.4.5 Base de datos de Berkeley La base de datos de Berkeley es una de las bases de datos de imágenes más usadas en el ámbito de procesamiento de imagen, puesto que en ella, se encuentran una gran cantidad de imágenes de las que se puede Introducción 4 hacer uso para la pruebas de distintos algoritmos de segmentación. Posteriormente, se explicará más en profundidad. El uso de esta base de datos es el resultado de ver que en muchos de los artículos de segmentación de imágenes, se hacía uso de las imágenes que en dicha base se encuentran [14]. Es por ello, que me pareció correcto utilizarla para mi proyecto, puesto que, es usada en el ámbito de la investigación a la que yo mismo estoy haciendo referencia con mi proyecto. 1.4.6 Tesis doctorales y proyectos Como se ha comentado antes, el uso que se le ha dado al catálogo fama en este proyecto fue sobre todo para encontrar artículos relacionados con la segmentación de imágenes. A pesar de ello, el uso que se le ha dado ha sido también para encontrar trabajos de fin de carrera y tesis doctorales que guardasen relación con lo que en este proyecto se habla. 1.4.7 Google Academics Aunque google como buscador sobre documentos de investigación puede no tener muy buena fama, puesto que, los resultados que muestra no suelen ser fuentes muy fiables, google dispone de un buscador específico donde los únicos resultados que verterá serán artículos académicos. 5 2 DESARROLLO n este capítulo se explicará en profundidad el desarrollo de todo el trabajo. Se introducirá un marco teórico necesario para el buen seguimiento del proyecto. Se detallarán los resultados conseguidos y además, se describirá el desarrollo para conseguirlos. Por último, se explicarán las conclusiones a las que hemos llegado gracias a los datos conseguidos y compararlos con los objetivos que nos habíamos marcado en secciones anteriores. 2.1. Marco Teórico Esta sección pretende ser una introducción a una serie de conceptos básicos para poder entender el desarrollo del proyecto. Se introducirá, en primer lugar, el concepto básico de color. Luego, se introducirá un término muy ligado al anterior, como son los modelos representativos de color y las distancias utilizados en los mismos. Después, se dará un breve repaso sobre la segmentación de las imágenes y los métodos más populares. Por último, se nombrarán las bases de datos de imágenes que han servido de apoyo a este trabajo. 2.1.1 El color Según el vocabulario internacional de la luz, la definición de la misma es “Cualquier radiación capaz de causar una sensación visual” (CIE, 1987). La luz visible es una radiación electromagnética comprendida en un rango de 380 a 780 nanómetros. Para Wyszecki & Stiles (1982), “Color is that aspect of visual perception by which an observer may distinguish differences between two structure-free fields of views of the same size and shape, such as may be caused by differences in the spectral composition of the radiant energy concerned in the observation”. “El color es el aspecto de la percepción visual por el cual un observador es capaz de distinguir diferencias entre dos campos de visión del mismo tamaño, forma y estructura causadas por las diferencias en la composición espectral de la energía radiante implicada en la observación” El color no es más que la respuesta del sistema visual humano a la excitación recibida de la radiación electromagnética comprendida en el rango del espectro de luz visible. Al incidir en la retina del ojo, la radiación es captada e interpretada como un color. Dependiendo de la longitud de onda se caracterizará de una manera u otra. La distribución espectral de la luz visible se representa en la siguiente figura (Fig.1). E “As with sound, images are subjective. You and I may not see the same color as red, but we will probably agree that the image on the screen is a digital image or film image, based on contrast, bit depth and refresh rate” - John Dykstra- Desarrollo 12 Figura 6. Representación Tridimensional del espacio de color L*a*b*. 2.1.3 Distancias de color En el apartado anterior hemos destacado que ciertos modelos como CIELAB y CIELUV se consideraban espacios de color uniformes. Sin embargo, a pesar del supuesto perceptual uniforme, los últimos estudios e investigaciones demuestran que esa teoría no es del todo cierta [16]. Tal y como se especificó en el apartado anterior, la diferencia de color de CIELAB se realiza mediante la distancia euclídea entre dos puntos. A pesar de ello, se descubrió que considerar esta distancia para describir la diferencia perceptual entre dos puntos no era del todo equiparable con el sistema visual humano. Así pues, surgen fórmulas que permiten adaptar el espacio de color CIELAB aún mejor a la percepción del sistema visual humano. Las distancias propuestas por la CIE son CIEDE2000 [17] y CIEDE94 [18], basadas en el espacio de color CIELAB. La más reciente de todas ellas publicada en 2001 es CIEDE2000, la recomendada por la CIE. En nuestro trabajo, haremos una comparativa de las 3 distancias, la distancia por defecto de CIELAB (euclídea), la distancia CIEDE94 y la distancia CIEDE2000. Para llegar a las distancias de color propuestas, es necesario acudir a las relaciones que explicamos en el apartado anterior, donde a partir de las coordenadas de croma a* y b*, se pueden obtener parámetros tales como tono y saturación. 1. Relación de los valores de CIELAB con los valores de CIEDE2000 y CIEDE94: 𝑎′=(1+𝐺)𝑎∗ 𝑑𝑜𝑛𝑑𝑒 𝐺=0,5(1 − √𝐶𝑎𝑏 ∗7 𝐶𝑎𝑏 ∗7+257 𝑏′=𝑏∗ 𝐿′=𝐿∗ ( 2.19 ) 13 Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color 2. Cálculo de C’ (tono) y h’ (saturación) : 𝐶′= √𝑎′2+𝑏′2 ℎ′={0, 𝑏′=𝑎′=0 tan−1(𝑏′ 𝑎′), 𝑒.𝑜.𝑐 ( 2.20 ) 3. Cálculo de las componentes de diferencia de color entre las dos muestras: ∆𝐿′= 𝐿′1− 𝐿′2 ∆𝐶′= 𝐶′1− 𝐶′2 ∆ℎ′= ℎ′1− ℎ′2 ∆𝐻′= 2√𝐶′1𝐶′2sin(∆ℎ′ 2) ( 2.21 ) 4. Cálculo de la fórmula de la CIEDE2000: ∆𝐸00= √(∆𝐿′ 𝐾𝐿𝑆𝐿)2+(∆𝐶′ 𝐾𝐶𝑆𝐶)2+(∆𝐻′ 𝐾𝐻𝑆𝐻)2+𝑅𝑇(∆𝐶′ 𝐾𝐶𝑆𝐶)2(∆𝐻′ 𝐾𝐻𝑆𝐻)21 ( 2.22 ) 5. Cálculo de la fórmula de la CIEDE94: ∆𝐸94= √(∆𝐿∗ 𝐾𝐿𝑆𝐿)2+(∆𝐶𝑎𝑏 ∗ 𝐾𝐶𝑆𝐶)2+(∆𝐻𝑎𝑏 ∗ 𝐾𝐻𝑆𝐻)2 ( 2.23 ) En la siguiente figura se muestra a modo de ejemplo, una imagen segmentada mediante el algoritmo de Kmeans con las tres distancias explicadas anteriormente (euclídea, CIEDE94 y CIEDE2000) y 4 etiquetas (Fig. 7). 1 Los valores que no se han definido y que se encuentran en la fórmula, se pueden encontrar en la referencia [17] Desarrollo 14 Figura 7. Arriba a la izq.: imagen original. Arriba a la der.: segmentación realizada mediante K-means con la distancia euclídea y 4 etiquetas. Abajo a la izq.: segmentación realizada mediante K-means con la distancia CIEDE94 y 4 etiquetas. Abajo a la der.: segmentación realizada mediante K-means con la distancia CIEDE2000 y 4 etiquetas. 2.1.4 Segmentación de imágenes en color La segmentación de una imagen se define como la división o separación de dicha imagen en diferentes regiones con atributos similares. Dependiendo de qué atributo sea al que queremos dar importancia, ya que, según la necesidad querremos uno u otro, obtendremos una forma de segmentación diferente en cada caso mediante la utilización de diferentes algoritmos. La segmentación de imágenes es un proceso clave en el análisis y compresión de una imagen. Debido a ello, es un apartado muy importante siempre que, la caracterización y diferenciación sea primordial para el objeto de estudio (visión artificial, análisis médicos…). Existen cinco categorías en la segmentación de imágenes: segmentación basada en pixel, segmentación basada en regiones, segmentación basada en bordes, segmentación híbrida entre región y bordes y, por último, segmentación basada en agrupamiento. Además, existen otras técnicas de segmentación muy utilizadas basadas en la optimización de una función de energía generada por la imagen. En este apartado, trataré de ahondar en aquellos métodos de segmentación más relevantes para el desarrollo de este proyecto. 2.1.4.1 Segmentación basada en agrupamiento (clustering) Los algoritmos de segmentación basados en clustering clasifican los datos de las imágenes y los agrupan en función de una serie de características anteriormente definidas. Estos tipos de algoritmos son no supervisados, es decir, no requieren el conocimiento previo de aquellos objetos que se van a segmentar. Tan sólo requieren las características previas en base a las que van a realizar la segmentación. Por ello, resultan muy convenientes para aquellos ámbitos de aplicación en los que a priori, no se tiene mucha información, como en el caso de imágenes médicas o en el caso de segmentación de objetos 15 Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color sobre un fondo. Hay una gran variedad de algoritmos de este tipo como pueden ser: K-means, Fuzzy K-means, C-means… Nosotros nos centraremos en el primero de ellos, ya que es el que hemos requerido. Los otros dos, son variantes del mismo. 2.1.4.1.1 Algoritmo de K-means Como se ha explicado anteriormente, K-means es un algoritmo basado en clustering. Lo que quiere decir que su principal objetivo es optimizar la partición de la imagen en áreas conforme a unas características dadas. Este tipo de algoritmos ha sido usado comúnmente para una segmentación básica de imágenes ya que existen ciertas restricciones como la necesidad de que la imagen sea generalmente homogénea, sin texturas [6]. La restricción de texturas a la hora de usar K-means viene dado por dos problemas. El primero de ellos tiene que ver con la condición de comienzo, es decir, la inicialización de los clusters iniciales. El segundo de ellos tiene que ver con el hecho de que no se aplica una cohesión espacial a lo largo del proceso de segmentación. Antes de comenzar a aplicar el algoritmo es necesario realizar una transformación en el espacio de color que se vaya a utilizar. Es necesario crear uno independiente del dispositivo en el que se realice, con el fin de evitar diferencias de color. Uno de los más usuales suele ser el espacio de color RGB. El algoritmo K-means que se muestra más adelante es el algoritmo aplicado a imágenes en escala de grises. Para el algoritmo aplicado a imágenes en color se extrapolan esas ecuaciones a los planos que contiene el espacio de color correspondiente. Así pues, si utilizamos el espacio de color RGB, los vectores contendrían tres valores en lugar de uno como en el caso de imágenes en escala de grises. Según [7], el algoritmo de K-means básico consiste en cuatro pasos, que se describen de manera resumida a continuación. 1. Inicialización de (K) centros. Se generan un número de clusters de manera aleatoria en función de las condiciones iniciales dadas: 𝐶𝑒𝑛𝑡𝑒𝑟𝑖0=𝐺𝐿𝑚𝑖𝑛+(𝑖−12)𝐺𝐿𝑚𝑎𝑥−𝐺𝐿𝑚𝑖𝑛 𝐾 𝑖=1,2,…𝐾, ( 2.24 ) Donde 𝐶𝑒𝑛𝑡𝑒𝑟𝑖0 es el centroide inicial de la iésima clase, 𝐺𝐿𝑚𝑎𝑥 y 𝐺𝐿𝑚𝑖𝑛 son el máximo y el mínimo valor de gris (GL) en el espacio muestra respectivamente. 2. Generación de nuevas particiones asignando cada punto a su centro más cercano. El criterio de asignación de un punto a un centro está basado en la distancia euclídea. Actualmente existen nuevas distancias como CIEDE94 y CIEDE2000. Continuando la notación matemática con el uso de la distancia euclídea: 𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑖,𝑗=𝑎𝑏𝑠(𝐺𝐿𝑗−𝐶𝑒𝑛𝑡𝑒𝑟𝑖) 𝑖=1,2,…,𝐾;𝑗=1,2…𝑁. ( 2.25 ) Donde 𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑖,𝑗 es la distancia desde el punto j al centroide de la clase i. N es el número total de puntos pertenecientes al espacio muestra. 3. Cálculo de los (K) nuevos centros. Se calculan conforme a la media de los puntos que han sido Desarrollo 16 asignados al centro anterior según el paso anterior: 𝐶𝑒𝑛𝑡𝑒𝑟𝑖𝑚= 1 𝑁𝑖∑𝐺𝐿𝑗, 𝑖=1,2,…,𝐾 𝑁𝑖 𝑗=1 ( 2.26 ) Donde 𝑁𝑖 es el número total de puntos asignados a la clase iésima en el paso número 2. 4. Se repite el paso número 2 si alguno de los centros asignados cambia del paso 2 al 3. Si no, se acaba el algoritmo. En la siguiente figura se muestra una versión básica del agrupamiento entre muestras. En este caso, el ejemplo se ha realizado con dos etiquetas (Fig. 8) Figura 8. Agrupamiento de muestras aleatorias según dos etiquetas. El algoritmo de K-means no es sólo aplicable a imágenes, sino a matrices en general. Además, como se ha mencionado anteriormente, se trata de un algoritmo de aprendizaje no supervisado en el que el valor de cada uno de los píxeles que componen la imagen es tomado como un vector y sus componentes son tratadas sin tener en cuenta a qué hacen referencia. Es por ello que, el algoritmo no requiere de modificaciones en caso de usarse distintos espacios de color, tomando más o menos planos. Los elementos del vector pueden ser valores de luminancia, tono o saturación y la eficacia de ellos dependerá de la finalidad que tenga la segmentación. En nuestro caso en concreto, el algoritmo de K-means se aplicará sobre el espacio de color L*a*b (véase 2.1.2.2) con las distancias euclídea, CIEDE94 y CIEDE00 (véase 2.1.3). 2.1.4.2 Segmentación basada en la optimización de una función de energía Como se ha comentado en la introducción de esta sección, existen muchos métodos para la segmentación de imágenes. Un grupo muy importante de éstos, consiste en la optimización de la función de energía. Existen dos grupos de este tipo de segmentación. Por un lado, tenemos aquellas funciones definidas en un espacio continuo donde la función a optimizar da lugar a una ecuación diferencial donde para resolverla se 17 Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color suelen utilizar métodos como el descenso del gradiente. En segundo lugar, tenemos funciones que se definen en un conjunto discreto donde la segmentación de éste da lugar a la resolución de un problema de minimización de un espacio finito. Nuestro trabajo en concreto se basa en la utilización de un algoritmo novedoso basado en Max-Flow en el espacio continuo. Experimentos en la segmentación de imagen, tanto supervisado como sin supervisión, muestran que el algoritmo que utilizamos en el proyecto basado en Continuous Max-Flow, da lugar a unos mejores resultados en términos de eficiencia y rendimiento que anteriores aproximaciones en el mismo campo [12]. En primer lugar, se hará una breve introducción de los conceptos básicos de Max-Flow en el espacio discreto ya que muchos de los conceptos utilizados en éste son muy parecidos en el espacio continuo. Aparte, su explicación es mucho más fácil de entender y su visión conceptual también. Continuaremos explicando los conceptos claves y relaciones de lo explicado anteriormente con el algoritmo de Max-Flow en un espacio continuo. Por último, introduciremos el algoritmo que se utiliza en este proyecto, una variante de Max-Flow en espacio continuo, y la relación que existe con el algoritmo basado en clústering (K-means). Apoyándonos en los artículos [10] [12] y [24], seremos capaces de comprender y explicar los algoritmos de Min-Cut y Max-Flow tanto en tiempo discreto como en continuo. Además de definir el algoritmo que utilizamos, ya que [10] y [24] son artículos escritos conforme a la creación del nuevo algoritmo de Max-Flow. Figura 9. Representación del algoritmo de Max-Flow en tiempo discreto (izq.) y tiempo continuo (der.). 2.1.4.2.1 Algoritmo de Min-Cut / Max-Flow espacio discreto En relación a lo expuesto anteriormente, Greig, Porteous y Seheult [8], descubrieron que mediante algoritmos de Min-Cut /Max-Flow utilizados en optimización de combinatorias, se podían usar para minimizar una gran cantidad importante de funciones de energía en problemas de visión. En ese artículo en concreto, demostraron que el corte de grafos se podía usar para la restauración de imágenes binarias. Futuros trabajos de investigación estaban centrados en la utilidad de los grafos para la segmentación de imágenes, restauración… Sea un grafo unidireccional 𝐺={𝑉,𝐸} definido por un conjunto de nodos (vértices 𝑉 ), con dos nodos especiales, uno llamado fuente, 𝑠 y otro llamado sumidero, 𝑡, y un conjunto de bordes unidireccionales que conectan esos nodos (𝐸). El conjunto de bordes está compuesto por dos tipos de bordes: bordes espaciales 𝑒𝑛=(𝑟,𝑞), donde 𝑟,𝑞 ∈𝑉\{𝑠,𝑡}, que conectan entre sí los nodos r y q a excepción de la fuente y el sumidero, 𝑠 y 𝑡 respectivamente; los bordes terminales 𝑒𝑠=(𝑠,𝑟) o 𝑒𝑡=(𝑟,𝑡), donde 𝑟∈𝑉\{𝑠,𝑡} conecta el nodo 𝑠 o 𝑡 a otro nodo. Cada borde 𝑒∈𝐸 , tiene asignado un coste no negativo, 𝐶(𝑒)≥0. Min-Cut Definimos como corte a un subgrupo tal que la fuente y el sumidero quedan separados 𝐶 ∁ 𝐸, también llamado s-cut (Fig. 9 izquierda). Por lo tanto, la imagen queda claramente divida en dos partes, una relacionada con la fuente, 𝑆 y otra con el sumidero, 𝑇. Desarrollo 18 𝑉=𝑉𝑠∪𝑉𝑡, 𝑉𝑠∩𝑉𝑡=∅ ( 2.27 ) Para cada corte, la energía es definida como la suma de los costes 𝐶(𝑒) de cada borde 𝑒∈𝐸𝑠𝑡⊂𝐸 , cuyos puntos finales pertenecen a las dos particiones. Por lo tanto, el problema de Min-Cut es encontrar las dos particiones de los vértices tal que el correspondiente corte de energía sea mínimo: 𝑚𝑖𝑛 𝐸𝑠𝑡⊂𝐸 ∑𝐶(𝑒) 𝑒∈𝐸𝑠𝑡 ( 2.28 ) Max-Flow Por otro lado, cada borde 𝑒∈𝐸 se puede ver como una tubería y cada coste 𝐶(𝑒) puede ser considerado como la capacidad de esa tubería, para la cual el máximo flujo está permitido. Para cada red de “tuberías” tenemos las siguientes restricciones de flujos: 1. Capacidad de los flujos espaciales 𝑝: para los bordes unidireccionales espaciales 𝑒𝑛=(𝑟,𝑞)∈ 𝐸,𝑟,𝑞∈𝑉{𝑠,𝑡}, los flujos espaciales 𝑝(𝑒𝑛) vienen restringidos por: |𝑝(𝑒𝑛)| ≤ 𝐶(𝑒𝑛) ( 2.29 ) 2. Capacidad de flujo de la fuente 𝑝𝑠 : para el borde 𝑒𝑠(𝑣):𝑠→𝑣 que conecta la fuente 𝑠 a un nodo 𝑣∈𝑉{𝑠,𝑡}, el flujo de la fuente 𝑝𝑠(𝑣) es directo desde 𝑠 a 𝑣. Su capacidad 𝐶𝑠(𝑣) indica que: 0≤𝑝𝑠(𝑣) ≤ 𝐶𝑠(𝑣) ( 2.30 ) 3. Capacidad de flujo del sumidero 𝑝𝑡: para el borde 𝑒𝑡(𝑣):𝑣→𝑡 que conecta un nodo 𝑣∈𝑉{𝑠,𝑡} al sumidero 𝑡, 𝑝𝑡(𝑣) es directo desde 𝑣 a 𝑡. Su capacidad 𝐶𝑡(𝑣) indica que: 0≤𝑝𝑡(𝑣) ≤ 𝐶𝑡(𝑣) ( 2.31 ) 4. Conservación de los flujos: Para nodo 𝑣 ∈𝑉{𝑠,𝑡}, los flujos entrantes deben estar equilibrados con los flujos salientes. En otras palabras, todos los flujos que pasan a través de 𝑣, incluyendo los flujos espaciales, los flujos de la fuente y los flujos del sumidero vienen restringidos por: ( ∑ 𝑝((𝑞,𝑣)) 𝑞∈𝑁(𝑣))−𝑝𝑠(𝑣)+𝑝𝑡(𝑣)=0 ( 2.32 ) Donde 𝑞∈𝑁(𝑣) es el conjunto de nodos vecinos de 𝑣. 19 Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color En este caso, el problema de máximo flujo se basa en encontrar la mayor cantidad de flujo permitido para pasar de la fuente 𝑠 al sumidero 𝑡, en otras palabras: 𝑚𝑎𝑥 𝑝𝑠 ∑ 𝑝𝑠(𝑣) 𝑣 ∈𝑉{𝑠,𝑡} ( 2.33 ) Sujeto a las restricciones (2.29) (2.30) (2.31) y (2.32) Relación Min-Cut/Max-Flow Es bien sabido que el problema de Max-Flow (2.33) es equivalente al problema de Min-Cut (2.28), donde los flujos están saturados uniformemente en los cortes de los bordes, en otras palabras, el flujo total está limitado por “las tuberías saturadas”. Por la terminología de graph-cut, cuando un flujo 𝑝(𝑒) en el borde 𝑒 ∈𝐸 alcanza su correspondiente capacidad 𝐶(𝑒) dada por (2.29), (2.30), (2.31), diremos que está saturado; en otro caso, no saturado. 2.1.4.2.2 Algoritmo de Min-Cut / Max-Flow espacio continuo Min-Cut / Max-Flow con 2 etiquetas Antes de introducir el modelo de Max-Flow en el espacio continuo con n etiquetas, introduciremos el reciente estudio de Max-Flow en el espacio continuo con 2 etiquetas propuesto por los autores [12] el cual es dual a Min-Cut en el espacio continuo. Figura 10. Representación de Max-Flow en tiempo Continuo para 2 etiquetas (izq.) y n etiquetas (der.). Análogamente a Max-Flow y Min-Cut basado en grafos (Sec 2.1.4.2.1): dado el dominio temporal de la imagen Ω, asumimos que hay dos terminales, la fuente 𝑠 y el sumidero 𝑡 (Fig. 10 (a)). Además, asumimos que para cada posición de la imagen 𝑥∈ Ω intervienen tres tipos de flujos: el flujo de la fuente 𝑝𝑠(𝑥)∈ℝ directamente desde la fuente 𝑠 a 𝑥, el flujo del sumidero 𝑝𝑡(𝑥)∈ℝ directamente desde 𝑥 al sumidero 𝑡 y el flujo espacial 𝑝(𝑥)∈ℝ2. Los tres flujos tienen una serie de restricciones: |𝑝𝑠(𝑥)|≤𝐶𝑠(𝑥), ∀𝑥∈ Ω; |𝑝𝑡(𝑥)|≤𝐶𝑡(𝑥), ∀𝑥∈ Ω; |𝑝(𝑥)|≤𝐶(𝑥), ∀𝑥∈ Ω; ( 2.34 ) Desarrollo 20 Además, todos los flujos se conservan para ∀𝑥∈ Ω: 𝑝𝑡(𝑥)−𝑝𝑠(𝑥)+ 𝑑𝑖𝑣 𝑝(𝑥)=0, ∀𝑥∈ Ω; ( 2.35 ) Donde 𝑑𝑖𝑣 𝑝 evalúa la cantidad total de flujo espacial entrante localmente alrededor de 𝑥 , lo cual es una analogía al operador suma (2.32) para el tiempo discreto. En este caso, las restricciones del flujo de la fuente 𝑝𝑠(𝑥) (2.34) y el flujo del sumidero 𝑝𝑡(𝑥) (2.34) son diferentes en comparación con las restricciones de Max-Flow en el dominio temporal discreto (2.30) (2.31). Esto es debido a que la positividad de los flujos 𝑝𝑠(𝑥) y 𝑝𝑡(𝑥) no son necesarias puesto que son flujos directos y su valor indica cómo el flujo se distribuye desde 𝑠 hasta el punto 𝑥 o desde 𝑥 hasta 𝑡. De la misma manera, 𝐶𝑠(𝑥) y 𝐶𝑡(𝑥) tampoco es necesario que sean positivos. Por lo tanto, esto extiende la aplicación de Max-Flow y Min-Cut en el dominio temporal continuo. Análogamente con la formulación del problema de Max-Flow en tiempo discreto (2.33), podemos formular el correspondiente problema de Max-Flow en tiempo continuo mediante la maximización del flujo total desde la fuente: 𝑚𝑎𝑥 𝑝𝑠,𝑝𝑡,𝑝∫ 𝑝𝑠𝑑𝑥 Ω ( 2.36 ) Sujeto a las restricciones (2.34) y (2.35) Además, Yuan y otros [12] probaron que la formulación del problema de máximo flujo en el dominio continuo es equivalente al problema de Min-Cut de la siguiente manera: 𝑚𝑖𝑛 𝑢(𝑥)∈[0,1] ∫ (1−𝑢)𝐶𝑠𝑑𝑥 Ω+ ∫ 𝑢𝐶𝑡𝑑𝑥 Ω+∫ 𝐶|∇𝑢|𝑑𝑥 Ω ( 2.37 ) De hecho, la ecuación (2.37) tan sólo nos da el modelo dual de (2.36) y la función de etiquetado 𝑢(𝑥) es el multiplicador de la condición de conservación de flujo (2.35). Por lo tanto, un modelo eficiente y fiable puede ser construido en base al algoritmo (2.36). Min-Cut / Max-Flow con n etiquetas Basándose en las observaciones de lo comentado anteriormente, Yuan et al establecieron una configuración para un modelo de Max-Flow en espacio continuo con n etiquetas [24] (Fig. 10 (b)). 1. Tenemos 𝑛 copias de Ω𝑖,𝑖=1…𝑛, del dominio de la imagen Ω ; 2. Para cada posición 𝑥∈Ω, el flujo de la fuente 𝑝𝑠(𝑥) intenta ser enviado desde la fuente 𝑠 hasta 𝑥 para cada copia Ω𝑖,𝑖=1…𝑛 de Ω. El flujo de la fuente es el mismo para cada Ω𝑖,𝑖=1…𝑛, en otras palabras, 𝑝𝑠(𝑥) es único. 3. Para cada posición 𝑥∈Ω, el flujo del sumidero 𝑝𝑖(𝑥),𝑖=1…𝑛 es enviado de forma directa desde la posición 𝑥 en la i-esima copia Ω𝑖 hasta el sumidero 𝑡. Los 𝑛 flujos 𝑝𝑖(𝑥),𝑖=1…𝑛, pueden ser diferentes; 4. Los flujos espaciales 𝑞𝑖(𝑥),𝑖=1…𝑛 vienen definidos dentro de cada copia Ω𝑖,𝑖=1…𝑛. Pueden ser diferentes el uno del otro. 21 Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color Para una configuración dada, establecemos las condiciones de restricción para los flujos 𝑝𝑖(𝑥) 𝑦 𝑞𝑖(𝑥), donde 𝑥∈Ω, de la siguiente manera: |𝑞𝑖(𝑥),|≤𝐶𝑖(𝑥), 𝑖=1…𝑛; 𝑝𝑖(𝑥)≤𝜌(𝑙𝑖,𝑥), 𝑖=1…𝑛; 𝑝𝑖(𝑥)−𝑝𝑠(𝑥)+ 𝑑𝑖𝑣 𝑞𝑖(𝑥)=0, 𝑖=1…𝑛; ( 2.38 ) La función 𝜌(𝑙𝑖,𝑥), 𝑖=1…𝑛, evalúa la actuación de asignar la etiqueta 𝑙𝑖 a una posición específica 𝑥. Por lo tanto, se puede formular el modelo de Max-Flow en tiempo continuo de la siguiente manera: 𝑚𝑎𝑥 𝑝𝑠,𝑝,𝑞{𝑃(𝑝𝑠,𝑝,𝑞)∶=∫ 𝑝𝑠𝑑𝑥 Ω ( 2.39 ) Sujeto a las restricciones (2.38) 2.1.4.2.3 Algoritmo de Min-Cut / Max-Flow dirigido En los dos apartados anteriores, hemos introducido teóricamente el algoritmo de Max-Flow y su equivalente Min-Cut tanto en un espacio discreto como continuo. Como ya dije anteriormente, en nuestro proyecto, el algoritmo utilizado se basa en el algoritmo basado en un espacio continuo. Sin embargo, existen algunas pequeñas diferencias entre éste y el utilizado realmente. En comparación con el algoritmo de Max-Flow y Min-Cut en espacio continuo, el algoritmo aquí propuesto calcula una partición óptima sujeta a unas restricciones dadas de las configuraciones de las regiones, en otras palabas, algunos píxeles de la imagen son etiquetados previamente. Es aquí donde se establece la conjunción del algoritmo de K-means, con el algoritmo de Max-Flow en tiempo continuo. Según J.Yuan y colaboradores [12], el problema de particionado dirigido de las imágenes puede ser modelado según el siguiente problema de Min-Cut dirigido: 𝑚𝑖𝑛 {Ω𝑖}𝑖=1 𝑛∑∫ 𝐶𝑖(𝑥)𝑑𝑥+𝛼∑|𝜕Ω𝑖| 𝑛 𝑖 Ω𝑖 𝑛 𝑖 ( 2.40 ) Sujeto a: ⋃𝑖=1 𝑛=Ω𝑖=Ω; Ω𝑘∩ Ω𝑙=∅, ∀𝑘≠𝑙 ( 2.41 ) Donde |𝜕Ω𝑖|, mide el perímetro de cada subdominio disjunto Ω𝑖,𝑖=1…𝑛. La función 𝐶𝑖(𝑥),𝑖=1…𝑛, evalúa los costes de asignar a una posición específica 𝑥∈Ω a la región Ω𝑖. Además, según propusieron J.Yuan et al [12] y como ya se ha comentado en el apartado anterior, el problema de Max-Flow se puede modelar según: Desarrollo 28 Squares Como es un método que cuenta el número de píxeles de cada región, no es necesario realizar ningún tipo de transformación a la imagen puesto que estas imágenes ya vienen etiquetadas en 4 regiones diferentes, donde cada rectángulo pertenece a uno de ellos. Así pues, la imagen de ground truth es la imagen en sí y no será necesario realizar ninguna modificación en este paso (Fig. 17). Figura 17 Imágenes squares utilizadas como ground truth en el método de regiones. Reales En el caso de estas imágenes es diferente puesto que las imágenes no vienen etiquetadas de ninguna manera. Somos nosotros mismos los que definimos el número de etiquetas que creemos debe tener la imagen y a raíz de ello ser capaz de diseñar un ground truth de la imagen original. Para realizarlo, partimos de la imagen de bordes que tenemos de ground truth de bordes de cada imagen real (Fig. 14). A partir de esa imagen de bordes y mediante un programa de edición de imágenes como Gimp [35] rellenamos cada región de un color distinto para poder distinguirlo (Fig. 18). Figura 18. Imagen de ground truth utilizada para las imágenes del grupo reales 2.3.2.2.2 Algoritmo de evaluacio n de regiones Una vez ya tenemos el ground truth de todas las imágenes, procedemos a las comparaciones de píxeles entre regiones. El método que utilizamos se basa en comparar los píxeles que pertenecen a cada región y evaluarlos según true positive, true negative, false positive o false negative. Más adelante se explican las características que tienen cada uno de ellos. Como se puede intuir y dado que lo que se compara es la pertenencia de los píxeles a una región dada, es necesario que las regiones del ground truth y de la imagen segmentada estén etiquetadas de la misma 29 Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color manera, ya que, si las etiquetas no fuesen iguales estaríamos comparando dos regiones distintas y por lo tanto los resultados numéricos no serían fiables puesto que los píxeles que se comparan no serían de las mismas regiones. Para ello, el proceso de comparación se compone de dos pasos: 1. Se ordenan las etiquetas de la misma manera tanto en el ground truth como en la imagen obtenida. El algoritmo que se ha desarrollado para realizar esta tarea consiste básicamente en evaluar el número de píxeles que existen de cada región e ir asignándole de manera descendente el número de etiqueta a cada región. Así si tuviésemos dos regiones donde una de ellas tiene doscientos (200) píxeles y otra de ellas quinientos (500), a la región de 500 píxeles se le asignaría la etiqueta número 1 y a la región de 200 píxeles la etiqueta número dos. Con esto conseguimos que ambas imágenes (ground truth e imagen segmentada) tengan las mismas etiquetas para las mismas regiones, ya que las diferencias de regiones no serán abismales y este método funcionará (Fig. 19). Figura 19. A la izq. la imagen original. A la der. La imagen tras ordenarse las etiquetas de mayor a menor. 2. Se aplica el algoritmo para evaluar las regiones. Este algoritmo consiste en la búsqueda de los píxeles que componen cada región y evaluarlos. En primer lugar el algoritmo separa la imagen en tantos planos como regiones diferentes tenga, tanto la imagen de ground truth como la imagen segmentada. Así, si la imagen tiene 4 etiquetas, se crearán 4 planos. Cada plano contendrá una región y 1’s donde se sitúe cada región de píxeles. Una vez tenemos las dos imágenes separadas por planos se comparan las imágenes plano por plano según los siguiente criterios. Se considerarán pixeles true positive (TP) cuando los píxeles de una misma región coincidan en ambas imágenes. Esto es, si tenemos el primer plano y un píxel es etiquetado en ese plano como perteneciente a la región que hace referencia en ambas imágenes, será true positive. De manera contraria, se considerarán píxeles true negative (TN) cuando los píxeles de un plano, no estén etiquetados como pertenecientes a dicho plano en ambas imágenes. Se considerarán píxeles false positive (FP) cuando un píxel de la imagen segmentada esté etiquetado como perteneciente a una región, pero en la imagen de ground truth ese píxel no sea perteneciente a dicha región. Por último, se tienen los píxeles false negative (FN) cuando un píxel de la imagen segmentada esté etiquetado como no perteneciente a una región pero sí lo esté en la imagen de ground truth. Cuando ya tenemos todos los píxeles clasificados según estos cuatro grupos, procedemos a obtener un valor numérico que nos muestre cómo de buena ha sido nuestra clasificación (segmentación). Desarrollo 30 Sensitivity Mide la proporción de píxeles correctamente identificados. Se calcula como: 𝑇𝑃 𝑇𝑃+𝐹𝑁 ( 2.46 ) Specifity Mide la proporción de píxeles que han sido identificados de manera incorrecta. Se calcula como: 𝑇𝑁 𝑇𝑁+𝐹𝑃 ( 2.47 ) Accuracy Mide la precisión con la que se ha segmentado la imagen. Es la medida más completa ya que aúna la cantidad de los 4 tipos de píxeles. Se calcula como: 𝑇𝑃+𝑇𝑁 𝑇𝑃+𝑇𝑁+𝐹𝑃+𝐹𝑁∗100 (%) ( 2.48 ) En la siguiente figura (Fig. 20) se muestran tres imágenes. La imagen de arriba a la izquierda es la imagen de ground truth de regiones. La imagen de arriba a la derecha es la imagen de regiones de la segmentación realizada con el algoritmo de Continuous Max-Flow y K-means con la distancia CIE2000 y 4 etiquetas. La imagen de abajo se corresponde a la imagen diferencia de ambas. Si las imágenes fuesen totalmente iguales el resultado debería ser una imagen totalmente negra. Sin embargo, al existir diferencias hay zonas que quedan de color blanco que representan los píxeles de no coincidencia entre las imágenes. Como se podrá comprobar más adelante, los valores al realizar este tipo de cálculo es mucho mejor y más realista que en el caso de los bordes, ya que aquí se tienen en cuenta cómo se etiquetan los píxeles y no la forma que adquiere la imagen. 31 Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color Figura 20. Arriba a la izq.: imagen ground truth de regiones. Arriba a la der.: imagen de bordes segmentada con el algoritmo de Continuous Max-Flow.Abajo: imagen diferencia de regiones. 33 3 RESULTADOS ste capítulo servirá para introducir los resultados que hemos obtenidos al poner en práctica la conjunción de los algoritmos propuestos en el capítulo anterior. En primer lugar, se detallará el uso de los algoritmos utilizados para poner en práctica lo que se propuso de forma teórica (véase 2.1.4.2.3). En segundo lugar, se comentarán los diferentes experimentos que se han llevado a cabo para la consecución de los resultados numéricos. Por último, se mostrarán los resultados más representativos que se han obtenido ordenados de una manera clara mediante tablas. 3.1 Algoritmos utilizados En este apartado explicaremos de forma resumida los algoritmos más importantes utilizados para alcanzar los resultados que hemos obtenido. Todos los algoritmos que se han utilizado en este proyecto están escritos en código Matlab, perfectamente comentados, y se pueden solicitar a través en mi dirección de correo electrónico 3 . 3.1.1 Algoritmo de K-means El algoritmo para la segmentación en clusters de imágenes en color utilizando el espacio de color L*a*b, Kmeans, ha sido utilizado como método de etiquetado para la posible combinación con el algoritmo de Continuous Max-Flow. El algoritmo que hemos utilizado se encuentra en [25] y nos ofrece la posibilidad de etiquetar la imagen en color en tantos clusters como queramos. Sin embargo, este algoritmo tan sólo nos ofrecía la posibilidad de usar la distancia euclídea. Es por ello, que el algoritmo verdaderamente utilizado contiene algunas modificaciones con respecto al citado anteriormente. Las modificaciones básicas que se le han hecho con respecto al algoritmo original son las siguientes: 1. Hemos añadido la posibilidad de utilizar otras distancias. Además de la distancia euclídea, como se ha comentado a lo largo del proyecto, también nos interesa utilizar las distancias CIEDE00 y CIEDE94. Es por ello, que se ha modificado el código para tener la posibilidad de elegir la distancia que necesitemos en cada caso. Como es obvio, también contiene las fórmulas necesarias para llevar a cabo el cálculo de dichas distancias. 3 Dirección de correo electrónico: [email protected] E “Do things that have never been done before” -Russell Kirsch - Resultados 34 2. Además, también se han almacenado los vectores de distancia de los distintos píxeles a los centroides tanto en la primera iteración como en la última. Esto es clave, puesto que, son valores que deberemos incorporar al algoritmo de Continuous Max-Flow para que pueda realizar la segmentación de las imágenes. 3. Por último, también se ha tenido en cuenta otro factor como es el tiempo de computación. Se han recogido tanto el tiempo computacional en la primera iteración de K-means como en la última (véase 3.2.2). 3.1.2 Algoritmo de Continuous Max-Flow El algoritmo en el que se fundamenta el estudio y análisis de este trabajo de fin de grado es un algoritmo que se puede encontrar en [26]. El software que se obtiene incluye un programa que ha sido diseñado de forma eficiente para resolver los problemas de segmentación de imágenes multi-region en 2D/3D. Este software, como es lógico, se fundamenta en las ecuaciones enunciadas en los apartados anteriores (2.40). Este algoritmo ha sido desarrollado para tres herramientas de programación, matlab, C y GPU. El uso para matlab es muy sencillo de utilizar. Para que el software pueda resolver los problemas de segmentación multi-región, es necesario que se le introduzcan los valores de las diferentes capacidades 𝐶𝑖, el número de etiquetas nlab y los valores de penalty, entre otros. Es en este lugar donde el funcionamiento conjunto del algoritmo de K-means explicado en el apartado anterior y el algoritmo de Continuous Max-Flow tiene sentido. Los valores de las capacidades 𝐶𝑖 vienen dados por el vector de distancias de cada uno de los píxeles al centroide (Ec. 3.2). Este vector es el generado por el algoritmo de K-means. El número de etiquetas es el mismo que el que se creyó conveniente utilizar en el algoritmo de K-means. Los valores de penalty son utilizados como parámetros de penalización en la detección de bordes y se calcula mediante dos parámetros introducidos ag y bg como: 𝑝𝑒𝑛𝑎𝑙𝑡𝑦= 𝑏𝑔 1+𝑎𝑔∙𝑔𝑟𝑎𝑑(𝑖𝑚𝑎𝑔𝑒𝑛) ( 3.1 ) Donde grad(imagen) indica la función gradiente de matlab realizada a la imagen. 𝑚𝑖𝑛 {Ω𝑖}𝑖=1 𝑛∑∫ 𝐶𝑖(𝑥)𝑑𝑥+𝛼∑|𝜕Ω𝑖| 𝑛 𝑖 Ω𝑖 𝑛 𝑖 ( 3.2 ) Los valores de los 𝐶𝑖(𝑥) son los costes de las capacidades que coindicen en este caso con la distancia de cada uno de los píxeles a los centroides correspondientes. Es la aplicación de la Ec. 2.40 a nuestro caso en concreto, donde se combinan el algoritmo de Max-Flow y K-means. En este caso, no ha sido necesario realizar ningún tipo de modificación al software original. Tan sólo hemos tenido que construir un script que realizase las modificaciones necesarias a la imagen que se va a introducir en el algoritmo y llame al software que realiza la segmentación. 35 Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color 3.2 Experimentos realizados para la consecución de los resultados A continuación, explicaremos los distintos experimentos que se han llevado a cabo para poder obtener los resultados numéricos. Por un lado, hemos realizado la segmentación de las imágenes en color mediante el algoritmo de K-means únicamente. Por otro lado, la segmentación realizada mediante la combinación del algoritmo de K-means y C.Max-Flow. 3.2.1 Kmeans La segmentación de las imágenes en color mediante el algoritmo de K-means (véase 3.1.1) se ha realizado para poder comparar los resultados que se obtienen mediante este método y mediante la actuación combinada del algoritmo de K-means y C.Max-Flow y poder ver así si los resultados mejoran las segmentaciones de las imágenes en color. A pesar de que como se explicó en apartados anteriores, donde el ground truth tiene definidas unas etiquetas que nosotros creemos que son las mejores para su segmentación, el algoritmo de K-means segmenta las imágenes reales a color de 2 a 5 etiquetas cada una de ellas. Con ello, podremos comprobar cuál es la influencia del número de etiquetas en las distintas imágenes en los resultados de la segmentación. 3.2.2 K-means + C.Max-Flow Como ya se ha explicado en apartados anteriores, para poder realizar la segmentación mediante el algoritmo de C.Max-Flow es necesario un vector de distancia de los píxeles a cada uno de los centroides. En relación a esto se han realizado dos tipos de experimentos. En primer lugar, se ha ejecutado el algoritmo de C.Max-Flow con el vector de distancias que el algoritmo de K-means devuelve en la primera iteración. Con ello, dejamos que el algoritmo de C.Max-Flow realice la mayor carga de trabajo en la segmentación. En segundo lugar, se ha ejecutado el algoritmo con el vector de distancias que el algoritmo de Kmeans devuelve en la última iteración. Este experimento se utiliza para ver si el algoritmo realiza alguna mejora notoria sobre la segmentación que K-means realiza en las imágenes a color (véase Observación 1). Observación 1: se ha comprobado que el hecho de introducir al algoritmo de Continuous Max-Flow el vector de distancias de la última iteración del algoritmo de K-means no mejora los resultados obtenidos con éste. Por lo tanto, no se mostrarán los resultados numéricos en las tablas, ya que no tiene ninguna relevancia más allá de esta observación. Por otro lado, el algoritmo de C.Max-Flow admite los valores de penalty (véase 3.1.2). En este sentido, se han utilizado 19 valores para ag y 19 valores para bg, dando lugar a un total de 361 variaciones de los valores de penalty. Por lo tanto, si tenemos que cada imagen ha sido etiquetada por K-means con 2, 3,4 y 5 etiquetas y cada imagen tiene un total de 361 valores distintos de penalty, cada una de las imágenes reales en color lleva consigo un experimento de un total de 1444 grupos de valores distintos (sensitivity, specificty y accuracy) que el algoritmo de C.Max-Flow devuelve que hay que comprobar. Además, el experimento se repite dos veces, puesto que también se comprueba el hecho de probar con el vector de distancias en la primera iteración y en la última. Por lo que en total son 2888 conjuntos de valores que el algoritmo de C.Max-Flow devuelve para cada imagen. Es por ello que, a raíz de la gran cantidad de datos que tenemos para cada una de las imágenes, ha sido necesaria la programación de algoritmos de búsqueda de los valores más óptimos. 3.3 Resultados En este apartado se expondrán todos los resultados más relevantes que se han obtenido en el desarrollo del Resultados 36 proyecto sin comentar las conclusiones que se pueden obtener (véase 4.1). En primer lugar, se presentarán los resultados que se han obtenido de las imágenes denominadas “squares”. En segundo lugar, se expondrán los resultados de las imágenes denominadas “reales” (véase 2.3.1). Todos los valores se presentarán a modo de tabla para que se puedan comparar los resultados. 3.3.1 Imágenes Squares Las imágenes de los rectángulos de colores (squares) han sido utilizadas para ver cuál es la diferencia existente entre el uso de las distintas distancias que se han propuesto utilizar en este proyecto. Como ya se ha dicho, estas imágenes tienen la característica de que muchos de sus colores son prácticamente iguales, de hecho, en muchas de ellas es casi imposible detectar la existencia de cuatro rectángulos a simple vista. En relación a ese problema, a la hora de ejecutar el algoritmo de K-means, muchas veces nos daba el error “Empty cluster at iteration 1”. Esto quiere decir que, en la primera iteración, el algoritmo de K-means no era capaz de encontrar los 4 centroides correctamente, ya que la inicialización de los centroides estaba configurada para que se realice de manera aleatoria. Para resolver este problema se ejecutó el algoritmo de dos maneras: 1. Por un lado, se ejecutó el algoritmo con cada una de las imágenes tantas veces como fuese necesario para que no diese el error de cluster vacío en la primera iteración. (véase Observación 2) 2. Por otro lado, se cambió la forma en la que el algoritmo trata el error de cluster vacío para que en el caso de que encontrara un cluster vacío, en lugar de lanzar el error y que parase la ejecución, crease un nuevo clúster basado en futuras observaciones de su centroide. En el algoritmo, esta opción se modifica mediante el parámetro “EmptyAction” con la opción “singleton”. El caso anterior tendría la opción “error” en su lugar. Observación 2: el hecho de que el algoritmo de K-means sea ejecutado todas las veces que sea necesario para que el algoritmo no dé error de cluster vacío provoca que, todos los resultados obtenidos en relación a este tipo de imágenes sean siempre el valor máximo sea cual sea la distancia y el algoritmo que se aplique. Es por ello que, no se muestran los valores que se han conseguido de esta forma, ya que el algoritmo debe ser capaz de avanzar sin ningún tipo de error y sin supervisión y con esta metodología no lo conseguimos. Aún así, los resultados están disponibles en el paquete donde se incluye el código del proyecto. Los resultados que se muestran a continuación no son el total de las 47 imágenes, pues no considero relevante el hecho de tener que mostrarlas todas. La forma en la que se organiza la información es una tabla donde se muestran: la imagen original y las imágenes tomadas como referencia en cada uno de los experimentos 4 , los valores máximos obtenidos correspondientes a cada uno de los experimentos junto con sus imágenes y las distancias correspondientes (Eu, CIEDE94 y CIEDE00). No es necesario indicar el número de etiquetas de cada experimento, puesto que, en este caso es siempre 4. Además, también se incluirán los valores de penalty en el caso del algoritmo de C.MaxFlow. Los valores que se muestran en la tabla son: -Recall (R). -Precision (P). -Valor F (F). -Accuracy (AC). -Specifity (SP). -Sensitivity (SE). -Tiempo de computación (Tc segundos). 4 En el caso de las imágenes de los cuadrados, la imagen referencia en el cálculo de regiones es la misma que la imagen original. 37 Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color Imagen: 1.bmp K-means K-Means(Iter1)+C.Max-Flow Penalty: ag = 0,01, bg = 0,01 Bordes Todas las distancias Todas las distancias R P F Tc R P F Tc 1 1 1 1,32s 0,778 1 0,875 0,832s Regiones EU, CIEDE 94 Todas las distancias AC SP SE Tc AC SP SE Tc 100 1 1 1,32s 97,79 0,985 0,956 0,832s Tabla 1. Resultados de la imagen 1.bmp. Resultados 44 Imagen: 15.bmp K-means K-Means(Iter1)+C.Max-Flow Penalty: ag = 0,01, bg = 0,01 Bordes EU,CIEDE 94 Todas las distancias R P F Tc R P F Tc 1 1 1 1,27s 0,777 1 0,875 0,775s Regiones EU,CIEDE94 Todas las distancias AC SP SE Tc AC SP SE Tc 100 1 1 1,27s 97,79 0,985 0,956 0,775s Tabla 8. Resultados de la imagen 15.bmp. 45 Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color 3.3.2 Imágenes Reales Los resultados que se muestran a continuación son los referidos a las imágenes reales obtenidas de la base de datos de Berkeley [13]. La forma en la que se organizarán los valores presentados sigue la misma línea que el apartado anterior. En este caso, sí será necesario mostrar el número de etiquetas nlabs con el que está segmentada la imagen y con el que están etiquetados los resultados que se muestran (nlabsBordes y nlabsRegiones), ya que, el número de etiquetas de los resultados más óptimos no tienen por qué coincidir con el número de etiquetas de la imagen tomada como referencia. Sin embargo, el problema que se daba con las imágenes de cuadrados (squares) de “empty clusters” no se da en este tipo de imágenes. (Ver tablas siguiente página) Resultados 46 Imagen: 3096.jpg nlabs = 2 nlabsBordes = 2 nlabsRegiones = 2 K-means K-Means(Iter1)+C.Max-Flow Penalty: ag = 0,01, bg = 0,01 Bordes EU CIEDE 00 R P F Tc R P F Tc 1 0,797 0,887 0,65s 1 0,828 0,906 5,87s Regiones EU CIEDE 00 AC SP SE Tc AC SP SE Tc 99,03 0,993 0,985 0,65s 99,17 0,994 0,988 5,87s Tabla 9. Resultados de la imagen 3096.jpg. 47 Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color Imagen: 8068.jpg nlabs = 4 nlabsBordes = 3 nlabsRegiones = 2 K-means K-Means(Iter1)+C.Max-Flow Penalty Bordes: ag = 0,01, bg = 9,666 Penalty Regiones: ag = 0,01, bg = 0,01 Bordes CIEDE00 CIEDE 00 R P F Tc R P F Tc 0,972 0,349 0,513 24,17s 0,724 0,449 0,554 5,44s Regiones CIEDE 00 EU AC SP SE Tc AC SP SE Tc 94,27 0,962 0,886 45,30s 98,33 0,989 0,967 0,20s Tabla 10. Resultados de la imagen 8068.jpg. Resultados 48 Imagen: 12003.jpg nlabs = 4 nlabsBordes = 4 nlabsRegiones = 4 K-means K-Means(Iter1)+C.Max-Flow Penalty Bordes: ag = 0,01, bg = 3,2289 Penalty Regiones: ag = 17,7138, bg = 8,0572 Bordes EU CIEDE 94 R P F Tc R P F Tc 0,894 0,329 0,481 1,56s 0,913 0,323 0,477 0,19s Regiones EU CIEDE 94 AC SP SE Tc AC SP SE Tc 74,57 0,831 0,491 1,56s 73,33 0,822 0,467 0,19s Tabla 11. Resultados de la imagen 12003.jpg. 49 Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color Imagen: 35070.jpg nlabs = 2 nlabsBordes = 2 (K-means) y 3 (K-means + C.Max-Flow) nlabsRegiones = 2 (K-means) y 4 (K-means + C.Max-Flow) K-means K-Means(Iter1)+C.Max-Flow Penalty Bordes: ag = 0,01, bg = 20,9327 Penalty Regiones: ag = 0,01, bg = 0,01 Bordes EU EU R P F Tc R P F Tc 0,798 0,642 0,711 0,861s 1 0,309 0,473 0,03s Regiones EU CIEDE 94 AC SP SE Tc AC SP SE Tc 98,43 0,988 0,976 0,861s 92,53 0,951 0,888 0,12s Tabla 12. Resultados de la imagen 35070.jpg. Resultados 50 Imagen: 118035.jpg nlabs = 4 nlabsBordes = 3 (K-means) y 2 (K-means+C.Max-Flow) nlabsRegiones = 3 (K-means) y 4 (K-means+C.Max-Flow) K-means K-Means(Iter1)+C.Max-Flow Penalty Bordes: ag = 0,01, bg = 0,01 Penalty Regiones: ag = 0,01, bg = 0,01 Bordes EU CIEDE 00 R P F Tc R P F Tc 1 0,498 0,665 1,08s 0,971 0,455 0,619 5,49s Regiones CIEDE 94 CIEDE 94 AC SP SE Tc AC SP SE Tc 96,52 0,978 0,913 1,64s 95,52 0,972 0,888 0,198s Tabla 13. Resultados de la imagen 118035.jpg. 51 Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color Imagen: 124084.jpg nlabs = 3 nlabsBordes = 2 nlabsRegiones = 2 K-means K-Means(Iter1)+C.Max-Flow Penalty Bordes: ag = 27,3704, bg = 28,9799 Penalty Regiones: ag = 4,8383, bg = 12,8855 Bordes EU EU R P F Tc R P F Tc 0,588 0,599 0,594 0,91s 0,551 0,629 0,587 0,15s Regiones CIEDE 00 EU AC SP SE Tc AC SP SE Tc 93,36 0,950 0,9 0,84s 94,14 0,957 0,913 0,15s Tabla 14. Resultados de la imagen 124084.jpg. Resultados 52 Imagen: 207056.jpg nlabs = 3 nlabsBordes = 4 (K-means) y 2 (K-means+C.Max-Flow) nlabsRegiones = 2 K-means K-Means(Iter1)+C.Max-Flow Penalty Bordes: ag = 8.0572, bg = 12.885 Penalty Regiones: ag = 0,01, bg = 14,4949 Bordes CIEDE 00 EU R P F Tc R P F Tc 0,938 0,153 0,26 39,66s 1 0,446 0,617 0,29s Regiones CIEDE 00 EU AC SP SE Tc AC SP SE Tc 91,80 0,945 0,836 15,29s 95,55 0,970 0,911 0,33s Tabla 15. Resultados de la imagen 207056.jpg. 53 Análisis de la aplicación de algoritmos de K-means y Continuous Max-Flow a la segmentación de imágenes en color Imagen: 238011.jpg nlabs = 3 nlabsBordes = 4 (K-means) y 2 (K-means+C.Max-Flow) nlabsRegiones = 2 K-means K-Means(Iter1)+C.Max-Flow Penalty Bordes: ag = 0,01, bg = 0,01 Penalty Regiones: ag = 0,01, bg = 0,01 Bordes CIEDE 94 CIEDE 94 R P F Tc R P F Tc 1 0,691 0,817 2,92s 0,963 0,695 0,807 0,13s Regiones EU CIEDE 94 AC SP SE Tc AC SP SE Tc 98,22 0,988 0,964 0,66s 98,24 0,988 0,965 0,13s Tabla 16. Resultados de la imagen 238011.jpg. Referencias 60 [33] Vivek Kwatra, Arno Schoedl, Irfan Essa, Greg Turk, and Aaron Bobick. Graphcut textures: Image and video synthesis using graph cuts. ACM Transactions on Graphics, SIGGRAPH 2003, 22(3):277–286, July 2003. [34] Ben Appleton and Hugues Talbot. Globally minimal surfaces by continuous maximal flows. IEEE Trans. Pattern Anal. Mach. Intell., 28(1):106–118, 2006. [35] Programa Gimp. http://gimp.es