Une Idée

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: salem_b_a

salut tout le monde!!
je suis trés ravis de me joindre à la communauté des matheux malgré que je ne le suis pas!
Je suis plutot entre informaticien & mécanicien !
mais il se trouve qu'on fait face tout les jours à un problème mathèmatique que seuls les détenants du pouvoirs peuvent resoudre!
en fait je prépare un projet de reconnaissance d'empreinte digitale, mais lorsque j'ai atteint le stade de la comparaison je me trouve face à une complexité énorme du programme qui diminue ses performances!
L'idée classique était de retrouver les points particuliers de l'empreinte (les minuties), en construire un graphe et le comparé à un graphe précedemment défnis pour cette empreinte!!
si on opte pour cette technique,la comparaison des deux graphes, assez gourmandes en mémoires est un obstacle!
Donc je me suis dit, pourquoi ne pas remplacer ce graphe par une seule grandeur!
comme la probabilité de retrouver deux garphes identiques pour deux empreintes différentes est presque nulle!
et donc je demande à la communauté de matheux est ce qu'on peut retrouver une formule et une preuve pour appuier mon idée!!§
Merci


Posted by: ijk

Citation:
Posté par salem_b_a
(...) Donc je me suis dit, pourquoi ne pas remplacer ce graphe par une seule grandeur!


En fait, il te reste de l'empreinte qu'un ensemble de points.
Y a t il plusieurs categories de points particuliers ? Ou te limites tu qu'à un seule pour simplifier le problème ?

En tout cas jusque là, je n'ai pas l'impression que l'on puisse réellement parler de graphe. Dans le sens ou il n'y a pas vraiement de relation particulière entre les points ET entre chaque point.

Bon ok ! Tu peux quand même avoir un graphe des distances entre chaque points (matrice carrée symétrique)

Et tu aimerais représenter cela par une seule grandeur (un scalaire) En algorithmique on appelle cela un 'code de hashage'. C'est sûr ! Ce serait l'idéal car à partir de là il suffit de faire un parcours comme dans un dictionnaire (complexité en O(ln(n)) pour 'n' recherche)

Seulement il me semble improbable de trouver un nombre unique pour représenter une empreinte Car une empreinte peut être représentée de multiple façon ! Principalement parce que les distances entre chaqu point ne seront jamais les même pour la même empreinte prise sur différents supports. Ensuite pour la même enpreinte ce ne sont pas forcement les mêmes munities qui sont choisis en pas forcement dans le même ordre non plus. Donc une seule grandeur pas vraiement possible.

Cependant on peut peut-être quand même possible d'ordonner 'quelque chose là dedans' !!!

Alors faudrait déjà commencer par réussir à ordonner les points (du graphe/matrice) quelque soit l'ordre en entrée ...

... et puis je vais arrêter là pour l'instant car j'ai d'autre travail à faire... mais c'est quand même un sujet hashement interessant


Posted by: salem_b_a

Bonjour!
d'abord merci pour votre intervention;
la veille aprés avoir posté le message je me suis mis à penser à ce problème!
à 4h du math j'ai arrivé à fixer une certaine heurestique "pour arranger ce qu'il y a là dedans"
En fait, je suis parti du fait que l'empreinte est en général dans le même sens à chaque entrée, et donc pour deux échantillons différents le sens du haut et bas est presque le même (à quelques degrès près)...
L'idée était donc de les arrangé par ordre décroissant des ordonnée tout en introduisant une marge d'erreur de 2 pixel dans toutes les direction,
anisi un point est décris par 25 couple de coordonnée, (une chaine par exemple)
*****
*****
**x**^
*****|
*****|

pour la reconnaissance, il suffira de retrouver une parties (avec un seuil)des composantes de la chaine de coordonnée dans cette chaine de coordonnées référence!
bon, je sais que ça reste un peu flou, j'essayerai de la formaliser un peu plus et je te passerai une copie dès quelle sera prête!
je voulais juste te dire merci, c'est encourageant ...










-