IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Equation d une sphere a partir d un nuage de points


Sujet :

Algorithmes et structures de données

  1. #21
    Membre averti
    Profil pro
    Inscrit en
    Novembre 2005
    Messages
    46
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2005
    Messages : 46
    Par défaut
    Bon j ai quelques trucs:
    me suis "amusé" dans les parametres cet aprem. Si j augmente la distance separant deux points successifs (dans l echantillonement) et/ou augmente le nombre de points j obtiens un meilleur resultat. Le parametre qui joue le plus etant surtout la distance entre deux points.
    Avant c etait:
    nbPoints = 120
    distanceMinimale = 1

    je suis passe a
    nbPoints = 50
    distanceMinimale = 30

    et ca marche mieux mais pas toujours a cause de cette raison:
    si je decris un mouvement d une grande amplitude (genre de l ordre de 100° ou 180°) ca marche. Par contre si je reste sur une partie plus restreinte de la sphere (ce qui est cense etre l objectif) cela me donne un resultat aberrant ( genre rayon immense, centre decale, sphere ne correspondant pas points echantillones).

    Pour te repondre Miles:
    Je n ai pas encore trouver la reponse a ta question. J utilise une bibliotheque. Les commentaires disent que c est tirer du livre Numerical Recipes. Mais pas plus. Je suis en train de parcourir le source pour voir.

  2. #22
    Membre averti
    Profil pro
    Inscrit en
    Novembre 2005
    Messages
    46
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2005
    Messages : 46
    Par défaut
    Bonjour

    Je reviens un peu sur ce sujet. La fonction de cout utilisee est la suivante:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    double SphereFit::calcCostFunction(const MatrixD& param) const
    	{
     
     
    		Vector3D M =Vector3D(param(0),param(1),param(2));
    		double radius = param(3);
     
    		double SumOfSquareDistance=0;
     
    		for(int i=0; i<m_PointList.size(); i++)
    		{ 
    			double Distance =  M.getDistance(m_PointList[i])-radius;
    			SumOfSquareDistance+=  Distance*Distance;
    		}
     
    		return SumOfSquareDistance;
    	}
    Actuellement l algorithme utilise est un "DownHill simplex". Est il possible d´utiliser facilement un autre algorithme de convergence (comme la descente du gradient) ? Je ne sais pas comment faire.

    Merci d'avanve.

  3. #23
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    Oui, il te suffit de coder le gradient et le hessien - le hessien est nécessaire pour les optimiseurs Newton-like -.
    Ton optimiseur n'est pas optimal car il ne fait aucune hypothèse sur la forme de la fonction alors qu'on sait qu'elle est continue et dérivable 2 fois - et qudratique si je ne me trompe pas ! -, les optimiseurs de Newton sont tout à fait adaptés à cet exercice - comme déjà indiqué par le passé dans ce topic -

  4. #24
    Membre averti
    Profil pro
    Inscrit en
    Novembre 2005
    Messages
    46
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2005
    Messages : 46
    Par défaut
    Merci

    Excuse moi, au risque de passer pour un idiot, mais ou est ce que je peux trouver des infos pour coder le gradient ou le hessien (peut etre que ca existe deja dans une librairie ?), car je n´y connais pas grand chose encore.

    Merci d´avance.

  5. #25
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    Ben il te faut chercher un livre de maths ou chercher sur le net gradient et hessien. Ce n'est pas une histoire de codage, c'est une histoire de calcul. dans ton cas, tu dois faire le calcul de ces éléments - ce sont les dérivées premières et secondes de la fonction de coùut par rapport aux éléments du vecteur paramètres - et ensuite coder la formule résultante.

  6. #26
    Membre averti
    Profil pro
    Inscrit en
    Novembre 2005
    Messages
    46
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2005
    Messages : 46
    Par défaut
    Rebonjour,

    Bon finalement j ai trouvé également une solution qui m´évite de rester coincer dans un mauvais minimum local. Je prends un echantillon (60) de points relativement espacés et je calcule 15 fois le centre et le rayon de la sphere a partir de 4 de ces points a partir de la methode suivante:
    http://astronomy.swin.edu.au/~pbourke/geometry/spherefrom4/

    Puis pour chaque solution trouve je calcule l ecart entre (les points et le centre) et le rayon. J ecarte les reponses un peu douteuses. Je fais la moyenne des solutions restantes.

    Je prends cette moyenne comme le point de départ de l algortihme du Downhill Simplex
    Et ca marche.
    Ca doit pouvoir etre optimiser et etre fait plus elegament mais en tout cas ca a le merite de marcher a tous les coups (a confirmer dans quelques temps) et vite en plus.

    Voila, merci à vous dans ce qui a été ma première rencontre avec l'optimisation.

  7. #27
    Membre actif Avatar de larnicebafteur
    Inscrit en
    Mai 2006
    Messages
    133
    Détails du profil
    Informations forums :
    Inscription : Mai 2006
    Messages : 133
    Par défaut
    Le fait que si les points sont très proches les uns des autres conduit a qqch de faux me semble logique.
    Imaginons un cas simple : trouver une droite qui passe par 2 points.

    Dans un 1er cas, tu prends les 2 poinst très éloignés, et tu trouves une droite. Si tu déplaces legerement un de ces points (car il y a des incertitudes sur la position des points), on comprend bien que la droite ne va pas beaucoup changer.

    Dans le 2ème cas, imaginons que les 2 points soient trés proches. On trouve aussi une droite, mais une petite variation de position de l'un des 2 points conduit à une droite extremement différente ! (faire un essai à la main pour s'en convaincre).

    Moralité, il faut que les points soient le plus espacés possible.

    Sinon, pour l'histoire de determiner LA sphère qui passe par 4 points, de recommencer cette étape plusieurs fois et de moyenner les résultats, cela me semble une mauvaise méthode. Nous ne sommes pas sur un problème linéaire, et certaines sphères obtenues par cette méthode seront totalement fausses.
    Une méthode d'optimisation qui prend globalement tous les points en même temps me semble parfaitement adaptée. Il y a 4 paramètres d'optimisation (XC, YC, ZC et R), et on minimise la somme des carrés des distances.

    Le fait que le problème soit en 3D et non pas en 2D n'augemente pas du tout la compléxité du problème, il y a juste un paramètre en plus. Mathématiquement, c'est pareil.

  8. #28
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    Faire un tel algorithme sur une fonction dérivable 2 fois, c'est un peu... sous optimal ?

Discussions similaires

  1. Approximation d'une droite 3D à partir d'un nuage de points 3D
    Par appouch dans le forum Mathématiques
    Réponses: 2
    Dernier message: 28/09/2009, 14h12
  2. Réponses: 1
    Dernier message: 29/07/2009, 21h23
  3. Réponses: 0
    Dernier message: 27/11/2008, 12h05
  4. affichage d'une courbe a partir d'un tableau de point
    Par topzozo dans le forum Tkinter
    Réponses: 2
    Dernier message: 30/05/2007, 12h19
  5. Dessiner une courbe à partir d'un nuage de points
    Par Bil-Prog dans le forum Windows Mobile
    Réponses: 2
    Dernier message: 26/01/2007, 03h06

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo