Correlation entre points .

Bonjour a tous :)

Oulala j'ai l'impression de passez ma vie sur le forum algorithme ;o)
( enfin ca va, on y est bien, il fait chaud, les gens sont chaleureux et la mer est belle :D )

bref, revenons a nos pb :/ ( hehe y faut bien ... )

Aprés avoir implémenter un détecteur de coins ( Moravec ) , je me retrouve avec deux images , et sur chaqune , une série de points marqué comme point d'interet .
Mon but ? l'étape suivante de ce genre d'algo ; mettre en relation chaque point d'interet d'une image avec l'autre .
Pour cela j'ai testé une méthode qui donne de piètre résultats :

Voici la méthode en question :
- on prend un point ( px, py ) dans l'image 1dont on veux trouver l'homologue dans l'image 2
- on compte le nbre de voisin ( pts dinteret ) dans un rayon R autour du point .
- on se place dans l'image 2 en (px,py) ; on "créer" une fenetre de recherche centré en (px,py); fenêtre de taille X .
- pour chaque point dinteret dans la fenetre , on compte son nombre de voisin dans un rayon R .

Enfin , ca part un peu en freestyle ; on est censé obtenir des points possible correspondant au point de départ .
Pour selectionner celui qui nous interesse ; j'ai essayer de me baser sur l'intensité ( pas top comme résultat ) ...

A part ce dernier détails , ca ne me donne pas du tout de bon résultat ; pour une raison que je crois avoir identifié :

Mes images sont prise de deux point de vue assez différent; donc l'homologue d'un point se trouve dans un fenetre qui fait la moitié de la taille de l'image !! .
Ce qui m'oblige pour avoir un espoir de résultat valide a prendre une fenetre de cherche de trés grande taille .
Ors, plus la fenetre est grande, plus le nombre de point possible est élevè ; et comme je n'ai aucun critére fiable pour selectionner le candidat le plus probable parmis ceux possible, mon problème en est décuplé :/

Si vous avez d'autre méthode ( si possible pas "TROP" exigante niveau math ) ou alors des bon critéres pour départager mes candidat possible ; je suis preneurs .

( j'ai pensé a "augmenter" le critère " nombre de voisin ", pour l'étendre a une notion + précise ; qui consisterai a trier le nombre de voisin par direction ... je pense que ca peut aider ; mais c'est assez lourd a implémenter ( enfin surtout fastidieux a coder ... rien de bien mechant . )

je m'en remet a vous :)

quand tu parles de "deux points de vue assez différents" qu'est-ce que tu entends ?
Si les deux images sont prises à la même hauteur, tu devrais pouvoir utiliser la contrainte épipolaire : deux points qui se correspondent ont la même ordonnée sur le deux images. Sinon c'est plus difficile.

Les points de vue sont a la meme hauteur a peu de chose prés il me semble .
par contre tu peux developé sil te plait? Car , pour moi, je vais me servir de mes poitn en corélation pour calculer la matrice fondamentale puis, pour trouver TOUTE les paire de points .

Je vient de tenter de répartir les voisin dans un tableau de 8 direction ; ca marche ; mais les résultat sont toujours aussi bancals :/

Je suis a court d'idée la .

http://bensoire.free.fr/expe/rapport_proj_dessie.htm
Voici un lien traitant de la détection de coins et du calcul de la matrice fondamentale à l'aide de la contrainte épipolaire

a priori ça correspond EXACTEMENT à ce que tu cherches :wink:

merci, j'ai dejé etudié ce lien :)
Mais en le relisant je me suis appercu d'un truc que je n'avais pas vu avant, il utilise les "flux optique" pour appareiller ces points .
Je vais chercher dans cette direction ; en espérant que nivo math de ne soit pas trop hardu ;)

le flux optique a l'air de se basé sur des transformation de fouriers ... ca me tente pas trop :D
enfin, je continue de chercher une autre méthode ;)
**wish me luck**

Je me demande , si, au lieux de passer par toutes ces recherche fenêtré ( ce qui ne semble pas trop dnné de bon résultats pour le moment ) , est-ce que, passer par l'intensité ( d'une facons plus developé ) est plus adapté ?

Par exemple, mesuré la valeur moyenne de l'intensité autour d'un point ; ou mesurer les variation dans les 8 directions " simple" .

Hum concernant cette derniére idée , je epnse que ca peut amrcher, a condition que d'une image a l'autre ces variation soit ~~ identique .
Autrement dit, est-ce que le point de vue peut influencer ce genre de paramétre ou pas ( j'ai du mal a voir ca ) .
Bien sur l'intensité d'un point peut varier ; mais je pense que celle des point autour va varier pareillement non ?

Enfin , je reste a votr écoute si vous avez des idées / comentaires .:)
merci

