# Gnral Dveloppement > Algorithme & Mathmatiques > Traitement d'images >  Reconnaissance de formes gomtriques temps rel

## Dovice

Bonjour  tous, 


Je travaille actuellement sur un systme de reconnaissance de forme en temps rel. Le but est de pouvoir discriminer 3 types de formes : 
-Cercle
-Droite diagonale
-Droite verticale
Et peut tre des formes plus complexes par la suite.

Mes donnes sont constitues de points (donc de leur coordonnes polaires ou cartsiennes) dans une image, des points noirs sur fond blanc, donc une image dj binarise. 

Ces donnes s'accumulent avec le temps. En ralit c'est comme si on prennait des photos a un instant t d'un cran sur lequel pointe un laser, on en retire les coordonnes du point d'impact. 

Je souhaite donc dans un premier temps relier ces point entre eux, et ensuite determiner la forme trace par l'utilisateur. Il me faut donc un systeme de reconnaissance de forme sur ces points, pour determiner l'une des 3 formes souhaites.

Je suis evidemment contraint par la notion de temps rel. J'ai explor la piste d'OpenCV mais ce n'est pas concluant pour mon projet (transforme de Hough, et templates; matching ...)
Je me suis dit que je pourrais utiliser un reseau de neurones mais je ne vois pas trop quelle caractristiques utiliser pour mon probleme, sachant que les cercles et droites traces ne seront pas parfaite car effectuer a main lev par un utilisateur...
J'ai penser utiliser dans un premier temps les diffrences d'angles, et la distance entre les points mais 2 caractristiques pour discriminer 3 formes me parrait trop peu.

Voila je ne sais pas si j'ai t clair, je fourni ci joint des exemple d'image qui pourraient etre retirer du systeme de tir sur l'cran...

----------


## kessoufi

Salut 

tu peux t'inspirer de cet article :

http://www.codeproject.com/KB/graphi...rAnalysis.aspx

----------


## Dovice

salut Kessoufi, 

Merci pour ta rponse, j'avais effectivement dj consult ce papier, mais le problme pour ma part, contrairement a l'tude faite dans ce papier, est que je n'ai pas rellement de formes exactes qui se reproduisent puisque chaque forme est ralise par un utilisateur, qui peut etre diffrent de l'un a l'autre et qu'ainsi cette forme peut subir des modifications.
Plus clairement, pour un cercle, je peux avoir aussi bien 5 points pour le dcrire, que 6 ou 7 ... Idem pour une ligne, et l'espacement des points peut galement varier

Par ailleurs, j'avais dj envisag les techniques d'analyse de contour, mais cette technique ne prends pas en compte l'intersection des contours comme dans l'image fournie dans mon premier post sur ce sujet.
J'ai donc envisag de faire "glisser" une fentre pour limiter l'analyse a un certain nombre de point, pouvant ainsi sparer le cercle de la partie linaire, mais cela impose que je fixe un nombre de point pour cette fenetre.
Le probleme est que pour une forme le nombre de point varie en fonction de l'utilisateur et de sa "rapidit" a effectuer le mouvement ... 

L'idal serait galement de dtecter la forme le plus tot possible, avec un minimum de point ... par exemple, considrant 3 mouvements cercle, axe diagonal et axe vertical ... je peux facilement detecter un cercle par une courbure ... le demi cercle suffit donc pour le discriminer de la droite...

----------


## ToTo13

Bonjour,

relier des points c'est bien, mais dans quel ordre ?
Pour les relier correctement cela voudrait dire que tu aurais des informations complmentaires.

Ensuite je vois dans ta figure qu'il n'y a pas qu'une seule forme par image.

La question intressante est de savoir combien de points au maximum tu peux avoir dans ton image ?

----------


## Dovice

Salut toto13,

En faite, les points peuvent etre relier ou non. Pour ma part je les reliais premirement pour avoir une meilleur vue pour moi, et deuxiemement car je comptais utiliser les analyses de contours.

En ralit, ce que j'ai c'est les points d'impacts d'un laser infra rouge sur un ecran... a peu prs 6 points par joueur par seconde. J'en rcupre donc les coordonnes (x,y) du point sur l'cran...

Les points apparaissent donc dans un ordre prcis et les coordonnes stockes dans un tableau. Je peux donc facilement connaitre quel est le premier point, quel est le second... les relier ou non, tout dpend de la mthode la plus approprie pour analyser les formes...

Mon problme est que les point apparaissent en continue, car le laser emet en continue (et ca je ne peux pas y toucher). je dois donc utiliser une methode temps rel de detection de forme, en prenant par exemple 5 points, voir si une forme est dtecte parmis un cercle une droite diagonale, et une droite verticale... si ce n'est pas le cas, je dplace ma fenetre d'analyse a quelques points suivant... 

