Algos pour reconnaissance de formes

Version imprimable

06/12/2005, 18h39
Laurent Gomila

Algos pour reconnaissance de formes

Salut

Tout d'abord je tiens à préciser que ce problème ne me concerne qu'indirectement, donc s'il manque certaines précisions je m'en excuse.

Le but est de faire de la reconnaissance de formes, ou plutôt de la comparaison. L'utilisateur trace une forme (une suite de segments) dans une grille en coordonnées 2D réelles, et le but est de déterminer si celle-ci correspond à une forme simple prédéfinie : cercle, carré, segment, ...

J'avais tout d'abord pensé aux réseaux de neurones, mais en réflechissant à la structure de celui-ci ainsi qu'à ses entrées / sorties, je me suis dit que ce n'était peut-être pas adapté à ce problème particulier.

Donc, est-ce tout de même la bonne piste ? Si oui, comment procéder ? Sinon, quels sont les pistes à suivre ?

:merci:
06/12/2005, 18h44
j.p.mignot

J'ai pas mal de solutions pour cela pour avoir développé de la reconnaissance de caractères RT.
A-t-on l'historique des points?
06/12/2005, 18h49
Laurent Gomila

Qu'est-ce que tu entends par l'historique des points ?
06/12/2005, 18h52
j.p.mignot

Le probleme est TRES différent si on a une image avec un tracé ou si on acquiere les points a une fréquence donnée et que l'on stokes les couples (X,Y) (t) pour t= n*dt

voir notre brevet

Procédé de reconnaissance de caractères tracés manuellement sur une zone de saisie et dispositif électronique permettant de mettre en oeuvre ce procédé
06/12/2005, 19h13
GrandFather

Re: Algos pour reconnaissance de formes

Salut,

Citation:

Envoyé par Loulou24

J'avais tout d'abord pensé aux réseaux de neurones, mais en réflechissant à la structure de celui-ci ainsi qu'à ses entrées / sorties, je me suis dit que ce n'était peut-être pas adapté à ce problème particulier.

Qu'est-ce qui te fait les exclure ? C'est pourtant un domaine où ils ont fait leurs preuves...
06/12/2005, 19h27
j.p.mignot

Je suis assez d'accord si on traite des bitmap mais cela requière pas mal de ressources. Si on à du Real Time sur des processur embarqués de faible performance- mémoire, il existe des moyens nettements plus efficaces.
Nous avons pu obtenir environ 97 à 99% de tau de reconnaissance sur un palette d'environ 60 caractères ( alpha numnérique + ponctuation + caractères standards + - ! ? # * & & @ ...)
ceci temps réel sur um proc à 4MHz et 64k de mémoire totale (soft + data + stack + FS )
06/12/2005, 20h05
Laurent Gomila

Citation:

Le probleme est TRES différent si on a une image avec un tracé ou si on acquiere les points a une fréquence donnée et que l'on stokes les couples (X,Y) (t) pour t= n*dt

L'utilisateur entrant les segments au fur et à mesure (il me semble), on peut donc partir sur le second cas.

Citation:

Qu'est-ce qui te fait les exclure ? C'est pourtant un domaine où ils ont fait leurs preuves...

Je ne suis pas très calé en réseaux neuronaux, mais il me semblait qu'ils étaient très performant pour détecter une ressemblance entre deux images bien définies, pas pour dire si telle forme a plutôt une allure de cercle ou de carré. Mais comme je l'ai dit, peut-être que je me trompe.
06/12/2005, 20h56
xxiemeciel

Salut,

il y a plusieurs moyens de traiter ceci, le premier comme tu l'as dis est le reseau de neurone mais qui sera plus adapté pour reconnaitre un type de forme particulier dans une serie d'image

et tu as la base de données qui contient une certaine quantité de formes connues. Ensuite tu peux definir une distance de similarité et comparer avec ta base de données sur quelle formes la distance est la plus faible.

si tu cherches sur le net sur les mots clefs data mining et image mining tu trouveras aussi des articles qui traitent de ce sujet.

XXiemeciel
07/12/2005, 09h56
mathieu_t

Salut !

Il y a une solution simple et efficace quand on connaît les segements de la forme : ce sont les descripteurs de Fourier.

En gros cela consiste à décomposer la forme en série de Fourier (ou transformée il faut que je potasse un peu...). Plus on donne de coefficients, plus la forme est précise, ce qui veut dire que les premiers correspondent aux basses fréquences de la forme (cad la forme globale), les "derniers" (enfin comme il y en a une infinité...) correspondent aux hautes fréquences...

