Discussion :

[Seb.26]

Bonjour à tous,

alors, mon problème en quelques mots :

J'ai 2 séries de données représentées sous la forme d'une image :

- Série de données A :
Une reconnaissance de formes sur une photo qui me donne la positions d'objets (tag RFID ronds et noirs) détectés sur une feuille blanche (facile donc)

- Série de données B :
C'est un lecteur RFID fixé sur 2 axes, qui balayent la même feuille avec les mêmes tags (de gauche à droite, et de haut en bas), en enregistrant la position (x;y) de chaque tag RFID qui sera lu.

Le problème, c'est que si les données A peuvent être considérées comme précises, les données B, elles le sont nettement moins (on ne peut prévoir "quand" le lecteur va lire le tag).

Graphiquement, cela nous donne :

Le but étant de faire le lien entre les 2 sources de données.

Dans le cas ci-dessus, ça donnerait :

A -> 1
B -> 2
C -> 3
D -> 4
E -> 5
F -> 6
G -> 7

On peut également voir qu'il existe dans chaque série des échantillons orphelins ( Z et 99 ), ces derniers sont provoqués dans la série A par un tag RFID défectueux, et dans la série B, par un tag placé malicieusement SOUS la feuille, donc non visible sur la photo.

On complète donc le résultat :

Z -> Non trouvé
99 -> Non trouvé

Cet exercice est très simple à faire pour un humain, mais comment programmer cela ??? ... je sèche.

Pour le moment, j'ai envie d'essayer de représenter les données "absolue" de chaque série par des données "relatives".

Je pensais donc faire pour chaque donnée de chaque série, une liste de sa position relative (sur X et sur Y) avec chacune des autres donnée de sa série, et ensuite essayer de chercher l'association (A->1, B->2) qui offrent le plus petit taux d'erreur, et qui donc est le plus probable.

Mais concrètement, je vois pas trop par où attaquer ...

Si vous avez une idée et/ou une piste pour débuter, c'est sympa de m'aider

NB: Si certains points ne vous semblent pas clairs, n'hésitez pas à demander des éclaircissements.

Merci par avance,
Seb.

[pseudocode]

Dans notre petit monde très fermé du traitement d'images, ce que tu veux faire s'appelle du "matching".

La méthode la plus simple est de construire une grosse matrice (A,B,C,...,Z,[]) x (1,2,3,...,99,[]).

On met un "1" dans la matrice quand un point correspond à un autre, et "0" sinon. La contrainte étant d'avoir un seul "1" par ligne et colonne (sauf pour la dernière ligne/colonne qui sert a indiquer qu'il n'y a pas de correspondant = les orphelins)

Au début tu mets dans les cases de la matrice une valeur inversement proportionnelle a la distance entre les points, par exemple 1/(1+distance).

Ensuite on doit "améliorer" la matrice dans le but de n'avoir plus que un seul "1" par ligne et colonne.

Suis-je clair ?

[Seb.26]

Dans notre petit monde très fermé du traitement d'images, ce que tu veux faire s'appelle du "matching".

OK ... ... cool, au moins maintenant je sais quoi chercher sur google ...

La méthode la plus simple est de construire une grosse matrice (A,B,C,...,Z,[]) x (1,2,3,...,99,[]).

On met un "1" dans la matrice quand un point correspond à un autre, et "0" sinon. La contrainte étant d'avoir un seul "1" par ligne et colonne (sauf pour la dernière ligne/colonne qui sert a indiquer qu'il n'y a pas de correspondant = les orphelins)

Au début tu mets dans les cases de la matrice une valeur inversement proportionnelle a la distance entre les points, par exemple 1/(1+distance).

Ensuite on doit "améliorer" la matrice dans le but de n'avoir plus que un seul "1" par ligne et colonne.

Suis-je clair ?

Je vois en gros le concept de la matrice ... reste à voir comment l'améliorer ...
-> je vais chercher des articles sur le "matching"

J'imagine qu'il est préférable de "normaliser" les 2 séries de données ?
(les inclure dans un carré de taille 1.0 x 1.0)

Merci de ta réponse

Seb

[pseudocode]

Je vois en gros le concept de la matrice ...

Pour être plus clair, voila la matrice pour ton exemple.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
   A B C D E F G Z | []
  +--------------------
1 |1 0 0 0 0 0 0 0 | 0 
2 |0 1 0 0 0 0 0 0 | 0 
3 |0 0 1 0 0 0 0 0 | 0 
4 |0 0 0 1 0 0 0 0 | 0 
5 |0 0 0 0 1 0 0 0 | 0 
6 |0 0 0 0 0 1 0 0 | 0 
7 |0 0 0 0 0 0 1 0 | 0 
99|0 0 0 0 0 0 0 0 | 1 
-------------------+---
[]|0 0 0 0 0 0 0 1 | 0

reste à voir comment l'améliorer

Vu ton exemple, tu peux faire simple. Tu cherches le plus gros coef dans la matrice, tu le forces a "1" et tu forces le reste de sa ligne/colonne a "0". Puis tu prends le second plus gros coef, etc.

J'imagine qu'il est préférable de "normaliser" les 2 séries de données ?
(les inclure dans un carré de taille 1.0 x 1.0)

bof, pas forcement. Tout dépend de ta fonction de distance, et de ta méthode d' "amélioration" (appelons la "convergence" pour faire pro )

[Seb.26]

... je vais revoir mon vocabulaire de profane !!!

Donc, si j'ai bien compris, j'initialise chaque valeur de ma matrice avec 1/distance et ensuite je considère comme "juste" l'association qui a le plus gros coef.

Mais j'ai l'impression que cela ne va pas tenir compte de la "globalité" du matching (oups, il doit me manquer un terme "pro" là )

Par exemple

va probablement me donner :

A <-> Non trouvé
B <-> 1
C <-> 2
3 <-> Non trouvé

Car ils sont les plus proches, mais un résultat plus "correct" pour moi serait :

A <-> 1
B <-> 2
C <-> 3



[Edit] Par "correct", j'entends qui est le plus proche dans la globalité, pas juste pour chaque point ... je sais pas si c'est clair ...

[pseudocode]

Mais j'ai l'impression que cela ne va pas tenir compte de la "globalité" du matching (oups, il doit me manquer un terme "pro" là )

[Edit] Par "correct", j'entends qui est le plus proche dans la globalité, pas juste pour chaque point ... je sais pas si c'est clair ...

Oui, c'est clair.

Et effectivement un algorithme de convergence aussi "simple" que celui que j'ai donné ne va pas marcher. Le matching est un problème d'optimisation assez complexe et il n'existe pas encore de solution miracle simple.

La plupart des méthodes consistent à ajouter une contrainte au matching, généralement que les points aient subit une transformation (dans ton exemple, la transformation serait une translation horizontale). On cherche alors le "meilleur" matching qui répond a cette contrainte (meilleur = la plus petite erreur globale). Cela nécessite pas mal de calculs et d'itérations.

Si tu as peu de points a faire correspondre, tu peux ajouter un peu de hasard dans les assignations (prendre le x-ieme plus fort coef) et recommencer plusieurs fois le calcul de la matrice. La matrice avec le meilleur matching sera ton résultat final.

[Seb.26]

OK.

Dans mon cas, le nombre de points à "matcher" est relativement faible (<100) ... et le traitement peut prendre quelques secondes ... ça en fait des opérations avec les CPU actuels ...

Je vais aussi essayer de "caractériser" (trouver le max par des éssais) l'erreur entre mes 2 série afin de borner le rayon de recherche ...

Je vais réfléchir calmement à tout ça ...

Merci de ton aide.

@+
Seb.