Diagramme de Voronoï et algorithme de Lloyd-Max

Quantification de signal

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Tout le monde se secoue ! :D

J'ai commencé (il y a une heure) la rédaction d'un tutoriel au doux nom de « Diagramme de Voronoï et algorithme de Lloyd-Max » et j'ai dans l'objectif de proposer en validation un texte aux petits oignons. Je fais donc appel à votre bonté sans limite pour dénicher le moindre pépin, que ce soit à propos du fond ou de la forme. Vous pourrez consulter la bêta à votre guise à l'adresse suivante :

Merci !

+1 -0

Cette réponse a aidé l'auteur du sujet

Salut !

Il y a des applications de dehors de la théorie du signal ou pas ? Car en temps que non informaticien ça ne parle pas de trop. J'imagine que ça soit pouvoir servir en biologie ou en physique pour expliquer certain phénomènes non ?

"Toute extrapolation est valide dès lors que son résultat m’est sympathique." Loi de Lomborg

+1 -0
Auteur du sujet

Alors en dehors de l'informatique, je présume fortement que oui, notamment en physique et biologie, en effet, mais je ne peux pas te le confirmer.

Pour la petite histoire, l'utilisation d'un diagramme de Voronoï a permis en 1854 par le médecin John Snow (true story)

De déterminer l'origine d'une épidémie de choléra à Mancherster en positionnant l'épicentre des décès résultant de la contamination. C'est une histoire assez connue qu'on raconte au étudiant en science à propos de la méthodologie scientifique.

Du coup c'est cool, je vais un peu expliciter tout ça:

  • L'historique.
  • Les cas d'utilisations autres que ceux en informatiques.

Édité par denissalem

+2 -0
Staff

Coucou, très rapide message (parce que j'ai pas le temps ce soir de lire soigneusement, je le ferais plus tard).

  • Contenu original ! C'est super, et je t'ai inscrit sur la liste des contenus mathématiques en rédaction. N'hésite pas à venir vers moi si tu as des besoin pendant ta rédaction.
  • Attention aux intro et conclusions : semblent légères.
  • Qu'est-ce que tu veux comme retours ? Sur la forme ? Le fond ? Le tout ?
  • Pour les expressions mathématiques, préfère plutôt l'utilisation de Mathjax.
+2 -0
Auteur du sujet

Merci de ton intérêt!

  • En ce qui concerne la conclusion/introduction, c'est un moyen, et pas une fin me semble-t-il. En ce qui me concerne, ça ne match pas trop avec ma façon d'écrire et d'expliquer les choses. Si c'est vraiment problématique je peux envisager de revoir tout ça cela. Je vais déjà me concentrer sur ce que j'ai dit que j'allais faire.

  • Pour les retours, ce qui m'intéresse c'est de savoir si c'est compréhenssible et accessible. Par ailleurs, je suis très pénalisé au niveau de l'orthographe, j'essay vraiment de m'améliorer, mais je suis vraiment, vraiment mauvais à ce niveau :(. Un seigneur de guerre de la langue française ou un grammar nazi est donc le bienvenu!

  • Pour les expressions mathématiques, je vais regarder ça :)

+0 -0

Il y a des applications de dehors de la théorie du signal ou pas ? Car en temps que non informaticien ça ne parle pas de trop. J'imagine que ça soit pouvoir servir en biologie ou en physique pour expliquer certain phénomènes non ?

Demandred

J'étais à une conférence la semaine dernière où un groupe des USA s'en servait pour avoir une microstructure initiale. En soit, l'idée n'est pas nouvelle, et j'avais déjà demandé à mes étudiants de le faire. Là où c'était plus intéressant, c'est qu'ils avaient aussi reproduit la microstructure exacte, et en modélisant la croissance des grains (modèle de Potts je suppose, le plus facile) à partir des deux microstructures, ils arrivaient à des résultats très semblables après très peu d'itérations. En gros, c'était une preuve que cette distribution extrêmement simple était une approximation suffisament bonne pour leur application.

Édité par Rockaround

Staff

Cette réponse a aidé l'auteur du sujet

Mes remarques après lecture :

Dans ce tutoriel nous allons d'une part voir rapidement ce qu'est un diagramme de Voronoï, et d'autre part, étudier la façon dont on s'en sert dans le cadre de l'algorithme dit de Lloyd-Max. Le tout sera appuyé par un exemple de cas d'usage très courant ainsi qu'un peu de code source en C/C++

Introduction mal ficelée. Ou bien on connaît le sujet et on en a pas besoin, ou bien on le connaît pas et on apprend rien et on se sent perdu.

Il s’agit d’un objet mathématique découpant l’espace en cellules de manière particulière. On parle de pavage de Voronoï, ou de Voronoï tesselation en anglais.

Introduction de la notion à revoir pour la même raison. Quelles sont les motivations ? Quels sont les problèmes sous-jacents ?

On appelle région ou cellule (cell, en anglais) de Voronoï, associé à un élément p de S, l’ensemble de TOUS les points qui sont plus proches de p que de tout autre point de S. Ici, les élément de S sont des points de références et on évalue les distances entre ceux là et tous les points qui existent sur le plan. Parmi tous les points d’une cellule de Voronoï V, il ne peut y avoir qu’un seul élément de S : Celui qui a servie à construire V.

Il faut préciser la distance choisie.

À titre de rappelle un plan affine est un plan dans lequel il n’y aurait pas de repère. En effet dans ce plan nous ne nous intéressons pas aux positions des points mais à la distance de ceux là entre eux.

À revoir.

De nombreux domaines d'applications peuvent être ramené à la théorie du signal ce qui rend donc l'algorithme de Lloyd-Max très commode à utiliser en une ou n dimensions. En effet on représente le plus souvent un diagramme de LLoyd en deux dimensions, mais il est tout à fait possible de généraliser son principe en une ou trois dimensions. Par exemple dans le cas du domaine du traitement d'image, lorsque l'on veut réduire le nombre de couleurs d'une image on travaille en réalité avec un diagramme de Voronoï en trois dimensions, une pour chaque composante RGB de l'image. On pourrait d'ailleurs faire la même c

Il aurait fallu développer cet exemple. On voit qu'il se passe quelque chose mais on reste sur notre faim. À ce stade du tutoriel on devrait largement avoir pris connaissance du domaine d'application et un cas concret et adaptable, ce qui n'est pas le cas.

D'un point de vue abstrait, pour un diagramme de Voronoï non-restreint (c'est à dire pour lequel on considère tous les points de l'espace), l'algorithme de Lloyd-Max fait converger le diagramme dans un état tel que la différence entre toutes distances entre tous les germes soit minimisé. Dit autrement l'algorithme dont nous parlons fait en sorte que le barycentre d'une cellule de Voronoï donnée coïncide avec son germe. Ce type de diagrammes où les germes coïncident avec le barycentre de leurs cellules respectives est appelé diagramme de Voronoï centroïdal.

Il faut beaucoup plus de détails.


Actuellement je vois deux chantiers à mener :

  • rendre l'exposé compréhensible : actuellement ça ressemble plus à une présentation à des spécialistes qu'à des néophytes ;
  • motiver l'apprentissage dès le début.
+1 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte