Download redes neuronales no supervisadas con topología din´amica para la
Document related concepts
Transcript
UNIVERSIDAD DE MÁLAGA ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA INFORMÁTICA INGENIERO TÉCNICO EN INFORMÁTICA DE SISTEMAS REDES NEURONALES NO SUPERVISADAS CON TOPOLOGÍA DINÁMICA PARA LA SEGMENTACIÓN DE IMÁGENES EN COLOR. Realizado por ANTONIO DÍAZ RAMOS Dirigido por EZEQUIEL LÓPEZ RUBIO Departamento LENGUAJES Y CIENCIAS DE LA COMPUTACIÓN MÁLAGA, Noviembre 2010 1 UNIVERSIDAD DE MÁLAGA ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA INFORMÁTICA INGENIERO TÉCNICO EN INFORMÁTICA DE SISTEMAS Reunido el tribunal examinador en el dı́a de la fecha, constituido por: Presidente/a Do /Da . Secretario/a Do /Da . Vocal Do /Da . para juzgar el proyecto Fin de Carrera titulado: realizado por Do /Da tutorizado por Do /Da . y, en su caso, dirigido académicamente por Do /Da . ACORDÓ POR OTORGAR LA CALIFICACIÓN DE Y PARA QUE CONSTE, SE EXTIENDE FIRMADA POR LOS COMPARECIENTES DEL TRIBUNAL, LA PRESENTE DILIGENCIA. de Málaga a 2 del 20 Índice general 1. Introducción. 1.1. Descripción de un mapa auto-organizado. . . . 1.2. Aprendizaje en un mapa auto-organizado. . . 1.3. Algunas variantes de mapas auto-organizados. 1.4. Otras variantes de mapas auto-organizados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 7 11 15 20 2. Nuevo enfoque teórico. 23 2.1. Recuperando las variantes. . . . . . . . . . . . . . . . . . . . . 26 3. Un 3.1. 3.2. 3.3. 3.4. mapa auto-organizado generalizado. Construcción de la densidad continua. . . . . Construcción del grafo de distancias. . . . . Construcción de las geodésicas y la distancia Funcionamiento del mapa auto-organizado. . . . . . . . . . . . . . geodésica. . . . . . . 4. Aplicación a la segmentación de imágenes. 4.1. Implementación MATLAB. . . . . . . . . . . . . . 4.2. Dependencia de los parámetros. . . . . . . . . . . 4.3. Resultados. . . . . . . . . . . . . . . . . . . . . . 4.3.1. Algoritmo de aprendizaje de dos fases. . . 4.3.2. Algoritmo de aprendizaje de dos fases con convergencia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . criterio de . . . . . . . . . . 28 30 32 36 42 . . . . 43 47 50 55 61 . 66 5. Discusión y conclusiones. 69 A. Geometrı́a y Topologı́a. 74 B. Glosario. 81 3 Capı́tulo 1 Introducción. Los mapas auto-organizados o redes de Kohonen (SOM por sus siglas en inglés, self-organizing map) fueron introducidos por el profesor finlandés Teuvo Kohonen en los artı́culos [8, 9]. Un mapa auto-organizado es una herramienta que analiza datos en muchas dimensiones con relaciones complejas entre ellos y los presenta en una visualización sencilla en sólo dos dimensiones. La propiedad más importante de una SOM es que preserva las propiedades topológicas de los datos, es decir, que datos próximos aparecen próximos en la visualización. Para entender las posibilidades de un mapa auto-organizado imaginemos por un momento que queremos comparar los niveles de vida de distintos paı́ses. Los datos estadı́sticos del Banco Mundial para 126 paı́ses dan 39 indicadores de calidad de vida para cada paı́s, relacionados con salud, nutrición, educación, etc. El efecto conjunto y complejo de todos estos factores se puede visualizar en un mapa auto-organizado. Los paı́ses que tienen niveles de vida similares aparecen uno junto a otro en el mapa, y los colores sólo se han añadido para resaltar las similitudes entre paı́ses: 4 CAPÍTULO 1. INTRODUCCIÓN. Figura 1.1: Niveles de vida de diversos paı́ses en un mapa auto-organizado. Los datos son del Banco Mundial son de 1992 y el ejemplo está tomado de la Universidad Tecnológica de Helsinki (http://www.cis.hut.fi/research/somresearch/worldmap.html), donde actualmente trabaja el profesor Kohonen. En este caso, datos estadı́sticos complejos en 39 dimensiones han sido representados usando únicamente dos dimensiones y preservando en el proceso las relaciones de proximidad entre los datos. La literatura relacionada con los mapas auto-organizados y sus aplicaciones es muy diversa y numerosa. Desde su origen en 1981 se han publicado más de 7000 artı́culos que usan, analizan o se benefician de las SOM de algún modo, incluyendo las siguientes áreas: imagen y vı́deo, reconocimiento de patrones, técnicas matemáticas, inteligencia artificial, software, ingenierı́a en biologı́a y medicina, teorı́a de la información y la codificación, reconocimiento de voz, control, procesamiento de señales, circuitos, ciencias de la información y documentación y negocios y administración [10, 16, 19]. Este trabajo arranca del concepto de mapa auto-organizado y se ramifica en una parte teórica y otra práctica. Partiendo de una descripción de los mapas auto-organizados y algunas de sus variantes más populares desarrollamos un nuevo concepto de mapa auto-organizado generalizado. El nuevo enfoque se llevará a cabo mediante conceptos matemáticos del área de la 5 CAPÍTULO 1. INTRODUCCIÓN. Geometrı́a y la Topologı́a. La parte práctica del proyecto se concretará en la aplicación de estas ideas al diseño de un mapa auto-organizado generalizado que realice segmentación de imágenes en color. Éste constará esencialmente de los mismos elementos que posee un mapa auto-organizado, a saber, un conjunto de neuronas con una topologı́a y un algoritmo de aprendizaje. Para evaluar la eficacia de este nuevo tipo de red neuronal no supervisada en la segmentación de imágenes en color se realizará un análisis estadı́stico a posteriori. El contenido del trabajo se subdivide en 3 capı́tulos y 2 apéndices. El primero de ellos empieza con esta introducción y las dos secciones siguientes 1.1 y 1.2 se dedican, respectivamente, a una primera descripción elemental de los mapas auto-organizados tras introducir conceptos básicos de redes neuronales artificiales, y a una exposición detallada del algoritmo de aprendizaje de un mapa auto-organizado, incluyendo las ecuaciones introducidas por Kohonen. Las dos siguientes secciones se dedican a revisar algunos artı́culos que presentan variantes de mapas auto-organizados o construcciones relacionadas. La sección 1.3 se centra en las variantes que modifican la topologı́a, distancia entre neuronas o distancia entre la entrada y las neuronas. La sección 1.4 en cambio presenta trabajos no tan directamente relacionados con estas componentes de un mapa auto-organizado. En ambas secciones se van abstrayendo y resaltando las ideas que dan a lugar a variantes de mapas auto-organizados y que a nuestro juicio merece la pena destacar. El Capı́tulo 2 contiene el desarrollo teórico. Como hilo motivador y conductor del desarrollo teórico se usarán las ideas que se destacaron en la secciones 1.3 y 1.4. Para lo conceptos matemáticos involucrados se remite al lector al Apéndice A. El Capı́tulo 3 contiene una aplicación de las ideas desarrolladas en el Capı́tulo 2. Se describe un mapa auto-organizado generalizado cuya diferencia fundamental con los mapas auto-organizados clásicos estriba en que las neuronas recorren las geodésicas en cierta métrica en vez de segmentos rectilı́neos. Esta construcción se complementa con el Capı́tulo 4, donde se proporciona una instancia de este mapa auto-organizado aplicado al proble6 CAPÍTULO 1. INTRODUCCIÓN. ma de la segmentación de imágenes en color. Esto se ha concretado como una serie de ejecutables en MATLAB y en C. Se concluye el capı́tulo con un estudio comparativo estadı́stico de la calidad de los resultados obtenidos con este nuevo método. El último capı́tulo contiene una discusión de los logros y limitaciones de este trabajo, ası́ como varias direcciones en las que seguir investigando a partir de lo aquı́ expuesto. El Apéndice A contiene las definiciones matemáticas necesarias del ámbito de la Geometrı́a y Topologı́a para introducir el concepto de variedad diferenciable Riemanniana, ası́ como los conceptos de distancia geodésica y geodésica (minimizante) en estas variedades. El Apéndice B contiene un glosario de términos especializados relacionados con el área de redes neuronales artificiales y algunas de sus aplicaciones. 1.1. Descripción de un mapa auto-organizado. Un SOM o mapa auto-organizado se puede clasificar como un tipo particular de red neuronal artificial. Recordemos que una red neuronal artificial es un objeto computacional que hace las veces de una función o aplicación entre un determinado espacio de entrada y un espacio de salida f : X → Y : Figura 1.2: Red neuronal artificial como una función. Las redes neuronales artificiales están modeladas en la biologı́a del cerebro humano y constan de una serie de unidades o neuronas interconectadas. La función f que representa un red neuronal artificial depende directamente de estas neuronas y sus interconexiones. Su principal virtud y aquello que 7 CAPÍTULO 1. INTRODUCCIÓN. caracteriza a las redes neuronales artificiales es que son capaces de aprender. El aprendizaje se consigue alterando la naturaleza de la red misma: las conexiones y su intensidad ası́ como las neuronas mismas se modifican. Estos cambios producen a su vez que la función f que representa la red se altere. Este proceso ocurre en una serie de etapas o iteraciones en cada una de las cuales se produce una actualización de la red neuronal y de la función que representa. Las redes neuronales artificiales se clasifican según el tipo de aprendizaje que contemplen: Aprendizaje supervisado: dado un conjunto de pares {(xi , yi )}i=1,...,M pertenecientes a X × Y la red aprende para dar la mejor aproximación a una función f que satisfaga f (xi ) = yi . Aprendizaje no supervisado: se parte de un conjunto o distribución en el espacio de entrada {xi }i=1,...,M y la red aprende para dar una función f que minimize una función de coste C = C(f ). En vez de introducir aquı́ en detalle el paradigma completo de las redes neuronales artificiales y sus distintos tipos vamos a centrarnos en describir en profundidad los mapa auto-organizados, ya que son el único tipo de red neuronal artificial que se utiliza a lo largo de este trabajo. Los mapas auto-organizados son un tipo particular de red neuronal artificial con aprendizaje no supervisado. Un mapa auto-organizado consiste en un conjunto de nodos o neuronas usualmente dispuestos en forma unidimensional o en forma de malla de dos dimensiones con distribución ortogonal o hexagonal: 8 CAPÍTULO 1. INTRODUCCIÓN. Figura 1.3: Distribuciones tı́picas de las neuronas en un mapa autoorganizado. Las conexiones entre las neuronas que se observan en la figura son crı́ticas para el funcionamiento del mapa auto-organizado. Cada neurona de la malla tiene asociado un vector de las mismas dimensiones que el espacio de entrada. Este vector se conoce como vector de pesos de la neurona. Por esto mismo uno puede imaginar la red neuronal como un un segmento unidimensional o una malla bidimensional, según corresponda, que yace en el espacio de entrada. Durante el proceso de aprendizaje estos vectores se modifican iterativamente: cuando se presenta un dato de entrada x a la red la neurona con el vector de pesos más cercano y sus neuronas próximas en la malla de la red modifican sus pesos de forma que se asemejen más a la entrada x. Figura 1.4: Aprendizaje en un mapa auto-organizado. En la figura anterior se representa una red bidimensional dispuesta en el espacio de entrada a la izquierda. En la imagen central un dato de entrada x es presentado a la red y la neurona más cercana se selecciona (en rojo). Finalmente, esta neurona y su vecinas en la malla se mueven hacia la entrada x. La neurona más cercana o neurona ganadora se suele denotar por sus siglas en inglés BMU (best matching unit). Este tipo de aprendizaje se conoce cómo 9 CAPÍTULO 1. INTRODUCCIÓN. aprendizaje competitivo ya que las neuronas compiten por ser la más cercana a la entrada. Después de un número suficiente de iteraciones, la red se adapta a la forma de los datos o distribución de entrada {xi }i=1,...,M : Figura 1.5: Mapa auto-organizado tras un número grande de iteraciones. La función f : X → Y asociada a un mapa auto-organizado es la función que asigna a cualquier valor de entrada x la neurona de la malla cuyo vector de pesos es más cercana a la entrada, es decir, la BMU. Por tanto en este caso el espacio de salida es la malla de la red. Por sencillez denotemos a esta función por BM U : X → malla de la red, en vez de por f . Abusando un poco de notación usaremos BMU tanto para denotar la neurona ganadora en la malla como para denotar su vector de pesos en el espacio de entrada. Qué versión estamos usando estará claro por el contexto. Como comentamos anteriormente un mapa-organizado es un red neuronal artificial con aprendizaje no supervisado y por tanto debe haber una función de coste asociada que el mapa intenta minimizar durante su aprendizaje. En nuestras aplicaciones esta función de coste será el error cuadrático medio o M SE por sus siglas en inglés, mean squared error: PM ||xi − BM U (xi )||2 M SE = , (1.1) M son los datos de entradas y M el número de entradas o i=1 donde {xi }i=1,...,M 10 CAPÍTULO 1. INTRODUCCIÓN. muestras. Esta cantidad mide como de bien la red ha capturado la distribución de entrada. En general, el funcionamiento de un mapa auto-organizado se puede dividir en tres etapas: 1. Inicialización de los vectores de peso de las neuronas. 2. Aprendizaje de la red. 3. Evaluación de una función de coste como (1.1). En la siguiente sección se explican las dos primeras etapas en detalle. 1.2. Aprendizaje en un mapa auto-organizado. En esta sección repasamos las ecuaciones clásicas introducidas por Kohonen que determinan el aprendizaje en un mapa auto-organizado. Supongamos que los datos de entrada viven en el espacio real de n dimensiones Rn . Ası́ que xi ∈ Rn para cada muestra de los datos de entrada {xi }i=1,...,M . Consideremos una población de N neuronas y denotemos por ni el vector de pesos de Rn asociado a la neurona i para i = 1, . . . , N . Usemos la variable t para denotar la iteración actual t = 0, 1, 2, 3, . . ., de manera que ni (t) corresponde al vector de la neurona i en el instante t. Por último, denotemos por x(t) el dato de entrada que se presenta a la red en la iteración t. Este valor será una de las muestras de entrada {xi }i=1,...,M y es elegida de entre todas ellas mediante algún orden o algún procedimiento aleatorio. Podemos dar ahora una fórmula explı́cita para el movimiento de las neuronas hacia la entrada cuando esta es presentada a la red: ni (t + 1) = ni (t) + γ(t, x(t), i)(x(t) − ni (t)). (1.2) Nótese que x(t) − ni (t) es un vector que apunta desde la posición de la neurona i hacia la entrada x(t). Por tanto, los nuevos pesos de la neurona i, ni (t + 1), se obtienen sumando a la posición actual, ni (t), un múltiplo de este vector. La magnitud de este múltiplo viene dada por la cantidad 11 CAPÍTULO 1. INTRODUCCIÓN. γ = γ(t, x(t), i) que depende de la iteración en la que nos encontramos t, de la entrada x(t) y de la neurona i en cuestión. Esta cantidad γ debe ser un número entre 0 y 1, 0 ≤ γ ≤ 1, y por tanto la nueva posición de la neurona i-ésima se encuentra recorriendo γ por ciento del segmento que va desde la posición actual de la neurona hasta la entrada. Figura 1.6: Recorrido a lo largo del segmento neurona-entrada. La función γ debe satisfacer las dos siguientes condiciones: ser función decreciente de la distancia entre la neurona i y la neurona ganadora BM U en la malla unidimensional o bidimensional del mapa auto-organizado, y ser función decreciente del tiempo t. Esto quiere decir que cuanto más alejada en la malla este una neurona de la BMU menos aprenderá y que conforme avanza el número de iteraciones las neuronas irán aprendiendo menos. Por lo general la función γ se escribe como el producto de dos funciones γ = θ(t, x(t), i)·η(t), donde θ se conoce como la función de entorno o vecindad y η es la función de aprendizaje. Un ejemplo habitual de función de entorno es la (pseudo) distribución normal 2 θ(t, x(t), i) = e −dmalla (i,BM U ) 2σ(t)2 , (1.3) donde dmalla (i, BM U ) es la distancia en la malla entre la neurona i y la neurona ganadora BM U . Esta distancia se define como la distancia euclı́dea entre las neuronas en el espacio euclı́deo en el que la malla se halla inmersa. Además, asumimos que la distancia entre dos neuronas adyacentes de la malla 12 CAPÍTULO 1. INTRODUCCIÓN. es 1. Esto es una normalización que será útil después. El papel de la varianza σ(t) es determinar como de lejos llega la influencia de la BMU en la malla. Recordemos que aproximadamente el 68 % de la distribución θ se lo llevarán las neuronas que estén a una distancia menor o igual que la varianza σ(t). La varianza σ(t) debe decrecer con el tiempo. De esta forma, el entorno de neuronas de la malla alrededor de la BMU que aprenden va decreciendo con el tiempo: Figura 1.7: Los entornos alrededor de la BMU encogen con el tiempo. El decrecimiento de la varianza se modela como sigue: −t σ(t) = σ0 · e λ , donde λ es una constante relacionada con el número máximo de iteraciones y tamaño del entorno inicial: λ= N umM axIteraciones . log(σ0 ) Se deduce que cuando t iguala el número máximo de iteraciones σ(t) toma el valor 1. Por tanto, la influencia del aprendizaje de la BMU se reduce a ella misma (ya que las neuronas adyacentes están a una distancia de 1). Por otro lado, el entorno inicial σ0 se inicializa con la mitad de la distancia máxima entre cualesquiera dos neuronas de la malla, es decir, con el “radio” de la malla. 13 CAPÍTULO 1. INTRODUCCIÓN. La función de aprendizaje tiene una expresión similar: −t η(t) = η0 · e λ , donde el coeficiente de aprendizaje inicial η0 es un número entre 0 y 1. Esto quiere decir que las neuronas sufrirán un proceso de “aprendizaje rápido y olvido lento”. Los vectores de pesos de las neuronas se inicializan con algún procedimiento aleatorio, como tomar valores aleatorios dentro de un rango significativo o tomar directamente el valor de muestras elegidas aleatoriamente. El número máximo de iteraciones que llevará a cabo el algoritmo de aprendizaje lo hemos denotado N umM axIteraciones. Este número puede ser, por ejemplo, el número de muestras, con lo que se realiza una iteración para cada muestra. También puede existir algún criterio de convergencia que determine la parada del algoritmo antes de llegar a N umM axIteraciones iteraciones. Por ejemplo, se puede estudiar si el cambio de posición en las neuronas es suficientemente pequeño como para parar el proceso de aprendizaje. Esto describe en reglas generales el aprendizaje en un mapa auto-organizado. En las aplicaciones prácticas puede haber variaciones en las exponenciales usadas, la inicialización de las neuronas, el criterio de convergencia, etc. Ejemplo 1.2.1. Como ejemplo práctico de los coeficientes de aprendizaje supongamos que tenemos una malla unidimensional de 10 neuronas, que tomamos 100 muestras y que realizamos una iteración por muestra. Según las fórmulas vistas anteriormente tendremos los siguientes valores para el entorno inicial y para la constante λ: σ0 = 5 , λ = 100/ log(5) ≈ 62,133. Tomemos además el coeficiente de aprendizaje inicial η0 = 0,9. En la siguiente gráfica hemos representado en rojo el coeficiente γ = θ · η para la BMU y en azul el mismo coeficiente para una neurona que se encuentra a la distancia máxima de la BMU, es decir, para los casos dmalla (i, BM U ) = 0 y 14 CAPÍTULO 1. INTRODUCCIÓN. dmalla (i, BM U ) = 9 respectivamente. 0.9 neurona BMU neurona a distancia máxima 0.8 0.7 coeficiente 0.6 0.5 0.4 0.3 0.2 0.1 0 0 20 40 60 Número de iteración 80 100 Figura 1.8: Coeficientes para la BMU y para una neurona a distancia máxima. 1.3. Algunas variantes de mapas auto-organizados. En esta sección comentamos algunos artı́culos que presentan variantes de los mapas auto-organizados tal y como fueron introducidos en las secciones 1.1 y 1.2. En el apéndice A se puede encontrar una introducción a los conceptos matemáticos que usamos. A lo largo de la sección se irán destacando variantes a las que puede someterse un mapa auto-organizado. Una de las fuentes más ricas de alteraciones de los mapas auto-organizados clásicos es el uso de distintas topologı́as y distancias entre las neuronas. Aquı́ entendemos por esta topologı́a la manera en que las neuronas están conectadas entre sı́. Por ejemplo, hemos visto anteriormente que las topologı́as clásicas consisten en un grafo lineal con cada neurona (salvo los 2 extremos) conectada a 2 vecinos o un grafo plano en que cada neurona (excepto los 15 CAPÍTULO 1. INTRODUCCIÓN. 4 bordes) se conecta a 4 vecinos (distribución ortogonal) o 6 vecinos (distribución hexagonal). Recordemos (Sección 1.2) que para estos casos hemos definido la distancia entre neuronas como la distancia euclı́dea entre ellas en el espacio en el que la malla se halla inmersa. Una primera idea es sustituir el segmento por un cı́rculo y la malla cuadrada por un toro. Ası́ se consigue que todas las neuronas tengan 2 vecinos en el caso unidimensional o 4 o 6 vecinos en el caso bidimensional. Figura 1.9: Malla unidimensional con topologı́a circular. Los trabajos [13] y [15] van más allá y consideran una matriz cuadrada que almacena la distancia entre cada par de neuronas de la malla. Estas distancias no provienen de la inmersión de la malla en un espacio (euclı́deo por ejemplo) como anteriormente, por lo que no corresponden a las distancias entre las neuronas en algún espacio si no a una medida abstracta. De estas ideas podemos abstraer el concepto de que la topologı́a y distancias entre neuronas podrı́an estar en general determinadas por un espacio al que las neuronas pertenecen. Este espacio serı́a el sustituto para el espacio euclı́deo o el cı́rculo o el toro vistos arriba. Como requerimos una distancia entre puntos de este espacio, debemos considerar espacios métricos, es decir, espacios dotados de una métrica o distancia. De lo comentado sobre [15] nos quedamos con la idea de que las distancias entre neuronas podrı́an variar, o equivalentemente, las neuronas podrı́an moverse en este espacio métrico. En resumen: Variante 1.3.1. Sustituir la topologı́a y distancia entre neuronas por la topologı́a y distancias en una espacio métrico al que pertenecen y en el que se 16 CAPÍTULO 1. INTRODUCCIÓN. mueven las neuronas. Otro grupo de autores han apostado por conservar la topologı́a y distancias clásicas y variar en cambio el tipo de distancia entre la entrada y las neuronas en el espacio de entrada. Recordemos que una fase fundamental del aprendizaje es determinar la BMU calculando el mı́nimo de estas distancias. Ası́ que estamos ante variaciones crı́ticas de un mapa auto-organizado. En lo que llevamos visto el espacio de entrada es un espacio euclı́deo y la distancia de la entrada a las neuronas es simplemente la distancia euclı́dea entre la entrada y el vector de pesos de las neuronas. El nuevo enfoque consiste en conservar el espacio euclı́deo como espacio de entrada pero dotarlo de otra métrica. Esta nueva métrica se usa para calcular las distancias entrada-neuronas. Esto se hace en dos fases: (a) se da un modelo continuo de densidad que ajuste los datos de entrada, y (b) se usa esta densidad para definir una métrica Riemanniana en el espacio euclı́deo de entrada. Estas métricas se conocen como métricas de aprendizaje (learning metrics) y se utilizan en los artı́culos [20], [18] y [11]. Estas nuevas métricas se ajustan a los datos y permiten descubrir propiedades intrı́nsecas de los datos, lo cual es básico en un paradigma no supervisado como el de los mapas auto-organizados. Ejemplo 1.3.1. Como ejemplo veamos cómo estas métricas pueden permitir aislar agregaciones de datos en problemas de clustering [20]. La siguiente figura muestra una configuración de datos con forma de dos medias lunas engarzadas, ası́ como un modelo de densidad continuo que se ajusta a los datos. Los entornos rojos y azules corresponden a entornos en métrica euclı́dea y en métrica de aprendizaje de un mismo punto respectivamente. Claramente la métrica de aprendizaje es capaz de separar mucho mejor las dos componentes de los datos que la métrica euclı́dea. 17 CAPÍTULO 1. INTRODUCCIÓN. Figura 1.10: Métrica de aprendizaje versus métrica euclı́dea. En este caso la matriz de la métrica Riemanniana en el punto x ∈ Rn viene dada por [20, Ecuación (2)] G(x) = ∇log p(x)(∇log p(x))t , donde p es el modelo de densidad continua y ∇ es gradiente. Esto quiere decir que la métrica es sensible a los cambios (en el logaritmo) de la densidad. Zonas con pocos cambios corresponden a distancias cortas y zonas con muchos cambios a distancias largas. En el trabajo original el autor aplica el algoritmo de clustering “medias-k” (o k-means en inglés) para mostrar como la métrica Riemanniana supera con creces a la euclı́dea al agrupar los datos de entrada de una configuración similar a la mostrada aquı́ [20, Figure 2]. De esto podemos concluir otro tipo de variante para los mapas autoorganizados Variante 1.3.2. Sustituir la métrica euclı́dea en el espacio de entrada por una métrica Riemanniana construida a partir de una una densidad continua que se ajusta a los datos de entrada. Entre los métodos para construir la densidad continua a partir de la nube de datos de entrada (a) cabe destacar [14]. La densidad construida aquı́ consiste en un conjunto de distribuciones normales cuyos parámetros se estiman a partir de los datos de entrada y cuyo número de direcciones principales se ajustan también a los datos. Este método será descrito con mayor detalle en la Sección 3.1. 18 CAPÍTULO 1. INTRODUCCIÓN. Profundizando un poco más en el punto (b) destaca el problema de como calcular la distancia entre dos puntos alejados dada, como en el ejemplo 1.3.1, la matriz de la métrica en cada punto. Esto es, queremos calcular la geodésica o camino más corto entre dos puntos p y q del espacio euclı́deo dotado de una métrica Riemanniana. En vez de minimizar la longitud en la métrica Riemanniana (integral de camino) sobre todos los caminos entre p y q aquı́ seguimos un enfoque práctico e intentamos aproximar esta geodésica por un camino lineal a trozos. El método más sencillo es definir la distancia geodésica como la longitud en la métrica Riemanniana del segmento rectilı́neo entre p y q. La integral de camino resultante se puede aproximar con un trapezoide. Otro método más razonable, usado en [18] y [20], consiste en elegir el camino que minimiza la distancia entre p y q en un grafo con vértices en el espacio euclı́deo de entrada que incluye a p y q, y cuyas aristas tienen pesos dados por las longitudes en la métrica Riemanniana de los segmentos rectilı́neos entre los vértices (método explicado antes). La elección del camino óptimo en el grafo se puede realizar con un algoritmo como el de Floyd. La discusión de qué vértices y aristas se usan para construir el grafo la posponemos. Figura 1.11: Geodésicas y distancias geodésicas usando un segmento y un grafo. Al camino construido según este método lo llamaremos geodésica entre p y q y a la suma de los pesos de las aristas que incluye dicho camino la llamaremos distancia geodésica entre p y q. 19 CAPÍTULO 1. INTRODUCCIÓN. Variante 1.3.3. Sustituir la distancia euclı́dea entre la entrada y las neuronas por la distancia geodésica correspondiente. Es interesante que aunque los trabajos citados usen distancia geodésica para calcular la BMU no usan en ningún caso la geodésica para desplazar las neuronas hacia la entrada. En realidad se usa el camino que minimiza la distancia geodésica sólo localmente y, como se deduce en [11, III.A y III.B], esto nos trae de vuelta al segmento rectilı́neo entre la neurona y la entrada. Esto nos permite introducir la siguiente novedad: Variante 1.3.4. Sustituir el desplazamiento a lo largo del segmento entre la neurona y la entrada por el desplazamiento a lo largo de la geodésica correspondiente. 1.4. Otras variantes de mapas auto-organizados. En esta sección discutimos otras variantes de mapas auto-organizados que no están tan directamente relacionados con la topologı́a, distancia entre neuronas o distancia entre entrada y neuronas como las de sección anterior. Aquı́ también recopilamos las variantes destacadas. Empezamos discutiendo modificaciones que se centran en la dinámica de la población de neuronas. Recordemos que en los casos clásicos las neuronas y las conexiones entre ellas son estáticas. Sin embargo, en el trabajo [1] se presenta el mapa auto-organizado LARFSOM (local adaptive receptive field SOM), en el cual las neuronas y las conexiones entre ellas pueden crearse y destruirse según las necesidades de la red. La creación de neuronas tiene lugar cuando la BMU no está suficientemente cerca de la entrada. Una neurona es destruida cuando queda desconectada del resto de la red. En el trabajo [6] se presentan “The Growing Hierarchical Self-Organizing Map”, el mapa auto-organizado jerárquico que crece. En este caso hay construcción de neuronas y aristas cuando la información que guarda una porción de la red necesita ser subclasificada con más detalle. No hay destrucción de neuronas o aristas. 20 CAPÍTULO 1. INTRODUCCIÓN. Variante 1.4.1. Permitir la creación y destrucción de neuronas y aristas en la malla para adaptarse mejor a los datos de entrada. Por otro lado, en los trabajos [5] y [21] se modifican las estrategias mismas de competitividad entre las neuronas con los mapas auto-organizados FS-SOM (frequency sensitive SOM) y SA-SOM (sample-size adaptive SOM) respectivamente. En ambos casos las neuronas que ganan repetidamente son penalizadas de forma que tienen menos posibilidades de ganar en las próximas iteraciones. De esta forma se favorece a todas las neuronas más homogéneamente. En [21] además el entorno de una neurona se reduce progresivamente cuando esta neurona es la BMU repetidamente. Variante 1.4.2. Modificar la estrategia de competitividad para dar iguales oportunidades a todas las neuronas. Siendo la visualización en dos dimensiones de datos en muchas dimensiones una de las caracterı́sticas más destacadas de los mapas auto-organizados no es de extrañar que se hayan planteado otras opciones con este objetivo en mente. En [12] se explica un método para crear una representación en un toro dos dimensional de datos en muchas dimensiones, preservando las distancias tanto como sea posible. El método se conoce como relational perspective map, mapa en perspectiva relacional. La idea es resolver las ecuaciones diferenciales que resultan de una dinámica de partı́culas sobre el toro en la que se considera una partı́cula por cada dato de entrada y en el que las fuerzas son proporcionales a las distancias originales en el espacio de entrada (e inversamente proporcionales a las distancias sobre el toro). Esta idea de que las neuronas “se mueven” al aprender refuerza la Variante 1.3.1. Por otro lado, en [3] se presenta la “GTM: The Generative Topographic Mapping”, la aplicación topográfica generativa. En este caso la visualización dos dimensional se consigue en dos fases. Primero, se construye una función que va de una malla bidimensional de neuronas al espacio de entrada. Esta función se define a través de funciones no lineales y el proceso de aprendizaje consiste en ajustar los parámetros de estas funciones hasta conseguir una adaptación óptima a la nube de datos de entrada. Nótese que la función BMU en un mapa auto-organizado clásico es del tipo BM U : X → malla de la red 21 CAPÍTULO 1. INTRODUCCIÓN. (ver Sección 1.1) y que aquı́ estamos considerando una función en sentido contrario malla de la red → X (donde X es el espacio de entrada). La segunda fase de este método consiste en construir una aplicación en el “sentido correcto” usando el teorema de Bayes. Los dos últimos trabajos comentados no son variantes de un mapa autoorganizado sino conceptos esencialmente distintos aunque relacionados. Lo mismo ocurre con el trabajo [17], que está relacionado con problemas de clustering. Aquı́ se expone el concepto de afinidad como concepto alternativo al de clustering: en vez de decidir que datos pertenecen al mismo cluster se construye un número, la afinidad, entre cada par de datos de entrada. Esta afinidad se construye a partir de un “feature space” o espacio de caracterı́sticas como un histograma, y es proporcional a la longitud del camino en este espacio que minimiza la distancia euclı́dea y evita las regiones de baja densidad. Nos quedamos con la siguiente idea: Variante 1.4.3. La métrica Riemanniana de que se dota al espacio de entrada a partir de una densidad continua podrı́a ser tal que las geodésicas eviten las zonas de baja densidad. Nótese que la métrica Riemanniana presentada en el Ejemplo 1.3.1 tiende a evitar las zonas con mucho cambio en la densidad, lo cual es diferente de lo expuesto en la variante anterior. Por último, mencionar los trabajos [22] y [7]. En el primero se presenta un tipo especial de mapa auto-organizado con dos tipos de neuronas como solución a un problema de cuantificación vectorial (VQ por sus siglas en inglés, vector quantization). Se aplica a compresión de imágenes. En el trabajo [7] un mapa auto-organizado es usado como paso previo a un proceso de clustering mediante templado simulado (SA por sus siglas en inglés, simulated annealing). El templado es un proceso fı́sico en el que algún material es sometido a altas temperaturas para después dejarlo enfriar lentamente. Destaquemos aquı́ también que este artı́culo trata sobre segmentación de imágenes en color y que trabaja en el espacio de color CIELU V , un espacio de color donde la diferencia en percepción es proporcional a la diferencia entre los colores (en el espacio de color RGB este no es el caso). 22 Capı́tulo 2 Nuevo enfoque teórico. Este capı́tulo se puede considerar como un ejercicio de abstracción del concepto de mapa auto-organizado. Basándonos en las Secciones 1.3 y 1.4 daremos una definición de mapa auto-organizado generalizado. Ésta no servirá directamente como herramienta práctica sino más bien como marco desde que el iniciar o generar aplicaciones concretas. Esto es, por ejemplo, lo que haremos en el Capı́tulo 3, donde elegiremos de este concepto de mapa autoorganizado generalizado los elementos que nos interesen para desarrollar en el Capı́tulo 4 una aplicación a la segmentación de imágenes en color. En la Sección 2.1 veremos qué variantes de mapas auto-organizados de la Secciones 1.3 y 1.4 encajan dentro de este nuevo concepto. Quizás la propiedad más interesante del concepto que presentamos es que es simétrico: los datos de entrada en el espacio de entrada por un lado y las neuronas por otro lado juegan ahora papeles intercambiables. Esta simetrı́a puede, en potencia, dar lugar a nuevos desarrollos. Comencemos con la variantes 1.3.1 y 1.3.3, las cuales reproducimos aquı́ para la conveniencia del lector: Variante. Sustituir la topologı́a y distancia entre neuronas por la topologı́a y distancias en una espacio métrico al que pertenecen y en el que se mueven las neuronas. Variante. Sustituir la distancia euclı́dea entre la entrada y las neuronas por la distancia geodésica correspondiente. 23 CAPÍTULO 2. NUEVO ENFOQUE TEÓRICO. Por la primera variante impondremos que las neuronas vivan en un espacio métrico por el que se pueden desplazar. De la tercera variante queremos que el espacio de entrada sea también un espacio métrico (métrica es la distancia geodésica). Ası́ que tenemos dos espacios, uno en el que viven las neuronas y otro, el espacio de entrada, en el que tenemos los datos de entrada. Queremos que estos dos espacios tengan una noción de distancia, es decir, que sean espacios métricos. Ası́ que denotemos por N y por X a sendos espacios métricos. El primero de ellos contendrá a las neuronas y el segundo de ellos a los datos de entrada. Por tanto, cada neurona tiene un posición dinámica en N y cada dato de entrada tiene una posición dinámica en X . En un mapa autoorganizado clásico estas posiciones son estáticas, es decir, que no varı́an con el tiempo. En el caso clásico, el vector de pesos de cada neurona es una posición en el espacio de entrada X . Ası́, que cada neurona tiene en realidad asociadas dos posiciones, una en N y otra en X . Por otro lado, la función best matching unit, BMU, introducida en la Sección 1.1, asocia a cada dato de entrada una posición en N . Nótese que el codiminio de la función BM U definida en esa sección es la malla de la red o el conjunto de las neuronas, no el espacio donde viven las neuronas como aquı́. En cualquier caso, cada dato de entrada también tiene asociadas dos posiciones, una en X y otra en N . Definición 2.0.1. Un mapa auto-organizado generalizado consta de dos espacios métricos X y N en cada uno de los cuales se dan dos poblaciones iniciales de M puntos y de N puntos. En cada iteración t = 0, 1, 2, 3, . . . un algoritmo de aprendizaje genera las nuevas posiciones de los 2·(M +N ) puntos a partir de las posiciones actuales. La función de coste para evaluar el aprendizaje depende de las posiciones de los puntos. En el caso clásico, las M posiciones en X son los datos de entrada y son estáticas. Las M posiciones en N son la evaluación de la función BM U sobre los datos de entrada y son dinámicas. Las N posiciones en N corresponden a las posiciones de las neuronas en la malla y son estáticas. Las N posiciones en 24 CAPÍTULO 2. NUEVO ENFOQUE TEÓRICO. X corresponden a los vectores de peso de las neuronas y son dinámicas. En un mapa auto-organizado generalizado todas las posiciones son dinámicas. Figura 2.1: Un mapa auto-organizado generalizado. No se ha especificado ninguna propiedad del algoritmo de aprendizaje ası́ que este es totalmente genérico. Esto da lugar a que la definición sea quizás un poco vaga, pero hemos preferido centrarnos en los dos espacios y su simetrı́a. Recordemos ahora las variantes 1.3.2 y 1.3.4: Variante. Sustituir la métrica euclı́dea en el espacio de entrada por una métrica Riemanniana construida a partir de una una densidad continua que se ajusta a los datos de entrada. Variante. Sustituir el desplazamiento a lo largo del segmento entre la neurona y la entrada por el desplazamiento a lo largo de la la geodésica correspondiente. En nuestra definición de mapa auto-organizado generalizado no hemos exigido que las distancias de X y N vengan inducidas por una métrica Riemanniana. Esto darı́a lugar a: Definición 2.0.2. Una mapa auto-organizado Riemanniano es un mapa auto-organizado generalizado en el que las métricas de X y/o N vienen inducidas por una métrica Riemanniana. La segunda variante expuesta arriba impone que las neuronas se desplacen por geodésicas: 25 CAPÍTULO 2. NUEVO ENFOQUE TEÓRICO. Definición 2.0.3. Una mapa auto-organizado geodésico es un mapa autoorganizado generalizado en el que los espacios X y/o N son espacios geodésicos, es decir, espacios dotados de una geodésica entre cada par de puntos, y el algoritmo de aprendizaje actualiza las nuevas posiciones mediante desplazamientos a lo largo de geodésicas. 2.1. Recuperando las variantes. Recordemos que todas las variantes de la sección 1.3 se centraban en modificar la topologı́a, distancia entre neuronas o distancia entrada-neuronas de la red. Todas ellas salvo [13] y [15] encajan como mapas auto-organizados generalizados, y algunas de ellas dan lugar a mapas auto-organizados Riemannianos. Nótese que, como también comentamos al final de esa sección, ninguna de ellas da lugar a un mapa auto-organizado geodésico. Revisemos ahora las variantes de la Sección 1.4 algunas de las cuales, como ya dijimos, están sólo relacionadas con mapas auto-organizados. La Variante 1.4.1 Variante. Permitir la creación y destrucción de neuronas y aristas en la malla para adaptarse mejor a los datos de entrada, no se contempla en el mapa auto-organizado generalizado, ya que las poblaciones de neuronas y datos de entrada son estáticas (no ası́ sus posiciones). Ası́ que los trabajos [1] y [6] no se pueden enmarcar dentro del nuevo contexto teórico. Por otro lado, los trabajos [5] y [21] dieron lugar a la Variante 1.4.2 Variante. Modificar la estrategia de competitividad para dar iguales oportunidades a todas las neuronas. Como no se han impuesto restricciones en el algoritmo de aprendizaje de un mapa auto-organizado generalizado esta variante sı́ es abarcada. Pasamos ahora a los dos trabajos más interesante desde el punto de vista de comparación con un mapa auto-organizado generalizado. Empecemos por 26 CAPÍTULO 2. NUEVO ENFOQUE TEÓRICO. el mapa en perspectiva relacional [12], con el cual se consigue representar datos de dimensión arbitraria en un toro bidimensional. Este trabajo se puede ver como un mapa auto-organizado generalizado en el cual X es el espacio euclı́deo y N es el toro bidimensional. Además, M = N y podemos identificar las dos poblaciones en X como una sola y las dos poblaciones en N como una sola. Las M posiciones en X corresponden a los datos de entrada y son estáticas. Las M posiciones en N son dinámicas y corresponden a las iteraciones del algoritmo para resolver las ecuaciones diferenciales involucradas (hay una partı́cula por cada dato de entrada). La función de coste que se quiere minimizar [12, Ecuación (1)] es función de las M posiciones en N . La aplicación topográfica generativa [3] también se enmarca dentro del presente contexto teórico. En este caso tanto X como N corresponden a espacios euclı́deos de las dimensiones adecuadas. La población de N puntos en X corresponde a la función y(x;W) definida en [3, Ecuación (7)] y evaluada en las N posiciones de la malla en N . El algoritmo de aprendizaje serı́an las iteraciones del algoritmo EM [3, Sección 2.1]. La función de coste a maximizar se describe en [3, Ecuaciones (1) y (6)], y depende de las N posiciones en X . Las M posiciones en N sólo se construyen después del aprendizaje usando el teorema de Bayes [3, Sección 2.1]. Nuestro parámetros M y N corresponden a N y K respectivamente en [3]. El trabajo [17], en el cual se asocia una número llamado afinidad a cada par de puntos del espacio de entrada, no se enmarca dentro de los mapas autoorganizados generalizados, ya que no existe un proceso de aprendizaje. Los mapas auto-organizados descritos en [22] y [7] encajan sin más novedad como mapas auto-organizados generalizados debido, otra vez, a que no imponemos condiciones a nuestro algoritmo de aprendizaje. 27 Capı́tulo 3 Un mapa auto-organizado generalizado. En este capı́tulo describimos un mapa auto-organizado generalizado particular. Conforme a las definiciones del Capı́tulo 2 estarı́amos considerando una mapa auto-organizado Riemanniano y geodésico, pero como escribimos aquı́ todos los detalles no es necesario entender la notación dada allı́, ası́ que emplearemos sólo la notación clásica para mapas auto-organizados del Capı́tulo 1. En el Capı́tulo 4 se implementará una versión de este algoritmo aplicada a la segmentación de imágenes en color. La malla de nuestro mapa auto-organizado es una malla unidimensional con N neuronas. El espacio de entrada es un espacio euclı́deo. A este espacio lo dotaremos de una métrica Riemanniana obtenida a partir de una densidad continua que modela la nube de datos de entrada. A partir de esta métrica Riemanniana dotaremos a este espacio euclı́deo de entrada de una noción de geodésica y de una noción de distancia geodésica, obteniendo una métrica distinta a la de la euclı́dea (ver Apéndice A). Supongamos que el espacio de entrada es el espacio euclı́deo Rm y que la matriz de la métrica Riemanniana en x ∈ Rm es G(x). Dados p y q puntos del espacio euclı́deo de entrada, la distancia geodésica entre ellos vendrá dada 28 CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO. entonces por: Z dgeodésica (p, q) = Ínfimo 1 0 p γ ′ (t)G(γ(t))γ ′ (s)tr dt, (3.1) donde γ : [0, 1] → Rm es una curva continua y diferenciable a trozos que empieza en p y termina en q, el ı́nfimo se toma sobre todas tales curvas y tr significa traspuesta. Las neuronas competirán por ser la neurona ganadora o BMU usando para ello su distancia geodésica a la entrada. Las ecuaciones de aprendizaje son similares a las clásicas de Kohonen (Sección 1.2), pero los vectores de pesos de las neuronas se moverán hacia la entrada siguiendo las geodésicas del espacio. Es esto último lo que distingue a este mapa auto-organizado de los desarrollados hasta ahora (ver la Variante 1.3.4 en la Sección 1.4). Un elemento clave para entender la métrica Riemanniana que usamos es que, siguiendo la Variante 1.4.3, la geodésica entre dos puntos del espacio de entrada intentará evitar las zonas de baja densidad. Esto lo conseguiremos definiendo la matriz de la métrica Riemanniana en el punto x ∈ Rn del espacio de entrada Rm como G(x) = 1 In , d2 (x) donde d(x) es la densidad en el punto x e In es la matriz identidad n × n. Ası́ que el espacio que obtenemos es isótropo, es decir que la longitud de un vector no depende de su dirección. Más precisamente, la longitud del vector v en el espacio tangente de x viene dada por 1 ||v||, d(x) donde ||v|| es la norma euclı́dea de v. En las siguientes secciones se explican en detalle cada uno de los elementos constituyentes del mapa auto-organizado. 29 CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO. 3.1. Construcción de la densidad continua. Dado un conjunto de muestras o datos de entrada {xi }i=1,...,N umM uestras en el espacio euclı́deo de entrada Rm , se dará una densidad continua que se ajusta lo más posible a estos datos. No hay que confundir estos datos con los M datos de entrada que se presentarán a la red durante el aprendizaje. Para construir esta densidad hemos usado el algoritmo descrito en el artı́culo [14] de los autores Ezequiel López Rubio y Juan Miguel Ortiz de Lazcano Lobato. En esta sección explicamos a grandes rasgos cómo funciona dicho algoritmo, para una descripción detallada se remite al lector al citado trabajo. Dicho algoritmo es un método de estimación de la función de densidad de probabilidad de una distribución desconocida continua a partir de una cantidad finita de muestras de dicha distribución. La presente solución genera como estimación una suma de distribuciones normales o Gaussianas multidimensionales. Las medias y demás parámetros de las distribuciones se estiman a partir de las muestras en dos fases: Primero, para cada una de las N umM uestras muestras se crea un entorno que incluye a las muestras vecinas (más cercanas en distancia euclı́dea). Se calcula la media y matriz de correlaciones de estos entornos. Segundo, un proceso de suavizado. Se crean N umClusters clusters, cada uno de los cuales tienen contribuciones o pesos de cada uno de los entornos. Cada cluster recibirá contribuciones de los entornos circundantes de manera inversamente proporcional a la distancia a estos, con lo que la información de todos ellos queda fusionada y suavizada a la vez. Cada cluster creado tendrá una media y una matriz de correlaciones asociada obtenida a partir de las medias y matrices de los entornos involucrados con los pesos adecuados. A partir de estos datos se construye entonces una distribución Gaussiana para cada cluster. En dicha construcción es de destacar que: 30 CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO. La dimensionalidad o número de direcciones principales de dicha distribución Gaussiana se ajusta a la información del cluster, reflejando la dimensión de la variedad subyacente a los datos. Esto se consigue reteniendo sólo parte de los autovalores y autovectores de la matriz de covarianza del cluster. La cantidad de autovalores a preservar se controla mediante un parámetro α ∈ [0, 1] que especifica que proporción de la traza de dicha matriz deben sumar los autovalores retenidos. Para las direcciones no conservadas se hace una estimación de la varianza en estas direcciones especificando un nivel de ruido. Este nivel se controla con un parámetro γ ∈ [0, 1]. En general cuanto mayor sea α menor deberá ser γ y viceversa. Si α es próximo a 1 conservaremos casi todas las direcciones principales y en el resto habrá que añadir poco ruido. Si α es próximo a 0 conservaremos muy pocas direcciones y habrá que añadir más ruido en el resto de direcciones. El presente procedimiento tiene las siguientes ventajas respecto a otros métodos de estimación de función de densidad de probabilidad anteriores: Cada distribución normal tiene sus propios parámetros. Existe un proceso de suavizado al pasar de los entornos a los clusters. Para una comparativa detallada de este método con otros métodos de estimación de la función de densidad de probabilidad ver [14, Sección 5]. A la densidad calculada por este método la denotaremos por d(x) : Rm → R, donde Rm es el espacio euclı́deo de entrada. Ejemplo 3.1.1. En la siguiente figura mostramos una densidad continua que queremos aproximar usando el método de estimación de la densidad explicado. Esta es la distribución desconocida. 31 CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO. En la siguiente figura mostramos 100 muestras tomadas aleatoriamente de la densidad anterior (cı́rculos azules), junto con los clusters (cruces verdes) y la función de densidad computados por el algoritmo. Los parámetros son α = 0,1 y γ = 0,07. 0.9 muestra cluster 100 10 0.8 90 20 80 0.7 30 0.6 70 40 0.5 60 50 0.4 50 60 40 70 30 80 20 90 10 0.3 0.2 0.1 0.1 3.2. 100 0.2 0.3 0.4 0.5 0.6 0.7 0.8 10 20 30 40 50 60 70 80 90 100 Construcción del grafo de distancias. Con el objetivo de dotar al espacio euclı́deo de entrada Rm de geodésicas necesitaremos introducir un grafo con pesos sobre el cual se computará el camino más corto o geodésica usando el algoritmo de Floyd (ver Sección 1.3 y Figura 1.11). Como vértices de este grafo tomaremos los clusters calculados por el algoritmo descrito en la Sección 3.1. El peso de la arista entre los clusters en posiciones p y q será la longitud en la métrica Riemanniana del segmento rectilı́neo entre p y q. Recordemos que la métrica Riemanniana que estamos considerando es exactamente G(x) = d21(x) In , para x ∈ Rm , y donde d(x) es la densidad 32 CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO. continua calculada en la Sección 3.1. Sean p y q las posiciones de dos clusters y γ : [0, 1] → R la parametrización del segmento rectilı́neo de p a q: γ(t) = p + t(q − p). La longitud de este segmento en nuestra métrica viene dada por Z 1 0 p γ ′ (t)G(γ(t))γ ′ (t)tr dt. (3.2) Como γ ′ (t) = q − p al sustituir tenemos Z 1 0 s d2 (p 1 (q − p)In (q − p)tr dt, + t(q − p)) y reordenando y reparametrizando obtenemos ||q − p|| Z 1 0 dt = d(p + t(q − p)) Z 0 ||q−p|| dt q−p , d(p + t ||q−p|| ) donde ||q − p|| es la norma euclı́dea de q − p. Esta integral la aproximamos con el siguiente trapezoide ||q − p|| N umSubdivisiones N umSubdivisiones X i=1 1 d(p + i (q N umSubdivisiones − p)) , (3.3) donde N umSubdivisiones es el número de segmentos en que dividimos el segmento q − p, y que controla la precisión de la integración. Una vez que sabemos como calcular el peso de una arista y que sabemos que el conjunto de vértices del grafo está formado exactamente por los clusters calculados en la Sección 3.1 hay que decidir qué aristas incluir y qué aristas no. Con este fin, para cada cluster c, se incluyen las aristas de c a los clusters más cercanos. Este número de clusters que se conectan al cluster c es un número fijo que denotamos N umV ecinosGraf o. La noción de cercanı́a aquı́ no es distancia euclı́dea. En su lugar, ya que el cluster c tiene una distribución Gaussiana asociada, se evalúa esta distribución en el resto 33 CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO. de los clusters y se seleccionan los N umV ecinosGraf o clusters que obtengan mayor valor. Este concepto de cercanı́a intenta aproximar a escala local la distancia geodésica que se quiere obtener a escala global, esto es, distancia inversamente proporcional a la densidad. Estas nociones quedan ilustradas en la siguiente figura, en la cual se muestra un cluster (en rojo) con su distribución normal asociada y los dos clusters más cercanos (N umV ecinosGraf o = 2, en verde) según esta distribución normal, los cuales no coinciden con los dos clusters más cercanos en distancia euclı́dea. El número N umV ecinosGraf o es crı́tico. Como muestra el siguiente ejemplo un número bajo puede resultar insuficiente para mantener la conexión de la densidad original y un número muy alto puede dar lugar a aristas “erróneas”. 34 CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO. Ejemplo 3.2.1. En la siguiente figura mostramos una densidad a aproximar ası́ como la reconstrucción a partir de 100 muestras mediante el método explicado en la Sección 3.1: 10 70 20 60 30 50 40 40 50 60 30 70 20 80 10 90 100 10 20 30 40 50 60 70 80 90 100 Las siguientes figuras muestran las muestras (cı́rculos azules), los clusters (cruces verdes) y las aristas del grafo (en negro) para valores de N umV ecinosGraf o iguales a 1, 5, 10 y 15 (de izquierda a derecha y de arriba abajo): 1 1 0.9 0.9 0.8 0.8 0.7 0.7 0.6 0.6 0.5 0.5 0.4 0.4 0.3 0.3 0.2 0.2 0.1 0 0.1 0 0.2 0.4 0.6 0.8 0 1 1 1 0.9 0.9 0.8 0.8 0.7 0.7 0.6 0.6 0.5 0.5 0.4 0.4 0.3 0.3 0.2 0.2 0.1 0 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 0.1 0 0.2 0.4 0.6 0.8 0 1 35 CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO. Se observan aristas “erróneas” que se salen de la nube de densidad en la última figura abajo a la derecha. Para evitar estos problemas en el caso general se ensayaron los siguientes métodos en la elección de los N umV ecinosGraf o vecinos a un cluster dado: Elegir los 2·N umV ecinosGraf o clusters que maximizan sus Gaussianas en el cluster dado, y después elegir de estos los N umV ecinosGraf o clusters que minimizan la integral del inverso de la densidad d(x) a lo largo del segmento entre cada cluster y el cluster dado c. Elegir los 2·N umV ecinosGraf o clusters que maximizan sus Gaussianas en el cluster dado, y después elegir de estos los N umV ecinosGraf o clusters que minimizan la integral del inverso de la densidad d(x) a lo largo del segmento entre cada cluster y el cluster dado c dividido por la longitud de dicho segmento (valor medio del inverso de la densidad). Elegir los 2·N umV ecinosGraf o clusters que maximizan sus Gaussianas en el cluster dado, y después elegir de estos los N umV ecinosGraf o clusters que maximizan el mı́nimo de la densidad d(x) a lo largo del segmento entre cada cluster y el cluster dado (maxmin, para evitar atravesar cuellos de botella). Sin embargo, se comprobó que estos métodos no proporcionan ventaja alguna en todos los casos y que la clave es seleccionar el valor N umV ecinosGraf o correctamente según la aplicación. Nótese que los cálculos se hacen con 2 · N umV ecinosGraf o clusters y no todos lo clusters por razones de tiempo de cómputo. 3.3. Construcción de las geodésicas y la distancia geodésica. Una vez que hemos construido el grafo de la Sección 3.2 estamos preparados para la construcción de las geodésicas y las distancias geodésicas. Dados dos puntos p y q del espacio de entrada Rm empezaremos determinando la 36 CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO. geodésica de p a q. La distancia geodésica entre p y q será la longitud de dicha geodésica. Si ambos puntos p y q fueran vértices del grafo entonces la geodésica serı́a directamente el camino más corto en el grafo determinado, por ejemplo, por el algoritmo de Floyd. En general ni p ni q serán vértices del grafo y un primer escollo es determinar el vértice de entrada al grafo y el vértice de salida del grafo. Es decir, la geodésica de p a q consistirá de un segmento rectilı́neo desde p a un vértice del grafo, de un camino minimizante en el grafo y de un segmento rectilı́neo desde un vértice del grafo a q. Para calcular los vértices de entrada y salida replicaremos lo hecho en la Sección 3.2 para calcular los vecinos de un cluster dado del grafo. Es decir, vamos a seleccionar un número determinado de clusters o vértices del grafo vecinos al punto p y el mismo número de clusters vecinos al punto q. Este número fijo lo denotaremos por N umV ecinos. Para el punto p elegimos los N umV ecinos clusters que maximizan el valor de sus distribuciones Gaussianas en p, y análogamente para q (nótese que ahora p y q no tienen distribuciones asociadas). Una vez tenemos los vértices más cercanos a p y a q calculamos, para cada vértice vecino a p, cp , y para cada vértice vecino a q, cq , la longitud del camino que empieza en p, continua por un segmento rectilı́neo hasta cp , sigue el camino minimizante en el grafo de cp a cq y termina con el segmento rectilı́neo de cq a q. La longitud de los segmentos de p a cp y de cq a q viene dada por la Ecuación (3.3). La longitud de cada arista del grafo que se atraviesa se calcula de la misma forma y de hecho ya se almacenó como el peso de dicha arista. La longitud total del camino es la suma de todas estas longitudes. La geodésica de p a q se obtiene eligiendo entre los vecinos de p y los vecinos de q los vértices cp y cq tales que la distancia del camino p → cp → camino minimizante → cq → q es mı́nima entre todos estos caminos. Podemos representar estos elementos gráficamente como sigue: 37 CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO. En la figura se muestra el grafo con los vértices como clusters, ası́ como las aristas. Cada vértices tiene 4 vecinos, es decir, N umV ecinosGraf o = 4. Se muestran los vecinos más cercanos a p y q encerrados en cı́rculos verdes, ası́ como los segmentos rectilı́neos de p y q a estos vecinos. Se ha elegido N umV ecinos = 3. Por último, se muestra en trazo grueso la geodésica de p a q. Ejemplo 3.3.1. La siguiente figura muestra una densidad a aproximar y su aproximación mediante 100 muestras: 10 60 20 50 30 40 40 50 30 60 70 20 80 10 90 100 20 40 60 80 100 En la siguiente figura se muestran los clusters que se usaron para reconstruir la densidad (cruces verdes), ası́ como una geodésica (trazo negro) y los vecinos a los puntos de inicio y fin de la geodésica (puntos negros). Los ve38 CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO. cinos seleccionados como entrada y salida al grafo de clusters están rodeados de un cı́rculo negro, y N umV ecinos = 5. 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Una versión anterior del algoritmo elegı́a únicamente el vértice más cercano a p y el vértice más cercano a q (según proximidad Gaussiana) y definı́a la geodésica pasando a través del camino minimizante en el grafo a través de estos vértices. El método explicado arriba da resultados notablemente mejores. De nuevo, al igual que en la construcción del grafo, al determinar los vértices de entrada y salida al grafo estamos aproximando a escala local la distancia geodésica global y mientras que el método descrito arriba tiene una componente global el descrito al principio de este párrafo no la tiene. Otra versión del algoritmo para geodésicas que implementé usaba como vértices del grafo una retı́cula ortogonal en vez de los clusters dados por el algoritmo que reconstruye la densidad de la Sección 3.2, y conectaba cada vértice a sus vértices inmediatamente adyacentes. Por ejemplo, en 2 dimensiones los vecinos estarı́an dispuestos ası́: 39 CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO. Ejemplo 3.3.2. La siguiente figura muestra una densidad a aproximar, su aproximación mediante 100 muestras y la retı́cula o vértices del grafo superpuestos (cruces verdes). Además se muestra una geodésica en trazo negro. 10 20 30 40 50 60 70 80 90 100 10 20 30 40 50 60 70 80 90 100 Esta versión no se ha seguido desarrollando por el alto coste computacional en dimensiones superiores. En m dimensiones y con tamaño de un lado del retı́culo L tenemos un total de Lm vértices. El algoritmo de Floyd tiene una complejidad O(|V |3 ), donde |V | es el número de vértices del grafo. En nuestro caso esto darı́a una complejidad O(L3m ), con lo que para L fijo la complejidad es exponencial en m. En contraste, el algoritmo de la Sección 3.2 genera como mucho un número de clusters N umClusters, y por tanto de vértices, igual al número de muestras de entrada N umM uestras. Ası́ que la complejidad es O(|N umM uestras|3 ) donde N umM uestras es el número de muestras. Esto es mucho más manejable que O(L3m ) en las aplicaciones. 40 CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO. Ejemplo 3.3.3. En una aplicación de segmentación a imágenes en color los datos tienen 3 coordenadas, es decir, m = 3. Suponiendo que tomamos 100 muestras y que usamos un retı́culo tridimensional de lado 20 tenemos: O(L3m ) = O(512000000000) y O(|N umM uestras|3 ) = O(1000000). La diferencia es patente incluso a esta pequeña escala. Para terminar esta sección hacemos una pequeña digresión sobre las componentes conexas del grafo y las geodésicas. Supongamos que tenemos un grafo de distancias que tiene dos componentes conexas C1 y C2 (en términos de adyacencia). Si una neurona se encuentra suficientemente cerca de C1 y suficientemente lejos de C2 los N umV ecinos clusters que se usen para calcular su geodésica hasta la entrada estarán todos en la componente C1 . Ası́ mismo, si la entrada está suficientemente cerca de C2 , los N umV ecinos clusters de la entrada pertenecerán a la componente C2 . Resulta entonces que el algoritmo de Floyd dará distancia infinita para estas N umV ecinos × N umV ecinos combinaciones de clusters, ya que están en componentes distintas del grafo de distancias. Una forma de remediarlo es, en general, comparar las N umV ecinos × N umV ecinos distancias geodésicas que se obtienen con la integral a lo largo del segmento rectilı́neo entre la neurona y la entrada del inverso de la densidad (Ecuación (3.3)). Ası́, en el caso que tratamos de las dos componentes, aunque la distancia geodésica es infinita si intentamos progresar por el grafo, si en cambio usamos el segmento rectilı́neo obtendremos una distancia finita (posiblemente muy grande si atravesamos zonas de muy baja densidad). Si no añadimos la solución con el segmento rectilı́neo permitiremos que las neuronas sean “capturadas” por la componente del grafo más próxima, lo cual puede ser interesante según la aplicación que se esté desarrollando. 41 CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO. 3.4. Funcionamiento del mapa auto-organizado. El funcionamiento algorı́tmico de este mapa auto-organizado se divide en las siguientes etapas: (a) Construcción de la densidad continua a partir de los N umM uestras datos de entrada en el espacio de entrada Rm (Sección 3.1). (b) Construcción del grafo de distancias con N umClusters clusters (Sección 3.2). (c) Cálculo de la matriz de distancias mı́nimas entre clusters según el algoritmo de Floyd (Sección 3.3). (d) Inicialización de los parámetros de la red σ0 , λ y η0 . (e) Inicialización de los vectores de pesos de las N neuronas. (f) Realizar iteraciones de aprendizaje presentando a la red o bien los clusters de (b) o bien las muestras de (a) o bien nuevas muestras. Para inicializar los vectores de pesos de las neuronas (e) se asigna a cada una de ellas la posición de un cluster elegido aleatoriamente. Cada iteración t en (f) se subdivide en las siguientes subetapas: (f.1) Cálculo de la geodésica y la distancia geodésica entre la entrada x(t) y el vector de pesos de cada neurona ni (t). (f.2) Selección de la neurona ganadora o BMU como la que minimiza su distancia geodésica hasta la entrada. (f.3) Cálculo de los coeficientes de aprendizaje γ(t, x(t), i) según lo explicado en la Sección 1.2 o alguna variante de estas ecuaciones. Recordemos que estamos usando una malla unidimensional. (f.4) Desplazamiento de cada neurona i a lo largo de la geodésica hasta la entrada en una cantidad que es el γ(t, x(t), i) por ciento de su distancia geodésica hasta la entrada. 42 Capı́tulo 4 Aplicación a la segmentación de imágenes. En este capı́tulo explicamos los detalles de implementación de un mapa auto-organizado generalizado (Capı́tulo 3) aplicado a la segmentación de imágenes en color. La segmentación de imágenes en color trata de seleccionar los colores más caracterı́sticos de una imagen plana digital en color. En general esto se realiza como uno de los pasos iniciales de un proceso de análisis de imagen por ordenador. En esta sección usaremos neurona y prototipo indistintamente. De forma condensada, un número de muestras M se toma de la imagen y se sitúan en algún espacio de color (RGB por ejemplo). Las N neuronas o prototipos se mueven por esta nube de datos de entrada durante el proceso de aprendizaje de la red. Finalmente, la imagen original se reconstruye sustituyendo cada color de la imagen por su prototipo más cercano. Tanto la percepción visual de la imagen reconstruida como el error cuadrático medio dan una idea de la bonanza de los prototipos seleccionados por la red. Como espacio de entrada no usaremos el espacio de color RGB si no el espacio de color CIELU V . Este espacio es también tridimensional (m = 3) y tiene ventajas en cuanto a la percepción de los colores. Ası́ que dada las muestras RGB tomadas de la imagen estos valores se convierten a valores CIELU V y todo el aprendizaje tiene lugar en este espacio de color CIELU V . 43 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. Sólo al final, durante la reconstrucción de la imagen original, se vuelve al espacio RGB. Con más detalle, el funcionamiento de la red es como sigue: (A) Se carga una imagen en color en algún formato estándar como .bmp, .gif, etc. (B) Se toman N umM uestras puntos aleatorios de la imagen y se almacenan sus valores RGB. (C) Estos valores se convierten a valores CIELU V dando lugar a los N umM uestras datos de entrada en el espacio CIELU V que se usan para construir la densidad continua. (D) Se aplica el algoritmo del mapa auto-organizado generalizado tal y como está descrito en la Sección 3.4 en el espacio de color CIELU V . Si se requieren más muestras para presentar a la red estas se irán generando aleatoriamente en cada iteración. (E) Los N prototipos obtenidos se usan para reconstruir la imagen y calcular el error cuadrático medio. 44 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. Ejemplo 4.0.1. En este ejemplo mostramos la ejecución sobre una imagen de tamaño 128 × 128. Se usan 100 muestras (N umM uestras = 100) y 16 neuronas o prototipos (N = 16). También ponemos N umV ecinosGraf o = 5, N umV ecinos = 5 y η0 = 1. Los parámetros del algoritmo de reconstrucción de la densidad (Sección (3.1)) son α = 0,1 y γ = 0,07. 20 40 60 80 100 120 20 40 60 80 100 120 Figura 4.1: Imagen original 128 × 128 y 100 muestras en el espacio CIELU V decoradas con el color RGB original. 20 60 40 40 20 60 0 80 −20 −40 60 100 40 100 80 20 120 60 0 40 −20 20 20 40 60 80 100 120 Figura 4.2: A la izquierda, grafo de clusters (clusters en verdes, aristas en negro) y distribución final de las 16 neuronas (en rojo) en el espacio CIELU V . A la derecha, reconstrucción de la imagen original usando los prototipos. Como error cuadrático medio se obtuvo M SE = 0,045208. En la siguiente sección comentamos las distintas funciones diseñadas en MATLAB y C y que parte del algoritmo implementan. En la Sección 4.2 se 45 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. realiza un estudio sobre la dependencia del aprendizaje de los parámetros de la red. En la Sección 4.3 se ha probado el nuevo mapa auto-organizado generalizado en imágenes de bancos estándares y se han comparado los resultados con los obtenidos en otros trabajos de ı́ndole similar. 46 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. 4.1. Implementación MATLAB. El mapa auto-organizado se ha implementado en MATLAB usando para ellos scripts MATLAB y también código en C (funciones MEX) para optimizar en velocidad. Las funciones MATLAB construidas son las siguientes. También especificamos que acciones de las listadas en la Sección 3.4 o en la introducción a este capı́tulo se implementa en el código de cada función. Nombre función Descripción Implementa AnalizaImagen Script principal (A) (B) (C) (e) AprendeRed Ejecuta el algoritmo de aprendi- (f) zaje DesplazaNeurona Desplaza una neurona a lo largo (f.4) de una geodésica en una proporción dada Geodesica Calcula la geodésica entre dos (f.1) puntos IniciaRed Inicializa los parámetros de la red (d) IntegraInversoDensidad Aproximación a la integral de lı́nea sobre un segmento del inverso de la densidad (Ecuación (3.3)) MatrizDistanciasLineales Crea el grafo de distancias dados (b) los clusters MueveNeuronas Mueve las neuronas según las re- (f.2) (f.3) glas de aprendizaje Reconstruye Calcula el error cuadrático medio (E) para la imagen y las neuronas dadas y reconstruye la imagen usando dichas neuronas RecorreCamino Recupera el camino mı́nimo entre (f.1) dos vértices 47 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. Además, se usan las siguientes funciones MATLAB. Las 3 primeras me fueron proporcionadas por el profesor Ezequiel López Rubio y constituyen la implementación del trabajo [14]. La función colorspace fue creada por Pascal Getreuer (ColorSpace, Copyright (c) 2009, Pascal Getreuer). La última función forma parte de la librerı́a de grafos para MATLAB creada por David Gleich (MatlabBGL, Copyright (c) 2006-2007, David Gleich). Nombre función Descripción Implementa TrainSmoothParzenWindows Construye la densidad continua a (a) partir de las muestras TestSmoothParzen Evalúa la densidad continua en un punto GaussianaLocalSmoothParzen Evalúa la distribución Gaussiana de un cluster en un punto colorspace Conversión RGB ↔ CIELU V allshortestpaths Algoritmo de Floyd, computa la (c) matriz de distancias mı́nimas para el grafo de distancias (C) La siguiente tabla muestra las dependencias entre las funciones MATLAB y qué funciones tienen una versión MEX. El criterio para elegir qué funciones convertir a funciones MEX fue el profiler de MATLAB: se convirtieron a MEX las funciones en las que se empleaba la mayorı́a del tiempo de ejecución. 48 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. Nombre función MEX AnalizaImagen NO Hijos Padres IniciaRed AprendeRed Reconstruye colorspace TrainSmoothParzenWindows allshortestpaths NO AprendeRed NO colorspace NO IniciaRed MueveNeuronas AnalizaImagen AnalizaImagen Reconstruye DesplazaNeurona NO GaussianaLocal- SI MueveNeuronas MatrizDistancias- SmoothParzen Geodesica Lineales Geodesica SI GaussianaLocalSmoothParzen IntegraInversoDensidad RecorreCamino IniciaRed NO MatrizDistanciasLineales AnalizaImagen allshortest- paths IntegraInversoDensidad SI TestSmoothParzen MatrizDistanciasLineales, Geodesica MatrizDistancias- NO Lineales GaussianaLocal- IniciaRed SmoothParzen IntegraInversoDensidad MueveNeuronas NO Geodesica Desplaza- AprendeRed Neurona Reconstruye NO RecorreCamino SI TestSmoothParzen SI TrainSmoothParzen- Geodesica colorspace AnalizaImagen RecorreCamino RecorreCamino IntegraInversoDensidad NO AnalizaImagen Windows Prácticamente el 100 % del tiempo de ejecución de lo reparten entres las 5 funciones con versiones MEX de la tabla anterior. La función de cálculo 49 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. de geodésicas, Geodesica, está optimizada de forma que se almacenan los N umV ecinos clusters de cada neurona de una iteración a otra. Ası́, si la neurona no se desplaza no se recalculan sus clusters vecinos en la siguiente iteración. Como el proceso de aprendizaje de la red tiende a mover las neuronas menos cuanto más iteraciones se realizan esto resulta en una aceleración del aprendizaje en su parte final. En la versión final los N umV ecinos elegidos para construir geodésicas se seleccionan como aquellos que minimizan la distancia euclı́dea y no como aquellos que minimizan la distancia Gaussiana (ver Sección 3.3). Ası́ se consigue mayor velocidad y más estabilidad en los resultados. El segmento rectilı́neo entre una muestra y la entrada se elige como geodésica si las geodésicas a través del grafo dan todas distancia infinita (ver tres últimos párrafos de la citada sección). 4.2. Dependencia de los parámetros. Durante el Capı́tulo 3 se estableció que el algoritmo de aprendizaje del mapa auto-organizado generalizado que estamos usando depende de los siguientes parámetros: 1. Parámetros α y γ, que determinan respectivamente la proporción de autovalores a conservar y el nivel de ruido en la construcción de la densidad continua. 2. Parámetro N umM uestras y N umClusters usados en la construcción de la densidad continua. 3. Parámetro N umV ecinosGraf o, que determinan el número de clusters vecinos a un cluster dado en la construcción del grafo de distancias, y parámetro N umV ecinos, que determina el número de clusters vecinos a la entrada o a una neurona en la construcción de geodésicas y distancias geodésicas. 4. Parámetros σ0 , η0 , que determinan respectivamente el entorno inicial y la razón de aprendizaje inicial en las ecuaciones de aprendizaje. 50 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. En esta sección describimos un estudio realizado para estudiar la calidad del aprendizaje del mapa auto-organizado generalizado en función de los distintos parámetros. Las pruebas se han realizado sobre la imagen del mandril del Ejemplo 4.0.1 en tamaño 128 × 128 con N umM uestras = 100 muestras, N umClusters = 100 clusters y N umN euronas = 10 neuronas (salvo cuando son estos parámetros los que se están estudiando claro está). Empezamos por α y γ. Fijando una muestra con N umM uestras = 100 pı́xeles aleatorios de la imagen hemos construido la densidad continua d(x) : Rm → R con N umClusters = 100 clusters para distintos valores de α y γ y evaluado la siguiente cantidad: M X −1 AN LL = ln d(xi ), N umM uestras i=1 (4.1) donde {xi }i=1,...,N umM uestras son las muestras y ln es logaritmo neperiano. Las siglas vienen del inglés average negative log likelihood. Esta cantidad AN LL cuantifica cómo de bien aproxima la densidad continua a las muestras, y la optimización trata de minimizar su valor. La siguiente gráfica muestra el valor de ANLL para α y γ tomando valores entre 0 y 1. 12 11.5 11 10.5 10 9.5 9 100 80 60 40 20 0 Alpha*100 0 10 20 30 40 50 Gamma*100 51 60 70 80 90 100 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. Hemos encontrado que los valores óptimos para α y γ son 0,1 y 0,14 respectivamente. Debido al paso intermedio de la construcción de la densidad continua hay otros parámetros que estudiar en nuestro algoritmo. En particular, el algoritmo depende del número de muestras N umM uestras tomadas para construir la densidad y también del número de clusters N umClusters que conforman la densidad. La siguiente gráfica muestra valores de M SE para N umM uestras entre 100 y 500 y N umClusters entre 20 y 100: 0.03 0.025 0.02 0.015 500 450 400 350 300 100 90 250 80 70 200 NumMuestras 60 50 150 40 100 30 20 NumClusters En general y como era de esperar el error cuadrático medio M SE disminuye conforme aumentan el número de muestras N umM uestras o el número de clusters N umClusters. En la siguiente sección hacemos un estudio más detallado sobre la dependencia del aprendizaje de estos parámetros. Los parámetros N umV ecinosGraf o y N umV ecinos también los hemos estudiado al mismo tiempo. Dejando el resto de valores fijos hemos ejecutado el algoritmo de aprendizaje y evaluado el error cuadrático medio barriendo los valores para N umV ecinosGraf o y N umV ecinos entre 1 y 20. Los parámetros α y γ se fijaron en los óptimos 0,1 y 0,14 encontrados anteriormente. La siguiente figura muestra el M SE para los distintos valores de N umV ecinos y N umV ecinosGraf o. 52 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. 0.04 0.035 0.03 0.025 0.02 0.015 20 15 20 15 10 10 5 NumVecinosGrafo 5 0 0 NumVecinos Como se observa para valores N umV ecinos ≥ 7 y N umV ecinosGraf o ≥ 7 la dependencia es mı́nima y con valores N umV ecinos = 5 y N umV ecinosGraf o = 8 hemos obtenido buenos resultados a la vez que un compromiso con el tiempo de cómputo. La cantidad de parámetros de los que depende nuestro modelo hace que su optimización sea una tarea a acometer seria. Para terminar esta sección notemos también la variedad de datos que podemos mostrar a la red durante el aprendizaje. Tenemos tres candidatos: las N umM uestras muestras que se usaron para construir la densidad, los N umClusters clusters de la densidad o M nuevas muestras de la imagen. Empı́ricamente hemos determinado que se obtienen buenos resultados iniciando el aprendizaje con una fase competitiva pura en el que se muestran a la red cada cluster de la densidad y a continuación se siguen presentando a la red dichos clusters de manera cı́clica hasta alcanzar N umM axIteraciones. Hemos acompañado este método de funciones lineales a trozos para las funciones σ y η: 53 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. 2 1 1.8 0.9 1.6 0.8 1.4 0.7 1.2 1 0.6 0.8 0.5 0.6 0.4 0.4 0.3 0.2 0 0 20 40 60 80 100 120 140 160 180 200 0.2 0 20 40 60 80 100 120 140 160 180 200 Figura 4.3: Función σ a la izquierda y función η a la derecha para N umClusters = 100 y N umM axIteraciones = 200. Estudiando el error cuadrático medio M SE para distintos valores máximo y residual de σ y distintos valores del segundo máximo de η y residual de η (el primer máximo de η lo hemos fijado en 1) hemos obtenido óptimos con valor máximo de σ = 0,3, valor residual de σ = 0,1, segundo valor máximo de η = 0,6 y valor residual de η = 0,25. Este algoritmo de aprendizaje de dos fases junto con los parámetros óptimos comentados son los que usaremos en la siguiente sección. 54 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. 4.3. Resultados. La calidad de la reconstrucción de la imagen se suele evaluar mediante la razón señal-ruido pico, PSNR por sus siglas en inglés, definida como sigue: 3 ), (4.2) M SE donde el error cuadrático medio fue introducido en la Ecuación (1.1) y reproducimos aquı́ P SN R = 10 · log10 ( M SE = PN umP ixeles i=1 ||xi − BM U (xi )||2 , N umP ixeles (4.3) donde nótese que el valor M SE se calcula usando para ello todos los pı́xeles de la imagen. Antes de pasar al estudio comparativo hemos estudiado en más profundidad la dependencia del P SN R con respecto a N umM uestras, N umClusters y N umM axIteraciones con el método de aprendizaje de dos fases descrito en la sección anterior. Para ello hemos calculado la media y desviaciones tı́picas de P SN R sobre una muestra de 10 ejecuciones sobre la imagen del mandril en tamaño 128 × 128, tal y como muestran las siguientes tablas: NumClusters NumNeuronas 6 16 50 19.04 22.18 100 19.61 22.98 150 19.41 23.09 200 19.12 23.2 32 23.58 23.77 24.65 25.08 64 23.84 24.74 25.65 26.25 128 23.99 25.19 26.09 27.02 256 24.15 25.48 26.56 27.39 Cuadro 4.1: Valores medios de P SN R con N umM uestras = 200 y N umM axIteraciones = 200. 55 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. NumClusters NumNeuronas 6 16 32 50 1.25 0.6 0.57 100 1.58 0.32 0.68 150 1.54 0.39 0.59 200 0.88 0.35 0.37 64 128 0.54 0.56 0.51 0.39 0.51 0.52 0.38 0.2 256 0.28 0.59 0.37 0.53 Cuadro 4.2: Desviaciones tı́picas de P SN R con N umM uestras = 200 y N umM axIteraciones = 200. Como muestran los valores medios de P SN R el aprendizaje mejora conforme aumenta el número de clusters. Además, esta mejora es mayor cuanto más neuronas consideremos: para 256 neuronas la diferencia en P SN R entre 200 y 50 clusters es de 27,39 − 24,15 = 3,24, para 16 neuronas la diferencia es de 23,2 − 22,18 = 1,02. La representación gráfica de los valores medios P SN R es la siguiente: 28 27 26 25 24 23 22 21 20 19 200 256 150 128 64 100 32 16 NumClusters 50 6 56 NumNeuronas CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. La siguientes tablas recopilan información sobre valores P SN R variando N umM uestras frente a N umN euronas: NumMuestras NumNeuronas 6 16 200 19.61 22.77 500 19.97 22.93 1000 19.7 22.99 2000 20.21 23.2 5000 19.56 23.21 32 23.85 24.08 24.23 24.26 24.31 64 128 256 24.87 25.31 25.25 24.55 25.37 25.57 24.78 25.46 25.91 25 25.78 25.99 25.36 25.79 26 Cuadro 4.3: Valores medios de P SN R con N umClusters = 100 y N umM axIteraciones = 200. NumMuestras NumNeuronas 6 16 32 100 1.58 0.33 0.52 200 1.19 0.46 0.51 500 1.23 0.37 0.41 2000 1.09 0.36 0.35 5000 1.39 0.29 0.53 64 0.51 0.45 0.59 0.18 0.22 128 256 0.49 0.45 0.37 0.34 0.27 0.31 0.15 0.16 0.15 0.17 Cuadro 4.4: Desviaciones tı́picas de P SN R con N umClusters = 100 y N umM axIteraciones = 200. Como se observa el aumento del número de muestras produce una mejora en el aprendizaje en términos de P SN R y esta mejora no aumenta tan acusadamente como en el caso anterior al incrementar el número de neuronas. Es de destacar sin embargo que el decremento de las desviaciones tı́picas es mucho más patente en este caso que en el anterior. Representamos a continuación los valores medios P SN R: 57 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. 26 25 24 23 22 21 20 19 5000 256 2000 128 1000 64 32 500 16 NumMuestras 200 6 NumNeuronas Para terminar hemos estudiado los valores P SN R enfrentando N umM axIteraciones y N umN euronas: NumMaxIteraciones 200 500 1000 2000 5000 NumNeuronas 6 16 18.81 22.63 18.6 22.54 18.69 22.54 18.96 22.6 19.23 22.59 32 24.03 24.18 24.22 24.25 24.27 64 24.84 24.96 24.98 24.98 24.97 128 25.25 25.32 25.35 25.36 25.36 256 25.15 25.17 25.17 25.17 25.17 Cuadro 4.5: Valores medios de P SN R con N umM uestras = 100 y N umClusters = 100. 58 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. NumMaxIteraciones NumNeuronas 6 16 32 64 1.33 0.55 0.63 0.46 1.42 0.8 0.57 0.47 1.67 0.83 0.59 0.49 1.54 0.84 0.59 0.5 1.63 0.86 0.58 0.51 200 500 1000 2000 5000 128 0.42 0.42 0.42 0.42 0.43 256 0.56 0.57 0.57 0.57 0.57 Cuadro 4.6: Desviaciones tı́picas de P SN R con N umM uestras = 100 y N umClusters = 100. En este caso, fijado el número de neuronas, la mejora en el aprendizaje en términos de P SN R que produce el aumento del número máximo de iteraciones es mı́nimo. Esto no deberı́a sorprender ya que, como se describió en la sección anterior, el método de aprendizaje que estamos usando presenta cı́clicamente los clusters a la red. Los valores medios P SN R tienen la siguiente representación: 26 25 24 23 22 21 20 19 18 5000 256 2000 128 1000 64 32 500 16 NjumMaxIteraciones 200 6 NumNeuronas En conclusión, deducimos que es el número de clusters la variable cuyo aumento produce mayores mejoras en el aprendizaje, mientras que el incremento de el número de muestras o el número máximo de iteraciones producen mejoras sólo marginales. 59 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. El estudio comparativo lo dividimos en dos partes. En la primera ejecutaremos el algoritmo de aprendizaje de dos fases de la Sección 4.2 hasta alcanzar N umM axIteraciones. En la segunda parte añadiremos un criterio de convergencia a dicho algoritmo. 60 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. 4.3.1. Algoritmo de aprendizaje de dos fases. La primera parte la realizaremos sobre las siguientes imágenes, conocidas respectivamente como Mandrill, Lena y Peppers: En los artı́culos [5] y [21] se presentan dos tipos de mapa auto-organizados conocidos como FS-SOM (frequency sensitive SOM) y SA-SOM (sample-size adaptative SOM) respectivamente. Estos algoritmos ya fueron comentados en la Sección 1.4. De [21, Fig. 8] tomamos los valores P SN R (redondeados) para la segmentación de Mandrill, Lena y Peppers en tamaño 128 × 128 y con un 10 % de razón de muestreo, es decir, tomando unas 1638 muestras de la imagen, para distintos número de neuronas: Imagen Método NumNeuronas 16 32 64 FS-SOM 24.5 23 20.5 Mandrill SA-SOM 25.5 28 30 FS-SOM 28.5 27.5 25 Lena SA-SOM 29.5 32.5 34 FS-SOM 26 25 23 Peppers SA-SOM 27 28.5 30.5 128 256 19 18 31.5 33 22 22 36 37 21 20.5 32 33 Cuadro 4.7: Valores de P SN R para SA-SOM sobre imágenes 128 × 128. Se observa que los valores P SN R para FS-SOM decrecen conforme aumenta el número de neuronas. Este comportamiento anormal cesa al aumentar el número de iteraciones [5, Table I] o el tamaño de la imagen [21, Fig. 8]. Hemos ejecutado nuestro mapa auto-organizado generalizado con 1638 muestras, 200 clusters, 400 iteraciones y diversos números de neuronas sobre 61 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. imágenes en tamaño 128 × 128 para obtener los siguientes resultados, dónde las medidas estadı́sticas se realizaron sobre muestras de 10 ejecuciones: Imagen PSNR NumNeuronas 16 32 Media 23.14 24.19 Mandrill Desviación tı́pica 0.33 0.46 Media 27.19 29.61 Lena Desviación tı́pica 0.89 0.31 Media 24.84 26.03 Peppers Desviación tı́pica 0.33 0.54 64 25.2 0.19 30.87 0.43 27.16 0.19 128 25.92 0.26 31.53 0.3 27.72 0.2 256 26.44 0.26 32.33 0.55 28.06 0.15 Cuadro 4.8: Valores medios y desviaciones tı́tpicas de P SN R sobre imágenes 128 × 128. Nuestros valores de P SN R se encuentran por encima de los de FS-SOM y por debajo de los de SA-SOM y la diferencia aumenta conforme aumenta el número de neuronas. Es de destacar que nuestro algoritmo sólo está presentando a la red 200 muestras distintas mientras que FS-SOM y SA-SOM están presentando a la red más de 1600 muestras. En la siguiente gráfica podemos observar los valores P SN R de las dos últimas tablas: 62 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. 38 Mandrill FS−SOM Mandrill SA−SOM Mandrill Lena FS−SOM Lena SA−SOM Lena Peppers FS−SOM Peppers SA−SOM Peppers 36 34 32 PSNR 30 28 26 24 22 20 18 16 32 64 NumNeuronas 128 256 Figura 4.4: Valores P SN R para las tres imágenes Mandrill (en azul), Lena (en rojo) y Peppers (en verde) y los tres métodos FS-SOM (lı́nea continua), SA-SOM (lı́nea rayada) y nuestro mapa auto-organizado generalizado (lı́nea punteada). Las siguientes imágenes muestran reconstrucciones RGB tı́picas de las imágenes Mandrill, Lena y Peppers en tamaño 128 × 128 para 16, 64 y 256 neuronas y los demás parámetros iguales a los usados en la tabla anterior: Figura 4.5: Reconstrucción de Mandrill con 16, 64 y 256 neuronas. 63 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. Figura 4.6: Reconstrucción de Lena con 16, 64 y 256 neuronas. Figura 4.7: Reconstrucción de Peppers con 16, 64 y 256 neuronas. La siguiente comparación será con el mapa auto-organizado descrito en [1, Table 3], conocido como LARFSOM (local adaptive receptive field SOM). En [1, Table 4, Table 3, Table 2] encontramos la siguiente información sobre segmentación con número de neuronas bajo para las imágenes Mandrill, Lena y Peppers en tamaño 512 × 512: Imagen NumNeuronas Iteraciones Mandrill 6 271 Lena 4 219 Peppers 6 330 PSNR 20.75 23.53 22.75 Cuadro 4.9: Valores de P SN R para LARFSOM sobre imágenes 512 × 512. Usando nuestro mapa auto-organizado hemos obtenido las siguientes medidas estadı́sticas para valores P SN R sobre 10 ejecuciones: 64 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. Imagen Mandrill Lena Peppers Neuronas NumMaxIteraciones 6 271 4 219 6 330 Media Desviación tı́pica 19.96 0.29 22.6 0.82 20.75 0.9 Cuadro 4.10: Valores de P SN R sobre imágenes 512 × 512. Hemos tomado N umM uestras = N umM axIteraciones y N umClusters = N umM axIteraciones/2 de forma que se presentan los clusters dos veces a la red, primero en aprendizaje competitivo puro y después en aprendizaje clásico, tal y como se describió en la sección anterior. Los valores P SN R obtenidos son inferiores a los de LARFSOM. Reduciendo el número de muestras y de iteraciones a la mitad obtuvimos los siguientes valores de P SN R: Imagen Mandrill Lena Peppers Neuronas NumMaxIteraciones 6 135 4 108 6 165 Media Desviación tı́pica 20.01 0.53 22.67 0.52 20.72 0.75 Cuadro 4.11: Valores de P SN R sobre imágenes 512 × 512. Aquı́ de nuevo pusimos N umM uestras = N umM axIteraciones y N umClusters = N umM axIteraciones/2. Como se observa los valores medios de P SN R son prácticamente idénticos a los de la tabla anterior. Esto demuestra, por un lado, un excelente comportamiento de nuestro mapa autoorganizado para número de neuronas, muestras e iteraciones bajos. Por otro lado, esto induce a creer que mejorando el método de aprendizaje los valores medios de P SN R obtenidos en el Cuadro 4.10 pueden incrementarse ya que aparentemente hay más información que puede extraerse de las muestras usadas. 65 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. Figura 4.8: Reconstrucción de Mandrill, Lena y Peppers con 6, 4 y 6 prototipos respectivamente. 4.3.2. Algoritmo de aprendizaje de dos fases con criterio de convergencia. La segunda parte del estudio comparativo la realizaremos sobre las imágenes Flowers, Sailboat, Pens y Yacht, que son de tamaños 500×362, 512×512, 512 × 480 y 512 × 480 respectivamente: 66 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. La siguiente tabla [1, Table 5, Table 6, Table 7, Table 8] muestra valores P SN R sobre estas imágenes para FS-SOM, LARFSOM y el algoritmo clásico de mapa auto-organizado SOM para segmentación de imágenes. Imagen Método Neuronas Iteraciones SOM 16 18064 Flowers FS-SOM 16 892 LARFSOM 16 2636 SOM 16 4066 Sailboat FS-SOM 16 389 LARFSOM 16 437 SOM 16 13504 Pens FS-SOM 16 449 LARFSOM 16 599 SOM 16 3851 Yacht FS-SOM 16 270 LARFSOM 16 364 PSNR 21.95 20.50 24.82 21.12 21.69 24.45 20.55 21.68 24.74 20.07 21.72 24.35 El algoritmo de aprendizaje que usamos es idéntico al explicado en la Sección 4.2 salvo que en la segunda fase, es decir, en la fase con aprendizaje no competitivo puro, hemos añadido el siguiente criterio de convergencia: PN ||ni (t + 1) − ni (t)||2 ≤ 0,0001. N Es decir, que paramos el algoritmo si la diferencia (al cuadrado) media entre las posiciones de las neuronas es menor que 10−4 o si alcanzamos N umM axIteraciones. Hemos calculado los siguientes valores estadı́sticos i=1 67 CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES. sobre 10 ejecuciones con N umM uestras = 1000, N umClusters = 100, N umN euronas = 16 y N umM axIteraciones = 10000: Imagen Neuronas Flowers 16 Sailboat 16 Pens 16 Yacht 16 Iteraciones me- P SN R medio dias (desviación) (desviación) 167.9 (44.62) 21.64 (1.59) 173.7 (57.38) 25.39 (0.35) 189.4 (149.06) 23.64 (1.76) 250.5 (255.67) 24.14 (0.82) Como vemos los valores medios P SN R superan en general a los de SOM y FS-SOM y en ocasiones también a los de LARFSOM. Recordemos de nuevo que estos resultados se consiguen presentado a la red sólo 100 muestras distintas (N umClusters = 100 clusters). Las siguientes figuras muestran reconstrucciones con 16 prototipos: 68 Capı́tulo 5 Discusión y conclusiones. En este trabajo hemos presentado los mapas auto-organizados tal y como fueron introducidas por Kohonen y particularizando desde el punto de vista general de redes neuronales artificiales. De entre las miles de aplicaciones que tienen los mapas auto-organizados hemos descrito varias de ellas orientadas a la segmentación de imágenes en color. Posteriormente hemos introducido el concepto de mapa auto-organizado generalizado, cuya principal virtud sea quizás su simetrı́a respecto a los datos de entrada y las neuronas. Hemos visto como algunas de las variantes de mapas auto-organizados explicados anteriormente se enmarcan dentro de este nuevo concepto generalizado mientras que no lo hacı́an en el concepto clásico de mapa auto-organizado. Creemos que este concepto podrı́a dar a nuevas desarrollos o variaciones de mapas auto-organizados. Como aplicación hemos diseñado un mapa auto-organizado generalizado orientado a la segmentación de imágenes en color. La diferencia con un mapa clásico radica fundamentalmente en que el movimiento de las neuronas se realiza a lo largo de las geodésicas de cierta métrica. Esta métrica depende de una densidad continua calculada a partir de las muestras. La implementación se ha llevado a cabo en MATLAB y C. Se ha probado el mapa sobre imágenes estándares. Los valores de P SN R obtenidos se encuentran entre aquellos obtenidos por otros mapas auto-organizados recientes orientados a la segmentación de imágenes en color y llegan 69 CAPÍTULO 5. DISCUSIÓN Y CONCLUSIONES. a superar a los mejores de estos métodos en algunas de las pruebas. Resaltemos aquı́ que los métodos contra los que se ha comparado el algoritmo, FS-SOM, SA-SOM y LARFSOM, son incompatibles entre si ya que proponen distintas estrategias relacionadas con la elección de la BMU. Sin embargo, ya que nuestro mapa auto-organizado modifica un mapa autoorganizado clásico a un nivel profundo, a saber, en el cómputo de distancias en el espacio de entrada y en el movimiento de las neuronas hacia la entrada, es totalmente plausible desarrollar distintas versiones de nuestro algoritmo que incluyan las estrategias BMU de FS-SOM, SA-SOM o LARFSOM. Nuestro mapa se muestra más competitivo para número de iteraciones bajo, mientras que para número de iteraciones alto los valores P SN R divergen más de los otros métodos estudiados. Esto no es de extrañar ya que en el método de aprendizaje de dos fases explicado los clusters de la densidad son presentados reiterativamente a la red, con lo que se pierde parte de la información de la imagen. Un número de muestras y de clusters equiparable a un número de iteraciones grande (del orden de 104 ) es computacionalmente intratable. Veamos además por qué el presentar una muestra en vez de un cluster a la red puede distorsionar el aprendizaje. Para ello nótese primero que los clusters tienden a estar en el interior de la nube de muestras como en los Ejemplos 3.1.1 y 3.2.1. Ası́ que una distribución tı́pica del inverso de la densidad entre un cluster y una muestra será como se muestra en la siguiente figura: Si una neurona cercana al cluster ha de moverse en dirección a la muestra una pequeña cantidad, digamos un 5 %, esto puede producir un gran desplazamiento en distancia euclı́dea: 70 CAPÍTULO 5. DISCUSIÓN Y CONCLUSIONES. Esta distorsión es importante en tanto en cuanto los valores M SE y P SN R se calculan usando para ello distancia euclı́dea. Un primer objetivo para seguir desarrollando esta red serı́a pues integrar mejor la densidad continua con un aprendizaje basado en muestras de la imagen independientes de la densidad. Una posible opción aquı́ serı́a aprender siempre mediante clusters pero ir calculando nuevas densidades a medida que se toman nuevas muestras de la imagen. Algún efecto de memoria deberı́a considerarse para minimizar la discrepancia entre una densidad y la siguiente, como por ejemplo usar parte de los clusters o muestras de la densidad antigua como muestras para la nueva densidad. Además, un estudio más pormenorizado de la influencia de los numerosos parámetros de la red en los valores de salida P SN R serı́a conveniente. Estos parámetros incluyen el número de iteraciones, el número de clusters, número de vecinos, número de vecinos del grafo, parámetros de construcción de la densidad y las funciones σ y η de aprendizaje. Posiblemente distintos tipos de imágenes requieran distintos conjuntos de parámetros. Igualmente, distintos valores P SN R objetivo requerirán métodos de aprendizaje distintos. Tampoco deberı́a obviarse un estudio sistemático del tiempo de aprendizaje, el cual es otro baremo para comparar este trabajo con otros de la misma área. Debido a la considerable mayor carga computacional del cálculo de una geodésica frente al cálculo de un segmento rectilı́neo aquı́ se deberı́a esperar estar en seria desventaja frente a otros métodos. En otro orden, una versión con una malla dos dimensional para las neuronas deberı́a producir mejores resultados en términos de P SN R. Un problema abierto de carácter más teórico pero que merece la pena considerar es el estudio de condiciones para que la aproximación a las geodésicas 71 CAPÍTULO 5. DISCUSIÓN Y CONCLUSIONES. y a la distancia geodésica consideradas aquı́ convergen a las geodésicas y a las distancias geodésicas teóricas respectivamente. Esto darı́a una base más solida al algoritmo en sı́. En el trabajo [2] se presentan dichos criterios para un algoritmo relacionado de reducción de la dimensión conocido como Isomap. Con referencia a los valores P SN R para segmentación de imágenes en la bibliografı́a es interesante que, aunque frecuentemente se muestran valores para distintos tamaños de imágenes (como 128 × 128, 256 × 256 y 512 × 512), los valores P SN R obtenidos deberı́an ser, al menos teóricamente, iguales. Si tomamos M muestras de una imagen en tamaño TX × TY elegidas con pares de proporciones aleatorias entre 0 y 1, estos mismos pares darı́an las mismas muestras en la misma imagen en tamaño λTX × λTY con λ > 1. Dado que las muestras son las mismas el algoritmo de aprendizaje deberı́a encontrar los mismos prototipos para ambas ejecuciones. Finalmente, el valor M SE para la imagen grande M SE = Pλ2 TX TY i=1 ||xi − BM U (xi )||2 λ2 TX TY puede reescribirse como PTX TY i=1 λ2 ||xi − BM U (xi )||2 λ2 TX TY ya que cada pı́xel de la imagen pequeña da lugar a λ2 pı́xeles en la imagen grande. Cancelando los dos términos λ2 notamos que esto es exactamente el valor M SE para la imagen pequeña. Podemos observar este hecho en [21, Table 1] comparando los valores P SN R de tamaño de imagen 512 × 512 y razón de muestreo 0,1 con los valores P SN R de tamaño de imagen 256 × 256 y razón de muestreo 0,4, ya que ambos valores P SN R son similares y corresponden aproximadamente a unas 26200 muestras. Lo mismo ocurre con los tamaños 256×256 y 128×128 de la misma tabla y también en la gráfica de [21, Fig. 8]. También serı́a interesante investigar el mı́nimo global de M SE para una imagen dada y un número de neuronas dado y compararlo con los valores M SE en la bibliografı́a. Para ello podrı́a ensayarse una aproximación me72 CAPÍTULO 5. DISCUSIÓN Y CONCLUSIONES. diante posiciones de las neuronas en una malla de vértices tridimensional. Esto serı́a sin duda computacionalmente muy costoso, pero arrojarı́a cierta luz sobre la calidad de los métodos SOM en general. Es claro que tal mı́nimo global debe existir ya que los valores de las prototipos o neuronas están acotados a un cubo del tipo [0, 255]3 o [0, 1]3 y M SE es función continua de las posiciones de las neuronas (a pesar de que la función BM U no es función continua de la variable de entrada). Se puede probar que si queremos obtener el valor M SE mı́nimo global con un error menor que ǫ > 0 es suficiente tomar la distancia δ entre vértices de la malla suficientemente pequeña. Para convencerse, supongamos que nb1 , . . . , nc N son las posiciones de las neuronas (posiblemente no en la malla) que dan un valor M SE mı́nimo global. Ahora podemos tomar δ suficientemente pequeño tal que la distancia de cada pı́xel xi a una neurona que no esté a la misma distancia que la neurona BM U (xi ) sea mayor que la distancia a BM U (xi ) más δ, en fórmulas: δ tal que ||xi − nbj || > ||xi − BM U (xi )|| + δ si ||xi − nbj || > ||xi − BM U (xi )||, para cada pı́xel xi y cada prototipo nbj . Esta elección de δ es posible por la finitud de los conjuntos involucrados. Tomemos ahora una malla de radio δ y vértices de la malla n1 , . . . , nN a distancias menores que 2δ de nb1 , . . . , nc N respectivamente. Por la elección de δ, si la neurona BM U para el pı́xel xi era el prototipo nbj ahora tendremos también que la neurona más cercana es nj . Considerando δ más pequeño si hace falta se comprueba entonces que el M SE con respecto a n1 , . . . , nN difiere del M SE con respecto a nb1 , . . . , nc N, es decir, difiere del mı́nimo global, en menos de ǫ. 73 Apéndice A Geometrı́a y Topologı́a. En esta sección introducimos varias nociones matemáticas que se usan en el trabajo. Para una versión más detallada se remite al lector a [4]. Empezamos con la noción de espacio métrico. Definición A.0.1. Un espacio métrico es un conjunto M no vacı́o y una función d : M × M → R tal que para cualesquiera x, y, z ∈ M se satisface d(x, y) ≥ 0 (no negatividad), d(x, y) = 0 ⇔ x = y, d(x, y) = d(y, x) (simetrı́a), d(x, y) ≤ d(x, z) + d(z, y) (desigualdad triangular). La función d es la métrica del espacio. Por ejemplo, el espacio euclı́deo Rm es un espacio métrico con la métrica euclı́dea d((x1 , . . . , xm ), (y1 , . . . , ym )) = p (x1 − y1 )2 + . . . + (xm − ym )2 . (A.1) Si M es un espacio métrico con métrica d, la bola centrada en x ∈ M con radio r ∈ R, r > 0 es el conjunto B(x, r) = {y ∈ M |d(x, y) < r}. 74 (A.2) APÉNDICE A. GEOMETRÍA Y TOPOLOGÍA. En el espacio métrico R2 las bolas corresponden a discos rellenos sin la circunferencia que lo delimitan, y en el espacio métrico R3 corresponden a esferas macizas sin la superficie esférica que lo delimitan. Un subconjunto U de un espacio métrico M se denomina abierto si se puede escribir como una unión, posiblemente infinita, de bolas. Esto es es equivalente a que para cualquier punto x ∈ U existe un radio r > 0 suficientemente pequeño tal que B(x, r) ⊆ U . Es decir, que si un punto está en U también lo está una pequeña bola alrededor de este punto. Por ejemplo, el subconjunto (0, 1) = {x ∈ R|0 < x < 1} es abierto en el espacio métrico R. El conjunto [0, 1] = {x ∈ R|0 ≤ x ≤ 1} no lo es porque la condición falla en los puntos 0 y 1. Un disco en R2 es abierto sólo si no contiene ningún punto de la circunferencia que lo delimita. Una esfera en R3 es abierto sólo si no contiene ningún punto de la superficie esférica que lo delimita. Cualquier subconjunto de un espacio métrico M se convierte en un espacio métrico sin más que restringir la métrica de M a los puntos del subconjunto. Por ejemplo, una recta, un segmento, un plano, una esfera o un toro yaciendo en R3 se convierten en espacios métricos al heredar la métrica euclı́dea de R3 . Pasamos ahora a la noción de variedad diferenciable de dimensión m. Es este un tipo especial de espacio métrico que localmente es indistinguible de Rm . Más concretamente, cada punto x ∈ M debe yacer en un entorno coordenado. Un entorno coordenado es simplemente un conjunto U abierto en M junto con una biyección ϕ de U a un abierto de Rm . A esta función se le exige que sea un homeomorfismo, es decir, se le requiere que lleve abiertos de U a abiertos de Rm y viceversa, es decir, que su inversa lleve abiertos de Rm a abiertos de U . Esta función ϕ es la función coordenada porque asigna m coordenadas a cada punto del abierto U de M . ¿Qué ocurre cuando dos entornos coordenados intersecan? Sean ϕ : U → Rm y ψ : V → Rm dos entornos coordenados y supongamos que U ∩ V 6= ∅, esto es, que los abiertos U y V intersecan. Tenemos entonces un nuevo homeomorfismo ψ ◦ ϕ−1 : ϕ(U ∩ V ) → ψ(U ∩ V ). (A.3) 75 APÉNDICE A. GEOMETRÍA Y TOPOLOGÍA. A esta aplicación se le llama función de transición y convierte las m coordenadas que asigna ϕ a un punto de U ∩ V a las m coordenadas que les asigna ψ. Definición A.0.2. Una variedad diferenciable es un espacio métrico M con una familia de entornos coordenados {Uα , ϕα } tales que cada punto de M está en al menos un subconjunto Uα y para cualesquiera α y β con Uα ∩ Uβ 6= ∅ la función de transición entre Uα , ϕα y Uβ , ϕβ es infinitamente diferenciable. Para introducir la noción de geodésica necesitamos primero introducir el concepto de curva en una variedad diferenciable M . Definición A.0.3. Sea M una variedad diferenciable. Una curva en M es una aplicación γ : (a, b) → R o γ : [a, b] → R tal que para cada instante t en el intervalo y para cada entorno coordenado U , ϕ que contenga a γ(t) la función γ ϕ γ −1 (U ) → U → Rm es continua y diferenciable a trozos. Ası́ que una curva en M es simplemente una función desde un intervalo de R a M que es continua y diferenciable a trozos cuando la escribimos en coordenadas. Podemos ahora introducir el concepto de plano tangente en un punto x de la variedad M . Para ello sean γ1 : (−1, 1) → M y γ2 : (−1, 1) → M dos curvas en M con γ1 (0) = γ2 (0) = x y sea U , ϕ un entorno coordenado que contiene x. Diremos que γ1 y γ2 son equivalentes si las derivadas de ϕ ◦ γ1 y ϕ ◦ γ2 en 0 coinciden (como vectores de Rm ). Esto da una relación de equivalencia entre tales curvas y a cualquiera de sus clases de equivalencia la llamamos un vector tangente de M en x. El conjunto de tales vectores se denota por Tx M y no depende del entorno coordenado que hemos elegido U , ϕ. Este conjunto es un espacio vectorial de dimensión m, y la estructura de espacio vectorial de Tx M queda determinada asociando a cada clase de 76 APÉNDICE A. GEOMETRÍA Y TOPOLOGÍA. equivalencia de curvas su vector derivada en Rm . Esta estructura tampoco depende del entorno coordenado elegido. Este espacio corresponde por tanto a las posibles direcciones a las que una curva puede dirigirse a su paso por p. La siguiente figura muestra el espacio tangente en un punto de una superficie esférica ası́ como como un espacio tangente genérico junto con un vector como derivada de una curva en x. Pasamos ahora a definir lo que es una variedad Riemanniana. El objetivo es añadir a nuestra variedad diferenciable una manera de medir la longitud de los vectores de los espacios tangentes de M . Como veremos esto nos permitirá también medir la longitud de una curva en M . Recordemos que una forma bilineal definida positiva en un espacio vectorial V es una aplicación Φ : V × V → R tal que para todos v, w ∈ V , a1 , a2 , b1 , b2 ∈ R: Φ(a1 v1 +a2 v2 , b1 w1 +b2 w2 ) = a1 b1 Φ(v1 , w1 )+a1 b2 Φ(v1 , w2 )+a2 b1 Φ(v2 , w1 )+ a2 b2 Φ(v2 , w2 ) (bilineal), Φ(v, w) = Φ(w, v) (simétrica), Φ(v, v) ≥ 0 y Φ(v, v) = 0 ⇔ v = 0 (definida positiva). Si V tiene dimensión m y fijamos una base en V una forma bilineal simétrica definida positiva está determinada y determina una matriz m × m. Definición A.0.4. Una variedad Riemanniana es una variedad diferenciable con una forma bilineal simétrica definida positiva G(x) en el espacio tangente Tx M para cada punto x ∈ M . Al tomar cualquier entorno coordenado U , ϕ 77 APÉNDICE A. GEOMETRÍA Y TOPOLOGÍA. la matriz asociada a G(x) para cada punto x ∈ U debe tener sus m2 entradas infinitamente diferenciables. A G se le conoce como métrica Riemanniana de M. Dada una variedad Riemanniana M con métrica Riemanniana G el tamaño de un vector v ∈ Tx M está dado por p G(x)(v, v) ∈ R. En ocasiones identificaremos G(x) con la matriz de la forma bilineal G(x) tras fijar una base en Tx M . En ese caso el tamaño de v lo podemos reescribir como p vG(x)v t , donde v es un vector fila y tr significa traspuesta. El espacio euclı́deo Rm es una variedad Riemanniana cuya forma bilineal simétrica definida positiva tiene asociada la matriz identidad Im en coordenadas canónicas (x1 , . . . , xm ) y el tamaño de un vector v = (v1 , . . . , vm ) es p 2 , es decir, la norma euclı́dea de v. v12 + . . . + vm La longitud de una curva γ : [a, b] → M viene dada por la integral de camino L(γ) = Z bp G(γ(t))(γ ′ (t), γ ′ (t))dt = Z bp γ ′ (t)G(γ(t))γ ′ (t)tr dt. (A.4) a a Ası́, dados dos puntos x e y de la variedad Riemanniana M podemos definir una nueva distancia entre ellos, la distancia geodésica, mediante Z bp dgeodésica (x, y) = Ínfimo γ ′ (t)G(γ(t))γ ′ (t)tr dt, (A.5) a donde el ı́nfimo se toma sobre todas las curvas γ : [a, b] → M que empiezan en x y terminan en y, es decir, con γ(a) = x y γ(b) = y. A partir de la Ecuación (A.5) y mediante el uso de cálculo de variaciones se llegan a las ecuaciones geodésicas. Estas ecuaciones son ecuaciones dife2 i renciales ordinarias en dγ y ddtγ2i cuyas soluciones proporcionan (localmente) dt 78 APÉNDICE A. GEOMETRÍA Y TOPOLOGÍA. las geodésicas. Se escriben en término de los sı́mbolos de Christoffel que a su vez dependen de las derivadas de las entradas de la matriz G(x) y de su inversa G(x)−1 . La distancia dada por la Ecuación (A.5) produce una función dgeodésica : M × M → R que satisface las propiedades de la Definición A.0.1, es decir, dgeodésica es una métrica en M . Surge naturalmente la pregunta de cual es la relación de esta nueva métrica con la métrica original d en M . La respuesta es que ambas métricas son equivalentes. Esto quiere decir que los conjuntos abierto que generan dgeodésica y d son los mismos, es decir, que un conjunto se puede escribir como unión de dgeodésica -bolas si y sólo si se puede escribir como unión de d-bolas. También equivale a que las dos topologı́as inducidas por las métricas son iguales. Como en la Ecuación (A.5) estamos tomando un ı́nfimo no tenemos asegurado que exista una curva minimizante γmin entre x e y que tenga exactamente longitud L(γmin ) = dgeodésica (x, y). A una tal curva la llamaremos geodésica entre x e y. Sin embargo, en general, la existencia y unicidad de tales curvas minimizantes no está asegurada. Hay variedades Riemannianas donde no existen tales curvas minimizantes y variedades Riemannianas donde existe más de una. Se puede dar un ejemplo sencillo de esto último: en la superficie esférica las geodésicas o curvas minimizantes son arcos de circunferencias máximas, es decir, de circunferencias contenidas en la superficie esférica y en un plano que pasa por el centro de esta. Hay infinitas geodésicas entre el polo norte y el polo sur. La métrica Riemanniana en el espacio euclı́deo Rm usado en el mapa auto-organizado generalizado del Capı́tulo 3 es de la forma G(x) = 1 Im , d2 (x) donde Im es la matriz identidad y d(x) : Rm → R es la función densidad reconstruida evaluada en el punto x ∈ Rm . Esta función es una suma de distribuciones Gaussianas o normales con distintos parámetros y medias y satisface d(x) > 0 para todo x ∈ Rm y 79 APÉNDICE A. GEOMETRÍA Y TOPOLOGÍA. lı́m||x||→∞ d(x) = 0. Usando el teorema de Hopf-Rinow [4, VII.7.7] no es difı́cil demostrar usando la segunda propiedad de las anteriores que siempre habrá al menos una geodésica en nuestras condiciones. Por otro lado, una densidad degenerada con una única distribución Gaussiana simétrica es un ejemplo donde es fácil encontrar dos puntos con más de una geodésica entre ellos. 80 Apéndice B Glosario. Algoritmo de Floyd: Dado un grafo con pesos el algoritmo de Floyd permite hallar el camino entre dos vértices que minimiza la suma de los pesos de las aristas incluidas en el camino (el camino más corto). Una sola ejecución del algoritmo de Floyd genera dos matrices, una con las distancias mı́nimas entre cada par de vértices, y otra con el próximo vértice a recorrer para cada par de vértices. El camino más corto entre dos vértices se encuentra por recursión usando la segunda matriz. El algoritmo de Floyd es de complejidad O(|V |3 ), donde |V | es el número de vértices del grafo. Algoritmo de clustering k-means o “medias-k”: Es una técnica de clustering (ver clustering) que intenta agrupar n muestras en k grupos o clusters. El algoritmo procede iterativamente a partir de k valores iniciales calculando para cada una de las n entradas cual es el valor de estos k valores más cercano. Esto divide a las n entradas en k grupos o clusters. Los nuevos k valores se actualizan como el centroide de cada cluster. El algoritmo se vuelve a aplicar hasta que los clusters se estabilizan. Clustering: El análisis de clustering o agrupamiento consiste en dividir una conjunto de datos en distintos grupos de forma que los datos de un mismo grupo sean similares. El criterio de similitud se suele dar en términos de una distancia. 81 APÉNDICE B. GLOSARIO. Figura B.1: Conjunto de datos agrupados en 3 grupos. Los grupos están coloreados para poder identificarlos. Compresión de imágenes: Consiste en la aplicación de técnicas de compresión de datos a la información de una imagen. Esta ı́ntimamente relacionada con la segmentación de imágenes en color ya que la segmentación trata de encontrar patrones y regularidades en la imagen que a su vez pueden usarse para comprimirla. Cuantificación vectorial: La cuantificación vectorial es un tipo de algoritmo para clustering (ver clustering), y se puede considerar como un tipo de mapa auto-organizado con competitividad extrema o pura entre las neuronas y con topologı́a degenerada. Sólo la BMU se mueve hacia la entrada. Esto equivale a hacer tender σ a 0 en la Ecuación (1.3), para conseguir la siguiente función de entorno: θ(t, i, x(t)) = 1 si i = BM U 0 si i 6= BM U . Claramente no hay topologı́a en la malla de de neuronas en cuantificación vectorial (o siendo más precisos, se dota al conjunto de neuronas de la topologı́a discreta). Espacios de color CIELU V y CIELAB: Las siglas CIELU V y CIELAB son abreviaturas para los espacios de color CIE 1976 (L∗, u∗, v∗) y CIE 1976 (L∗, a∗, b∗). Estos espacios de colores fueron adoptados por la Comisión Internacional de la Iluminación (CIE) en 1976 a partir del espa82 APÉNDICE B. GLOSARIO. cio de color CIE 1931 XY Z. Ambos intentan conseguir percepción uniforme, es decir, que la similaridad perceptual entre colores se mida con la distancia que separa las coordenadas de dichos colores. Las transformaciones CIELAB ↔ RGB y CIELU V ↔ RGB son no lineales. Espacio de color RGB: Espacio de color que no satisface la percepción uniforme (ver espacios de color CIELAB y CIELU V ). Función MEX de MATLAB: MEX es la abreviatura de “MATLAB executable”. Un fichero MEX es una librerı́a dinámica compilada a partir de código fuente C, C + + o F ORT RAN y que se puede ejecutar en el entorno MATLAB como una función más. La transferencia de datos entre la función MEX y MATLAB y la ejecución de funciones MATLAB desde el fichero MEX se hace gracias a una librerı́a MATLAB que se enlaza al código fuente. La velocidad de ejecución suele ser entre 10 y 20 veces más rápida que la versión equivalente con un script de MATLAB. Segmentación de imágenes en color: En el campo de la visión artificial la segmentación de imágenes es un proceso por el cual los pı́xeles de una imagen se etiquetan para crear grupos que comparten ciertas caracterı́sticas visuales. Ejemplos de estas caracterı́sticas son la textura, el color o la intensidad. Este proceso se usa como paso previo a otros procesamientos de la imagen como el reconocimiento de contornos. El sentido en el que se usa segmentación de imágenes en color en este trabajo siempre se refiere a agrupar los pı́xeles con respecto a su color creando ası́ zonas de color homogéneo en una imagen a color. 83 Bibliografı́a [1] Araujo A.R.F., Costa D.C., Local adaptive receptive field self-organizing map for image color segmentation, Image and Vision Computing, Volume 27, Issue 9, 3 August 2009, Pages 1229-1239, ISSN 0262-8856, DOI: 10.1016/j.imavis.2008.11.014 [2] Bernstein M., de Silva V., Langford J. C., Tenenbaum J.B., Graph approximations to geodesics on embedded manifolds, 2000, preprint available at http://isomap.stanford.edu [3] Bishop C.M., Svensén M., Williams C.K.I., GTM: The Generative Topographic Mapping, Neural Computation, January 1, 1998, Vol. 10, No. 1, pages 215-234. [4] Boothby W.M., An introduction to differentiable manifolds and Riemannian geometry, Academic Press, 1986, Orlando, Florida. [5] Chang C., Xu P., Xiao R., Srikanthan T., New adaptive color quantization method based on self-organizing maps, IEEE Trans Neural Netw. 2005 Jan;16(1):237-49. [6] Dittenbach M., Merkl D., Rauber A., The Growing Hierarchical SelfOrganizing Map, Neural Networks, IEEE - INNS - ENNS International Joint Conference on, p. 6015, IEEE-INNS-ENNS International Joint Conference on Neural Networks (IJCNN’00)-Volume 6, 2000. [7] Dong G., Xie M., Color clustering and learning for image segmentation based on neural networks, IEEE Trans Neural Netw. 2005 Jul; 16(4):92536. 84 BIBLIOGRAFÍA [8] Kohonen T., Automatic formation of topological maps of patterns in a self-organizing system, in Erkki Oja and Olli Simula, editors, Proc. 2SCIA, Scand. Conf. on Image Analysis, pages 214-220, Helsinki, Finland, 1981, Suomen Hahmontunnistustutkimuksen Seura r. y. [9] Kohonen T., Self-organizing formation of topologically correct feature maps, Biol. Cyb., 43(1):59-59, 1982. [10] Kaski S., Kangas J., Kohonen T., Bibliography of Self-Organizing Map (SOM) Papers: 1981-1997, 1998, Neural Computing Surveys, 1, 102-350. [11] Kaski S., Sinkkonen J., Peltonen J., Bankruptcy analysis with selforganizing maps in learning metrics, IEEE Trans Neural Netw., 2001, 12(4), 936-47. [12] Li J. X., Visualization of high-dimensional data with relational perspective map, Information Visualization 3, 1 (Mar. 2004), 49-59. [13] López-Rubio E., Muñoz-Pérez J., Gómez-Ruiz J. A., Self-Organizing Dynamic Graphs. Neural Process. Lett. 16, 2 (Oct. 2002), 93-109. [14] López-Rubio E., Ortiz-de-Lazcano-Lobato J. M., Soft clustering for nonparametric probability density function estimation. Pattern Recogn. Lett. 29, 16 (Dec. 2008), 2085-2091. [15] López-Rubio E., Ortiz-De-Lazcano-Lobato J. M., Vargas-González M. C., Probabilistic Self-Organizing Graphs, in Proceedings of the 10th international Work-Conference on Artificial Neural Networks: Part I: Bioinspired Systems: Computational and Ambient intelligence (Salamanca, Spain, June 10 - 12, 2009). J. Cabestany, F. Sandoval, A. Prieto, and J. M. Corchado, Eds. Lecture Notes In Computer Science. Springer-Verlag, Berlin, Heidelberg, 180-187. [16] Oja M., Kaski S., Kohonen T., Bibliography of Self-Organizing Map (SOM) Papers: 1998-2001 Addendum, Neural Computing Surveys, 2003, 3, 1-56. 85 BIBLIOGRAFÍA [17] Omer I., Werman M., The Bottleneck Geodesic: Computing Pixel Affinity, Computer Vision and Pattern Recognition, IEEE Computer Society Conference on, pp. 1901-1907, 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 2 (CVPR’06), 2006. [18] Peltonen J., Klami A., Kaski S., Improved learning of Riemannian metrics for exploratory analysis. Neural Netw. 17, 8-9 (Oct. 2004), 10871100, DOI= http://dx.doi.org/10.1016/j.neunet.2004.06.008 [19] Pöllä M., Honkela T., Kohonen T., Bibliography of Self-Organizing Map (SOM) Papers: 2002-2005 Addendum. TKK Reports in Information and Computer Science, Helsinki University of Technology, Report TKK-ICSR24, 2009. [20] Rattray M., A Model-Based Distance for Clustering, Proc. of International Joint Conference on Neural Networks, 2000, p. 4013–4016. [21] Wang C., Lee C., Hsieh C., Sample-size adaptive self-organization map for color images quantization. Pattern Recogn. Lett. 28, 13 (Oct. 2007), 1616-1629, DOI= http://dx.doi.org/10.1016/j.patrec.2007.04.005 [22] Wang C., Lee C., Hsieh C., Classified self-organizing map with adaptive subcodebook for edge preserving vector quantization, Neurocomput. 72, 16-18 (Oct. 2009), 3760-3770, DOI= http://dx.doi.org/10.1016/j.neucom.2009.06.002 86