En ingeniería eléctrica y ciencias de la computación , 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 espaciados uniformemente en subconjuntos de espacios euclidianos y particiones de estos subconjuntos en celdas convexas bien formadas y de tamaño uniforme. [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 sea el más cercano. En este contexto, la operación de media es una integral sobre una región del espacio, y la operación de centroide más cercana 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 de Voronoi centroidales 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 por código de pulsos . El trabajo de Lloyd se difundió ampliamente, pero permaneció inédito hasta 1982. [1] Joel Max desarrolló un algoritmo similar de forma independiente y lo publicó en 1960, [3] razón por la cual a veces se lo conoce como el algoritmo Lloyd-Max.
El algoritmo de Lloyd comienza con la colocación inicial de una cierta cantidad k de puntos en el dominio de entrada. En aplicaciones de suavizado de mallas, estos serían los vértices de la malla que se va a suavizar; en otras aplicaciones, se pueden colocar de forma aleatoria o intersectando una malla triangular uniforme del tamaño adecuado con el dominio de entrada.
Luego ejecuta repetidamente el siguiente paso de relajación:
Debido a que los algoritmos de construcción de diagramas de Voronoi pueden ser altamente no triviales, especialmente para entradas de dimensión mayor 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 habitual consiste en emplear una discretización adecuada del espacio, como una cuadrícula de píxeles fina, por ejemplo, el búfer de texturas del hardware gráfico. 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. Como alternativa, se pueden utilizar métodos de Monte Carlo , en los que se generan puntos de muestra aleatorios según una 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 incrustación en otros espacios, esta elaboración supone el espacio euclidiano utilizando la norma L 2 y analiza los dos escenarios más relevantes, que son de dos y tres dimensiones, respectivamente.
Como una celda de Voronoi tiene forma convexa y siempre encierra su sitio, existen descomposiciones triviales en símplices fácilmente integrables:
La integración de una celda y el cálculo de su centroide (centro de masa) ahora se da como una combinación ponderada de los centroides de sus símplices (en adelante llamados ).
Para una celda 2D con n símplices triangulares y un área acumulada (donde es el área de un triángulo símplice), el nuevo centroide de la celda se calcula como:
De manera análoga, para una celda 3D con un volumen de (donde es el volumen de un tetraedro símplex), el centroide se calcula como:
Cada vez que se realiza un paso de relajación, los puntos quedan distribuidos de forma ligeramente más uniforme: los puntos con poca separación entre sí se alejan más y los puntos con mayor separación entre sí se acercan más. En una dimensión, se ha demostrado que este algoritmo converge a un diagrama de Voronoi centroidal, también denominado teselación de Voronoi centroidal . [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 no converger. Por lo tanto, las aplicaciones del algoritmo de Lloyd en el mundo real suelen detenerse 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 excesivamente 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 la teoría de la información . El método de Lloyd se utiliza en gráficos de computadora porque la distribución resultante tiene características de ruido azul (ver también Colores del 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 en el estilo de punteado . [8] En esta aplicación, los centroides se pueden ponderar en función de una imagen de referencia para producir ilustraciones de punteado 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) a menudo se dividen 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 sean 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 genera elementos más equiláteros y evita los problemas de enredos que pueden surgir con el suavizado 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 utiliza habitualmente en un espacio euclidiano . La distancia euclidiana desempeña 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 de mosaicos . [11] En esta aplicación, a pesar de variar la métrica, Hausner continuó utilizando centroides como puntos representativos de sus celdas de Voronoi. Sin embargo, para métricas que difieren más significativamente de la euclidiana, puede ser apropiado elegir el minimizador de la distancia al cuadrado promedio como punto representativo, en lugar del centroide. [12]
