Discussion :

[MDiabolo]

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.

[MDiabolo]

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.

[Matthieu Brucher]

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 -

[MDiabolo]

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.

[Matthieu Brucher]

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.

[MDiabolo]

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.

[larnicebafteur]

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.

[Matthieu Brucher]

Faire un tel algorithme sur une fonction dérivable 2 fois, c'est un peu... sous optimal ?