La comparaison est donc faite sur les N premiers coefficients de Fourier, ce qui bien sûr diminue les calculs... (N est choisi selon ton appréciation)

C'est pas mal utilisé dans le genre exact de cas que tu décris (cad on dispose des segments de la forme, donc en quelque sorte elle est déjà segmentée)...

A+

[EDIT] Quant au réseau de neurones, il faudrait quand même un long apprentissage je pense, ce qui est souvent pénible... enfin je crois...
07/12/2005, 12h28
mathieu_t

Voici un cours sur les descripteurs de Fourier et autres méthodes : http://www.tsi.enst.fr/~tupin/cours/...urs_formes.pdf...

A+
08/12/2005, 08h25
Matthieu Brucher

Exact, et c'est indépendant de l'échelle, de la translation ou d'une rotation.
08/12/2005, 11h12
GrandFather

Citation:

Envoyé par Loulou24

Je ne suis pas très calé en réseaux neuronaux, mais il me semblait qu'ils étaient très performant pour détecter une ressemblance entre deux images bien définies, pas pour dire si telle forme a plutôt une allure de cercle ou de carré. Mais comme je l'ai dit, peut-être que je me trompe.

Dans ce cas, il s'agit plus d'une tâche de classification que d'association entre deux formes. Mais c'est également du ressort des réseaux neuronaux.

Citation:

Envoyé par Miles

[EDIT] Quant au réseau de neurones, il faudrait quand même un long apprentissage je pense, ce qui est souvent pénible... enfin je crois...

Certes, le temps d'apprentissage du réseau peut être important, et les choix de type, de dimensionnement du réseau et des jeux d'apprentissage et de test peuvent être assez délicats, mais une fois que ton réseau marche, il sera beaucoup plus rapide que des calculs de transformées de fourrier pour chaque forme soumise.
08/12/2005, 11h29
mathieu_t

Citation:

Envoyé par GrandFather

Citation:

Envoyé par Miles

[EDIT] Quant au réseau de neurones, il faudrait quand même un long apprentissage je pense, ce qui est souvent pénible... enfin je crois...

Certes, le temps d'apprentissage du réseau peut être important, et les choix de type, de dimensionnement du réseau et des jeux d'apprentissage et de test peuvent être assez délicats, mais une fois que ton réseau marche, il sera beaucoup plus rapide que des calculs de transformées de fourrier pour chaque forme soumise.

C'est justement tout le problème : l'apprentissage doit être très long, et on ne sait jamais vraiment pourquoi ça marche : ça fait vraiment boîte noire qui sort un résultat, donc il faut être vraiment très prudent, non ? En fait je nesuis pas familier des réseaux neurones, mais c'est un peu l'opinion qu'ont les gens qui s'y connaissent dans mon entourage...

A+
08/12/2005, 12h31
GrandFather

Citation:

Envoyé par mathieu_t

C'est justement tout le problème : l'apprentissage doit être très long, et on ne sait jamais vraiment pourquoi ça marche : ça fait vraiment boîte noire qui sort un résultat, donc il faut être vraiment très prudent, non ? En fait je nesuis pas familier des réseaux neurones, mais c'est un peu l'opinion qu'ont les gens qui s'y connaissent dans mon entourage...

Je suis assez d'accord avec eux : une fois l'apprentissage terminé, on ne sait jamais vraiment ce que le réseau a appris ! :lol:
C'est pour cela que le jeu de test doit être le plus complet et pertinent possible, il faut essayer de prendre l'apprentissage en défaut, et vérifier que le réseau est capable de généraliser.

Quant à la durée de l'apprentissage, elle peut être certes longue, mais il n'a lieu qu'une fois.
09/12/2005, 10h34
Matthieu Brucher

C'est pour ça que je préfère les SVMs, c'est adapté à toute classification en n classes, avec frontières non-linéaires, pas de sur-fitting, complexité du calcul résiduel très faible car on ne prend en compte qu'un nombre de vecteurs défini à l'avance.

Le pb, c'est que pour tous ces algos, il vaut mieux utiliser un descripteur de forme invariant par rotation/translation/homothétie, sans quoi je ne suis même pas sûr qu'un réseau de neurones puisse être entraîné correctement - il y a un // entre RN et SVM qui existe -