Discussion :

[walks]

Bonjour a tous!

Je m'interesse a la question du best fit d'un nuage de points (x,y) par une ellipse, en utilisant Matlab. Voici le bout de code concerné:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
%determination de l'equation de l'ellipse moyenne
%equation sous la forme ax²+2bxy+cy²+2dx+2fy+g=0
%on fixe g=-1
for i=1:longueur
         X(i,:)=[AA(i,1)*AA(i,1)    AA(i,1)*BB(i,1) BB(i,1)*BB(i,1) AA(i,1) BB(i,1)];
     end
 
Y = ones(size(AA));
int=(inv((X'*X)));
C=int*X';
r=C*Y;

AA et BB etant les matrices des points evidemment (une colonne= les coordonnées x ou y d'un nuage), je cherche donc a resoudre le probleme X.A=Y avec X la matrice(l,5) [x² xy y² x y] calculée a partir de tous mes points, ou l=longueur de mes matrices AA ou BB (meme longueur)
A est ma matrice d'inconnues (a, b, c, d, f) et Y la matrice (l,1) [1]. (on pose g=-1 pour pouvoir resoudre)

Probleme: les resultats obtenus ne sont pas du tout coherent avec l'aspect du nuage (je tombe sur des ellipses avec grand axe>>>petit axe, au point qu'elles ressemblent a une ligne seule) et pourtant mes nuages sont relativement "propres".

Voyez vous une erreur possible dans le calcul ou comment procederiez vous?


2) AU lieu de faire un best fit, est il possible de determiner la plus petite ellipse qui contienne tous les points du nuage?? (ellipse dont l'angle est bien sur non nul cad dont les axes ne sont pas paralleles aux axes du repere)

Cordialement,

walks

[Jean Dumoncel]

Salut,

une petite remarque :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
for i=1:longueur
         X(i,:)=[AA(i,1)*AA(i,1)    AA(i,1)*BB(i,1) BB(i,1)*BB(i,1) AA(i,1) BB(i,1)];

end
s'écrit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

X = [AA.^2 AA.*BB BB.^2 AA BB];

Sinon comment calcules-tu les paramètres de ton ellipses? (centre, petit/grand axe orientation...)

Une contribution du fex qui pourrait t'intéresser :
fit_ellipse

[walks]

Merci de ta remarque, effectivement mon code de toute façon n'est pas forcement optimisé, je suis loin d'etre specialiste des meilleures syntaxes possibles

concernant mes parametres d'ellipse, une fois l'equation determinée sous la forme ax²+2bxy+cy²+2dx+2fy+g=0, ils se calculent de maniere assez simple grace aux formules du site http://mathworld.wolfram.com/Ellipse.html
(formules 19 a 23)

Merci beaucoup pour ton lien, tres interessant mais qui prouve definitivement que je fais un tant soit peu fausse route

Mon probleme n'est pas en fait de faire un best fit d'un nuage de point mais bien de trouver la plus petite ellipse contenant tout mon nuage.....pas vraiment la meme paire de manche.

Pour info, mon algo conceptuel pour le moment est le suivant:

1) Determiner les deux points les plus eloignés de mon nuage => ils definissent le "grand diametre" de mon ellipse
2) Determiner le point le plus eloigné perpediculairement a cet axe => il definit, euuh.... pas grand chose pour l'instant, a part la valeur mini possible pour le demi-petit axe de mon ellipse.
3) En reflexion: phase iterative de construction d'une ellipse en augmentant petit a petit le demi-petit axe jusqu'a ce que tous les points soient a l'interieur??
=> pb1: comment tester cette condition?
=> pb2: il s'avere que le grand axe n'est pas forcement le meilleur possible...algo vaseux?

bref, si des idées peuvent jaillir de vos cerveaux, je suis preneur

Cordialement,

[Jean Dumoncel]

concernant mes parametres d'ellipse, une fois l'equation determinée sous la forme ax²+2bxy+cy²+2dx+2fy+g=0, ils se calculent de maniere assez simple grace aux formules du site http://mathworld.wolfram.com/Ellipse.html
(formules 19 a 23)

Oui, je connais les formules, c'était pour avoir un aperçu complet de ton code, faire des tests rapidement...

Mais bon, finalement ton problème contient une contrainte supplémentaire : tous les points doivent se trouver à l'intérieur de l'ellipse. Du coup, je pense que tu devrais chercher du coté des algos de minimisation : ton problème reviens par exemple à minimiser l'aire (ou le périmètre) de ton ellipse avec la contraintes des points à l'intérieur.

Par exemple, je suis tombé sur cette contribution du file exchange :
Minimum Volume Enclosing Ellipsoid

La méthode que tu as décrites (prendre les 2 points les plus éloignés comme grand axe) impose une contrainte très forte qui élimine de nombreuses solutions et donc tu n'as aucune garantie de trouver la meilleure. Après tout dépend à quel point tu veux t'approcher de la solution optimale...

[walks]

De nouveau merci Magellan, excellente source, cela resoud parfaitement mon probleme...la journée va etre beaucoup moins dure que prevue pour mon ptit cerveau :p
Je n'ai pas encore cherché a comprendre, juste a utiliser, et le resultat pour l'instant visuel semble parfaitement coller.

Pour mon code, il est "inspiré" (traduisez: pompé) du post suivant:
http://www.developpez.net/forums/d37...mes-lineaires/

Si cela t'interesse je peux te faire une copie de mon code mais il n'y a rien de changé par rapport aux sources que j'ai indiqué...

Cordialement,