Download redes neuronales no supervisadas con topología din´amica para la

Document related concepts

Mapa autoorganizado wikipedia , lookup

Perceptrón wikipedia , lookup

Aprendizaje de cuantificación vectorial wikipedia , lookup

Redes neuronales probabilísticas wikipedia , lookup

Transcript

UNIVERSIDAD DE MÁLAGA
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
INFORMÁTICA
INGENIERO TÉCNICO EN INFORMÁTICA DE
SISTEMAS
REDES NEURONALES NO
SUPERVISADAS CON TOPOLOGÍA
DINÁMICA PARA LA SEGMENTACIÓN
DE IMÁGENES EN COLOR.
Realizado por
ANTONIO DÍAZ RAMOS
Dirigido por
EZEQUIEL LÓPEZ RUBIO
Departamento
LENGUAJES Y CIENCIAS DE LA COMPUTACIÓN
MÁLAGA, Noviembre 2010
1
UNIVERSIDAD DE MÁLAGA
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
INFORMÁTICA
INGENIERO TÉCNICO EN INFORMÁ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 académicamente por
Do /Da .
ACORDÓ POR
OTORGAR LA CALIFICACIÓN
DE
Y PARA QUE CONSTE, SE EXTIENDE FIRMADA POR LOS COMPARECIENTES DEL TRIBUNAL, LA PRESENTE DILIGENCIA.
de
Málaga a
2
del 20
Índice general
1. Introducción.
1.1. Descripció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 teórico.
23
2.1. Recuperando las variantes. . . . . . . . . . . . . . . . . . . . . 26
3. Un
3.1.
3.2.
3.3.
3.4.
mapa auto-organizado generalizado.
Construcción de la densidad continua. . . . .
Construcción del grafo de distancias. . . . .
Construcción de las geodésicas y la distancia
Funcionamiento del mapa auto-organizado. .
. . . . . .
. . . . . .
geodésica.
. . . . . .
4. Aplicación a la segmentación de imágenes.
4.1. Implementación MATLAB. . . . . . . . . . . . . .
4.2. Dependencia de los pará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. Discusión y conclusiones.
69
A. Geometrı́a y Topologı́a.
74
B. Glosario.
81
3
Capı́tulo 1
Introducción.
Los mapas auto-organizados o redes de Kohonen (SOM por sus siglas
en inglés, self-organizing map) fueron introducidos por el profesor finlandé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 visualización sencilla en sólo dos dimensiones.
La propiedad más importante de una SOM es que preserva las propiedades
topológicas de los datos, es decir, que datos próximos aparecen próximos en
la visualizació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, nutrición, educació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 sólo se
han añadido para resaltar las similitudes entre paı́ses:
4
CAPÍTULO 1. INTRODUCCIÓ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 está tomado de
la Universidad Tecnoló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 ú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
más de 7000 artı́culos que usan, analizan o se benefician de las SOM de
algún modo, incluyendo las siguientes áreas: imagen y vı́deo, reconocimiento
de patrones, técnicas matemáticas, inteligencia artificial, software, ingenierı́a
en biologı́a y medicina, teorı́a de la información y la codificación, reconocimiento de voz, control, procesamiento de señales, circuitos, ciencias de la
información y documentación y negocios y administración [10, 16, 19].
Este trabajo arranca del concepto de mapa auto-organizado y se ramifica
en una parte teórica y otra práctica. Partiendo de una descripción de los
mapas auto-organizados y algunas de sus variantes más populares desarrollamos un nuevo concepto de mapa auto-organizado generalizado. El nuevo
enfoque se llevará a cabo mediante conceptos matemáticos del área de la
5
CAPÍTULO 1. INTRODUCCIÓN.
Geometrı́a y la Topologı́a. La parte práctica del proyecto se concretará en la
aplicación de estas ideas al diseño de un mapa auto-organizado generalizado
que realice segmentación de imágenes en color. Éste constará 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 segmentación de imágenes en color se realizará un análisis estadı́stico a
posteriori.
El contenido del trabajo se subdivide en 3 capı́tulos y 2 apéndices. El
primero de ellos empieza con esta introducción y las dos secciones siguientes
1.1 y 1.2 se dedican, respectivamente, a una primera descripción elemental
de los mapas auto-organizados tras introducir conceptos básicos de redes
neuronales artificiales, y a una exposició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 secció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 secció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 teórico. Como hilo motivador y conductor del desarrollo teórico se usarán las ideas que se destacaron en la secciones 1.3 y 1.4. Para lo conceptos matemáticos involucrados se remite al
lector al Apéndice A.
El Capı́tulo 3 contiene una aplicació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 clásicos estriba en que
las neuronas recorren las geodésicas en cierta métrica en vez de segmentos
rectilı́neos. Esta construcción se complementa con el Capı́tulo 4, donde se
proporciona una instancia de este mapa auto-organizado aplicado al proble6
CAPÍTULO 1. INTRODUCCIÓN.
ma de la segmentación de imá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 método.
El último capı́tulo contiene una discusió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 Apéndice A contiene las definiciones matemáticas
necesarias del ámbito de la Geometrı́a y Topologı́a para introducir el concepto
de variedad diferenciable Riemanniana, ası́ como los conceptos de distancia
geodésica y geodésica (minimizante) en estas variedades. El Apéndice B contiene un glosario de términos especializados relacionados con el área de redes
neuronales artificiales y algunas de sus aplicaciones.
1.1.
Descripció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 función o aplicación
entre un determinado espacio de entrada y un espacio de salida f : X → Y :
Figura 1.2: Red neuronal artificial como una función.
Las redes neuronales artificiales están modeladas en la biologı́a del cerebro humano y constan de una serie de unidades o neuronas interconectadas.
La función f que representa un red neuronal artificial depende directamente
de estas neuronas y sus interconexiones. Su principal virtud y aquello que
7
CAPÍTULO 1. INTRODUCCIÓ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 funció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 actualización de la red neuronal y de la función que
representa.
Las redes neuronales artificiales se clasifican segú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 aproximación
a una función f que satisfaga f (xi ) = yi .
Aprendizaje no supervisado: se parte de un conjunto o distribución en
el espacio de entrada {xi }i=1,...,M y la red aprende para dar una función
f que minimize una funció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 ú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 distribución ortogonal o
hexagonal:
8
CAPÍTULO 1. INTRODUCCIÓ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, segú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 más cercano y sus neuronas próximas en la malla de la red modifican
sus pesos de forma que se asemejen má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 más cercana se selecciona (en rojo).
Finalmente, esta neurona y su vecinas en la malla se mueven hacia la entrada
x. La neurona más cercana o neurona ganadora se suele denotar por sus siglas
en inglés BMU (best matching unit). Este tipo de aprendizaje se conoce cómo
9
CAPÍTULO 1. INTRODUCCIÓN.
aprendizaje competitivo ya que las neuronas compiten por ser la más cercana
a la entrada.
Después de un número suficiente de iteraciones, la red se adapta a la
forma de los datos o distribución de entrada {xi }i=1,...,M :
Figura 1.5: Mapa auto-organizado tras un número grande de iteraciones.
La función f : X → Y asociada a un mapa auto-organizado es la función
que asigna a cualquier valor de entrada x la neurona de la malla cuyo vector
de pesos es má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
función por BM U : X → malla de la red, en vez de por f . Abusando un
poco de notación usaremos BMU tanto para denotar la neurona ganadora
en la malla como para denotar su vector de pesos en el espacio de entrada.
Qué versión estamos usando estará 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 función
de coste asociada que el mapa intenta minimizar durante su aprendizaje. En
nuestras aplicaciones esta función de coste será el error cuadrático medio o
M SE por sus siglas en inglés, mean squared error:
PM
||xi − BM U (xi )||2
M SE =
,
(1.1)
M
son los datos de entradas y M el número de entradas o
i=1
donde {xi }i=1,...,M
10
CAPÍTULO 1. INTRODUCCIÓN.
muestras. Esta cantidad mide como de bien la red ha capturado la distribución de entrada.
En general, el funcionamiento de un mapa auto-organizado se puede dividir en tres etapas:
1. Inicialización de los vectores de peso de las neuronas.
2. Aprendizaje de la red.
3. Evaluación de una función de coste como (1.1).
En la siguiente sección se explican las dos primeras etapas en detalle.
1.2.
Aprendizaje en un mapa auto-organizado.
En esta sección repasamos las ecuaciones clá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 població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 iteración actual t = 0, 1, 2, 3, . . ., de manera que
ni (t) corresponde al vector de la neurona i en el instante t. Por último, denotemos por x(t) el dato de entrada que se presenta a la red en la iteración
t. Este valor será una de las muestras de entrada {xi }i=1,...,M y es elegida de
entre todas ellas mediante algún orden o algún procedimiento aleatorio.
Podemos dar ahora una fó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)
Nótese que x(t) − ni (t) es un vector que apunta desde la posició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 posición actual, ni (t), un múltiplo
de este vector. La magnitud de este múltiplo viene dada por la cantidad
11
CAPÍTULO 1. INTRODUCCIÓN.
γ = γ(t, x(t), i) que depende de la iteración en la que nos encontramos t, de
la entrada x(t) y de la neurona i en cuestión. Esta cantidad γ debe ser un
número entre 0 y 1, 0 ≤ γ ≤ 1, y por tanto la nueva posición de la neurona
i-ésima se encuentra recorriendo γ por ciento del segmento que va desde la
posición actual de la neurona hasta la entrada.
Figura 1.6: Recorrido a lo largo del segmento neurona-entrada.
La función γ debe satisfacer las dos siguientes condiciones:
ser funció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 función decreciente del tiempo t.
Esto quiere decir que cuanto más alejada en la malla este una neurona de la
BMU menos aprenderá y que conforme avanza el número de iteraciones las
neuronas irán aprendiendo menos.
Por lo general la función γ se escribe como el producto de dos funciones
γ = θ(t, x(t), i)·η(t), donde θ se conoce como la función de entorno o vecindad
y η es la función de aprendizaje.
Un ejemplo habitual de función de entorno es la (pseudo) distribució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.
Además, asumimos que la distancia entre dos neuronas adyacentes de la malla
12
CAPÍTULO 1. INTRODUCCIÓN.
es 1. Esto es una normalización que será útil despué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 distribución θ se lo llevarán
las neuronas que esté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 número máximo de iteraciones
y tamaño del entorno inicial:
λ=
N umM axIteraciones
.
log(σ0 )
Se deduce que cuando t iguala el número má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 están a una distancia de 1). Por otro
lado, el entorno inicial σ0 se inicializa con la mitad de la distancia máxima
entre cualesquiera dos neuronas de la malla, es decir, con el “radio” de la
malla.
13
CAPÍTULO 1. INTRODUCCIÓN.
La función de aprendizaje tiene una expresión similar:
−t
η(t) = η0 · e λ ,
donde el coeficiente de aprendizaje inicial η0 es un número entre 0 y 1. Esto
quiere decir que las neuronas sufrirán un proceso de “aprendizaje rápido y
olvido lento”.
Los vectores de pesos de las neuronas se inicializan con algún procedimiento aleatorio, como tomar valores aleatorios dentro de un rango significativo
o tomar directamente el valor de muestras elegidas aleatoriamente.
El número máximo de iteraciones que llevará a cabo el algoritmo de aprendizaje lo hemos denotado N umM axIteraciones. Este número puede ser, por
ejemplo, el número de muestras, con lo que se realiza una iteración para cada
muestra. También puede existir algú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 posición en las neuronas es
suficientemente pequeño como para parar el proceso de aprendizaje.
Esto describe en reglas generales el aprendizaje en un mapa auto-organizado. En las aplicaciones prácticas puede haber variaciones en las exponenciales usadas, la inicialización de las neuronas, el criterio de convergencia,
etc.
Ejemplo 1.2.1. Como ejemplo práctico de los coeficientes de aprendizaje
supongamos que tenemos una malla unidimensional de 10 neuronas, que tomamos 100 muestras y que realizamos una iteración por muestra. Según las
fórmulas vistas anteriormente tendremos los siguientes valores para el entorno inicial y para la constante λ:
σ0 = 5 , λ = 100/ log(5) ≈ 62,133.
Tomemos además el coeficiente de aprendizaje inicial η0 = 0,9. En la
siguiente grá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 máxima de la BMU, es decir, para los casos dmalla (i, BM U ) = 0 y
14
CAPÍTULO 1. INTRODUCCIÓ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 máxima.
1.3.
Algunas variantes de mapas auto-organizados.
En esta secció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 apéndice A se puede encontrar una introducción a los conceptos matemáticos que usamos. A lo largo de la sección se irán destacando
variantes a las que puede someterse un mapa auto-organizado.
Una de las fuentes más ricas de alteraciones de los mapas auto-organizados
clá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 están conectadas entre sı́. Por ejemplo, hemos visto anteriormente que las topologı́as
clá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
CAPÍTULO 1. INTRODUCCIÓN.
4 bordes) se conecta a 4 vecinos (distribución ortogonal) o 6 vecinos (distribución hexagonal). Recordemos (Secció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 más allá y consideran una matriz cuadrada
que almacena la distancia entre cada par de neuronas de la malla. Estas
distancias no provienen de la inmersió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 algú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 métricos, es decir,
espacios dotados de una mé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 métrico. En
resumen:
Variante 1.3.1. Sustituir la topologı́a y distancia entre neuronas por la topologı́a y distancias en una espacio métrico al que pertenecen y en el que se
16
CAPÍTULO 1. INTRODUCCIÓN.
mueven las neuronas.
Otro grupo de autores han apostado por conservar la topologı́a y distancias clá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 métrica. Esta nueva mé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 métrica Riemanniana en el espacio
euclı́deo de entrada.
Estas métricas se conocen como métricas de aprendizaje (learning metrics) y se utilizan en los artı́culos [20], [18] y [11]. Estas nuevas métricas se
ajustan a los datos y permiten descubrir propiedades intrı́nsecas de los datos, lo cual es básico en un paradigma no supervisado como el de los mapas
auto-organizados.
Ejemplo 1.3.1. Como ejemplo veamos cómo estas métricas pueden permitir aislar agregaciones de datos en problemas de clustering [20]. La siguiente
figura muestra una configuració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 métrica euclı́dea y en
métrica de aprendizaje de un mismo punto respectivamente. Claramente la
métrica de aprendizaje es capaz de separar mucho mejor las dos componentes
de los datos que la métrica euclı́dea.
17
CAPÍTULO 1. INTRODUCCIÓN.
Figura 1.10: Métrica de aprendizaje versus métrica euclı́dea.
En este caso la matriz de la métrica Riemanniana en el punto x ∈ Rn
viene dada por [20, Ecuació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 mé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 inglés) para mostrar como
la métrica Riemanniana supera con creces a la euclı́dea al agrupar los datos
de entrada de una configuració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 métrica euclı́dea en el espacio de entrada por
una métrica Riemanniana construida a partir de una una densidad continua
que se ajusta a los datos de entrada.
Entre los mé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 parámetros
se estiman a partir de los datos de entrada y cuyo número de direcciones
principales se ajustan también a los datos. Este método será descrito con
mayor detalle en la Sección 3.1.
18
CAPÍTULO 1. INTRODUCCIÓN.
Profundizando un poco má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 métrica en cada punto. Esto es, queremos calcular la
geodésica o camino más corto entre dos puntos p y q del espacio euclı́deo
dotado de una métrica Riemanniana. En vez de minimizar la longitud en la
métrica Riemanniana (integral de camino) sobre todos los caminos entre p y
q aquı́ seguimos un enfoque práctico e intentamos aproximar esta geodésica
por un camino lineal a trozos.
El método más sencillo es definir la distancia geodésica como la longitud
en la métrica Riemanniana del segmento rectilı́neo entre p y q. La integral de
camino resultante se puede aproximar con un trapezoide. Otro método más
razonable, usado en [18] y [20], consiste en elegir el camino que minimiza la
distancia entre p y q en un grafo con vé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
métrica Riemanniana de los segmentos rectilı́neos entre los vértices (método
explicado antes). La elección del camino óptimo en el grafo se puede realizar
con un algoritmo como el de Floyd. La discusión de qué vértices y aristas se
usan para construir el grafo la posponemos.
Figura 1.11: Geodésicas y distancias geodésicas usando un segmento y un
grafo.
Al camino construido según este método lo llamaremos geodésica entre
p y q y a la suma de los pesos de las aristas que incluye dicho camino la
llamaremos distancia geodésica entre p y q.
19
CAPÍTULO 1. INTRODUCCIÓN.
Variante 1.3.3. Sustituir la distancia euclı́dea entre la entrada y las neuronas por la distancia geodésica correspondiente.
Es interesante que aunque los trabajos citados usen distancia geodésica
para calcular la BMU no usan en ningún caso la geodésica para desplazar
las neuronas hacia la entrada. En realidad se usa el camino que minimiza la
distancia geodésica só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 geodésica correspondiente.
1.4.
Otras variantes de mapas auto-organizados.
En esta sección discutimos otras variantes de mapas auto-organizados
que no están tan directamente relacionados con la topologı́a, distancia entre
neuronas o distancia entre entrada y neuronas como las de sección anterior.
Aquı́ también recopilamos las variantes destacadas.
Empezamos discutiendo modificaciones que se centran en la dinámica de
la población de neuronas. Recordemos que en los casos clásicos las neuronas
y las conexiones entre ellas son está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 según las necesidades de la red. La creación de neuronas tiene lugar
cuando la BMU no está 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 jerárquico que crece. En este caso hay construcción de neuronas y aristas cuando la información que guarda una porción
de la red necesita ser subclasificada con más detalle. No hay destrucción de
neuronas o aristas.
20
CAPÍTULO 1. INTRODUCCIÓN.
Variante 1.4.1. Permitir la creación y destrucció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 próximas
iteraciones. De esta forma se favorece a todas las neuronas más homogéneamente. En [21] ademá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 visualización en dos dimensiones de datos en muchas dimensiones una de las caracterı́sticas más destacadas de los mapas auto-organizados
no es de extrañar que se hayan planteado otras opciones con este objetivo en
mente. En [12] se explica un método para crear una representación en un toro
dos dimensional de datos en muchas dimensiones, preservando las distancias
tanto como sea posible. El método se conoce como relational perspective
map, mapa en perspectiva relacional. La idea es resolver las ecuaciones diferenciales que resultan de una diná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 aplicación topográfica generativa. En este caso la visualización
dos dimensional se consigue en dos fases. Primero, se construye una función
que va de una malla bidimensional de neuronas al espacio de entrada. Esta
función se define a través de funciones no lineales y el proceso de aprendizaje consiste en ajustar los parámetros de estas funciones hasta conseguir una
adaptación óptima a la nube de datos de entrada. Nótese que la función BMU
en un mapa auto-organizado clásico es del tipo BM U : X → malla de la red
21
CAPÍTULO 1. INTRODUCCIÓN.
(ver Sección 1.1) y que aquı́ estamos considerando una función en sentido
contrario malla de la red → X (donde X es el espacio de entrada). La segunda fase de este método consiste en construir una aplicación en el “sentido
correcto” usando el teorema de Bayes.
Los dos últimos trabajos comentados no son variantes de un mapa autoorganizado sino conceptos esencialmente distintos aunque relacionados. Lo
mismo ocurre con el trabajo [17], que está 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 nú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 métrica Riemanniana de que se dota al espacio de entrada a partir de una densidad continua podrı́a ser tal que las geodésicas eviten
las zonas de baja densidad.
Nótese que la mé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 ú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
solución a un problema de cuantificación vectorial (VQ por sus siglas en
inglés, vector quantization). Se aplica a compresión de imá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 inglés, simulated annealing). El templado es un proceso fı́sico en el que
algún material es sometido a altas temperaturas para después dejarlo enfriar
lentamente. Destaquemos aquı́ también que este artı́culo trata sobre segmentación de imágenes en color y que trabaja en el espacio de color CIELU V ,
un espacio de color donde la diferencia en percepció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 teórico.
Este capı́tulo se puede considerar como un ejercicio de abstracción del
concepto de mapa auto-organizado. Basándonos en las Secciones 1.3 y 1.4
daremos una definición de mapa auto-organizado generalizado. Ésta no servirá directamente como herramienta práctica sino má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 aplicación a la segmentación de imágenes en color. En la
Sección 2.1 veremos qué variantes de mapas auto-organizados de la Secciones
1.3 y 1.4 encajan dentro de este nuevo concepto.
Quizás la propiedad más interesante del concepto que presentamos es que
es simé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 mé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 geodésica correspondiente.
23
CAPÍTULO 2. NUEVO ENFOQUE TEÓRICO.
Por la primera variante impondremos que las neuronas vivan en un espacio
métrico por el que se pueden desplazar. De la tercera variante queremos que
el espacio de entrada sea también un espacio métrico (métrica es la distancia
geodé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 noción de distancia, es decir, que sean espacios
métricos. Ası́ que denotemos por N y por X a sendos espacios métricos. El
primero de ellos contendrá a las neuronas y el segundo de ellos a los datos
de entrada. Por tanto, cada neurona tiene un posición dinámica en N y
cada dato de entrada tiene una posición dinámica en X . En un mapa autoorganizado clásico estas posiciones son estáticas, es decir, que no varı́an con
el tiempo.
En el caso clásico, el vector de pesos de cada neurona es una posició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 función best matching
unit, BMU, introducida en la Sección 1.1, asocia a cada dato de entrada
una posición en N . Nótese que el codiminio de la función BM U definida en
esa secció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
también tiene asociadas dos posiciones, una en X y otra en N .
Definición 2.0.1. Un mapa auto-organizado generalizado consta de dos espacios métricos X y N en cada uno de los cuales se dan dos poblaciones
iniciales de M puntos y de N puntos.
En cada iteració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 función de coste para evaluar el aprendizaje depende de las posiciones de
los puntos.
En el caso clásico, las M posiciones en X son los datos de entrada y son
estáticas. Las M posiciones en N son la evaluación de la función BM U sobre
los datos de entrada y son dinámicas. Las N posiciones en N corresponden a
las posiciones de las neuronas en la malla y son estáticas. Las N posiciones en
24
CAPÍTULO 2. NUEVO ENFOQUE TEÓRICO.
X corresponden a los vectores de peso de las neuronas y son dinámicas. En
un mapa auto-organizado generalizado todas las posiciones son dinámicas.
Figura 2.1: Un mapa auto-organizado generalizado.
No se ha especificado ninguna propiedad del algoritmo de aprendizaje
ası́ que este es totalmente genérico. Esto da lugar a que la definición sea
quizá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 métrica euclı́dea en el espacio de entrada por una
mé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 geodésica correspondiente.
En nuestra definición de mapa auto-organizado generalizado no hemos
exigido que las distancias de X y N vengan inducidas por una métrica Riemanniana. Esto darı́a lugar a:
Definición 2.0.2. Una mapa auto-organizado Riemanniano es un mapa
auto-organizado generalizado en el que las métricas de X y/o N vienen inducidas por una métrica Riemanniana.
La segunda variante expuesta arriba impone que las neuronas se desplacen
por geodésicas:
25
CAPÍTULO 2. NUEVO ENFOQUE TEÓRICO.
Definición 2.0.3. Una mapa auto-organizado geodésico es un mapa autoorganizado generalizado en el que los espacios X y/o N son espacios geodésicos, es decir, espacios dotados de una geodésica entre cada par de puntos, y
el algoritmo de aprendizaje actualiza las nuevas posiciones mediante desplazamientos a lo largo de geodésicas.
2.1.
Recuperando las variantes.
Recordemos que todas las variantes de la secció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. Nótese que, como también comentamos al final de esa sección,
ninguna de ellas da lugar a un mapa auto-organizado geodésico.
Revisemos ahora las variantes de la Sección 1.4 algunas de las cuales,
como ya dijimos, están sólo relacionadas con mapas auto-organizados.
La Variante 1.4.1
Variante. Permitir la creación y destrucció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 estáticas (no ası́ sus posiciones).
Ası́ que los trabajos [1] y [6] no se pueden enmarcar dentro del nuevo contexto teó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 más interesante desde el punto de vista
de comparación con un mapa auto-organizado generalizado. Empecemos por
26
CAPÍTULO 2. NUEVO ENFOQUE TEÓRICO.
el mapa en perspectiva relacional [12], con el cual se consigue representar datos de dimensió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. Ademá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 estáticas. Las M posiciones en N son dinámicas y corresponden a las
iteraciones del algoritmo para resolver las ecuaciones diferenciales involucradas (hay una partı́cula por cada dato de entrada). La función de coste que
se quiere minimizar [12, Ecuación (1)] es función de las M posiciones en N .
La aplicación topográfica generativa [3] también se enmarca dentro del
presente contexto teórico. En este caso tanto X como N corresponden a
espacios euclı́deos de las dimensiones adecuadas. La población de N puntos en
X corresponde a la función y(x;W) definida en [3, Ecuació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, Sección 2.1]. La funció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 sólo se construyen después del aprendizaje usando el
teorema de Bayes [3, Sección 2.1]. Nuestro parámetros M y N corresponden
a N y K respectivamente en [3].
El trabajo [17], en el cual se asocia una nú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 má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 geodésico, pero como escribimos aquı́ todos los detalles no es necesario entender la notación dada allı́,
ası́ que emplearemos sólo la notación clásica para mapas auto-organizados del
Capı́tulo 1. En el Capı́tulo 4 se implementará una versión de este algoritmo
aplicada a la segmentación de imá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 métrica Riemanniana obtenida a partir de una densidad
continua que modela la nube de datos de entrada. A partir de esta métrica
Riemanniana dotaremos a este espacio euclı́deo de entrada de una noción de
geodésica y de una noción de distancia geodésica, obteniendo una métrica
distinta a la de la euclı́dea (ver Apéndice A).
Supongamos que el espacio de entrada es el espacio euclı́deo Rm y que la
matriz de la métrica Riemanniana en x ∈ Rm es G(x). Dados p y q puntos del
espacio euclı́deo de entrada, la distancia geodésica entre ellos vendrá dada
28
CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO.
entonces por:
Z
dgeodésica (p, q) = Í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 competirán por ser la neurona ganadora o BMU usando
para ello su distancia geodésica a la entrada. Las ecuaciones de aprendizaje
son similares a las clásicas de Kohonen (Sección 1.2), pero los vectores de
pesos de las neuronas se moverán hacia la entrada siguiendo las geodésicas
del espacio. Es esto último lo que distingue a este mapa auto-organizado de
los desarrollados hasta ahora (ver la Variante 1.3.4 en la Sección 1.4).
Un elemento clave para entender la métrica Riemanniana que usamos es
que, siguiendo la Variante 1.4.3, la geodésica entre dos puntos del espacio de
entrada intentará evitar las zonas de baja densidad. Esto lo conseguiremos
definiendo la matriz de la mé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 isótropo, es decir que la longitud de un
vector no depende de su dirección. Má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
CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO.
3.1.
Construcció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 dará una densidad continua que se
ajusta lo más posible a estos datos. No hay que confundir estos datos con los
M datos de entrada que se presentará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 López Rubio y Juan Miguel Ortiz de Lazcano Lobato.
En esta sección explicamos a grandes rasgos cómo funciona dicho algoritmo,
para una descripción detallada se remite al lector al citado trabajo.
Dicho algoritmo es un método de estimación de la función de densidad de
probabilidad de una distribución desconocida continua a partir de una cantidad finita de muestras de dicha distribución. La presente solución genera
como estimación una suma de distribuciones normales o Gaussianas multidimensionales. Las medias y demás pará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 (má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 recibirá contribuciones de los entornos circundantes de manera inversamente proporcional a la distancia a estos, con
lo que la información de todos ellos queda fusionada y suavizada a la
vez.
Cada cluster creado tendrá 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
distribución Gaussiana para cada cluster. En dicha construcción es de destacar que:
30
CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO.
La dimensionalidad o número de direcciones principales de dicha distribución Gaussiana se ajusta a la información del cluster, reflejando
la dimensión de la variedad subyacente a los datos. Esto se consigue
reteniendo sólo parte de los autovalores y autovectores de la matriz de
covarianza del cluster. La cantidad de autovalores a preservar se controla mediante un parámetro α ∈ [0, 1] que especifica que proporción
de la traza de dicha matriz deben sumar los autovalores retenidos.
Para las direcciones no conservadas se hace una estimación de la varianza en estas direcciones especificando un nivel de ruido. Este nivel
se controla con un parámetro γ ∈ [0, 1]. En general cuanto mayor sea
α menor deberá ser γ y viceversa. Si α es próximo a 1 conservaremos
casi todas las direcciones principales y en el resto habrá que añadir
poco ruido. Si α es próximo a 0 conservaremos muy pocas direcciones
y habrá que añadir más ruido en el resto de direcciones.
El presente procedimiento tiene las siguientes ventajas respecto a otros
métodos de estimación de función de densidad de probabilidad anteriores:
Cada distribución normal tiene sus propios parámetros.
Existe un proceso de suavizado al pasar de los entornos a los clusters.
Para una comparativa detallada de este método con otros métodos de
estimación de la función de densidad de probabilidad ver [14, Sección 5]. A
la densidad calculada por este mé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 método de estimación de la densidad explicado. Esta es la distribución desconocida.
31
CAPÍ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 función de densidad computados por el algoritmo. Los pará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
Construcción del grafo de distancias.
Con el objetivo de dotar al espacio euclı́deo de entrada Rm de geodésicas
necesitaremos introducir un grafo con pesos sobre el cual se computará el
camino más corto o geodésica usando el algoritmo de Floyd (ver Sección 1.3
y Figura 1.11).
Como vértices de este grafo tomaremos los clusters calculados por el algoritmo descrito en la Sección 3.1. El peso de la arista entre los clusters en
posiciones p y q será la longitud en la métrica Riemanniana del segmento
rectilı́neo entre p y q.
Recordemos que la métrica Riemanniana que estamos considerando es
exactamente G(x) = d21(x) In , para x ∈ Rm , y donde d(x) es la densidad
32
CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO.
continua calculada en la Sección 3.1. Sean p y q las posiciones de dos clusters
y γ : [0, 1] → R la parametrización del segmento rectilı́neo de p a q:
γ(t) = p + t(q − p).
La longitud de este segmento en nuestra mé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 número de segmentos en que dividimos el
segmento q − p, y que controla la precisión de la integración.
Una vez que sabemos como calcular el peso de una arista y que sabemos que el conjunto de vértices del grafo está formado exactamente por los
clusters calculados en la Sección 3.1 hay que decidir qué aristas incluir y
qué aristas no. Con este fin, para cada cluster c, se incluyen las aristas de c
a los clusters más cercanos. Este número de clusters que se conectan al cluster c es un número fijo que denotamos N umV ecinosGraf o. La noción de
cercanı́a aquı́ no es distancia euclı́dea. En su lugar, ya que el cluster c tiene
una distribución Gaussiana asociada, se evalúa esta distribución en el resto
33
CAPÍ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 geodé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 distribución normal asociada y los dos clusters
más cercanos (N umV ecinosGraf o = 2, en verde) según esta distribución
normal, los cuales no coinciden con los dos clusters más cercanos en distancia euclı́dea.
El número N umV ecinosGraf o es crı́tico. Como muestra el siguiente
ejemplo un número bajo puede resultar insuficiente para mantener la conexión de la densidad original y un número muy alto puede dar lugar a
aristas “erróneas”.
34
CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO.
Ejemplo 3.2.1. En la siguiente figura mostramos una densidad a aproximar ası́ como la reconstrucción a partir de 100 muestras mediante el método
explicado en la Secció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
CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO.
Se observan aristas “erróneas” que se salen de la nube de densidad en la
última figura abajo a la derecha. Para evitar estos problemas en el caso general se ensayaron los siguientes métodos en la elecció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 despué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 despué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 despué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 comprobó que estos métodos no proporcionan ventaja alguna en todos los casos y que la clave es seleccionar el valor N umV ecinosGraf o
correctamente según la aplicación. Nótese que los cálculos se hacen con
2 · N umV ecinosGraf o clusters y no todos lo clusters por razones de tiempo
de cómputo.
3.3.
Construcción de las geodésicas y la distancia geodésica.
Una vez que hemos construido el grafo de la Sección 3.2 estamos preparados para la construcción de las geodésicas y las distancias geodésicas. Dados
dos puntos p y q del espacio de entrada Rm empezaremos determinando la
36
CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO.
geodésica de p a q. La distancia geodésica entre p y q será la longitud de
dicha geodésica.
Si ambos puntos p y q fueran vértices del grafo entonces la geodésica serı́a
directamente el camino más corto en el grafo determinado, por ejemplo, por
el algoritmo de Floyd. En general ni p ni q serán vértices del grafo y un primer
escollo es determinar el vértice de entrada al grafo y el vértice de salida del
grafo. Es decir, la geodésica de p a q consistirá de un segmento rectilı́neo
desde p a un vértice del grafo, de un camino minimizante en el grafo y de un
segmento rectilı́neo desde un vértice del grafo a q.
Para calcular los vértices de entrada y salida replicaremos lo hecho en
la Sección 3.2 para calcular los vecinos de un cluster dado del grafo. Es decir, vamos a seleccionar un número determinado de clusters o vértices del
grafo vecinos al punto p y el mismo número de clusters vecinos al punto q.
Este nú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 análogamente para q (nótese que ahora p y q no tienen
distribuciones asociadas).
Una vez tenemos los vértices más cercanos a p y a q calculamos, para
cada vértice vecino a p, cp , y para cada vé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
Ecuación (3.3). La longitud de cada arista del grafo que se atraviesa se calcula
de la misma forma y de hecho ya se almacenó como el peso de dicha arista.
La longitud total del camino es la suma de todas estas longitudes.
La geodésica de p a q se obtiene eligiendo entre los vecinos de p y los
vecinos de q los vé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 gráficamente como sigue:
37
CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO.
En la figura se muestra el grafo con los vértices como clusters, ası́ como
las aristas. Cada vértices tiene 4 vecinos, es decir, N umV ecinosGraf o = 4.
Se muestran los vecinos má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 último, se muestra en trazo grueso la geodésica de p
a q.
Ejemplo 3.3.1. La siguiente figura muestra una densidad a aproximar y su
aproximació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 geodésica (trazo negro) y los
vecinos a los puntos de inicio y fin de la geodésica (puntos negros). Los ve38
CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO.
cinos seleccionados como entrada y salida al grafo de clusters está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 versión anterior del algoritmo elegı́a únicamente el vértice más cercano a p y el vértice más cercano a q (según proximidad Gaussiana) y definı́a
la geodésica pasando a través del camino minimizante en el grafo a través de
estos vértices. El método explicado arriba da resultados notablemente mejores. De nuevo, al igual que en la construcción del grafo, al determinar los
vértices de entrada y salida al grafo estamos aproximando a escala local la
distancia geodésica global y mientras que el método descrito arriba tiene una
componente global el descrito al principio de este párrafo no la tiene.
Otra versión del algoritmo para geodésicas que implementé usaba como
vértices del grafo una retı́cula ortogonal en vez de los clusters dados por el
algoritmo que reconstruye la densidad de la Sección 3.2, y conectaba cada
vértice a sus vértices inmediatamente adyacentes. Por ejemplo, en 2 dimensiones los vecinos estarı́an dispuestos ası́:
39
CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO.
Ejemplo 3.3.2. La siguiente figura muestra una densidad a aproximar, su
aproximación mediante 100 muestras y la retı́cula o vértices del grafo superpuestos (cruces verdes). Además se muestra una geodé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 versión no se ha seguido desarrollando por el alto coste computacional en dimensiones superiores. En m dimensiones y con tamaño de un lado
del retı́culo L tenemos un total de Lm vértices. El algoritmo de Floyd tiene
una complejidad O(|V |3 ), donde |V | es el número de vé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 Sección 3.2 genera como mucho un número
de clusters N umClusters, y por tanto de vértices, igual al número de muestras de entrada N umM uestras. Ası́ que la complejidad es O(|N umM uestras|3 )
donde N umM uestras es el número de muestras. Esto es mucho más manejable que O(L3m ) en las aplicaciones.
40
CAPÍTULO 3. UN MAPA AUTO-ORGANIZADO GENERALIZADO.
Ejemplo 3.3.3. En una aplicación de segmentación a imá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 pequeña escala.
Para terminar esta sección hacemos una pequeña digresión sobre las componentes conexas del grafo y las geodésicas. Supongamos que tenemos un
grafo de distancias que tiene dos componentes conexas C1 y C2 (en té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 geodésica hasta la entrada estarán todos en la componente C1 .
Ası́ mismo, si la entrada está suficientemente cerca de C2 , los N umV ecinos
clusters de la entrada pertenecerán a la componente C2 .
Resulta entonces que el algoritmo de Floyd dará distancia infinita para
estas N umV ecinos × N umV ecinos combinaciones de clusters, ya que están
en componentes distintas del grafo de distancias. Una forma de remediarlo es,
en general, comparar las N umV ecinos × N umV ecinos distancias geodé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 (Ecuación (3.3)). Ası́, en el
caso que tratamos de las dos componentes, aunque la distancia geodé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 añadimos la solución con el segmento rectilı́neo permitiremos que
las neuronas sean “capturadas” por la componente del grafo más próxima,
lo cual puede ser interesante según la aplicación que se esté desarrollando.
41
CAPÍ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) Construcción de la densidad continua a partir de los N umM uestras
datos de entrada en el espacio de entrada Rm (Sección 3.1).
(b) Construcción del grafo de distancias con N umClusters clusters (Sección
3.2).
(c) Cálculo de la matriz de distancias mı́nimas entre clusters según el algoritmo de Floyd (Sección 3.3).
(d) Inicialización de los parámetros de la red σ0 , λ y η0 .
(e) Inicializació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 posición de un cluster elegido aleatoriamente. Cada iteración
t en (f) se subdivide en las siguientes subetapas:
(f.1) Cálculo de la geodésica y la distancia geodésica entre la entrada x(t) y
el vector de pesos de cada neurona ni (t).
(f.2) Selección de la neurona ganadora o BMU como la que minimiza su
distancia geodésica hasta la entrada.
(f.3) Cálculo de los coeficientes de aprendizaje γ(t, x(t), i) según lo explicado
en la Secció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 geodésica hasta la
entrada en una cantidad que es el γ(t, x(t), i) por ciento de su distancia
geodésica hasta la entrada.
42
Capı́tulo 4
Aplicación a la segmentación de
imágenes.
En este capı́tulo explicamos los detalles de implementación de un mapa auto-organizado generalizado (Capı́tulo 3) aplicado a la segmentación de
imágenes en color.
La segmentación de imágenes en color trata de seleccionar los colores
má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 análisis de imagen por
ordenador. En esta sección usaremos neurona y prototipo indistintamente.
De forma condensada, un número de muestras M se toma de la imagen
y se sitúan en algú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 más cercano. Tanto la
percepción visual de la imagen reconstruida como el error cuadrá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 también tridimensional (m = 3)
y tiene ventajas en cuanto a la percepció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
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
Sólo al final, durante la reconstrucción de la imagen original, se vuelve al
espacio RGB. Con más detalle, el funcionamiento de la red es como sigue:
(A) Se carga una imagen en color en algún formato está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
está descrito en la Sección 3.4 en el espacio de color CIELU V . Si se
requieren más muestras para presentar a la red estas se irán generando
aleatoriamente en cada iteración.
(E) Los N prototipos obtenidos se usan para reconstruir la imagen y calcular
el error cuadrático medio.
44
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
Ejemplo 4.0.1. En este ejemplo mostramos la ejecución sobre una imagen
de tamaño 128 × 128. Se usan 100 muestras (N umM uestras = 100) y 16
neuronas o prototipos (N = 16). También ponemos N umV ecinosGraf o = 5,
N umV ecinos = 5 y η0 = 1. Los parámetros del algoritmo de reconstrucción
de la densidad (Secció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 distribución final de las 16 neuronas (en rojo) en el espacio CIELU V .
A la derecha, reconstrucción de la imagen original usando los prototipos.
Como error cuadrático medio se obtuvo M SE = 0,045208.
En la siguiente sección comentamos las distintas funciones diseñadas en
MATLAB y C y que parte del algoritmo implementan. En la Sección 4.2 se
45
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
realiza un estudio sobre la dependencia del aprendizaje de los parámetros de
la red. En la Sección 4.3 se ha probado el nuevo mapa auto-organizado generalizado en imágenes de bancos estándares y se han comparado los resultados
con los obtenidos en otros trabajos de ı́ndole similar.
46
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
4.1.
Implementación MATLAB.
El mapa auto-organizado se ha implementado en MATLAB usando para
ellos scripts MATLAB y también código en C (funciones MEX) para optimizar en velocidad. Las funciones MATLAB construidas son las siguientes.
También especificamos que acciones de las listadas en la Sección 3.4 o en la
introducción a este capı́tulo se implementa en el código de cada función.
Nombre función
Descripció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 geodésica en una proporción dada
Geodesica
Calcula la geodésica entre dos (f.1)
puntos
IniciaRed
Inicializa los parámetros de la red (d)
IntegraInversoDensidad
Aproximación a la integral de
lı́nea sobre un segmento del inverso de la densidad (Ecuación (3.3))
MatrizDistanciasLineales Crea el grafo de distancias dados (b)
los clusters
MueveNeuronas
Mueve las neuronas según las re- (f.2) (f.3)
glas de aprendizaje
Reconstruye
Calcula el error cuadrá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 vértices
47
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
Además, se usan las siguientes funciones MATLAB. Las 3 primeras me
fueron proporcionadas por el profesor Ezequiel López Rubio y constituyen la
implementación del trabajo [14]. La función colorspace fue creada por Pascal Getreuer (ColorSpace, Copyright (c) 2009, Pascal Getreuer). La última
función forma parte de la librerı́a de grafos para MATLAB creada por David
Gleich (MatlabBGL, Copyright (c) 2006-2007, David Gleich).
Nombre función
Descripción
Implementa
TrainSmoothParzenWindows
Construye la densidad continua a (a)
partir de las muestras
TestSmoothParzen
Evalúa la densidad continua en
un punto
GaussianaLocalSmoothParzen
Evalúa la distribución Gaussiana
de un cluster en un punto
colorspace
Conversió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 qué funciones tienen una versión MEX. El criterio para elegir qué 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 ejecución.
48
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
Nombre funció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
Prácticamente el 100 % del tiempo de ejecución de lo reparten entres las
5 funciones con versiones MEX de la tabla anterior. La función de cálculo
49
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
de geodésicas, Geodesica, está optimizada de forma que se almacenan los
N umV ecinos clusters de cada neurona de una iteración a otra. Ası́, si la
neurona no se desplaza no se recalculan sus clusters vecinos en la siguiente
iteración. Como el proceso de aprendizaje de la red tiende a mover las neuronas menos cuanto más iteraciones se realizan esto resulta en una aceleración
del aprendizaje en su parte final.
En la versión final los N umV ecinos elegidos para construir geodésicas
se seleccionan como aquellos que minimizan la distancia euclı́dea y no como aquellos que minimizan la distancia Gaussiana (ver Sección 3.3). Ası́ se
consigue mayor velocidad y más estabilidad en los resultados. El segmento rectilı́neo entre una muestra y la entrada se elige como geodésica si las
geodésicas a través del grafo dan todas distancia infinita (ver tres últimos
párrafos de la citada sección).
4.2.
Dependencia de los parámetros.
Durante el Capı́tulo 3 se estableció que el algoritmo de aprendizaje del
mapa auto-organizado generalizado que estamos usando depende de los siguientes parámetros:
1. Parámetros α y γ, que determinan respectivamente la proporción de
autovalores a conservar y el nivel de ruido en la construcción de la
densidad continua.
2. Parámetro N umM uestras y N umClusters usados en la construcción
de la densidad continua.
3. Parámetro N umV ecinosGraf o, que determinan el número de clusters
vecinos a un cluster dado en la construcción del grafo de distancias, y
parámetro N umV ecinos, que determina el número de clusters vecinos a
la entrada o a una neurona en la construcción de geodésicas y distancias
geodésicas.
4. Parámetros σ0 , η0 , que determinan respectivamente el entorno inicial y
la razón de aprendizaje inicial en las ecuaciones de aprendizaje.
50
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
En esta sección describimos un estudio realizado para estudiar la calidad
del aprendizaje del mapa auto-organizado generalizado en función de los distintos parámetros. Las pruebas se han realizado sobre la imagen del mandril
del Ejemplo 4.0.1 en tamaño 128 × 128 con N umM uestras = 100 muestras,
N umClusters = 100 clusters y N umN euronas = 10 neuronas (salvo cuando
son estos parámetros los que se están estudiando claro está).
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 inglés average negative log likelihood. Esta cantidad AN LL
cuantifica cómo de bien aproxima la densidad continua a las muestras, y
la optimización trata de minimizar su valor. La siguiente grá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
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
Hemos encontrado que los valores óptimos para α y γ son 0,1 y 0,14
respectivamente.
Debido al paso intermedio de la construcción de la densidad continua
hay otros parámetros que estudiar en nuestro algoritmo. En particular, el
algoritmo depende del número de muestras N umM uestras tomadas para
construir la densidad y también del número de clusters N umClusters que
conforman la densidad. La siguiente grá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 cuadrático medio M SE disminuye conforme aumentan el número de muestras N umM uestras o el número
de clusters N umClusters. En la siguiente sección hacemos un estudio más
detallado sobre la dependencia del aprendizaje de estos parámetros.
Los parámetros N umV ecinosGraf o y N umV ecinos también los hemos
estudiado al mismo tiempo. Dejando el resto de valores fijos hemos ejecutado
el algoritmo de aprendizaje y evaluado el error cuadrático medio barriendo los
valores para N umV ecinosGraf o y N umV ecinos entre 1 y 20. Los parámetros α y γ se fijaron en los ó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
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁ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 cómputo.
La cantidad de parámetros de los que depende nuestro modelo hace que
su optimización sea una tarea a acometer seria. Para terminar esta sección
notemos tambié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 continuación se siguen presentando a la
red dichos clusters de manera cı́clica hasta alcanzar N umM axIteraciones.
Hemos acompañado este método de funciones lineales a trozos para las funciones σ y η:
53
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁ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: Función σ a la izquierda y función η a la derecha para
N umClusters = 100 y N umM axIteraciones = 200.
Estudiando el error cuadrático medio M SE para distintos valores máximo
y residual de σ y distintos valores del segundo máximo de η y residual de η
(el primer máximo de η lo hemos fijado en 1) hemos obtenido óptimos con
valor máximo de σ = 0,3, valor residual de σ = 0,1, segundo valor máximo
de η = 0,6 y valor residual de η = 0,25. Este algoritmo de aprendizaje de dos
fases junto con los parámetros óptimos comentados son los que usaremos en
la siguiente sección.
54
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
4.3.
Resultados.
La calidad de la reconstrucción de la imagen se suele evaluar mediante la
razón señal-ruido pico, PSNR por sus siglas en inglés, definida como sigue:
3
),
(4.2)
M SE
donde el error cuadrático medio fue introducido en la Ecuació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 nó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 más profundidad la dependencia del P SN R con respecto a N umM uestras, N umClusters
y N umM axIteraciones con el método de aprendizaje de dos fases descrito
en la secció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 tamañ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
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁ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 número de clusters. Además, esta mejora es mayor cuanto
má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 representación grá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
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
La siguientes tablas recopilan informació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 número de muestras produce una mejora
en el aprendizaje en términos de P SN R y esta mejora no aumenta tan acusadamente como en el caso anterior al incrementar el número de neuronas.
Es de destacar sin embargo que el decremento de las desviaciones tı́picas es
mucho más patente en este caso que en el anterior. Representamos a continuación los valores medios P SN R:
57
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁ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
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁ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 número de neuronas, la mejora en el aprendizaje
en términos de P SN R que produce el aumento del número máximo de iteraciones es mı́nimo. Esto no deberı́a sorprender ya que, como se describió en la
sección anterior, el método de aprendizaje que estamos usando presenta cı́clicamente los clusters a la red. Los valores medios P SN R tienen la siguiente
representación:
26
25
24
23
22
21
20
19
18
5000
256
2000
128
1000
64
32
500
16
NjumMaxIteraciones
200
6
NumNeuronas
En conclusión, deducimos que es el número de clusters la variable cuyo
aumento produce mayores mejoras en el aprendizaje, mientras que el incremento de el número de muestras o el número máximo de iteraciones producen
mejoras sólo marginales.
59
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
El estudio comparativo lo dividimos en dos partes. En la primera ejecutaremos el algoritmo de aprendizaje de dos fases de la Sección 4.2 hasta
alcanzar N umM axIteraciones. En la segunda parte añadiremos un criterio
de convergencia a dicho algoritmo.
60
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
4.3.1.
Algoritmo de aprendizaje de dos fases.
La primera parte la realizaremos sobre las siguientes imá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 Sección 1.4. De [21, Fig. 8] tomamos los valores P SN R (redondeados)
para la segmentación de Mandrill, Lena y Peppers en tamaño 128 × 128 y
con un 10 % de razón de muestreo, es decir, tomando unas 1638 muestras de
la imagen, para distintos número de neuronas:
Imagen
Mé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 imágenes 128 × 128.
Se observa que los valores P SN R para FS-SOM decrecen conforme aumenta el número de neuronas. Este comportamiento anormal cesa al aumentar el número de iteraciones [5, Table I] o el tamaño de la imagen [21, Fig.
8]. Hemos ejecutado nuestro mapa auto-organizado generalizado con 1638
muestras, 200 clusters, 400 iteraciones y diversos números de neuronas sobre
61
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
imágenes en tamaño 128 × 128 para obtener los siguientes resultados, dónde
las medidas estadı́sticas se realizaron sobre muestras de 10 ejecuciones:
Imagen
PSNR
NumNeuronas
16
32
Media
23.14 24.19
Mandrill
Desviación tı́pica 0.33 0.46
Media
27.19 29.61
Lena
Desviación tı́pica 0.89 0.31
Media
24.84 26.03
Peppers
Desviació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 imá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 número de neuronas. Es de destacar que nuestro algoritmo sólo está presentando a la red 200 muestras distintas mientras que FS-SOM y SA-SOM
están presentando a la red más de 1600 muestras.
En la siguiente gráfica podemos observar los valores P SN R de las dos
últimas tablas:
62
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁ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 imágenes Mandrill (en azul), Lena
(en rojo) y Peppers (en verde) y los tres métodos FS-SOM (lı́nea continua),
SA-SOM (lı́nea rayada) y nuestro mapa auto-organizado generalizado (lı́nea
punteada).
Las siguientes imágenes muestran reconstrucciones RGB tı́picas de las
imágenes Mandrill, Lena y Peppers en tamaño 128 × 128 para 16, 64 y 256
neuronas y los demás parámetros iguales a los usados en la tabla anterior:
Figura 4.5: Reconstrucción de Mandrill con 16, 64 y 256 neuronas.
63
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
Figura 4.6: Reconstrucción de Lena con 16, 64 y 256 neuronas.
Figura 4.7: Reconstrucción de Peppers con 16, 64 y 256 neuronas.
La siguiente comparación será 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 información sobre
segmentación con número de neuronas bajo para las imágenes Mandrill, Lena
y Peppers en tamañ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 imágenes 512 × 512.
Usando nuestro mapa auto-organizado hemos obtenido las siguientes medidas estadı́sticas para valores P SN R sobre 10 ejecuciones:
64
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
Imagen
Mandrill
Lena
Peppers
Neuronas NumMaxIteraciones
6
271
4
219
6
330
Media Desviación tı́pica
19.96
0.29
22.6
0.82
20.75
0.9
Cuadro 4.10: Valores de P SN R sobre imá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 después en
aprendizaje clásico, tal y como se describió en la sección anterior. Los valores
P SN R obtenidos son inferiores a los de LARFSOM. Reduciendo el nú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 Desviación tı́pica
20.01
0.53
22.67
0.52
20.72
0.75
Cuadro 4.11: Valores de P SN R sobre imá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 prácticamente idénticos a los de la tabla anterior. Esto
demuestra, por un lado, un excelente comportamiento de nuestro mapa autoorganizado para número de neuronas, muestras e iteraciones bajos. Por otro
lado, esto induce a creer que mejorando el método de aprendizaje los valores medios de P SN R obtenidos en el Cuadro 4.10 pueden incrementarse ya
que aparentemente hay más información que puede extraerse de las muestras
usadas.
65
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
Figura 4.8: Reconstrucció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 imágenes Flowers, Sailboat, Pens y Yacht, que son de tamaños 500×362, 512×512,
512 × 480 y 512 × 480 respectivamente:
66
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁGENES.
La siguiente tabla [1, Table 5, Table 6, Table 7, Table 8] muestra valores
P SN R sobre estas imágenes para FS-SOM, LARFSOM y el algoritmo clásico
de mapa auto-organizado SOM para segmentación de imágenes.
Imagen
Mé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 idéntico al explicado en la
Sección 4.2 salvo que en la segunda fase, es decir, en la fase con aprendizaje
no competitivo puro, hemos añ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
CAPÍTULO 4. APLICACIÓN A LA SEGMENTACIÓN DE IMÁ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 (desviación) (desviació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 también a los de LARFSOM. Recordemos de nuevo que estos resultados se consiguen presentado a la red sólo 100 muestras
distintas (N umClusters = 100 clusters). Las siguientes figuras muestran
reconstrucciones con 16 prototipos:
68
Capı́tulo 5
Discusió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 segmentación de imágenes en color.
Posteriormente hemos introducido el concepto de mapa auto-organizado
generalizado, cuya principal virtud sea quizá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 clásico
de mapa auto-organizado. Creemos que este concepto podrı́a dar a nuevas
desarrollos o variaciones de mapas auto-organizados.
Como aplicación hemos diseñado un mapa auto-organizado generalizado
orientado a la segmentación de imágenes en color. La diferencia con un mapa
clásico radica fundamentalmente en que el movimiento de las neuronas se
realiza a lo largo de las geodésicas de cierta métrica. Esta métrica depende de
una densidad continua calculada a partir de las muestras. La implementación
se ha llevado a cabo en MATLAB y C.
Se ha probado el mapa sobre imágenes estándares. Los valores de P SN R
obtenidos se encuentran entre aquellos obtenidos por otros mapas auto-organizados recientes orientados a la segmentación de imágenes en color y llegan
69
CAPÍTULO 5. DISCUSIÓN Y CONCLUSIONES.
a superar a los mejores de estos métodos en algunas de las pruebas.
Resaltemos aquı́ que los mé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 elección de la BMU.
Sin embargo, ya que nuestro mapa auto-organizado modifica un mapa autoorganizado clásico a un nivel profundo, a saber, en el có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 más competitivo para número de iteraciones
bajo, mientras que para número de iteraciones alto los valores P SN R divergen más de los otros métodos estudiados. Esto no es de extrañar ya que en
el mé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
información de la imagen. Un número de muestras y de clusters equiparable
a un número de iteraciones grande (del orden de 104 ) es computacionalmente
intratable.
Veamos además por qué el presentar una muestra en vez de un cluster a la
red puede distorsionar el aprendizaje. Para ello nó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 distribución tı́pica del inverso de la densidad entre
un cluster y una muestra será como se muestra en la siguiente figura:
Si una neurona cercana al cluster ha de moverse en dirección a la muestra una pequeña cantidad, digamos un 5 %, esto puede producir un gran
desplazamiento en distancia euclı́dea:
70
CAPÍTULO 5. DISCUSIÓN Y CONCLUSIONES.
Esta distorsió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 opción aquı́ serı́a aprender siempre mediante
clusters pero ir calculando nuevas densidades a medida que se toman nuevas muestras de la imagen. Algú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.
Además, un estudio más pormenorizado de la influencia de los numerosos
parámetros de la red en los valores de salida P SN R serı́a conveniente. Estos
parámetros incluyen el número de iteraciones, el número de clusters, número
de vecinos, número de vecinos del grafo, parámetros de construcción de la
densidad y las funciones σ y η de aprendizaje. Posiblemente distintos tipos de
imágenes requieran distintos conjuntos de parámetros. Igualmente, distintos
valores P SN R objetivo requerirán métodos de aprendizaje distintos.
Tampoco deberı́a obviarse un estudio sistemático del tiempo de aprendizaje, el cual es otro baremo para comparar este trabajo con otros de la
misma área. Debido a la considerable mayor carga computacional del cálculo
de una geodésica frente al cálculo de un segmento rectilı́neo aquı́ se deberı́a
esperar estar en seria desventaja frente a otros métodos.
En otro orden, una versión con una malla dos dimensional para las neuronas deberı́a producir mejores resultados en términos de P SN R.
Un problema abierto de carácter más teórico pero que merece la pena considerar es el estudio de condiciones para que la aproximación a las geodésicas
71
CAPÍTULO 5. DISCUSIÓN Y CONCLUSIONES.
y a la distancia geodésica consideradas aquı́ convergen a las geodésicas y a las
distancias geodésicas teóricas respectivamente. Esto darı́a una base más solida al algoritmo en sı́. En el trabajo [2] se presentan dichos criterios para un
algoritmo relacionado de reducción de la dimensión conocido como Isomap.
Con referencia a los valores P SN R para segmentación de imágenes en la
bibliografı́a es interesante que, aunque frecuentemente se muestran valores
para distintos tamaños de imágenes (como 128 × 128, 256 × 256 y 512 × 512),
los valores P SN R obtenidos deberı́an ser, al menos teóricamente, iguales. Si
tomamos M muestras de una imagen en tamañ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 tamañ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 pequeña da lugar a λ2 pı́xeles en la imagen
grande. Cancelando los dos términos λ2 notamos que esto es exactamente el
valor M SE para la imagen pequeña.
Podemos observar este hecho en [21, Table 1] comparando los valores
P SN R de tamaño de imagen 512 × 512 y razón de muestreo 0,1 con los
valores P SN R de tamaño de imagen 256 × 256 y razó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 tamaños 256×256 y 128×128
de la misma tabla y también en la gráfica de [21, Fig. 8].
También serı́a interesante investigar el mı́nimo global de M SE para una
imagen dada y un número de neuronas dado y compararlo con los valores
M SE en la bibliografı́a. Para ello podrı́a ensayarse una aproximación me72
CAPÍTULO 5. DISCUSIÓN Y CONCLUSIONES.
diante posiciones de las neuronas en una malla de vértices tridimensional.
Esto serı́a sin duda computacionalmente muy costoso, pero arrojarı́a cierta
luz sobre la calidad de los métodos SOM en general. Es claro que tal mı́nimo global debe existir ya que los valores de las prototipos o neuronas están
acotados a un cubo del tipo [0, 255]3 o [0, 1]3 y M SE es función continua de
las posiciones de las neuronas (a pesar de que la función BM U no es funció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 vértices de la malla suficientemente pequeñ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 pequeño tal que la distancia de cada pı́xel xi a una neurona que no
esté a la misma distancia que la neurona BM U (xi ) sea mayor que la distancia
a BM U (xi ) más δ, en fó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 elección de δ es posible por la
finitud de los conjuntos involucrados. Tomemos ahora una malla de radio δ
y vértices de la malla n1 , . . . , nN a distancias menores que 2δ de nb1 , . . . , nc
N
respectivamente. Por la elección de δ, si la neurona BM U para el pı́xel xi
era el prototipo nbj ahora tendremos también que la neurona más cercana es
nj . Considerando δ más pequeñ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
Apéndice A
Geometrı́a y Topologı́a.
En esta sección introducimos varias nociones matemáticas que se usan en
el trabajo. Para una versión más detallada se remite al lector a [4]. Empezamos con la noción de espacio métrico.
Definición A.0.1. Un espacio métrico es un conjunto M no vacı́o y una
funció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 función d es la métrica del espacio.
Por ejemplo, el espacio euclı́deo Rm es un espacio métrico con la métrica
euclı́dea
d((x1 , . . . , xm ), (y1 , . . . , ym )) =
p
(x1 − y1 )2 + . . . + (xm − ym )2 .
(A.1)
Si M es un espacio métrico con mé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)
APÉNDICE A. GEOMETRÍA Y TOPOLOGÍA.
En el espacio métrico R2 las bolas corresponden a discos rellenos sin la circunferencia que lo delimitan, y en el espacio métrico R3 corresponden a esferas
macizas sin la superficie esférica que lo delimitan.
Un subconjunto U de un espacio métrico M se denomina abierto si se
puede escribir como una unión, posiblemente infinita, de bolas. Esto es es
equivalente a que para cualquier punto x ∈ U existe un radio r > 0 suficientemente pequeño tal que B(x, r) ⊆ U . Es decir, que si un punto está en U
también lo está una pequeña bola alrededor de este punto.
Por ejemplo, el subconjunto (0, 1) = {x ∈ R|0 < x < 1} es abierto en el
espacio métrico R. El conjunto [0, 1] = {x ∈ R|0 ≤ x ≤ 1} no lo es porque
la condición falla en los puntos 0 y 1. Un disco en R2 es abierto sólo si no
contiene ningún punto de la circunferencia que lo delimita. Una esfera en R3
es abierto sólo si no contiene ningún punto de la superficie esférica que lo
delimita.
Cualquier subconjunto de un espacio métrico M se convierte en un espacio
métrico sin más que restringir la mé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 métricos al heredar la métrica euclı́dea de
R3 .
Pasamos ahora a la noción de variedad diferenciable de dimensión m.
Es este un tipo especial de espacio métrico que localmente es indistinguible
de Rm . Má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 biyección ϕ de U a un abierto de Rm . A esta funció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 función ϕ es la función coordenada porque asigna
m coordenadas a cada punto del abierto U de M .
¿Qué 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
APÉNDICE A. GEOMETRÍA Y TOPOLOGÍA.
A esta aplicación se le llama función de transición y convierte las m coordenadas que asigna ϕ a un punto de U ∩ V a las m coordenadas que les asigna
ψ.
Definición A.0.2. Una variedad diferenciable es un espacio métrico M con
una familia de entornos coordenados {Uα , ϕα } tales que
cada punto de M está en al menos un subconjunto Uα y
para cualesquiera α y β con Uα ∩ Uβ 6= ∅ la función de transición entre
Uα , ϕα y Uβ , ϕβ es infinitamente diferenciable.
Para introducir la noción de geodésica necesitamos primero introducir el
concepto de curva en una variedad diferenciable M .
Definición A.0.3. Sea M una variedad diferenciable. Una curva en M es
una aplicació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
función
γ
ϕ
γ −1 (U ) → U → Rm
es continua y diferenciable a trozos.
Ası́ que una curva en M es simplemente una funció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 relació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 dimensión m, y la estructura
de espacio vectorial de Tx M queda determinada asociando a cada clase de
76
APÉNDICE A. GEOMETRÍA Y TOPOLOGÍ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 esférica ası́ como como un espacio
tangente gené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 añadir a nuestra variedad diferenciable una manera de medir la longitud
de los vectores de los espacios tangentes de M . Como veremos esto nos permitirá también medir la longitud de una curva en M . Recordemos que una
forma bilineal definida positiva en un espacio vectorial V es una aplicació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) (simétrica),
Φ(v, v) ≥ 0 y Φ(v, v) = 0 ⇔ v = 0 (definida positiva).
Si V tiene dimensión m y fijamos una base en V una forma bilineal
simétrica definida positiva está determinada y determina una matriz m × m.
Definición A.0.4. Una variedad Riemanniana es una variedad diferenciable
con una forma bilineal simétrica definida positiva G(x) en el espacio tangente
Tx M para cada punto x ∈ M . Al tomar cualquier entorno coordenado U , ϕ
77
APÉNDICE A. GEOMETRÍA Y TOPOLOGÍ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 métrica Riemanniana de
M.
Dada una variedad Riemanniana M con métrica Riemanniana G el tamaño de un vector v ∈ Tx M está 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 tamañ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
simétrica definida positiva tiene asociada la matriz identidad Im en coordenadas canónicas (x1 , . . . , xm ) y el tamañ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 geodésica, mediante
Z bp
dgeodésica (x, y) = Í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 Ecuación (A.5) y mediante el uso de cálculo de variaciones
se llegan a las ecuaciones geodésicas. Estas ecuaciones son ecuaciones dife2
i
renciales ordinarias en dγ
y ddtγ2i cuyas soluciones proporcionan (localmente)
dt
78
APÉNDICE A. GEOMETRÍA Y TOPOLOGÍA.
las geodésicas. Se escriben en té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 Ecuación (A.5) produce una función
dgeodésica : M × M → R que satisface las propiedades de la Definición A.0.1,
es decir, dgeodésica es una métrica en M . Surge naturalmente la pregunta de
cual es la relación de esta nueva métrica con la métrica original d en M .
La respuesta es que ambas métricas son equivalentes. Esto quiere decir
que los conjuntos abierto que generan dgeodésica y d son los mismos, es decir,
que un conjunto se puede escribir como unión de dgeodésica -bolas si y sólo
si se puede escribir como unión de d-bolas. También equivale a que las dos
topologı́as inducidas por las métricas son iguales.
Como en la Ecuació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 ) = dgeodésica (x, y). A una tal curva la llamaremos
geodésica entre x e y. Sin embargo, en general, la existencia y unicidad de
tales curvas minimizantes no está asegurada. Hay variedades Riemannianas
donde no existen tales curvas minimizantes y variedades Riemannianas donde existe más de una. Se puede dar un ejemplo sencillo de esto último: en
la superficie esférica las geodésicas o curvas minimizantes son arcos de circunferencias máximas, es decir, de circunferencias contenidas en la superficie
esférica y en un plano que pasa por el centro de esta. Hay infinitas geodésicas
entre el polo norte y el polo sur.
La mé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 función densidad
reconstruida evaluada en el punto x ∈ Rm . Esta función es una suma de
distribuciones Gaussianas o normales con distintos parámetros y medias y
satisface
d(x) > 0 para todo x ∈ Rm y
79
APÉNDICE A. GEOMETRÍA Y TOPOLOGÍ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 habrá al menos una
geodésica en nuestras condiciones. Por otro lado, una densidad degenerada
con una única distribución Gaussiana simétrica es un ejemplo donde es fácil
encontrar dos puntos con más de una geodésica entre ellos.
80
Apéndice B
Glosario.
Algoritmo de Floyd: Dado un grafo con pesos el algoritmo de Floyd
permite hallar el camino entre dos vértices que minimiza la suma de los pesos
de las aristas incluidas en el camino (el camino más corto). Una sola ejecución
del algoritmo de Floyd genera dos matrices, una con las distancias mı́nimas
entre cada par de vértices, y otra con el próximo vértice a recorrer para cada
par de vértices. El camino más corto entre dos vértices se encuentra por recursión usando la segunda matriz. El algoritmo de Floyd es de complejidad
O(|V |3 ), donde |V | es el número de vértices del grafo.
Algoritmo de clustering k-means o “medias-k”: Es una té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
má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 aná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 términos
de una distancia.
81
APÉNDICE B. GLOSARIO.
Figura B.1: Conjunto de datos agrupados en 3 grupos. Los grupos están
coloreados para poder identificarlos.
Compresión de imágenes: Consiste en la aplicación de técnicas de
compresión de datos a la información de una imagen. Esta ı́ntimamente relacionada con la segmentación de imágenes en color ya que la segmentación
trata de encontrar patrones y regularidades en la imagen que a su vez pueden
usarse para comprimirla.
Cuantificación vectorial: La cuantificació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. Sólo la BMU se mueve hacia la entrada.
Esto equivale a hacer tender σ a 0 en la Ecuación (1.3), para conseguir la
siguiente funció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 cuantificación vectorial (o siendo má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
Comisión Internacional de la Iluminación (CIE) en 1976 a partir del espa82
APÉNDICE B. GLOSARIO.
cio de color CIE 1931 XY Z. Ambos intentan conseguir percepció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 percepción
uniforme (ver espacios de color CIELAB y CIELU V ).
Función MEX de MATLAB: MEX es la abreviatura de “MATLAB
executable”. Un fichero MEX es una librerı́a dinámica compilada a partir de
código fuente C, C + + o F ORT RAN y que se puede ejecutar en el entorno
MATLAB como una función más. La transferencia de datos entre la función
MEX y MATLAB y la ejecución de funciones MATLAB desde el fichero MEX
se hace gracias a una librerı́a MATLAB que se enlaza al código fuente. La
velocidad de ejecución suele ser entre 10 y 20 veces más rápida que la versión
equivalente con un script de MATLAB.
Segmentación de imágenes en color: En el campo de la visión artificial la segmentación de imá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 segmentación de imágenes en color en este trabajo siempre se refiere a agrupar los pı́xeles con respecto a su color creando
ası́ zonas de color homogé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., Svensé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
BIBLIOGRAFÍ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] López-Rubio E., Muñoz-Pérez J., Gómez-Ruiz J. A., Self-Organizing
Dynamic Graphs. Neural Process. Lett. 16, 2 (Oct. 2002), 93-109.
[14] Ló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] López-Rubio E., Ortiz-De-Lazcano-Lobato J. M., Vargas-Gonzá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
BIBLIOGRAFÍ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] Pöllä 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

Top subcategories

Top subcategories

Top subcategories

Top subcategories

Top subcategories

Top subcategories

Top subcategories

Download redes neuronales no supervisadas con topología din´amica para la