Discussion :

[Clad3]

Re-bonjour a tous
Me voici dans la dernière ligne droite de mon projet ... et malheuresement j'obtient des résultat plus qu'incertain :/
Je suis presque sur qur mes valeurs sont bonnes , mais que les erreurs viennent des calculs matricielle .

J'ai donc un systéme de type AX = B a résoudre .

2 cas : le premier , A est une matrice (n,n ) ,X est une matrice ( n,1) et B une matrice (n,1) .
-> dans ce cas, j'ai décomposé A en 2 matrice LU ( Lower-Upper ) , puis je résound le système de facons simple ( forward subsitution / backward susbtituion )

2 éme cas , A est une matrice ( m,n ) avec m > n ; X est une matrice ( n,1) et B une matrice (n,1) ; j'ai donc un systéme surdéterminé . j'ai trouvé sur le web que cela revenais au meme de résoudre

CX = D ;
avec C = trans(A)*A
avec D = trans(A)*B
C, matrice (n,n )
D matrice (n,1 )

La théorie c'est bien beau ( enfin en espérant que je n'ai aps fait d'erreur a ce niveau la... c'est pas sur ) . Mais en pratique ca coince .

Dans les 2 cas , je calcule ma matrice A en fonction des coordonées de paires de point homologue sur 2 images différente . La matrice final ( X ) étant la meme quelque soit les 8 point selectionné ( en théorie ) , il me parait juste que pour 8 paire de point donnée, l'ordre de sélection des point importe peu .... ors ce n'est pas du tout le cas, et selon l'ordre dans lequel je sélectionne mes point, j'obtient des résultat totalement différent .

De plus, lors de la résolution de mon système sur-déterminé, j'obtient des résultat tout aussi peu précis que avec mon premier algo et seulment 8 points .

De plus, il faut précise que pour le pemier algo, les point sont selectionné a la main ( donc peu de précision ) ; dans le second ils sont selectionné par un autre algo ( donc gain de précision ) ...

Je ne sais plus trop ou chercher ...si vous avez des idées

[ceugniet]

j'ai trouvé sur le web que cela revenais au meme de résoudre

CX = D ;
avec C = trans(A)*A
avec D = trans(A)*B
C, matrice (n,n )
D matrice (n,1 )

Cela ne revient pas au même. Il faut le dire différemment. En fait si tu as plus de lignes que de colonnes (plus d'équations que d'inconnues) deux cas peuvent se produire. Soit certaines lignes peuvent se déduire d'autres (malgré qu'il y a m lignes (m>n) le rang r de ta matrice A est inférieur ou égal à n) alors effectivement ton système est équivalent à CX=D : à prendre dans le sens de "il a les mêmes solutions". C'est-à-dire, que si le r = n la solution ton système CX=D sera solution de AX=B. Et si r<n toutes les solutions de CX=D (une infinité) seront solutions de AX=B.

Par contre si le r est supérieur à n, alors AX=B n'a pas de solutions. Il peut être intéressant (ça dépend de ton problème évidemment) de chercher X tel que AX soit "le plus proche possible" de B, dans un certain sens. Résoudre CX=D te donnera le vecteur X qui minimisera la norme L2 de AX-B : on dira que tu as minimisé AX-B au sens des moindres carrés.

Donc dire que "cela revient au même" est inexact. On a un problème impossible (sans solution), et on cherche un X qui vérifie au mieux possible les conditions imposées, au sens des moindres carrés, étant entendu qu'aucun X ne vérifie exactement les m équations.

Si

La matrice final ( X ) étant la meme quelque soit les 8 point selectionné ( en théorie ) , il me parait juste que pour 8 paire de point donnée, l'ordre de sélection des point importe peu .... ors ce n'est pas du tout le cas, et selon l'ordre dans lequel je sélectionne mes point, j'obtient des résultat totalement différent .

alors, c'est que tu as fait une erreur de programmation, car ta théorie est correcte !

[Clad3]

