"Fitter" un cercle avec un nuage de points
dans Statistiques
de plus je voudrais pouvoir fitter plus de points avec un cercle, j'ai entendu parler de la méthode des moindres carrés mais je ne la comprends pas, auriez-vous de bons tutos ou mieux un algo de fittage de cercle déjà fonctionnel ou du moins un pseudo-code ?
Merci.
Bien cordialement.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
J'ai cherché la signification du mot "fitter".
J'ai trouvé du bridge, mais pas de cercle.
Cordialement,
Rescassol
Quel est le cercle qui 'coïncide' le mieux avec la liste des points fournis.
Selon qu'on a 3 points, ou plus de 3 points, la problématique n'est pas du tout la même.
Avec 3 points, c'est très simple, il y a 1 cercle et 1 seul qui passe par 3 points. 'Par 2 points, il passe une et une seule droite, et par 3 points, il passe 1 et 1 seul cercle'.
Pour trouver le cercle qui passe par 3 points A B C, on trace la médiatrice de AB, on trace la médiatrice de AC, et le centre du cercle, c'est le point où ces 2 droites se croisent (bien entendu, la médiatrice de BC passe aussi par ce point). Et ensuite, on peut calculer le rayon de ce fameux cercle.
Si on a plus de 3 points, à moins d'un coup de chance miraculeux, il n'y aura pas de cercle qui passe strictement par ces 3 points. Et il faudra effectivement passer par une méthode type 'moindres carrés'.
Dans mes lointains souvenirs, la méthode des moindres carrés ne va pas donner un résultat magique dans le cas d'un cercle. Il n'y a pas une formule toute faite qui va donner l'équation du cercle qui marche le mieux.
Une solution approximative, c'est de prendre 3 points parmi le jeu de données , de préférence 3 points le plus éloignés possibles, et appliquer la méthode du 1er cas... Très approximatif.
C\mapsto \frac{1}{n}\sum_{i=1}^np(A_i,C)^2.$$ Ça marche comme la minimisation de la distance d'un plan à un nuage de points. Le problème m'avait été posé par Laurent Puech, un physicien de Grenoble. Je peux t'envoyer un document par message privé.
J'ai fait un M2 de stats sans passer par le M1, au début je ne comprenais pas les profs quand ils disaient "on ajuste un modèle".
Puis au boulot, là où je suis, on n'ajuste plus les modèles, on les "fit".
une méthode exacte dans le cas de seulement trois points et qui convient dans le cas de plus de trois points (avec ou sans dispersion) est donnée pp. 11-13 dans ce papier : https://fr.scribd.com/doc/14819165/Regressions-coniques-quadriques-circulaire-spherique .
Voici un code en Python:
Cordialement,
Rescassol
Bravo pour l'implémentation en Python (que je n'ai pas, donc sans vérifier. Mais il n'y a pas de raison pour que cela ne marche pas).
Le petit exemple numérique de ma réponse a été fait avec MathCad. Pour la petite histoire, le premier code qui a été écrit était en Fortran, au début des années 1980. C'est dire que ce n'est pas tout jeune !
Bien cordialement,
JJ.
La visualisation d'un résultat numérique avec beaucoup de points illustre bien la discussion.
Bien cordialement,
JJ.
Y=x0+R*np.sin(T) ne devrait-il pas être Y=y0+R*np.sin(T)
Merci Sylvain, ce sont les joies du copier/coller.
En plus, dans mon exemple, on avait x0=y0=1.
J'ai corrigé le script Python.
Cordialement,
Rescassol
ton script marche dans la majorité des cas mais je suis tombé sur un cas où il ne marche pas je te joins le fichier des points :
http://sylvain-ard.fr/temp/contour.csv
et le script modifié pour lire un fichier CSV de points :
http://sylvain-ard.fr/temp/regression_circulaire.py
ça m'ennuie car mon programme doit fonctionner dans presque tous les cas
ce que je souhaiterais pour ce nuage de points c'est qu'il me trouve un très grand cercle passant par la majorité des points
si c'est impossible, peut-on au moins détecter les cas faussés pour ne pas répercuter l'erreur dans le reste du programme ?
Merci
Cordialement
Volla à quoi ressemblent tes points, sans et avec le cercle.
On ne peut pas vraiment dire qu'une approximation circulaire se justifie.
Aucun cercle ne peut passer par une majorité de ces points.
Dans ce cas, la méthode fait ce qu'elle peut.
J'ai calculé l'erreur avec Erreur=sum((r**2-(X-a)**2-(Y-b)**2)**2)
Sur mon exemple de 100 points, on obtient Erreur = 5.129802488161554
Avec tes 77 points, on obtient Erreur = 14628865.101046737
Cordialement,
Rescassol
il faut bien comprendre que le code écrit par Rescassol (que je salue) n'est ni plus ni moins que la traduction informatique des résultats théoriques qui sont publiés dans https://fr.scribd.com/doc/14819165/Regressions-coniques-quadriques-circulaire-spherique . Il est donc normal que le logiciel donne de bons résultats si le problème correspond au cas théorique qui a été considéré dans cette étude et de mauvais résultats si le problème n'est pas celui qui a été étudié.
L'étude théorique et l'application pratique concerne strictement le problème de "régressiojn circulaire", tel que défini dans le document cité. C'est très différent de "trouver un très grand cercle passant par la majorité des points". Encore faudrait-il définir précisément ce que veut dire "la majorité des points" au sens mathématique.
En conséquence, le code (qu'il soit écrit pour Python, ou pour MathCad, ou pour Delphi, etc. dans quelque soit le language) ne répond pas au problème de "trouver un très grand cercle passant par la majorité des points". Pour y répondre il faudrait une étude théorique de ce problème qui n'est pas traité dans le document référencé.
Ah je croyais pourtant que la régression circulaire consistait à trouver le cercle le plus proche des points. Oui je ne voulais pas dire qui passe par une majorité de points mais qui est le plus proche des points.
s'il en est ainsi, le malentendu vient de l'ambiguité de la question. En effet "qui est au plus proche des points" n'a pas de sens mathématique bien défini : https://fr.wikipedia.org/wiki/Méthode_des_moindres_carrés. Il faut expliquer pourquoi les réponses qui ont été données ne sont pas satisfaisantes.
je cherche l'algo complet de régression linéaire.
A savoir j'ai n points et je veux l'équation de la droite s'en rapprochant le plus (en 2D).
Merci
Bien cordialement
Cependant, il y a différentes définitions de " la droite s'en rapprochant le plus", la seule qui est vraiment et généralement utilisée est " la droite s'en rapprochant le plus au sens des moindres carrés", c'est-à-dire une droite d'équation y=ax+b choisie de façon que la somme des $(y_i-(ax_i+b))^2$ soit la plus faible possible.
On peut trouver la droite qui rend la somme des distances aux points minimale, mais c'est nettement plus compliqué, sans que ça apporte quelque chose de plus.
Donc encore une fois, que veut dire pour toi " la droite s'en rapprochant le plus" ?
Cordialement.
Par exemple dans ce document, au bas de la page 33(la première) deux dernières lignes..
Cordialement.
L'instruction Python np.polyfit(x,y,1) où x et y sont des tableaux de n nombres donne les coefficients de la droite.
Cordialement,
Rescassol
Bonjour,
Il y a plusieurs exemples différents, selon le critère de "proximité" dans ce papier, pages 7-8 : https://fr.scribd.com/doc/14819165/Regressions-coniques-quadriques-circulaire-spherique
je me sers des équations de régression linéaire que vous m'avez données mais pour certains exemples comme ceux que je vais vous montrer les résultats sont très décevants.
Voilà mon problème, en reconnaissance d'image je reconnais les contours de feuilles sans les lobes et tente de faire passer une droite sur ces contours. Ces contours sont en vert sur les images suivantes. La droite calculée est en rouge.
Voici les images :
http://sylvain-ard.fr/temp/regression_lineaire/droiteDeLaFeuille.jpg
http://sylvain-ard.fr/temp/regression_lineaire/gaucheDeLaFeuille.jpg
la liste des points de chaque contour est ici :
http://sylvain-ard.fr/temp/regression_lineaire/droite.csv
http://sylvain-ard.fr/temp/regression_lineaire/gauche.csv
les équations calculées sont ici :
http://sylvain-ard.fr/temp/regression_lineaire/droites.txt
Merci de me dire si avec d'autres équations on peut avoir des résultats meilleurs. Je pense que les résultats sont mauvais car les droites sont quasi-verticales.
Merci
Bien cordialement
http://sylvain-ard.fr/temp/regression_lineaire/IMAGE.jpg
Tes fichiers de points ne sont pas terribles.
Tu ne pourrais pas donner quelque chose de plus précis qui ressemblerait très grossièrement au contour de ta feuille ?
Cordialement,
Rescassol
Qu'est ce que tu veux faire avec ça ?
On ne peut rien tirer d'un modèle qui ne correspond pas à la situation étudiée.
De plus, tes fichiers contiennent $650$ points chacun alors que $4$ pour l'un et $5$ pour l'autre suffisent.
Cordialement,
Rescassol
Si, c'est de la reconnaissance de forme : as-tu pensé aux réseaux de neurones ?
Cordialement
Non, la régression linéaire n'est pas adaptée.
S'il s'agit de voir si $4$ ou $5$ points sont coplanaires, le problème est tout autre.
Cordialement,
Rescassol
Il y a plusieurs exemples différents, selon le critère de "proximité" dans ce papier, pages 7-8"
c'est ça qui m'intéresse
"Moindres carrés des écarts de distances"
http://sylvain-ard.fr/temp/regression_lineaire2/
mon code est :
Je remet ce problème dans un nouveau sujet pour faire plus propre.
Je travaille actuellement sur un projet de génération de la description botanique textuelle de feuilles d'arbre sur scan en 600 DPI.
Parmi les multiples problèmes posés, se pose la question de savoir si les marges gauches et droites de la feuilles sont "linéaires" (forment à peu près une ligne droite).
Pour cela je tente de faire passer une droite sur les contours gauches et droits de la feuille et calcule l'erreur (moyenne des distances des points à la droite) pour avoir ma réponse.
J'ai essayé d'implémenter la régression linéaire par écart de distances de ce papier : https://fr.scribd.com/document/14819165/Regressions-coniques-quadriques-circulaire-spherique
Sur ces images je cherche à faire coller une droite sur les points verts : http://sylvain-ard.fr/temp/regression_lineaire2/droiteDeLaFeuille.jpg http://sylvain-ard.fr/temp/regression_lineaire2/gaucheDeLaFeuille.jpg
Vous pouvez voir les droites calculées en rouge.
L'image de départ est :
http://sylvain-ard.fr/temp/regression_lineaire2/IMAGE.jpg
Les listes de points sont : http://sylvain-ard.fr/temp/regression_lineaire2/droite.csv http://sylvain-ard.fr/temp/regression_lineaire2/gauche.csv
et mon code est : SVP aidez-moi à voir ce qui ne va pas
Merci.
Bien cordialement.
[Il vaut mieux rester dans la discussion précédemment ouverte. AD]
finalement j'ai trouvé tout seul je pense que la formule du papier n'est pas bonne. J'ai pris la formule de la régression orthogonale sur wikipédia et ça marche !
Voici mon code :
[Mettre une ' ' entre [ et i sinon, l'afficheur du forum le prend pour une bannière BBcode de mise en italique. AD]
La régression linéaire classique donne des rôles différents à l'axe des x et à l'axe des y.
Fais cette expérience : tu prends par exemple 30 points assez aléatoire. Tu calcules la droite de régression qui fitte le mieux tes 30 points : y=ax+b.
Ensuite, tu recommences avec les mêmes données, mais en inversant les axes (x devient y, et y devient x), tu trouves une nouvelle droite, d'équaation x=a'y+b' ...et tu vas constater que la nouvelle droite obtenue n'est pas la symétrique de la première.
Si les 2 droites étaient symétriques on aurait a*a'=1.
Mais tu vas trouver quelque chose de très différent, beaucoup plus petit. Sur le test que j'ai fait, j'ai trouvé a*a' proche de 0.3.
Quand la droite recherchée est plus ou moins parallèle à l'axe des x, la méthode des moindres carrés marche bien. Mais elle ne marche pas du tout quand la droite recherchée est plus ou moins parallèle à l'axe des y.
Il faut passer par un changement de repère.
Ou sinon, passer à une méthode différente, la régression orthogonale.
Ce n'est pas si mauvais que ça.
Cordialement,
Rescassol
Je me demandais : pourquoi écris-tu tant de code pour une régression simple ? Est-ce qu'il n'y a pas une fonction qui te permettrait de la faire ? De plus, il y a une quantité qui pourrait t'aider à dire si les ajustements linéaires, que tu fais, sont de bonne qualité.
Cordialement.