Embed Size (px)
Citation preview
El algoritmo de Lloyd y sus aplicaciones a la
discretización de superficies
porJ. Estrada-Sarlabous
(ICIMAF)
La solución computacional de problemas complejos frecuentemente se basa en generar representaciones discretas (mallas) que son óptimas con relación a la minimización de alguna función de costo
Este algoritmo surgió en el contexto de los métodos de agrupamiento o clustering, en particular asociado al famoso K-means
ecorative Mosaics SIGGRAPH 20012
Las mallas se suelen clasificar en estructuradas y no estructuradas, vamos a concentrarnos en esta charla en las últimas, explicando como el algoritmo de Lloyd puede ser utilizado para generar mallas triangulares, en cierto sentido óptimas
Clustering aglomerativo :
Para hallar el clustering óptimo se deben generar todos los
clusters posibles y comparar las medidas de sus errores.
Para conjuntos de datos grandes esto es computacionalmente
muy costoso!
Método k-means
Algoritmo para agrupar n objetos
en k<n particiones
- Asume que los atributos de los objetos
forman un espacio vectorial
Objetivo: minimizar la varianza intracluster total
Decorative Mosaics SIGGRAPH
2001
4
para k clusters Si, donde mi es el centroide de todos los
xi in Si .
- Propuesto por Steinhaus en 1956
- Variante más popular: algoritmo de Lloyd, basado en una
heurística de refinamiento iterativo
K-means estándard
• El k-means estándard usa los centroides como generadores
para las particiones subsecuentes, pero los centroides se
actualizan durante (y después) de cada partición:
Si el punto x en Si es más cercano al centroide mj de Sj :
• se asigna x al cluster Sj,
• los nuevos centriodes mi y mj de Si \ {x} y de Sj U {x} se calculan y
• se asignan mi y mj a los generadores
Decorative Mosaics SIGGRAPH
2001
5
K-means “continuo”
• Es más rápido que el estándar, lo que
permite aumentar el tamaño del conjunto
de datos a agrupar
• Los generadores iniciales se generan
aleatoriamente de una muestra de los
datos, en lugar de ser seleccionados
arbitrariamente
• En cada iteratión el k-means estándar
examina secuencialmente todos los datos,
el k-means “continuo” examina sólo una
muestra aleatoria de los datos
• Si el conjunto de datos es muy grande y si
las muestras son representativas, k-means
“continuo ” converge rápido (usualmente
después de examinar una fracción pequeña
(10-15 %) de los datos.Decorative Mosaics SIGGRAPH
2001
6
Algoritmo de Lloyd (1957)
Decorative Mosaics SIGGRAPH
2001
7
Algoritmo heurístico para resolver el problema k-means
0) Se hace partición inicial (aleatoria o usando una heurística) de
los puntos en k subconjuntos
1) Se calcula el centroide de cada subconjunto
2) Se construye una nueva partición, asociando a cada punto
con el centroide más cercano
3) Se calculan los centroides de los miembros de la nueva partición
4) Se repiten 2) y 3) hasta alcanzar algún criterio de convergencia
Decorative Mosaics SIGGRAPH
2001
8
Que es un DV?
Dado un conjunto {zi} de puntos de referencia o generadores,
es una partición en regiones (celdas) {Vi} de los puntos más
cercanos a un punto de referencia que a los otros
Diagrama Centroidal de Voronoi (DCV)
DV no DCV DCV
(o)centroides
(.) generadores
Que es un DCV?
Un DV , tal que zi es el centroide de Vi, para todo i.
Triangulaciones Duales de Delaunay (TDD)
• Los Diagramas Centroidales de Voronoi (DCV) son
la base para construir mallas triangulares buenas:
las triangulaciones de duales de Delaunay (TDD)
Decorative Mosaics SIGGRAPH
2001
9
• Los nodos de la TDD son
los centroides del DCV
• Dos nodos están
conectados por una arista
de la TDD si y solo si sus
celdas de Voronoi son
adjacentes
Por que decimos que las TDD son mallas
triangulares buenas ?
• El interior de cada circunesfera de los símplices de la
TDD no contiene generadores ( criterio de Delaunay )
• Cada arista de la TDD es perpendicular a alguna cara
del DCV correspondiente ( dualidad )
• Para cada arista de la TDD existe una esfera tal que los
únicos generadores que contiene son los extremos de la
arista ( propiedad del círculo vacío)
Decorative Mosaics SIGGRAPH
2001
10
En 2D las TDD satisfacen también las propiedades
• del mayor ángulo mínimo,
• del mayor círculo circunscrito
• del mayor círculo “enclosing” mínimo
• Un mínimo local de la función error V corresponde a un diagrama
centroidal de Voronoi (DCV), donde cada punto es más cercano al punto
de referencia (centroide) de su celda que a cualquier otro punto de
referencia :
Q.Du, V.Faber, M.Gunzburger, SIAM Rev.41 (1999). Rev.41 (1999)
• La iteración traslada la partición hacia un DCV y por tanto la aproxima
a un mínimo local de la función error V
11
• Particiones iniciales diferentes pueden converger a mínimos locales
diferentes, pero para muchas aplicaciones esto no es problemático...
• Calcular el óptimo global para n puntos en Rd es un problema NP-duro
( si n , d no son fijos)
-
- Cotas para el número de iteraciones para métodos del tipo
Lloyd:
Inaba-Katoh-Imai; Har-Peled-Sadri; A. Vassilvitskii (2006)
- Es un método muy sensible a la selección de las semillas
para los generadores, existe mucha literatura proponiendo
“buenos” métodos para generar semillas:
The Effectiveness of Lloyd-type Methods for the k-means
Problem de Swamy, Ostrovsky, Rabani & Schulman
-
Decorative Mosaics SIGGRAPH
2001
12
Generalización de los DCV
• Podemos usar métricas no euclideanas, o una función
de densidad anisotrópica
Definición 1: Dada una región V de Rn y una función de densidad rr definida sobre V, el centroide z* de V se
define como
Decorative Mosaics SIGGRAPH
2001
13
Definición 2: Dados k puntos {zi } de una región X y una función de densidad rr definida sobre X, el diagrama de
Voronoi asociado a {zi } es un Diagrama Centroidal de
Voronoi (DCV) ssi para i=1,2,..,k
zi = zi*
Decorative Mosaics SIGGRAPH
200
14
La triangulación de Delaunay dual correspondiente
a un DCV se denomina ... (TDDCV)
Para cualquier partición {Vi} de la región X y para
cualquier conjunto de puntos {zi} de X, se define el
funcional de costo ( de energía, de error):
Los DCV {Vi} junto los centroides {zi} son puntos críticos de
este funcional:
Q. Du, M. Gunzburger, App. Math. and Comp. 133 (2002)
D
15
Generación de mallas con restricciones:
formulación variacional
Muchas situaciones prácticas requieren imponer restricciones a
los DV que se traducen en imponer restricciones a la posición de sus
generadores, o de las aristas y caras de sus símplices.
Un caso importante consiste en adaptar el DV a la frontera de la
región X que se desea discretizar:
Sean X una región acotada con
frontera F, {zi} N puntos del
interior de X, {yk} M puntos de F
y sean {Vi} y {Wk} particiones del
interior de X y de F.
La TD correspondiente al DCV
que minimiza al siguiente
funcional respecto a {zi}, {yk}, {Vi}
y {Wk} es una buena malla
triangular que se adapta a la
frontera
Decorative Mosaics SGGRAPH
2001
16
Las funciones de densidad
r1 y r2 definidas sobre X y
F pueden ser diferentes y
basarse en información a
priori, en estimados del
error, etc.
Decorative Mosaics SIGGRAPH
2001
17
Suavizamiento local
El suavizamiento Laplaciano es uno de los más populares.
Consiste en trasladar cada vértice de la triangulación a la
posición del centroide de sus vértices vecinos
Los resultados obtenidos para los DCV aportan una justificación
teórica al método del suavizamiento Laplaciano :
Se trata de una aproximación al algoritmo de Lloyd para
construir un DCV y por lo tanto en cada iteración disminuye el
funcional de costo
Decorative Mosaics SIGGRAPH
2001
18
Algoritmos
Para calcular un DCV (sin restricciones) sobre un
conjunto X con una función densidad r dada
0. Seleccionar k puntos {zi} de X, usando por ejemplo Monte Carlo
1. Construir el DV, {Vi}, asociado a los puntos {zi} , respecto a la densidad r
2. Calcular los centroides de los Vi y asignárselos a los nuevos puntos zi
3. Si el nuevo conjunto {zi} satisface algún criterio de convergencia,
calcular la TD correspondiente a {zi} y STOP, de lo contrario regresar a 1.
Este es el algoritmo de Lloyd para una función densidad r
definida sobre X y puede verse como una iteración de
punto fijo de la aplicación que mapea los generadores en
los centroides
Convergencia: Q.Du, V.Faber, M.Gunzburger, SIAM Rev.41 (1999).
Algoritmos
0. Seleccionar conjunto inicial de k puntos en P, {zi}
1. Construir el DV, {Vi}, asociado a los puntos {zi} , respecto a
la densidad r
2. Calcular el mínimo en P del funcional
Decorative Mosaics SIGGRAPH
2001
19
Para calcular un DCV sobre un conjunto X con una función
densidad r dada y conjunto de restricciones P
3. Asignar a los nuevos puntos zi los puntos calculados en 2.
4. Si el nuevo conjunto {zi} satisface algún criterio de
convergencia, calcular la TD correspondiente a {zi} y STOP, de
lo contrario regresar a 1.
Ejemplos numéricos
TD asociadas a DVs (función densidad constante)
Decorative Mosaics SIGGRAPH
2001
20
generadores de la DV
seleccionados aleatoriamente
generadores de la DV obtenidos
aplicando Lloyd
Ejemplos numéricos
• TD asociadas a DVs (función densidad no constante)
Decorative Mosaics SIGGRAPH
2001
21
generadores de la DV
seleccionados aleatoriamente
generadores de la DV obtenidos
aplicando Lloyd
Solución numérica de EDP
• Las TDDCV pueden vincularse a la solución numérica de
EDPs.
• La estrategia de generación óptima de mallas
triangulares puede insertarse en la metodología de
discretización de las EDP
• Los estimados a posteriori de los errores pueden ser
eventualmente usados para determinar una función de
densidad efectiva
Decorative Mosaics SIGGRAPH
2001
22
Solución numérica de EDP
Ejemplo: solución de la ecuación de Poisson con condiciones
de frontera tipo Dirichlet en el cuadrado unitario
• En todos los casos, en la discretización se usaron elementos finitos
triangulares cuadráticos
• Las mallas TDDCV y las cartesianas que se comparan tienen
aproximadamente el mismo número de nodos y triángulos
• Se comparan los errores entre las aproximaciones por elementos
finitos cuadráticos de las mallas TDDCV y las cartesianas con la
solución exacta dada por
Decorative Mosaics SIGGRAPH
2001
23
u(x) tiene un gradiente grande en el origen y
decae rápidamente lejos de éste
Solución numérica de EDP
Las mallas cartesianas se refinan usando la aplicación x --> xs, con s > 1
Mallas cartesianas 16x16 para s=1,2,3e Mosaics SIGGRAPH 2001
24
Mallas cartesianas 8x8 para s=2,3,4
Solución numérica de EDP
• Para las mallas TDDCV los refinamientos se hacen seleccionando
convenientemente la función de densidad
• Puesto que los estimados a priori de los errores de elementos
finitos cuadráticos se calculan en términos de las terceras
derivadas, la función densidad que se considera es:
Decorative Mosaics SIGGRAPH
2001
25
Para k=0, obtenemos la densidad uniforme
TDDCV con k=0.5,1,1.5, 64 generadores, aprox. 100 triángulos
Solución numérica de EDP
• TDDCV con k=0.5,1,1.5, 64 generadores, aprox. 100 triángulos
Decorative Mosaics SIGGRAPH
2001
26
• TDDCV con k=0.25,0.5,0.75, aprox. 450 triángulos
Generalización de los DCV a superficies
curvasD. Qiang, M. Gunzburger, L. Ju, SIAM J. Sci. Comp. (2003)
Sustituyendo la métrica en R3 por la distancia geodésica, se generaliza la
definición de centroide de un subconjunto Vi de una superficie S, como el
punto w* de S que minimiza el funcional de energía
Decorative Mosaics SIGGRAPH
2001
27
donde d es la distancia geodésica sobre S y ds es el elemento de área.
Si S es una superficie de Riemann, asumiendo hipótesis no muy
restrictivas se demuestra la existencia de w* .
También se precisa como generalizar la definición de DCV y se demuestra
que éstos se caracterizan por minimizar un funcional de energía
No se aportan condiciones suficientes para la convergencia global del
algoritmo de Lloyd en este contexto
Aplicaciones a superficies
• Parametrización y mapeo de texturas
• Remallado
• Generación de puntos
representativos
• Segmentación
• Mosaicos
Decorative Mosaics SIGGRAPH
2001
28