Si une forme est dtecte alors j'efface les points. Mon probleme est donc la methode d'analyse, ne disposant que de points comme information, et surtout de determiner ou un geste et donc une forme commence et s'arrete...

----------


## pseudocode

> Mon probleme est donc la methode d'analyse, ne disposant que de points comme information, et surtout de determiner ou un geste et donc une forme commence et s'arrete...


Si j'ai bien compris :
- Il faut construire 3 dtecteurs vrai/faux pour les 3 formes cercle, verticale et diagonale.
- Chaque dtecteur fait une analyse temps rel du signal => chaque nouveau point du signal doit mettre  jour la valeur dtecteur. 
- Le but est de trouver sur chaque dtecteur les fronts montants (Faux/Vrai) et descendants (Vrai/Faux) qui indiquent des squences de points reprsentant la forme

C'est ca ?

----------


## Dovice

Oui voila vous avez bien rsum le problme. Tout d'abord il me faut dtecter le dbut ou la fin d'un mouvement...
Ensuite savoir de quelle forme il s'agit. Mais je n'ai aucune ide de comment implmenter de faon fiable ce problme. J'ai pens a la dtection de contour, ou mme la dtection par histogrammes...
Mais il me faut trouver des caractristiques discriminantes pour chaque forme.
Enfin je peux galement travailler sur l'espacement des points pour calculer la "vitesse" du mouvement connaissant le nombre d'images par seconde captures par la camra...
car entre chaque mouvement il peut y avoir des phases de transitions... je rsume cela dans l'image suivante avec une forme de cercle avec des points, et une transition vers une diagonale ou les points sont plus espacs car le mouvement est fait plus rapidement que les transitions. 
Les transitions sont en rouge, les formes en noire...

----------


## pseudocode

Ca complexifie un peu le problme si la transition ressemble  une diagonale. Je suppose qu'on peut effectivement se servir de la vitesse/densit des points pour discriminer forme/transition. Mais ca ne me semble pas trs robuste.  ::?: 

Construire les 3 dtecteurs ne m'a pas l'air trs compliqu du moment qu'on  les points de dpart/fin de la forme. C'est ce qui m'a l'air le plus problmatique dans ton cas.

Si on n'a pas ces informations, on peut tenter de dtecter simultanment les 3 formes et prendre celle qui est la plus vraisemblable. Ca demandera surement du tunning de paramtres pour tre efficace.

----------


## Dovice

Oui les transitions peuvent tre diagonales, ou bien horizontale ou verticale... C'est la toute ma difficult car j'ai rellement l'impression d'tre dans une impasse...
Le problme qui rside dans la mesure de l'espacement des points est que la rapidit des transition et/ou des formes traces est lie  l'efficacit du joueur, donc varie d'un joueur a l'autre...

Pour ma part j'ai dj un algorithme via OpenCV qui me permet de reconnatre les trois formes lorsque les points de dpart et d'arrive sont bien connus.

