En génie électrique et en informatique , l'algorithme de Lloyd , également connu sous le nom d'itération ou de relaxation de Voronoi , est un algorithme du nom de Stuart P. Lloy...
Worldlex WikiFrancaisLecture gratuite
En génie électrique et en informatique , l'algorithme de Lloyd , également connu sous le nom d'itération ou de relaxation de Voronoi , est un algorithme du nom de Stuart P. Lloyd permettant de trouver des ensembles de points équidistants dans des sous-ensembles d' espaces euclidiens et de partitionner ces sous-ensembles en cellules convexes bien définies et de taille uniforme. À l'instar de l'algorithme de clustering k -means , il détermine itérativement le centroïde de chaque ensemble dans la partition, puis repartitionne l'ensemble d'entrée en fonction du centroïde le plus proche. Dans ce contexte, la moyenne est une intégrale sur une région de l'espace, et la recherche du centroïde le plus proche produit des diagrammes de Voronoi .
Sur la dernière image, les sites sont très proches des centroïdes des cellules de Voronoï. Une tessellation de Voronoï centroïdale a été mise en évidence.
Histoire
L'algorithme a été proposé pour la première fois par Stuart P. Lloyd des Bell Labs en 1957 comme technique de modulation par impulsions et codage . Les travaux de Lloyd ont été largement diffusés mais sont restés inédits jusqu'en 1982. Un algorithme similaire a été développé indépendamment par Joel Max et publié en 1960, c'est pourquoi l'algorithme est parfois appelé algorithme de Lloyd-Max.
Description de l'algorithme
L'algorithme de Lloyd commence par le placement initial d'un certain nombre k de points dans le domaine d'entrée. Dans les applications de lissage de maillage, il s'agit des sommets du maillage à lisser ; dans d'autres applications, ils peuvent être placés aléatoirement ou par intersection d'un maillage triangulaire uniforme de taille appropriée avec le domaine d'entrée.
Il exécute ensuite de manière répétée l'étape de relaxation suivante :
Chaque cellule du diagramme de Voronoi est intégrée, et le centroïde est calculé.
Chaque site est ensuite déplacé vers le centroïde de sa cellule de Voronoi.
Intégration et calcul du centroïde
Étant donné que les algorithmes de construction de diagrammes de Voronoi peuvent être très complexes, en particulier pour des entrées de dimension supérieure à deux, les étapes de calcul de ce diagramme et de recherche des centroïdes exacts de ses cellules peuvent être remplacées par une approximation.
Approximation
Une simplification courante consiste à utiliser une discrétisation spatiale appropriée, telle qu'une grille de pixels fine, par exemple le tampon de texture d'une carte graphique. Les cellules sont matérialisées sous forme de pixels, étiquetés avec leur identifiant de site. Le nouveau centre d'une cellule est approximé en faisant la moyenne des positions de tous les pixels ayant la même étiquette. On peut également utiliser des méthodes de Monte Carlo , dans lesquelles des points d'échantillonnage aléatoires sont générés selon une distribution de probabilité sous-jacente fixe, affectés au site le plus proche, et moyennés pour approximer le centroïde de chaque site.
Calcul exact
Bien que l'intégration dans d'autres espaces soit également possible, cette élaboration suppose l'espace euclidien en utilisant la norme L2 et examine les deux scénarios les plus pertinents, à savoir deux et trois dimensions.
Puisqu'une cellule de Voronoi est de forme convexe et qu'elle entoure toujours son emplacement, il existe des décompositions triviales en simplexes intégrables faciles :
En deux dimensions, les bords de la cellule polygonale sont reliés à son emplacement, créant un ensemble de triangles en forme de parapluie.
En trois dimensions, la cellule est entourée de plusieurs polygones plans qui doivent d'abord être triangulés :
Calculer le centre de la face polygonale, par exemple la moyenne de tous ses sommets.
Relier les sommets d'une face polygonale à son centre donne une triangulation plane en forme de parapluie.
De façon triviale, un ensemble de tétraèdres est obtenu en reliant les triangles de l'enveloppe de la cellule avec le site de la cellule.
L'intégration d'une cellule et le calcul de son centroïde ( centre de masse ) sont désormais donnés comme une combinaison pondérée des centroïdes de ses simplexes (appelés ci-après centroïdes).
Deux dimensions :
Pour un triangle, le centre de gravité peut être facilement calculé, par exemple en utilisant les coordonnées cartésiennes .
La pondération est calculée comme le rapport entre la surface du simplexe et celle de la cellule .
Trois dimensions :
Le centre de gravité d'un tétraèdre se trouve à l'intersection de trois plans bissecteurs et peut être exprimé comme un produit matrice-vecteur.
La pondération est calculée comme le rapport du volume du simplexe au volume de la cellule .
Pour une cellule 2D avec simplexes triangulaires et une aire cumulée
De même, pour une cellule 3D d'un volume de
Convergence
À chaque étape de relaxation, les points sont répartis de manière légèrement plus uniforme : les points proches s’éloignent les uns des autres, tandis que les points éloignés se rapprochent. En une dimension, cet algorithme converge vers un diagramme de Voronoï centroïdal, également appelé tessellation de Voronoï centroïdale . En dimensions supérieures, des résultats de convergence légèrement moins marqués ont été observés
L'algorithme converge lentement, voire pas du tout en raison de limitations de précision numérique. C'est pourquoi, dans la pratique, l'algorithme de Lloyd s'arrête généralement une fois la distribution jugée « suffisante ». Un critère d'arrêt courant consiste à interrompre l'algorithme lorsque la distance maximale parcourue par un point quelconque au cours d'une itération descend en dessous d'un seuil prédéfini. La convergence peut être accélérée en surrelaxant les points, c'est-à-dire en déplaçant chaque point d'une distance ω fois supérieure à la distance au centre de masse, généralement avec une valeur de ω légèrement inférieure à 2.
Applications
La méthode de Lloyd a été initialement utilisée pour la quantification scalaire, mais il est clair qu'elle s'étend également à la quantification vectorielle . De ce fait, elle est largement utilisée dans les techniques de compression de données en théorie de l'information . La méthode de Lloyd est employée en infographie car la distribution résultante présente des caractéristiques de bruit bleu (voir aussi Couleurs du bruit ), ce qui signifie qu'il y a peu de composantes basse fréquence susceptibles d'être interprétées comme des artefacts. Elle est particulièrement adaptée à la sélection des positions d'échantillonnage pour le tramage . L'algorithme de Lloyd est également utilisé pour générer des dessins pointillistes de type pointillisme . Dans cette application, les centroïdes peuvent être pondérés à l'aide d'une image de référence afin de produire des illustrations pointillistes correspondant à une image d'entrée.
Dans la méthode des éléments finis , un domaine d'entrée à géométrie complexe est partitionné en éléments de formes plus simples ; par exemple, les domaines bidimensionnels (sous-ensembles du plan euclidien ou surfaces tridimensionnelles) sont souvent partitionnés en triangles. Pour la convergence de la méthode des éléments finis, il est important que ces éléments soient bien formés ; dans le cas des triangles, on privilégie souvent des éléments quasi équilatéraux. L'algorithme de Lloyd permet de lisser un maillage généré par un autre algorithme, en déplaçant ses sommets et en modifiant la configuration des connexions entre ses éléments afin de produire des triangles plus équilatéraux. Ces applications utilisent généralement un nombre réduit d'itérations de l'algorithme de Lloyd, en l'arrêtant à convergence, afin de préserver d'autres caractéristiques du maillage, telles que les différences de taille des éléments dans différentes parties du maillage. Contrairement à une autre méthode de lissage, le lissage laplacien (qui consiste à déplacer les sommets du maillage vers la position moyenne de leurs voisins), l'algorithme de Lloyd peut modifier la topologie du maillage, ce qui permet d'obtenir des éléments plus équilatéraux et d'éviter les problèmes d'enchevêtrement pouvant survenir avec le lissage laplacien. Cependant, le lissage laplacien peut être appliqué plus généralement à des maillages comportant des éléments non triangulaires.
Distances différentes
L'algorithme de Lloyd est généralement utilisé dans un espace euclidien . La distance euclidienne joue un double rôle dans cet algorithme : elle sert à définir les cellules de Voronoï, mais elle détermine également le choix du centroïde comme point représentatif de chaque cellule, puisque le centroïde est le point qui minimise la moyenne des carrés des distances euclidiennes aux points de sa cellule. D'autres distances, et d'autres points centraux que le centroïde, peuvent être utilisés. Par exemple, métrique de Manhattan (avec des orientations localement variables) pour trouver un pavage d'une image par des tuiles approximativement carrées dont l'orientation correspond aux caractéristiques de l'image. Il a ensuite utilisé ce pavage pour simuler la construction de mosaïques . [ cette application, malgré la variation de la métrique, Hausner a continué d'utiliser les centroïdes comme points représentatifs des cellules de Voronoï. Cependant, pour des métriques plus éloignées de la métrique euclidienne, il peut être judicieux de choisir le point minimisant la moyenne des carrés des distances comme point représentatif, plutôt que le centroïde.
Worldlex Wiki 