Cela ne revient pas au même. Il faut le dire différemment. En fait si tu as plus de lignes que de colonnes (plus d'équations que d'inconnues) deux cas peuvent se produire. Soit certaines lignes peuvent se déduire d'autres (malgré qu'il y a m lignes (m>n) le rang r de ta matrice A est inférieur ou égal à n) alors effectivement ton système est équivalent à CX=D :

Si je comprend bien, si certaine ligne sont des multiple d'une autre, on se retrouve dans ce cas la ( avec n lignes non proportinel entre elles ) .

Et si r<n toutes les solutions de CX=D (une infinité) seront solutions de AX=B.

Dans ce cas, on a donc moins d'équation que d'inconnu c'est ca ?

Par contre si le r est supérieur à n, alors AX=B n'a pas de solutions. Il peut être intéressant (ça dépend de ton problème évidemment) de chercher X tel que AX soit "le plus proche possible" de B

La on est dans mon cas, + d'équation que d'inconnnu, c'est bien ca?
et en effet, mon but est de trouver des valeur de mes inconnu qui sataisfassent " au mieux " mon système AX=B .

dans un certain sens. Résoudre CX=D te donnera le vecteur X qui minimisera la norme L2 de AX-B : on dira que tu as minimisé AX-B au sens des moindres carrés.

Je n'ai pas tout saisie, mais dans l'ensemble, ca veut dire que j'ai employée la bonne méthode ,non ?

Donc dire que "cela revient au même" est inexact. On a un problème impossible (sans solution), et on cherche un X qui vérifie au mieux possible les conditions imposées, au sens des moindres carrés, étant entendu qu'aucun X ne vérifie exactement les m équations.

Je crois qu'on est d'accord , je ne peux pas trouver des solutions exactes, mais des solutions approché . C'est qu'il me faut d'ailleur ...

Aprés, savoir ou j'ai une erreur d'implémentation c'est vraiment une autre paire de manche .. je ne sais aps trop comment débusquer ca ... voir meme aps du tout :/

EDIT : j'ai *peut-etre* une pist concernant mes erreurs :
http://www-igm.univ-mlv.fr/~vnozick/ENSEIGNEMENTS/IMAC1/IMAC1B/epipolaire.pdf

Avec seulement 8 points ( système non surdéterminé ) j'ai procédé comme indiqué .

Avec + de 8 point , mon systeme AX=B ... ( initialement B = 0 ) , je l'ai transformé en B(8,1) avec B(i,1) = -1 ... alors que eux .. je pense pas que j'ai le droit de faire ca .

En gros, je ne vois aps comment transformer B de facons a ce que ces coef ne soient pas tous nul avec un systéme surdéterminé ( exemple avec un syste NON surdéterminé page 4->5 du pcf ci dessus ).

[ceugniet]

Si je comprend bien, si certaine ligne sont des multiple d'une autre, on se retrouve dans ce cas la ( avec n lignes non proportinel entre elles ) .

Tu comprends presque bien. Le problème ne survient pas uniquement si certaines lignes sont proportionnelles à d'autres, mais plus généralement si certaines lignes sont combinaisons linéaires d'autres ; par exemple si (ligne 1) = 18,53 * (ligne 2) + pi * (ligne 5) !

Dans ce cas, on a donc moins d'équation que d'inconnu c'est ca ?

Oui

La on est dans mon cas, + d'équation que d'inconnnu, c'est bien ca?

Oui

Je n'ai pas tout saisie, mais dans l'ensemble, ca veut dire que j'ai employée la bonne méthode ,non ?

Si ! Tu as employé la bonne méthode.

EDIT : j'ai *peut-etre* une pist concernant mes erreurs :
http://www-igm.univ-mlv.fr/~vnozick/ENSEIGNEMENTS/IMAC1/IMAC1B/epipolaire.pdf