J'ai pens faire parcourir une sorte de fentre sur un nombre limit de point (6 points par seconde, donc une fentre sur 5  6 points me semble raisonnable) et voir si il y a une forme ou non. Si je dtecte une forme alors je supprime les points traits ... mais il y a un risque que je ne prenne pas toute l'information (que certains points suivants ne soient pas pris en compte alors qu'ils font partis de la forme). 
De plus ma mthode se basant sur les contours, ma difficult rside dans le fait de boucler ou non le point de dpart sur le point d'arrive (ncessit pour le cercle pour avoir un contour ferm, mais pas pour les droites...).

Je suis donc perdu ^^

----------


## ToTo13

Bonjour,

vu ton nombre de point, tu peux tenter des mini transformes de Hough.

----------


## Dovice

Oui j'ai dj utilis la transforme de Hough via OpenCV. Mais cela necessite pour le cercle un contour ferm

----------


## pseudocode

> J'ai pens faire parcourir une sorte de fentre sur un nombre limit de point (6 points par seconde, donc une fentre sur 5  6 points me semble raisonnable) et voir si il y a une forme ou non. Si je dtecte une forme alors je supprime les points traits ... mais il y a un risque que je ne prenne pas toute l'information (que certains points suivants ne soient pas pris en compte alors qu'ils font partis de la forme).


Il faudrait plutt un systme d'accumulateur au lieu d'une fentre fixe. Avec un accumulateur par forme qui reprsente la probabilit/vraisemblance de la dtection.

Un "nouveau" point P contribue ainsi  faire voluer simultanment tous les accumulateurs, suivant que le point P appartient ou non  la forme.

----------


## Nebulix

tu gardes 4 points (a,b,c,d) en mmoire. Tu calcules les angles abc et bcd.
S'ils sont tous les deux trs petits, tu as une droite, s'ils ne sont pas petits mais voisins, tu as un cercle.

----------


## Feriaman

Bonjour,

Si j'avais ce problme (et bien que par ailleurs, je sois un grand fan de traitement du signal, transforme de fourrier et autres joyeusets de ce genre), 
je tenterais une approche qui ne fait pas intervenir toutes ces subtilits.

D'abord : faire que a marche. On verra ensuite pour les optimisations.

Tu dis que tu as 6 points par secondes. Je propose qu'on fixe ensemble une limite qui dit qu'une forme ne peut pas "durer" plus de 2 secondes.

A partir de l j'essaierais ceci : 


```

```

En utilisant des reconnaisseurs de cercle et de droite ultra-simple (le but est de faire une discrimination entre deux formes trs diffrentes l'une de l'autre) :


J'explicite un petit peu, mais le dessin est clair.
Pour le cercle :


```

```

Pour la droite : 



```

```

Bien sur : pour diffrencier entre diagonale et horizontale, tu fais en fonction de la pente que tu as calcul en 2.

Le problme de ces discriminateurs "de premire approche" (pour ne pas dire "simplistes"), est qu'ils ne discriminent presque rien : la droite versus le cercle. Donc il existe plein d'autres formes qui seront comptes positives bien qu'elles ne soient ni des rond ni des droites, mais si j'ai bien compris a va plutt dans ton sens.

Bien sur, si ce n'est pas le cas ; il ne faut pas faire comme a.

Exemple :

----------


## Dovice

Merci pour vos rponses. J'ai en effet dj pens  me baser sur les angles entre les points, cependant cela ne me permet que (dans un premier temps bien sur) de discriminer droite et cercle ... Il me reste alors a discriminer diagonale et verticale...
Pour cela je me demandais si les histogrammes projets sur les axes verticaux et horizontaux ne seraient pas intressant ...

Le problme rel rside dans le manque d'information que j'ai, je ne sais pas exactement la dure d'un mouvement humain, relatif a chaque personne... Mais cela peut ventuellement passer en comparant les angles en effet.

En ce qui concerne les accumulateurs, cela pourrait donc tre la comparaison des trois premiers point (au niveau de l'angle et distance les sparant), puis ensuite voir l'angle avec les deux derniers point parmi ces trois, et le suivant?

----------


## Dovice

Merci pour ta rponse feriaman,

Mais le fait de dtecter tout et n'importe quoi ne me convient pas vraiment ... dtecter un cercle en reconnaissant un pentagone passe encore, mais pour le reste des exemples que tu as mis, cela n'est pas possible, car l'utilisateur peut faire un mouvement totalement diffrent du cercle et un cercle sera alors reconnaitre, cela n'est pas souhaitable pour un jeu...

De plus je n'ai pas compris pour les droites ton explication, en clair, une droite passant par les points extremes suffit, ensuite on a juste besoin de calculer l'ecart des autres points a la droite?

----------


## pseudocode

> En ce qui concerne les accumulateurs, cela pourrait donc tre la comparaison des trois premiers point (au niveau de l'angle et distance les sparant), puis ensuite voir l'angle avec les deux derniers point parmi ces trois, et le suivant?


Le plus simple c'est de faire l'approche inverse : dtecter si un point P n'appartient PAS  la forme. Auquel cas son accumulateur est remis  zro. Sinon, le point P "peut" appartenir  la forme, et l'accumulateur est incrment.

Pour imager un peu le principe :

  
  P0
      P1
      
      P2
      
  P3
   
  P4Accumulateurs : (C)ercle, (D)iagonale, (V)erticale
    C  D  V
    -------
    0  0  0
P0  1  1  1
P1  2  2  0
P2  3  0  1
P3  4  1  0
P4  0  0  1
..
L j'utilise des proba binaires, mais on peut utiliser des rels. On peut aussi avoir des seuils de tolrance dynamique (autoriser une erreur plus/moins grande si l'accumulateur est haut). C'est assez souple comme technique.

Le problme c'est d'ajouter un detecteur de "transition" qui soit fiable (et son accumulateur correspondant).

----------


## Dovice

Oui d'accord, cependant j'ai aucune notion de comment implmenter des accumulateurs (peut tre bte comme remarque je le conois ^^).

Ici en loccurrence, vous travaillez sur les angles si je comprends bien tout de mme pour les accumulateurs?

En tous les cas cela me semble une bonne piste a tudier... En effet il reste le problme des transitions, pour lesquelles seule les mesures de distance peuvent me sauver pour le moment...

Mais pour discriminer droite diagonale et verticale, comment procd? la je peux jouer sur un encadrement de la forme( largeur plus grande pour le rectangle entourant une diagonale que pour une vertical, rapport aire du contour sur aire du rectangle...)

----------


## pseudocode

> Oui d'accord, cependant j'ai aucune notion de comment implmenter des accumulateurs (peut tre bte comme remarque je le conois ^^).
> 
> Ici en loccurrence, vous travaillez sur les angles si je comprends bien tout de mme pour les accumulateurs?


Pas ncessairement. Mais oui, pour les premiers points (quand l'accu est vide) ca me semble une bonne ide de partir sur les positions relatives (donc les angles).

Mais a partir du moment ou il y a 3,4 points dans l'accumulateur, on a dj une bonne ide du modle de la forme. On peut alors utiliser un dtecteur plus sophistiqu.

----------


## Dovice

Un dtecteur de quel type? Parce que je n'ai plus trop d'ide la dessus, je pense avoir fait le tour de ce qui me paraissait intressant mais sans arriv  une conclusion satisfaisante

----------


## pseudocode

> Un dtecteur de quel type? Parce que je n'ai plus trop d'ide la dessus, je pense avoir fait le tour de ce qui me paraissait intressant mais sans arriv  une conclusion satisfaisante


Il ne faut pas oublier que c'est un dtecteur "inverse" : dtecter un point qui n'est PAS dans la forme. 

Tout ce qui a t dit avant peut tre utiliss : des masques, des valeurs limites (angles, droites), l'quation des formes (= la distance point/forme), ...

----------


## Feriaman

> Un dtecteur de quel type? Parce que je n'ai plus trop d'ide la dessus, je pense avoir fait le tour de ce qui me paraissait intressant mais sans arriv  une conclusion satisfaisante


Je pense que tu n'en sauras pas plus en discutant sur le forum.
A mon avis : go !

- Implmente tes accu (tu dois tre capable de retrouver les n derniers points non-traits).
- Implmente un dtecteur selon n'importe laquelle des mthodes propose ici (personellement, je crois que pour du RT le plus simple est le mieux).
- Teste.
- Si cela ne fonctionne pas : dbugue et comprends. Ensuite tu changera ce qui ne va pas (taille des accus, first-in ou last-in, rigidit des dtecteurs, dure de l'analyse...)
- tiens nous au courant

Bonne chance

----------


## ToTo13

> Oui j'ai dj utilis la transforme de Hough via OpenCV. Mais cela necessite pour le cercle un contour ferm


Euh... normalement non. Il suffit de tirer un triplet de points et de calculer le cercle passant par les points.

----------


## Dovice

> Euh... normalement non. Il suffit de tirer un triplet de points et de calculer le cercle passant par les points.


A bon? j'ai toujours vu la transforme de hough applique  des contours ferms, et pas uniquement a des points... Peux tu m'en dire un peu plus la dessus, ou as tu des documents?

----------


## ToTo13

Fais une recherche dans ce forum, je l'ai dj expliqu plusieurs fois.
Mais c'est une application simple au cercles :
 - tirer alatoirement un triplet de points non aligns.
 - calculer le cercle passant par ces trois points.
 - accumuler le centre et le rayon

----------


## Al_th

Ca n'est qu'une proposition, sans doute pas du tout adapte, mais je propose tout de mme.

N'est il pas possible de crer des "formes" de test, de les appliquer sur tes points, et de dterminer une marge d'erreur ?

Je m'explique en images :
http://img220.imageshack.us/i/formes.jpg/

En gros, le but serait de crer des formes qui se rapprochent le plus de tout tes points ( par exemple les 5 derniers ?), et a ce moment la de dterminer une marge d'erreur.

Par exemple, pour l'image du cercle de 5 points a droite au milieu, on essaye de le match avec une droite, on peut voir qu'il y a normment de points dcentrs (mme si tu fais passer la droite en plein centre, compar au cercle de gauche, pour lesquels le cercle passe beaucoup plus prt de tout les points).

De plus, pas besoin d'un cercle "ferm", 3 points suffisent pour faire le tri entre un cercle et une droite.

Enfin peut etre que c'est beaucoup trop lourd niveau traitement d'image, j'en sais rien, c'tait une ide comme ca...

Edit : je me rends compte que ma solution ressemble a une de celle propose plus haut, ne pas tenir compte de ce post donc, qui a une utilit proche du 0kelvin :<

----------


## Dovice

Bonjour, 

J'ai quelque peu avanc sur mon projet au cours de ces derniers jours...

Ce que j'ai fait :
-implementation des accumulateurs pour les cercles et le droites-dtection basique des cercles et droites base sur la valeur des angles et les distance entre les points ... par consquent j'arrive a liminer les transitions.-implmentation d'un "testeur" sous forme de paint qui rcupre les points du curseur souris tous les 100 ms
J'aurais cependant aim avoir quelques conseils pour la suite. J'aimerais un systme qui soit un peu plus robuste, notamment sur la dtection des formes sans me baser uniquement sur les angles et distances entre les points. Pour les cercles j'analyse galement la convexit du contour... Auriez vous d'autres pistes sur ce point?

J'ai de plus quelques soucis concernant mon analyse avec la transforme de hough pour les cercles. J'utilise la fonction dj ralise et fournie par OpenCV  savoir cvHoughCircles, cependant je ne sais pas bien comment la paramtrer, et le rsultat dpend beaucoup du flou appliqu a l'image pralablement via cvSmooth ... Mon problme est que d'une forme  l'autre, reprsentant un cercle, la valeur du flou doit alors changer pour bien dtecter un cercle. J'ai penser faire varier le flou mais cela multiplie mes calculs et ralentit alors le processus... Je n'ai pas vraiment d'autres ides la dessus. Une autre solution serait d'implmenter moi mme ma transforme de hough, mais je ne sais pas comment m'y prendre...

Enfin pour ce qui est d'acqurir des points toutes les 100ms, je n'ai pas rellement trouv de fonctions satisfaisantes, j'utilise la fonction clock(), mais pas trs prcise en ms, en tout cas qui ne me donne pas satisfaction, ou alors un sleep de 100 ms, mais qui n'est pas la bonne solution...

----------


## souviron34

> Enfin pour ce qui est d'acqurir des points toutes les 100ms, je n'ai pas rellement trouv de fonctions satisfaisantes, j'utilise la fonction clock(), mais pas trs prcise en ms, en tout cas qui ne me donne pas satisfaction, ou alors un sleep de 100 ms, mais qui n'est pas la bonne solution...


tu as la fonction que j'ai fournie dans les sources C _GetClock()_, en temps absolu  la microseconde..

----------


## Dovice

> tu as la fonction que j'ai fournie dans les sources C _GetClock()_, en temps absolu  la microseconde..


Je ne comprends pas trs bien comment l'utiliser pour de milisecondes... en clair je veux mettre une condition comme quoi toutes les 100ms je veux faire telle opration ...

----------


## souviron34

elle s'utilise comme _clock()_ sauf que le rsultat est en double et en units de secondes..

donc par exemple :



```

```

----------


## Dovice

j'ai plusieurs problmes en voulant utiliser ta fonction : 
- il ne trouve pas le <sys/time.h>- tval, timerclear et gettimeofday ne sont pas reconnus (je suppose que cela dcoule du premier problme ^^)

----------


## souviron34

peut-tre que tu es sur Win (et peut-tre Win64)..

Il faut voir le symbole par lequel a passe dans les #ifdef...

C'tait prvu pour Linux, Unix, et Win32..

----------


## Dovice

> peut-tre que tu es sur Win (et peut-tre Win64)..
> 
> Il faut voir le symbole par lequel a passe dans les #ifdef...
> 
> C'tait prvu pour Linux, Unix, et Win32..


Oui je suis effectivement sur Win, et plus prcisment Win32. Je travaille sous MVS 2010, peut tre qu'il me faut inclure un chemin spcial qui indique l'endroit d'une des librairies ou je ne sais quoi ...?

----------


## Nebulix

> sur la dtection des formes sans me baser uniquement sur les angles et distances entre les points.


 ::koi::  


> le rsultat dpend beaucoup du flou appliqu a l'image pralablement


  ::koi:: 



> Enfin pour ce qui est d'acqurir des points toutes les 100ms, je n'ai pas rellement trouv de fonctions satisfaisantes, j'utilise la fonction clock(), mais pas trs prcise en ms, en tout cas qui ne me donne pas satisfaction, ou alors un sleep de 100 ms, mais qui n'est pas la bonne solution...


Si tu veux tre prcis, je pense que c'est impossible sous Windows, qui fait ce qu'il veut quand il veut. ( Sous DOS ou W98, on pouvait bloquer les interruptions). 
La fonction QueryPerformanceCounter te permet de savoir quand tu fais qqch et de corriger dans certains cas.

----------