Edit: la varaition d'intensité me donne ceci :
( a gauche pixel1 ; a droite son homologue ; 8 ligne ( 1 / direction )

Code:

---

1 2 3 4 5 6 7 8 9

55 81 60 93 37 83 -11 -6 -8 7 -38 -79 -36 -81 -31 -78

---

j'hesite a exploiter ca .
Car bon , en faisant un rapport on obteint quelquchose d'a peu prés sympa ... mais je sais pas si c'est assez précis pour trouvé le bon candidat parmis ~200 candidats possibles ...
a méditer ;)

ça dépend des conditions de prises de vues. A combien de niveaux de gris travaille-tu ? Peut etre pourrais tu passer en 16 niveaux de gris.

Ensuite, tu es obligé de faire des hypothèses, par exemple en considérant que l'éclairage de la scène ne varie pas entre deux prises de vues pour une région donnée. Les problèmes interviennent quand la scène comporte de nombreux éléments réflechissants.

je suis en 255 niveaux de gris .
Passer en 16 ne ferait que démultiplier mon pb, ou alors je ne vois pas l'interet que tu y vois ;)

Il n'y a aucun elt réfléchissant sur ma scéne ; et je pense que l'éclairage varie peu ...

EDIT: hop nouvelle idée :D je ne sais pas si c'est trés orthodoxe, mais ca me plait :
Je vais pour chaque point , tester TOUT les points possible ( ~200 de mémoire ) . Et tenter de repéré si l'un deux ( pas certain ! ) a est l'homologue de mon point de départ . COmment ?

par élimination ; je vais essayer de déterminer plusieur critère ; dont je suis certain qu'il conduisent a une impossibilité que ce soit ce point
( un ex simple : un point 100% blanc, ne peut pas correspondre avec un pt 100% noir ( sauf cas extreme ... on va les oublier :/ ).
Avec une bonne série de critère, je doit pouvoir obtenir qquchose de satisfaisant, qu'en pensez vous ?

c'est justement la méthode à éviter !

pou l'histoire des niveaux de gris je me suis peut etre mal exprimé.
D'ailleurs je me suis mal exprimé !
Je pensais plutot à l'application d'un filtre gaussien passe-bas pour éliminer le bruit dans l'image. L'idéal étant d'obtenir des belles régions bien uniformes (en terme de niveaux de gris) séparées par des frontières assez marquées.

Heu j'aimerai savoir pourquoi c'est a eviter ?
je trouve ca plutot bien moi , j'élimine peu a peu les point dont je suis CERTAIN qu'il ne sont pas compatible ... rien ne m'empeche au final , de tester ceux qui me reste avec un algo particulier , non ?
Concernant ta remarque sur les niveau des gris ; tu veut dire que avec ta methode, je vais me retrouver avec une image en 16 couleur , et des contour net en terme de changement de couleur, c'est ca?
Ca parait sympa ;) est-ce simple a implémenter? ( as tu un lien qui montre ca ? )
merci

