En ingeniería eléctrica e informática , el algoritmo de Lloyd , también conocido como iteración o relajación de Voronoi, es un algoritmo que lleva el nombre de Stuart P. Lloyd para encontrar conjuntos de puntos uniformemente espaciados en subconjuntos de espacios euclidianos y particiones de estos subconjuntos en espacios bien formados y uniformes. Células convexas de gran tamaño. [1] Al igual que el algoritmo de agrupamiento de k -medias estrechamente relacionado , encuentra repetidamente el centroide de cada conjunto en la partición y luego vuelve a particionar la entrada según cuál de estos centroides es el más cercano. En este contexto, la operación media es una integral sobre una región del espacio, y la operación del centroide más cercano da como resultado diagramas de Voronoi .
Aunque el algoritmo se puede aplicar más directamente al plano euclidiano , también se pueden aplicar algoritmos similares a espacios de dimensiones superiores o a espacios con otras métricas no euclidianas . El algoritmo de Lloyd se puede utilizar para construir aproximaciones cercanas a teselaciones centroidales de Voronoi de la entrada, [2] que se pueden utilizar para cuantificación , tramado y punteado . Otras aplicaciones del algoritmo de Lloyd incluyen el suavizado de mallas triangulares en el método de elementos finitos .
El algoritmo fue propuesto por primera vez por Stuart P. Lloyd de Bell Labs en 1957 como una técnica para la modulación de código de pulso . El trabajo de Lloyd tuvo una amplia circulación, pero permaneció inédito hasta 1982. [1] Joel Max desarrolló de forma independiente un algoritmo similar y lo publicó en 1960, [3] razón por la cual el algoritmo a veces se denomina algoritmo de Lloyd-Max.
El algoritmo de Lloyd comienza con la colocación inicial de un número k de sitios puntuales en el dominio de entrada. En aplicaciones de suavizado de malla, estos serían los vértices de la malla a suavizar; en otras aplicaciones, se pueden colocar al azar o intersectando una malla triangular uniforme del tamaño apropiado con el dominio de entrada.
Luego ejecuta repetidamente el siguiente paso de relajación:
Debido a que los algoritmos de construcción del diagrama de Voronoi pueden no ser triviales, especialmente para entradas de dimensión superior a dos, los pasos de calcular este diagrama y encontrar los centroides exactos de sus celdas pueden reemplazarse por una aproximación.
Una simplificación común es emplear una discretización adecuada del espacio como una fina cuadrícula de píxeles, por ejemplo, el búfer de textura en el hardware de gráficos. Las celdas se materializan como píxeles, etiquetados con su correspondiente ID de sitio. El nuevo centro de una celda se aproxima promediando las posiciones de todos los píxeles asignados con la misma etiqueta. Alternativamente, se pueden utilizar métodos de Monte Carlo , en los que se generan puntos de muestra aleatorios de acuerdo con alguna distribución de probabilidad subyacente fija, se asignan al sitio más cercano y se promedian para aproximar el centroide de cada sitio.
Aunque también es posible la integración en otros espacios, esta elaboración asume el espacio euclidiano utilizando la norma L 2 y analiza los dos escenarios más relevantes, que son dos y, respectivamente, tres dimensiones.
Dado que una celda de Voronoi tiene forma convexa y siempre encierra su sitio, existen descomposiciones triviales en simples integrables fáciles:
La integración de una celda y el cálculo de su centroide (centro de masa) ahora se dan como una combinación ponderada de los centroides de sus simples (en lo sucesivo denominados ).
Para una celda 2D con n triángulos simples y un área acumulada (donde es el área de un triángulo simple), el nuevo centroide de la celda se calcula como:
De manera análoga, para una celda 3D con un volumen de (donde está el volumen de un tetraedro simple), el centroide se calcula como:
Cada vez que se realiza un paso de relajación, los puntos se dejan en una distribución ligeramente más uniforme: los puntos muy espaciados se separan más y los puntos muy espaciados se acercan. En una dimensión, se ha demostrado que este algoritmo converge a un diagrama centroidal de Voronoi, también denominado teselación centroidal de Voronoi . [4] En dimensiones superiores, se conocen algunos resultados de convergencia ligeramente más débiles. [5] [6]
El algoritmo converge lentamente o, debido a limitaciones en la precisión numérica, puede que no converja. Por lo tanto, las aplicaciones del algoritmo de Lloyd en el mundo real normalmente se detienen una vez que la distribución es "suficientemente buena". Un criterio de terminación común es detenerse cuando la distancia máxima recorrida por cualquier sitio en una iteración cae por debajo de un umbral preestablecido. La convergencia se puede acelerar relajando demasiado los puntos, lo que se hace moviendo cada punto ω veces la distancia al centro de masa, generalmente usando un valor ligeramente menor que 2 para ω . [7]
El método de Lloyd se utilizó originalmente para la cuantificación escalar, pero está claro que el método se extiende también a la cuantificación vectorial. Como tal, se utiliza ampliamente en técnicas de compresión de datos en teoría de la información . El método de Lloyd se utiliza en gráficos por computadora porque la distribución resultante tiene características de ruido azul (ver también Colores de ruido ), lo que significa que hay pocos componentes de baja frecuencia que podrían interpretarse como artefactos. Es particularmente adecuado para seleccionar posiciones de muestra para tramado . El algoritmo de Lloyd también se utiliza para generar dibujos de puntos al estilo del punteado . [8] En esta aplicación, los centroides se pueden ponderar en función de una imagen de referencia para producir ilustraciones punteadas que coincidan con una imagen de entrada. [9]
En el método de elementos finitos , un dominio de entrada con una geometría compleja se divide en elementos con formas más simples; por ejemplo, los dominios bidimensionales (ya sean subconjuntos del plano euclidiano o superficies en tres dimensiones) suelen dividirse en triángulos. Es importante para la convergencia de los métodos de elementos finitos que estos elementos estén bien formados; en el caso de los triángulos, a menudo se prefieren elementos que son triángulos casi equiláteros. El algoritmo de Lloyd se puede utilizar para suavizar una malla generada por algún otro algoritmo, moviendo sus vértices y cambiando el patrón de conexión entre sus elementos para producir triángulos que sean más equiláteros. [10] Estas aplicaciones suelen utilizar un número menor de iteraciones del algoritmo de Lloyd, deteniéndolo hasta la convergencia, para preservar otras características de la malla, como las diferencias en el tamaño de los elementos en diferentes partes de la malla. A diferencia de un método de suavizado diferente, el suavizado laplaciano (en el que los vértices de la malla se mueven al promedio de las posiciones de sus vecinos), el algoritmo de Lloyd puede cambiar la topología de la malla, lo que lleva a elementos más casi equiláteros y evita los problemas con enredos que pueden surgir con el alisado laplaciano. Sin embargo, el suavizado laplaciano se puede aplicar de manera más general a mallas con elementos no triangulares.
El algoritmo de Lloyd se suele utilizar en un espacio euclidiano . La distancia euclidiana juega dos papeles en el algoritmo: se utiliza para definir las celdas de Voronoi, pero también corresponde a la elección del centroide como punto representativo de cada celda, ya que el centroide es el punto que minimiza la distancia euclidiana al cuadrado promedio. a los puntos de su celda. En su lugar, se pueden utilizar distancias alternativas y puntos centrales alternativos al centroide. Por ejemplo, Hausner (2001) utilizó una variante de la métrica de Manhattan (con orientaciones que varían localmente) para encontrar un mosaico de una imagen mediante mosaicos aproximadamente cuadrados cuya orientación se alinea con las características de una imagen, que utilizó para simular la construcción de mosaicos en mosaico. . [11] En esta aplicación, a pesar de variar la métrica, Hausner continuó usando centroides como puntos representativos de sus células de Voronoi. Sin embargo, para métricas que difieren más significativamente de las euclidianas, puede ser apropiado elegir el minimizador de la distancia promedio al cuadrado como punto representativo, en lugar del centroide. [12]