Je vais voir ça, si j'ai le temps. Mais je persiste, ta méthode est bonne au niveau du calcul matriciel : il faut chercher le bug ailleurs. Il y a bien sûr l'interprétation du texte que tu mentionnes. Mais il y a aussi, la traduction de la multiplication de matrices, de la transposition, etc... Peut-être tout simplement une bête erreur de programmation ou une faute de frappe (i au lieu de j : c'est si vite fait un bug introuvable !)

Bon courage !

[Clad3]

Ups, ui, combinaison linéaire c'est vrai

heu sinon ... et bien je vais traqué le petit engrenage qui casse ma chaine

Enfin la multiplication de matrice et la transposée sont géré par une lib annexe , donc ca devrais allez de ce coté la .

Bon et bien , je vais voir ca
En attendant si qqun a une idée ...

[ceugniet]

A cause de tous ces indices et exposants, je t'ai écrit une réponse sous word, et j'ai fait une copie d'écran.
Va voir
http://cjoint.com/?gupj0XekJC

[Clad3]

Le lien a pas marché

[ceugniet]

Le lien a pas marché

Ouais, ça ne marchait pas. Essaie encore !

[Clad3]

D'accord, en faite mon erreur a été de mettre B ( 8,1 ) au lieu de B ( nbre_de_points,1) ...
En tout cas, trés jolie dessein, merci beaucoup

Je vais de ce pas rempalcer B par ce qu'il faut et voir ce que ca change, je revient d'ici quelques minutes ...

[Clad3]

Ca a surement aidé, mais j'obtient toujours des résultats non cohérents :/
Il doit y avoir d'autres erreurs ...

edit: voila le code qui me calcule la matrice :

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
void cFcompute::getF_Moravec(matrix<double> & F,
						 std::vector<cVector2D> s1_match ,
						 std::vector<cVector2D> s2_match , int nbre) 
{
 
	// Pour trouver F, on va resoudre AG = 0  ... G ~ F mais en vecteur colonne
	matrix<double> B(nbre,1) ;
	matrix<double> G(8,1) ; 
 	matrix<double> A(nbre,8) ; 
 
	for ( int i = 0 ; i < (nbre-1) ; i ++ )
	{
		B(i,0) = -1 ; 
		G(i,0) = 0 ;  
	}
 
	// On va ensuite initialiser notre matrice A avec les valeurs (x,y) (x',y') des couples de pixels .
	for ( int j = 0 ; j < nbre ; j++ )
	{
		cVector2D & v1 = s1_match[j] ;
		cVector2D & v2 = s2_match[j] ;
 
		A(j,0) = v2.X * v1.X ;
		A(j,1) = v2.X * v1.Y ;
		A(j,2) = v2.X ;
		A(j,3) = v2.Y * v1.X ;
		A(j,4) = v2.Y * v1.Y ; 
		A(j,5) = v2.Y ;
		A(j,6) = v1.X ;
		A(j,7) = v1.Y ;
	}
	matrix < double > Aprime(8,8) ;
	matrix < double > Bprime(8,1) ;
 
	Aprime = prod(trans(A),A);
	Bprime = prod(trans(A),B);
 
	LU_manager.solveLU(Aprime,G,Bprime,8) ;
 
	// Reconstruction de F
	F(0,0) = G(0,0) ;     F(0,1) = G(1,0) ;     F(0,2) = G(2,0) ;
	F(1,0) = G(3,0) ;     F(1,1) = G(4,0) ;     F(1,2) = G(5,0) ;
	F(2,0) = G(6,0) ;     F(2,1) = G(7,0) ;     F(2,2) = 1 ;
 
 
}

Pour info les vector s1_match et s2_match contiennent les point homologue ( j'ai vérifié ) aucun pb a ce niveaux la !
s1_match[i] est bien l'homologue de s2_match[i] .

Enfin aprés ca peut venir de ma facons de résoudre effectivement le systéme ... OU de ma facons de calculer les épipole / droite épipolaire , OU de ma facons de les afficher ( je doute que ce soit ce dernnier points ; quand aux autre, je ne suis pas plus avancé . )

[ceugniet]

Je ne connais pas le langage que tu utilises, alors je suis un peu perdu sur tes définitions de tableaux. Pourquoi B est-il dimensionné à (nbre,1) alors que G n'est dimensionné qu'à (8,1). Juste en dessous tu définis
g(nbre-2,0) ! Peut-être tes tableaux sont-ils définis ailleurs ?

matrix<double> B(nbre,1) ;
matrix<double> G(8,1) ;
matrix<double> A(nbre,8) ;

for ( int i = 0 ; i < (nbre-1) ; i ++ )
{
B(i,0) = -1 ;
G(i,0) = 0 ;
}

Et je ne comprends pas d'où vient cette initialisation de B(i,0) à -1. Pas plus que l'initialisation de G(i,0) à 0. Apparemment, G va recevoir le résultat de la résolution, pourquoi l'initialiser et en partie seulement ?
En effet, on ne sait pas la valeur de nbre, mais je sens que c'est 8. Ai-je tort ? Est-ce plutôt 9 ? Oui peut-être. Au moins dans ce cas, il est souhaitable, pour un code clair, de décider que c'est 9 une fois pour toutes, ou de décider que c'est nbre une fois pour toutes. Si la dimension de ton système est nbre-1, alors il faut écrire nbre-1 dans ton appel à LU_manager.solveLU(Aprime,G,Bprime,8), et pas 8. Ca complique tout !!!

Je n'ai pas tout lu...
C'est très dur de se faire une idée comme ça au saut du lit...Ca manque un peu de commentaires...En fait, à la réflexion, je crois que les w sont tous égaux à 1. Dans ce cas, cela justifie le b[i,0)=-1. Il est bien possible que ton code soit correct ! Mais manque de clarté, manque de commentaire, et manque d'homogénéité (un coup 8, un coup nbre-1,...) ça rend le code beaucoup plus ardu à décrypter. Finalement, peut-être l'erreur est-elle ailleurs...

[Clad3]

;o Moi qui pensais que c'étais transparent ... dsl
je vais expliquer tout ca :

En effet B est initialiser a -1 car tout les w(i) sont supposé egale a 1 .
G est ma matrice d'inconnu , j'ai 8 inconnu quoi qu'il arrive .
G est initialisé a zéro par commodité, ca evite d'avoir des valeur non définit et des comportement non prévisible aprés ...

Et je ne l'initialise aps en partie, mais en totalité, cela vient du faite que boost ( ma lib de matrice ) compte les valeur de 0 a n-1 et initilise a n dimension .


Je n'ai donc pas a décider entre nbre et 8 ou 9 ou je ne sais quoi , le nonbre de point homologue est simplement passé en paramètre de la fonction .

Lors de l'apelle a mon Lu_manager, je passe la dimension des matrice, soit 8 . Il suffit de regarder la dimension des matrice Aprime, Bprime .

Manque de commentaire d'accord, d'homogénéité, je ne pense pas :p

/me retourne a la recherche de *the faute*

[ceugniet]

Très bien, alors expliques moi pourquoi, alors que B est dimensionné à nbre, c'est à dire avec des indices allant de 0 à nbre-1 inclus, tu éprouves le besoin d'initialiser seulement de B(0,0) à B(nbre-2,0) : b(nbre-1,0) n'est pas initialisé : il ne sera jamais défini, mais il me semble qu'il est utilisé (dans Bprime = prod(trans(A),B)) et par conséquent la valeur quelconque qu'il a va sans doute perturber le calcul de Bprime. Pourquoi alors que G est dimensionné à 8, soit avec des indices allant de 0 à 7 inclus, tu éprouves le besoin d'initialiser G(i,0) pour i allant de 0 à nbre-2 inclus. Je devine que nbre doit être au moins égal à 9, que nbre-1 au moins égal à 8, mais comme G est dimensionné à 8 et que nbre peut être 20 ou 30, il n'est pas sain de faire une boucle de i=0 à i=nbre-2 inclus qui définit G(i,0) ! Si tu utilises ce code avec nbre>9, tu vas écraser quelque chose hors de ton tableau G...

[Clad3]

Tout juste auguste
Il faut en effet faire une 2eme boucle pour initialiser G(i) a ééro , pour i = 0 to 8 .
Dsl ...

[Clad3]

Je vient de re-lire a fond ma méthod pour calculer les equation des droite ( résultat visible lié a cette matrice calculer précédement ) et je ne vois pas d'erreur . De meme pour mon solveur d'équation, je debug A et BX et j'obtient bien les meme matrices ... mystére ... ou se trouve le pb ;o)

EDIT : net progrés ! je fait encore quelque test pour re-centrer le problème ...
EDIT 2 :
- avec 8 point ou plus , l'ordre de sélection importe toujours .
- avec plus de 8 point lorsque j'obtient des valeur de ma matrice X ( dans AX=B ) de l'ordre de e^240 ... ce qui fausse des calcul en aval .
EDIT3 : le probléme est réglé ( il s'agissait d'un bete erreur d'indice )

Sinon il rest d'actualité :
- probléme lié a l'ordre des points , et des probléme de précision ..que ce soit avec 8 points ou plus, selon les paire de points, on obtient des résultat différent .... ( enfin remarque, c'est pas étonnant vu que deja avec 8 point identique mais aps sasie dans le meme ordre ca déraille lol )

[Caine]

J'ai lu le fil en diagonale, je note une manque de méthode dans tes tests.

J'ai l'impression que tu ne testes pas tes modules en "unitaire" avant de te lancer dans les Algos finaux qui mélangent les modules.

D'expérience, les tests unitaires doivent être le plus simple possible, du type automatiqe avec des valeurs référentielles connues (entrées => Résultats).

[Clad3]

Je vois ce que tu veux dire .
Tu veux dire qu'il faut que je teste une à une chacun de mes algo, avec en entré quelque chose dont je connias le résultat en sortie et que je vérifie .
C'est ce que je fait ... Mais dans ce genre de choses , les résultats sont difficilement appréciable :/ ( je n'ai aucun moyen de savoir par exemple OU se trouve exactement l'un des épipole ... je ne le saurais que lorsque mon algo trouvera une position donné a un % d'erreur donné a tout les coups .

Enfin, merci du conseil quand meme

[ceugniet]

Sinon il rest d'actualité :
- probléme lié a l'ordre des points , et des probléme de précision ..que ce soit avec 8 points ou plus, selon les paire de points, on obtient des résultat différent .... ( enfin remarque, c'est pas étonnant vu que deja avec 8 point identique mais aps sasie dans le meme ordre ca déraille lol )

Euh, ben, c'est-à-dire, je sais pas !

Ca me rappelle quelque chose...

Un jour je devais calculer a*c-b*d, tout simplement et mes résultats étaient complètement aberrants...Je ne me souviens plus des détails alors j'invente : en fait a*c était de l'ordre de 10**20, comme b*d, mais a*c-b*d était plutôt de l'ordre de 10**-20... Ceci explique cela.

Pour revenir à ton problème, ça voudrait dire matrice mal conditionnée. La probabilité que cela se produise diminue si tu as un grand nombre de points (nbre) mais ne s'annulle pas : c'est toujours possible.

Si tu ne l'as pas encore fait, je te suggère, une fois que tu as résolu AX=B, de vérifier AX et de comparer à B : imprimer AX, imprimer B, imprimer AX-B. Bien sûr, je ne mets pas en doute ton solveur : je soupçonne simplement une erreur d'indice quelque part, ou une matrice mal conditionnée. Vérifier le résultat du solveur me paraît la première chose à faire.

Et puis, si j'étais à ta place : aux grands maux les grands remèdes : je ferais une simultation. Tu crées une scène avec une vingtaine de points, tu calcules leur images par deux projections de deux points de vue différents. Et tu utilises cette scène simulée pour retrouver les trois coordonnées x,y,z de chacun des points. Tu devrais finalement trouver où ça coince ... Je sais que ça c'est un gros boulot, un grand remède quoi ! Mais, je n'ai rien d'autre à proposer...

Edit : Dailleurs, la vérification des résultats du solveur d'une part, la simulation d'autre part, se rapprochent beaucoup de ce que suggère Caine, que je viens de découvrir juste après avoir posté ma réponse...

[Clad3]

Mon solveur marche trés bien , j'ai testé plusieur fois d'afficher AX et B cela donne le meme résultat

Par contre, je ne saisie pas par quoi se traduit "mal conditionné" en terme de matrice, ca veux dire que tu pense qu'il y a une erreur dans mon algo ? ou alors que c'es inhérent au problème et que je ne peut rien y faire a part prendre plus de point ?

Heu concernant la simulation , je crois que c'est peu radical . Et je pense que pour trouver mon erreur concernant le pb de l'ordre des points influencant ma matrice, ca risque de prendre une éternité .. sachant qu'il y a toujours le risque que le pb viennent d'autre part et qu'il me manque tout bonnement une piéce du puzzle ( un prétratement , un calcul supplémentaire ect ... )
Enfin bref, l'idée est bonne, mais la réalisation est un peu difficile

J'ai passé mon code a la loupe sans arrêt depuis 2 jours, je epnse avoir trouvé la plsupart des erreurs , non sans mal , et grace a votre aide

Je m'oriente plus vers la recherche de nouvelle technique .

je pense ( *pense* car je n'ai trouvé nul part quelque chose qui m'influencerai a penser ca ou le contraire ) ... que j'obtient des résultat normal comtpe tenu de ce que je fait .
En effet, je pense que ce genre de méthode ( moindre carré ) doit surtout être apppliqué avec beaucoup de points ( > 50 ) et moi j'en utilise 11-12 ...

Enfin j'hesite, car j'ai encore du mal a expliquer les résultat du a l'ordre de selection des points ... mais d'un autre coté, je n'ai lu nul part que ca DEVAIT marcher pour 8 point dans n'importe quel ordre ...

bref, ... je vais continuer a fouiner, et encore merci pour votre aide ca me donne de nouvelle piste dans mes recherches !

[ceugniet]

Par contre, je ne saisie pas par quoi se traduit "mal conditionné" en terme de matrice, ca veux dire que tu pense qu'il y a une erreur dans mon algo ? ou alors que c'es inhérent au problème et que je ne peut rien y faire a part prendre plus de point ?

D'abord, je ne pense rien : je cherche quelles sont les possibilités d'obstacles à la résolution de ton problème. Donc, j'envisage ceci ou cela, sans avoir aucune idée préconçue (et pour cause) sur le fait que "ça doit être ceci" ou "ça doit être cela".

Ceci posé, je précise ce que j'entends par mal conditionné : c'est l'exemple ac-bd que j'ai donné dans mon post précédent. Si j'ai un système de deux équations à deux inconnues ax+by=e, dx+cy=f, le déterminant est ac-bd. Quelle que soit la méthode employée, le résultat du solveur utiliseras (ac-bd) au dénominateur. Il y a de fortes chances que ce sera 0 dans l'exemple ci-dessus, ce qui arrêtera le solveur. Mais cela peut aussi être 10**5 alors que le vrai résultat est 10**-20 ! D'où panique du solveur qui n'y est d'ailleurs absolument pour rien : c'est la précision de la machine qui empêche le calcul d'être exact !

Ça c'était pour répondre à ta question. Mais ne t'inquiète pas, la vérification que je t'ai suggérée et que tu avais déjà faite (imprimer AX et B) suffit à montrer que la matrice est bien conditionnée. Elle doit être fausse, pour d'autres raisons, à trouver, mais elle est bien conditionnée...

Bon courage !