"Fitter" un cercle avec un nuage de points

systeme.png
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.
«1

Réponses

  • Bonjour,

    J'ai cherché la signification du mot "fitter".
    J'ai trouvé du bridge, mais pas de cercle.

    Cordialement,

    Rescassol
  • fitter, dans ce contexte, on va pouvoir le traduire par 'coïncider'
    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.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • La distance d'un point $A$ à un cercle $C$ est sa puissance $p(A,C)$. Le meilleur cercle est celui qui minimise $$
    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é.
  • je crois qu'il y a eu un petit bug dans le forum car je n'ai pas vu arriver le message de P., ai répondu merci puis le message a disparu puis réapparu avec mon message merci après le message de P. !
  • "fitter", de l'anglais "to fit", = "ajuster".

    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".
  • Bonjour,

    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 .
  • Bonjour,

    Voici un code en Python:
    ###################################################################
    # Régression circulaire aux moindres carrés
    # Rescassol - Mars 2020
    ###################################################################
    # Importations
    ###################################################################
    
    import numpy as np
    import numpy.linalg as la
    
    import matplotlib.pyplot as plt
    
    ###################################################################
    # Fonctions
    ###################################################################
    
    def maxfig():
        mng = plt.get_current_fig_manager()
        mng.window.showMaximized()
    
    ###################################################################
    
    def init1(N):
        T=2*np.pi*np.random.rand(N)
        X=x0+R*np.cos(T)
        Y=y0+R*np.sin(T)
        perturbMax=0.2
        perturbX=perturbMax*(2*np.random.rand(N)-1)
        perturbY=perturbMax*(2*np.random.rand(N)-1)
        # X*=1+perturbX # variante proportionnelle
        # Y*=1+perturbY # variante proportionnelle
        X+=perturbX # variante constante
        Y+=perturbY
    
        return X,Y
    
    def init2(N):
        X=np.random.rand(N)
        Y=np.random.rand(N)
    
        return X,Y
    
    def RegressionCirculaire(X,Y):
        n=len(X)
        D11=n*sum(X*Y)-sum(X)*sum(Y)
        D20=n*sum(X**2)-sum(X)**2
        D02=n*sum(Y**2)-sum(Y)**2
        D30=n*sum(X**3)-sum(X**2)*sum(X)
        D03=n*sum(Y**3)-sum(Y**2)*sum(Y)
        D21=n*sum(X**2*Y)-sum(X**2)*sum(Y)
        D12=n*sum(X*Y**2)-sum(X)*sum(Y**2)
    
        M=np.array([(D20,D11),(D11,D02)])
        B=np.array([(D30+D12)/2,(D03+D21)/2])
        C=la.solve(M,B)
        c=(sum(X**2)+sum(Y**2)-2*C[0]*sum(X)-2*C[1]*sum(Y))/n
        R=np.sqrt(c+C[0]**2+C[1]**2)
    
        return C[0],C[1],R
    
    ###################################################################
    # Script principal de test
    ###################################################################
    
    x0, y0, R = 1.0, 1.0, 1.0
    n = 100
    X,Y=init1(n)
    
    plt.close('all')
    fig=plt.figure(linewidth=10,facecolor = 'gold',edgecolor='red')
    plt.axis('equal')
    plt.plot(X,Y,'ob',markersize=5)
    plt.title('Régression circulaire', fontsize=30, fontweight='bold', color='m')
    plt.xlabel('Nombre de points = '+str(n), fontsize=30, fontweight='bold', color='m')
    
    p=3
    a,b,r = RegressionCirculaire(X,Y)
    print('Cercle(['+str(round(a,p))+','+str(round(b,p))+'],'+str(round(r,p))+')')
    T=np.linspace(0.0,2*np.pi,n)
    X=a+r*np.cos(T)
    Y=b+r*np.sin(T)
    plt.plot(X,Y,'r',linewidth=3)
    
    maxfig()
    plt.show()
    

    Cordialement,

    Rescassol
  • Joli !
  • Bonjour à 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.
  • Le code de Rescassol affiche quelque chose comme ceci.98060
  • Bonjour à Brian,

    La visualisation d'un résultat numérique avec beaucoup de points illustre bien la discussion.

    Bien cordialement,
    JJ.
  • Merci beaucoup à tous
  • Je vois un petit problème dans le script Python :
    Y=x0+R*np.sin(T) ne devrait-il pas être Y=y0+R*np.sin(T)
  • Bonjour,

    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
  • Bonjour,
    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
  • Bonjour,

    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,

    Rescassol98158
    98160
  • Bonjour Sylvain Ard,

    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é.
  • Rebonjour,
    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.
  • Bonjour,

    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 veux dire un algo qui minimise la somme des distances de chaque point avec le bord du cercle car en effet sur mon exemple, un cercle de très grand rayon pourrait minimiser plus cette valeur que le cercle de l'algo, je pensais que la régression circulaire consistait justement en cela
  • Bonjour,
    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
  • Il y a des tas de cours sur le sujet sur Internet.

    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.
  • au sens des moindres carrés, je parle, ce que je cherche est un algo en pseudocode par exemple
  • Comme c'est un calcul, les formules suffisent.
    Par exemple dans ce document, au bas de la page 33(la première) deux dernières lignes..

    Cordialement.
  • merci je venais de trouver la même solution par Wikipédia
  • Eh oui, c'est ce que j'avais fait !!
  • Bonsoir,

    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
  • @ Sylvain Ard

    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
  • Bonjour,
    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
  • Bonjour,

    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
  • non je peux pas ce sont les fichiers bruts des points et ce ne sont pas les contours de la feuille mais les contours en vert sur les images
  • Bonsoir,

    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,

    Rescassol104922
  • Bonsoir,

    Si, c'est de la reconnaissance de forme : as-tu pensé aux réseaux de neurones ?

    Cordialement
  • oui je vais utiliser les réseaux de neurones pour d'autres parties du logiciel mais là il s'agit de dire si les côtés de la feuille sans tenir compte des lobes sont planes ou pas donc je prends l'enveloppe convexe, puis je tire les contours du flan cette enveloppe puis je fais une régresssion linéaire et calcule l'erreur
  • je crois qu'il y a plusieurs façons de calculer une régression linéaire par différentes façons de calculer l'erreur, merci donc de me dire si l'une d'entre elles serait mieux adaptée à mon cas
  • Bonjour,

    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
  • c'est pas s'ils sont coplanaires, c'est trouver la droite qui passe le plus près de ces points pour en calculant l'erreur voir si ces points "forment une droite" ou pas
  • "
    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
  • je pense que ce qu'il me faut est :
    "Moindres carrés des écarts de distances"
  • J'ai essayé d'implémenter la régression linéaire avec écart de distances mais les résultats sont catastrophiques :
    http://sylvain-ard.fr/temp/regression_lineaire2/
    mon code est :
    Straight::Straight(vector<Point> points) {
    	double moyX = 0;
    	for (int i = 0; i < points.size(); i++) {
    		moyX += points[ i].x;
    	}
    	moyX /= points.size();
    	double sommeA=0;
    	for (int i = 0; i < points.size(); i++) {
    		sommeA+=points[ i].y*points[ i].y;
    	}
    	double sommeB=0;
    	for (int i = 0; i < points.size(); i++) {
    		sommeB+=points[ i].y;
    	}
    	double sommeC=0;
    	for (int i = 0; i < points.size(); i++) {
    		sommeC+=points[ i].x*points[ i].x;
    	}
    	double sommeD=0;
    	for (int i = 0; i < points.size(); i++) {
    		sommeD+=points[ i].x;
    	}
    	double sommeE=0;
    	for (int i = 0; i < points.size(); i++) {
    		sommeE+=points[ i].x*points[ i].y;
    	}
    	double numerateur=0.5*(points.size()*sommeA-sommeB*sommeB-points.size()*sommeC+
    	sommeD*sommeD);
    	double denominateur=points.size()*sommeE-sommeB*sommeD;
    	
    	if (denominateur == 0)
    	{
    		this->vertical = true;
    		this->x = moyX;
    	}
    	else
    	{
    		double c = numerateur / denominateur; 
    		this->slope = c+sqrt(c*c+1);
    		this->originOrdinate = (1/points.size())*(sommeB-(this->slope)*sommeD);
    		this->vertical = false;
    	}
    }
    
  • Bonjour
    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 :
    double moyX = 0;
    	for (int i = 0; i < points.size(); i++) {
    		moyX += points[ i].x;
    	}
    	moyX /= points.size();
    	double sommeA=0;
    	for (int i = 0; i < points.size(); i++) {
    		sommeA+=points[ i].y*points[ i].y;
    	}
    	double sommeB=0;
    	for (int i = 0; i < points.size(); i++) {
    		sommeB+=points[ i].y;
    	}
    	double sommeC=0;
    	for (int i = 0; i < points.size(); i++) {
    		sommeC+=points[ i].x*points[ i].x;
    	}
    	double sommeD=0;
    	for (int i = 0; i < points.size(); i++) {
    		sommeD+=points[ i].x;
    	}
    	double sommeE=0;
    	for (int i = 0; i < points.size(); i++) {
    		sommeE+=points[ i].x*points[ i].y;
    	}
    	double numerateur=0.5*(points.size()*sommeA-sommeB*sommeB-points.size()*sommeC+
    	sommeD*sommeD);
    	double denominateur=points.size()*sommeE-sommeB*sommeD;
    	
    	if (denominateur == 0)
    	{
    		this->vertical = true;
    		this->x = moyX;
    	}
    	else
    	{
    		double c = numerateur / denominateur; 
    		this->slope = c+sqrt(c*c+1);
    		this->originOrdinate = (1/points.size())*(sommeB-(this->slope)*sommeD);
    		this->vertical = false;
    	}
    
    SVP aidez-moi à voir ce qui ne va pas
    Merci.
    Bien cordialement.
  • J'ai créé un nouveau sujet pour ne pas polluer celui-là qui était dédié à la régression circulaire.

    [Il vaut mieux rester dans la discussion précédemment ouverte. AD]
  • Rebonjour,
    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 :
    Straight::Straight(vector<Point> points) {
    	double moyX = 0;
    	double moyY = 0;
    	for (int i = 0; i < points.size(); i++) {
    		moyX += points[ i].x;
    		moyY += points[ i].y;
    	}
    	moyX /= points.size();
    	moyY /= points.size();
    	double sommeA=0;
    	for (int i = 0; i < points.size(); i++) {
    		sommeA+=(points[ i].x-moyX)*(points[ i].x-moyX);
    	}
    	double sommeB=0;
    	for (int i = 0; i < points.size(); i++) {
    		sommeB+=(points[ i].y-moyY)*(points[ i].y-moyY);
    	}
    	double sommeC=0;
    	for (int i = 0; i < points.size(); i++) {
    		sommeC+=(points[ i].x-moyX)*(points[ i].y-moyY);
    	}
    	double erreur = 0;
    	cout << "sommeC = " << sommeC << endl;
    	if (sommeC == 0)
    	{
    		cout << "vertical" << endl;
    		this->vertical = true;
    		this->x = moyX;
    		for (int i = 0; i < points.size(); i++) {
    			erreur += this->getDistance(points[ i]);
    		}
    	}
    	else
    	{
    		double C=0.5*(sommeA-sommeB)/(2*sommeC);
    		this->slope=-C+sqrt(C*C+1);
    		this->originOrdinate=moyY-this->slope*moyX;
    		double erreur1 = 0;
    		for (int i = 0; i < points.size(); i++) {
    			erreur1 += this->getDistance(points[ i]);
    		}
    		this->slope = -C - sqrt(C*C + 1);
    		this->originOrdinate = moyY - this->slope*moyX;
    		double erreur2 = 0;
    		for (int i = 0; i < points.size(); i++) {
    			erreur2 += this->getDistance(points[ i]);
    		}
    		if (erreur1 > erreur2) {
    			erreur = erreur2;
    			this->slope = -C - sqrt(C*C + 1);
    		}
    		else
    		{
    			erreur = erreur2;
    			this->slope = -C+ sqrt(C*C + 1);
    		}
    		this->originOrdinate = moyY - this->slope*moyX;
    		this->vertical = false;
    	}
    	
    	this->error=erreur/points.size();
    }
    

    [Mettre une ' ' entre [ et i sinon, l'afficheur du forum le prend pour une bannière BBcode de mise en italique. AD]
  • Tout à fait.
    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.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • Bonjour,

    Ce n'est pas si mauvais que ça.

    Cordialement,

    Rescassol104966
  • Bonjour,

    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.
Connectez-vous ou Inscrivez-vous pour répondre.