non tu resteras en 256 couleurs (je savais bien que je m'étais mal exprimé). J'ai confondu avec un seuillage (:roll:)
Le grand dilemne des filtres anti-bruits, c'est qu'il s'attaquent aux hautes fréquences (caractéristiques du bruit) sans toucher aux régions de la même couleur (basse fréquence). Du coup ils s'attaquent aussi aux contours, qui sont des hautes fréquences !!
C'est pour cela qu'il est assez compliqué d'obtenir un filtre anti-bruit respectant les contours. Le filtre gaussien est un de ceux qui y parviennent le mieux mais il en existe peut etre d'autres (je suis pas expert).

l'implémentation consiste en un filtre que tu promènes sur ton image.
Concrètement, c'est une matrice carrée 3x3 ou 5x5 qui contient des coefficients qui permettent de filtrer ton image.

Je connais pas de lien mais ça doit pas être dur à trouver, en tapant des mots comme :"Traitement de l'image" "filtre" "bruit blanc"

Citation:

---

Envoyé par Clad3

Heu j'aimerai savoir pourquoi c'est a eviter ?

---

Tout simplement parce qu'en informatique, on cherche d'abord à simplifier le plus possible un problème avant de le programmer !
Une bonne analyse de ton problème avec un bon crayon HB et du bon papier (et aussi accesoirement des bon cours de traitement de l'image) doivent te permettre de dégager des contraintes évidentes qui te permettent de simplifier la résolution du problème. Ce qui se traduit par un gain de temps à l'exécution.


Par exemple prenons deux points A et B.
Comme tu as deux clichés, tu as A¹ et B¹ sur l'image 1; et A² et B² sur l'image 2. A partir de là, on peut déduire des tas de choses !!

Si A¹ est à gauche de B¹, alors forcéments A² est à gauche de B² ! C'est tout simple mais ça te permet de réduire ton champ de recherche au fur et à mesure que tu apparies les couples de points (X¹,X²)

tu vois ce que je veux dire ?

On doit vraiment pas se comprendre lol ^^
Car s'est exactement ce que je veux faire :)

Réduire mon champ de recherche petit a petit, avec des idées de ce genre .

Je me renseigne dés demain sur le filtre que m'a indiqué :)
merci pti hamster :D

d'accord !
ce qui m'avait fait peur, c'était surtout le

Citation:

---

Je vais pour chaque point , tester TOUT les points possible

---

J'avais l'impression que tu allais, pour chaque point, tester TOUS les points de l'autre image pour trouver des candidats.

Un dernier conseil : une fois que ta procédure d'appariement est mise au point, exécute là deux fois. Une fois avec les images dans un ordre (1,2) et une fois avec les images dans l'autre ordre (2,1).
Les listes de couples seront parfois diférentes, ce qui te permettra un plus grande précision (notamment la suppression de couples "parasites")

Merci pour l'idée de faire deux tests dans les 2 ordres :)

En effet, je constate que je m'était mal exprimé ; je veux dire, que au départ, je réduit ma liste de point a comparer ( qui elle contient TOUT les point d'interet de l'image 2 °; en apliquant des methode tel que celle que tu as décrite auparavant :)

bref on est d'accord ;)

Citation:

---

Si A¹ est à gauche de B¹, alors forcéments A² est à gauche de B² !

---

Heu , dans un cas ideal oui ( ideal = j'ai x point dans l'image de droite et x dans celle de gauche avec chaque point qui posséde un et un seul homologue)
ors dans la réalité, j'ai x point d'un coté , y de l'autre , et z correpondance ( avec z <= x et z <= y ) .
Ce qui, m'empeche de faire des calcul précis sur la position / le nombre de voisin d'un point ... au mieux je peut faire de calcul de ressemblance ( calcul avec une précision de +- 2 voisin par ex . ) Mais pas mieux ...

Petite question sur les variatations d'intensité .
Dans mon pré-tri des points, je supprime tout ceux dont le signe de la variation est différente dans 5+ directions . Je me demande si je peut diminuer ce nombre sans perdre "trop" de point valable .

je m'explique :
Je *pense* qu'il est trés PEU probable que le signe de variation d'intensité varie dans plus de 5 direction ; mais par exemple si une source lumineuse est d'un coté par rapport au pixel test dans l'image 2 ; est-ce que le signe ne va pas changer sur le "front" de lumiére ?
( c'est aps facile a expliqué ... si vous ne m'avez pas comprit , je tacherais de faire plus clair :)

Sinon si vous voyez des methode permettant de faire le tri comme celle la ... je suis preneur :)
merci .

effectivement j'ai pas tout compris !

j'ai de la doc qui traine chez moi et qui traite plus ou moins du même sujet. J'essaierai de la retrouver et de vous donner les grandes lignes.

merci bien :)
Mais tu sais, étant donné donnée que l'on est que deux sur le topic ( pas besoin de vous ^^ ) , tu peux me tutoyer :D

Sinon, jusque la j'ai effectuer 4 test pour éliminer les point non-concordant :

Si l'ecart en Y est > 50
Si l'ecart en X est > 350
Si l'intensité du point est != de + de 50
Si le signe de l'intensité varie dans plus de 5 direction .

je passe de 135 pts a tester a environ 5-15 . Il y a de l'espoir ;)

J'ai choisit ces nombre en fonction de mes image :

http://max.cat.free.fr/stereo1.png
http://max.cat.Free.fr/stereo2.png

Je pense ne pas avoir exclu trop de point pouvant être cohérent avec ca pour le moment :)

tes liens sont morts

rho ! je ve vérifier ca, je les réactualise dans - de 2 min :)

edit : c'est bon :

Et sinon , je pense que je vais changer un poil mon fusil d'épaule :)
Je vais garder ces méthode pour réduire le nombre de candidat possible ; puis laisser le soin a l'utilisateur, de ciblé l'un des point ( marqué / clcikable facilement ); puis avec les réduction faite, je lui afficherais la liste des point ( 5-6 maxi ) qui correspondent le mieux, puis a lui de finir le travail en choissisant le bon ... ) C'est pas satisfaisant algorithmiquement parlant ; mais bon , pour ce que je veux obtenir je m'en contenterais ;)

Pour ta dernière idée, je pense que cela ce rapproche à la k-clusterisation, ou un truc du genre.

Tu fais des paquets des points proches.
Tu en fais des super-points.
Tu fait un fil de fer de ces super-points.
Tu fait correspondre les deux dessins pour savoir à quel super-point de l'image 1 correspont un super points de l'image 2. (<- le plus dur à mon gout mais avec moins de points ;) )
Enfin tu proposes à l'utilisateur les points de ton super-points

Merci de l'idée, malheuresuement j'aprroche de la fin de mon stage, et je n'aurais pas le temps je pense de me re-pencher la dessus :/
enfin merci quand meme !!

Pas de problème c'etait juste une idée. ;) courage pour le stage.